A direct function (dfn, pronounced "dee fun") is an alternative way to define a function and operator (a higher-order function) in the programming language APL. A direct operator can also be called a dop (pronounced "dee op"). They were invented by John Scholes in 1996.[1] They are a unique combination of array programming, higher-order function, and functional programming, and are a major distinguishing advance of early 21st century APL over prior versions.
A dfn is a sequence of possibly guarded expressions (or just a guard) between, separated by or new-lines, wherein denotes the left argument and the right, and denotes recursion (function self-reference). For example, the function tests whether each row of is a Pythagorean triplet (by testing whether the sum of squares equals twice the square of the maximum).
The factorial function as a dfn:
The rules for dfns are summarized by the following "reference card":
| guard | |||
| left argument | left operand | error-guard | |
| right argument | right operand | default left argument | |
| self-reference | self-reference | shy result |
A dfn is a sequence of possibly guarded expressions (or just a guard) between, separated by or new-lines.
Names assigned in a dfn are local by default, with lexical scope.
denotes the left function argument and the right; denotes the left operand and the right. If occurs in the definition, then the dfn is a dyadic operator; if only occurs but not, then it is a monadic operator; if neither or occurs, then the dfn is a function.
The special syntax is used to give a default value to the left argument if a dfn is called monadically, that is, called with no left argument. The is not evaluated otherwise.
denotes recursion or self-reference by the function, and denotes self-reference by the operator. Such denotation permits anonymous recursion.
Error trapping is provided through error-guards, . When an error is generated, the system searches dynamically through the calling functions for an error-guard that matches the error. If one is found, the execution environment is unwound to its state immediately prior to the error-guard's execution and the associated expression of the error-guard is evaluated as the result of the dfn.
Additional descriptions, explanations, and tutorials on dfns are available in the cited articles.[2] [3] [4] [5]
The examples here illustrate different aspects of dfns. Additional examples are found in the cited articles.
The function adds to (or
\sqrt{-1}
The significance of this function can be seen as follows:
Moreover, analogous to that monadic ⇔ (negate) and monadic ⇔ (reciprocal), a monadic definition of the function is useful, effected by specifying a default value of 0 for : if, then ⇔ ⇔ .
3 j 4 ¯5.6 7.893J4 3J¯5.6 3J7.89
j 4 ¯5.6 7.890J4 0J¯5.6 0J7.89
sin← 1∘○ cos← 2∘○ Euler←
Euler (¯0.5+?10⍴0) j (¯0.5+?10⍴0)1 1 1 1 1 1 1 1 1 1
The last expression illustrates Euler's formula on ten random numbers with real and imaginary parts in the interval
\left(-0.5,0.5\right)
The ternary construction of the Cantor set starts with the interval [0,1] and at each stage removes the middle third from each remaining subinterval:
l[0,1r]\to
| \left[0, | 1 |
| 3 |
\right]\cup\left[
| 2 | |
| 3 |
,1\right]\to
| \left[0, | 1 |
| 9 |
\right]\cup\left[
| 2 | , | |
| 9 |
| 1 | |
| 3 |
\right]\cup\left[
| 2 | , | |
| 3 |
| 7 | |
| 9 |
\right]\cup\left[
| 8 | |
| 9 |
,1\right]\to …
The Cantor set of order defined as a dfn:
Cantor 01 Cantor 11 0 1 Cantor 21 0 1 0 0 0 1 0 1 Cantor 31 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1
Cantor 0 to Cantor 6 depicted as black bars:
The function computes a bit vector of length so that bit (for and) is 1 if and only if is a prime.
10 10 ⍴ sieve 1000 0 1 1 0 1 0 1 0 00 1 0 1 0 0 0 1 0 10 0 0 1 0 0 0 0 0 10 1 0 0 0 0 0 1 0 00 1 0 1 0 0 0 1 0 00 0 0 1 0 0 0 0 0 10 1 0 0 0 0 0 1 0 00 1 0 1 0 0 0 0 0 10 0 0 1 0 0 0 0 0 10 0 0 0 0 0 0 1 0 0
b←sieve 1e9 ≢b1000000000 (10*⍳10) (+⌿↑)⍤0 1 ⊢b0 4 25 168 1229 9592 78498 664579 5761455 50847534
The last sequence, the number of primes less than powers of 10, is an initial segment of . The last number, 50847534, is the number of primes less than
109
\pi(109)=50847478
uses two different methods to mark composites with 0s, both effected using local anonymous dfns: The first uses the sieve of Eratosthenes on an initial mask of 1 and a prefix of the primes 2 3...43, using the insert operator (right fold). (The length of the prefix obtains by comparison with the primorial function .) The second finds the smallest new prime remaining in, and sets to 0 bit itself and bits at times the numbers at remaining 1 bits in an initial segment of . This second dfn uses tail recursion.
Typically, the factorial function is define recursively (as above), but it can be coded to exploit tail recursion by using an accumulator left argument:
Similarly, the determinant of a square complex matrix using Gaussian elimination can be computed with tail recursion:
A partition of a non-negative integer
n
v
v
P(n)
| n | |
| P(n)=\sum | |
| k=1 |
(-1)k+1[P(n-
| 1 | k(3k-1))+P(n- | |
| 2 |
| 1 | |
| 2 |
k(3k+1))]
derived from Euler's pentagonal number theorem. Written as a dfn:
pn 1042 pn¨ ⍳13 ⍝ OEIS A0000411 1 2 3 5 7 11 15 22 30 42 56 77
The basis step states that for, the result of the function is, 1 if ⍵ is 0 or 1 and 0 otherwise. The recursive step is highly multiply recursive. For example, would result in the function being applied to each element of, which are:
and requires longer than the age of the universe to compute (
7.57 x 1047
pn M 2003.973E12 0 ⍕ pn M 200 ⍝ format to 0 decimal places 3972999029388
This value of agrees with that computed by Hardy and Ramanujan in 1918.
The memo operator defines a variant of its operand function to use a cache and then evaluates it. With the operand the variant is:
Quicksort on an array works by choosing a "pivot" at random among its major cells, then catenating the sorted major cells which strictly precede the pivot, the major cells equal to the pivot, and the sorted major cells which strictly follow the pivot, as determined by a comparison function . Defined as a direct operator (dop) :
⍝ precedes ⍝ follows ⍝ equals 2 (×-) 8 8 (×-) 2 8 (×-) 8¯1 1 0
x← 2 19 3 8 3 6 9 4 19 7 0 10 15 14
(×-) Q x0 2 3 3 4 6 7 8 9 10 14 15 19 19
is a variant that catenates the three parts enclosed by the function instead of the parts per se. The three parts generated at each recursive step are apparent in the structure of the final result. Applying the function derived from to the same argument multiple times gives different results because the pivots are chosen at random. In-order traversal of the results does yield the same sorted array.
(×-) Q3 x┌────────────────────────────────────────────┬─────┬┐│┌──────────────┬─┬─────────────────────────┐│19 19││││┌──────┬───┬─┐│6│┌──────┬─┬──────────────┐││ │││││┌┬─┬─┐│3 3│4││ ││┌┬─┬─┐│9│┌┬──┬────────┐│││ │││││││0│2││ │ ││ ││││7│8││ │││10│┌──┬──┬┐││││ │││││└┴─┴─┘│ │ ││ ││└┴─┴─┘│ │││ ││14│15││││││ ││││└──────┴───┴─┘│ ││ │ │││ │└──┴──┴┘││││ ││││ │ ││ │ │└┴──┴────────┘│││ ││││ │ │└──────┴─┴──────────────┘││ │││└──────────────┴─┴─────────────────────────┘│ ││└────────────────────────────────────────────┴─────┴┘ (×-) Q3 x┌───────────────────────────┬─┬─────────────────────────────┐│┌┬─┬──────────────────────┐│7│┌────────────────────┬─────┬┐││││0│┌┬─┬─────────────────┐││ ││┌──────┬──┬────────┐│19 19││││││ │││2│┌────────────┬─┬┐│││ │││┌┬─┬─┐│10│┌──┬──┬┐││ ││││││ │││ ││┌───────┬─┬┐│6│││││ │││││8│9││ ││14│15││││ ││││││ │││ │││┌┬───┬┐│4│││ │││││ │││└┴─┴─┘│ │└──┴──┴┘││ ││││││ │││ │││││3 3│││ │││ │││││ ││└──────┴──┴────────┘│ ││││││ │││ │││└┴───┴┘│ │││ │││││ │└────────────────────┴─────┴┘││││ │││ ││└───────┴─┴┘│ │││││ │ ││││ │││ │└────────────┴─┴┘│││ │ ││││ │└┴─┴─────────────────┘││ │ ││└┴─┴──────────────────────┘│ │ │└───────────────────────────┴─┴─────────────────────────────┘
The above formulation is not new; see for example Figure 3.7 of the classic The Design and Analysis of Computer Algorithms. However, unlike the pidgin ALGOL program in Figure 3.7, is executable, and the partial order used in the sorting is an operand, the the examples above.
Dfns, especially anonymous dfns, work well with operators and trains. The following snippet solves a "Programming Pearls" puzzle:[6] given a dictionary of English words, here represented as the character matrix, find all sets of anagrams.
The algorithm works by sorting the rows individually, and these sorted rows are used as keys ("signature" in the Programming Pearls description) to the key operator to group the rows of the matrix. The expression on the right is a train, a syntactic form employed by APL to achieve tacit programming. Here, it is an isolated sequence of three functions such that ⇔, whence the expression on the right is equivalent to .
When an inner (nested) dfn refers to a name, it is sought by looking outward through enclosing dfns rather than down the call stack. This regime is said to employ lexical scope instead of APL's usual dynamic scope. The distinction becomes apparent only if a call is made to a function defined at an outer level. For the more usual inward calls, the two regimes are indistinguishable.[7]
For example, in the following function, the variable is defined both in itself and in the inner function . When calls outward to and refers to, it finds the outer one (with value) rather than the one defined in (with value):
which ' scope'lexical scope
The following function illustrates use of error guards:[7]
In APL, error number 5 is "length error"; error number 11 is "domain error"; and error number 0 is a "catch all" for error numbers 1 to 999.
The example shows the unwinding of the local environment before an error-guard's expression is evaluated. The local name is set to describe the purview of its following error-guard. When an error occurs, the environment is unwound to expose 's statically correct value.
Since direct functions are dfns, APL functions defined in the traditional manner are referred to as tradfns, pronounced "trad funs". Here, dfns and tradfns are compared by consideration of the function : On the left is a dfn (as defined above); in the middle is a tradfn using control structures; on the right is a tradfn using gotos and line labels.
Kenneth E. Iverson, the inventor of APL, was dissatisfied with the way user functions (tradfns) were defined. In 1974, he devised "formal function definition" or "direct definition" for use in exposition. A direct definition has two or four parts, separated by colons:
Direct definition was too limited for use in larger systems. The ideas were further developed by multiple authors in multiple works[13] [14] [15] [16] but the results were unwieldy. Of these, the "alternative APL function definition" of Bunda in 1987[15] came closest to current facilities, but is flawed in conflicts with existing symbols and in error handling which would have caused practical difficulties, and was never implemented. The main distillates from the different proposals were that (a) the function being defined is anonymous, with subsequent naming (if required) being effected by assignment; (b) the function is denoted by a symbol and thereby enables anonymous recursion.[12]
In 1996, John Scholes of Dyalog Limited invented direct functions (dfns).[1] [5] The ideas originated in 1989 when he read a special issue of The Computer Journal on functional programming.[17] He then proceeded to study functional programming and became strongly motivated ("sick with desire", like Yeats) to bring these ideas to APL.[5] He initially operated in stealth because he was concerned the changes might be judged too radical and an unnecessary complication of the language; other observers say that he operated in stealth because Dyalog colleagues were not so enamored and thought he was wasting his time and causing trouble for people. Dfns were first presented in the Dyalog Vendor Forum at the APL '96 Conference and released in Dyalog APL in early 1997.[1] Acceptance and recognition were slow in coming. As late as 2008, in Dyalog at 25,[18] a publication celebrating the 25th anniversary of Dyalog Limited, dfns were barely mentioned (mentioned twice as "dynamic functions" and without elaboration)., dfns are implemented in Dyalog APL,[7] NARS2000, and ngn/apl.[19] They also play a key role in efforts to exploit the computing abilities of a graphics processing unit (GPU).[20] [12]