After coding the factorial program, this is the second session with SML, where we leave the purely functional domain and try some side-effect programming. This has a negative taste in a world heading for pervasive concurrency, but it yields some elegant code sometimes.

The accumulator generator is a classic problem to compare the conciseness of programming languages, at least Paul Graham declared it so. His website lists implementations in various languages, but not with SML. The problem definition:

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.

Point (a) is no problem, since SMLs type inference will take care of that, but (b) is a serious problem, if you try to solve it purely functional. The Haskell solution doesn't look nice. Here is my implementation:

(* mk_acc returns a fresh accumulator function *)
fun mk_acc start =
    let
        val sum = ref start;
        fun acc x = let in
            sum := !sum + x ; !sum
        end;
    in
        acc
    end;

It is a little verbose compared to the Arc one-liner:

(def mk_acc (n) [++ n _])

Yet it is readable and not too ornate. I'm not sure whether the last four lines can be compressed more, at least i was not able to get it through the type checker.

Since i'm not familiar with SML semantics, a little testing proofs that the semantics are as intended. Multiple accumulator functions must not interfere with each other for example.

(* trying calling and testing non-interference *)
val acc = mk_acc 10;
acc(2);
val acc2 = mk_acc 10;
acc2(100);
print ((Int.toString (acc 1)) ^ "\n"); (* ... prints 13 *)

Writing the mk_acc function took me some time, because i struggled a lot with syntax and type checking. I have not found a good syntax reference so far, which clearly describes for example the difference between let ... in ... end and local ... in ... end. As far as i understood it: Let creates a local namespace for the declared variables, while local exports the body to the global namespace.

One particular gotcha was the semicolon in the most inner line. Ending the line with !sum; makes the function return type [unit] (which means void/None/nil/null in other languages) instead of [int]. The semicolon is a delimiter in SML, but not a end-of-statement symbol.

In the episode the type checker was more of a barrier than helpful. The syntax is not as intuitive as other languages and (partly because of type inference) the compiler errors were not very helpful most of the time.

© 2010-01-22