API tools faq
paste
Advertisement
VladNitu

Untitled

VladNitu
Apr 18th, 2023
903
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Scala 9.28 KB | None | 0 0
raw download clone embed print report
  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
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!