Wednesday, 5 January 2011

Paul Graham's accumulator generator

Paul Graham once published an article about what he called "accumulator generators". This problem requires the existence of an unspecified numeric tower. Lisp happens to have one and it happens to be adequate for Paul Graham's examples.

You can implement a numeric tower in F# either using a union type (like type number = Int of int | Float of float) or by boxing everything. The following solution uses the latter approach:

let add (x: obj) (y: obj) =
match x, y with
| (:? int as m), (:? int as n) -> box(m+n)
| (:? int as n), (:? float as x)
| (:? float as x), (:? int as n) -> box(x + float n)
| (:? float as x), (:? float as y) -> box(x + y)
| _ -> failwith "Run-time type error"

let acc x =
let x = ref x
fun (y: obj) ->
:= add !x y

let x : obj -> _ = acc(box 1)
do x(box 5)
do acc(box 3)
do printfn "%A" (x(box 2.3))

However, numeric towers are of little use in general purpose programming and usually do more harm than good. Trying to learn from these kinds of challenges can do more harm than good. The real question is: why we do not want a numeric tower, do not want to box and do not want run-time type promotion?

In other words, why didn't we just write:

let x = 1
let x = x + 5
let x = float x + 2.3

We know the type of x at every step. Every number is stored unboxed. And we know that this code cannot produce a run-time type error.


Art Vandalay said...

I agree that the dynamic typing part of Graham's challenge is odd and irrelevant to what I believe to be his main point: the value of code that can construct and use other code (i.e. functions with closure). He could say the same thing with string concatenation instead of addition as the example. Perhaps within a lexer that used the closures for backtracking.

In most real-world business cases, someone would likely just throw a decimal type at the problem if they were so interested in a general "numeric" type that can act like an int or a float. In which case the C# version wouldn't be so far off from the F# version, if not for all the explicit types...

Func acc(decimal x)
decimal x2 = x;
return y => { x2 += y; return x2; };

Art Vandalay said...

Argh. The intended return type is of course Func<decimal,decimal> . And C# doesn't allow using "x" as both parameter and local variable, hence "x2".