Options




Id




Substitution






Call-by // TODO


Scope



Values

abstract class Value
case class VNum(n: Int) extends Value
case class VClosureVFun(param: String, body: Expr, env) extends Value

AST

abstract class Expr
case class Num(n: Int) extends Expr
case class Add(lhs: Expr, rhs: Expr) extends Expr
case class Sub(lhs: Expr, rhs: Expr) extends Expr
case class If0(c: Expr, t: Expr, f: Expr) extends Expr
case class Let(name: String, namedExpr: Expr, body: Expr) extends Expr
case class Id(name: String) extends Expr
case class App(funExpr: ExprfunName: String, argExpr: Expr) extends Expr
case class Fun(param: String, body: FLAE) extends Expr

Interpreter

def interp(expr: Expr, funDefs: Map[String, FunDef], env: Map[String, Box[Value]]): Value = expr match {
case Num(n) => n
case Add(lhs, rhs) => interp(lhs, funDefs, env) + interp(rhs, funDefs, env)
case Sub(lhs, rhs) => interp(lhs, funDefs, env) - interp(rhs, funDefs, env)
case If0(c, t, f) => if (interp(c, funDefs, env) == 0)
interp(t, funDefs, env) else interp(f, funDefs, env)
case Id(name) => env.getOrElse(name, sys.error(s"unbound variable $name"))
case Let(name, namedExpr, body) =>
val body = subst(body, name, Num(interp(namedExpr, funDefs)))
val newEnv = env + (id -> Box.Immutable(interp(expr, funDefs, env)))
interp(body, funDefs, newEnv)
case LetRec(name, namedExpr, body) =>
val recExpr = LetRec(name, namedExpr, Id(name))val mutableBox = Box.Mutable[Value](Num(-42))
val transformedNamedExpr = subst(namedExpr, name, recExpr)val recEnv = env + (name -> mutableBox)
val body = subst(body, name, Num(interp(transformedNamedExpr, funDefs)))val namedValue = interp(namedExpr, recEnv)
mutableBox.value = namedValue
interp(body, recEnv)
case App(funExprfunName, argExpr) => interp(funExpr, env)funDefs(funName) match {
case VFunVClosureFunDef(param, body, funEnv) =>
val body = subst(body, param, Num(interp(argExpr, funDefs)))
val argVal = Box.Immutable(interp(argExpr, funDefs, env))
val newEnv = funEnv + env + Map(param -> argVal)
interp(body, funDefs, newEnv)
case v1 => error(s"Expected funct value but got $v1")
}
case class Fun(param, body) => VClosureVFun(param, body, env)
}

Substitute

// Substitutes "substId" with "value" in "expr"
// The resulting expression contains no free instances of the 2nd argument.
def subst(expr: Expr, substId: String, value: Expr): Expr = expr match {
case Num(_) => expr
case Add(lhs, rhs) => Add(subst(lhs, substId, value), subst(rhs, substId, value))
case Sub(lhs, rhs) => Sub(subst(lhs, substId, value), subst(rhs, substId, value))
case If0(test, thenBody, elseBody) =>
If0(subst(test, substId, value), subst(thenBody, substId, value), subst(elseBody, substId, value))
case Id(name) => if substId == name then value else expr
case Let(name, namedExpr, body) =>
val substNamedExpr = subst(namedExpr, substId, value)
if name == substId then
Let(name, substNamedExpr, body)
else
  Let(name, substNamedExpr, subst(body, substId, value))
case LetRec(name, namedExpr, body) =>
if name == substId then
LetRec(name, namedExpr, body)
else
LetRec(name, subst(namedExpr, substId, value), subst(body, substId, value))
case App(funExprfunName, argExpr) =>
val newArg = subst(argExpr, substId, value)
val newFunExpr = subst(funExpr, substId, value)
App(newFunExprfunName, newArg)
case Fun(param, body) =>
if param == substId then
Fun(param, body)
else if !freeVariables(value).contains(param) then
  Fun(param, subst(body, substId, value))
else
val potentialConflicts = freeVariables(value) union freeVariables(body)
val freshId = Id(freshName(param, potentialConflicts))
val alphaRenamed = subst(body, param, freshId)
Fun(freshId.name, subst(alphaRenamed, substId, value))
}

def freeVariables(expr: Expression): Set[String] = expr match {
case Num(_) => Set.empty
case Add(lhs, rhs) => freeVars(lhs) union freeVars(rhs)
case Sub(lhs, rhs) => freeVars(lhs) union freeVars(rhs)
case If0(c, t, f) => ??? // TODO
case Id(name) => Set(name)
case Let(name, namedExpr, body) => (freeVars(namedExpr) - name) union freeVars(body)
case LetRec(name, namedExpr, body) => ??? // TODO
case App(funExprfunName, argExpr) => freeVariables(funExpr) ++ freeVariables(argExpr)
case Fun(param, body) => freeVariables(body) - param
}

def freshName(id: String, known: Set[String]): String =
def rec(count: Int): String =
val newName = s"$id-$count"
if known.contains(newName)
then rec(count + 1)
else newName
rec(0)