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 var cnt = -1

    27 def Fresh(s: String) = {

    28     cnt = cnt + 1

    29     s"${s}_${cnt}"

    30 }

    31 

    32 def CPS(e: Expr)(k: KVal => KExp): KExp = e match { 

    33     case Num(i) => k(KNum(i))

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

    35         val z = Fresh("z")

    36         CPS(l)(l => 

    37           CPS(r)(r => KLet(z, KAop(op, l, r), k(KVar(z)))))

    38     }

    39     case Call(fname, args) => {

    40         def aux(args: List[Expr], vs: List[KVal]) : KExp = args match {

    41             case Nil => {

    42                 val z = Fresh("tmp")

    43                 KLet(z, KCall(fname, vs), k(KVar(z)))

    44             }

    45             case a::as => CPS(a)(r => aux(as, vs ::: List(r)))

    46         }

    47         aux(args, Nil)  

    48     }

    49 }

    50 

    51 def CPSi(e: Expr) : KExp = CPS(e)(KReturn(_))

    52 

    53 

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

    55 val etest = 

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

    57              Call("foo", 

    58                 List(Call("bar", 

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

    60                      Num(3), 

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

    62 

    63 println(CPSi(etest))