Direct function: Difference between revisions

Revision as of 00:51, 2 December 2020

Revision as of 05:14, 26 December 2020

Line 1:

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

{{redirect|Dfns|the political entity sometimes known as the Democratic Federation of Northern Syria|Rojava}}

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 9 ⟶ 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 76 ⟶ 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=2019-09-15 September 2019}}</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 ===

Line 87 ⟶ 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>

Line 180 ⟶ 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]] 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 255 ⟶ 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 302 ⟶ 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 321 ⟶ 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 435 ⟶ 436:

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}}</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 2020}}</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}}</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 journal|last=Hui|first=Roger|author-link=Roger Hui|display-authors=etal|title=APL\?|journal=APL90 Conference Proceedings, APL Quote Quad|volume=20|number=4|date=July 1990|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 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=Ph.D.PhD|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 ==