Guides/Lexical Closure
Accumulator Generator
motivation
This page answers the challenge posed by Paul Graham in his accumulator generator challenge because it crops up periodically in the Forums.
the challenge
The challenge, in short, is to prove that your favorite language has, or can closely emulate, (A) lexical closure and, (B) higher order functions (functions which return other [anonymous] functions), where "function" really means "subroutine" and does not mean a mathematical function.
We want to write a function that generates accumulators-- a function that takes a number n, and returns a function that takes another number i and returns n incremented by i. (That's incremented by, not plus. An accumulator has to accumulate.) --Paul Graham
That is, Graham wants you to demonstrate a stateful function. However, implicitly, he discourages the use of global variables. He wants to see the use of variables which are local to their function (invisible outside its definition), but which retain their values across invocations of that function.
If you're familiar with Visual Basic, think of the keyword static
Approach
First: in J, a "function" is a verb, adverb or conjunction. Verbs return nouns and only nouns (including names and gerunds), while adverbs and conjunctions can return nouns, verbs, adverbs or conjunctions.
Since the "function which returns a function" only needs one argument (to wit: n, the initial value of the lexical variable), the solution in J will be an adverb.
Consequently, in J, our goal is to provide a definition accGen:
accGen =: adverb define NB. Some magical definition )
The issue to be solved is: where should this definition keep its state? We could keep state in a locale, or in the operating system (for example, in a file). Locales are preferred as they are somewhat cleaner than the alternatives. Some people might object to the use of locales because they are well documented and the challenge implied that the state involved should be secret.
Solutions
The first solution was provided by ChrisBurke:
burke=: 1 : 0 n=. 'n_',(> cocreate''),'_' (n)=. m 3 : (n,'=:',n,'+y') ) ag =: 0 burke ag 1 1 ag 1 2 ag 1 3
Subsequently, a more general solution was provided by OlegKobchenko:
oleg=: 1 : 0 a=. cocreate'' n__a=: m a&(4 : 'n__x=: n__x + y') ) f=. 3 oleg f 0 3 f 2 5 f 5 10 f 0 10
This solution is more general because the entire generated locale is available to the derived verb; it therefore has the potential to store and retrieve any number of data, not just x. Furthermore, Oleg's verb avoids code generation (that is, the text of derived verbs is constant; only the bound variable changes).
Can you list other solutions?
other solutions
1. For an amusing (but abusive) way to "solve" this puzzle, see: the mapped files solution
2. Oleg's solution can readily be translated into a one-liner thus: accgen=:1 :'(a[n__a=.m[a=.18!:3$~0)&(4 :''n__x=.n__x+y'')'
3. The current dyadic definition of verbs derived from accgen is supplied by the powering aspect of & (see the bond page in the dictionary). So
ag =: 0 accgen 10 ag 1 1024 2^10 1024
If this is not useful, we can provide a different definition, such as accgenr =: accgen ( : (] ($:@:[) $:@:-@:$:@:0:) ) which allows us to reset the accumulator:
agr =: 0 accgenr agr 1 1 agr 10 11 agr 100 111 agr~ 0 0 agr 1 1 agr~ 42 42 agr 1 43
5. A variation on Chris's approach uses no dynamic code in the body of the accumulator, and no globally qualified name for the accumulator's numeric value, but does construct a globally valid reference to the accumulator "function":
miller=: 1 :0
object=. cocreate''
n__object=: m
accum__object=: 3 :'n=:n+y'"0
''1 :('accum_',(>object),'_')
)
a=: 3 miller
b=: 4 miller
a 4 5 6
7 12 18
b 4 5 6
8 13 19
a 10
28
a f.
3 : 'n=:n+y'"0
6. Can you list other, meaningfully different, solutions?
A solution without locales, and with stretched interpretation, anonymous function (name does not need to be predefined). It also provides the flexibility of entirely changing the function:
pascalj =: 2 : 0
a =. n~ :: ] y
(n) =: a&u
a
)
erase 'f'
1
+ pascalj 'f' 2
2
+ pascalj 'f' 3
5
f
5&+
- pascalj 'f' 1
6
f
6&-
- pascalj 'f' 2
4
can lock in function to a name as long as an extra dummy name is used:
f =. + pascalj 'fii'
f 2
2
f 3
5
f
+ (2 : 0) 'fii'
a =. n~ :: ] y
(n) =: a&u
a
)
f 4
9
f 1
10
fii
10&+
"anonymous" version is preferable because it more descriptively shows what it does, and uses only 1 name just as original request.
This version provides arbitrary initial value, and arbitrary function polymorphing on next call. Also allows you to peek at next value without modifying function (f 2 will peek at next value)
resetting existing function may require double call:
* pascalj 'f'"0 ] 1 1
1 1
f
1&*
* pascalj 'f'"0 ] 2 3
2 6
f
6&*
dissent
Graham cites lexical scope as a feature of a "powerful" language. This appears to me like backwards reasoning. Graham likes Lisp; he thinks it's a powerful language. Lisp has lexical scope. Graham therefore concludes that all powerful languages must have lexical scope. Or, equivalently, a language must have lexical scope to be powerful.
I disagree with this conclusion. Lexical closure is incompatible with the functional programming model (a mathematical way of describing algorithms).
In the example section, notice how calling the same function with the same arguments produces a different result. A function whose output is not wholly determined by its input -- a function with "hidden inputs" -- is anathema to functional programming. (And yet, thinking about papers I've read, closures, "projections" and "monads" (in the Haskell/Scheme sense) are hot topics. So I must be wrong)
Contrast this with tacit definition in J, which does not even mention its arguments: mean =: +/ % #; this means tacit verbs are so dependent on their arguments that their indivual components' contexts are determined by their placement within the definition!
I maintain that functional programming is a powerful paradigm (in the same way mathematics is a powerful paradigm), and is at odds with lexical closure, and therefore lexical closure is not required of a powerful language. (Which is not the same as saying a language with lexical closure is not powerful, or that a language cannot achieve (greater) power through its addition.)
Regardless, because Graham is widely known and respected, his challenge has been and will be presented on the Forums, so we might as well answer it. Onward, then.
-- Dan Bron <<DateTime(2006-12-12T06:07:10Z)>>