1 // Source language: arithmetic expressions with function calls 

     2 enum Expr {

     3     case Num(n: Int)

     4     case Aop(op: String, e1: Expr, e2: Expr)

     5     case Call(fname: String, args: List[Expr])

     6 }

     7 import Expr._

     8 

     9 // Target language 

    10 // "trivial" KValues

    11 enum KVal {

    12     case KVar(s: String)

    13     case KNum(n: Int)

    14     case KAop(op: String, v1: KVal, v2: KVal)

    15     case KCall(fname: String, args: List[KVal])

    16 }

    17 import KVal._

    18 

    19 // KExpressions 

    20 enum KExp {

    21     case KReturn(v: KVal)

    22     case KLet(x: String, v: KVal, e: KExp) 

    23 }

    24 import KExp._

    25 

    26 // Intermediate KExpressions2 

    27 enum KExp2 {

    28     case KPrim(v: KVal)

    29     case KLet2(x: String, e1: KExp2, e2: KExp2) 

    30 }

    31 import KExp2._

    32 

    33 def pexp(e: KExp): String = e match {

    34     case KReturn(v) => s"KReturn($v)"

    35     case KLet(x,e1,e2) => s"KLet($x = ${e1} \n in ${pexp(e2)})"

    36 }

    37 

    38 

    39 var cnt = -1

    40 def Fresh(s: String) = {

    41     cnt = cnt + 1

    42     s"${s}_${cnt}"

    43 }

    44 

    45 def KNorm(e: Expr): KExp2 = e match { 

    46     case Num(i) => KPrim(KNum(i))

    47     case Aop(op, l, r) => {

    48         val zl = Fresh("zl")

    49         val zr = Fresh("zr")

    50         KLet2(zl, KNorm(l), 

    51            KLet2(zr, KNorm(r), 

    52               KPrim(KAop(op, KVar(zl), KVar(zr)))))

    53     }

    54     case Call(fname, args) => {

    55         def aux(args: List[Expr], zs: List[KVal]) : KExp2 = args match {

    56             case Nil => KPrim(KCall(fname, zs))

    57             case a::as => {

    58                 val z = Fresh("z")

    59                 KLet2(z, KNorm(a), aux(as, zs ::: List(KVar(z))))

    60             }

    61         }

    62         aux(args, Nil)  

    63     }

    64 }

    65 

    66 def KNormi(e: Expr) = {

    67    val z = Fresh("z")

    68    KLet2(z, KNorm(e), KPrim(KVar(z)))

    69 }

    70 

    71 def Kdenest(ke: KExp2) : KExp = ke match {

    72     case KPrim(v) => KReturn(v)

    73     case KLet2(xt, e1, e2) => {

    74         def insert(ke: KExp) : KExp = ke match {

    75             case KLet(yt, e3, e4) => KLet(yt, e3, insert(e4))

    76             case KReturn(v) => KLet(xt, v, Kdenest(e2))

    77         }

    78         insert(Kdenest(e1))

    79     }

    80 }

    81 

    82 // Constant Folding

    83 def opt(v: KVal, env: Map[String, Int]) : KVal = v match {

    84     case KVar(s) => if (env.isDefinedAt(s)) KNum(env(s)) else KVar(s)

    85     case KNum(n) => KNum(n)

    86     case KAop(op, v1, v2) => (op, opt(v1, env), opt(v2, env)) match {

    87         case ("+", KNum(n1), KNum(n2)) => KNum(n1 + n2)

    88         case ("*", KNum(n1), KNum(n2)) => KNum(n1 * n2)

    89         case (_, v1o, v2o) => KAop(op, v1o, v2o)

    90     }

    91     case KCall(fname, args) => KCall(fname, args.map(opt(_, env)))

    92 }

    93     

    94 def Koptimise(ke: KExp, env: Map[String, Int] = Map()) : KExp = ke match {

    95     case KReturn(v) => KReturn(opt(v, env)) 

    96     case KLet(x, v, e) => opt(v, env) match {

    97         case KNum(n) => Koptimise(e, env + (x -> n))

    98         case vo => KLet(x, vo, Koptimise(e, env))

    99     }

   100 }    

   101 

   102 

   103 //1 + foo(bar(4 * -7), 3, id(12))

   104 val etest = 

   105     Aop("+", Num(1),

   106              Call("foo", 

   107                 List(Call("bar", 

   108                              List(Aop("*", Num(4), Num(-7)))), 

   109                      Num(3), 

   110                      Call("id", List(Num(12))))))

   111 

   112 val ke = Koptimise(Kdenest(KNormi(etest)))

   113 

   114 println(pexp(ke))