Direct function
A direct function is an alternative way to define a function and operator in the programming language APL. A direct operator can also be called a dop. They were invented by John Scholes in 1996. 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 between, separated by or new-lines, wherein denotes the left argument and the right, and denotes recursion. For example, the function tests whether each row of is a Pythagorean triplet.
PT←
PT 3 4 5
x
4 5 3
3 11 6
5 13 12
17 16 8
11 12 4
17 15 8
PT x
1 0 1 0 0 1
The factorial function as a dfn:
fact←
fact 5
120
fact¨ ⍳10 ⍝ fact applied to each element of 0 to 9
1 1 2 6 24 120 720 5040 40320 362880
Description
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 between, separated by or new-lines.
expression
guard: expression
guard:
The expressions and/or guards are evaluated in sequence. A guard must evaluate to a 0 or 1; its associated expression is evaluated if the value is 1. A dfn terminates after the first unguarded expression which does not end in assignment, or after the first guarded expression whose guard evaluates to 1, or if there are no more expressions. The result of a dfn is that of the last evaluated expression. If that last evaluated expression ends in assignment, the result is "shy"—not automatically displayed in the session.
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.
Examples
The examples here illustrate different aspects of dfns. Additional examples are found in the cited articles.Default left argument
The function adds to times.3 4
3J4
∘.⍨ ¯2+⍳5
¯2J¯2 ¯2J¯1 ¯2 ¯2J1 ¯2J2
¯1J¯2 ¯1J¯1 ¯1 ¯1J1 ¯1J2
0J¯2 0J¯1 0 0J1 0J2
1J¯2 1J¯1 1 1J1 1J2
2J¯2 2J¯1 2 2J1 2J2
The significance of this function can be seen as follows:
Moreover, analogous to that monadic ⇔ and monadic ⇔ , a monadic definition of the function is useful, effected by specifying a default value of 0 for : if, then ⇔ ⇔.
j←
3 j 4 ¯5.6 7.89
3J4 3J¯5.6 3J7.89
j 4 ¯5.6 7.89
0J4 0J¯5.6 0J7.89
sin← 1∘○
cos← 2∘○
Euler←
Euler j
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.
Single recursion
The ternary construction of the Cantor set starts with the interval and at each stage removes the middle third from each remaining subinterval:The Cantor set of order defined as a dfn:
Cantor←
Cantor 0
Cantor 1
1 0 1
Cantor 2
1 0 1 0 0 0 1 0 1
Cantor 3
1 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 is 1 if and only if is a prime.
sieve←
10 10 ⍴ sieve 100
0 0 1 1 0 1 0 1 0 0
0 1 0 1 0 0 0 1 0 1
0 0 0 1 0 0 0 0 0 1
0 1 0 0 0 0 0 1 0 0
0 1 0 1 0 0 0 1 0 0
0 0 0 1 0 0 0 0 0 1
0 1 0 0 0 0 0 1 0 0
0 1 0 1 0 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0 0
b←sieve 1e9
≢b
1000000000
⍤0 1 ⊢b
0 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. It is called Bertelsen's number, memorably described by MathWorld as "an erroneous name erroneously given the erroneous value of ".
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 . 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.
Tail recursion
Typically, the factorial function is define recursively, but it can be coded to exploit tail recursion by using an accumulator left argument:fac←
Similarly, the determinant of a square complex matrix using Gaussian elimination can be computed with tail recursion:
det←
Multiple recursion
A partition of a non-negative integer is a vector of positive integers such that, where the order in is not significant. For example, and are partitions of 4, and and and are considered to be the same partition.The partition function counts the number of partitions. The function is of interest in number theory, studied by Euler, Hardy, Ramanujan, Erdős, and others. The recurrence relation
derived from Euler's pentagonal number theorem. Written as a dfn:
pn ←
rec ←
pn 10
42
pn¨ ⍳13 ⍝ OEIS A000041
1 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:
rec 200
199 195 188 178 165 149 130 108 83 55 24 ¯10
198 193 185 174 160 143 123 100 74 45 13 ¯22
and requires longer than the age of the universe to compute. The compute time can be reduced by memoization, here implemented as the direct operator :
M←
pn M 200
3.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:
Direct operator (dop)
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 :Q←
⍝ 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 x
0 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←
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.