Content deleted Content added
→Multiple recursion: fixed wikilink to Cache (computing) |
m Open access bot: url-access updated in citation with #oabot. |
||
| (47 intermediate revisions by 23 users not shown) | |||
Line 1:
{{Short description|Alternate way to define a function in APL}}
{{redirect|Dfns|the political entity sometimes known as the Democratic Federation of Northern Syria|Autonomous Administration of North and East Syria}}
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 (programming language)|APL]]. A direct operator can also be called a '''dop''' (pronounced "dee op"). They were invented by [[John M. Scholes|John Scholes]] in 1996.<ref name=Scholes1996>{{cite journal|last=Scholes|first=John|title=Direct Functions in Dyalog APL|journal=Vector|volume=13|number=2|date=October 1996|url=http://www.dyalog.com/uploads/documents/Papers/dfns.pdf|access-date=16 September 2019}}</ref> 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 [[Guard (computer science)|guarded expressions]] (or just a guard) between {{code|{|apl}} and {{code|}|apl}}, separated by {{code|⋄|apl}} or new-lines, wherein {{code|⍺|apl}} denotes the left argument and {{code|⍵|apl}} the right, and {{code|∇|apl}} denotes [[Recursion (computer science)|recursion]] (function self-reference). For example, the function {{code|PT|apl}} tests whether each row of {{code|⍵|apl}} is a [[Pythagorean triplet]] (by testing whether the sum of squares equals twice the square of the maximum).
<
PT← {(+/⍵*2)=2×(⌈/⍵)*2}
PT 3 4 5
Line 16 ⟶ 18:
PT x
1 0 1 0 0 1
</syntaxhighlight>
{{Anchor|factorial}}
The [[factorial]] function as a dfn:
<
fact← {0=⍵:1 ⋄ ⍵×∇ ⍵-1}
fact 5
Line 27 ⟶ 29:
fact¨ ⍳10 ⍝ fact applied to each element of 0 to 9
1 1 2 6 24 120 720 5040 40320 362880
</syntaxhighlight>
== Description ==
The rules for dfns are summarized by the following "reference card":<ref name=refcard>{{citation|last=Scholes|first=John|title=Direct Functions Reference Card|date=1998–2019|url=http://dfns.dyalog.com/n_refcard|access-date=26 September 2019}}{{Dead link|date=February 2024 |bot=InternetArchiveBot |fix-attempted=yes }}</ref>
{| class="wikitable"
Line 56 ⟶ 57:
A dfn is a sequence of possibly [[Guard (computer science)|guarded expressions]] (or just a guard) between {{code|{|apl}} and {{code|}|apl}}, separated by {{code|⋄|apl}} or new-lines.
<
expression
guard: expression
guard:
</syntaxhighlight>
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 (computer science)|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.
Line 69 ⟶ 70:
The special syntax {{code|⍺←expression|apl}} 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 {{code|⍺←expression|apl}} is not evaluated otherwise.
{{code|∇|apl}} denotes [[
[[Exception handling|Error trapping]] is provided through error-guards, {{code|errnums::expression|apl}}. 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.<ref name=Scholes2001a>{{
== Examples ==
The examples here illustrate different aspects of dfns. Additional examples are found in the cited articles.<ref name=dfnsWS>{{citation|last=Scholes|first=John|title=Direct Functions Workspace|date=1998–2019|url=http://dfns.dyalog.com|access-date=2019-09-15}}</ref><ref name=APL1978/><ref name=history50>{{citation|last=Hui|first=Roger|author-link=Roger Hui|title=A History of APL in 50 Functions|date=27 November 2016|url=http://www.jsoftware.com/papers/50|access-date=17 September 2019}}</ref>
=== Default left argument ===
The function {{code|{⍺+0j1×⍵}|apl}} adds {{code|⍺|apl}} to {{code|0j1|apl}} ({{mvar|i}} or <math>\sqrt{-1}</math>) times {{code|⍵|apl}}.
<syntaxhighlight lang=apl>
3 {⍺+0j1×⍵} 4
3J4
Line 92 ⟶ 91:
1J¯2 1J¯1 1 1J1 1J2
2J¯2 2J¯1 2 2J1 2J2
</syntaxhighlight>
The significance of this function can be seen as follows:
{{
Moreover, analogous to that monadic {{code|-⍵|apl}}
<
j←{⍺←0 ⋄ ⍺+0j1×⍵}
Line 115 ⟶ 114:
Euler (¯0.5+?10⍴0) j (¯0.5+?10⍴0)
1 1 1 1 1 1 1 1 1 1
</syntaxhighlight>
The last expression illustrates [[Euler's formula]] on ten random numbers with real and imaginary parts in the interval <math>\left(-0.5,0.5\right)</math>.
Line 129 ⟶ 128:
<math>\left[0,\frac{1}{9}\right] \cup \left[\frac{2}{9},\frac{1}{3}\right] \cup \left[\frac{2}{3},\frac{7}{9}\right] \cup \left[\frac{8}{9},1\right] \to \cdots </math>
The Cantor set of order {{code|⍵|apl}} defined as a dfn:<ref name=Hui2016>{{citation|last=Hui|first=Roger|author-link=Roger Hui|title=APL Exercises|date=18 July 2016|url=http://www.jsoftware.com/papers/APL_exercises/|access-date=24 September 2019}}</ref>{{rp|§2.5}}
<
Cantor← {0=⍵:,1 ⋄ ,1 0 1 ∘.∧ ∇ ⍵-1}
Line 142 ⟶ 141:
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
</syntaxhighlight>
Cantor 0 to Cantor 6 depicted as black bars:
Line 151 ⟶ 150:
The function {{code|sieve ⍵|apl}} computes a bit vector of length {{code|⍵|apl}} so that bit {{code|i|apl}} (for {{code|0≤i|apl}} and {{code|i<⍵|apl}}) is 1 if and only if {{code|i|apl}} is a [[Prime number|prime]].<ref name=history50/>{{rp|§46}}
<
sieve←{
4≥⍵:⍵⍴0 0 1 1
Line 178 ⟶ 177:
(10*⍳10) (+⌿↑)⍤0 1 ⊢b
0 4 25 168 1229 9592 78498 664579 5761455 50847534
</syntaxhighlight>
The last sequence, the number of primes less than powers of 10, is an initial segment of {{OEIS2C|id=A006880}}. The last number, 50847534, is the number of primes less than <math>10^9</math>. It is called Bertelsen's number, memorably described by [[MathWorld]] as "an erroneous name erroneously given the erroneous value of <math>\pi(10^9) = 50847478</math>".<ref name=MathWorld>{{citation|last=Weisstein|first=Eric W.|title=Bertelsen's Number|publisher=MathWorld, A Wolfram Web Resource|url=http://mathworld.wolfram.com/BertelsensNumber.html|access-date=26 September 2019}}</ref>
{{code|sieve|apl}} 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 {{code|⌿|apl}} ([[
=== Tail recursion ===
Typically, the [[factorial]] function is define recursively (as [[#factorial|above]]), but it can be coded to exploit [[tail call|tail recursion]] by using an accumulator left argument:<ref name=fact>{{citation|last=Scholes|first=John|title=Factorial|date=1998–2019|journal=DFNS Workspace|url=http://dfns.dyalog.com/n_factorial.htm|access-date=20 September 2019}}</ref>
<syntaxhighlight lang=apl>
fac←{⍺←1 ⋄ ⍵=0:⍺ ⋄ (⍺×⍵) ∇ ⍵-1}
</syntaxhighlight>
Similarly, the [[determinant]] of a square complex matrix using [[Gaussian elimination]] can be computed with tail recursion:<ref name=det>{{citation|last=Scholes|first=John|title=Determinant|date=
<
det←{ ⍝ determinant of a square complex matrix
⍺←1 ⍝ product of co-factor coefficients so far
Line 200 ⟶ 198:
(⍺×⍵[i;j]ׯ1*i+j) ∇ ⍵[k~i;k~j] - ⍵[k~i;j] ∘.× ⍵[i;k~j]÷⍵[i;j]
}
</syntaxhighlight>
=== Multiple recursion ===
A [[Integer partition|partition]] of a non-negative integer <math>n</math> is a vector <math>v</math> of positive integers such that {{code|n {{=}} +⌿v|apl}}, where the order in <math>v</math> is not significant. For example, {{code|2 2|apl}} and {{code|2 1 1|apl}} are partitions of 4, and {{code|2 1 1|apl}} and {{code|1 2 1|apl}} and {{code|1 1 2|apl}} are considered to be the same partition.
The [[Partition function (number theory)|partition function]] <math>P(n)</math> counts the number of partitions. The function is of interest in [[number theory]], studied by [[Leonhard Euler|Euler]], [[G. H. Hardy|Hardy]], [[Srinivasa Ramanujan|Ramanujan]], [[Paul Erdős|Erdős]], and others. The recurrence relation
:<math>P(n)=\sum_{k=1}^n (-1)^{k+1}[P(n-\frac{1}{2}k(3k-1))+P(n-\frac{1}{2}k(3k+1))]</math>
derived from Euler's [[pentagonal number theorem]].<ref name=MathWorldP>{{citation|last=Weisstein|first=Eric W.|title=Partition Function P, equation 11|publisher=MathWorld, A Wolfram Web Resource|url=http://mathworld.wolfram.com/PartitionFunctionP.html|access-date=3 October 2019}}</ref> Written as a dfn:<ref name=history50/>{{rp|§16}}
<
pn ← {1≥⍵:0≤⍵ ⋄ -⌿+⌿∇¨rec ⍵}
rec ← {⍵ - (÷∘2 (×⍤1) ¯1 1 ∘.+ 3∘×) 1+⍳⌈0.5*⍨⍵×2÷3}
Line 220 ⟶ 217:
pn¨ ⍳13 ⍝ OEIS A000041
1 1 2 3 5 7 11 15 22 30 42 56 77
</syntaxhighlight>
The basis step {{code|1≥⍵:0≤⍵|apl}} states that for {{code|1≥⍵|apl}}, the result of the function is {{code|0≤⍵|apl}}, 1 if ⍵ is 0 or 1 and 0 otherwise. The recursive step is highly multiply recursive. For example, {{code|pn 200|apl}} would result in the function being applied to each element of {{code|rec 200|apl}}, 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
</syntaxhighlight>
and {{code|pn 200|apl}} requires longer than the [[age of the universe]] to compute (<math>7.57\times10^{47}</math> function calls to itself).<ref name=history50/>{{rp|§16}} The compute time can be reduced by [[memoization]], here implemented as the direct operator (higher-order function) {{code|M|apl}}:
<
M←{
f←⍺⍺
Line 243 ⟶ 240:
0 ⍕ pn M 200 ⍝ format to 0 decimal places
3972999029388
</syntaxhighlight>
This value of {{code|pn M 200|apl}} agrees with that computed by Hardy and Ramanujan in 1918.<ref>{{citation|last1=Hardy|first1=G.H.|last2=Ramanujan|first2=S.|title= Asymptotic Formulæ in Combinatory Analysis|journal=Proceedings of the London Mathematical Society|volume=17|number=2|date=1918|url=http://ramanujan.sirinudi.org/Volumes/published/ram36.pdf|access-date=24 December 2019}}</ref>
The memo operator {{code|M|apl}} defines a variant of its operand function {{code|⍺⍺|apl}} to use a [[Cache (computing)|cache]] {{code|T|apl}} and then evaluates it. With the operand {{code|pn|apl}} the variant is:
<
{T←(1+⍵)⍴¯1 ⋄ {1≥⍵:0≤⍵ ⋄ ¯1≢T[⍵]:⊃T[⍵] ⋄ ⊃T[⍵]←⊂-⌿+⌿∇¨rec ⍵}⍵}
</syntaxhighlight>
=== Direct operator (dop) ===
[[Quicksort]] on an array {{code|⍵|apl}} 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 {{code|⍺⍺|apl}}. Defined as a direct [[Higher-order function|operator]] (dop) {{code|Q|apl}}:
<
Q←{1≥≢⍵:⍵ ⋄ (∇ ⍵⌿⍨0>s)⍪(⍵⌿⍨0=s)⍪∇ ⍵⌿⍨0<s←⍵ ⍺⍺ ⍵⌷⍨?≢⍵}
Line 265 ⟶ 263:
(×-) Q x
0 2 3 3 4 6 7 8 9 10 14 15 19 19
</syntaxhighlight>
{{code|Q3|apl}} is a variant that catenates the three parts enclosed by the function {{code|⊂|apl}} 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 {{code|Q3|apl}} to the same argument multiple times gives different results because the pivots are chosen at random. [[Tree traversal#In-order,
<
Q3←{1≥≢⍵:⍵ ⋄ (⊂∇ ⍵⌿⍨0>s)⍪(⊂⍵⌿⍨0=s)⍪⊂∇ ⍵⌿⍨0<s←⍵ ⍺⍺ ⍵⌷⍨?≢⍵}
Line 297 ⟶ 295:
│└┴─┴──────────────────────┘│ │ │
└───────────────────────────┴─┴─────────────────────────────┘
</syntaxhighlight>
The above formulation is not new; see for example Figure 3.7 of the classic ''The Design and Analysis of Computer Algorithms''.<ref name=AHU>{{citation|last1=Aho|first1=A.V.|author-link=Alfred Aho|last2=Hopcroft|first2=J.E.|author-link2=John Hopcroft|last3=Ullman|first3=J.D.|author-link3=Jeffrey Ullman|title=The Design and Analysis of Computer Algorithms|date=1974|publisher=Addison-Wesley|bibcode=1974daca.book.....A }}</ref>
=== Dfns with operators and trains ===
Dfns, especially anonymous dfns, work well with operators and trains. The following snippet solves a "Programming Pearls" puzzle:<ref name=Bentley1983>{{cite journal|last=Bentley|first=Jon|title=Programming Pearls|journal=[[Communications of the ACM]]|volume=26|number=8 and 9|date=August 1983}}</ref> given a dictionary of English words, here represented as the character matrix {{code|a|apl}}, find all sets of anagrams.
<syntaxhighlight lang=apl>
a {⍵[⍋⍵]}⍤1 ⊢a ({⍵[⍋⍵]}⍤1 {⊂⍵}⌸ ⊢) a
pats apst ┌────┬────┬────┐
Line 320 ⟶ 317:
east aest
seta aest
</syntaxhighlight>
The algorithm works by sorting the rows individually ({{code|{⍵[⍋⍵]}⍤1 ⊢a|apl}}), and these sorted rows are used as keys ("signature" in the Programming Pearls description) to the ''key'' operator {{code|⌸|apl}} to group the rows of the matrix.<ref name=APL1978/>{{rp|§3.3}} 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 {{code|(f g h) ⍵|apl}}
=== Lexical scope ===
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 [[Scope (computer science)#Lexical scoping|lexical scope]] instead of APL's usual [[Scope (computer science)#Dynamic scoping|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.<ref name=Dyalog17.1>{{cite book|last=Dyalog|title=Dyalog Programming Reference Guide, version 17.1, Dfns & Dops, pp. 133-147|publisher=Dyalog Ltd.|date=15 August 2019|url=http://docs.dyalog.com/17.0/Dyalog%20Programming%20Reference%20Guide.pdf|access-date=30 September 2019}}</ref>{{rp|p.137}}
For example, in the following function {{code|which|apl}}, the variable {{code|ty|apl}} is defined both in {{code|which|apl}} itself and in the inner function {{code|f1|apl}}. When {{code|f1|apl}} calls outward to {{code|f2|apl}} and {{code|f2|apl}} refers to {{code|ty|apl}}, it finds the outer one (with value {{code|'lexical'|apl}}) rather than the one defined in {{code|f1|apl}} (with value {{code|'dynamic'|apl}}):
<
which←{
ty←'lexical'
Line 340 ⟶ 336:
which ' scope'
lexical scope
</syntaxhighlight>
=== Error-guard ===
The following function illustrates use of error guards:<ref name=Dyalog17.1/>{{rp|p.139}}
<
plus←{
tx←'catch all' ⋄ 0::tx
Line 360 ⟶ 355:
2 3 plus 3 4⍴5 ⍝ can't add vector to matrix
catch all
</syntaxhighlight>
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.
Line 367 ⟶ 362:
== Dfns ''versus'' tradfns ==
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 {{code|sieve|apl}}: On the left is a dfn (as defined [[#sieve|above]]); in the middle is a tradfn using [[Control flow|control structures]]; on the right is a tradfn using [[goto]]s ({{code|→|apl}}) and [[Label (computer science)|line label]]s.
{| class="wikitable"
|-
| {{sxhl|1=
sieve←{
4≥⍵:⍵⍴0 0 1 1
Line 383 ⟶ 375:
{r<q←b⍳1:b⊣b[⍵]←1 ⋄ b[q,q×⍸b↑⍨⌈n÷q]←0 ⋄ ∇ ⍵,q}p
}
|2=apl}}
| {{sxhl|1=
∇ b←sieve1 n;i;m;p;q;r
:If 4≥n ⋄ b←n⍴0 0 1 1 ⋄ :Return ⋄ :EndIf
Line 404 ⟶ 388:
b[p]←1
∇
|2=apl}}
| {{sxhl|1=
∇ b←sieve2 n;i;m;p;q;r
→L10 ⍴⍨ 4<n ⋄ b←n⍴0 0 1 1 ⋄ →0
Line 427 ⟶ 406:
b[p]←1
∇
|2=apl}}
|}
Line 440 ⟶ 419:
* [[Recursion (computer science)|Recursion]] in a dfn is effected by invoking {{code|∇|apl}} or {{code|∇∇|apl}} or its name; recursion in a tradfn is effected by invoking its name.
* [[Control flow|Flow control]] in a dfn is effected by guards and function calls; that in a tradfn is by control structures and {{code|→|apl}} (goto) and line labels.
*
* A dfn returns on
* The simpler flow control in a dfn makes it easier to detect and implement [[Tail call|tail recursion]] than in a tradfn.
* A dfn may call a tradfn and ''vice versa''; a dfn may be defined in a tradfn, and ''vice versa''.
== History ==
[[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.<ref name=directdef>{{citation|last=Iverson|first=Kenneth E.|author-link=Kenneth E. Iverson|title=Elementary Functions|chapter=Chapter 10, Formal Function Definition|date=1974|publisher=IBM Corporation|chapter-url=http://www.jsoftware.com/papers/DirectDef.htm|access-date=18 September 2019}}</ref> A direct definition has two or four parts, separated by colons:
<syntaxhighlight lang=apl>
name : expression
name : expression0 : proposition : expression1
</syntaxhighlight>
Within a direct definition, {{code|⍺|apl}} denotes the left argument and {{code|⍵|apl}} the right argument. In the first instance, the result of {{code|expression|apl}} is the result of the function; in the second instance, the result of the function is that of {{code|expression0|apl}} if {{code|proposition|apl}} evaluates to 0, or {{code|expression1|apl}} if it evaluates to 1. Assignments within a direct definition are [[Scope (computer science)#Dynamic scoping|dynamically local]]. Examples of using direct definition are found in the 1979 [[Turing Award]] Lecture<ref name=TOT>{{cite journal|last=Iverson|first=Kenneth E.|author-link=Kenneth E. Iverson|title=Notation as a Tool of Thought|journal=[[Communications of the ACM]]|volume=23|number=8|date=August 1980|url=https://www.jsoftware.com/papers/tot.htm|access-date=8 April 2016|doi=10.1145/358896.358899|pages=444–465|doi-access=free}}</ref> and in books and application papers.<ref name=Iverson1976>{{cite book|last=Iverson|first=Kenneth E.|author-link=Kenneth E. Iverson|title=Elementary Analysis|publisher=APL Press|date=1976}}</ref><ref name=Orth1976>{{cite book|last=Orth|first=D.L.|title=Calculus in a New Key|publisher=APL Press|date=1976}}</ref><ref name=Hui1987>{{cite journal|last=Hui|first=Roger|author-link=Roger Hui|title=Some Uses of { and }|journal=APL 87 Conference Proceedings|date=May 1987|url=http://www.jsoftware.com/papers/from.htm|access-date=15 April 2016}}</ref><ref name=McDonnell1987>{{citation|last=McDonnell|first=E.E.|title=Life: Nasty, Brutish, and Short|journal=APL 87 Conference Proceedings|date=May 1987|url=http://www.jsoftware/papers/EEM/life.htm|access-date=6 October 2019}}{{Dead link|date=May 2023 |bot=InternetArchiveBot |fix-attempted=yes }}</ref><ref name=APL1978>{{
Direct definition was too limited for use in larger systems. The ideas were further developed by multiple authors in multiple works<ref name=opfns>{{citation|last=Iverson|first=Kenneth E.|author-link=Kenneth E. Iverson|title=Operators and Functions|journal=Research Report Number #RC7091|date=26 April 1978|publisher=IBM Corporation|url=http://www.jsoftware.com/papers/opfns.htm|access-date=2019-09-19}}</ref>{{rp|§8}}<ref name=IversonWooster1981>{{
In 1996, [[John M. Scholes|John Scholes]] of Dyalog Limited invented direct functions (dfns).<ref name=Scholes1996/><ref name=Scholes2018v/><ref name=Scholes2018t/> The ideas originated in 1989 when he read a special issue of ''[[The Computer Journal]]'' on functional programming.<ref name=Wadler>{{
== References ==
Line 462 ⟶ 440:
==External links==
*
{{APL programming language}}
| |||