Английская Википедия:Direct function

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Шаблон:Short description Шаблон:Redirect 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. 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 Шаблон:Code and Шаблон:Code, separated by Шаблон:Code or new-lines, wherein Шаблон:Code denotes the left argument and Шаблон:Code the right, and Шаблон:Code denotes recursion (function self-reference). For example, the function Шаблон:Code tests whether each row of Шаблон:Code 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
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

Шаблон:Anchor The factorial function as a dfn:

   fact← {0=⍵:1 ⋄ ⍵×∇ ⍵-1}
   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":

Шаблон:Code	Шаблон:Code	Шаблон:Code   guard
Шаблон:Code  left argument	Шаблон:Code  left operand	Шаблон:Code  error-guard
Шаблон:Code  right argument	Шаблон:Code  right operand	Шаблон:Code  default left argument
Шаблон:Code  self-reference	Шаблон:Code  self-reference	Шаблон:Code  shy result

A dfn is a sequence of possibly guarded expressions (or just a guard) between Шаблон:Code and Шаблон:Code, separated by Шаблон:Code 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.

Шаблон:Code denotes the left function argument and Шаблон:Code the right; Шаблон:Code denotes the left operand and Шаблон:Code the right. If Шаблон:Code occurs in the definition, then the dfn is a dyadic operator; if only Шаблон:Code occurs but not Шаблон:Code, then it is a monadic operator; if neither Шаблон:Code or Шаблон:Code occurs, then the dfn is a function.

The special syntax Шаблон:Code 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 is not evaluated otherwise.

Шаблон:Code denotes recursion or self-reference by the function, and Шаблон:Code denotes self-reference by the operator. Such denotation permits anonymous recursion.

Error trapping is provided through error-guards, Шаблон:Code. 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 Шаблон:Code adds Шаблон:Code to Шаблон:Code (Шаблон:Mvar or <math>\sqrt{-1}</math>) times Шаблон:Code.

   3 {⍺+0j1×⍵} 4
3J4
   ∘.{⍺+0j1×⍵}⍨ ¯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 Шаблон:Code ⇔ Шаблон:Code (negate) and monadic Шаблон:Code ⇔ Шаблон:Code (reciprocal), a monadic definition of the function is useful, effected by specifying a default value of 0 for Шаблон:Code: if Шаблон:Code, then Шаблон:Code ⇔ Шаблон:Code ⇔ Шаблон:Code.

   j←{⍺←0 ⋄ ⍺+0j1×⍵}

   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← {(*j ⍵) = (cos ⍵) j (sin ⍵)}

   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 <math>\left(-0.5,0.5\right)</math>.

Single recursion

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:

<math>\biggl[0,1\biggr] \to</math>

<math>\left[0,\frac{1}{3}\right] \cup \left[\frac{2}{3},1\right] \to</math>

<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 defined as a dfn:Шаблон:Rp

   Cantor← {0=⍵:,1 ⋄ ,1 0 1 ∘.∧ ∇ ⍵-1}

   Cantor 0
1
   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:

Файл:Cantor set in seven iterations.svg

Шаблон:Anchor The function Шаблон:Code computes a bit vector of length Шаблон:Code so that bit Шаблон:Code (for Шаблон:Code and Шаблон:Code) is 1 if and only if Шаблон:Code is a prime.Шаблон:Rp

sieve←{
  4≥⍵:⍵⍴0 0 1 1
  r←⌊0.5*⍨n←⍵
  p←2 3 5 7 11 13 17 19 23 29 31 37 41 43
  p←(1+(n≤×⍀p)⍳1)↑p
  b← 0@1 ⊃ {(m⍴⍵)>m⍴⍺↑1 ⊣ m←n⌊⍺×≢⍵}⌿ ⊖1,p
  {r<q←b⍳1:b⊣b[⍵]←1 ⋄ b[q,q×⍸b↑⍨⌈n÷q]←0 ⋄ ∇ ⍵,q}p
}

   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
   (10*⍳10) (+⌿↑)⍤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 Шаблон:OEIS2C. 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>".

Шаблон:Code 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 (right fold). (The length of the prefix obtains by comparison with the primorial function Шаблон:Code.) The second finds the smallest new prime Шаблон:Code remaining in Шаблон:Code (Шаблон:Code), and sets to 0 bit Шаблон:Code itself and bits at Шаблон:Code times the numbers at remaining 1 bits in an initial segment of Шаблон:Code (Шаблон:Code). This second dfn uses tail recursion.

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:

fac←{⍺←1 ⋄ ⍵=0:⍺ ⋄ (⍺×⍵) ∇ ⍵-1}

Similarly, the determinant of a square complex matrix using Gaussian elimination can be computed with tail recursion:

det←{                ⍝ determinant of a square complex matrix
  ⍺←1                ⍝ product of co-factor coefficients so far
  0=≢⍵:⍺             ⍝ result for 0-by-0
  (i j)←(⍴⍵)⊤⊃⍒|,⍵   ⍝ row and column index of the maximal element
  k←⍳≢⍵
  (⍺×⍵[i;j]ׯ1*i+j) ∇ ⍵[k~i;k~j] - ⍵[k~i;j] ∘.× ⍵[i;k~j]÷⍵[i;j]
}

Multiple recursion

A partition of a non-negative integer <math>n</math> is a vector <math>v</math> of positive integers such that Шаблон:Code, where the order in <math>v</math> is not significant. For example, Шаблон:Code and Шаблон:Code are partitions of 4, and Шаблон:Code and Шаблон:Code and Шаблон:Code are considered to be the same partition.

The partition function <math>P(n)</math> 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

<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. Written as a dfn:Шаблон:Rp

   pn  ← {1≥⍵:0≤⍵ ⋄ -⌿+⌿∇¨rec ⍵}
   rec ← {⍵ - (÷∘2 (×⍤1) ¯1 1 ∘.+ 3∘×) 1+⍳⌈0.5*⍨⍵×2÷3}

   pn 10
42
   pn¨ ⍳13    ⍝ OEIS A000041
1 1 2 3 5 7 11 15 22 30 42 56 77

The basis step Шаблон:Code states that for Шаблон:Code, the result of the function is Шаблон:Code, 1 if ⍵ is 0 or 1 and 0 otherwise. The recursive step is highly multiply recursive. For example, Шаблон:Code would result in the function being applied to each element of Шаблон:Code, 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 Шаблон:Code requires longer than the age of the universe to compute (<math>7.57\times10^{47}</math> function calls to itself).Шаблон:Rp The compute time can be reduced by memoization, here implemented as the direct operator (higher-order function) Шаблон:Code:

M←{
  f←⍺⍺
  i←2+'⋄'⍳⍨t←2↓,⎕cr 'f'
  ⍎'{T←(1+⍵)⍴¯1 ⋄ ',(i↑t),'¯1≢T[⍵]:⊃T[⍵] ⋄ ⊃T[⍵]←⊂',(i↓t),'⍵}⍵'
}

   pn M 200
3.973E12
   0 ⍕ pn M 200  ⍝ format to 0 decimal places
 3972999029388

This value of Шаблон:Code agrees with that computed by Hardy and Ramanujan in 1918.

The memo operator Шаблон:Code defines a variant of its operand function Шаблон:Code to use a cache Шаблон:Code and then evaluates it. With the operand Шаблон:Code the variant is:

{T←(1+⍵)⍴¯1 ⋄ {1≥⍵:0≤⍵ ⋄ ¯1≢T[⍵]:⊃T[⍵] ⋄ ⊃T[⍵]←⊂-⌿+⌿∇¨rec ⍵}⍵}

Direct operator (dop)

Quicksort on an array Шаблон:Code 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. Defined as a direct operator (dop) Шаблон:Code:

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

   ⍝ 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

Шаблон:Code is a variant that catenates the three parts enclosed by the function Шаблон:Code 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 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←{1≥≢⍵:⍵ ⋄ (⊂∇ ⍵⌿⍨0>s)⍪(⊂⍵⌿⍨0=s)⍪⊂∇ ⍵⌿⍨0<s←⍵ ⍺⍺ ⍵⌷⍨?≢⍵}

   (×-) 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, Шаблон:Code is executable, and the partial order used in the sorting is an operand, the Шаблон:Code the examples above.

Dfns with operators and trains

Dfns, especially anonymous dfns, work well with operators and trains. The following snippet solves a "Programming Pearls" puzzle: given a dictionary of English words, here represented as the character matrix Шаблон:Code, find all sets of anagrams.

   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

The algorithm works by sorting the rows individually (Шаблон:Code), and these sorted rows are used as keys ("signature" in the Programming Pearls description) to the key operator Шаблон:Code to group the rows of the matrix.Шаблон:Rp 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 ⇔ Шаблон:Code, whence the expression on the right is equivalent to Шаблон:Code.

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 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.Шаблон:Rp

For example, in the following function Шаблон:Code, the variable Шаблон:Code is defined both in Шаблон:Code itself and in the inner function Шаблон:Code. When Шаблон:Code calls outward to Шаблон:Code and Шаблон:Code refers to Шаблон:Code, it finds the outer one (with value Шаблон:Code) rather than the one defined in Шаблон:Code (with value Шаблон:Code):

which←{
  ty←'lexical'
  f1←{ty←'dynamic' ⋄ f2 ⍵}
  f2←{ty,⍵}
  f1 ⍵
}

   which ' scope'
lexical scope

Error-guard

The following function illustrates use of error guards:Шаблон:Rp

plus←{
  tx←'catch all' ⋄  0::tx
  tx←'domain'    ⋄ 11::tx
  tx←'length'    ⋄  5::tx
  ⍺+⍵
}      
   2 plus 3              ⍝ no errors
5
   2 3 4 5 plus 'three'  ⍝ argument lengths don't match
length
   2 3 4 5 plus 'four'   ⍝ can't add characters
domain
   2 3 plus 3 4⍴5        ⍝ can't add vector to matrix
catch all

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 Шаблон:Code is set to describe the purview of its following error-guard. When an error occurs, the environment is unwound to expose Шаблон:Code's statically correct value.

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: 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 (Шаблон:Code) and line labels.

Шаблон:Sxhl

Шаблон:Sxhl

Шаблон:Sxhl

• A dfn can be anonymous; a tradfn must be named.
• A dfn is named by assignment (Шаблон:Code); a tradfn is named by embedding the name in the representation of the function and applying Шаблон:Code (a system function) to that representation.
• A dfn is handier than a tradfn as an operand (see preceding items: a tradfn must be named; a tradfn is named by embedding ...).
• Names assigned in a dfn are local by default; names assigned in a tradfn are global unless specified in a locals list.
• Locals in a dfn have lexical scope; locals in a tradfn have dynamic scope, visible in called functions unless shadowed by their locals list.
• The arguments of a dfn are named Шаблон:Code and Шаблон:Code and the operands of a dop are named Шаблон:Code and Шаблон:Code; the arguments and operands of a tradfn can have any name, specified on its leading line.
• The result (if any) of a dfn is unnamed; the result (if any) of a tradfn is named in its header.
• A default value for ⍺ is specified more neatly than for the left argument of a tradfn.
• Recursion in a dfn is effected by invoking Шаблон:Code or Шаблон:Code or its name; recursion in a tradfn is effected by invoking its name.
• Flow control in a dfn is effected by guards and function calls; that in a tradfn is by control structures and Шаблон:Code (goto) and line labels.
• Evaluating an expression in a dfn not ending in assignment causes return from the dfn; evaluating a line in a tradfn not ending in assignment or goto displays the result of the line.
• A dfn returns on evaluating an expression not ending in assignment, on evaluating a guarded expression, or after the last expression; a tradfn returns on Шаблон:Code (goto) line 0 or a non-existing line, or on evaluating a Шаблон:Code control structure, or after the last line.
• The simpler flow control in a dfn makes it easier to detect and implement 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. A direct definition has two or four parts, separated by colons:

name : expression
name : expression0 : proposition : expression1

Within a direct definition, Шаблон:Code denotes the left argument and Шаблон:Code the right argument. In the first instance, the result of Шаблон:Code is the result of the function; in the second instance, the result of the function is that of Шаблон:Code if Шаблон:Code evaluates to 0, or Шаблон:Code if it evaluates to 1. Assignments within a direct definition are dynamically local. Examples of using direct definition are found in the 1979 Turing Award Lecture and in books and application papers.

Direct definition was too limited for use in larger systems. The ideas were further developed by multiple authors in multiple worksШаблон:RpШаблон:Rp but the results were unwieldy. Of these, the "alternative APL function definition" of Bunda in 1987 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.

In 1996, John Scholes of Dyalog Limited invented direct functions (dfns). The ideas originated in 1989 when he read a special issue of The Computer Journal on functional programming. He then proceeded to study functional programming and became strongly motivated ("sick with desire", like Yeats) to bring these ideas to APL. 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. Acceptance and recognition were slow in coming. As late as 2008, in Dyalog at 25, a publication celebrating the 25th anniversary of Dyalog Limited, dfns were barely mentioned (mentioned twice as "dynamic functions" and without elaboration). Шаблон:As of, dfns are implemented in Dyalog APL, NARS2000, and ngn/apl. They also play a key role in efforts to exploit the computing abilities of a graphics processing unit (GPU).

External links

• Шаблон:Official website, Dyalog