Search code examples
functional-programmingsmlsmlnj

Achieving laziness and memoization

Laziness is a corner stone in the book Purely Functional Data Structures, but it is not clearly described how he obtains it, at least to me. I thought I only needed to write:

datatype 'a susp = $ of 'a
fun force ($x) = x
fun plus (x, y) = $case (x, y) of ($m, $n) => m + n

But then I get the error:

- use "ch4.sml";;
[opening ch4.sml]
ch4.sml:3.20 Error: syntax error: inserting  ORELSE
[unexpected exception: Compile]

uncaught exception Compile [Compile: "syntax error"]
raised at: ../compiler/Parse/main/smlfile.sml:19.24-19.46
../compiler/TopLevel/interact/evalloop.sml:45.54
../compiler/TopLevel/interact/evalloop.sml:306.20-306.23
../compiler/TopLevel/interact/interact.sml:65.13-65.16

I tried modifying the function to

fun plus (x, y) = $(print "Evaluating...\n"; force x + force y)

But calling it with plus ($4, $5) evaluated it and didn't memoize it because it returns $ 9 instead of $ plus(force $4, force $5) and it printed Evaluating... both times.

- plus ($4, $5);;
Evaluating...
val it = $ 9 : int susp
- plus ($4, $5);;
Evaluating...
val it = $ 9 : int susp

I'd also like to obtain the keyword lazy, but I'm not sure whether SML New Jersey supports this, whether it was implemented by Chris Okasaki, or that it's manually desugared. The keyword is highlighted in my editor but when writing

fun lazy plus ($x, $y) = $ (x + y)

I get that lazy is the function taking two parameters plus and ($x, $y) as given by the type:

val lazy = fn : 'a -> int susp * int susp -> int susp

My question boils down to How do I obtain laziness and memoization in SML New Jersey?

Solution

  • You need to enable laziness and add some parentheses (the $ in the book has peculiar parsing rules):

    Standard ML of New Jersey v110.83 [built: Thu May 31 09:04:19 2018]
- Control.lazysml := true;
[autoloading]
[ ... boring details ...] 
[autoloading done]
val it = () : unit
- open Lazy;
[autoloading]
[autoloading done]
opening Lazy

  datatype 'a susp = $ of 'a
- fun plus (x, y) = $(case (x, y) of ($m, $n) => m + n);
val plus = fn : int susp * int susp -> int susp
-  val x = plus($4, $5);
val x = $$ : int susp
- fun force ($x) = x;
val force = fn : 'a susp -> 'a
- force x;
val it = 9 : int
- fun lazy plus ($x, $y) = $ (x + y);
val plus = fn : int susp * int susp -> int susp
val plus_ = fn : int susp * int susp -> int

    Note that this does not memoize plus.