Scala Teil Endrekursion

Question

Weil ich mit vielen Variablen einen Dolmetscher bin definiert, schreibe ich das:

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

Für sehr lange Ausdrücke versagt dies wegen StackOverflowException, für Ausdrücke des Typs:

Sobald jedoch der Wert einer Variablen definiert ist, muss ich nur noch den Evaluator auf dem Körper der Let aufrufen, es scheint mir, dass es nur eine Art partielle Tail-Rekursion tun sollte.
Wie ist es möglich, partielle Tail-Rekursion in Scala zu erreichen?

Answer 1

Sie möchten eine Möglichkeit, Tail-Call-Optimierungen nur für einige Zweige von eval zu erhalten. Ich glaube nicht, dass dies möglich ist - die meisten Scala werden eine Annotation @tailrec an eine Methode als Ganzes akzeptieren und beim Kompilieren fehlschlagen, wenn sie die Methode nicht in eine Schleife optimieren kann.

jedoch diese iterativen macht, ist ziemlich geradlinig mit den Let Vorteil der Schwanz-Call zu nehmen:

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

Hinweis: Das wird den Stapelüberlauf durch lange Ketten von Plus s nicht lösen - Es gibt wirklich nicht viel, was wir damit machen können, weil die rekursiven Aufrufe nicht in der Endposition sind.

Es gab eine Zeit, in der ich dachte, dass Scala einige Anmerkungen zu dieser Art von Sache machen würde, aber ich bin nicht sicher, ob es so viel Interesse an solchen Dingen mehr gibt.