Advertisement
VladNitu

Untitled

Apr 18th, 2023
884
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Scala 9.28 KB | None | 0 0
  1. import Library._
  2. import Untyped._
  3. import Parser._
  4.  
  5. case class NotImplementedException(s: String) extends RuntimeException(s)
  6. case class DesugarOpInvalidExcep(s: String) extends DesugarException(s)
  7. case class InterpOpInvalidExcep(s: String) extends InterpException(s)
  8.  
  9.  
  10.  
  11. object Desugar {
  12.  
  13.   val ZCombinator =
  14.   """
  15.  (lambda (f)
  16.    ((lambda (y)
  17.       (y y))
  18.     (lambda (z)
  19.       (f (lambda (x)
  20.            ((z z) x))))))
  21.  """
  22.  
  23.  
  24.   def desugarList (l: List[ExprExt]): ExprC = l match {
  25.     case h :: t => ConsC(desugar(h), desugarList(t))
  26.     case _ => NilC()
  27.   }
  28.  
  29.   def solveCondEExt(cs: List[(ExprExt, ExprExt)], e: ExprExt): ExprC = (cs, e) match {
  30.     case ((e1, e2) :: t, e)=> IfC(desugar(e1), desugar(e2), solveCondEExt(t, e))
  31.     case _ => desugar(e)
  32.   }
  33.  
  34.    def solveCondExt(cs: List[(ExprExt, ExprExt)]): ExprC = cs match {
  35.     case (e1, e2) :: t => IfC(desugar(e1), desugar(e2), solveCondExt(t))
  36.     case _ => UndefinedC()
  37.   }
  38.  
  39.   def desugar(e: ExprExt): ExprC = e match {
  40.  
  41.     case NilExt() => NilC()
  42.     case TrueExt() => TrueC()
  43.     case FalseExt() => FalseC()
  44.     case NumExt(x) => NumC(x)
  45.     case BinOpExt(sym, l, r) => sym match {
  46.       case "+" => PlusC(desugar(l), desugar(r))
  47.       case "*" => MultC(desugar(l), desugar(r))
  48.       case "-" => PlusC(desugar(l), MultC(NumC(-1), desugar(r))) // l - r
  49.      
  50.  
  51.       // TODO: Check AND FALSE, OR TRUE logic
  52.       case "and" => IfC(desugar(l), desugar(r), FalseC()) // OR (for a strictly-typed language): IfC(desugar(l), desugar(r), FalseC())
  53.       case "or" => IfC(desugar(l), desugar(l), desugar(r)) // OR (for a strictly-typed language): IfC(desugar(l), TrueC(), desugar(r))
  54.  
  55.       case "num=" => EqNumC(desugar(l), desugar(r))
  56.       case "num<" => LtC(desugar(l), desugar(r))
  57.       case "num>" => LtC(desugar(r), desugar(l)) // (l > r) <=> (r < l)
  58.       case "cons" => ConsC(desugar(l), desugar(r))
  59.  
  60.       case _ => throw new DesugarOpInvalidExcep("Cannot desugarize this binary operator: " + sym);
  61.     }
  62.  
  63.     case UnOpExt(sym, l) => sym match {
  64.       case "-" => MultC(NumC(-1), desugar(l))
  65.       case "not" => IfC(desugar(l), FalseC(), TrueC())
  66.       case "head" => HeadC(desugar(l))
  67.       case "tail" => TailC(desugar(l))
  68.       case "is-nil" => IsNilC(desugar(l))
  69.       case "is-list" => IsListC(desugar(l))
  70.  
  71.       // NEW
  72.       case "print" => PrintC(desugar(l))
  73.       case "force" => ForceC(desugar(l))
  74.  
  75.       case _ => throw new DesugarOpInvalidExcep("Cannot desugarize this unary operator: " + sym);
  76.     }
  77.     case ListExt(l) => l match { // Alternative: ConsC(desugar(h), desugar(ListExt(t))) // !!: generative recursion;
  78.       case h :: t => desugarList(l)
  79.       case _ => NilC()
  80.     }
  81.  
  82.     case IfExt(c, t, e) => IfC(desugar(c), desugar(t), desugar(e))
  83.    
  84.     case CondExt(cs) => solveCondExt(cs)
  85.  
  86.     case CondEExt(cs, e) => solveCondEExt(cs, e)
  87.  
  88.     // Newly added
  89.  
  90.     case AppExt(f, args) => AppC(desugar(f), args.map(arg => desugar(arg)))
  91.  
  92.     case IdExt(c) => IdC(c)
  93.  
  94.     case FdExt(params, body) => FdC(params, desugar(body))
  95.  
  96.     // LetExt should be desugared into AppC
  97.     case LetExt(binds, body) => AppC(
  98.       FdC(binds.map(bind => bind.name), desugar(body)),
  99.       binds.map(bind => desugar(bind.value)) // List[ExprExt]
  100.     )
  101.  
  102.     // Make use of Z_Combinator from Lecture Notes (!);
  103.     // Desugar RecLamExt as a AppC(ZComb, FdC(name, FdC(param), body)) <=> Application of ZComb function that takes as a parameter the body of actual function
  104.     case RecLamExt(name, param, body) => AppC (
  105.       desugar(parse(ZCombinator)),
  106.       List(FdC(List(name), FdC(List(param), desugar(body))))
  107.     )
  108.  
  109.     // NEW
  110.     case LetRecExt(binds, body) => LetRecC(binds.map(bind => LetBindC(bind.name, desugar(bind.value))), desugar(body))
  111.    
  112.   }
  113. }
  114.  
  115. object Interp {
  116.   def interp(e: ExprC): Value = interp(e, Nil)
  117.    def take(myEnv: Environment, name: String): Value = myEnv match {
  118.     case Nil => throw new InterpOpInvalidExcep(s"Could not find $name in environment `nv`")
  119.     case Bind(name_, value) :: t if name_ == name =>  value
  120.     case Bind(name_, value) :: t => take(t, name)
  121.   }
  122.  
  123.   // def letRecLazy(binds: List[LetBindC], body: ExprC, nv: Environment)
  124.  
  125.   def updateEnv(nv: Environment, binds: List[Value]): Unit = binds match {
  126.     case bind :: bindsTail => {
  127.       nv.head.value = bind
  128.       updateEnv(nv.tail, bindsTail)
  129.     }
  130.     case Nil => {}
  131.   }
  132.  
  133.   def produceOutput(v: Value): Unit = v match {
  134.           case NumV(n) => print(s"$n")
  135.           case BoolV(b) => print(s"$b")
  136.           case NilV() => print("[]")
  137.           case ConsV(head, tail) => {
  138.             print("[")
  139.             produceOutput(strict(head))
  140.             print(" ")
  141.             produceOutput(strict(tail))
  142.             print("]")
  143.           }
  144.           case ClosV(f, env) => print("<closure>")
  145.           case UninitializedV() => print("<uninitialized>")
  146.           case _ => throw new InterpOpInvalidExcep("produceOutput err")
  147.         }
  148.  
  149.  
  150.   def interp(e: ExprC, nv: Environment): Value = e match {
  151.    
  152.     case NilC() => NilV()
  153.     case TrueC() => BoolV(true)
  154.     case FalseC() => BoolV(false)
  155.     case NumC(x) => NumV(x)
  156.  
  157.     case PlusC(l, r) => (strict(interp(l, nv)), strict(interp(r, nv))) match {
  158.       case (NumV(a), NumV(b)) => NumV(a + b)
  159.       case _ => throw new InterpOpInvalidExcep("These operations are only defined for numbers")
  160.     }
  161.  
  162.     case MultC(l, r) => (strict(interp(l, nv)), strict(interp(r, nv))) match {
  163.       case (NumV(a), NumV(b)) => NumV(a * b)
  164.       case _ => throw new InterpOpInvalidExcep("These operations are only defined for numbers")
  165.     }
  166.  
  167.     case EqNumC(l, r) => (strict(interp(l, nv)), strict(interp(r, nv))) match {
  168.       case (NumV(a), NumV(b)) => if (a == b) BoolV(true) else BoolV(false)
  169.       case _ => throw new InterpOpInvalidExcep("These operations are only defined for numbers")
  170.     }
  171.  
  172.     case LtC(l, r) => (strict(interp(l, nv)),  strict(interp(r, nv))) match {
  173.       case (NumV(a), NumV(b)) => if (a < b) BoolV(true) else BoolV(false)
  174.       case _ => throw new InterpOpInvalidExcep("These operations are only defined for numbers")
  175.     }
  176.  
  177.  
  178.     case ConsC(l, r) => ConsV(ThunkV(Left(l, nv)), ThunkV(Left(r, nv)))
  179.  
  180.     case HeadC(e) => strict(interp(e, nv)) match {
  181.     case ConsV(h, _) => h
  182.     case x => throw new InterpOpInvalidExcep(s"HEAD not allowed: $x")
  183.     }
  184.  
  185.     case TailC(e) => strict(interp(e, nv)) match {
  186.     case ConsV(_, t) => t
  187.     case _ => throw new InterpOpInvalidExcep("TAIL not allowed")
  188.     }
  189.  
  190.     case IsNilC(e) => strict(interp(e, nv)) match {
  191.       case NilV() => BoolV(true)
  192.       case ConsV(_, _) => BoolV(false)
  193.       case _ => throw new InterpOpInvalidExcep("IS_NIL not allowed")
  194.     }
  195.  
  196.     case IsListC(e) => strict(interp(e, nv)) match {
  197.       case NilV() | ConsV(_, _) => BoolV(true)
  198.       case _ => BoolV(false)
  199.     }
  200.  
  201.     case IfC(e, e1, e2) => strict(interp(e, nv)) match {
  202.       case BoolV(true) => interp(e1, nv)
  203.       case BoolV(false) => interp(e2, nv)
  204.       case _ => throw new InterpOpInvalidExcep("IF not allowed as _e_ does not evaluate to Boolean")
  205.     }
  206.  
  207.       // NEW
  208.  
  209.       case PrintC(e) =>
  210.         val v = strict(interp(e, nv))
  211.         produceOutput(v)
  212.         println()
  213.         v
  214.  
  215.       case ForceC(e) => force(interp(e, nv))
  216.  
  217.       case LetRecC(binds, body) =>
  218.         val bindsThunked: List[Bind] = binds.map(bind => Bind(bind.name, UninitializedV()))
  219.         updateEnv(bindsThunked, binds.map(bind => ThunkV(Left((bind.value, bindsThunked ::: nv)))))
  220.         interp(body, bindsThunked ::: nv)
  221.  
  222.       case UndefinedC() => throw new InterpOpInvalidExcep("Desugarizing went wrong!")
  223.  
  224.  
  225.     // Newly added
  226.  
  227.     // See notes (3) Interp AppC
  228.       // match on the interpreted value of (f, nv)
  229.     case AppC(f: ExprC, args: List[ExprC]) => strict(interp(f, nv)) match {
  230.       case ClosV(FdC(params, body), env) if params.size == args.size => { // NOTE!: `f` param. from ClosV shadows `f` param from case AppC(f:ExprC)
  231.           val params_args: List[(String, Value)] = params.zip(args.map(arg => ThunkV(Left((arg, nv))))) // arguments should be evaluated in the `nv` environment, so the current one before applying the function
  232.           val binded_params_args: List[Bind] =  params_args.map {case (param, arg) => Bind(param, arg)}
  233.           interp(body, binded_params_args ::: env) // The function body evaluation SHOULD also take the environment of the Closure of
  234.         }
  235.  
  236.       case _ => throw new InterpOpInvalidExcep("Error thrown in case AppC - `f` IS NOT a closure")
  237.     }
  238.  
  239.     case IdC(c) => take(nv, c)
  240.  
  241.     case fdc@FdC(params, body) => ClosV(fdc, nv) // Use `named patterns`
  242.  
  243.     case _ => throw new UnknownInstructionInterpException(e)
  244.  
  245.   }
  246.  
  247.   def strict(v: Value): Value = v match {
  248.     case thunk@ThunkV(Left((e, nv))) => {
  249.       // System.out.println(ans + "----------" + strict(ans))
  250.       val ans = strict(interp(e, nv))
  251.       thunk.value = Right(ans) // update thunk
  252.       ans
  253.     }
  254.     case ThunkV(Right(e)) => e
  255.     case x => x
  256.   }
  257.  
  258.   def force(v: Value): Value = v match {
  259.     case thunk@ThunkV(Left((e, nv))) =>  {
  260.       val ans = force(interp(e, nv))
  261.       thunk.value = Right(ans) // update thunk
  262.       ans
  263.     }
  264.     case ThunkV(Right(e)) => force(e)
  265.     case ConsV(l, r) => ConsV(force(l), force(r))
  266.     case x => x
  267.    
  268.   }
  269. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement