API tools faq
paste
VladNitu

ObjectVlad

VladNitu
Apr 2nd, 2023
169
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Scala 15.01 KB | None | 0 0
raw download clone embed print report
  1. import Library._
  2. import Parser._
  3. import Untyped._
  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.         object Desugar {
  10.  
  11.         val ZCombinator =
  12.         """
  13.  (lambda (f)
  14.    ((lambda (y)
  15.       (y y))
  16.     (lambda (z)
  17.       (f (lambda (x)
  18.            ((z z) x))))))
  19.  """
  20.  
  21.  
  22.         def desugarList (l: List[ExprExt]): ExprC = l match {
  23.         case h :: t => ConsC(desugar(h), desugarList(t))
  24.         case _ => NilC()
  25.         }
  26.  
  27.         /** Binds all the values before processing the `body`, so that all the names are in scope */
  28.         def solveLetBinds(binds: List[LetBindExt], body: ExprExt): ExprC = binds match {
  29.         case LetBindExt(name, value) :: t => SeqC(SetC(name, desugar(value)), solveLetBinds(t, body))
  30.         case Nil => desugar(body)  // No more bindings to declare
  31.         }
  32.  
  33.         def desugarMethods(methods: List[MethodExt]): ExprC = methods match {
  34.         case Nil => UndefinedC()
  35.         case meth :: t => IfC(EqStrC(IdC("msg"), StringC(meth.name)), FdC("self" :: meth.args, desugar(meth.body)), desugarMethods(t))
  36.         }
  37.  
  38.         def desugarMethodsDelegate(methods: List[MethodExt]): ExprC = methods match {
  39.         case Nil => AppC(IdC("method"), List(IdC("msg")))
  40.         case meth :: t => IfC(EqStrC(IdC("msg"), StringC(meth.name)), FdC("self" :: meth.args, desugar(meth.body)), desugarMethodsDelegate(t))
  41.         }
  42.        
  43.         // OBJECTS
  44.  
  45.         def solveLetBindsObjects(binds: List[FieldExt], body: ExprC): ExprC = binds match {
  46.         case FieldExt(name, value) :: t => SeqC(SetC(name, desugar(value)), solveLetBindsObjects(t, body))
  47.         case Nil => body  // No more bindings to declare
  48.         }
  49.  
  50.         def desugarDoSeq (l: List[ExprExt]): ExprC = l match {
  51.         case h :: Nil => desugar(h)
  52.         case h :: t :: Nil => SeqC(desugar(h), desugar(t))
  53.         case h :: t => SeqC(desugar(h), desugarDoSeq(t))
  54.         }
  55.  
  56.         def desugar(e: ExprExt): ExprC = e match {
  57.  
  58.         case NilExt() => NilC()
  59.         case TrueExt() => TrueC()
  60.         case FalseExt() => FalseC()
  61.         case NumExt(x) => NumC(x)
  62.         case BinOpExt(sym, l, r) => sym match {
  63.         case "+" => PlusC(desugar(l), desugar(r))
  64.         case "*" => MultC(desugar(l), desugar(r))
  65.         case "-" => PlusC(desugar(l), MultC(NumC(-1), desugar(r)))
  66.  
  67.         case "and" => IfC(desugar(l), desugar(r), FalseC())
  68.         case "or" => IfC(desugar(l), TrueC(), desugar(r))
  69.  
  70.         case "num=" => EqNumC(desugar(l), desugar(r))
  71.         case "num<" => LtC(desugar(l), desugar(r))
  72.         case "num>" => LtC(MultC(NumC(-1), desugar(l)), MultC(NumC(-1), desugar(r))) // In interp, evaluate `l` first while also use `LtC` => Multiply eq. by (-1) on both sides
  73.         case "cons" => ConsC(desugar(l), desugar(r))
  74.  
  75.         case "setbox" => SetboxC(desugar(l), desugar(r))
  76.         case "seq" => SeqC(desugar(l), desugar(r))
  77.  
  78.         // NEW
  79.         case "str=" => EqStrC(desugar(l), desugar(r))
  80.         case "str++" => ConcStrC(desugar(l), desugar(r))
  81.  
  82.  
  83.         case _ => throw new DesugarOpInvalidExcep(s"Cannot desugarize this binary operator: $sym")
  84.         }
  85.  
  86.         case UnOpExt(sym, l) => sym match {
  87.         case "-" => MultC(NumC(-1), desugar(l))
  88.         case "not" => IfC(desugar(l), FalseC(), TrueC())
  89.         case "head" => HeadC(desugar(l))
  90.         case "tail" => TailC(desugar(l))
  91.         case "is-nil" => IsNilC(desugar(l))
  92.         case "is-list" => IsListC(desugar(l))
  93.  
  94.         // Newly added unOps: `box`, `unbox`
  95.         case "box" => BoxC(desugar(l))
  96.         case "unbox" => UnboxC(desugar(l))
  97.  
  98.         case _ => throw new DesugarOpInvalidExcep("Cannot desugarize this unary operator: " + sym);
  99.         }
  100.         case ListExt(l) => l match { // Alternative: ConsC(desugar(h), desugar(ListExt(t))) // !!: generative recursion;
  101.         case h :: t => desugarList(l)
  102.         case _ => NilC()
  103.         }
  104.  
  105.         case IfExt(c, t, e) => IfC(desugar(c), desugar(t), desugar(e))
  106.  
  107.         case AppExt(f, args) => AppC(desugar(f), args.map(arg => desugar(arg)))
  108.  
  109.         case IdExt(c) => IdC(c)
  110.  
  111.         case FdExt(params, body) => FdC(params, desugar(body))
  112.  
  113.         case LetExt(binds, body) => AppC(
  114.         FdC(binds.map(bind => bind.name), desugar(body)),
  115.         binds.map(bind => desugar(bind.value))
  116.         )
  117.         case SetExt(id, e) => SetC(id, desugar(e))
  118.  
  119.         // Make use of Z_Combinator from Lecture Notes (!);
  120.         // Desugar RecLamExt as a AppC(ZComb, FdC(List(name), FdC(List(param)), body)) <=> Application of ZComb function that takes as a parameter the body of actual function
  121.         case RecLamExt(name, param, body) => AppC (
  122.         desugar(parse(ZCombinator)),
  123.         List(FdC(List(name), FdC(List(param), desugar(body))))
  124.         )
  125.  
  126.         // Newly added: `LetRecExt`, which makes use of `LetBindExt`
  127.         // Desugar `let-rec` into `AppC`; ALTERNATIVE - desugar `let-rec` into `let`, but this would imply generative recursion
  128.         // 2 pass algorithm:
  129.         // 1. Scan bindings; Create bindings for all names in `let-rec` w/ `UninitializedC`
  130.         // 2. Rescan when evaluating (in interp) and update the bindings' values accordingly
  131.         case LetRecExt(binds, body) => AppC(
  132.         FdC(binds.map(bind => bind.name), solveLetBinds(binds, body)),
  133.         binds.map(bind => UninitializedC()) // Allow `indirect recursion`
  134.         )
  135.  
  136.         // NEW
  137.         case StringExt(str) => StringC(str)
  138.  
  139.         case ObjectExt(fields: List[FieldExt], methods: List[MethodExt]) => {
  140.  
  141.         if (fields.size == 0) throw new DesugarOpInvalidExcep("Objects must have at least one filed")
  142.  
  143.         val body = FdC(List("msg"), desugarMethods(methods))
  144.  
  145.         AppC ( // LetRecExt desugar
  146.         FdC(fields.map(bind => bind.name), solveLetBindsObjects(fields, body)),
  147.         fields.map(bind => UninitializedC())
  148.         )
  149.         }
  150.  
  151.  
  152.         case ObjectDelExt(del: ExprExt, fields: List[FieldExt], methods: List[MethodExt]) => {
  153.         // IDEA: Parametrize all methods by `self`
  154.  
  155.         val delegate = desugar(del)
  156.  
  157.         val body = FdC(List("msg"), desugarMethodsDelegate(methods))
  158.  
  159.         AppC ( // LetRecExt desugar
  160.         FdC("method" :: fields.map(bind => bind.name), solveLetBindsObjects(fields, body)),
  161.         delegate :: fields.map(bind => UninitializedC())
  162.         )
  163.  
  164.         }
  165.  
  166.  
  167.         case MsgExt(recvr: ExprExt, msg: String, args: List[ExprExt]) => {
  168.         val initBody = AppC(AppC(IdC("self"), List(StringC(msg))), IdC("self") :: args.map(desugar))
  169.         AppC(FdC(List("self"), initBody), List(desugar(recvr)))
  170.         }
  171.  
  172.         case DoSeqExt(expr: List[ExprExt]) => {
  173.         // Parser ensures the following cond:
  174.         //  if (expr.size < 1) throw new DesugarOpInvalidExcep("do-seq expressions should always have at least one subexpression")
  175.         if (expr.size == 1)
  176.         desugar(expr(0))
  177.         else
  178.         desugarDoSeq(expr)
  179.         }
  180.  
  181.  
  182.         }
  183.         }
  184.  
  185.         object Interp {
  186.         type Store = List[Cell]
  187.         type PointerEnvironment = List[Pointer]
  188.  
  189.         // Do not remove this method. We use this for grading.
  190.         def interp(e: ExprC): Value = interp(e, Nil, Nil)._1
  191.  
  192.         // Helper methods from assignment "Manipulating Stores"
  193.  
  194.         def lookup(name: String, nv: PointerEnvironment): Int = nv match {
  195.         case Nil => throw new InterpOpInvalidExcep("Identifier not found")
  196.         case Pointer(_name, location) :: t if _name == name => location
  197.         case h :: t => lookup(name, t)
  198.         }
  199.  
  200.         def update(loc: Int, st: Store, v: Value): Store = st match {
  201.         case Nil => throw new InterpOpInvalidExcep("Cell location not found")
  202.         case Cell(location, value) :: t if location == loc => Cell(loc, v) :: t
  203.         case h :: t => h :: update(loc, t, v)
  204.         }
  205.  
  206.         def fetch(loc: Int, st: Store): Value = st match {
  207.         case Nil => throw new InterpOpInvalidExcep("Cell location not found")
  208.         case Cell(location, value) :: t if location == loc => value
  209.         case h :: t => fetch(loc, t)
  210.         }
  211.  
  212.         def newLoc(store: Store): Int = store.length
  213.  
  214.         def extendStore(c: Cell, st: Store): Store = c :: st
  215.  
  216.         def interpArgs(args: List[ExprC], nv: PointerEnvironment, st1: Store): (List[Value], Store) = args match {
  217.         case Nil => (Nil, st1) // base case -> Empty list in current environment; later on prepend to List[Value]s
  218.         case arg :: t => {
  219.         val (v, st2): (Value, Store) = interp(arg, nv, st1)
  220.         val (values, st3) = interpArgs(t, nv, st2)
  221.         (v :: values, st3)
  222.         }
  223.         }
  224.  
  225.         def extendEnvStore(params: List[String], interpretedArgs: List[Value], nv: PointerEnvironment, st1: Store): (PointerEnvironment, Store)
  226.         =  (params, interpretedArgs) match { // REMEMBER: params.length == interpretedArgs.length
  227.         case (Nil, Nil) => (nv, st1)
  228.         case (param :: t_params, arg :: t_args) => {
  229.         val newLocation = newLoc(st1)
  230.         val newPointer: Pointer = Pointer(param, newLocation)
  231.         val extendedNv: PointerEnvironment = newPointer :: nv
  232.         val extendedStore: Store = extendStore(Cell(newLocation, arg), st1)// Extend store by prepending new values to previous Store
  233.         extendEnvStore(t_params, t_args, extendedNv, extendedStore)
  234.         }
  235.         }
  236.  
  237.         def interp(e: ExprC, nv: PointerEnvironment, st1: Store): (Value, Store) = e match {
  238.  
  239.         case NilC() => (NilV(), st1)
  240.         case TrueC() => (BoolV(true), st1)
  241.         case FalseC() => (BoolV(false), st1)
  242.         case NumC(x) => (NumV(x), st1)
  243.  
  244.         case PlusC(l, r) => {
  245.  
  246.         val (v1, st2) = interp(l, nv, st1)
  247.         val (v2, st3) = interp(r, nv, st2)
  248.  
  249.         (v1, v2) match {
  250.         case (NumV(a), NumV(b)) => (NumV(a + b), st3)
  251.         case _ => throw new InterpOpInvalidExcep("These operations are only defined for numbers")
  252.         }
  253.         }
  254.  
  255.         case MultC(l, r) => {
  256.  
  257.         val (v1, st2) = interp(l, nv, st1)
  258.         val (v2, st3) = interp(r, nv, st2)
  259.  
  260.         (v1, v2) match {
  261.         case (NumV(a), NumV(b)) => (NumV(a * b), st3)
  262.         case _ => throw new InterpOpInvalidExcep("These operations are only defined for numbers")
  263.         }
  264.         }
  265.  
  266.         case EqNumC(l, r) => {
  267.  
  268.         val (v1, st2) = interp(l, nv, st1)
  269.         val (v2, st3) = interp(r, nv, st2)
  270.  
  271.         (v1, v2) match {
  272.         case (NumV(a), NumV(b)) => if (a == b) (BoolV(true), st3) else (BoolV(false), st3)
  273.         case _ => throw new InterpOpInvalidExcep("These operations are only defined for numbers")
  274.         }
  275.         }
  276.  
  277.         case LtC(l, r) => {
  278.  
  279.         val (v1, st2) = interp(l, nv, st1)
  280.         val (v2, st3) = interp(r, nv, st2)
  281.  
  282.         (v1, v2) match {
  283.         case (NumV(a), NumV(b)) => if (a < b) (BoolV(true), st3) else (BoolV(false), st3)
  284.         case _ => throw new InterpOpInvalidExcep("These operations are only defined for numbers")
  285.         }
  286.         }
  287.  
  288.  
  289.         case ConsC(l, r) => {
  290.         val (v1, st2) = interp(l, nv, st1)
  291.         val (v2, st3) = interp(r, nv, st2)
  292.  
  293.         (ConsV(v1, v2), st3)
  294.         }
  295.  
  296.  
  297.         case HeadC(e) => interp(e, nv, st1) match {
  298.         case (ConsV(h, _), st2) => (h, st2)
  299.         case _ => throw new InterpOpInvalidExcep("HEAD not allowed")
  300.         }
  301.  
  302.         case TailC(e) => interp(e, nv, st1) match {
  303.         case (ConsV(_, t), st2) => (t, st2)
  304.         case _ => throw new InterpOpInvalidExcep("TAIL not allowed")
  305.         }
  306.  
  307.         case IsNilC(e) => interp(e, nv, st1) match {
  308.         case (NilV(), st2) => (BoolV(true), st2)
  309.         case (ConsV(_, _), st2) => (BoolV(false), st2)
  310.         case _ => throw new InterpOpInvalidExcep("isNil not allowed")
  311.         }
  312.  
  313.         case IsListC(e) => {
  314.         val (v1, st2) = interp(e, nv, st1)
  315.         v1 match {
  316.         case NilV() | ConsV(_, _) => (BoolV(true), st2)
  317.         case _ => (BoolV(false), st2)
  318.         }
  319.         }
  320.  
  321.         case IfC(e, e1, e2) => interp(e, nv, st1) match {
  322.         case (BoolV(true), st2) => interp(e1, nv, st2)
  323.         case (BoolV(false), st2) => interp(e2, nv, st2)
  324.         case _ => throw new InterpOpInvalidExcep(s"IF not allowed as $e does not evaluate to Boolean")
  325.         }
  326.  
  327.         case UninitializedC() => (UninitializedV(), st1)
  328.  
  329.         case AppC(f, args) => interp(f, nv, st1) match {
  330.         case (PointerClosV(f@FdC(params, body), env), st2) => {
  331.         //Alternative - val (interpretedArgs, st3) = interpArgsAlt(args, nv, st2, Nil)
  332.         val (interpretedArgs, st3) = interpArgs(args, nv, st2)
  333.         val (envNew, stNew): (PointerEnvironment, Store) = extendEnvStore(params, interpretedArgs, env, st3)
  334.         interp(body, envNew, stNew)
  335.         }
  336.         //case FdC(params, body) if (params.size != args.size) => throw new InterpOpInvalidExcep("Error thrown in case AppC/ClosV - Number of `params` and `args` do not match")
  337.         case _ => throw new InterpOpInvalidExcep("Error thrown in case AppC/ClosV - `f` IS NOT a function definition")
  338.         }
  339.  
  340.         case IdC(s) =>  (fetch(lookup(s, nv), st1), st1)
  341.  
  342.         case fdc@FdC(params, body) => (PointerClosV(fdc, nv), st1)
  343.  
  344.         case BoxC(v) => {
  345.         val (v1, st2) = interp(v, nv, st1)
  346.         val newLocation = newLoc(st2)
  347.         (BoxV(newLocation), extendStore(Cell(newLocation, v1), st2))
  348.         }
  349.  
  350.         case UnboxC(b) => {
  351.         val (b1, st2) = interp(b, nv, st1)
  352.         b1 match {
  353.         case BoxV(loc) => (fetch(loc, st2), st2)
  354.         case _ => throw new InterpOpInvalidExcep(s"Cannot unbox $b1, as it is not a box")
  355.         }
  356.         }
  357.  
  358.         case SetboxC(b, c) => { // REMEMBER - left->right evaluation order
  359.  
  360.         val (b1, st2) = interp(b, nv, st1)
  361.         val (b2, st3) = interp(c, nv, st2)
  362.  
  363.         b1 match {
  364.         case BoxV(loc) => (b2, update(loc, st3, b2))
  365.         case _ => throw new InterpOpInvalidExcep(s"Cannot Setbox $b1, as it is not a box")
  366.         }
  367.  
  368.         }
  369.  
  370.         case SetC(v, b) => interp(b, nv, st1) match{
  371.         case (v1, st2) => (v1, update(lookup(v, nv), st2, v1))
  372.         case _ => throw new InterpOpInvalidExcep("SetC not allowed.")
  373.         }
  374.  
  375.         case SeqC(b1, b2) => {
  376.         val st2 = interp(b1, nv, st1)._2
  377.         interp(b2, nv, st2)
  378.         }
  379.  
  380.         // NEW
  381.         case EqStrC(l, r) => {
  382.         val (v1, st2) = interp(l, nv, st1)
  383.         val (v2, st3) = interp(r, nv, st2)
  384.         (v1, v2) match {
  385.         case (StringV(s1), StringV(s2)) => if (s1 == s2) (BoolV(true), st3) else (BoolV(false), st3)
  386.         case _ => throw new InterpOpInvalidExcep("EqStringC not allowed.")
  387.         }
  388.         }
  389.         case ConcStrC(l, r) => {
  390.         val (v1, st2) = interp(l, nv, st1)
  391.         val (v2, st3) = interp(r, nv, st2)
  392.  
  393.         (v1, v2) match {
  394.         case (StringV(s1), StringV(s2)) => (StringV(s1 + s2), st3)
  395.         case _ => throw new InterpOpInvalidExcep("EqStringC not allowed.")
  396.         }
  397.  
  398.         }
  399.         case StringC(str) => (StringV(str), st1)
  400.         }
  401.         }
Add Comment
Please, Sign In to add comment
Public Pastes
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!