Standard ML

references

---

pure functional programming

Pure functional programming is achieved when:

• All data is immutable
• All functions are pure, which means:
  1. They have no side-effects
  2. They are completely deterministic

Pure functional programming has its advantages, however it is not practical for most use cases.

pure functional programming

So far we treated SML as a pure functional programming language.

Now is a good time to tell you that this is not entirely true…

---

ref cells

In SML, we may use ref to create a mutable cell:

val x = ref 4;

ref cells

ref is a constructor and as such is also a function:

ref;

---

ref cells

We may use := to replace a cell’s contents:

val x = ref 0;
x := 15;
x;

Note that := returns ()

val := = fn : 'a ref * 'a -> unit

ref cells

We may use ! to get the cell’s content:

val x = ref 8;
!x;

val ! = fn : 'a ref -> 'a

---

sequencing with ;

; is used to sequence expressions (with side-effects)

fun swap x y =
    (x := !x + !y ; y := !x - !y ; x := !x - !y);

val x = ref 1 and y = ref 2;
swap x y;
(!x, !y);

sequencing with ;

An expression created by ; evaluates to the value of the last expression

val x = ref 42;
(x := !x * !x; !x);

---

example - memoization

Memoization is an optimization technique used to speed up computations by caching results.

This is technique is applied to pure functions and relies on the fact that these are deterministic.

example - memoization

For each function f that receives an argument x we store in memory pairs of x and f(x) values.

example - memoization

When f is called with x we check if f was already called with x before. If so, we return the cached value, otherwise we compute f(x), store it in memory and return it.

example - memoization

First let’s define a type for our cache memory (memoizer):

type (''a, 'b) memoizer = {max_size: int, memory: (''a * 'b) list ref};

example - memoization

memoizer_put will let us store new values in the cache memory:

fun memoizer_put (memo: (''a, 'b) memoizer) x y =
	let 
      val state = #memory memo
    in
      state :=
          (if length (!state) < #max_size memo then
              !(state)
          else
              tl (!state))
          @ [(x, y)]
    end;

example - memoization

memoize will be our memoization function, i.e. it will apply the memoization technique to a given function:

fun memoize (memo: (''a, 'b) memoizer) f x =
    

example - memoization

Now let’s apply memoization to the Fibonacci function:

local
    val memo = {max_size=10, memory=ref []}
in
fun fib 0 = 0
  | fib 1 = 1
  | fib n = let
        val aux = memoize memo fib
    in
        aux (n - 1) + aux (n - 2)
    end
end;

example - memoization

Let’s compare:

fib 43;

fun fib_exp 0 = 0
  | fib_exp 1 = 1
  | fib_exp n = fib_exp (n - 1) + fib_exp (n - 2);
fib_exp 43;