diff options
Diffstat (limited to 'lab3/src')
-rw-r--r-- | lab3/src/main/scala/jsy/lab3/Lab3.scala | 360 | ||||
-rw-r--r-- | lab3/src/main/scala/jsy/lab3/Lab3.worksheet.js | 24 | ||||
-rw-r--r-- | lab3/src/main/scala/jsy/lab3/Lab3.worksheet.sc | 51 | ||||
-rw-r--r-- | lab3/src/main/scala/jsy/lab3/Parser.scala | 284 | ||||
-rw-r--r-- | lab3/src/main/scala/jsy/lab3/ast.scala | 106 | ||||
-rw-r--r-- | lab3/src/main/scala/jsy/util/JsyApplication.scala | 191 | ||||
-rw-r--r-- | lab3/src/test/resources/lab3/test3004_call.ans | 8 | ||||
-rw-r--r-- | lab3/src/test/resources/lab3/test3004_call.jsy | 2 | ||||
-rw-r--r-- | lab3/src/test/resources/lab3/test3006_curry.ans | 8 | ||||
-rw-r--r-- | lab3/src/test/resources/lab3/test3006_curry.jsy | 2 | ||||
-rw-r--r-- | lab3/src/test/resources/lab3/test3008_call.ans | 48 | ||||
-rw-r--r-- | lab3/src/test/resources/lab3/test3008_call.jsy | 2 | ||||
-rw-r--r-- | lab3/src/test/scala/jsy/lab3/Lab3Spec.scala | 150 | ||||
-rw-r--r-- | lab3/src/test/scala/jsy/tester/JavascriptyTester.scala | 23 |
14 files changed, 1259 insertions, 0 deletions
diff --git a/lab3/src/main/scala/jsy/lab3/Lab3.scala b/lab3/src/main/scala/jsy/lab3/Lab3.scala new file mode 100644 index 0000000..4660c6d --- /dev/null +++ b/lab3/src/main/scala/jsy/lab3/Lab3.scala @@ -0,0 +1,360 @@ +package jsy.lab3 +import scala.util.Try + +object Lab3 extends jsy.util.JsyApplication { + import ast._ + + /* + * CSCI 3155: Lab 3 + * Jack Sangdahl + */ + + /** *************************************************** + */ + /** ************** Regular Section ******************** + */ + /** *************************************************** + */ + + /* Static Scoping */ + + def substitute(v: Expr, x: String, e: Expr): Expr = { + require(isValue(v), s"substitute: v ${v} to substitute is not a value") + def subst(e: Expr): Expr = substitute(v, x, e) + e match { + case Print(e1) => Print(subst(e1)) + case Unary(uop, e1) => Unary(uop, subst(e1)) + case Binary(bop, e1, e2) => Binary(bop, subst(e1), subst(e2)) + case If(e1, e2, e3) => If(subst(e1), subst(e2), subst(e3)) + case Call(e1, e2) => Call(subst(e1), subst(e2)) + case Var(y) => if (x == y) v else e + case Fun(xopt, y, e1) if (x != y) => Fun(xopt, y, subst(e1)) + case ConstDecl(y, e1, e2) if (x != y) => + ConstDecl(y, subst(e1), subst(e2)) + case _ => e + } + } + + /* Iteration */ + + def iterateBasic[A](acc0: A)(stepi: (A, Int) => Option[A]): A = { + def loop(acc: A, i: Int): A = stepi(acc, i) match { + case Some(acc1) => loop(acc1, i + 1) + case None => acc + } + loop(acc0, 0) + } + + def iterate[Err, A]( + acc0: A + )(stepi: (A, Int) => Option[Either[Err, A]]): Either[Err, A] = { + def loop(acc: A, i: Int): Either[Err, A] = stepi(acc, i) match { + case Some(Right(acc1)) => loop(acc1, i + 1) + case Some(Left(err)) => Left(err) + case None => Right(acc) + } + loop(acc0, 0) + } + + /* Small-Step Interpreter with Static Scoping */ + + def toBoolean(v: Expr): Boolean = { + require(isValue(v)) + (v: @unchecked) match { + case B(b) => b + case S(s) => s != "" + case N(n) => n != 0 + case Fun(_, _, _) => true + } + } + + def stepBasic(e: Expr): Expr = (e: @unchecked) match { + + case Print(v1) if isValue(v1) => println(pretty(v1)); Undefined + case Print(e1) => Print(stepBasic(e1)) + + case Binary(Seq, e1, e2) if !isValue(e1) => Binary(Seq, stepBasic(e1), e2) + case Binary(Seq, e1, e2) if isValue(e1) => stepBasic(e2) + + case If(e1, e2, e3) if !isValue(e1) => If(stepBasic(e1), e2, e3) + case If(e1, e2, e3) => { + if (toBoolean(e1)) + if (isValue(e2)) e2 else stepBasic(e2) + else + if (isValue(e3)) e3 else stepBasic(e3) + } + + case ConstDecl(y, e1, e2) if !isValue(e1) => ConstDecl(y, stepBasic(e1), e2) + case ConstDecl(y, e1, e2) => substitute(e1, y, e2) + + case Call(e1, e2) if !isValue(e2) => Call(e1, stepBasic(e2)) + case Call(Fun(xopt, y, e1), e2) => { + val noVarsBody = substitute(e2, y, e1) + xopt match { + case Some(x) => substitute(Fun(xopt, y, e1), x, noVarsBody) + case None => noVarsBody + } + } + + case Binary(Plus, N(x), N(y)) => N(x + y) + case Binary(Plus, e1, N(e2)) => Binary(Plus, stepBasic(e1), N(e2)) + case Binary(Plus, N(e1), e2) => Binary(Plus, N(e1), stepBasic(e2)) + + case Binary(Minus, N(x), N(y)) => N(x - y) + case Binary(Minus, e1, N(e2)) => Binary(Minus, stepBasic(e1), N(e2)) + case Binary(Minus, N(e1), e2) => Binary(Minus, N(e1), stepBasic(e2)) + + case Binary(Eq, x, y) if isValue(x) && isValue(y) => B(x == y) + case Binary(Eq, e1, e2) if !isValue(e1) => Binary(Eq, stepBasic(e1), e2) + case Binary(Eq, e1, e2) if !isValue(e2) => Binary(Eq, e1, stepBasic(e2)) + + /* Cases that should never match. Your cases above should ensure this. */ + case Var(_) => + throw new AssertionError( + s"Gremlins: internal error, not closed expression $e." + ) + case v if isValue(v) => + throw new AssertionError( + s"Gremlins: internal error, step should not be called on values $v." + ) + } + + def stepCheck(e: Expr): Either[DynamicTypeError, Expr] = e match { + + case Print(v1) if isValue(v1) => println(pretty(v1)); Right(Undefined) + case Print(e1) => stepCheck(e1).map(Print) + + case Binary(Seq, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Seq, e1, e2)) + case Binary(Seq, e1, e2) if isValue(e1) => stepCheck(e2) + + case If(e1, e2, e3) if !isValue(e1) => + stepCheck(e1).map(e1 => If(e1, e2, e3)) + case If(e1, e2, e3) => { + if (toBoolean(e1)) + if (isValue(e2)) Right(e2) else stepCheck(e2) + else + if (isValue(e3)) Right(e3) else stepCheck(e3) + } + + case ConstDecl(y, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => ConstDecl(y, e1, e2)) + case ConstDecl(y, e1, e2) => Right(substitute(e1, y, e2)) + + case Call(e1, e2) if !isValue(e1) => stepCheck(e1).map(e1 => Call(e1, e2)) + case Call(e1, e2) if !isValue(e2) => stepCheck(e2).map(e2 => Call(e1, e2)) + case Call(Fun(xopt, y, e1), e2) => { + val noVarsBody = substitute(e2, y, e1) + xopt match { + case Some(x) => Right(substitute(Fun(xopt, y, e1), x, noVarsBody)) + case None => Right(noVarsBody) + } + } + case Call(e1, e2) => Left(DynamicTypeError(Call(e1, e2))) + + case Binary(Plus, N(x), N(y)) => Right(N(x + y)) + case Binary(Plus, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Plus, e1, e2)) + case Binary(Plus, e1, e2) if !isValue(e2) => + stepCheck(e2).map(e2 => Binary(Plus, e1, e2)) + case Binary(Plus, e1, e2) => Left(DynamicTypeError(Binary(Plus, e1, e2))) + + case Binary(Minus, N(x), N(y)) => Right(N(x - y)) + case Binary(Minus, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Minus, e1, e2)) + case Binary(Minus, e1, e2) if !isValue(e2) => + stepCheck(e2).map(e2 => Binary(Minus, e1, e2)) + case Binary(Minus, e1, e2) => Left(DynamicTypeError(Binary(Minus, e1, e2))) + + case Binary(Times, N(x), N(y)) => Right(N(x * y)) + case Binary(Times, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Times, e1, e2)) + case Binary(Times, e1, e2) if !isValue(e2) => + stepCheck(e2).map(e2 => Binary(Times, e1, e2)) + case Binary(Times, e1, e2) => Left(DynamicTypeError(Binary(Times, e1, e2))) + + case Binary(Div, N(x), N(y)) => Right(N(x / y)) + case Binary(Div, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Div, e1, e2)) + case Binary(Div, e1, e2) if !isValue(e2) => + stepCheck(e2).map(e1 => Binary(Div, e1, e2)) + case Binary(Div, e1, e2) => Left(DynamicTypeError(Binary(Div, e1, e2))) + + case Binary(Eq, x, y) if isValue(x) && isValue(y) => Right(B(x == y)) + case Binary(Eq, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Eq, e1, e2)) + case Binary(Eq, e1, e2) if !isValue(e2) => + stepCheck(e2).map(e2 => Binary(Eq, e1, e2)) + case Binary(Eq, e1, e2) => Left(DynamicTypeError(Binary(Eq, e1, e2))) + + case Binary(Ne, x, y) if isValue(x) && isValue(y) => Right(B(x != y)) + case Binary(Ne, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Ne, e1, e2)) + case Binary(Ne, e1, e2) if !isValue(e2) => + stepCheck(e2).map(e2 => Binary(Ne, e1, e2)) + case Binary(Ne, e1, e2) => Left(DynamicTypeError(Binary(Ne, e1, e2))) + + case Binary(Lt, N(x), N(y)) => Right(B(x < y)) + case Binary(Lt, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Lt, e1, e2)) + case Binary(Lt, e1, e2) if !isValue(e2) => + stepCheck(e2).map(e2 => Binary(Lt, e1, e2)) + case Binary(Lt, e1, e2) => Left(DynamicTypeError(Binary(Lt, e1, e2))) + + case Binary(Le, N(x), N(y)) => Right(B(x <= y)) + case Binary(Le, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Le, e1, e2)) + case Binary(Le, e1, e2) if !isValue(e2) => + stepCheck(e2).map(e2 => Binary(Le, e1, e2)) + case Binary(Le, e1, e2) => Left(DynamicTypeError(Binary(Le, e1, e2))) + + case Binary(Gt, N(x), N(y)) => Right(B(x > y)) + case Binary(Gt, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Gt, e1, e2)) + case Binary(Gt, e1, e2) if !isValue(e2) => + stepCheck(e2).map(e2 => Binary(Gt, e1, e2)) + case Binary(Gt, e1, e2) => Left(DynamicTypeError(Binary(Gt, e1, e2))) + + case Binary(Ge, N(x), N(y)) => Right(B(x >= y)) + case Binary(Ge, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Ge, e1, e2)) + case Binary(Ge, e1, e2) if !isValue(e2) => + stepCheck(e2).map(e2 => Binary(Ge, e1, e2)) + case Binary(Ge, e1, e2) => Left(DynamicTypeError(Binary(Ge, e1, e2))) + + case Unary(Neg, N(x)) => Right(N(-x)) + case Unary(Neg, e1) if !isValue(e1) => + stepCheck(e1).map(e1 => Unary(Neg, e1)) + case Unary(Neg, e1) => Left(DynamicTypeError(Unary(Neg, e1))) + + case Binary(And, e1, e2) => { + (e1, e2) match { + case (e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(And, e1, e2)) + case (e1, e2) if !isValue(e2) => + stepCheck(e2).map(e2 => Binary(And, e1, e2)) + case (e1, e2) => + if (!toBoolean(e1)) Right(e1) else Right(e2) + } + } + + /* Cases that should never match. Your cases above should ensure this. */ + case Var(_) => + throw new AssertionError( + s"Gremlins: internal error, not closed expression $e." + ) + case v if isValue(v) => + throw new AssertionError( + s"Gremlins: internal error, step should not be called on values $v." + ) + } + + /* IMPORTANT: Choose which version of step to use for testing by choosing one of the lines. You will pick one version to submit. */ + // def step(e: Expr): Either[DynamicTypeError, Expr] = Right(stepBasic(e)) + def step(e: Expr): Either[DynamicTypeError, Expr] = stepCheck(e) + + /** *************************************************** + */ + /** ********** End Regular Section ******************** + */ + /** *************************************************** + */ + + /** *************************************************** + */ + /** ********** Accelerated Section ******************** + */ + /** *************************************************** + */ + + def toNumber(v: Expr): Double = { + require(isValue(v)) + ??? + } + + def toStr(v: Expr): String = { + require(isValue(v)) + ??? + } + + def stepCoerce(e: Expr): Either[DynamicTypeError, Expr] = ??? + + /* Choose to use this version of step for testing uncommenting this line and commenting the definition of step above. */ + // def step(e: Expr): Either[DynamicTypeError, Expr] = stepCoerce(e) + + /** *************************************************** + */ + /** ********** End Accelerated Section **************** + */ + /** *************************************************** + */ + + /* External Interfaces */ + + // this.debug = true // comment this out or set to false if you don't want print debugging information + this.maxSteps = Some( + 1000 + ) // comment this out or set to None to not bound the number of steps. + this.keepGoing = + true // comment this out if you want to stop at first exception when processing a file + + /** Interface to take a small-step from a string. This is convenient for unit + * testing. + */ + def oneStep(s: String): Either[DynamicTypeError, Expr] = step(Parser.parse(s)) + + /** Interface to run your small-step interpreter and print out the steps of + * evaluation if debugging. + */ + def iterateStep(e: Expr): Either[DynamicTypeError, Expr] = { + require(closed(e), s"iterateStep: ${e} not closed") + if (debug) { + println("------------------------------------------------------------") + println("Evaluating with step ...") + } + val v = iterate(e) { (e: Expr, n: Int) => + if (debug) { println(s"Step $n: $e") } + if (isValue(e)) None else Some(step(e)) + } + if (debug) { println("Value: " + v) } + v + } + + /** Interface to run your small-step interpreter from a string. This is + * convenient for unit testing. + */ + def iterateStep(s: String): Either[DynamicTypeError, Expr] = iterateStep( + Parser.parse(s) + ) + + /** Interface for main for JsyApplication */ + def processFile(file: java.io.File): Unit = { + if (debug) { + println("============================================================") + println("File: " + file.getName) + println("Parsing ...") + } + + val e1 = + handle(None: Option[Expr]) { + Some { + Parser.parseFile(file) + } + } getOrElse { + return + } + + handle(()) { + println("# Stepping ...") + def loop(e: Expr, n: Int): Either[DynamicTypeError, Expr] = { + println("## %4d: %s".format(n, e)) + if (isValue(e)) Right(e) else step(e) flatMap { e1 => loop(e1, n + 1) } + } + loop(e1, 0) match { + case Right(v1) => println(pretty(v1)) + case Left(err) => println(err) + } + } + } + +} diff --git a/lab3/src/main/scala/jsy/lab3/Lab3.worksheet.js b/lab3/src/main/scala/jsy/lab3/Lab3.worksheet.js new file mode 100644 index 0000000..8d4d9ce --- /dev/null +++ b/lab3/src/main/scala/jsy/lab3/Lab3.worksheet.js @@ -0,0 +1,24 @@ +/* + * CSCI 3155: Lab 3 JavaScript Worksheet + * + * This worksheet is a place to experiment with JavaScript expressions. + */ + +// The new language feature in Lab 3 is first-class functions. + +const id = function (x) { + return x; +}; + +const plus = (x) => (y) => x + y; + +const j = plus(3)(4); + +id("Hello, ") + j; + +const factorial = function f(n) { + return n === 0 ? 1 : n * f(n - 1); +}; + +const factorial3 = factorial(3); +factorial3; diff --git a/lab3/src/main/scala/jsy/lab3/Lab3.worksheet.sc b/lab3/src/main/scala/jsy/lab3/Lab3.worksheet.sc new file mode 100644 index 0000000..e5744ec --- /dev/null +++ b/lab3/src/main/scala/jsy/lab3/Lab3.worksheet.sc @@ -0,0 +1,51 @@ +/* + * CSCI 3155: Lab 3 Worksheet + * + * This worksheet demonstrates how you could experiment + * interactively with your implementations in Lab3.scala. + */ + +// Imports the parse function from jsy.lab3.Parser +import jsy.lab3.Parser.{parse, parseFile} + +// Imports the ast nodes +import jsy.lab3.ast._ + +// Imports all of the functions form jsy.student.Lab3 (your implementations in Lab3.scala) +import jsy.lab3.Lab3._ + +// The new language feature in Lab 3 is first-class functions. + +// In JavaScript, functions can be written in a number of different +// ways. Here, we write the same identity function with different +// concrete syntax that all get parsed to the same abstract. +parse("x => x") +parse("x => { return x }") +parse("x => { return x; }") +parse("(x) => x") +parse("function (x) { return x }") + +// Functions can optionally have a name, which we use for declaring +// potentially recursive functions. +parse("function id(x) { return x }") + +// To simplify your implementation, we only allow single parameter +// functions. But we can get the effect of multi-parameter functions +// through currying (i.e., having a function that returns another +// function). +parse("const plus = x => y => x + y") + +// Here are some more function expressions. +parse("x => { const z = 3; return x + z }") +parse("function (x) { const z = 3; return x + z }") + +// Run your small-step interpreter +//iterateStep("1 + 2") +//iterateStep("x => y => x + y") +//iterateStep("const plus = x => y => x + y; plus(3)(4)") + +// Parse the JavaScripty expression in your worksheet +val worksheetJsy = parseFile("src/main/scala/jsy/lab3/Lab3.worksheet.js") + +// Eval the JavaScripty expression in your worksheet +//iterateStep(worksheetJsy)
\ No newline at end of file diff --git a/lab3/src/main/scala/jsy/lab3/Parser.scala b/lab3/src/main/scala/jsy/lab3/Parser.scala new file mode 100644 index 0000000..e044311 --- /dev/null +++ b/lab3/src/main/scala/jsy/lab3/Parser.scala @@ -0,0 +1,284 @@ +/** + * + */ +package jsy.lab3 + +import jsy.lab3.ast._ +import scala.util.parsing.combinator._ +import scala.util.parsing.input.{StreamReader} +import java.io.{InputStreamReader,FileInputStream} +import java.io.InputStream +import java.io.File +import scala.util.parsing.input.Position +import scala.util.parsing.input.NoPosition + +trait JSTokens extends token.StdTokens { + case class FloatLiteral(chars: String) extends Token { + override def toString = chars + } +} + +class Lexer extends lexical.StdLexical with JSTokens { + override def token: this.Parser[Token] = + decimal ~ opt(exponent) ^^ { + case dec ~ exp => FloatLiteral(List(Some(dec), exp).flatten.mkString) + } | + super.token + + def decimal: this.Parser[String] = + rep1(digit) ~ opt('.' ~ rep(digit)) ^^ { + case ws ~ fs => + List(Some(ws), fs map { mkList }).flatten.flatten.mkString + } + + def exponent: this.Parser[String] = + (accept('e') | accept('E')) ~ opt(accept('+') | accept('-')) ~ rep1(digit) ^^ { + case exp ~ sign ~ digits => + List(Some(List(exp)), sign map { List(_) }, Some(digits)).flatten.flatten.mkString + } +} + +trait TokenParser extends syntactical.StdTokenParsers { + type Tokens = JSTokens + val lexical = new Lexer + + import lexical.FloatLiteral + + def floatLit: this.Parser[String] = + elem("float", _.isInstanceOf[FloatLiteral]) ^^ (_.chars) +} + +object Parser extends TokenParser { + /* Lexer Set Up */ + lexical.reserved ++= List("jsy", "undefined", "true", "false", "print", "console", "log", "const", "function", "return", "number", "bool", "string", "Undefined", "null", "Null", "interface", "var", "name", "ref", "RegExp") + lexical.delimiters ++= List("-", "!", ";", ",", "+", "*", "/", "=", "===", "!==", "<", "<=", ">", ">=", "&&", "||", "(", ")", ".", "{", "}", "?", ":", "=>") + + /* Helpers */ + def seqExpr(e1: Expr, e2: Expr): Expr = Binary(Seq, e1, e2) + + /* EBNF + * + * prog ::= {stmt} + * stmt ::= block | decl | ; | expr + * block ::= '{' prog '}' + * decl ::= const x = expr + * expr ::= seq + * seq ::= cond{,cond} + * noseq ::= arrow + * arrow ::= x => noseq | cond + * cond ::= binary [? cond : cond] + * binary ::= unary{bop(_)unary} + * unary ::= uop unary | call + * call ::= term{(expr)} + * term ::= x | n | b | undefined | jsy.print(expr) | (expr) + */ + + sealed abstract class PStmt + case class ExprPStmt(e: Expr) extends PStmt + case class DeclPStmt(d: Expr => Expr) extends PStmt + case object EmpPStmt extends PStmt + + def prog: this.Parser[Expr] = + stmts ^^ (s => s(None)) + + def stmts: this.Parser[Option[Expr] => Expr] = + rep(stmt) ^^ { (stmts: List[PStmt]) => (body: Option[Expr]) => + (stmts foldRight body){ + case (EmpPStmt, eopt) => eopt + case (ExprPStmt(e), None) => Some(e) + case (ExprPStmt(e1), Some(e2)) => Some(seqExpr(e1, e2)) + case (DeclPStmt(d), None) => Some(d(Undefined)) + case (DeclPStmt(d), Some(e)) => Some(d(e)) + } match { + case None => Undefined + case Some(e) => e + } + } + + def stmt: this.Parser[PStmt] = + block ^^ ExprPStmt | + decl ^^ DeclPStmt | + expr ^^ ExprPStmt | + empty_stmt + + def empty_stmt: this.Parser[PStmt] = + ";" ^^ (_ => EmpPStmt) + + def block: this.Parser[Expr] = + "{" ~> prog <~ "}" + + def decl: this.Parser[Expr => Expr] = + ("const" ~> ident) ~ withpos("=" ~> expr) ^^ { + case x ~ ((pos,e1)) => ((e2: Expr) => ConstDecl(x, e1, e2) setPos pos) + } + + def expr: this.Parser[Expr] = + seq + + def seq: this.Parser[Expr] = + noseq ~ withposrep("," ~> noseq) ^^ { + case e0 ~ es => + (es foldRight (None: Option[(Position,Expr)])){ + case ((posi,ei), None) => Some(posi,ei) + case ((posi,ei), Some((pos,e))) => Some(posi, seqExpr(ei,e) setPos pos) + } match { + case None => e0 + case Some((pos,e)) => seqExpr(e0, e) setPos pos + } + } + + def noseq: this.Parser[Expr] = + arrow + + def arrow: this.Parser[Expr] = + (opt("(") ~ ident ~ opt(")")) ~ (withpos("=>" ~> (noseq | funblock))) ^^ { + case _ ~ x ~ _ ~ ((pos,body)) => Fun(None, x, body) setPos pos + } | + cond + + def funblock: this.Parser[Expr] = + ("{" ~> stmts ~ ret <~ rep(empty_stmt) <~ "}") ^^ { + case stmts ~ ret => stmts(Some(ret)) + } + + def ret: this.Parser[Expr] = + "return" ~> expr + + def cond: this.Parser[Expr] = + binary(0) ~ opt(withpos(("?" ~> noseq) ~ (":" ~> noseq))) ^^ { + case e1 ~ None => e1 + case e1 ~ Some((pos, e2 ~ e3)) => If(e1, e2, e3) setPos pos + } + + val binaryOperators: Vector[List[(String, (Expr, Expr) => Expr)]] = { + def createBinaryFunction(op: Bop): (Expr, Expr) => Expr = + { Binary(op, _, _) } + Vector() ++ List( + List("||" -> createBinaryFunction(Or)), + List("&&" -> createBinaryFunction(And)), + List("===" -> createBinaryFunction(Eq), + "!==" -> createBinaryFunction(Ne)), + List("<" -> createBinaryFunction(Lt), + "<=" -> createBinaryFunction(Le), + ">" -> createBinaryFunction(Gt), + ">=" -> createBinaryFunction(Ge)), + List("+" -> createBinaryFunction(Plus), + "-" -> createBinaryFunction(Minus)), + List("*" -> createBinaryFunction(Times), + "/" -> createBinaryFunction(Div)) + ) + } + + def binary(level: Int): this.Parser[Expr] = + if (level >= binaryOperators.length) + unary + else + binary(level + 1) * bop(level) + + def bop(level: Int): this.Parser[(Expr, Expr) => Expr] = { + def doBop(opf: (String, (Expr, Expr) => Expr)): this.Parser[(Expr, Expr) => Expr] = { + val (op, f) = opf + withpos(op) ^^ { case (pos, _) => ((e1, e2) => f(e1, e2) setPos pos) } + } + val bopf0 :: bopfrest = binaryOperators(level) + (bopfrest.foldLeft(doBop(bopf0)))((acc, bopf) => acc | doBop(bopf)) + } + + def unary: this.Parser[Expr] = + positioned(uop ~ unary ^^ { case op ~ e => op(e) }) | + call + + def uop: this.Parser[Expr => Expr] = + "-" ^^ (_ => (e: Expr) => Unary(Neg, e)) | + "!" ^^ (_ => (e: Expr) => Unary(Not, e)) + + def call: this.Parser[Expr] = + term ~ rep(callop) ^^ { case e0 ~ calls => (calls.foldLeft(e0)){ case (acc, mk) => mk(acc) } } + + def callop: this.Parser[Expr => Expr] = + withpos("(" ~> expr <~ ")") ^^ { case (pos, arg) => (e0 => Call(e0, arg) setPos pos) } + + def term: this.Parser[Expr] = + positioned( + ident ^^ (s => Var(s)) | + floatLit ^^ (s => N(s.toDouble)) | + stringLit ^^ (s => S(s)) | + "true" ^^ (_ => B(true)) | + "false" ^^ (_ => B(false)) | + "undefined" ^^ (_ => Undefined) | + ("jsy" ~ "." ~ "print") ~> "(" ~> expr <~ ")" ^^ (e => Print(e)) | + ("console" ~ "." ~ "log") ~> "(" ~> expr <~ ")" ^^ (e => Print(e)) | + function + ) | + "(" ~> expr <~ ")" | + "{" ~> "{" ~> prog <~ "}" <~ "}" | + failure("atomic expression expected") + + def function: this.Parser[Expr] = + ("function" ~> opt(ident)) ~ ("(" ~> ident <~ ")") ~ funblock ^^ { + case f ~ x ~ body => Fun(f, x, body) + } + + def withpos[T](q: => this.Parser[T]): this.Parser[(Position, T)] = this.Parser { in => + q(in) match { + case Success(t, in1) => Success((in.pos,t), in1) + case ns: NoSuccess => ns + } + } + + def withposrep[T](q: => this.Parser[T]): this.Parser[List[(Position,T)]] = + rep(withpos(q)) + + def withposrep1[T](q: => this.Parser[T]): this.Parser[List[(Position,T)]] = + rep1(withpos(q)) + + private var parseSource: String = "<source>" + + def formatErrorMessage(pos: Position, kind: String, msg: String): String = + if (pos != NoPosition) + "%s\n%s:%s:%s: %s\n%s".format(kind, parseSource, pos.line, pos.column, msg, pos.longString) + else + "%s\n%s: %s".format(kind, parseSource, msg) + + class SyntaxError(msg: String, next: Input) extends Exception { + override def toString = formatErrorMessage(next.pos, "SyntaxError", msg) + } + + def parseTokens(tokens: lexical.Scanner): Expr = { + phrase(prog)(tokens) match { + case Success(e, _) => e + case NoSuccess(msg, next) => throw new SyntaxError(msg, next) + case Error(msg, next) => throw new SyntaxError(msg, next) + case Failure(msg,next) => throw new SyntaxError(msg, next) + } + } + + /*** External Interface ***/ + + def formatErrorMessage(e: Expr, kind: String, msg: String): String = + formatErrorMessage(e.pos, kind, msg) + + def parse(s: String): Expr = { + parseTokens(new lexical.Scanner(s)) + } + + def parse(in: InputStream): Expr = { + val reader = StreamReader(new InputStreamReader(in)) + parseTokens(new lexical.Scanner(reader)) + } + + def parseFile(filename: String): Expr = { + parseSource = filename + parse(new FileInputStream(filename)) + } + + def parseFile(file: File): Expr = { + parseSource = file.getName + parse(new FileInputStream(file)) + } + + implicit class StringExpr(s: String) { + val e = parse(s) + def a: Expr = e + } +} diff --git a/lab3/src/main/scala/jsy/lab3/ast.scala b/lab3/src/main/scala/jsy/lab3/ast.scala new file mode 100644 index 0000000..eb15400 --- /dev/null +++ b/lab3/src/main/scala/jsy/lab3/ast.scala @@ -0,0 +1,106 @@ +package jsy.lab3 + +import scala.util.parsing.input.Positional + +/** + * @author Bor-Yuh Evan Chang + */ +object ast { + sealed trait Expr extends Positional // e ::= + + /* Literals */ + case class N(n: Double) extends Expr // e ::= n + case class B(b: Boolean) extends Expr // e ::= b + case class S(str: String) extends Expr // e ::= str + case object Undefined extends Expr // e ::= undefined + + /* Unary and Binary Expressions */ + case class Unary(uop: Uop, e1: Expr) extends Expr // e ::= uop e1 + case class Binary(bop: Bop, e1: Expr, e2: Expr) extends Expr // e ::= e1 bop e2 + + sealed trait Uop // uop ::= + sealed trait Bop // bop ::= + + /* Numbers */ + case object Neg extends Uop // uop ::= - + + case object Plus extends Bop // bop ::= + + case object Minus extends Bop // bop ::= - + case object Times extends Bop // bop ::= * + case object Div extends Bop // bop ::= / + + /* Booleans */ + case object Not extends Uop // uop ::= ! + case object And extends Bop // bop ::= && + case object Or extends Bop // bop ::= || + + case class If(e1: Expr, e2: Expr, e3: Expr) extends Expr // e ::= e1 ? e2 : e3 + + case object Eq extends Bop // bop ::= === + case object Ne extends Bop // bop ::= !== + case object Lt extends Bop // bop ::= < + case object Le extends Bop // bop ::= <= + case object Gt extends Bop // bop ::= > + case object Ge extends Bop // bop ::= >= + + /* Side-Effects */ + case class Print(e1: Expr) extends Expr // e ::= console.log(e1) + case object Seq extends Bop // bop ::= , + + /* Variables */ + case class Var(x: String) extends Expr // e ::= x + case class ConstDecl(x: String, e1: Expr, e2: Expr) extends Expr // e ::= const x = e1; e2 + + /* Functions */ + case class Fun(p: Option[String], x: String, e1: Expr) extends Expr // e::= p(x) => e1 + case class Call(e1: Expr, e2: Expr) extends Expr // e ::= e1(e2) + + /* Define values. */ + def isValue(e: Expr): Boolean = e match { + case N(_) | B(_) | Undefined | S(_) | Fun(_, _, _) => true + case _ => false + } + + /* + * Pretty-print values. + * + * We do not override the toString method so that the abstract syntax can be printed + * as is. + */ + def pretty(v: Expr): String = { + require(isValue(v)) + (v: @unchecked) match { + case N(n) => prettyNumber(n) + case B(b) => b.toString + case Undefined => "undefined" + case S(s) => s + case Fun(p, _, _) => + "[Function%s]".format(p match { case None => "" case Some(s) => ": " + s }) + } + } + + def prettyNumber(n: Double): String = + if (n.isWhole) "%.0f" format n else n.toString + + /* Get the free variables of e. */ + def freeVars(e: Expr): Set[String] = e match { + case Var(x) => Set(x) + case ConstDecl(x, e1, e2) => freeVars(e1) | (freeVars(e2) - x) + case Fun(None, x, e1) => freeVars(e1) - x + case Fun(Some(x1), x2, e1) => freeVars(e1) - x2 - x1 + case N(_) | B(_) | Undefined | S(_) => Set.empty + case Unary(_, e1) => freeVars(e1) + case Binary(_, e1, e2) => freeVars(e1) | freeVars(e2) + case If (e1, e2, e3) => freeVars(e1) | freeVars(e2) | freeVars(e3) + case Call(e1, e2) => freeVars(e1) | freeVars(e2) + case Print(e1) => freeVars(e1) + } + + /* Check closed expressions. */ + def closed(e: Expr): Boolean = freeVars(e).isEmpty + + /* typeerror e */ + case class DynamicTypeError(e: Expr) { + override def toString = s"TypeError: in expression $e" + } +} diff --git a/lab3/src/main/scala/jsy/util/JsyApplication.scala b/lab3/src/main/scala/jsy/util/JsyApplication.scala new file mode 100644 index 0000000..46b658d --- /dev/null +++ b/lab3/src/main/scala/jsy/util/JsyApplication.scala @@ -0,0 +1,191 @@ +package jsy.util + +import java.io.{ByteArrayOutputStream, File} +import java.nio.file.Files + +trait JsyApplication { + var debug = false /* set to false to disable debugging output */ + var keepGoing = true /* set to true to keep going after exceptions */ + var maxSteps: Option[Int] = None /* set to a number to bound the number of execution steps */ + + /*** Implement this method to process a file. ***/ + def processFile(file: File): Unit + + var anonOption = ("input", + { case filename :: Nil => new File(filename) }: PartialFunction[List[String], File], + "A file containing a JavaScripty program or a directory with .jsy files.") + + var flagOptions = List( + ("debug", options.SetBool(b => debug = b, Some(b => debug == b)), "debugging"), + ("keep-going", options.SetBool(b => keepGoing = b, Some(b => keepGoing == b)), "keep going after exceptions"), + ("bound-steps", options.SetInt( + { i => maxSteps = i }, + Some({ + case true => maxSteps map { i => ": %d".format(i) } + case false => if (maxSteps == None) Some("") else None + })), + "bound for maximum number of execution steps before aborting") + ) + + def handle[T](default: T)(e: => T): T = + if (!keepGoing) e + else try e catch { + case exn: Throwable => println(exn.toString); default + } + + def testJsy(file: File)(k: (File, File, => (Boolean, String)) => Unit): Unit = { + val jsyext = """[.]jsy$""".r + val ans: File = new File(jsyext.replaceAllIn(file.getPath, ".ans")) + k(file, ans, { + if (!ans.exists()) { + (false, s"Expected output file ${ans} does not exist.") + } + else { + val outstream = new ByteArrayOutputStream() + Console.withOut(outstream)(handle(()){ processFile(file)}) + + val encoding = java.nio.charset.StandardCharsets.UTF_8 + val ansstring = new String(Files.readAllBytes(ans.toPath), encoding) + + outstream.flush() + val outstring = new String(outstream.toString(encoding.toString)) + outstream.close() + + (ansstring == outstring, s"Computed output does not match expected output.\nComputed:\n${outstring}\nExpected:\n${ansstring}") + } + }) + } + + def isJsy(file: File): Boolean = { + val jsyext = """[.]jsy$""".r + jsyext findFirstIn file.getName match { + case Some(_) => true + case None => false + } + } + + def doFile(doit: File => Unit, file: File) = { + def loop(file: File): Unit = { + if (file.isFile) { + doit(file) + } + else if (file.isDirectory) { + file.listFiles filter { f => f.isDirectory || isJsy(f) } foreach loop + } + else { + throw new IllegalArgumentException("File %s does not exist.".format(file)) + } + } + loop(file) + } + + def test(fileordir: File)(k: (File, File, => (Boolean, String)) => Unit): Unit = { + doFile({ f => testJsy(f)(k) }, fileordir) + } + + def main(args: Array[String]): Unit = { + val opts = new options.Options("jsy", flagOptions, anonOption) + val file: File = opts.process(args) + doFile(processFile, file) + } +} + +object options { + sealed abstract class Spec + case class SetBool(setter: Boolean => Unit, default: Option[Boolean => Boolean]) extends Spec + case class SetInt(setter: Option[Int] => Unit, default: Option[Boolean => Option[String]]) extends Spec + + class Options[T](program: String, specs: List[(String, Spec, String)], anon: (String, PartialFunction[List[String], T], String)) { + val opts: Map[String, List[String] => Option[List[String]]] = + specs.foldLeft[Map[String, List[String] => Option[List[String]]]](Map.empty)((acc, spec) => spec match { + case (name, SetBool(setter, _), _) => + acc + + (("--" + name) -> { (t: List[String]) => setter(true); Some(t) }) + + (("--no-" + name) -> { (t: List[String]) => setter(false); Some(t) }) + case (name, SetInt(setter, _), _) => + acc + + (("--" + name) -> { (t: List[String]) => t match { + case arg :: t => + val argp: Int = try arg.toInt catch { case _: Throwable => usageErr() } + setter(Some(argp)); Some(t) + case _ => usageErr() + } }) + + (("--no-" + name) -> { (t: List[String]) => setter(None); Some(t) }) + }) + + val (anonName, anonDo, anonDesc) = anon + + val nameWidth: Int = opts.foldLeft(anonName.length){ case (acc, (n, _)) => acc max (n.length + 5) } + + def padRight(s: String, w: Int): String = { + val nspaces = (w - s.length) max 0 + s + (" " * nspaces) + } + + def optline(name: String, text: String): String = { + "%-2s".format("") + padRight(name, nameWidth) + " %s%n".format(text) + } + + val descriptions: String = { + (specs foldRight "")((spec, acc) => spec match { + case (name, SetBool(_, default), desc) => { + def defaultStr(b: Boolean): String = + default map (f => if (f(b)) " (default)" else "") getOrElse("") + optline("--" + name, "turn on %s".format(desc) + defaultStr(true)) + + optline("--no-" + name, "turn off %s".format(desc) + defaultStr(false)) + + acc + } + case (name, SetInt(_, default), desc) => { + def defaultStr(b: Boolean): String = { + val opt = + for { + f <- default + s <- f(b) + } yield " (default%s)".format(s) + opt.getOrElse("") + } + optline("--" + name + " <int>", "set %s".format(desc) + defaultStr(true)) + + optline("--no-" + name, "unset %s".format(desc) + defaultStr(false)) + + acc + } + }) + } + + val header = + """ +Usage: %s [options] %s + +""".format(program, anonName) + +optline(anonName, anonDesc) + """ +Options: +""" + + private var currentArgs: List[String] = List() + + def usageErr(): Nothing = { + val unprocessed = currentArgs match { + case Nil => "" + case _ => """ +Unprocessed Arguments: + """ + currentArgs.reduceRight({ _ + " " + _ }) + "%n".format() + } + print(header + descriptions + unprocessed) + sys.exit(1) + } + + def process(args: Array[String]): T = { + def loop(l: List[String]): List[String] = { + currentArgs = l + l match { + case Nil => Nil + case h :: t => opts.get(h) match { + case None => l + case Some(doit) => { val tp = doit(t).getOrElse(t); loop(tp) } + } + } + } + val err: PartialFunction[List[String], T] = { case _ => usageErr() } + (anonDo orElse err)(loop(args.toList)) + } + } +}
\ No newline at end of file diff --git a/lab3/src/test/resources/lab3/test3004_call.ans b/lab3/src/test/resources/lab3/test3004_call.ans new file mode 100644 index 0000000..cedff5b --- /dev/null +++ b/lab3/src/test/resources/lab3/test3004_call.ans @@ -0,0 +1,8 @@ +# Stepping ... +## 0: ConstDecl(w,Fun(None,y,Binary(Minus,Var(y),N(7.0))),Print(Call(Var(w),N(4.3)))) +## 1: Print(Call(Fun(None,y,Binary(Minus,Var(y),N(7.0))),N(4.3))) +## 2: Print(Binary(Minus,N(4.3),N(7.0))) +## 3: Print(N(-2.7)) +-2.7 +## 4: Undefined +undefined diff --git a/lab3/src/test/resources/lab3/test3004_call.jsy b/lab3/src/test/resources/lab3/test3004_call.jsy new file mode 100644 index 0000000..4054060 --- /dev/null +++ b/lab3/src/test/resources/lab3/test3004_call.jsy @@ -0,0 +1,2 @@ +const w = function (y) { return y - 7 } +console.log(w(4.3)) diff --git a/lab3/src/test/resources/lab3/test3006_curry.ans b/lab3/src/test/resources/lab3/test3006_curry.ans new file mode 100644 index 0000000..8a00bc5 --- /dev/null +++ b/lab3/src/test/resources/lab3/test3006_curry.ans @@ -0,0 +1,8 @@ +# Stepping ... +## 0: ConstDecl(g,Fun(None,x,Fun(None,y,Binary(And,Var(x),Var(y)))),Binary(Plus,Call(Call(Var(g),N(1.0)),N(0.0)),N(0.1))) +## 1: Binary(Plus,Call(Call(Fun(None,x,Fun(None,y,Binary(And,Var(x),Var(y)))),N(1.0)),N(0.0)),N(0.1)) +## 2: Binary(Plus,Call(Fun(None,y,Binary(And,N(1.0),Var(y))),N(0.0)),N(0.1)) +## 3: Binary(Plus,Binary(And,N(1.0),N(0.0)),N(0.1)) +## 4: Binary(Plus,N(0.0),N(0.1)) +## 5: N(0.1) +0.1 diff --git a/lab3/src/test/resources/lab3/test3006_curry.jsy b/lab3/src/test/resources/lab3/test3006_curry.jsy new file mode 100644 index 0000000..2e87562 --- /dev/null +++ b/lab3/src/test/resources/lab3/test3006_curry.jsy @@ -0,0 +1,2 @@ +const g = function(x) { return function(y) { return x && y } }; +g(1)(0) + 0.1 diff --git a/lab3/src/test/resources/lab3/test3008_call.ans b/lab3/src/test/resources/lab3/test3008_call.ans new file mode 100644 index 0000000..3e34395 --- /dev/null +++ b/lab3/src/test/resources/lab3/test3008_call.ans @@ -0,0 +1,48 @@ +# Stepping ... +## 0: ConstDecl(f,Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Plus,Call(Var(f),N(8.0)),N(0.1))) +## 1: Binary(Plus,Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),N(8.0)),N(0.1)) +## 2: Binary(Plus,If(Binary(Eq,N(8.0),N(0.0)),N(1.0),Binary(Times,N(8.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(8.0),N(1.0))))),N(0.1)) +## 3: Binary(Plus,If(B(false),N(1.0),Binary(Times,N(8.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(8.0),N(1.0))))),N(0.1)) +## 4: Binary(Plus,Binary(Times,N(8.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(8.0),N(1.0)))),N(0.1)) +## 5: Binary(Plus,Binary(Times,N(8.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),N(7.0))),N(0.1)) +## 6: Binary(Plus,Binary(Times,N(8.0),If(Binary(Eq,N(7.0),N(0.0)),N(1.0),Binary(Times,N(7.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(7.0),N(1.0)))))),N(0.1)) +## 7: Binary(Plus,Binary(Times,N(8.0),If(B(false),N(1.0),Binary(Times,N(7.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(7.0),N(1.0)))))),N(0.1)) +## 8: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(7.0),N(1.0))))),N(0.1)) +## 9: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),N(6.0)))),N(0.1)) +## 10: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),If(Binary(Eq,N(6.0),N(0.0)),N(1.0),Binary(Times,N(6.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(6.0),N(1.0))))))),N(0.1)) +## 11: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),If(B(false),N(1.0),Binary(Times,N(6.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(6.0),N(1.0))))))),N(0.1)) +## 12: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(6.0),N(1.0)))))),N(0.1)) +## 13: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),N(5.0))))),N(0.1)) +## 14: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),If(Binary(Eq,N(5.0),N(0.0)),N(1.0),Binary(Times,N(5.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(5.0),N(1.0)))))))),N(0.1)) +## 15: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),If(B(false),N(1.0),Binary(Times,N(5.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(5.0),N(1.0)))))))),N(0.1)) +## 16: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(5.0),N(1.0))))))),N(0.1)) +## 17: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),N(4.0)))))),N(0.1)) +## 18: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),If(Binary(Eq,N(4.0),N(0.0)),N(1.0),Binary(Times,N(4.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(4.0),N(1.0))))))))),N(0.1)) +## 19: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),If(B(false),N(1.0),Binary(Times,N(4.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(4.0),N(1.0))))))))),N(0.1)) +## 20: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(4.0),N(1.0)))))))),N(0.1)) +## 21: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),N(3.0))))))),N(0.1)) +## 22: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),If(Binary(Eq,N(3.0),N(0.0)),N(1.0),Binary(Times,N(3.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(3.0),N(1.0)))))))))),N(0.1)) +## 23: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),If(B(false),N(1.0),Binary(Times,N(3.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(3.0),N(1.0)))))))))),N(0.1)) +## 24: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(3.0),N(1.0))))))))),N(0.1)) +## 25: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),N(2.0)))))))),N(0.1)) +## 26: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),If(Binary(Eq,N(2.0),N(0.0)),N(1.0),Binary(Times,N(2.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(2.0),N(1.0))))))))))),N(0.1)) +## 27: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),If(B(false),N(1.0),Binary(Times,N(2.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(2.0),N(1.0))))))))))),N(0.1)) +## 28: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Binary(Times,N(2.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(2.0),N(1.0)))))))))),N(0.1)) +## 29: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Binary(Times,N(2.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),N(1.0))))))))),N(0.1)) +## 30: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Binary(Times,N(2.0),If(Binary(Eq,N(1.0),N(0.0)),N(1.0),Binary(Times,N(1.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(1.0),N(1.0)))))))))))),N(0.1)) +## 31: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Binary(Times,N(2.0),If(B(false),N(1.0),Binary(Times,N(1.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(1.0),N(1.0)))))))))))),N(0.1)) +## 32: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Binary(Times,N(2.0),Binary(Times,N(1.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(1.0),N(1.0))))))))))),N(0.1)) +## 33: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Binary(Times,N(2.0),Binary(Times,N(1.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),N(0.0)))))))))),N(0.1)) +## 34: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Binary(Times,N(2.0),Binary(Times,N(1.0),If(Binary(Eq,N(0.0),N(0.0)),N(1.0),Binary(Times,N(0.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(0.0),N(1.0))))))))))))),N(0.1)) +## 35: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Binary(Times,N(2.0),Binary(Times,N(1.0),If(B(true),N(1.0),Binary(Times,N(0.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(0.0),N(1.0))))))))))))),N(0.1)) +## 36: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Binary(Times,N(2.0),Binary(Times,N(1.0),N(1.0))))))))),N(0.1)) +## 37: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Binary(Times,N(2.0),N(1.0)))))))),N(0.1)) +## 38: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),N(2.0))))))),N(0.1)) +## 39: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),N(6.0)))))),N(0.1)) +## 40: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),N(24.0))))),N(0.1)) +## 41: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),N(120.0)))),N(0.1)) +## 42: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),N(720.0))),N(0.1)) +## 43: Binary(Plus,Binary(Times,N(8.0),N(5040.0)),N(0.1)) +## 44: Binary(Plus,N(40320.0),N(0.1)) +## 45: N(40320.1) +40320.1 diff --git a/lab3/src/test/resources/lab3/test3008_call.jsy b/lab3/src/test/resources/lab3/test3008_call.jsy new file mode 100644 index 0000000..0ec8239 --- /dev/null +++ b/lab3/src/test/resources/lab3/test3008_call.jsy @@ -0,0 +1,2 @@ +const f = function f(x) { return x === 0 ? 1 : x * f(x - 1) }; +f(8) + 0.1 diff --git a/lab3/src/test/scala/jsy/lab3/Lab3Spec.scala b/lab3/src/test/scala/jsy/lab3/Lab3Spec.scala new file mode 100644 index 0000000..1b40c01 --- /dev/null +++ b/lab3/src/test/scala/jsy/lab3/Lab3Spec.scala @@ -0,0 +1,150 @@ +package jsy.lab3 + +import org.scalatest.flatspec.AnyFlatSpec +import Parser.parse +import ast._ +import Lab3._ + +class Lab3StudentSpec extends AnyFlatSpec { + + "StudentSpec" should "evaluate a higher order function" in { + val jsyStr: String = + "(function f(g) { return g(g)}) (function g(x) { return x }) (5);" + val answer: Either[DynamicTypeError, Expr] = Right(N(5)) + assert(answer === iterateStep(parse(jsyStr))) + } + + it should "evaluate a recursive function" in { + val jsyStr: String = + "(function f(x) { return x <= 1 ? 1 : x * f(x - 1)}) (3);" + val answer: Either[DynamicTypeError, Expr] = Right(N(6)) + assert(answer === iterateStep(parse(jsyStr))) + } + + it should "evaluate your test case" in { + val jsyStr: String = "1 + 1" + val answer: Either[DynamicTypeError, Expr] = Right(N(2)) + assert(answer === iterateStep(parse(jsyStr))) + } + +} + +class Lab3Spec extends AnyFlatSpec { + + "substitute" should "perform syntatic substitution respecting shadowing" in { + val xplus1 = parse("x + 1") + val twoplus1 = parse("2 + 1") + assert(substitute(N(2), "x", xplus1) === twoplus1) + val constx3 = parse("const x = 3; x") + val shadowx = Binary(Plus, constx3, Var("x")) + assert(substitute(N(2), "x", shadowx) === Binary(Plus, constx3, N(2))) + } + + "iterateBasic" should "work for sumTo(100)" in { + def sumTo(n: Int) = { + iterateBasic(0) { case (acc, i) => + require(n >= 0) + if (i > n) None + else Some(acc + i) + } + } + + assertResult(5050) { sumTo(100) } + } + + { + def sumTo(n: Int): Either[String, Int] = { + iterate(0) { case (acc, i) => + if (n < 0) Some(Left("requirement failed")) + else if (i > n) None + else Some(Right(acc + i)) + } + } + + "iterate" should "work for sumTo(100)" in { + assertResult(Right(5050)) { sumTo(100) } + } + + "iterate" should "work for sumTo(-1)" in { + assertResult(Left("requirement failed")) { sumTo(-1) } + } + + val one = parse("1") + + it should "stop if the callback body returns None" in { + assertResult(Right(one)) { + iterate(one) { (_, _) => None } + } + } + + it should "increment the loop counter on each iteration and use e if the callback body returns Some(e)" in { + assertResult(Right(parse("--1"))) { + iterate(one) { (e: Expr, n: Int) => + if (n == 2) None else Some(Right(Unary(Neg, e))) + } + } + } + } + + "step/call" should "evaluate a function using small-step semantics" in { + val f = "f" + val x = "x" + val e1 = Fun(None, x, Binary(Plus, Var(x), N(1))) + val e2 = N(2) + val e3 = iterateStep(Call(e1, e2)) + assert(e3 === Right(N(3))) + } + + it should "handle recursive functions using small-step semantics" in { + val f = "f" + val x = "x" + val fbody = If( + Binary(Eq, Var(x), N(0)), + Var(x), + Binary(Plus, Var(x), Call(Var(f), Binary(Minus, Var(x), N(1)))) + ) + val e1 = Fun(Some(f), x, fbody) + val e2 = N(3) + val e3 = iterateStep(Call(e1, e2)) + assert(e3 === Right(N(6))) + } + + /* Some tests based on rules */ + + { + val xval = N(2) + val varx = Var("x") + + val e1 = parse("2 - 1 - 1") + val e1p = parse("1 - 1") + val e2 = parse("3 - 1 - 1") + val e2p = parse("2 - 1") + val v1 = N(0) + val v2 = N(1) + + val vidfunction = parse("function (x) { return x }") + + "DoNeg" should "perform DoNeg" in { + val np = -0 + assertResult(Right(N(np))) { + step(Unary(Neg, v1)) + } + } + + "SearchUnary" should "perform SearchUnary" in { + assertResult(Right(Unary(Neg, e1p))) { + step(Unary(Neg, e1)) + } + } + + val e_callerror = Call(N(1), N(2)) + + "TypeErrorCall" should "perform TypeErrorCall" in { + assertResult(Left(DynamicTypeError(e_callerror))) { + step(e_callerror) + } + } + } +} + +class Lab3JsyTests extends jsy.tester.JavascriptyTester(None, "lab3", Lab3) diff --git a/lab3/src/test/scala/jsy/tester/JavascriptyTester.scala b/lab3/src/test/scala/jsy/tester/JavascriptyTester.scala new file mode 100644 index 0000000..48e789c --- /dev/null +++ b/lab3/src/test/scala/jsy/tester/JavascriptyTester.scala @@ -0,0 +1,23 @@ +package jsy.tester +import java.io.File +import jsy.util.JsyApplication +import org.scalatest._ +import flatspec._ + +/* + * A ScalaTest interface for running system tests. + */ +class JavascriptyTester(rootPrefix: Option[String], testDirectory: String, jsy: JsyApplication) extends AnyFlatSpec { + val testResources = s"src${File.separator}test${File.separator}resources" + val testPrefix = rootPrefix match { + case None => testResources + case Some(p) => s"${p}${File.separator}${testResources}" + } + val testPath = s"${testPrefix}${File.separator}${testDirectory}" + jsy.test(new File(testPath)) { case (in,ans,assertion) => + s"eval on ${in}" should s"match ${ans}" in { + val (b: Boolean, msg: String) = assertion + assert(b, msg) + } + } +} |