实现懒惰的函数式语言 [英] Implementing lazy functional languages

问题描述

在实现惰性函数语言时，需要将值存储为未评估的thunk，仅在需要时才进行评估。

When implementing a lazy functional language, it is necessary to store values as unevaluated thunks, to be evaluated only when needed.

高效实现的挑战之一，如在例如无骨髓无标记G机是这个评估只能对每个thunk进行一次，随后的访问必须重新使用计算的值 - 不这样做会导致至少二次减速（可能指数？我不确定关闭我的头顶。）

One of the challenges of an efficient implementation, as discussed in e.g. The Spineless Tagless G-machine, 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.)

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

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 http://www.andrej.com/plzoo/ which contains the following code.

因为它被称为高效的解释器，所以我会认为它确实只执行一次评估并保存计算出的值以供重用，但我很难看到哪里和哪里怎么样;我只能在解释器本身看到一个赋值语句，而且看起来并不像是覆盖了一个thunk记录的一部分。

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.

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

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?)

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")

推荐答案

关键是记录：notice ！r ， r：= v 。每当我们从环境中查找一个变量时，我们实际上会找回一条记录，我们可以通过取消引用来查看它是否是一个thunk。如果它是一个thunk，我们评估它，然后保存结果。我们在应用程序中创建thunks（注意对 ref 构造函数的调用），递归定义和模式匹配，因为它们是绑定变量的构造。

The key are the records: notice !r, r := v. Whenever we lookup a variable from the environment, we actually get back a record, which we dereference to see if it's a thunk. If it is a thunk, we evaluate it and then save the result. We create thunks during application (notice the call to the ref constructor), recursive definitions and pattern matching, because those are constructs that bind variables.

这篇关于实现懒惰的函数式语言的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！