Scala 部分尾递归

Question

因为我正在定义一个有很多变量的解释器，所以我这样写：

type Context = Map[String, Int]
abstract class Expr
case class Let(varname: String, varvalue: Expr, body: Expr) extends Expr
case class Var(name: String) extends Expr
case class Plus(a: Expr, b: Expr) extends Expr
case class Num(i: Int) extends Expr

def eval(expr: Expr)(implicit ctx: Context): Int = expr match {
  case Let(i, e, b) => eval(b)(ctx + (i -> eval(e)))
  case Var(s) => ctx(s)
  case Num(i) => i
  case Plus(a, b) => eval(a) + eval(b)
}

对于非常长的表达式，由于 WhosebugException 而失败，对于类型的表达式：

Let("a", 1, 
Let("b", Plus("a", "a"), 
Let("c", Plus("b", "a"), 
Let("d", 1,  ...  )

但是，一旦定义了变量的值，我只需要在 Let 的主体上再次调用求值器，在我看来它应该只做一些部分 tail-recursion.
Scala 中如何实现部分尾递归？

Answer 1

您需要某种方法来仅对 eval 的某些分支进行尾调用优化。我不认为这是可能的——Scala 最多会做的就是接受一个方法的 @tailrec 注释作为一个整体，如果它不能将方法优化成一个循环，就会在编译时失败。

但是，通过 Let 进行此迭代以利用尾调用非常简单：

def eval(expr: Expr, ctx: Context): Int = {

  // The expression/context pair we try to reduce at every loop iteration
  var exprM = expr;
  var ctxM = ctx;

  while (true) {
    expr match {
      case Var(s) => return ctxM(s)
      case Num(i) => return i
      case Plus(a, b) => return eval(a,ctxM) + eval(b,ctxM)
      case Let(i, e, b) => {
        ctxM += i -> eval(e,ctxM). // Update ctxM
        exprM = b                  // Update exprM
      }
    }
  }
  return 0; // unreachable, but Scala complains otherwise I'm not returning 'Int'
}

请注意，这不会解决由于 Pluss 的长链而导致的堆栈溢出问题 - 我们真的没有太多可以做的，因为递归调用不在尾部位置。

曾经有一段时间我认为 Scala 会做一些 @tailcall 注释来处理这种事情，但我不确定人们是否对这种事情有那么大的兴趣。

Answer 2

你应该避免在 Scala 中使用 return。在这种情况下，您可以为 while 控件使用一个标志。例如

var result = Option.empty[Int]
while (result.isEmpty) {
  ...
  result = ctxM(s)
  ...
}
result

还有其他（IMO 更好）方法可以解决这个问题。例如https://typelevel.org/cats/datatypes/freemonad.html

Scala 部分尾递归

Scala partial tail recursion

scala

recursion

stack-overflow

tail-recursion