-
Philippe Suter authoredPhilippe Suter authored
ExprComp.scala 2.26 KiB
object ExprComp {
// Values
case class Value(v : Int)
// Operations
sealed abstract class BinOp
case class Plus() extends BinOp
case class Times() extends BinOp
// Expressions
sealed abstract class Expr
case class Constant(v : Value) extends Expr
case class Binary(exp1 : Expr, op : BinOp, exp2 : Expr) extends Expr
def evalOp(v1 : Value, op : BinOp, v2 : Value) : Value = op match {
case Plus() => Value(v1.v + v2.v)
case Times() => Value(v1.v * v2.v)
}
// Expression evaluation
def eval(e : Expr) : Value = e match {
case Constant(v) => v
case Binary(e1,op,e2) => evalOp(eval(e1),op,eval(e2))
}
// Instructions
sealed abstract class Instruction
case class PushVal(v : Value) extends Instruction
case class ApplyBinOp(op : BinOp) extends Instruction
// Programs
sealed abstract class Program
case class EProgram() extends Program
case class NProgram(first : Instruction, rest : Program) extends Program
// Value stack
sealed abstract class ValueStack
case class EStack() extends ValueStack
case class NStack(v : Value, rest : ValueStack) extends ValueStack
// Outcomes of running the program
sealed abstract class Outcome
case class Ok(v : ValueStack) extends Outcome
case class Fail() extends Outcome
// Running programs on a given initial stack
def run(p : Program, vs : ValueStack) : Outcome = p match {
case EProgram() => Ok(vs)
case NProgram(i,rest) => i match {
case PushVal(v) => run(rest, NStack(v,vs))
case ApplyBinOp(op) => vs match {
case EStack() => Fail()
case NStack(v1,vs1) => vs1 match {
case EStack() => Fail()
case NStack(v2,vs2) => run(rest, NStack(evalOp(v1,op,v2),vs2))
}
}
}
}
def run0(p : Program) = run(p, EStack())
// Compiling expressions to programs
def compile(e : Expr, acc : Program) : Program = e match {
case Constant(v) => NProgram(PushVal(v), acc)
case Binary(e1,op,e2) => NProgram(ApplyBinOp(op),compile(e2,compile(e1,acc)))
}
def compile0(e : Expr) : Program = compile(e, EProgram())
// Correctness statement
// val anyS : ValueStack = EStack() // not really, but arbitrary
// val anyE : Expr = Constant(Value(42)) // not really, but arbitrary
// assert(run(compile0(anyE),anyS) == NStack(eval(anyE),anyS))
}