Vector, the Journal of the British APL Association
- ️British APL Association
D: A functional subset of Dyalog APL
Dynamic functions and operators appeared in Dyalog APL/W Version 8.1 in early 1997. Since that time, experience has shown that their field of application is at least as wide as expected and ‘D-Fns’ have started appearing in many operational workspaces. A number of applications [1] have been written entirely in D-Fns and D-Ops and so we can consider them to constitute a small, complete sub-language within Dyalog APL. As the letter is one of the remaining few, not currently assigned to a programming language, we could call it: D.
D functions and operators are lightweight, faster but richer alternatives to the traditional ‘header-style’ container for the collection of APL expressions. D is described in detail in [2] but the following little ‘reference card’ is a summary:
| {⍺ Function ⍵} | {⍺⍺ Operator ⍵⍵} | : Guard |
| ⍺ Left argument | ⍺⍺ Left Operand | :: Error-Guard * |
| ⍵ Right argument | ⍵⍵ Right Operand | ⍺← Default larg |
| ∇ Self reference | ∇∇ Self Reference | 1:s← Shy result |
* Error-Guards are due to appear as an enhancement to Dyalog Version 9 and will be released initially via the web-based Dyalog Subscription Service.
The following example shows some of the look and feel of D:
display ⎕cr'display'
┌→─────────────────────────────────────────────────────────────────────┐
↓display←{⎕IO ⎕ML←0 ⍝ Boxed display of array. │
│ │
│ ⍺←1 ⋄ chars←⍺⊃'..''''|-' '┌┐└┘│─' ⍝ ⍺: 0-clunky, 1-smooth. │
│ │
│ tl tr bl br vt hz←chars ⍝ Top left, top right, ...│
│ │
│ box←{ ⍝ Box with type and axes. │
│ vrt hrz←(¯1+⍴⍵)⍴¨vt hz ⍝ Vert. and horiz. lines. │
│ top←(hz,'⊖→')[¯1↑⍺],hrz ⍝ Upper border with axis. │
│ bot←(⊃⍺),hrz ⍝ Lower border with type. │
│ rgt←tr,vt,vrt,br ⍝ Right side with corners.│
│ lax←(vt,'⌽↓')[¯1↓1↓⍺],¨⊂vrt ⍝ Left side(s) with axes, │
│ lft←⍉tl,(↑lax),bl ⍝ ... and corners. │
│ lft,(top⍪⍵⍪bot),rgt ⍝ Fully boxed array. │
│ } │
│ │
│ deco←{⍺←type open ⍵ ⋄ ⍺,axes ⍵} ⍝ Type and axes vector. │
│ axes←{(-2⌈⍴⍴⍵)↑1+×⍴⍵} ⍝ Array axis types. │
│ open←{(1⌈⍴⍵)⍴⍵} ⍝ Expose null axes. │
│ trim←{(~1 1⍷^⌿⍵=' ')/⍵} ⍝ Remove extra blank cols.│
│ type←{{(1=⍴⍵)⊃'+'⍵}∪,char¨⍵} ⍝ Simple array type. │
│ char←{⍬≡⍴⍵:hz ⋄ (⊃⍵∊'¯',⎕D)⊃'#~'}∘⍕ ⍝ Simple scalar type. │
│ │
│ { ⍝ Recursively box arrays: │
│ 0=≡⍵:' '⍵(⎕FMT ⍵)⍵(⊃⍵ ⍵∊⎕AV)⊃' -' ⍝ Simple scalar. │
│ 1 ⍬≡(≡⍵)(⍴⍵):'∇' 0 0 box ⎕FMT ⍵ ⍝ Object rep: ⎕OR. │
│ 1=≡⍵:(deco ⍵)box ⎕FMT open ⍵ ⍝ Simple array. │
│ ('∊'deco ⍵)box trim ⎕FMT ∇¨open ⍵ ⍝ Nested array. │
│ }⍵ │
│} │
└──────────────────────────────────────────────────────────────────────┘
Functional programming
D facilitates, but does not impose, writing in a purely functional style. To do justice to exactly what this means is beyond the scope of this note but see [3] and [4] for an introduction.
An indication that a piece of code is in the structured programming style is that it contains no branches. Likewise, an indication that a piece of code is in the pure, functional style is that it contains no variables. In this context, there is a distinction between a variable and a definition. A definition is a name, associated (just once) with an object, whereas a variable may be re-assigned any number of times. Pure functional programming does not admit this ‘destructive’ assignment or any of its variations: indexed, selective or modified assignment.
If we adhere to this restriction, we are entitled to pronounce
the symbol ← as
is, rather than gets, becomes, etc. The
display function, above, is an
example of such code.
There is a (possibly apocryphal) story that a great advance in
the field came when some computer scientists were trying to
teach programming to a group of geography students. The students
couldn’t understand the meaning of: I=I+1, and on reflection,
the teachers realized that they weren’t too sure either!
Enumeration of all possible D functions
If we were to list all possible D functions in order of complexity, each of the first six would be useful:
sink←{} ⍝ Discard unwanted value.
lev←{⍺} ⍝ Left argument.
dex←{⍵} ⍝ Right argument.
const←{0} ⍝ Return constant.
dup←{⍵ ⍵} ⍝ Duplicate.
link←{⍺ ⍵} ⍝ Left arg, right arg, pair.
const¨ provides the shortest (but not quickest) way
to return an array of values, the same shape as an arbitrary
array: {'woof'}¨102⍴'K'9.
Tail recursion vs iteration
D’s guard construct is sufficient to replace all the
usual control structures. People find this unsurprising for
:If :Else and
:Select, but
sometimes have difficulty with the iterative controls.
:For splits into two cases. If there is no
communication among the passes of the loop, it maps immediately
onto {…⍵}¨. The construct is recognised by the
interpreter and special-cased to re-use the D function stack
frame, which gives it the same slick performance as a tail call.
Otherwise, if there is some ‘accumulation’ of values by
successive passes, it maps onto ↑{…⍵}/.
:While and :Until, each contain an
implicit test for termination. In D, this test maps onto a guard at
the top or bottom of the function, where the ‘loop’ becomes a
tail-recursive call on the function. In this context, tail recursion
has been described as ‘looping with parameters’. Look at the
following equivalent versions of a function for the sum of the items
of a vector. (There are of course, easier ways to achieve this.)
| Traditional APL | D |
|---|---|
∇ rslt←sum nums
[1] rslt←0
[2] :While 0¨⍴nums
[3] rslt+←⊃nums
[4] nums←1↓nums
[5] :EndWhile
∇
|
sum←{
⍺←0
0=⍴⍵:⍺
(⍺+⊃⍵)∇ 1↓⍵
}
|
We sometimes seem reluctant to use recursion. To be fair, we may be worried by a perceived cost of stack allocation and at first find it difficult to distinguish between a ‘tail call’ and a ‘stack call’. In Dyalog, a tail call is by a small margin, the fastest way of ‘branching’! Look at the following two versions of factorial.
| Stack Call | Tail Call |
|---|---|
fact←{
⍵=1:1
⍵×∇ ⍵-1
}
|
fact←{
⍺←1
⍵=1:⍺
(⍵×⍺)∇ ⍵-1
}
|
Techniques
The rest of this note is devoted to a variety of techniques that
have been discovered while programming in D. References such as
[max parse], show [workspace function], where
examples of the technique can be found in sample workspaces
supplied with Dyalog Version 9.
Avoiding name clashes
APL’s ‘name clash problem’ can be largely avoided in D.
Traditional functions that do workspace administration tasks
such as function cross-referencing, must be careful that their
own local names do not obscure the global names in which they
are interested. This leads to the choosing of ‘nasty’ local
names: ∆_∆_fns __cr_list, etc. (The author has
been tempted to use obscene words for such names in locked
functions, reasoning that if a name clash did occur, the victim
would be unlikely to call to complain – but decency prevailed).
Names in D are localised dynamically. In the following function,
names and source are localised
after the evaluation of ⎕CR and
⎕NL and so do not obscure global homonyms.
wsdoc←{
names source←↓⍉↑{⍵(⎕CR ⍵)}¨↓⎕NL ⍵
...
}
[dfns attrib]
This technique is fine for simple tasks such as the above, but can become unwieldy for more complex ones, as it requires that all ‘external work’ be done before the first assignment. More generally, we can preserve an outer name-free environment as a function operand to an inner operator. This is one advantage of D’s static scope rules.
find←{
{⍎⍵}{ ⍝ 'external' operand.
local names←… ⍝ local names
…
vars←⍺⍺'⎕nl 2' ⍝ name list via operand.
vals←⍺⍺¨↓vars ⍝ values via operand.
…
}⍵
}
[dfns find]
Function pipelines
It is sometimes convenient to break up a large function into a
‘pipeline’ of smaller ones, where the result of each is passed
as argument to the next. In particular, this gives fine control
over the amount of workspace used, as large temporary
definitions may be localized more accurately. In some cases, the
indentation in a ‘raw’ pipeline of functions shows the structure
of the code better than does a succession of function names:
foo goo ….
{
… ∇ …
}∘{
… ∇ …
}¨ …
[dfns factors] [dfns stamps] [dfns wsdiff]
Initial left argument
One way to provide an initial (as opposed to default) left
argument, as an accumulator for a function, is to bind it at
definition time using composition. This delivers a slight
performance benefit, particularly in a recursive function, as
the body of the code no longer needs to test (⍺←…)
for the existence of the left argument. The sum
example above would become:
sum←0∘{
0=⍴⍵:⍺
(⍺+1↑⍵)∇ 1↓⍵
}
[max.parse]
‘Call me’
The ∇ or self token refers to its nearest enclosing brace pair. If we want a recursive call that ‘reaches’ out more than one level, it seems we are obliged to name the target function, solely in order to use its name for the call:
foo←{
{
foo ⍵ ⍝ recursive call on outer function.
} ⍵
}
An alternative is for the target function to pass a reference to itself as an operand to the inner function, which then becomes an operator:
{
∇{
⍺⍺ ⍵ ⍝ recursive call on outer function.
}⍵
}
The technique can be used to pass the function reference through
an arbitrary level of nesting. This means that we are not forced
to invent an artificial name for a function just in order to
recur. We name things only for elucidation and to avoid repeated
evaluation. Perhaps for this reason, defined operators seem to
occur more frequently in D than in traditional APL. [min
parse]
Complex guards
Finally, an obvious point: there is no limit to the complexity
of the guard expression to the left of the :. In
particular, it can include a D function call.
{
…
}⍵:{
…
[max unify]
References
-
minandmaxare sample workspaces supplied with Dyalog Version 9.0. -
Vector, Vol. 13.2, 88 “Dynamic Functions in Dyalog APL”
Available from dyalog.com/download/dfns.zip.
This rich text format file uses font “Dyalog Std TT”, from dyalog.com/download/dlogttst.zip [Ed: compatible with APL2741 as used on the Vector site.] - The Computer Journal, Vol. 32.2, April 1989.
- Bird, R. & Wadler, P. Introduction to Functional Programming, Prentice Hall, ISBN 0-13-484197-2