title: Implementing lazy functional languages
body: <p>When implementing a lazy functional language, it is necessary to store values as unevaluated thunks, to be evaluated only when needed.</p>
  
  <p>One of the challenges of an efficient implementation, as discussed in e.g. <em>The Spineless Tagless G-machine</em>, is that this evaluation must be carried out only once for each thunk, and subsequent accesses must reuse the calculated value - failure to do this would lead to at least quadratic slowdown (perhaps exponential? I'm not sure off the top of my head.)</p>
  
  <p>I'm looking for a simple example implementation whose operation is easily understood (as opposed to an industrial-strength implementation like GHC which is designed for performance over simplicity). I came across minihaskell at <a href="http://www.andrej.com/plzoo/">http://www.andrej.com/plzoo/</a> which contains the following code.</p>
  
  <p>As it is dubbed "an efficient interpreter", I would assume it does indeed carry out each evaluation only once and save the calculated value for reuse, but I'm having difficulty seeing where and how; I can only see one assignment statement in the interpreter itself, and that doesn't look like it's overwriting part of a thunk record.</p>
  
  <p>So my question is, is this interpreter indeed doing such caching, and if so where and how? (And if not, what's the simplest extant implementation that does do so?)</p>
  
  <p>Code from <a href="http://www.andrej.com/plzoo/html/minihaskell.html">http://www.andrej.com/plzoo/html/minihaskell.html</a></p>
  
  <pre><code>let rec interp env = function
    | Var x -&gt;
       (try
       let r = List.assoc x env in
         match !r with
             VClosure (env', e) -&gt; let v = interp env' e in r := v ; v
           | v -&gt; v
         with
         Not_found -&gt; runtime_error ("Unknown variable " ^ x))
     ... snipping the easy stuff ...
    | Fun _ as e -&gt; VClosure (env, e)
    | Apply (e1, e2) -&gt;
        (match interp env e1 with
         VClosure (env', Fun (x, _, e)) -&gt;
           interp ((x, ref (VClosure (env, e2)))::env') e
       | _ -&gt; runtime_error "Function expected in application")
    | Pair _ as e -&gt;  VClosure (env, e)
    | Fst e -&gt;
        (match interp env e with
         VClosure (env', Pair (e1, e2)) -&gt; interp env' e1
       | _ -&gt; runtime_error "Pair expected in fst")
    | Snd e -&gt;
        (match interp env e with
         VClosure (env', Pair (e1, e2)) -&gt; interp env' e2
       | _ -&gt; runtime_error "Pair expected in snd")
    | Rec (x, _, e) -&gt; 
        let rec env' = (x,ref (VClosure (env',e))) :: env in
      interp env' e
    | Nil ty -&gt; VNil ty
    | Cons _ as e -&gt; VClosure (env, e)
    | Match (e1, _, e2, x, y, e3) -&gt;
        (match interp env e1 with
         VNil _ -&gt; interp env e2
       | VClosure (env', Cons (d1, d2)) -&gt;
           interp ((x,ref (VClosure(env',d1)))::(y,ref (VClosure(env',d2)))::env) e3
       | _ -&gt; runtime_error "List expected in match")
  </code></pre>