Loops, Folds and Tuples

For-loops
Given an initial state defined by a number of variables, a for-loop iterates through its argument array modifying the state.

    A←... ⋄ B←... ⋄ C←...       ⍝ initial state
    :For item :In items         ⍝ iterating through array "items"
        A←A ... item            ⍝ new value for A depending on item
        C←C ... A ... item      ⍝ new value for C depending on A and item
        ...                     ⍝ state updated
    :EndFor
    A B C                       ⍝ final state

In the above example the state comprises just three variables. In general, it may be arbitrarily complex, as can the interactions between its various components within the body of the loop.

Dfns
Dfns don’t have for-loops. Instead, we can use reduction (or “fold”) with an accumulating vector “tuple” of values representing the state. Here is the D-equivalent of the above code:

    ⊃{                      ⍝ next item is ⍺
        (A B C)←⍵           ⍝ named items of tuple ⍵
        A∆←A ... ⍺          ⍝ new value for A depending on item ⍺
        C∆←C ... A∆ ... ⍺   ⍝ new value for C depending on A∆ and item ⍺
        ...                 ⍝ ...
        A∆ B C∆             ⍝ "successor" tuple (A and C changed)
    }/(⌽items),⊂A B C       ⍝ for each item and initial state tuple A B C

In this coding, the accumulating tuple arrives as the right argument (⍵) of the operand function, with the next “loop item” on the left (⍺). Notice how the items vector is reversed (⌽items) so that the items arrive in index-order in the right-to-left reduction.

If you prefer your accumulator to be on the left, you can replace the primitive reduction operator (/) with Phil Last’s foldl operator, which also presents its loop items in index-order:

    foldl←{⊃⍺⍺⍨/(⌽⍵),⊂⍺}    ⍝ fold left

then:

    A B C {                 ⍝ final state from initial state (left argument)
        (A B C)←⍺           ⍝ named items of tuple ⍺
        A∆←A ... ⍵          ⍝ new value for A depending on item ⍵
        C∆←C ... A∆ ... ⍵   ⍝ new value for C depending on A∆ and item ⍵
        A∆ B C∆             ⍝ successor tuple (A and C changed)
    } foldl items

If the number of elements in the state tuple is large, it can become unwieldy to name each on entry and exit to the operand function. In this case it simplifies the code to name the indices of the tuple vector, together with an at operator to denote the items of its successor:

    T ← (...) (...) ...         ⍝ intitial state tuple T
    A B C D ... ← ⍳⍴T           ⍝ A B C D ... are tuple item "names"

    T {                         ⍝ final state from initial state (left argument)
        A∆←(A⊃⍺) ... ⍵          ⍝ new value for A depending on item ⍵
        C∆←(C⊃⍺) ... A∆ ... ⍵   ⍝ new value for C depending on A∆ and item ⍵
        A∆ C∆(⊣at A C)⍺         ⍝ successor tuple (A and C changed)
    } foldl items

where:

    at←{A⊣A[⍵⍵]←⍺ ⍺⍺(A←⍵)[⍵⍵]}   ⍝ (⍺ ⍺⍺ ⍵) at ⍵⍵ in ⍵

There is some discussion about providing a primitive operator @ for at in Dyalog V16.

Examples
Function kk illustrates naming tuple elements (S E K Q) at the start of the operand function.
Function scc accesses tuple elements using named indices (C L X x S) and an at operator.

Tuples: a postscript
We might define a “tuple” in APL as a vector in which we think of each item as having a name, rather than an index position.

    bob         ⍝ Tuple: name gender age
┌───┬─┬──┐
│Bob│M│39│
└───┴─┴──┘

    folk        ⍝ Vector of tuples
┌──────────┬────────────┬──────────┬────────────┬─
│┌───┬─┬──┐│┌─────┬─┬──┐│┌───┬─┬──┐│┌─────┬─┬──┐│
││Bob│M│39│││Carol│F│31│││Ted│M│31│││Alice│F│32││ ...
│└───┴─┴──┘│└─────┴─┴──┘│└───┴─┴──┘│└─────┴─┴──┘│
└──────────┴────────────┴──────────┴────────────┴─

    ↓⍉↑ folk    ⍝ Tuple of vectors
┌─────────────────────────┬────────┬───────────────┐
│┌───┬─────┬───┬─────┬─   │MFMF ...│39 31 31 32 ...│
││Bob│Carol│Ted│Alice│ ...│        │               │
│└───┴─────┴───┴─────┴─   │        │               │
└─────────────────────────┴────────┴───────────────┘

    ⍪∘↑¨ ↓⍉↑ folk   ⍝ Tuple of matrices
┌─────┬─┬──┐
│Bob  │M│39│
│Carol│F│31│
│Ted  │M│31│
│Alice│F│32│
 ...   . ..
└─────┴─┴──┘

APLers sometimes talk about “inverted files”. In this sense, a “regular” file is a vector-of-tuples and an inverted file (or more recently: “column store”) is a tuple-of-vectors (or matrices).

Type Comments

I’ve taken to commenting the closing brace of my inner dfns with a home-grown type notation pinched from the Functional Programming community:

    dref←{                  ⍝ Value for name ⍵ in dictionary ⍺ 
        names values←⍺      ⍝ dictionary pair
        (names⍳⊂⍵)⊃values   ⍝ value corresponding to name ⍵
    }                       ⍝ :: Value ← Dict ∇ Name

I keep changing my mind about whether the result type should be to the left (Value ← ...) or to the right (... → Value). The FP crowd favours → Value but I’m coming around to Value ← because:

* In contrast to (say) Haskell, APL’s function/argument sequences associate right.
* Value ← mirrors the result pattern in a tradfn header and so looks familiar.
* The type of function composition f∘g is simpler this way round.

Such comments serve as an aide-mémoire when I later come to read the code though, with some ingenuity, the notation might possibly be extended to a more formal system, which could have value to a compiler or code-checker. We would need:

Glyphs for Dyalog’s three primitive atomic data types. For no particularly good reason, I’ve been using:

# number
' character
. ref

Glyphs for a few generic (polymorphic) types. These could be just regular lower-case letters a b c … though I currently prefer greek letters:

⍺ ∊ ⍳ ⍴ ⍵ ...

Some constructors for type expressions. This is the most contentious part. For what it’s worth, I’ve been using:

::  is of type ...
∇  function
∇∇  operator
←  returns
[⍺] vector of ⍺s
{⍺} optional left argument ⍺

For example:

foo :: ⍵ ← {⍺} ∇ ⍵

implies:
- foo is an ambi-valent function whose
- result is of the same type () as its right argument and whose
- optional left argument may be of a different type ().

I can abstract/name type expressions with (capitalised) identifiers using :=. For example:

Dict   := [Name][Value]        ⍝ dictionary name and value vectors
Eval   := Expr ← Dict ∇ Expr   ⍝ expression reduction
List ⍵ := '∘' | ⍵ (List ⍵)     ⍝ recursive pairs. See
list
Name   := ⍞                    ⍝ primitive type: character vector

The type: character vector ['] is used so frequently that the three glyphs fuse into: . This means that a vector-of-character-vectors, also a common type, is [⍞].

Primitive and derived function types.
If we’re not too nit-picky and ignore issues such as single extension and rank conformability, we can give at least hints for the types of some primitive functions and operators.

 ⍳ :: # ← ⍺ ∇ ⍺              ⍝ dyadic index-of
 ⍴ :: ⍺ ← [#] ∇ ⍺            ⍝ reshape (also take, transpose, ...)

The three forms of primitive composition have interesting types:

∘ :: ⍴ ← {⍺} (⍴ ← {⍺} ∇ ⍳) ∇∇ (⍳ ← ∇ ⍵ ) ⍵     ⍝ {⍺}f∘g ⍵
:: ⍴ ←                 ⍺ ∇∇ (⍴ ← ⍺ ∇ ⍵ ) ⍵   ⍝ A∘g ⍵
:: ⍴ ←      ((⍴ ← ⍺ ∇ ⍵) ∇∇ ⍵ )⍺             ⍝ (f∘B)⍵

It follows that:

f :: ⍴ ← {⍺} ∇ ⍳
g :: ⍳ ←     ∇ ⍵
=> f∘g :: ⍴ ← {⍺} ∇ ⍵          ⍝ intermediate type ⍳ cancels out

and for trains:

A :: ⍳                  ⍝ A is an array of type ⍳
f :: ⍳ ← {⍺} ∇ ⍵
g :: ⍴ ← {⍳} ∇ ∊
h :: ∊ ← {⍺} ∇ ⍵
=> f g h :: ⍴ ← {⍺} ∇ ⍵        ⍝ fgh fork
=> A g h :: ⍴ ←     ∇ ⍵        ⍝ Agh fork
=>   g h :: ⍴ ← {⍺} ∇ ⍵        ⍝ gh atop

For a more substantial example, search function joy for :: and := in a recent download of dfns.dws.

Muse:
This notation is not yet complete or rigorous enough to be of much use to a compiler but there may already be enough to allow the writing of a dfn, which checks its own and others internal consistency. In the long term, if a notation similar to this evolved into something useful, it might be attractive to allow optional type specification as part of the function definition: without the comment symbol:

    dref←{                  ⍝ Value for name ⍵ in dictionary ⍺ 
        names values←⍺      ⍝ dictionary pair
        (names⍳⊂⍵)⊃values   ⍝ value corresponding to name ⍵
    } :: Value ← Dict ∇ Name

Name Colouring for Dfns

APL is sometimes criticised because expressions that include names cannot, in general, be parsed without knowing whether the names represent functions or variables. For example, the name thing in the expression thing⍳3 could reference an array (in which case the is dyadic) or it could reference a function (making the monadic).

An APL expression becomes completely parsable if we distinguish each name with one of four colours, depending on the “kind” of its referent: array, function, monadic operator, dyadic operator. Now, with a bit of practice, we can at least parse thing⍳3 vs thing⍳3 without recourse to the definition of thing. Notice how kind differs slightly from APL’s name-class, which does not distinguish monadic from dyadic operators.

Names whose definitions are external to the code under consideration and so cannot be classified would be given a distinct colour, say red, which would at least draw attention to them. Colouring a number of interdependent functions at the same time should help with such issues.

Name-colouring can co-exist with the more superficial token-colouring ( green for comments and so forth) though we would probably want to configure the two schemes separately.

There’s a related argument for colouring parentheses to show the kind of value they contain: (~∘(⊂'')). This would mean that we could always determine the valency of a function call, or the kind of a hybrid token, such as /, by looking at the colour of the single token immediately to its left. Finally, we should probably kind-colour curly braces: {}, {⍺⍺ ⍵}, {⍵⍵ ⍵}.

Yeah but how?

In the following, where appropriate, “function” is a shorthand for “function or operator”.

Most generally, we want to process a number of definitions at the same time, so that inter-function references can be coloured. Such a set of functions may be considered as internal definitions in an anonymous outer function so, without loss of generality, we need consider only the case of a single multi-line nested function.

A function can be viewed as a tree, with nested subfunctions as subtrees. The definitions at each lexical level in the function comprise the information stored at each node of the tree.

The colouring process traverses the tree, accumulating a dictionary of (name kind) pairs at each level. At a particular level, definitions are processed in the same order as they would be executed, so that the (name kind) entries from earlier definitions are available to inform later expressions. Visiting each node before traversing its subtrees ensures that outer dictionary entries are available to lexically inner functions. Prefixing dictionary entries for inner functions ensures that a left-to-right search (à la dyadic iota) finds those names first, thus modelling lexical name-shadowing.

Each assignment expression adds one or more names to the dictionary. The kind of the assignment is inferred by looking at the defining expression to the right of the assignment arrow. This sounds heavy, but if we examine the expression from right-to-left then we can often stop after examining very few tokens. For example, an arbitrarily long expression ending in (… function array) must, if it is syntactically correct, reduce to an array value, while (… function function) must be a function (train). A sequence in braces {…} resolves to a function, monadic operator or dyadic operator, depending only on whether there are occurrences of ⍺⍺ or ⍵⍵ at its outermost level.

This approach, while relatively simple, is not perfect. It takes no account of the order in which names are defined relative to their being referenced. The assumption is that all definitions at an outer level are available to its inner levels. The following small function illustrates the problem:

    {
        M{A}      ⍝ this A correctly coloured function
        N{A}⍵     ⍝ this A should be coloured unclassified
        A←÷          ⍝ A defined as a function
        M N          ⍝ application of function to array
    }

It remains to be seen whether this would be a problem in practice or whether, if name-colouring proved popular, people might adjust their code to avoid such anomalies. The problem does not occur if we avoid re-using the same name for items of different kinds at the same lexical level – which IMHO is not a bad rule, anyway.

Implementation Status

I would like to experiment with name-kind colouring for the dfns code samples on the Dyalog website.

This project is under way, but has rather a low priority and so keeps stalling. In addition, I keep wavering between processing the tokens as a list with tail calling and the dictionary as an accumulating left argument, or in more classic APL style as a vector, developing parallel vectors for lexical depth and masks for assignment arrow positions and expression boundaries, etc.

In the meantime, here is an artist’s impression of what name- and bracket- coloured code might look like, with colours: array, function, dyadic-operator.

    eval{
        stk I(op ops)←⍵
        op in⊃⍺:⍺ prt stk I((dref op)cat ops)
        f(fr rr)f rstk
        c{op≡⍵~' '}
        c'dip ':⍺('*⌷'rgs{prt rr I(f cat fr ops)})
        ...

Notice how functions stand out from their arguments. For example, at the start of the third line: op in⊃⍺:, it is clear that in is a function taking ⊃⍺ (first of alpha) as right argument and op as left argument, rather than a monadic function op taking in⊃⍺ (in pick of alpha) as right argument. Other interpretations of the uncoloured expression op in⊃⍺: include:

    op in⊃⍺:    op in is a vector (array), so is pick.
    op in⊃⍺:    both op and in are monadic function calls, so is first.
    op in⊃⍺:    in is a monadic operator with array operand op.
    op in⊃⍺:    in is a dyadic operator with function operands op and .

I’m keen to hear any feedback and suggestions about name-colouring for dfns. What d’ya think?

Foo, Shmoo

“We do not realize what tremendous power the structure of an habitual language has. It is not an exaggeration to say that it enslaves us through the mechanism of s[emantic] r[eactions] and that the structure which a language exhibits, and impresses upon us unconsciously, is automatically projected upon the world around us.”
—Korzybski (1930) in Science & Sanity p. 90

I’m trying to train myself to choose nouns as names for my functions, in the hope that doing so will help to free me from the procedural mindset, which was pervasive when I learned to program. In those days, coding concentrated more or less exclusively on the manipulation of state and only rarely on the construction of definitions. In saying this, I’m distinguishing procedures, which legitimately deal in state, from functions, which don’t. Transitive verbs: print, init, reverse(vt), … make good names for procedures.

Many of APL’s primitive monadic functions have nouns as names: floor, reciprocal, reverse(n), shape, …

Except this doesn’t quite work. Each of these names seems to need an “of” when applied to an argument, where the of seems to bind to the word that follows it:

   ⌊÷blah   ⍝ "floor of reciprocal of blah"

I’ve seen dyadic iota documented as index-of, though this grates a bit as “index of” isn’t a noun phrase in English. In fact, as far as I know, all of the romance languages would parse Richard of York as Richard (of York), where (of York) is a noun phrase in the genitive case: York’s Richard; Ricardus Eboracum. Nobody seems to parse it (Richard of) York.

So much for that idea for a blog post; ho hum; back to real work.

Then Nick Nickolov found a Wikipedia entry that suggested: “Some languages, such as the Cariban languages, can be said to have a possessed case, used to indicate the other party (the thing possessed) in a possession relationship”. So the (Richard of) parsing would work in one of the Cariban languages and isn’t therefore a property of any deep structure of language, per se.

Now when I see ceiling, I can still think of it as a noun, but in the possessed case. To emphasise this, for the rest of this posting, I’ll write my function names with a back-tick inflection to represent the case: reverse` meaning reverse-of.

   ⌊÷blah   ⍝ floor` reciprocal` blah

… and when reading my code, I can vocalise the ending with a slight [əv] or [ə] sound as in “Land’v plenty”, “Bagguh chips, please”, “Floor’v reciprocal’v blah”.

But what about dyadic functions? Glad you asked. The left argument of a function (arrays are naturally nouns) can be seen as a noun acting as determiner, technically a noun adjunctcoffee tablebicycle thiefcube root, noun adjunct, … Thus: 2-residue`, N-take`, zilde-reshape`⎕AV-index`

Practising this discipline has been quite illuminating: it has pushed me towards left argument currying. I now mentally parse ¯2⌽V as (¯2⌽)V the ((neg-two)-rotation`) V, where neg qualifies two, which in turn qualifies rotation`.

But surely 2+3 is just a symmetrical expression with respect to its arguments? Well yes, but we could also parse it as follows: Starting from the monadic successor` function 1∘+, the curried dyadic version 1+ would be the one-successor` and so 2+3 is the two-successor` three.

Now, how should we incorporate operators and their operands into this scheme? “The reverse` each` V“, where each` is functioning as a determiner?

PS: Choosing nouns for the names of functions shouldn’t be confused with J’s excellent taxonomy of language components using parts of speech, in which functions are labelled “verbs”.

PPS: Functions reverse`, successor`, shape`, … could also be seen as properties of their argument. A number N has many properties: its successor, its square-root, its floor, ceiling, prime-factorisation vector, … This is beginning to sound a bit like OO…

Musings on Reduction

In one man’s humble opinion, reduction () is the Queen of Operators.

Each (¨) comes a close second, but doesn’t get the cigar because each can be written in terms of reduction.

Two special cases are of interest: reduction along axes of length 1 (or reduction of a scalar) and reduction along axes of length 0.

With a length-1 axis (or scalar), the operand function is not applied (+⌿'A' → 'A'). This can be useful as an implicit no-op – see DFS video on YouTube.

With a length-0 axis, a primitive operand returns its right identity item – but only if one is defined (⌊⌿⍬). Otherwise: DOMAIN ERROR.

Another way to think about the 0-length axis case is that a right identity item (if there is one) is catenated to the argument prior to the reduction. Functional Programming languages tend to define reduction in this way by supplying an explicit initial value (ival) to the reduction:

    fold fn ival [] = ival
    fold fn ival (x:xs) = fn x (fold fn ival xs)

We can write such a variant of in APL, supplying the initial value as right operand ⍵⍵:

      fold ← {⍺⍺⌿⍵⍪⍵⍵}        ⍝ right operand ⍵⍵ is initial value

      × fold 1 ⊢2 3 4         ⍝ same as regular ×⌿
24

      {⍺×⍵}fold 1 ⊢2 3 4      ⍝ non-primitive operand function
24

      {⍺×⍵}fold 1 ⊢⍬          ⍝ initial value returned for empty argument
1

Whilst it doesn’t provide the no-op trick for length-1 axes, fold gives us better control for null cases than does primitive reduction, which relies on the single prototypical item of its argument array:

      ⊢mat ← 2 3 ∘.+ 0(0 0)
┌─┬───┐
│2│2 2│
├─┼───┤
│3│3 3│
└─┴───┘

Notice the discontinuity in the depth of the result with regular +⌿ as the number of rows reaches 0:

      +⌿ 2↑mat
┌─┬───┐
│5│5 5│
└─┴───┘

      +⌿ 1↑mat
┌─┬───┐
│2│2 2│
└─┴───┘

      +⌿ 0↑mat              ⍝ Eh?
0 0

Supplying the variant with a prototypical row produces a more uniform convergence:

      +fold 0(0 0) ⊢2↑mat
┌─┬───┐
│5│5 5│
└─┴───┘

      +fold 0(0 0) ⊢1↑mat
┌─┬───┐
│2│2 2│
└─┴───┘

      +fold 0(0 0) ⊢0↑mat   ⍝ Ah!
┌─┬───┐
│0│0 0│
└─┴───┘

A similar discontinuity can be seen even for axes of length 1, with non-scalar primitive operand functions:

      ⊢mat ← 3 3⍴⍳9
1 2 3
4 5 6
7 8 9

Now:

      ,⌿ 3↑mat              ⍝ join reduction
┌─────┬─────┬─────┐
│1 4 7│2 5 8│3 6 9│
└─────┴─────┴─────┘

      ,⌿ 2↑mat
┌───┬───┬───┐
│1 4│2 5│3 6│
└───┴───┴───┘

      ,⌿ 1↑mat              ⍝ Tsk!
1 2 3

      ,⌿ 0↑mat              ⍝ Bah!
DOMAIN ERROR

But:

      ,fold(⊂⍬) ⊢3↑mat
┌─────┬─────┬─────┐
│1 4 7│2 5 8│3 6 9│
└─────┴─────┴─────┘

      ,fold(⊂⍬) ⊢2↑mat
┌───┬───┬───┐
│1 4│2 5│3 6│
└───┴───┴───┘

      ,fold(⊂⍬) ⊢1↑mat      ⍝ Ooh!
┌─┬─┬─┐
│1│2│3│
└─┴─┴─┘

      ,fold(⊂⍬) ⊢0↑mat      ⍝ Aah!
┌┬┬┐
││││
└┴┴┘

Although we have no specific plans to do so, it is conceivable that this definition of fold could be introduced as a variant of primitive reduction:

        nums ← ⍠(⊂⍬)        ⍝ possible variant for numeric reduction

      ,⌿nums 1↑mat          ⍝ Ooh!
┌─┬─┬─┐
│1│2│3│
└─┴─┴─┘
      ,⌿nums 0↑mat          ⍝ Aah!
┌┬┬┐
││││
└┴┴┘
      ,/nums 3 1↑mat        ⍝ Mmm! reduction along last axis
┌─┬─┬─┐
│1│4│7│
└─┴─┴─┘

Notice that the left and right arguments of a reduction’s operand function need not be of the same kind. Using an informal type notation:

      ⌿ :: (⍺ ∇ ⍵ → ⍵) ∇∇ [⍺]⍪⍵ → ⊂⍵

which, given an argument of uniform kind, collapses to:

      ⌿ :: (⍺ ∇ ⍺ → ⍺) ∇∇ [⍺] → ⊂⍺

I hope to say more about this style of polymorphic type notation in a future posting. In the meantime, the significant point is only that, in the general case, the operand function is of “kind” (⍺ ∇ ⍵ → ⍵), which means that the kind of its left argument may differ from that of its right argument and result. See more discussion on this idea in the notes for foldl in dfns.dws.

Selective Expression Tracing

Operator trace from dfns.dws is a simple and low-tech tool for displaying intermediate results of functions, during the evaluation of an expression. For example, what’s going on here?

      (+⌿ ÷ ≢) 1 2 3 4
2.5

We can guess that the above fork is computing the average of the right argument. To see how this works:

      )copy dfns trace
...

⍝ Rename to reduce clutter

      t ← trace

⍝ Bind each "tine" of the fork with t to see what's happening

      (+⌿t ÷t ≢t) 1 2 3 4
≢  1 2 3 4  =>  4
+⌿  1 2 3 4  =>  10
10  ÷  4  =>  2.5
2.5

⍝ But how is that +⌿ reduction evaluated?

      (+t⌿ ÷ ≢) 1 2 3 4
3  +  4  =>  7
2  +  7  =>  9
1  +  9  =>  10
2.5

As a second example, what does the atop (~⍷) do in the following function to remove superfluous '.' characters from its argument?

      {('··'(~⍷)⍵)/⍵} 'squeeze·····me'
squeeze·me

      {('··'(~⍷)t⍵)/⍵} 'squeeze·····me'
··  ~⍷  squeeze·····me  =>  1 1 1 1 1 1 1 0 0 0 0 1 1 1
squeeze·me

…and so forth. Notice how t can be injected to the right of any of the functions in an expression.

For more examples, see the notes for trace.