API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Mar 15th, 2014
317
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Scala 15.35 KB | None | 0 0
raw download clone embed print report
  1. object Lab4 extends jsy.util.JsyApplication {
  2.   import jsy.lab4.ast._
  3.   import jsy.lab4.Parser
  4.  
  5.   /*
  6.    * CSCI 3155: Lab 4
  7.    * <Matt Moskowitz>
  8.    *
  9.    * Partner: <David Bittle>
  10.    * Collaborators: <Any Collaborators>
  11.    */
  12.  
  13.   /*
  14.    * Fill in the appropriate portions above by replacing things delimited
  15.    * by '<'... '>'.
  16.    *
  17.    * Replace 'YourIdentiKey' in the object name above with your IdentiKey.
  18.    *
  19.    * Replace the 'throw new UnsupportedOperationException' expression with
  20.    * your code in each function.
  21.    *
  22.    * Do not make other modifications to this template, such as
  23.    * - adding "extends App" or "extends Application" to your Lab object,
  24.    * - adding a "main" method, and
  25.    * - leaving any failing asserts.
  26.    *
  27.    * Your lab will not be graded if it does not compile.
  28.    *
  29.    * This template compiles without error. Before you submit comment out any
  30.    * code that does not compile or causes a failing assert.  Simply put in a
  31.    * 'throws new UnsupportedOperationException' as needed to get something
  32.    * that compiles without error.
  33.    */
  34.  
  35.   /* Collections and Higher-Order Functions */
  36.  
  37.   /* Lists */
  38.  
  39.   //cd Desktop/eclipse/workspace/lab4    
  40.   //sbt "project lab4-grader" run
  41.  
  42.  
  43.   def compressRec[A](l: List[A]): List[A] = l match {
  44.     case Nil | _ :: Nil => l
  45.     case h1 :: (t1 @ (h2 :: _)) => if (h1 == h2) compressRec(t1) else h1:: compressRec(t1)
  46.   }
  47.  
  48.   def compressFold[A](l: List[A]): List[A] = l.foldRight(Nil: List[A]){
  49.     (h, acc) => acc match { //acc begins nil, h starts from value at end of list
  50.       case Nil => h :: acc
  51.       case h1 :: t => h1 match {
  52.         case `h` => acc
  53.         case _ => h :: acc
  54.       }
  55.        
  56.     }
  57.   }
  58.  
  59.   def mapFirst[A](f: A => Option[A])(l: List[A]): List[A] = l match {
  60.     case Nil => l
  61.     case h :: t => f(h) match {
  62.       case Some(x) => x :: t
  63.       case _ => h :: mapFirst(f)(t)
  64.     }
  65.   }
  66.  
  67.   /* Search Trees */
  68.  
  69.   sealed abstract class Tree {
  70.     def insert(n: Int): Tree = this match {
  71.       case Empty => Node(Empty, n, Empty)
  72.       case Node(l, d, r) => if (n < d) Node(l insert n, d, r) else Node(l, d, r insert n)
  73.     }
  74.    
  75.     def foldLeft[A](z: A)(f: (A, Int) => A): A = {
  76.       def loop(acc: A, t: Tree): A = t match {
  77.         case Empty => acc
  78.         //case Node(Empty, d, Empty) => f(acc, d)
  79.         //case Node(Empty, d, r) => loop(f(acc, d), r)
  80.        // case Node(l, d , Empty) => loop(f(acc, d), l)
  81.         case Node(l, d, r) => {
  82.           val v1 = loop(acc, l)
  83.           val v2 = f(v1, d)
  84.           loop(v2, r)
  85.         }
  86.       }
  87.       loop(z, this)
  88.     }
  89.    
  90.     def pretty: String = {
  91.       def p(acc: String, t: Tree, indent: Int): String = t match {
  92.         case Empty => acc
  93.         case Node(l, d, r) =>
  94.           val spacer = " " * indent
  95.           p("%s%d%n".format(spacer, d) + p(acc, l, indent + 2), r, indent + 2)
  96.       }
  97.       p("", this, 0)
  98.     }
  99.   }
  100.   case object Empty extends Tree
  101.   case class Node(l: Tree, d: Int, r: Tree) extends Tree
  102.  
  103.   def treeFromList(l: List[Int]): Tree =
  104.     l.foldLeft(Empty: Tree){ (acc, i) => acc insert i }
  105.  
  106.   def sum(t: Tree): Int = t.foldLeft(0){ (acc, d) => acc + d }
  107.  
  108.   def strictlyOrdered(t: Tree): Boolean = {
  109.     val (b, _) = t.foldLeft((true, None: Option[Int])){
  110.       (acc, h)  => acc match {
  111.         case (b1, None) => (true, Some(h))
  112.         case (b1, a) => (((a.get < h) && b1), Some(h))
  113.       }
  114.     }
  115.     b
  116.   }
  117.   /* Type Inference */
  118.  
  119.   // A helper function to check whether a jsy type has a function type in it.
  120.   // While this is completely given, this function is worth studying to see
  121.   // how library functions are used.
  122.   def hasFunctionTyp(t: Typ): Boolean = t match {
  123.     case TFunction(_, _) => true
  124.     case TObj(fields) if (fields exists { case (_, t) => hasFunctionTyp(t) }) => true
  125.     case _ => false
  126.   }
  127.  
  128.   def typeInfer(env: Map[String,Typ], e: Expr): Typ = {
  129.     // Some shortcuts for convenience
  130.     def typ(e1: Expr) = typeInfer(env, e1)
  131.     def err[T](tgot: Typ, e1: Expr): T = throw StaticTypeError(tgot, e1, e)
  132.  
  133.     e match {
  134.       case Print(e1) => typ(e1); TUndefined
  135.       case N(_) => TNumber
  136.       case B(_) => TBool
  137.       case Undefined => TUndefined
  138.       case S(_) => TString
  139.       case Var(x) => env(x)
  140.       case ConstDecl(x, e1, e2) => typeInfer(env + (x -> typ(e1)), e2)
  141.       case Unary(Neg, e1) => typ(e1) match {
  142.         case TNumber => TNumber
  143.         case tgot => err(tgot, e1)
  144.       }
  145.       case Unary(Not, e1) => typ(e1) match {
  146.         case TBool => TBool
  147.         case tgot => err(tgot,e1)
  148.       }
  149.      //   throw new UnsupportedOperationException
  150.       case Binary(Plus, e1, e2) => (typ(e1),typ(e2)) match{
  151.         case (TString,TString)=> TString
  152.         case (TNumber,TNumber)=>TNumber
  153.         case _ => err(typ(e1),e1)
  154.       }
  155.     //throw new UnsupportedOperationException
  156.       case Binary(Minus|Times|Div, e1, e2) =>(typ(e1),typ(e2)) match{
  157.         case (TNumber,TNumber)=>TNumber
  158.         case (_) => err(typ(e1),e1)
  159.       }
  160.  
  161.       case Binary(Eq|Ne, e1, e2) =>(typ(e1),typ(e2)) match{
  162.         case(e1type,_) if hasFunctionTyp(e1type)=> err(e1type, e1)
  163.         case(_,e2type) if hasFunctionTyp(e2type)=> err(e2type, e2)
  164.         case(e1type,e2type) if(e1type==e2type)=>TBool
  165.         case _ => err(typ(e1),e1)
  166.       //case(TBool,TBool)=> TBool
  167.       //    case(TBool,_)=> err(typ(e2),e2)
  168.      //
  169.       }
  170.      
  171.       case Binary(Lt|Le|Gt|Ge, e1, e2) =>(typ(e1),typ(e2)) match{
  172.         case(TNumber,TNumber) => TBool
  173.         case(TBool,TBool)=> TBool
  174.       case(TString,TString)=> TBool
  175.       case _=>err(typ(e1),e1)
  176.       }
  177.      
  178.       case Binary(And|Or, e1, e2) =>(typ(e1),typ(e2)) match{
  179.       case(TBool,TBool)=> TBool
  180.       //case(TBool,_)=> err(typ(e2),e2)
  181.       case _=>err(typ(e1),e1)
  182.       }
  183.      
  184.       case Binary(Seq, e1, e2) =>
  185.         typ(e2);
  186.         typ(e1)
  187.      
  188.        
  189.        
  190.         throw new UnsupportedOperationException
  191.       case If(e1, e2, e3) =>(typ(e1), typ(e2), typ(e3)) match {
  192. //e1 must be a bool.  e2 can be any type, e3 can be any type
  193. case (TBool, e2type, e3type) =>  {
  194.  
  195. if (e2type == e3type) e2type
  196.  
  197. else err(e3type, e3)
  198.  
  199. }
  200. case(e1NotBool, _, _) => err(e1NotBool, e1)
  201.  
  202.  }    
  203.  
  204.       case Function(p, params, tann, e1) => {
  205.         // Bind to env1 an environment that extends env with an appropriate binding if
  206.         // the function is potentially recursive.
  207.         val env1 = (p, tann) match {
  208.           case (Some(f), Some(tret)) =>
  209.             val tprime = TFunction(params, tret)
  210.             env + (f -> tprime)
  211.           case (None, _) => env
  212.           case _ => err(TUndefined, e1)
  213.         }
  214.         // Bind to env2 an environment that extends env1 with bindings for params.
  215.        
  216.         //base case will be the env1 that was defined above (code given to us)
  217.         //subsequently we will be calling fold left on every entry in params
  218.         //every time we will extend the environemnt with + along with names associated with values added
  219.         //the result will be a new environement, e2 with all the parameters
  220.        
  221.         val env2 = params.foldLeft(env1) {
  222.           case (acc, (pName, pValue)) => acc + (pName -> pValue)
  223.         }          
  224.          // throw new UnsupportedOperationException
  225.        
  226.         // Match on whether the return type is specified.
  227.         tann match {
  228.           case None =>
  229.             //val tBody will find the type of e1 given the environment e2 wi
  230.           val tBody = typeInfer(env2, e1)
  231.             //tfunction will return a type function with the params originally passed in and the type of the body.
  232.           TFunction(params, tBody)
  233.           case Some(tret) => {
  234.             val tBody = typeInfer(env2, e1)
  235.             val tBodyPrime = TFunction(params, tBody)
  236.             //in the case of recursive functions the type returned must be of the same type as
  237.             //the type that was passed in.
  238.             if (tBodyPrime != TFunction(params, tret))
  239.               err(tBody, e1)
  240.              
  241.               else TFunction(params, tret)
  242.           }
  243.         }
  244.       }
  245.       case Call(e1, args) => typ(e1) match {
  246.         case TFunction(params, tret) if (params.length == args.length) => {
  247.           (params, args).zipped.foreach {
  248.             case(parArgs@(st,t),e)=> if(t!=typ(e)) err(typ(e),e);
  249.             tret
  250.             //throw new UnsupportedOperationException
  251.           }
  252.           tret
  253.         }
  254.         case tgot => err(tgot, e1)
  255.       }
  256.       case Obj(fields) =>TObj(fields.mapValues((exp: Expr) => typ(exp)))
  257.        
  258.       case GetField(e1, f) => {
  259.         typ(e1) match {
  260.           case TObj(field) => field.get(f) match {
  261.             case Some(f) => f
  262.             case None => err(typ(e1), e1)
  263.           }
  264.           case _ => err(typ(e1), e1)
  265.         }
  266.       }
  267.     }
  268. }
  269.  
  270.  
  271.   /* Small-Step Interpreter */
  272.  
  273.   def inequalityVal(bop: Bop, v1: Expr, v2: Expr): Boolean = {
  274.     require(bop == Lt || bop == Le || bop == Gt || bop == Ge)
  275.     ((v1, v2): @unchecked) match {
  276.       case (S(s1), S(s2)) =>
  277.         (bop: @unchecked) match {
  278.           case Lt => s1 < s2
  279.           case Le => s1 <= s2
  280.           case Gt => s1 > s2
  281.           case Ge => s1 >= s2
  282.         }
  283.       case (N(n1), N(n2)) =>
  284.         (bop: @unchecked) match {
  285.           case Lt => n1 < n2
  286.           case Le => n1 <= n2
  287.           case Gt => n1 > n2
  288.           case Ge => n1 >= n2
  289.         }
  290.     }
  291.   }
  292.  
  293.   def substitute(e: Expr, v: Expr, x: String): Expr = {
  294.     require(isValue(v))
  295.    
  296.     def subst(e: Expr): Expr = substitute(e, v, x)
  297.    
  298.     e match {
  299.       case N(_) | B(_) | Undefined | S(_) => e
  300.       case Print(e1) => Print(subst(e1))
  301.       case Unary(uop, e1) => Unary(uop, subst(e1))
  302.       case Binary(bop, e1, e2) => Binary(bop, subst(e1), subst(e2))
  303.       case If(e1, e2, e3) => If(subst(e1), subst(e2), subst(e3))
  304.       case Var(y) => if (x == y) v else e
  305.       case ConstDecl(y, e1, e2) => ConstDecl(y, subst(e1), if (x == y) e2 else subst(e2))
  306.      
  307.      
  308.       case Function(p, params, tann, e1) =>
  309.         p match{
  310.           case(None)=>
  311.             Function(p, params, tann, if (params.forall{case(n,_) => (x != n)}) subst(e1) else e1)
  312.           case Some(a) => Function(p, params, tann, if (params.forall{case(n,_) => (x != n)}&& a!=x) subst(e1) else e1)            
  313.         }
  314.        case Obj(field) => Obj(field.mapValues((exp: Expr) => subst(exp)))
  315.      
  316.       //case f1 @ Function(p, params, tann, e1) => {
  317.       //  if (params.exists((t1: (String, Typ)) => t1._1 == x) || Some(x) == p) {
  318.      //     f1
  319.       //  } else {
  320.        //   Function(p, params, tann, subst(e1))
  321.       //  }
  322.       //}
  323.       case Call(e1, args) => Call(subst(e1), args map subst)
  324.      // case Call(e1, args) =>
  325.      //   throw new UnsupportedOperationException
  326.       //case Obj(fields) =>
  327.      //   throw new UnsupportedOperationException
  328.       case GetField(e1, f) => GetField(subst(e1), f)
  329.     }
  330.   }
  331.  
  332.   def step(e: Expr): Expr = {
  333.     require(!isValue(e))
  334.    
  335.     def stepIfNotValue(e: Expr): Option[Expr] = if (isValue(e)) None else Some(step(e))
  336.    
  337.     e match {
  338.       /* Base Cases: Do Rules */
  339.       case Print(v1) if isValue(v1) => println(pretty(v1)); Undefined
  340.       case Unary(Neg, N(n1)) => N(- n1)
  341.       case Unary(Not, B(b1)) => B(! b1)
  342.       case Binary(Seq, v1, e2) if isValue(v1) => e2
  343.       case Binary(Plus, S(s1), S(s2)) => S(s1 + s2)
  344.       case Binary(Plus, N(n1), N(n2)) => N(n1 + n2)
  345.      
  346.       case Binary(Minus, N(n1), N(n2)) => N(n1 - n2)
  347.       case Binary(Times, N(n1), N(n2)) => N(n1 * n2)
  348.       case Binary(Div, N(n1), N(n2)) => N(n1 / n2)
  349.      
  350.       case Binary(bop @ (Lt|Le|Gt|Ge), v1, v2) if isValue(v1) && isValue(v2) => B(inequalityVal(bop, v1, v2))
  351.       case Binary(Eq, v1, v2) if isValue(v1) && isValue(v2) => B(v1 == v2)
  352.       case Binary(Ne, v1, v2) if isValue(v1) && isValue(v2) => B(v1 != v2)
  353.       case Binary(And, B(b1), e2) => if (b1) e2 else B(false)
  354.       case Binary(Or, B(b1), e2) => if (b1) B(true) else e2
  355.       case ConstDecl(x, v1, e2) if isValue(v1) => substitute(e2, v1, x)
  356.      
  357.       case If(B(b1), e2, e3) => b1 match{
  358.         case (true) => e2
  359.         case (false) => e3
  360.       }
  361.      
  362.      case GetField(Obj(fields), f) => fields.get(f) match {
  363.            case Some(e1) => e1
  364.         case None => throw new StuckError(e)
  365.       }
  366.       case GetField(e1, f) => GetField(step(e1), f)
  367.      
  368.      
  369.          
  370.       case Call(v1, args) if isValue(v1) && (args forall isValue) =>
  371.         v1 match {
  372.           case Function(p, params, _, e1) => {
  373.             //e1p in this case
  374.             val e1p = (params, args).zipped.foldRight(e1){
  375.               //
  376.               (myParams,acc)=> myParams match{
  377.                 case((name,_),value) => substitute(acc,value,name)
  378.               }
  379.              
  380.             }
  381.             p match {
  382.               case None => e1p
  383.               case Some(x1) => substitute(e1p,v1,x1)
  384.             }
  385.           }
  386.           case _ => throw new StuckError(e)
  387.         }
  388.       /*** Fill-in more cases here. ***/
  389.       /* Inductive Cases: Search Rules */
  390.       case Call(v1,args) if isValue(v1)=> Call(v1, mapFirst(stepIfNotValue)(args))  
  391.       case Call(e1,e2)=> Call(step(e1),e2)
  392.        
  393.       case Print(e1) => Print(step(e1))
  394.       case Unary(uop, e1) => Unary(uop, step(e1))
  395.       case Binary(bop, v1, e2) if isValue(v1) => Binary(bop, v1, step(e2))
  396.       case Binary(bop, e1, e2) => Binary(bop, step(e1), e2)
  397.       case If(e1, e2, e3) => If(step(e1), e2, e3)
  398.       case ConstDecl(x, e1, e2) => ConstDecl(x, step(e1), e2)
  399.       /*** Fill-in more cases here. ***/
  400.      
  401.       /* Everything else is a stuck error. Should not happen if e is well-typed. */
  402.       case _ => throw StuckError(e)
  403.     }
  404.   }
  405.  
  406.  
  407.   /* External Interfaces */
  408.  
  409.   this.debug = true // comment this out or set to false if you don't want print debugging information
  410.  
  411.   def inferType(e: Expr): Typ = {
  412.     if (debug) {
  413.       println("------------------------------------------------------------")
  414.       println("Type checking: %s ...".format(e))
  415.     }
  416.     val t = typeInfer(Map.empty, e)
  417.     if (debug) {
  418.       println("Type: " + pretty(t))
  419.     }
  420.     t
  421.   }
  422.  
  423.   // Interface to run your small-step interpreter and print out the steps of evaluation if debugging.
  424.   def iterateStep(e: Expr): Expr = {
  425.     require(closed(e))
  426.     def loop(e: Expr, n: Int): Expr = {
  427.       if (debug) { println("Step %s: %s".format(n, e)) }
  428.       if (isValue(e)) e else loop(step(e), n + 1)
  429.     }
  430.     if (debug) {
  431.       println("------------------------------------------------------------")
  432.       println("Evaluating with step ...")
  433.     }
  434.     val v = loop(e, 0)
  435.     if (debug) {
  436.       println("Value: " + v)
  437.     }
  438.     v
  439.   }
  440.  
  441.   // Convenience to pass in a jsy expression as a string.
  442.   def iterateStep(s: String): Expr = iterateStep(Parser.parse(s))
  443.  
  444.   // Interface for main
  445.   def processFile(file: java.io.File) {
  446.     if (debug) {
  447.       println("============================================================")
  448.       println("File: " + file.getName)
  449.       println("Parsing ...")
  450.     }
  451.    
  452.     val expr =
  453.       handle(None: Option[Expr]) {Some{
  454.         Parser.parseFile(file)
  455.       }} getOrElse {
  456.         return
  457.       }
  458.    
  459.     handle() {
  460.       val t = inferType(expr)
  461.     }
  462.    
  463.     handle() {
  464.       val v1 = iterateStep(expr)
  465.       println(pretty(v1))
  466.     }
  467.   }
  468.  
  469. }
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!