CPL 1-2: Semantics and Transformations

목차

 

Translating from Java to Paret

Example 1)

 

Example 2)

 

Example 3)

 

Example 4)

 

 

 

Mandatory Assignment

desugar takes an abstract syntax tree (ExprExt) as input, and returns a core syntax tree (ExprC).
interp takes a core syntax tree (ExprC) as input, and returns a value (Value).

 

1. Basics

desugar:

case TrueExt() => TrueC()
case FalseExt() => FalseC()
case NumExt(n) => NumC(n)
case NilExt() => NilC()

interp:

case TrueC() => BoolV(true)
case FalseC() => BoolV(false)
case NumC(n) => NumV(n)
case NilC() => NilV()

 

 

2. Unary Operators

desugar:

case UnOpExt(s, e) => s match {
  case "-" => MultC(NumC(-1), desugar(e))
  case "not" => IfC(desugar(e), FalseC(), TrueC())
  case "head" => HeadC(desugar(e))
  case "tail" => TailC(desugar(e))
  case "is-nil" => IsNilC(desugar(e))
  case "is-list" => IsListC(desugar(e))
  case _ => throw new DesugarExceptionImpl("Unary")
}

interp:

case HeadC(e) => interp(e) match {
  case ConsV(h, t) => h
  case _ => throw new InterpExceptionImpl("Head")
}
case TailC(e) => interp(e) match {
  case ConsV(h, t) => t
  case _ => throw new InterpExceptionImpl("Tail")
}
case IsNilC(e) => interp(e) match {
  case NilV() => BoolV(true)
  case ConsV(h, t) => BoolV(false)
  case _ => throw new InterpExceptionImpl("is nil")
}
case IsListC(e) => interp(e) match {
  case NilV() => BoolV(true)
  case ConsV(h, t) => BoolV(true)
  case _ => BoolV(false)
}

 

 

3. Binary Operators

desugar:

case BinOpExt(s, l, r) => s match {
  case "+" => PlusC(desugar(l), desugar(r))
  case "*" => MultC(desugar(l), desugar(r))
  case "-" => PlusC(desugar(l), MultC(NumC(-1), desugar(r)))
  case "and" => IfC(desugar(l), desugar(r), FalseC())
  case "or" => IfC(desugar(l), TrueC(), desugar(r))
  case "num=" => EqNumC(desugar(l), desugar(r))
  case "num<" => LtC(desugar(l), desugar(r))
  case "num>" => LtC(desugar(r), desugar(l))
  case "cons" => ConsC(desugar(l), desugar(r))
  case _ => throw new DesugarExceptionImpl("Binary")
}

 

interp:

case PlusC(l, r) => (interp(l), interp(r)) match {
  case (NumV(l), NumV(r)) => NumV(l+r)
  case _ => throw new InterpExceptionImpl("Plus")
}
case MultC(l, r) => (interp(l), interp(r)) match {
  case (NumV(l), NumV(r)) => NumV(l*r)
  case _ => throw new InterpExceptionImpl("Plus")
}
case EqNumC(l, r) => (interp(l), interp(r)) match {
  case (NumV(l), NumV(r)) => BoolV(l==r)
  case _ => throw new InterpExceptionImpl("EqNum")
}
case LtC(l, r) => (interp(l), interp(r)) match {
  case (NumV(l), NumV(r)) => BoolV(l < r)
  case _ => throw new InterpExceptionImpl("LtC")
}

 

 

4. If statement

desugar:

case IfExt(c, t, e) => IfC(desugar(c), desugar(t), desugar(e))

 

interp:

case IfC(c, t, e) => interp(c) match {
  case BoolV(true) => interp(t)
  case BoolV(false) => interp(e)
  case _ => throw new InterpExceptionImpl("IF")
}

 

 

5. List

desugar: ConsC로 변환

case ListExt(l) => desugarList(l)

def desugarList(l: List[ExprExt]) : ExprC = l match {
  case Nil => NilC()
  case h :: t => ConsC(desugar(h), desugarList(t))
}

 

interp

case ConsC(l, r) => ConsV(interp(l), interp(r))

 

 

6. cond

desugar:

case CondExt(cs) => desugarCond(cs)

def desugarCond(cs: List[(ExprExt, ExprExt)]): ExprC = cs match {
  case Nil => UndefinedC()
  case (e1, e2) :: t => IfC(desugar(e1), desugar(e2), desugarCond(t))
  case _ => throw DesugarExceptionImpl("Cond") 
}

 

Multi-armed conditional이기 때문에 IfC형태로 변환. 

(e1  e2)뜻은 만약에 e1=true, then execute e2이기 때문에 이 두개를 IfC에 먼저 넣어주고 나머지 condition들이 있을 수 있기 때문에 IfC 뒤에 넣어준다.

 

7. condE

  case CondEExt(cs, e) => desugarCondE(cs, e)

  
  def desugarCondE(cs: List[(ExprExt, ExprExt)], e: ExprExt): ExprC = cs match {
    case Nil => desugar(e)
    case (e1, e2) :: t => IfC(desugar(e1), desugar(e2), desugarCondE(t, e))
    case _ => throw DesugarExceptionImpl("Cond") 
  }

 

condE도 multi-armed conditional인데 여기에는 else가 있다.