Direct function: Difference between revisions

Revision as of 05:14, 26 December 2020

Latest revision as of 12:55, 28 May 2025

(20 intermediate revisions by 15 users not shown)

Line 1:

{{Short description|Alternate way to define a function in APL}}

{{Use dmy dates|date=December 2020}}

{{redirect|Dfns|the political entity sometimes known as the Democratic Federation of Northern Syria|RojavaAutonomous 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.

Line 10:

1

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

Line 32:

== 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 77:

== 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=15 September 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{{sqrt|−1}}}-1}</math>) times {{code|⍵|apl}}.

<syntaxhighlight lang=apl>

Line 88:

¯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

</syntaxhighlight>

The significance of this function can be seen as follows:

{{quoteblockquote|Complex numbers can be constructed as ordered pairs of real numbers, similar to how integers can be constructed as ordered pairs of natural numbers and rational numbers as ordered pairs of integers. For complex numbers, {{code|{⍺+0j1×⍵}|apl}} plays the same role as {{code|-|apl}} for integers and {{code|÷|apl}} for rational numbers.<ref name=Hui2016/>{{rp|§8}}}}

Moreover, analogous to that monadic {{code|-⍵|apl}} ⇔ {{code|0-⍵|apl}} (''negate'') and monadic {{code|÷⍵|apl}} ⇔ {{code|1÷⍵|apl}} (''reciprocal''), a monadic definition of the function is useful, effected by specifying a default value of 0 for {{code|⍺|apl}}: if {{code|j←{⍺←0 ⋄ ⍺+0j1×⍵}|apl}}, then {{code|j ⍵|apl}} ⇔ {{code|0 j ⍵|apl}} ⇔ {{code|0+0j1×⍵|apl}}.

Line 181:

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&nbsp;3...43, using the ''insert'' operator {{code|⌿|apl}} ([[Fold (higher-order function)|right fold]]). (The length of the prefix obtains by comparison with the [[primorial]]|primorial function]] {{code|×⍀p|apl}}.) The second finds the smallest new prime {{code|q|apl}} remaining in {{code|b|apl}} ({{code|q←b⍳1|apl}}), and sets to 0 bit {{code|q|apl}} itself and bits at {{code|q|apl}} times the numbers at remaining 1 bits in an initial segment of {{code|b|apl}} ({{code|⍸b↑⍨⌈n÷q|apl}}). This second dfn uses tail recursion.

=== Tail recursion ===

Line 201:

=== Multiple recursion ===

A [[PartitionInteger (number theory)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

Line 256:

⍝ 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

Line 265:

</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, (LNR)|In-order traversal]] of the results does yield the same sorted array.

<syntaxhighlight lang=apl>

Q3←{1≥≢⍵:⍵ ⋄ (⊂∇ ⍵⌿⍨0>s)⍪(⊂⍵⌿⍨0=s)⍪⊂∇ ⍵⌿⍨0<s←⍵ ⍺⍺ ⍵⌷⍨?≢⍵}

Line 297:

</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> However, unlike the [[Pidgin code|pidgin]] [[ALGOL]] program in Figure 3.7, {{code|Q|apl}} is executable, and the partial order used in the sorting is an operand, the {{code|(×-)|apl}} the examples above.<ref name=APL1978/>

=== Dfns with operators and trains ===

Line 303:

<syntaxhighlight lang=apl>

a {⍵[⍋⍵]}⍤1 ⊢a ({⍵[⍋⍵]}⍤1 {⊂⍵}⌸ ⊢) a

pats apst ┌────┬────┬────┐

spat apst │pats│teas│star│

teas aest │spat│sate│ │

sate aest │taps│etas│ │

taps apst │past│seat│ │

etas aest │ │eats│ │

past apst │ │tase│ │

seat aest │ │east│ │

eats aest │ │seta│ │

tase aest └────┴────┴────┘

star arst

east aest

seta aest

</syntaxhighlight>

Line 322:

=== 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–147133-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}}):

Line 365:

{| class="wikitable"

|- bgcolorstyle="vertical-align:top; background-color:#ffffff;"

| {{sxhl|1=

|-

|- bgcolor="#ffffff"

| <pre>

sieve←{

4≥⍵:⍵⍴0 0 1 1

Line 377 ⟶ 375:

{r<q←b⍳1:b⊣b[⍵]←1 ⋄ b[q,q×⍸b↑⍨⌈n÷q]←0 ⋄ ∇ ⍵,q}p

}

|2=apl}}

| {{sxhl|1=

</pre>

| <pre>

∇ b←sieve1 n;i;m;p;q;r

:If 4≥n ⋄ b←n⍴0 0 1 1 ⋄ :Return ⋄ :EndIf

Line 391 ⟶ 388:

b[p]←1

∇

|2=apl}}

| {{sxhl|1=

</pre>

| <pre>

∇ b←sieve2 n;i;m;p;q;r

→L10 ⍴⍨ 4<n ⋄ b←n⍴0 0 1 1 ⋄ →0

Line 410 ⟶ 406:

b[p]←1

∇

|2=apl}}

</pre>

|}

Line 434 ⟶ 430:

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>{{cite journal|last1=Hui|first1=Roger|last2=Kromberg|first2=Morten|title=APL Since 1978|journal=Proceedings of the ACM on Programming Languages|volume=4|number=HOPL|date=June 2020|pages=1–108|doi=10.1145/3386319|s2cid=218517570|url=https://dl.acm.org/doi/pdf/10.1145/3386319|-access-date=17 June 2020free}}</ref>

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 September 2019}}</ref>{{rp|§8}}<ref name=IversonWooster1981>{{cite journal|last1=Iverson|first1=Kenneth E.|author-link=Kenneth E. Iverson|last2=Wooster|first2=Peter|title=A Function Definition Operator|journal=APL81 Conference Proceedings, APL Quote Quad|volume=12|number=1|date=September 1981}}</ref><ref name=Cheney>{{citation|last=Cheney|first=Carl M.|title=APL*Plus Nested Array System Reference Manual|date=March 1981|publisher=[[Scientific Time Sharing Corporation|STSC, Inc.]]|url=http://www.sudleyplace.com/APL/Nested%20Arrays%20System.pdf|access-date=18 September 2019}}</ref>{{rp|§4.17}}<ref name=ratapl>{{citation|last=Iverson|first=Kenneth E.|author-link=Kenneth E. Iverson|title=Rationalized APL|date=6 January 1983|publisher=[[I. P. Sharp Associates]]|url=http://www.jsoftware.com/papers/RationalizedAPL.htm|access-date=2019-09-19 September 2019}}</ref><ref name=dictionary>{{cite journal|last=Iverson|first=Kenneth E.|author-link=Kenneth E. Iverson|title=A Dictionary of APL|journal=APL Quote Quad|volume=18|number=1|date=September 1987|pages=5–40|doi=10.1145/36983.36984|s2cid=18301178|url=http://www.jsoftware.com/papers/APLDictionary.htm|access-date=19 September 2019|url-access=subscription}}</ref><ref name=Bunda1987>{{cite journal|last=Bunda|first=John|title=APL Function Definition Notation|journal=APL87 Conference Proceedings, APL Quote Quad|volume=17|number=4|date=May 1987}}</ref><ref name=J>{{cite journalbook|last=Hui|first=Roger|title=Conference proceedings on APL 90: For the future |chapter=APL\? |author-link=Roger Hui|display-authors=etal|title=APL\?|journal=APL90 Conference Proceedings, APL Quote Quad|volume=20|number=4|date=July 1990|pages=192–200|doi=10.1145/97808.97845|isbn=089791371X|s2cid=235453656 |chapter-url=http://www.jsoftware.com/papers/J1990.htm|access-date=2019-09-10 September 2019}}</ref> but the results were unwieldy. Of these, the "alternative APL function definition" of Bunda in 1987<ref name=Bunda1987/> 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]].<ref name=APL1978/>

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>{{cite journal|last=Wadler|first=Philip L.|display-authors=etal|title=Special Issue on Functional Programming|journal=[[The Computer Journal]]|volume=32|number=2|date=1 January 1989}}</ref> He then proceeded to study functional programming and became strongly motivated ("sick with desire", like [[W. B. Yeats|Yeats]]) to bring these ideas to APL.<ref name=Scholes2018v/><ref name=Scholes2018t/> 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.<ref name=Scholes1996/> Acceptance and recognition were slow in coming. As late as 2008, in ''Dyalog at 25'',<ref name=Dyalog@25>{{cite journal|last=Dyalog|title=Dyalog at 25|journal=Vector|date=September 2008|url=http://www.dyalog.com/uploads/documents/dyalog_25.pdf|access-date=2019-09-20 September 2019}}</ref> a publication celebrating the 25th anniversary of Dyalog Limited, dfns were barely mentioned (mentioned twice as "dynamic functions" and without elaboration). As{{as of |2019}}, dfns are implemented in Dyalog APL,<ref name=Dyalog17.1/> NARS2000,<ref name=NARS2000>{{citation|last=Smith|first=Bob|title=NARS2000|date=2006–2019|url=http://www.nars2000.org/|access-date=18 September 2019}}</ref> and ngn/apl.<ref name=Nickolov2013>{{cite journal|last=Nickolov|first=Nick|title=Compiling APL to JavaScript|journal=Vector|volume=26|number=1|date=September 2013|url=http://archive.vector.org.uk/art10501160|access-date=19 September 2019}}</ref> They also play a key role in efforts to exploit the computing abilities of a [[graphics processing unit]] (GPU).<ref name=Hsu2019>{{cite thesis|last=Hsu|first=Aaron|title=A Data Parallel Compiler Hosted on a GPU|degree=PhDPh.D.|institution=[[Indiana University]]|date=2019|url=http://scholarworks.iu.edu/dspace/bitstream/handle/2022/24749/Hsu%20Dissertation.pdf|access-date=25 December 2019}}</ref><ref name=APL1978/>

== References ==