Snippets

Peter Lane Paradigms - unit 1: Operational Semantics for Expressions

Created by Peter Lane
// First, define the basic data types for expressions
// We make everything a kind of Expr
class Expr
case class Numeral(r:Int) extends Expr
case class Neg(e:Expr) extends Expr
case class Sum(e1:Expr,e2:Expr) extends Expr
case class Diff(e1:Expr,e2:Expr) extends Expr
case class Prod(e1:Expr,e2:Expr) extends Expr
case class Quot(e1:Expr,e2:Expr) extends Expr

// For the operational semantics, we also want labels "just-sum" etc
// define these as Expr types too
case class JustNeg() extends Expr
case class JustSum() extends Expr
case class JustDiff() extends Expr
case class JustProd() extends Expr
case class JustQuot() extends Expr

// Second, define an operational semantics for expressions
// The control/value stacks are handled as lists

def ops (cstack:List[Expr], vstack:List[Int]):Int = {
  (cstack, vstack) match {
    // Finish successfully
    case (Nil, v::vs) => v 
    // handle Numeral
    case (Numeral(r)::cs, vs) => ops(cs, r::vs) 
    // handle Neg
    case (Neg(e)::cs, vs) => ops(e::JustNeg()::cs,vs) 
    case (JustNeg()::cs, v::vs) => ops(cs, (-v)::vs) 
    // handle Sum
    case (Sum(e1,e2)::cs, vs) => ops(e2::e1::JustSum()::cs,vs)
    case (JustSum()::cs, v1::v2::vs) => ops(cs, (v1+v2)::vs)
    // handle Diff
    case (Diff(e1,e2)::cs, vs) => ops(e2::e1::JustDiff()::cs,vs)
    case (JustDiff()::cs, v1::v2::vs) => ops(cs, (v1-v2)::vs)
    // handle Prod
    case (Prod(e1,e2)::cs, vs) => ops(e2::e1::JustProd()::cs,vs)
    case (JustProd()::cs, v1::v2::vs) => ops(cs, (v1*v2)::vs)
    // handle Quot
    case (Quot(e1,e2)::cs, vs) => ops(e2::e1::JustQuot()::cs,vs)
    case (JustQuot()::cs, v1::v2::vs) => ops(cs, (v1/v2)::vs)
    // some error has occurred
    case _ => println ("ERROR!"); 0
  }
}

// top-level function to interpret an expression
def interpretExpr (e:Expr) = {
  println ("Interpreting: " + e)
  println ("  ==> " + ops(List(e), Nil))
}

// ******************************************************
// Examples of using the semantics as an interpreter

// Sample expressions - parsing step not implemented
// 3
val ex1 = Numeral(3)
// 3+4
val ex2 = Sum(Numeral(3),Numeral(4))
// 3*5-2
val ex3 = Diff(Prod(Numeral(3),Numeral(5)),Numeral(2))

// To 'interpret' an expression, just pass it to 'interpretExpr'

interpretExpr(ex1)
interpretExpr(ex2)
interpretExpr(ex3)

Comments (0)