Don Box made another post on Continuations and Closures that made me realised I’d made a mistake in my last post. I had not used continuation; I merely used a closure that captured some mutable variables. Also F#/Caml does not have continuations in the same way Ruby does. F# does however have continuation style passing, also discussed in Mr. Box aforementioned post.
<?xml:namespace prefix = o ns = “urn:schemas-microsoft-com:office:office” />
Anyway I thought I’d write a sort piece to show continuation style passing in action in F# , using my old favourite the Fibonacci series. Consider the following recursive code function that calculated the Fibonacci series.
let rec fib i j =
if i < 1000 then
let _ = Printf.printf “%d\n” i in
fib j (i + j)
let _ = fib 0 1
While this is quite a nice implementation of the Fibonacci series there are a couple of problems with it. The basic problem is lack of flexibility; you can neither produce Fibonacci numbers above1000 nor can you do anything other than write them to the console. This can be solved using continuation style passing, the function could be rewritten removing all flow control and printing and replacing them with a continuation. A worker function can then be produced that replaces everything that was hard coded into the old function.
let rec fib i j cont =
fib j (i + j) cont
let worker i =
if i > 1000 then raise (new System.Exception());
Printf.printf “%d\n” i
let _ =
fib 0 1 worker with
_ -> ()
It is interesting to note an expectation is used to control the flow. In imperative programming we are often told not use exceptions as flow control. I have begun to wonder if this statement is a little bit silly, after all exception are a mechanism for flow control, so not used them as flow control would mean not to use them at all. In functional programming it is somewhat less of a taboo, as they are extremely useful for breaking out of infinite loops or recursion with resorting to more imperative style flow control.
I think final solution looks something similar to the Fibonacci stream in Joe Duffy’s post on laziness and streams in C# 2.0. Sure it not lazy, but the function does hand you a infinite set of numbers until you decide you don’t want any more. Of course F# does support streams and laziness.