OCaml and NML have the syntax for lazy evaluation of expressions. About a month or two ago, I decided to add lazy lists to NML. Haskell has some really neat features because of its overt lazy nature, and when dealing with potentially infinite calculations, I wanted some of those same benefits for NML.
In NML and OCaml the double-colon symbol “::” represents list concatenation -- the same as operator CONS in Lisp. I extended the notion of lists in NML to include lazy lists where the CDR of the list is a lazy expression. Lazy lists are consed using the operator “:>”.
So for some examples of lazy list programming in NML, see here, where we were playing around with some of John Hughes’ code from his paper on “Why Functional Programming Matters”, as well as some infinite series calculations from the Wizard Book of Abelson and Sussman.
One of the things that tickled my funny bone was the computation of the infinite series for sine and cosine by way of integration of each other....
let integrate_series s =
let rec iter s n =
car s / n :> iter (cdr s) (n+1)
in
iter s 1
let rec cos_series = 1 :> integrate_series (negate_stream sin_series)
and sin_series = 0 :> integrate_series cos_series
And then computing the infinite series for the tangent function by division of the series for sine by that for cosine...
let invert_unit_series s =
let rec x = 1 :> mul_series x (negate_stream (cdr s)) in
x
let rec div_series s1 s2 =
let sf = 1 / car s2 in
mul_series (scale_stream sf s1)
(invert_unit_series (scale_stream sf s2))
let tan_series = div_series sin_series cos_series
Is that cute? or what! Lazy streams in NML makes some rather more difficult problems very easy to express. We could have dispensed with the “:>” operator for lazy consing, but then our code would be peppered with “lazy” constructs and it wouldn’t appear quite so clean.
With lazy consing, everything following the “:>” operator is as though it had been written as a lazy expression:
e1 :> e2
same as
e1 :: lazy e2
where e1 is an expression representing the car of the list, evaluated in the usual NML eager manner, and e2 is an expression representing the cdr of the list. The cdr expression will not be evaluated until “stream_tail” is called on the overall list.
Okay... so what’s the big deal here? Why was it necessary to mess with the parser and compiler of NML to make this possible?
The answer lies in the fact that NML has no preprocessor, nor any macro capabilities. In Lisp all we would have to do is define a macro called “stream-cons” that would accomplish the same thing. But in NML we actually had to alter the parser and compiler to accomplish this.
In fact, in Lisp we could go one step further by writing an interpreter for a lazy subset language that would make all expressions lazy, not just the cdr of lazy lists. Now we have a language akin to Haskell itself.
Saturday, February 3, 2007
