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

Для очень длинных выражений это не удается из-за StackOverflowException, для выражений типа:

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

Однако, как только значение переменной определено, мне просто нужно снова вызвать оценщика на тело Let, мне кажется, что он должен просто выполнить некоторую частичную рекурсию хвоста.
Как можно добиться частичной рекурсии хвоста в 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' 
} 

Примечания это не решит переполнение стека из-за длинные цепочки Plus с - там действительно мало что можно сделать с ними, потому что рекурсивные вызовы не находятся в положении хвоста.

Было время, когда я подумал, что Scala сделает аннотацию @tailcall, чтобы иметь дело с подобными вещами, но я не уверен, что такой интерес у вас уже больше.