实现惰性函数式语言

当实现惰性函数式语言时，有必要将值存储为未计算的 thunk，仅在需要时才进行计算。

有效实施的挑战之一，如在例如中所讨论的。无脊椎无标签 G 机，是这个评估必须对每个重击执行一次，并且后续访问必须重用计算值 - 如果不这样做将导致至少二次方减速（也许是指数级？我不确定我的头脑.)

我正在寻找一个简单的示例实现，其操作很容易理解（而不是像 GHC 这样的工业强度实现，它是为了性能而不是简单性而设计的）。我遇到了 minihaskellhttp://www.andrej.com/plzoo/ http://www.andrej.com/plzoo/其中包含以下代码。

由于它被称为“高效的解释器”，我认为它确实只执行一次每个评估并保存计算值以供重用，但我很难看出在哪里以及如何进行；我只能在解释器本身中看到一个赋值语句，这看起来不像是覆盖了 thunk 记录的一部分。

所以我的问题是，这个解释器是否确实进行了这样的缓存，如果是的话，在哪里以及如何进行？ （如果没有，现有的最简单的实现是什么？）

代码来自http://www.andrej.com/plzoo/html/minihaskell.html http://www.andrej.com/plzoo/html/minihaskell.html

let rec interp env = function
  | Var x ->
     (try
     let r = List.assoc x env in
       match !r with
           VClosure (env', e) -> let v = interp env' e in r := v ; v
         | v -> v
       with
       Not_found -> runtime_error ("Unknown variable " ^ x))
   ... snipping the easy stuff ...
  | Fun _ as e -> VClosure (env, e)
  | Apply (e1, e2) ->
      (match interp env e1 with
       VClosure (env', Fun (x, _, e)) ->
         interp ((x, ref (VClosure (env, e2)))::env') e
     | _ -> runtime_error "Function expected in application")
  | Pair _ as e ->  VClosure (env, e)
  | Fst e ->
      (match interp env e with
       VClosure (env', Pair (e1, e2)) -> interp env' e1
     | _ -> runtime_error "Pair expected in fst")
  | Snd e ->
      (match interp env e with
       VClosure (env', Pair (e1, e2)) -> interp env' e2
     | _ -> runtime_error "Pair expected in snd")
  | Rec (x, _, e) -> 
      let rec env' = (x,ref (VClosure (env',e))) :: env in
    interp env' e
  | Nil ty -> VNil ty
  | Cons _ as e -> VClosure (env, e)
  | Match (e1, _, e2, x, y, e3) ->
      (match interp env e1 with
       VNil _ -> interp env e2
     | VClosure (env', Cons (d1, d2)) ->
         interp ((x,ref (VClosure(env',d1)))::(y,ref (VClosure(env',d2)))::env) e3
     | _ -> runtime_error "List expected in match")

关键是记录：通知!r, r := v。每当我们从环境中查找变量时，我们实际上都会返回一条记录，我们会取消引用该记录以查看它是否是一个thunk。如果它是一个 thunk，我们对其进行评估，然后保存结果。我们在应用程序期间创建 thunk（注意对ref构造函数）、递归定义和模式匹配，因为这些是绑定变量的构造。