在 Scala 的方案解释器中处理递归

Question

我给出了以下代码，它实现了 scala 的方案语言解释器。相关案例是那些包含对 updateEnvRec 或 updateEnv 的调用的案例：

 def evalRec(x: Data, env: Env): Data = {
    x match {
      case i: Int => i
      case Symbol(s) => env(s) match {
        case Some(v) => v
        case None => sys.error("Unknown symbol " + s)
      }
      case List('lambda, params: List[Data], body) =>
        ((args: List[Data]) => {
          val paramBinding = params.map(_.asInstanceOf[Symbol].name).zip(args)
          evalRec(body, updateEnv(env, paramBinding))
        })
      case List('val, Symbol(s), expr, rest) =>
        evalRec(rest, updateEnv(env, List(s -> evalRec(expr, env))))
      case List('def, Symbol(s), expr, rest) => {
        evalRec(rest, updateEnvRec(env, s, expr))
      }
      case List('if, bE, trueCase, falseCase) =>
        if (evalRec(bE, env) != 0) evalRec(trueCase, env)
        else evalRec(falseCase, env)
      case opE :: argsE => {
        val op = evalRec(opE, env).asInstanceOf[List[Data] => Data]
        val args: List[Data] = argsE.map((arg: Data) => evalRec(arg, env))
        op(args)
      }
    }
  }

这段代码的目的是处理如下表达式：

(val factorial (lambda (x)
(if (= x 0) 1 (* x (factorial (- x 1)))))
(factorial 6))

为此，我得到了以下环境更新和定义：

 type Env = String => Option[Data]
  val recEnv : Env = ((id:String) => funEnv.get(id)) 
  def updateEnv(env : Env, bindings : List[(String,Data)]) : Env = bindings match {
    case Nil => env
    case (id,d)::rest => ((x:String) =>
        if (x==id) Some(d)
        else updateEnv(env,rest)(x))
  }
  def updateEnvRec(env: Env, s : String, expr : Data) : Env = {
    def newEnv : Env = ((id:String) =>
      if (id==s) Some(evalRec(expr, newEnv))
      else env(id)
    )
    newEnv
  }

我的问题是我不明白为什么要调用：

 evalRec(rest, updateEnv(env, List(s -> evalRec(expr, env))))

有效。我宁愿写：

evalRec(rest, updateEnvRec(env,s,expr))

因为使用第一种策略我必须首先评估 evalRec(expr, env) 这会导致错误，因为此时 env 不包含阶乘。我错过了什么？

Answer 1

我相信你的榜样

(val factorial 
  (lambda (x)
    (if (= x 0) 
        1 
        (* x (factorial (- x 1)))))
(factorial 6))

错了。如果我正确理解代码，val 不会引入递归绑定，因此内部 factorial 是未绑定的。而你的解释器给了你那个错误。

试试这个程序：

(def factorial 
  (lambda (x)
    (if (= x 0) 
        1 
        (* x (factorial (- x 1)))))
(factorial 6))

在 Scala 的方案解释器中处理递归

Handling recursion in scala's scheme interpreter

scheme

interpreter

scala