Today's lunchtime fun: Rewriting the code from Matt Might's article on CEK machines in OCaml

cek.ml

(* See http://matt.might.net/articles/cek-machines/ *)

type var = string

type term =
  Ref of var
| Lam of lambda
| App of term * term

and lambda = L of var * term

let rec terminal step isFinal state0 =  
  match isFinal state0 with
    true -> state0
| false -> terminal step isFinal (step(state0)) 

module Env = Map.Make(String);;

type d = Clo of lambda * env
and env = d Env.t

type state = env * term * kont
and kont =
  Mt
| Ar of env * term * kont
| Fn of env * lambda * kont

let step = function
   (env, Ref x, k) ->
       let Clo (lam, env') = Env.find x env in
       (env', Lam lam, k)
| (env, App (f, e), k) -> (env, f, Ar(env, e, k))
| (env, Lam lam, Ar(env', e, k)) -> (env', e, Fn(env, lam, k))
| (env, Lam lam, Fn(env', L(x, e), k)) -> (Env.add x (Clo (lam, env)) env', e, k)

let inject e = (Env.empty, e, Mt)

let isFinal = function
  (env, Lam _, Mt) -> true
| _ -> false

let evaluate pr = terminal step isFinal (inject(pr))