free variable

I recently had occasion to visit this Wikipedia article about Alice ML. Alice ML extends Standard ML with a bunch of useful features, like future, typesafe persistence, and so on.

To motivate future, the wikipedia article author presents the recursive Fibonacci function:

fib 0 = 0
   | fib 1 = 1
   | fib n = fib(n-1) + fib(n-2);

The article then states that “[f]or large values of n, fib n will take a long time to compute.” No kidding; it’s exponential with n. However, Alice ML, according to the Wikipedia article, has a solution for this problem — and it’s not the one you learned in CS1. With future, the article informs us, it is possible to spawn a new thread to compute the nth Fibonacci number, thus saving time if the continuation of fib n does not need the result of fib n immediately.

The article neglects to mention that even Standard ML provides a mechanism to dramatically speed this function’s execution: the humble accumulator, whose straightforward application admits an implementation of fib that is linear with n.