Accumulator Generators

Paul Graham invited solutions to his Accumulator Generator [1] 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 language 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. For example, 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 [2]: "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."

DKF: Actually, functions are a special class of relations on pairs of sets such that every element in the domain of the function (i.e., the things in the source set) only has one mapping onto an element in range of the function (the things in the target set). That's the only requirement. (Interesting subclasses of functions are the injective, surjective and bijective functions. In particular, bijective functions are the functions with well-defined functional inverses.)

Lars H: Instead of "... only has one mapping onto an element in range ...", I'd suggest "... is related to precisely one element in the range ...", since one should use relation terminology when defining functions as a special kind of relation.

In computing, a more interesting distinction is between partial and total functions, where a total function is guaranteed to produce a value for every (legal) input, and a partial function is like a total function but isn't actually guaranteed to return anything at all. These concepts are linked to the notions of primitive and general recursiveness...

Lars H: It should be observed that DKF's two paragraphs are based in two different views on what a function is. The first paragraph follows the 20th century mathematical view that a function is a kind of set. The second paragraph is closer to the 18th century mathematical view that a function is a formula/rule/algorithm for computing the value of the function; the definitions of partial, total, primitive recursive, and general recursive functions all focus on the formula defining these. That said, the latter concepts are 20th century mathematics too, and very closely related to the Gödel Incompleteness Theorem that is one of its greatest achievements.

Why such a weird way to solve problems? Let's 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 fairly 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!

fixed typos in my post

I tried the above XOTcl code and it only works with integers!

But I do believe that objects are the more elegant and generalized solution. A Class is a very powerful notion, and XOTcl seems to be the most advanced and exciting OO Tcl extension.

And by the way, I think OCaml can solve the Accumulator Generator problem; the first time I read this Paul Graham article, I was into OCaml; I don't remember the code I sent him, but I remember that I created a Type whose members can be either int or float, used the object oriented extension. The object worked on one type, which is actually a glue of these two types.

But then think about it, a function that works on two different types implies there is a relation between those two types.

According to Peter Chen, if a relation exist between two types, then you have a new type that is the glue between these two.

Of course in OCaml that's not exactly the case, because a type member in that case can only hold one value of a type, a float or an integer.

In a relational db, the type will hold both.

But then maybe a relational db cannot express that type of relation, I don't know. You can maybe add rules and triggers and stuff. But it's simpler in ocaml.

 Type number = Int of int | Float of float ;;

Again I don't remember most of what I learned of OCaml the above syntax can be wrong.

I believe Alex Stepanov refers to this kind of relations as generic programming.

If a function works on two types, they must be related for some reason. Here the relation is that they are all numbers; they have like a common ancestor or something.

A function should not be polymorphic because it's cool; it should be when it makes sense.

It doesn't make sense to say

 add Elephant to girafe

But it can make sense to say

 add number to number ;# regardless of their specific type

That's why polymorphic message are okay, but not 100% of the time.

Languages like OCaml force you to rationalize about those type relations; C++ Templates I believe also does so.

Anyway, since now I am into tickle a.k.a Tcl, I thought I'd see how it does with this test. I personally vote for the XOTcl object solution.

Objects can be used to solve the problem, but the intent of the problem is to 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.

kruzalex Alternative to the existing definition of make-closure-proc definition without using namespaces

 proc make-closure-proc {name arglist variables lambda_proc} {
    variable auto_cnt -1
    proc $name "$arglist {variables [list $variables]} {lambda_proc [list $lambda_proc]}" {
        set closure_name [lindex [info level 0] 0][incr ::auto_cnt]
        foreach {variable __var __value} [subst $variables] {
         variable ${closure_name}:${__var} $__value
    }
    lset lambda_proc 2 "[regsub -all "variable\[ \t\]+$__var" [lindex $lambda_proc 2] \
    "variable ${closure_name}:${__var} 
    variable $__var \[set ${closure_name}:${__var}\]\\1"] set ${closure_name}:${__var} \$$__var"
    curry $closure_name [eval $lambda_proc]
    }
 }

 proc delete-closure {name} {
     foreach n [uplevel 1 [list info vars  $name:*]] {
     uplevel 1 [list unset $n]
     }
 }
 
 proc curry {new args} {
    eval [list interp alias {} $new {}] $args
 }

 proc lambda {arglst body} {
    set level [info level 0]
    set name [string map {\n _ \t _ \" _ " " _ \; _ $ _ : _ \{ _ \} _ \[ _ \] _} $level]
    set invoke_context [uplevel namespace current]
    proc ${invoke_context}::$name $arglst $body
    return ${invoke_context}::$name
 }

 make-closure-proc foo {N} {
    variable n $N
 } {
    lambda i {
        variable n 
        set n [expr {$n+$i}]
    }
 }

 set f [foo 100]
 set f1 [foo 200]
 puts "f: $f"
 puts [$f 10]
 puts [$f1 10]
 delete-closure $f
 puts [$f 10]

SS 11Mar2005:

Jim is "accumulator capable" now, with garbage collecting lambda, and static vars, so we have closures:

 proc accumulator n {
    lambda increment n {
        set n [expr {$n+$increment}]
    }
 }

 set f [accumulator 100]
 puts [$f 10]
 puts [$f 20]
 puts [$f 1.25]

This outputs:

 110
 130
 131.25

And as long as every reference to the returned closure is lost, the memory is automatically reclaimed. Note: to be valid it must have automatic memory management, see the full Graham's article. There is a reason for this: without automatic memory management to be able to do this kind of things is almost useless from a practical point of view.

Category Example

Category XOTcl Code