Paul Graham invited solutions to his Accumulator Generator [L1 ] problem written in various programming languages.
Here is the problem:
Write a function foo that takes a number n and returns a function that takes a number i, and returns n incremented by i. Note: (a) that's number, not integer, (b) that's incremented by, not plus.
After a slew of languages are presented that solve the problem, he concludes with:
Some languages are not represented here, either because you can't write this program in them (short of Greenspun's Tenth Rule) or because no one has yet sent me the code for that language. If you know how to write this program in a language that isn't listed here, please send it along. (Please make sure, first, that it actually does the same thing as these solutions.)
(Greenspun's Tenth Rule: any sufficiently complicated C or Fortran program contains an ad hoc informally-specified bug-ridden slow implementation of half of Common Lisp.)
Now, since Tcl is meant to be extended (like Lisp, you extend the langauge to solve problems), I don't think that Greenspun's rule applies. Now, that being said, Tcl doesn't support closures natively, but you can add that capability (sans any GC) to the language quite naturally (see Closures). To keep things short, I offered a solution that didn't use any generalized closure proc, but solved the problem directly:
namespace eval foo {variable instance 1}
proc foo {n} {
set id [namespace eval foo {incr instance}]
namespace eval foo::${id} [list variable n $n]
proc foo::${id}::foo {i} {
variable n
set n [expr {$n+$i}]
}
return foo::${id}::foo
}I haven't heard from him since... (and he did accept my lua submission). I am sure the above code snippet is not the optimal solution. Anyone care to improve upon it (or offer a better solution), post it here and then submit it to Graham?
-- Todd Coram
Talk
RS prefers pseudo-closure with default arguments as it appears less heavyweight (no namespace, no garbage collection needed..) The following variation from procs as objects is as long as the above code, but somehow has a "musical", rhythmic quality:
proc foo n {
set name [clock clicks] ;# get a (hopefully) unique name
proc $name "i {n $n}" {
set self [lindex [info level 0] 0]
set n [expr {$n+$i}]
proc $self "i {n $n}" [info body $self]
set n
}
set name
}See also procs as objects which goes deeper into the topic.
Arjen Markus I will not supply a solution using aliases (yet a third way to achieve the effect), but rather I would like to comment on the term function: it seems to me that these functions with side-effects are not functions in the proper sense of the word. They are more akin to subroutines in Fortran (and they have the same bad habits as C's not-so-functional functions). Proper functions should return a value and that value should be the same whenever the arguments are the same.
I mean this comment as more than just a word game!
Depends on whether you view closures as side-effects. The accumulator variable n is really local to the function (it is enclosed---or captured---by it), so while the function is not functionally pure, it has no global side-effects (n is private to the generated function). -- Todd Coram
I don't understand the "increment, not plus" requirement. Is he asking that, for example, 2.5 + 3 be calculated as (10 * 2.5 + 10 * 3) / 10? I don't get it.
-- What is meant is that the local variable gets updated each time the function gets called. So, the returned function works more or less in the same way as rnd() - each time a different value - AM
I finally figured out why Tcl was not accepted (quote from http://paulgraham.com/accgensub.html ):
I currently believe that you can't write this program in ML and Ocaml (no polymorphism), Tcl (the functions returned by foo have to be named, and there is no sure way to avoid name clashes), or K (doesn't support closures).
Hmmm... I believe my original submission is not subject to name clashes (at least up to the maximum integer that can be held by id). But, enough of this game...If I really wanted an accumulator generator in Tcl, I'd code it in C, Lisp, Java, Perl (or whatever) and wrap it! Never underestimate the power of glue. -- Todd Coram
RS: There is a sure way to avoid name clashes. If the name of the lambda contains its argument list and body, it will never clash with another of different argument list and body. The simplest way to retrieve both argument list and body is to use [info level 0] in the lambda proc.
If you believe your suggestion is valid, why not ask for a clarification from Paul? It's even possible to check if a procedure exists, before creating it... Todd Coram - I had a small email thread with him. There was a problem with my first submission (it only worked with integers) and I sent a corrected version (the one above). I think he may have been put off by the fact that Tcl didn't have anonymous procedures (but I am only guessing since I never heard from him again).
The article is a bit silly, though, if you think about it. It's using the one area Lisp is strong in. F.ex. in Tcl mostly we use code-as-data in the form of callback scripts, not anonymous procedures. We could pick an example such as "write extensions that logs all input/output of any script run through it", which would probably be equally unfair to many other languages.
Having said that, anonymous procedures would probably be a useful addition to Tcl if there was some way to do it properly.
--Setok
TV It seems we want to need lambda after all, and not bother about memory management and variable assignment, stacks and heaps, memory pages, bug free linked lists and memory allocation. When is a function a function ? - RS quotes [L2 ]: "Let A and B be sets. A function f from A to B is an assignment of exactly one element of B to each element of A."
Why such a weird way to solve problems? Lets do it object-oriented in XOTcl.
Class Accumulator -parameter {startValue 0}
Accumulator instproc addValue {value} {my incr startValue $value}and using it
set myAccumulator [Accumulator new -startValue 20] puts [$myAccumulator addValue 30]
you can also use strong named objects
Accumulator create myAccu -startValue 20 puts [myAccu addValue 30]
One difference. We have objects, no functions, but this way to solve problems is more than 20 years proven and it works.
By the way. The problem (exercise) is not fair described. It is not only the problem, but also the way how to solve it (write a function ...) And this way is LISP way. It is a good characteristic of Tcl that it can simulate other languages (C, List, object-oriented). I'd be interested in the question how other languages can simulate the Tcl way of programming (for example substitution). Also describe, the problem, not the solution!
Objects can be used to solve the problem, but the intent of the problem is too see if the languages have the equivalent of Closures and lambda. Now, Python took an OO approach to its solution. But every problem doesn't warrant an OO solution. Especially given the fact that your Tcl may not include an OO system -- or you may not want to do OO (the 30 years notwithstanding).
IMHO, it's a lot cheaper to add closures and lambda to Tcl core than a full blown OO system (which may not be the flavor you prefer -- XoTcl vs incrTcl anyone?).
If Tcl had closures and lambda, the solution could look something like:
proc foo {n} {
local n $n
return [lambda i {set n [expr {$n+$i}]}]
}
but we don't have closures and lambda (although we can emulate them).
Using the make-closure-proc definition from Closures, we can build an accumulator generator with the following:
make-closure-proc foo {N} {
variable n $N
} {
lambda i {
variable n
set n [expr {$n+$i}]
}
}-- Todd Coram
start:
.org somewhere
ld a,0x08
call _malloc
ld (ourvar),a
ld (ourvar), #something
ld (fp), $f
call (fp)
ret
fp: .space INT
f: add (ourvar),a
inc (ourvar)
ret
then at least you know what you're doing. Sort of like a list. So is memory.