Dynamic Functions in Dyalog APL
Vector 13:2, page 88
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 88
A Dynamic Function (D-Fn) is an experimental function definition style which bridges the gap between named function expressions such as rank←⍴∘⍴ and APL’s conventional ‘header’ style definition. Dynamic Functions are so called because they can be defined ‘on the fly’ at run time.
Simple Expressions¶
The simplest form of a D-Fn is: {expr} where expr is an APL expression containing '⍺'s and '⍵'s representing the left and right argument of the function respectively. For example:
{(+/⍵)÷⍴⍵} 1 2 3 4 ⍝ Arithmetic mean
2.5
2 {(⍺-⎕io)+⍳⍵-⍺-1} 5 ⍝ Sequence ⍺ ... ⍵
2 3 4 5
{{⍵*0.5}+/⍵*2} 3 4 ⍝ Pythagoras (Note inner D-Fn).
5
A D-Fn can be used in any function context ...
... and of course, assigned a name:
D-Fns are ambivalent. Their right (and if present, left) arguments are evaluated irrespective of whether these are subsequently referenced within the function body.
Guards¶
A guard is a boolean-single valued expression followed by ':'. A simple expression can be preceded by a guard, and any number of guarded expressions can occur separated by '⋄'s.
Guards are evaluated in turn (left to right) until one of them yields a 1. Its corresponding expr is then evaluated as the result of the D-Fn. A guard is equivalent to an If-Then-Else or Switch-Case construct.
A final simple expr can be thought of as a default case:
The '⋄'s in the previous examples can be replaced by newlines. During input, automatic indentation reminds us that we are typing into a D-Fn. If the closing '}' is the first character typed in a line, the interpreter’s input mechanism ‘snaps’ it back a tab stop before echoing it. For readability, extra null phrases '⋄ ⋄ ⋄ ...' can be included. The parity example above becomes:
D-Fns can be reviewed using the system editor: )ed or ⎕FX/⎕CR, and note that you can comment them in the normal way using '⍝'.
The following example interprets a dice throw:
Local Definition¶
The final piece of D-Fn syntax is the local definition. An expression whose principal function is a simple or vector assignment introduces a name which is local to the D-Fn. The name is shadowed dynamically as the assignment is executed. As we shall see later, this mechanism can be used to define local nested D-Fns.
mean←{ ⍝ Arithmetic mean.
sum←+/⍵
num←⍴⍵
sum÷num
}
roots ← { ⍝ Real roots of quadratic.
a b c←⍵ ⍝ Coefficients.
d←(b*2)-4×a×c ⍝ Discriminant.
d<0: ⍬ ⍝ No roots
d=0: -b÷2×a ⍝ One root
d>0: (-b+¯1 1×d*0.5)÷2×a ⍝ Two roots
}
A nuance: the special syntax ⍺←expr is executed only if the D-Fn is called with no left argument. This is equivalent to, but neater than:
in a conventionally defined function.
Recursion¶
D-Fns use recursion in place of iteration. Reference to the current function can of course use the function’s name explicitly. However because we allow unnamed D-Fns to be incorporated in larger APL expressions, we also need a special symbol to represent self-reference. '∇' does the job.
'∇' has a further small advantage in that a recursive function can be renamed without having to locate and change all the explicit self references within the function body.
fact←{ ⍝ Factorial.
⍵≤1: 1
⍵×fact ⍵-1 ⍝ !
}
{0<⍵:∇ ⍵-1}1e6 ⍝ Benchmark: iterate a million times.
⍝ *
gcd←{ ⍝ Euclid's greatest common divisor.
⍵=0: ⍺
⍵ ∇ ⍵|⍺ ⍝ *
}
fib←{ ⍝ ⍵'th Fibonacci number.
1≥⍵: ⍵
+/∇¨⍵-1 2 ⍝ !
}
ack←{ ⍝ Ackermann's function.
⍺=0: ⍵+1
⍵=0: (⍺-1)∇ 1 ⍝ *
(⍺-1)∇ ⍺ ∇ ⍵-1 ⍝*!
}
osc ← { ⍝ Oscillate - probably returns 1.
1=⍵: 1
2|⍵: ∇ 1+3×⍵ ⍝ *
∇ ⍵÷2 ⍝ *
}
These examples show that D-Fns contain a minimum of syntactic baggage - allowing the underlying algorithms to ‘shine through’. For example, compare the osc example above with the equivalent coding using control structures:
A happy consequence of reducing syntax is that the interpreter has less work to do. In the current experimental implementation, D-Fns significantly out-perform their conventionally defined counterparts.
Tail Recursion¶
In the previous examples, the recursive calls marked (⍝*) are said to be tail-recursive whereas those marked (⍝!) are not. A call is tail-recursive if its result is passed back unchanged to its own calling environment.
Tail recursion can be implemented in the interpreter by branching to, rather than calling, the current function. This delivers a substantial performance benefit, both in terms of execution time and workspace used.
It is often possible to turn a ‘stack-recursive’ D-Fn into tail-recursive form by accumulating the result on the way into, rather than on the way out of, the recursion. In general, this technique employs an auxiliary function which takes an accumulating parameter. APL’s infix syntax is particularly suited to this technique as we can use the left argument exclusively to accumulate result-so-far, and the right argument to specify work-outstanding. The calculation then consists of moving work from the incoming right argument into the left argument of the next recursive call.
fact←{ ⍝ Tail recursive Factorial.
1 {
⍵≤1: ⍺
(⍺×⍵)∇ ⍵-1 ⍝ *
} ⍵
}
fib←{ ⍝ Tail recursive Fibonacci.
1 0 {
⍵=0: 1↓⍺
(1↓⍺,+/⍺)∇ ⍵-1 ⍝ *
} ⍵
}
We can simplify the coding by expressing the auxiliary function as a dyadic case of the outer monadic function:
fact←{
⍺←1
⍵≤1: ⍺
(⍺×⍵)∇ ⍵-1 ⍝ *
}
sieve←{ ⍝ Sieve of Eratosthenes.
⍺←⍬ ⍝ No primes yet.
next←1↑⍵ ⍝ Next prime and ...
mask←×next|⍵ ⍝ Mask of non-multiples.
∧/1↓mask:⍺,⍵ ⍝ No multiples, finished.
(⍺,next)∇ mask/⍵ ⍝ Sieve out further primes.
⍝ *
}
sieve 1↓⍳20 ⍝ Sieve primes from 2 .. 20
2 3 5 7 11 13 17 19
It’s easy to check if a call is tail recursive by tracing it. Tail recursion appears to re-use the current trace window by branching back to the first line of the function, whereas a stack-recursive call pops up a new trace window.
D-Ops: Dynamic Operators¶
The operator equivalent of a D-Fn refers to its left and right operand using '⍺⍺' and '⍵⍵' respectively. A D-Op is distinguished from a D-Fn by the presence of either of these symbols anywhere in the definition. A D-Op containing only '⍺⍺'s is monadic, whereas one which contains at least one '⍵⍵', is dyadic.
Note: in these and following examples, ⎕ml migration level is set to 3. In particular, ⊃ means mix and ↑ means first.
else←{ ⍝ Condition f else g ...
⍺: ⍺⍺ ⍵ ⍝ True: apply left operand.
⍵⍵ ⍵ ⍝ False: apply right operand.
}
inner←{ ⍝ Inner product.
⍺⍺/⊃(↓⍺)∘.⍵⍵↓⍉⍵
}
The following example makes use of a coding technique, well established in Dyalog APL, of setting an undefined left argument to be the identity function. The following line then applies its function operands with the same valency as the derived function itself.
with←{ ⍝ Both operands applied.
⍺←{⍵} ⍝ Larg defaults to identity fn.
(⍺ ⍺⍺ ⍵)(⍺ ⍵⍵ ⍵) ⍝ Return 2-element vector.
}
For recursive D-Ops, there are two kinds of self reference: '∇' refers to the current derived function, that is, the operator bound with its operand(s). This is by far the most frequently used form of self reference. Occasionally however, we might need a recursive reference to the operator itself and then we would use: '∇∇', although a simple example doesn’t spring to mind!
pow←{ ⍝ Explicit function power.
0=⍺: ⍵ ⍝ Apply function operand ⍺ times.
(⍺-1)∇ ⍺⍺ ⍵ ⍝ ⍺⍺ ⍺⍺ ⍺⍺ ... ⍵ ⍝ *
}
until←{ ⍝ Conditional function power.
⍵⍵ ⍵: ⍵ ⍝ Until ⍵⍵,
∇ ⍺⍺ ⍵ ⍝ Apply ⍺⍺ ⍺⍺ ... ⍝ *
}
limit←{ ⍝ Function power limit.
z←⍺⍺ ⍵ ⍝ Apply operand until
z≡⍵: ⍵ ⍝ ... it has no effect.
∇ z ⍝ Else, repeat. ⍝ *
}
perv←{ ⍝ Scalar pervasion, apply ...
1=≡⍺ ⍵: ⍺ ⍺⍺ ⍵ ⍝ ... fn between simple scalars.
⍺ ∇¨⍵ ⍝ ... else, traverse each arg. ⍝ !
}
saw←{ ⍝ Simple-array-wise.
2>≡⍵: ⍺⍺ ⍵ ⍝ Simple, apply operand.
∇¨⍵ ⍝ Nested, visit each subarray ⍝ !
}
A contrived use of operator self reference '∇∇', would be to re-code the last example:
saw←{ ⍝ Simple-array-wise.
2>≡⍵: ⍺⍺ ⍵ ⍝ Simple, apply operand.
⍺⍺ ∇∇¨⍵ ⍝ Nested, visit each subarray ⍝ !
}
Example: Pythagorean numbers¶
The following sequence shows an example of combining Dynamic Functions and Operators in an attempt to find Pythagorean triangles (3 4 5)(5 12 13) ...
sqrt←{⍵*0.5} ⍝ Square root.
sqrt 9 16 25
3 4 5
hyp←{sqrt+/⊃⍵*2} ⍝ Hypotenuse of triangle.
hyp(3 4)(4 5)(5 12)
5 6.403124237 13
intg←{⍵=⌊⍵} ⍝ Whole number?
intg 2.5 3 4.5
0 1 0
pyth←{intg hyp ⍵} ⍝ Pythagorean pair?
pyth(3 4)(4 9)(5 12)
1 0 1
pairs←{,⍳⍵ ⍵} ⍝ Pairs of numbers 1..⍵.
pairs 3
1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
filter←{(⍺⍺ ⍵)/⍵} ⍝ Op: ⍵ filtered by ⍺⍺.
pyth filter pairs 12 ⍝ Pythagorean pairs 1..12
3 4 4 3 5 12 6 8 8 6 9 12 12 5 12 9
So far, so good, but we seem to have some duplicates: for example, (6 8) is just double (3 4).
rpm←{ ⍝ Relatively prime?
⍵=0:⍺=1 ⍝ C.f. Euclid's gcd.
⍵ ∇ ⍵|⍺
}/¨ ⍝ Note the /¨
rpm(2 4)(3 4)(6 8)(16 27)
0 1 0 1
rpm filter pyth filter pairs 20
3 4 4 3 5 12 8 15 12 5 15 8
We can use an operator to combine the tests:
and←{ ⍝ Lazy parallel 'And'.
mask←⍺⍺ ⍵ ⍝ Left predicate selects...
mask\⍵⍵ mask/⍵ ⍝ args for right predicate.
}
pyth and rpm filter pairs 20
3 4 4 3 5 12 8 15 12 5 15 8
Better, but we still have some duplicates: (3 4) (4 3).
less←{</⊃⍵}
less(3 4)(4 3)
1 0
less and pyth and rpm filter pairs 50
3 4 5 12 7 24 8 15 9 40 12 35 20 21 28 45
A larger example¶
The display function uses nested local D-Fns. The details of the code are not important - the example is included to show the appearance of a larger function.
display←{⎕IO ⎕ML←0 3 ⍝ Boxed display of array.
0=≡⍵:{ ⍝ Simple scalar ...
fmt←,⍕⍵ ⍝ ... formatted
num←0=↑0⍴⍵ ⍝ Numeric?
bar←num⊃'- ' ⍝ Underscore if char.
⊃' 'fmt bar ⍝ Formatted scalar.
}⍵
tax←{ ⍝ Type of axis:
axes←1+×⍵ ⍝ 1:null 2:non-null.
size←2⌈⍴⍵ ⍝ Size of result.
(-size)↑axes ⍝ 0:extra padding.
}⍴⍵
box←{ ⍝ ∇ Boxed char array.
vrt hrz←'|-'{
1↓⍵⍴⍺ ⍝ Vert and horiz lines.
}¨⍴⍵
top←'-⊖→'[¯1↑tax],hrz ⍝ Upper border with shape.
bot←⍺,hrz ⍝ Lower border with type.
rgt←'.|',vrt,'''' ⍝ Right border, corners.
lvex←'|⌽↓'[¯1↓tax],¨⊂vrt ⍝ Left border, shape
lft←⍉'.',(⊃lvex),'''' ⍝ ... and corners.
lft,(top⍪⍵⍪bot),rgt ⍝ Fully boxed array.
}
xnulls←{ ⍝ ∇ Expose nulls.
(1⌈⍴⍵)↑⍵
}
1=≡⍵:{ ⍝ Simple array.
type←{ ⍝ Type:
∧/⍵:'~' ⍝ ~: all numeric.
∨/⍵:'+' ⍝ +: mixed.
'-' ⍝ -: all char.
}0=↑0⍴⊂,⍵
type box ⎕FMT xnulls ⍵ ⍝ Box simple array.
}⍵
subs←⎕FMT ∇¨xnulls ⍵ ⍝ Formatted subarrays. ⍝ !
mask←∧⌿subs=' ' ⍝ Extra blank cols
'∊'box(~1 1⍷mask)/subs ⍝ Nested array
}
display 'a'(1 0 2⍴⊂⍳0)(2'b')
.→---------------------.
| ..→---------. .→--. |
| a ↓⌽ .⊖. .⊖. | |2 b| |
| - || |0| |0| | '+--' |
| || '~' '~' | |
| ''∊---------' |
'∊---------------------'
Summary¶
The syntax of a D-Fn / D-Op is shown in the railway diagram:
.-→--------→----. ⍝ Null phrase,
|-→--LDEF←EXPR-| ⍝ Local definition,
|-→-GUARD:EXPR-| ⍝ Guarded result expression,
-→-{-+-→--------EXPR-+-}-→- ⍝ Unguarded result expression,
'-←--------⋄--←-' ⍝ ... separated by ⋄-s.
| LDEF: | Definition local to the D-Fn using simple or vector assignment. |
| GUARD: | Expression which evaluates to a Boolean single. |
| EXPR: | Arbitrary APL expression: the result of the D-Fn. |
Following special characters are substituted:
⍺: |
Function Left Argument. (⍺←... if left argument omitted.) |
⍵: |
Function Right Argument. |
∇: |
Function (and Derived Function) Self reference. |
⍺⍺: |
Operator Left Operand. |
⍵⍵: |
Operator Right Operand. |
∇∇: |
Operator Self reference. |
The phrases are evaluated in turn until an unguarded EXPR, or one whose guard evaluates to 1, is encountered. The corresponding EXPR is then evaluated as the result of the D-Fn.
Conclusion¶
D-Fns give us the opportunity to combine the power of expression of APL with an alternative, and in some circumstances, more convenient functional framework.
They encourage (but don’t compel), the programming of ‘pure’ functions. There is evidence to suggest that coding in such a style produces more reliable software.
D-Fns provide true local functions. They encourage the use of sub-functions which may otherwise be avoided owing to a (perceived) degradation in performance or code readability. For example, it is often tempting to replace a call on a small function applied under each (¨) by embedding the code directly in the calling line and peppering it with '¨'s or '∘'s.
Using D-Fns in this situation improves both speed and readability. For example:
Implementation Status¶
D-Fns are currently implemented in Dyalog on an experimental basis. While some issues are yet to be resolved, the results so far look encouraging. Coding examples such as those included in this article show that they have a reasonably wide application. Measurements of their performance are particularly pleasing.
These ideas were first presented in the Dyadic Vendor Forum at APL96 where they appeared to meet with general approval. Depending on the reaction of the APL community at large, we hope to include many of them in a forthcoming release.