diff options
author | Jack Sangdahl <[email protected]> | 2024-12-12 21:02:45 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-12 21:02:45 -0700 |
commit | 0d13c649bdabafde59233609be7bd88e273c7ae6 (patch) | |
tree | 69e3a615f5c3e6a95a752161136acf00c973184d /lab2 | |
parent | 532be33588fd033fc7f814e725372923cf79a6c4 (diff) | |
download | csci3155-0d13c649bdabafde59233609be7bd88e273c7ae6.tar.gz csci3155-0d13c649bdabafde59233609be7bd88e273c7ae6.zip |
Unit 2
Signed-off-by: Jack Sangdahl <[email protected]>
Diffstat (limited to 'lab2')
19 files changed, 2434 insertions, 0 deletions
diff --git a/lab2/build.sbt b/lab2/build.sbt new file mode 100644 index 0000000..84ff83a --- /dev/null +++ b/lab2/build.sbt @@ -0,0 +1,47 @@ +name := "pppl-lab2" + +lazy val commonSettings = Seq( + organization := "edu.colorado.cs", + version := "4.0.0", + + scalaVersion := "2.13.14", + scalacOptions ++= Seq( + "-unchecked", // Enable additional warnings where generated code depends on assumptions. + "-feature", // Emit warning for features that should be imported explicitly + "-Xcheckinit", // Wrap field accessors to throw an exception on uninitialized access + "-deprecation", // Emit warning and location for usages of deprecated APIs. + "-explaintypes", // Explain type errors in more detail. + "-Ywarn-extra-implicit", // more than one implicit parameter section is defined + "-Xlint:nullary-unit", // nullary methods return Unit + "-Xlint:inaccessible", // inaccessible types in method signatures + "-Xlint:infer-any", // a type argument is inferred to be Any + "-Xlint:missing-interpolator", // literal appears to be missing an interpolator id + "-Xlint:option-implicit", // apply used implicit view + "-Xlint:package-object-classes", // object defined in package object + "-Xlint:stars-align", // wildcard must align with sequence component + "-Xlint:constant", // a constant arithmetic expression results in an error + //"-Xfatal-warnings", // turn warnings into errors + ), + libraryDependencies ++= Seq( + "org.scala-lang.modules" %% "scala-parser-combinators" % "2.4.0", + "org.scalatest" %% "scalatest" % "3.2.19" % "test" + ), + + // set logging to show only errors during runs + logLevel / run := Level.Error, + logLevel / runMain := Level.Error, + Global / excludeLintKeys += logLevel, + + // JVM arguments: 8G heap size, 2M stack size + //javaOptions in Test += "-Xmx8G -Xss2M", + + // scoverage options: always build with coverage + //coverageEnabled := true, + + // scalatest options: -o standard output, D durations + // -e stderr + Test / testOptions += Tests.Argument("-e") +) + +lazy val lab = (project in file(".")). + settings(commonSettings: _*) diff --git a/lab2/project/build.properties b/lab2/project/build.properties new file mode 100644 index 0000000..ee4c672 --- /dev/null +++ b/lab2/project/build.properties @@ -0,0 +1 @@ +sbt.version=1.10.1 diff --git a/lab2/src/main/scala/jsy/lab2/Lab2.scala b/lab2/src/main/scala/jsy/lab2/Lab2.scala new file mode 100644 index 0000000..5788d74 --- /dev/null +++ b/lab2/src/main/scala/jsy/lab2/Lab2.scala @@ -0,0 +1,150 @@ +package jsy.lab2 + +object Lab2 extends jsy.util.JsyApplication { + import ast._ + /* + * CSCI 3155: Lab 2 + * Jack Sangdahl + */ + + def toNumber(v: Expr): Double = { + require(isValue(v)) + (v: @unchecked) match { + case N(n) => n + case B(b) => if (b) 1.0 else 0.0 + case S(s) => try { s.toDouble} catch { case _: NumberFormatException => Double.NaN } + case Undefined => Double.NaN + } + } + + def toBoolean(v: Expr): Boolean = { + require(isValue(v)) + (v: @unchecked) match { + case B(b) => b + case N(n) => n != 0 && !n.isNaN + case S(s) => s.nonEmpty + case Undefined => false + } + } + + def toStr(v: Expr): String = { + require(isValue(v)) + (v: @unchecked) match { + case S(s) => s + case N(n) => n.toString + case B(b) => b.toString + case Undefined => "undefined" + } + } + + /* We represent a variable environment as a map from a string of the + * variable name to the value to which it is bound. + * + * You may use the following provided helper functions to manipulate + * environments, which are just thin wrappers around the Map type + * in the Scala standard library. You can use the Scala standard + * library directly, but these are the only interfaces that you + * need. + */ + type Env = Map[String, Expr] + val empty: Env = Map() + def lookup(env: Env, x: String): Expr = env(x) + def extend(env: Env, x: String, v: Expr): Env = { + require(isValue(v)) + env + (x -> v) + } + + def eval(env: Env, e: Expr): Expr = { + e match { + // literals + case N(n) => N(n) + case B(b) => B(b) + case S(s) => S(s) + case Undefined => Undefined + + // unary ops + case Unary(Neg, e1) => N(-toNumber(eval(env, e1))) + case Unary(Not, e1) => B(!toBoolean(eval(env, e1))) + + // binary ops + case Binary(Plus, e1, e2) => N(toNumber(eval(env, e1)) + toNumber(eval(env, e2))) + case Binary(Minus, e1, e2) => N(toNumber(eval(env, e1)) - toNumber(eval(env, e2))) + case Binary(Times, e1, e2) => N(toNumber(eval(env, e1)) * toNumber(eval(env, e2))) + case Binary(Div, e1, e2) => N(toNumber(eval(env, e1)) / toNumber(eval(env, e2))) + + case Binary(And, e1, e2) => eval(env, e1) match { + case B(b1) if !b1 => B(false) + case N(n1) if n1 == 0 => N(0) + case Undefined => eval(env, e1) + case _ => eval(env, e2) + } + case Binary(Or, e1, e2) => eval(env, e1) match { + case B(b1) if b1 => B(true) + case N(n1) if n1 != 0 => N(n1) + case Undefined => eval(env, e2) + case _ => eval(env, e2) + } + + case Binary(Eq, e1, e2) => (eval(env, e1), eval(env, e2)) match { + case (N(n1), N(n2)) => B(n1 == n2) + case (B(b1), B(b2)) => B(b1 == b2) + case (S(s1), S(s2)) => B(s1 == s2) + case (Undefined, Undefined) => B(true) + case (Undefined, _) => B(false) + case (_, Undefined) => B(false) + case _ => B(false) + } + case Binary(Ne, e1, e2) => B(toNumber(eval(env, e1)) != toNumber(eval(env, e2))) + + case Binary(Lt, e1, e2) => B(toNumber(eval(env, e1)) < toNumber(eval(env, e2))) + case Binary(Le, e1, e2) => B(toNumber(eval(env, e1)) <= toNumber(eval(env, e2))) + case Binary(Gt, e1, e2) => B(toNumber(eval(env, e1)) > toNumber(eval(env, e2))) + case Binary(Ge, e1, e2) => B(toNumber(eval(env, e1)) >= toNumber(eval(env, e2))) + + case Binary(Seq, e1, e2) => + eval(env, e1) + eval(env, e2) + + case If(e1, e2, e3) => + if (toBoolean(eval(env, e1))) eval(env, e2) else eval(env, e3) + + case ConstDecl(x, e1, e2) => + val v1 = eval(env, e1) + eval(env + (x -> v1), e2) + + case Print(e1) => println(pretty(eval(env, e1))); Undefined + case Var(x) => env.getOrElse(x, throw new RuntimeException(s"Variable $x not found")) + } + } + + /* Interface to run your interpreter starting from an empty environment. This is convenient for unit testing. */ + def eval(e: Expr): Expr = { + require(closed(e)) + eval(empty, e) + } + + /* Interface to run your interpreter from a string. This is convenient for unit testing. */ + def eval(s: String): Expr = eval(Parser.parse(s)) + + // You may set this debug flag to true to get the debugging output below, but you need to turn it off to pass test cases. + // debug = true + + /* Interface to run your interpreter on an input file. This is for file-based integration tests (see Lab2JsyTests in Lab2Spec.scala). */ + def processFile(file: java.io.File): Unit = { + + if (debug) { println("Parsing ...") } + + val expr = Parser.parseFile(file) + + if (debug) { + println("\nExpression AST:\n " + expr) + println("------------------------------------------------------------") + } + + if (debug) { println("Evaluating ...") } + + val v = eval(expr) + + println(pretty(v)) + } +} diff --git a/lab2/src/main/scala/jsy/lab2/Lab2.worksheet.js b/lab2/src/main/scala/jsy/lab2/Lab2.worksheet.js new file mode 100644 index 0000000..5a1cb50 --- /dev/null +++ b/lab2/src/main/scala/jsy/lab2/Lab2.worksheet.js @@ -0,0 +1,21 @@ +/* + * CSCI 3155: Lab 2 JavaScript Worksheet + * + * This worksheet is a place to experiment with JavaScript expressions. + */ + +const five = 5; + +five + "five"; + +console.log(five), console.log("five"); + +undefined - true; + +10 * false; + +10 * undefined; + +console.log(undefined ? "then" : "else"); + +console.log("" ? "then" : "else");
\ No newline at end of file diff --git a/lab2/src/main/scala/jsy/lab2/Lab2.worksheet.sc b/lab2/src/main/scala/jsy/lab2/Lab2.worksheet.sc new file mode 100644 index 0000000..3b401ee --- /dev/null +++ b/lab2/src/main/scala/jsy/lab2/Lab2.worksheet.sc @@ -0,0 +1,34 @@ +/* + * CSCI 3155: Lab 2 Worksheet + * + * This worksheet demonstrates how you could experiment + * interactively with your implementations in Lab2.scala. + */ + +// Imports the parse and parseFile functions +import jsy.lab2.Parser.{parse, parseFile} + +// Imports the ast nodes +import jsy.lab2.ast._ + +// Imports all of the functions from your implementation +import jsy.lab2.Lab2._ + +// Call the JavaScripty parser (from the provided library) on a string +val negFourAST = parse("-4") + +// Construct an AST directly +val negFiveAST: Expr = Unary(Neg, N(5.0)) + +// Evaluate that JavaScripty expression. +//eval(negFourAST) + +// For convenience, we also have an eval function that takes a string, +// which calls the parser and then delegates to your eval function. +//eval("undefined + 1") + +// Parse the JavaScripty expression in your worksheet +val worksheetJsy = parseFile("src/main/scala/jsy/lab2/Lab2.worksheet.js") + +// Eval the JavaScripty expression in your worksheet +//eval(worksheetJsy)
\ No newline at end of file diff --git a/lab2/src/main/scala/jsy/lab2/Parser.scala b/lab2/src/main/scala/jsy/lab2/Parser.scala new file mode 100644 index 0000000..b4cf478 --- /dev/null +++ b/lab2/src/main/scala/jsy/lab2/Parser.scala @@ -0,0 +1,255 @@ +/** + * + */ +package jsy.lab2 + +import jsy.lab2.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} + * cond ::= binary [? cond : cond] + * binary ::= unary{bop(_)unary} + * unary ::= uop unary | term + * 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] = + cond + + 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) }) | + term + + def uop: this.Parser[Expr => Expr] = + "-" ^^ (_ => (e: Expr) => Unary(Neg, e)) | + "!" ^^ (_ => (e: Expr) => Unary(Not, e)) + + 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)) + ) | + "(" ~> expr <~ ")" | + "{" ~> "{" ~> prog <~ "}" <~ "}" | + failure("atomic expression expected") + + 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/lab2/src/main/scala/jsy/lab2/ast.scala b/lab2/src/main/scala/jsy/lab2/ast.scala new file mode 100644 index 0000000..7c8fb5e --- /dev/null +++ b/lab2/src/main/scala/jsy/lab2/ast.scala @@ -0,0 +1,92 @@ +package jsy.lab2 + +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 + + /* Define values. */ + def isValue(e: Expr): Boolean = e match { + case N(_) | B(_) | S(_) | Undefined => 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 S(str) => str + case Undefined => "undefined" + } + } + + 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 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 Print(e1) => freeVars(e1) + } + + /* Check closed expressions. */ + def closed(e: Expr): Boolean = freeVars(e).isEmpty +} diff --git a/lab2/src/main/scala/jsy/util/JsyApplication.scala b/lab2/src/main/scala/jsy/util/JsyApplication.scala new file mode 100644 index 0000000..46b658d --- /dev/null +++ b/lab2/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/lab2/src/test/resources/lab2/test2001_boolean.ans b/lab2/src/test/resources/lab2/test2001_boolean.ans new file mode 100644 index 0000000..27ba77d --- /dev/null +++ b/lab2/src/test/resources/lab2/test2001_boolean.ans @@ -0,0 +1 @@ +true diff --git a/lab2/src/test/resources/lab2/test2001_boolean.jsy b/lab2/src/test/resources/lab2/test2001_boolean.jsy new file mode 100644 index 0000000..27ba77d --- /dev/null +++ b/lab2/src/test/resources/lab2/test2001_boolean.jsy @@ -0,0 +1 @@ +true diff --git a/lab2/src/test/resources/lab2/test2002_undefined.ans b/lab2/src/test/resources/lab2/test2002_undefined.ans new file mode 100644 index 0000000..417b7b5 --- /dev/null +++ b/lab2/src/test/resources/lab2/test2002_undefined.ans @@ -0,0 +1 @@ +undefined diff --git a/lab2/src/test/resources/lab2/test2002_undefined.jsy b/lab2/src/test/resources/lab2/test2002_undefined.jsy new file mode 100644 index 0000000..417b7b5 --- /dev/null +++ b/lab2/src/test/resources/lab2/test2002_undefined.jsy @@ -0,0 +1 @@ +undefined diff --git a/lab2/src/test/resources/lab2/test2013_undefinedplusnumber.ans b/lab2/src/test/resources/lab2/test2013_undefinedplusnumber.ans new file mode 100644 index 0000000..736991a --- /dev/null +++ b/lab2/src/test/resources/lab2/test2013_undefinedplusnumber.ans @@ -0,0 +1 @@ +NaN diff --git a/lab2/src/test/resources/lab2/test2013_undefinedplusnumber.jsy b/lab2/src/test/resources/lab2/test2013_undefinedplusnumber.jsy new file mode 100644 index 0000000..0944dac --- /dev/null +++ b/lab2/src/test/resources/lab2/test2013_undefinedplusnumber.jsy @@ -0,0 +1 @@ +undefined + 2.2 diff --git a/lab2/src/test/resources/lab2/test2036_variablelog.ans b/lab2/src/test/resources/lab2/test2036_variablelog.ans new file mode 100644 index 0000000..fed1126 --- /dev/null +++ b/lab2/src/test/resources/lab2/test2036_variablelog.ans @@ -0,0 +1,2 @@ +17.2 +13.1 diff --git a/lab2/src/test/resources/lab2/test2036_variablelog.jsy b/lab2/src/test/resources/lab2/test2036_variablelog.jsy new file mode 100644 index 0000000..8e0c0ad --- /dev/null +++ b/lab2/src/test/resources/lab2/test2036_variablelog.jsy @@ -0,0 +1,3 @@ +const x = 15.1; +console.log(x + 2.1) +x - 2
\ No newline at end of file diff --git a/lab2/src/test/scala/jsy/lab2/Lab2Spec.scala b/lab2/src/test/scala/jsy/lab2/Lab2Spec.scala new file mode 100644 index 0000000..b14d015 --- /dev/null +++ b/lab2/src/test/scala/jsy/lab2/Lab2Spec.scala @@ -0,0 +1,269 @@ +package jsy.lab2 + +import org.scalatest.flatspec.AnyFlatSpec +import Parser.parse +import ast._ + +/* Import your Lab 1 code. */ +import Lab2._ + +/** + * This is an empty test class that you may use to write your own tests. + */ +class Lab2StudentSpec extends AnyFlatSpec { + + val e_toNumber_test1 = N(3.0) + "toNumber" should s"${e_toNumber_test1}" in { + assertResult(3.0) { toNumber(e_toNumber_test1) } + } + + val e_toBoolean_test1 = B(true) + "toBoolean" should s"${e_toBoolean_test1}" in { + assertResult(true) { toBoolean(e_toBoolean_test1) } + } + + val e_toStr_test1 = S("hello") + "toStr" should s"${e_toStr_test1}" in { + assertResult("hello") { toStr(e_toStr_test1) } + } + +} + +/* + * This file contains a number of *Spec classes that define a set of + * tests. + */ +class Lab2Spec extends AnyFlatSpec { + + "And" should "return true only if both expressions are true" in { + val t = B(true) + val f = B(false) + assert(eval(Binary(And,t,t)) === t) + assert(eval(Binary(And,t,f)) === f) + assert(eval(Binary(And,f,t)) === f) + assert(eval(Binary(And,f,f)) === f) + } + + it should "return non-intuitive results from differing types" in { + val e1 = N(0) + val e2 = B(true) + val e3 = eval(Binary(And, e1, e2)) + assert(e3 === N(0)) + } + + "Or" should "return true if either or both expressions are true" in { + val t = B(true) + val f = B(false) + assert(eval(Binary(Or,t,t)) === t) + assert(eval(Binary(Or,f,t)) === t) + assert(eval(Binary(Or,t,f)) === t) + assert(eval(Binary(Or,f,f)) === f) + } + + it should "return non-intuitive results from differing types" in { + val e1 = N(5) + val e2 = B(false) + val e3 = eval(Binary(Or, e1, e2)) + assert(e3 === N(5)) + } + + "Plus" should "add two number values and return a number" in { + val e1 = N(1) + val e2 = N(2) + val e3 = eval(Binary(Plus, e1, e2)) + assert(e3 === N(3)) + } + + "Minus" should "subtract two number values and return a number" in { + val e1 = N(3) + val e2 = N(1) + val e3 = eval(Binary(Minus, e1, e2)) + assert(e3 === N(2)) + } + + "Times" should "multiply two number values and return a number" in { + val e1 = N(3) + val e2 = N(2) + val e3 = eval(Binary(Times, e1, e2)) + assert(e3 === N(6)) + } + + "Div" should "divide two number values and return a number" in { + val e1 = N(8) + val e2 = N(5) + val e3 = eval(Binary(Div, e1, e2)) + assert(e3 === N(1.6)) + } + + "Arithmetic Operators" should "produce non-intuitive solutions given differing expression types" in { + val e1 = B(true) + val e2 = N(7) + assert(eval(Binary(Plus,e1,e2)) == N(8)) + } + + "Eq" should "return true if two numerical values are the same" in { + val e1 = N(5) + val e2 = N(5) + val e3 = eval(Binary(Eq, e1, e2)) + assert(e3 === B(true)) + } + + it should "return false if two numerical values are not the same" in { + val e1 = N(5) + val e2 = N(7) + val e3 = eval(Binary(Eq, e1, e2)) + assert(e3 === B(false)) + } + + "Ne" should "return true if two numerical values are different" in { + val e1 = N(5) + val e2 = N(7) + val e3 = eval(Binary(Ne, e1, e2)) + assert(e3 === B(true)) + } + + it should "return false if two numerical values are the same" in { + val e1 = N(5) + val e2 = N(5) + val e3 = eval(Binary(Ne, e1, e2)) + assert(e3 === B(false)) + } + + "Lt" should "return true if the first expression is less than the second" in { + val e1 = N(5) + val e2 = N(7) + val e3 = eval(Binary(Lt, e1, e2)) + assert(e3 === B(true)) + } + + it should "return false if the first expression is not strictly less than the second" in { + val e1 = N(7) + val e2 = N(5) + val e3 = eval(Binary(Lt, e1, e2)) + assert(e3 === B(false)) + } + + it should "return false if two number values are the same" in { + val e1 = N(5) + val e2 = N(5) + val e3 = eval(Binary(Lt, e1, e2)) + assert(e3 === B(false)) + } + + "Le" should "return true if the first expression is less than the second" in { + val e1 = N(5) + val e2 = N(7) + val e3 = eval(Binary(Le, e1, e2)) + assert(e3 === B(true)) + } + + it should "return false if the first expression is greater than the second" in { + val e1 = N(7) + val e2 = N(5) + val e3 = eval(Binary(Le, e1, e2)) + assert(e3 === B(false)) + } + + it should "return true if two number values are the same" in { + val e1 = N(5) + val e2 = N(5) + val e3 = eval(Binary(Le, e1, e2)) + assert(e3 === B(true)) + } + + "Gt" should "return true if the first expression is greater than the second" in { + val e1 = N(8) + val e2 = N(7) + val e3 = eval(Binary(Gt, e1, e2)) + assert(e3 === B(true)) + } + + it should "return false if the first expression is not strictly greater than the second" in { + val e1 = N(4) + val e2 = N(5) + val e3 = eval(Binary(Gt, e1, e2)) + assert(e3 === B(false)) + } + + it should "return false if two number values are the same" in { + val e1 = N(5) + val e2 = N(5) + val e3 = eval(Binary(Gt, e1, e2)) + assert(e3 === B(false)) + } + + "Ge" should "return true if the first expression is greater than the second" in { + val e1 = N(8) + val e2 = N(7) + val e3 = eval(Binary(Ge, e1, e2)) + assert(e3 === B(true)) + } + + it should "return false if the first expression is less than the second" in { + val e1 = N(4) + val e2 = N(5) + val e3 = eval(Binary(Ge, e1, e2)) + assert(e3 === B(false)) + } + + it should "return true if two number values are the same" in { + val e1 = N(5) + val e2 = N(5) + val e3 = eval(Binary(Ge, e1, e2)) + assert(e3 === B(true)) + } + + "Comparisons" should "produce non-intuitive results given the expressions given" in { + val e1 = N(5) + val e2 = Undefined + assert(eval(Binary(Eq,e1,e2)) === B(false)) + } + + "ConstDecl" should "extend the environment with the first expression results bound to the identifier, and then eval the second expression" in { + val e1 = N(3) + val e2 = Binary(Plus, Var("x"), N(1)) + val e3 = eval(ConstDecl("x", e1, e2)) + assert(e3 === N(4)) + } + + "If" should "eval the first expression if the conditional is true" in { + val e1 = Binary(Plus, N(3), N(2)) + val e2 = Binary(Plus, N(1), N(1)) + val e3 = eval(If(B(true), e1, e2)) + assert(e3 === N(5)) + } + + it should "eval the second expression if the conditional is false" in { + val e1 = Binary(Plus, N(3), N(2)) + val e2 = Binary(Plus, N(1), N(1)) + val e3 = eval(If(B(false), e1, e2)) + assert(e3 === N(2)) + } + + "Seq" should "execute the first expression, followed by the second, and should eval to the second expression" in { + val e1 = Binary(Plus, N(3), N(2)) + val e2 = Binary(Plus, N(1), N(1)) + val e3 = eval(Binary(Seq, e1, e2)) + assert(e3 === N(2)) + } + + "Neg" should "return the negation of a number value" in { + val e1 = N(5) + val e2 = eval(Unary(Neg, e1)) + assert(e2 === N(-5)) + } + + "Not" should "return the compliment of a boolean value" in { + val e1 = B(true) + val e2 = B(false) + val e3 = eval(Unary(Not, e1)) + val e4 = eval(Unary(Not, e2)) + assert(e3 === B(false)) + assert(e4 === B(true)) + } + +} + +// The next bit of code runs a test for each .jsy file in src/test/resources/lab2. +// The test expects a corresponding .ans file with the expected result. +class Lab2JsyTests extends jsy.tester.JavascriptyTester(None, "lab2", Lab2) diff --git a/lab2/src/test/scala/jsy/tester/JavascriptyTester.scala b/lab2/src/test/scala/jsy/tester/JavascriptyTester.scala new file mode 100644 index 0000000..ab611b9 --- /dev/null +++ b/lab2/src/test/scala/jsy/tester/JavascriptyTester.scala @@ -0,0 +1,27 @@ +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) + } + } + +} diff --git a/lab2/variables-values-lab.ipynb b/lab2/variables-values-lab.ipynb new file mode 100644 index 0000000..0a7619a --- /dev/null +++ b/lab2/variables-values-lab.ipynb @@ -0,0 +1,1336 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "id": "e5c7e407-80c5-4211-9055-d94737de0b8d", + "metadata": {}, + "source": [ + "$\\newcommand{\\TirName}[1]{\\text{\\small #1}}\n", + "\\newcommand{\\inferrule}[3][]{\n", + " \\let\\and\\qquad\n", + " \\begin{array}{@{}l@{}}\n", + " \\TirName{#1}\n", + " \\\\\n", + " \\displaystyle\n", + " \\frac{#2}{#3}\n", + " \\end{array}\n", + "}\n", + "\\newcommand{\\infer}[3][]{\\inferrule[#1]{#2}{#3}}\n", + "$\n", + "\n", + "# Lab: Basic Values, Variables, and Judgments\n", + "\n", + "<!-- 3 Expressions -->\n", + "\n", + "<!-- 4 Binding and Scope -->\n", + "\n", + "<!-- 8 Recursion -->\n", + "\n", + "<!-- 9 Inductive Data Types -->\n", + "\n", + "<!-- 11 Concrete Syntax -->\n", + "\n", + "<!-- 12 Abstract Syntax and Parsing -->\n", + "\n", + "<!-- 13 Exercise: Syntax -->\n", + "\n", + "<!-- 14 Static Scoping -->\n", + "\n", + "<!-- 15 Judgments -->\n", + "\n", + "<!-- 16 Variables, Basic Values, and Judgments Lab -->\n", + "\n", + "### Learning Goals\n", + "\n", + "The primary learning goals of this assignment are to build intuition for\n", + "the following:\n", + "\n", + "- the distinction between concrete and abstract syntax;\n", + "- the relationship between judgment forms/inference rules/judgments\n", + " and implementation code;\n", + "- using a reference implementation as a definition of semantics;\n", + "- variable binding and variable environments.\n", + "\n", + "Functional Programming Skills \n", + "Recursion over abstract syntax. Representation invariants.\n", + "\n", + "Programming Language Ideas \n", + "Inductive definitions (grammars/productions/sentences and judgment\n", + "forms/inference rules/judgments). Semantics (via detective work).\n", + "\n", + "### Instructions\n", + "\n", + "A version of project files for this lab resides in the public\n", + "[pppl-lab2](https://github.com/csci3155/pppl-lab2) repository. Please\n", + "follow separate instructions to get a private clone of this repository\n", + "for your work.\n", + "\n", + "You will be replacing `???` or `case _ => ???` in the `Lab2.scala` file\n", + "with solutions to the coding exercises described below.\n", + "\n", + "**Your lab will not be graded if it does not compile**. You may check\n", + "compilation with your IDE, `sbt compile`, or with the “sbt compile”\n", + "GitHub Action provided for you. Comment out any code that does not\n", + "compile or causes a failing assert. Put in `???` as needed to get\n", + "something that compiles without error.\n", + "\n", + "You may add additional tests to the `Lab2Spec.scala` file. In the\n", + "`Lab2Spec.scala`, there is empty test class `Lab2StudentSpec` that you\n", + "can use to separate your tests from the given tests in the `Lab2Spec`\n", + "class. You are also likely to edit `Lab2.worksheet.sc` for any scratch\n", + "work. You can also use `Lab2.worksheet.js` to write and experiment in a\n", + "JavaScript file that you can then parse into a JavaScripty AST (see\n", + "`Lab2.worksheet.sc`).\n", + "\n", + "If you like, you may use this notebook for experimentation. However,\n", + "**please make sure your code is in `Lab2.scala`; this notebook will not\n", + "graded.**\n", + "\n", + "Recall that you need to switch kernels between running JavaScript and\n", + "Scala cells.\n", + "\n", + "## Interpreter: JavaScripty Calculator\n", + "\n", + "In this lab, we extend JavaScripty with additional value types and\n", + "variable binding. That is, the culmination of the lab is to implement an\n", + "interpreter for the subset of JavaScript with numbers, booleans,\n", + "strings, the undefined value, and variable binding." + ] + }, + { + "cell_type": "code", + "execution_count": 1, + "id": "fc23196d", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">trait</span> <span class=\"ansi-cyan-fg\">Expr</span>\n", + "defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">N</span>\n", + "defined <span class=\"ansi-green-fg\">type</span> <span class=\"ansi-cyan-fg\">Env</span>\n", + "<span class=\"ansi-cyan-fg\">empty</span>: <span class=\"ansi-green-fg\">Env</span> = <span class=\"ansi-yellow-fg\">Map</span>()</pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "trait Expr // e ::=\n", + "case class N(n: Double) extends Expr // n\n", + "\n", + "type Env = Map[String, Expr]\n", + "val empty: Env = Map.empty" + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "id": "3615c99b", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">eval</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "def eval(env: Env, e: Expr): Expr = ???" + ] + }, + { + "cell_type": "markdown", + "id": "a2f3b886-b8d3-482d-aac1-088e998593d0", + "metadata": {}, + "source": [ + "We leave the `Expr` inductive data type mostly undefined for the moment\n", + "to focus on the type of `eval`.\n", + "\n", + "First, observe that the return type of `eval` is an `Expr` (versus\n", + "`Double` in the previous lab), as we now have more value types. However,\n", + "`eval` should return an `Expr` that is a JavaScripty value (i.e., is an\n", + "$e$ `: Expr` such that `isValue(` $e$ `)` returns `true`). The need for\n", + "the object-language versus meta-language distinction is even more\n", + "salient here than in the previous lab. For example, it is critical to\n", + "keep straight that `N(1.0)` is the Scala value representing the\n", + "JavaScripty value `1.0`.\n", + "\n", + "Second, observe that the `eval` function takes a JavaScripty value\n", + "environment `env: Env` to give meaning to free JavaScripty variables in\n", + "`e`.\n", + "\n", + "These ideas take unpacking, so let us start from the arithmetic\n", + "sub-language of JavaScripty:" + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "id": "9088c943", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">Unary</span>\n", + "defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">Binary</span>\n", + "defined <span class=\"ansi-green-fg\">trait</span> <span class=\"ansi-cyan-fg\">Uop</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Neg</span>\n", + "defined <span class=\"ansi-green-fg\">trait</span> <span class=\"ansi-cyan-fg\">Bop</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Plus</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Minus</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Times</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Div</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case class Unary(uop: Uop, e1: Expr) extends Expr // e ::= uop e1\n", + "case class Binary(bop: Bop, e1: Expr, e2: Expr) extends Expr // | e1 bop e2\n", + "\n", + "trait Uop // uop ::=\n", + "case object Neg extends Uop // -\n", + "\n", + "trait Bop // bop ::=\n", + "case object Plus extends Bop // +\n", + "case object Minus extends Bop // | -\n", + "case object Times extends Bop // | *\n", + "case object Div extends Bop // | /" + ] + }, + { + "cell_type": "markdown", + "id": "44fff901-f124-48fc-bd1d-906b79120db5", + "metadata": {}, + "source": [ + "Thus far, we have considered only one type of value in our JavaScripty\n", + "object language: numbers $n$ (which we have considered double-precision\n", + "floating-point numbers). Specifically, we have stated the following:\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{expressions} & e& \\mathrel{::=}& v\n", + "\\\\\n", + "\\text{values} & v& \\mathrel{::=}& n\n", + "\\end{array}\n", + "$$\n", + "\n", + "Recall from our preliminary discussion about evaluation\n", + "(**?@sec-evaluation-preliminaries**) that the computational model is a\n", + "rewriting or reduction of expressions until reaching values. A value is\n", + "simply an expression that cannot be reduced any further. Thus, we can\n", + "also consider a unary judgment form $e\\;\\mathsf{value}$ that judges when\n", + "an expression is a value. $$\n", + "\\infer[NumVal]{\n", + "}{\n", + " n\\;\\mathsf{value}\n", + "}\n", + "$$\n", + "\n", + "This judgment form corresponds to the `isValue` function:" + ] + }, + { + "cell_type": "code", + "execution_count": 4, + "id": "bbf7152f", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">isValue</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "def isValue(e: Expr): Boolean = e match {\n", + " case N(_) => true\n", + " case _ => false\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "8dade6b2-d9fb-47a9-91fd-0e2b6aff8f0a", + "metadata": {}, + "source": [ + "From our discussion on grammars and inference rules\n", + "(**?@sec-grammars-and-inference-rules**), we can see this unary judgment\n", + "form $e\\;\\mathsf{value}$ as defining a syntactic category values $v$.\n", + "Thus, we freely write grammar productions for $v$ to define the judgment\n", + "form $e\\;\\mathsf{value}$.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 1**</span> For this part of the\n", + "lab, implement `eval` for the calculator language above (which is the\n", + "same language as in the previous lab) but now with type\n", + "`(Env, Expr) => Expr`." + ] + }, + { + "cell_type": "code", + "execution_count": 5, + "id": "4c173e3a", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">eval</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "def eval(env: Env, e: Expr): Expr = ???" + ] + }, + { + "cell_type": "markdown", + "id": "aa64c2db-875f-4d68-a8e9-61eb3951c890", + "metadata": {}, + "source": [ + "You will not use the `env` parameter yet. You will want to check that\n", + "your implementation returns JavaScripty values. For example," + ] + }, + { + "cell_type": "code", + "execution_count": 6, + "id": "f88d8980", + "metadata": {}, + "outputs": [], + "source": [ + "val e_oneplustwo = Binary(Plus, N(1), N(2))\n", + "assert( isValue( eval(empty, e_oneplustwo) ) )" + ] + }, + { + "cell_type": "markdown", + "id": "9bffa2f5-4fec-43f1-a871-322dd100c795", + "metadata": {}, + "source": [ + "## Coercions: Basic Values\n", + "\n", + "### Booleans, Strings, and Undefined\n", + "\n", + "Like most other languages, JavaScript has other basic value types. Let\n", + "us extend JavaScripty with Booleans, strings, and the\n", + "$\\mathbf{undefined}$ value:\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{values} & v& \\mathrel{::=}&\n", + "b\n", + " \\mid\\mathit{str}\n", + " \\mid\\mathbf{undefined}\n", + "\\\\\n", + "\\text{booleans} & b\n", + "\\\\\n", + "\\text{strings} & \\mathit{str}\n", + "\\end{array}\n", + "$$\n", + "\n", + "Boolean values $b$ are the literals $\\mathbf{true}$ and\n", + "$\\mathbf{false}$. String values $\\mathit{str}$ are string literals like\n", + "`\"hi\"` that we do not explicitly define here.\n", + "\n", + "The $\\mathbf{undefined}$ literal is a distinguished value that is\n", + "different than all other values. It is like the unit literal `()` in\n", + "Scala." + ] + }, + { + "cell_type": "code", + "execution_count": 7, + "id": "67096a6c", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">B</span>\n", + "defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">S</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Undefined</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case class B(b: Boolean) extends Expr // e ::= b\n", + "case class S(str: String) extends Expr // | str\n", + "case object Undefined extends Expr // | undefined" + ] + }, + { + "cell_type": "markdown", + "id": "e9e4fe7c-4dd9-4b7f-85ab-fcbe72cb0292", + "metadata": {}, + "source": [ + "> **Examples**\n", + ">\n", + "> ``` js\n", + "> true\n", + "> ```\n", + ">\n", + "> ``` js\n", + "> false\n", + "> ```\n", + ">\n", + "> ``` js\n", + "> \"Hello\"\n", + "> ```\n", + ">\n", + "> ``` js\n", + "> \"Hola\"\n", + "> ```\n", + ">\n", + "> ``` js\n", + "> undefined\n", + "> ```\n", + "\n", + "We update our `isValue` function appropriately:" + ] + }, + { + "cell_type": "code", + "execution_count": 8, + "id": "11b7ec3b", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">isValue</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "def isValue(e: Expr): Boolean = e match {\n", + " case N(_) | B(_) | S(_) | Undefined => true\n", + " case _ => false\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "2e5c680f-3806-4f25-a0e0-c568a6935a69", + "metadata": {}, + "source": [ + "A good exercise here is to reflect on what this code translates to in\n", + "terms of additional inference rules for the $e\\;\\mathsf{value}$ judgment\n", + "form.\n", + "\n", + "### Expressions\n", + "\n", + "Each value type comes with some operations. Our abstract syntax tree has\n", + "two constructors for unary and binary expressions that are parametrized\n", + "by unary $\\mathit{uop}$ and binary $\\mathit{bop}$ operators,\n", + "respectively:\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{expressions} & e& \\mathrel{::=}&\n", + " \\mid\\mathop{\\mathit{uop}} e_1\n", + " \\mid e_1 \\mathrel{\\mathit{bop}} e_2\n", + "\\end{array}\n", + "$$\n", + "\n", + "#### Numbers\n", + "\n", + "For example, numbers has\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{unary operators} & \\mathit{uop}& \\mathrel{::=}& \\texttt{-}\n", + "\\\\\n", + "\\text{binary operators} & \\mathit{bop}& \\mathrel{::=}& \\texttt{+}\\mid\\texttt{-}\\mid\\texttt{*}\\mid\\texttt{/}\n", + "\\end{array}\n", + "$$\n", + "\n", + "that we considered previously.\n", + "\n", + "#### Booleans\n", + "\n", + "For booleans, we add unary negation $\\texttt{!}$ and binary conjunction\n", + "$\\texttt{\\&\\&}$ and disjunction $\\texttt{||}$. $$\n", + "\\begin{array}{rrrl}\n", + "\\text{unary operators} & \\mathit{uop}& \\mathrel{::=}&\n", + "\\texttt{!}\n", + "\\\\\n", + "\\text{binary operators} & \\mathit{bop}& \\mathrel{::=}&\n", + "\\texttt{\\&\\&}\n", + "\\mid\\texttt{||}\n", + "\\end{array}\n", + "$$" + ] + }, + { + "cell_type": "code", + "execution_count": 9, + "id": "88028ed8", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Not</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">And</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Or</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case object Not extends Uop // uop ::= !\n", + "case object And extends Bop // bop ::= &&\n", + "case object Or extends Bop // | ||" + ] + }, + { + "cell_type": "markdown", + "id": "f21da0e4-59c4-4f78-bd80-ac09e77fa224", + "metadata": {}, + "source": [ + "> **Examples**\n", + ">\n", + "> ``` js\n", + "> !true\n", + "> ```\n", + ">\n", + "> ``` js\n", + "> true && false\n", + "> ```\n", + ">\n", + "> ``` js\n", + "> true || false\n", + "> ```\n", + "\n", + "We also expect to be able to elimate booleans with a conditional\n", + "if-then-else expression: $$\n", + "\\begin{array}{rrrl}\n", + "\\text{expressions} & e& \\mathrel{::=}& e_1\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3\n", + "\\end{array}\n", + "$$" + ] + }, + { + "cell_type": "code", + "execution_count": 10, + "id": "05ea3d8a", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">If</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case class If(e1: Expr, e2: Expr, e3: Expr) extends Expr // e ::= e1 ? e2 : e3" + ] + }, + { + "cell_type": "markdown", + "id": "6fe0176b-eb8a-4882-bd33-aa6e6065df6d", + "metadata": {}, + "source": [ + "We also expect to be able to compare values for equality and disquality\n", + "and numbers for inequality: $$\n", + "\\begin{array}{rrrl}\n", + "\\text{binary operators} & \\mathit{bop}& \\mathrel{::=}&\n", + "\\texttt{===}\n", + "\\mid\\texttt{!==}\n", + "\\mid\\texttt{<}\n", + "\\mid\\texttt{<=}\n", + "\\mid\\texttt{>}\n", + "\\mid\\texttt{>=}\n", + "\\end{array}\n", + "$$" + ] + }, + { + "cell_type": "code", + "execution_count": 11, + "id": "47b3dc58", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Eq</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Ne</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Lt</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Le</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Gt</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Ge</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case object Eq extends Bop // bop ::= ===\n", + "case object Ne extends Bop // | !==\n", + "case object Lt extends Bop // | <\n", + "case object Le extends Bop // | <=\n", + "case object Gt extends Bop // | >\n", + "case object Ge extends Bop // | >=" + ] + }, + { + "cell_type": "markdown", + "id": "ebd33875-524f-4966-96f9-2c1614fef714", + "metadata": {}, + "source": [ + "#### Strings\n", + "\n", + "The one string operation we support in JavaScripty is string\n", + "concatenation. In JavaScript, string concatenation is written with the\n", + "binary operator `+`, so we do not need to extend the syntax.\n", + "\n", + "> **Examples**\n", + ">\n", + "> ``` js\n", + "> \"Hello\" + \", \" + \"World\" + \"!\"\n", + "> ```\n", + "\n", + "#### Undefined\n", + "\n", + "As $\\mathbf{undefined}$ corresponds to unit `()` in Scala and is\n", + "uninteresting in itself, we add a side-effecting expression that prints\n", + "to console.\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{expressions} & e& \\mathrel{::=}& \\texttt{console}\\texttt{.}\\texttt{log}\\texttt{(}e_1\\texttt{)}\n", + "\\end{array}\n", + "$$" + ] + }, + { + "cell_type": "code", + "execution_count": 12, + "id": "226c53fa", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">Print</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case class Print(e1: Expr) extends Expr // e ::= console.log(e1)" + ] + }, + { + "cell_type": "markdown", + "id": "afc77e07-23e1-4c34-9f2e-1a4c7c5f5b4e", + "metadata": {}, + "source": [ + "> **Examples**\n", + ">\n", + "> ``` js\n", + "> console.log(\"Hello, World!\")\n", + "> ```\n", + "\n", + "If we now have side-effecting expressions, then we would expect to have\n", + "a way to sequence executing expressions for their effects.\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{binary operators} & \\mathit{bop}& \\mathrel{::=}& \\texttt{,}\n", + "\\end{array}\n", + "$$" + ] + }, + { + "cell_type": "code", + "execution_count": 13, + "id": "4c211bca", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Seq</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case object Seq extends Bop // bop ::= ," + ] + }, + { + "cell_type": "markdown", + "id": "579a39c5-348a-46e4-b706-a86e0fbfc617", + "metadata": {}, + "source": [ + "> **Examples**\n", + ">\n", + "> ``` js\n", + "> undefined, 3\n", + "> ```\n", + "\n", + "### Semantics Detective: JavaScript is Bananas\n", + "\n", + "In the above, we have carefully specified the abstract syntax of the\n", + "object language of interest and informally discussed its semantics. But\n", + "if we are to implement an interpreter in the `eval` function, we also\n", + "need to define its semantics! And we give a precise definition as\n", + "follows:\n", + "\n", + "> **Important**\n", + ">\n", + "> In this lab, the semantics of a JavaScripty expression $e$ is defined\n", + "> by the evaluation of it as a JavaScript program.\n", + "\n", + "Given the careful specification of the abstract syntax, a natural\n", + "question to ask is whether all abstract syntax trees of type `Expr` in\n", + "the above are valid expressions and have a semantics in JavaScript (and\n", + "hence JavaScripty). Is `3 + true` a valid expression?" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "3e3c4c0b-3d04-40c6-b11a-8ab618b54796", + "metadata": {}, + "outputs": [ + { + "data": {}, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "3 + true" + ] + }, + { + "cell_type": "markdown", + "id": "7af09a5d-90d7-4284-b408-51098a6bc898", + "metadata": {}, + "source": [ + "We try it out and see that yes it is. One aspect that makes the\n", + "JavaScript specification interesting is the presence of implicit\n", + "coercions (e.g., non-numeric values, such as booleans or strings, may be\n", + "implicitly converted to numeric values depending on the context in which\n", + "they are used).\n", + "\n", + "You might guess that defining coercions between value types can lead to\n", + "some interesting semantics. It is because of these coercions that we\n", + "have the meme that “JavaScript is bananas.”" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "0bbdf44a-efd4-42e7-ab8b-3e58b85414dd", + "metadata": {}, + "outputs": [ + { + "data": {}, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "\"b\" + \"a\" + \"n\" + - \"a\" + \"a\" + \"s\"" + ] + }, + { + "cell_type": "markdown", + "id": "a614770c-4f97-4e4b-8ffa-83c4ee7a535b", + "metadata": {}, + "source": [ + "Armed with knowledge that in JavaScript, numbers are floating-point\n", + "numbers, the `+` operator in JavaScript is overloaded for strings and\n", + "numbers, and coercions happen between value types, see if you can\n", + "explain what is happening in the “bananas” expression above.\n", + "\n", + "#### Coercions\n", + "\n", + "Our `eval` function interpreter will need to make use of three helper\n", + "functions for converting values to numbers, booleans, and strings:" + ] + }, + { + "cell_type": "code", + "execution_count": 14, + "id": "76e48b08", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">toNumber</span>\n", + "defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">toBoolean</span>\n", + "defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">toStr</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "def toNumber(v: Expr): Double = ???\n", + "def toBoolean(v: Expr): Boolean = ???\n", + "def toStr(v: Expr): String = ???" + ] + }, + { + "cell_type": "markdown", + "id": "877ad7ab-c025-46d1-8597-a2dc7960e167", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 2**</span> Write at least 1\n", + "JavaScript expression that shows a coercion from a non-numeric value to\n", + "a number and see what the result should be:" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "ecf717e2-a8a2-4163-a2fc-626d3c32614c", + "metadata": {}, + "outputs": [ + { + "data": {}, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "// YOUR CODE HERE\n", + "undefined" + ] + }, + { + "cell_type": "markdown", + "id": "c2e075a3-d8c2-4d4d-b50c-3b05446e7138", + "metadata": {}, + "source": [ + "Then, translate this JavaScript expression (written in concrete syntax)\n", + "into an `Expr` value (i.e., a JavaScripty abstract syntax tree)." + ] + }, + { + "cell_type": "code", + "execution_count": 15, + "id": "f2373c38", + "metadata": {}, + "outputs": [], + "source": [ + "???" + ] + }, + { + "cell_type": "markdown", + "id": "15ae65f0-171c-439e-8391-55db52bc29c7", + "metadata": {}, + "source": [ + "Finally, use this `Expr` as a unit test for `toNumber` in the\n", + "`Lab2StudentSpec` class in the `Lab2Spec.scala` file.\n", + "\n", + "``` scala\n", + "val e_toNumber_test1 = ???\n", + "\"toNumber\" should s\"${e_toNumber_test1}\" in {\n", + " assertResult(???) { toNumber(e_toNumber_test1) }\n", + "}\n", + "```\n", + "\n", + "<span class=\"theorem-title\">**Exercise 3**</span> Do the same to create\n", + "a `toBoolean` test. Write at least 1 JavaScript expression that shows a\n", + "coercion from a non-boolean value to a boolean, see what the result\n", + "should be, translate it to an `Expr` value, and add it as test in\n", + "`Lab2StudentSpec`." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "2028060d-7a15-4b27-9153-4acb2911dcce", + "metadata": {}, + "outputs": [ + { + "data": {}, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "// YOUR CODE HERE\n", + "undefined" + ] + }, + { + "cell_type": "code", + "execution_count": 16, + "id": "2eb72698", + "metadata": {}, + "outputs": [], + "source": [ + "???" + ] + }, + { + "cell_type": "markdown", + "id": "6e8628d8-49de-4749-8c8c-c3e9a5ae2569", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 4**</span> Do the same to create\n", + "a `toStr` test. Write at least 1 JavaScript expression that shows a\n", + "coercion from a non-string value to a string, see what the result should\n", + "be, translate it to an `Expr` value, and add it as test in\n", + "`Lab2StudentSpec`." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "09a51a9d-f222-4462-b99e-2237d3d7e76c", + "metadata": {}, + "outputs": [ + { + "data": {}, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "// YOUR CODE HERE\n", + "undefined" + ] + }, + { + "cell_type": "code", + "execution_count": 17, + "id": "2b0d83e9", + "metadata": {}, + "outputs": [], + "source": [ + "???" + ] + }, + { + "cell_type": "markdown", + "id": "b0804229-2e80-4c50-b10d-45bae14ac467", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 5**</span> Implement `toNumber`,\n", + "`toBoolean`, and `toStr` in `Lab2.scala` (using test-driven development\n", + "with the test cases you have written above).\n", + "\n", + "<span class=\"theorem-title\">**Exercise 6**</span> For this part of the\n", + "lab, extend your `eval` from\n", + "<a href=\"#exr-numbers-eval\" class=\"quarto-xref\">Exercise 1</a> for\n", + "booleans, strings, the undefined value, and printing." + ] + }, + { + "cell_type": "code", + "execution_count": 18, + "id": "d4af7b6b", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">eval</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "def eval(env: Env, e: Expr): Expr = ???" + ] + }, + { + "cell_type": "markdown", + "id": "59a41a5f-f9c2-472c-a3e8-ed1d1511985c", + "metadata": {}, + "source": [ + "You still will not use the `env` parameter yet. You again will want to\n", + "check that your implementation returns JavaScripty values using the\n", + "latest `isValue`. For example," + ] + }, + { + "cell_type": "code", + "execution_count": 19, + "id": "2913288e", + "metadata": {}, + "outputs": [], + "source": [ + "val e_nottrue = Unary(Not, B(true))\n", + "assert( isValue( eval(empty, e_nottrue) ) )" + ] + }, + { + "cell_type": "markdown", + "id": "5d9adaaa-44a9-4020-a559-e61e98217282", + "metadata": {}, + "source": [ + "## Interpreter: JavaScripty Variables\n", + "\n", + "The final piece of this lab is to extend our interpreter with variable\n", + "uses and binding (cf. **?@sec-static-scoping**).\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{expressions} & e& \\mathrel{::=}& x\\mid\\mathbf{const}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2\n", + "\\end{array}\n", + "$$" + ] + }, + { + "cell_type": "code", + "execution_count": 20, + "id": "9c0ab5cd", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">Var</span>\n", + "defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">ConstDecl</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case class Var(x: String) extends Expr // e ::= x\n", + "case class ConstDecl(x: String, e1: Expr, e2: Expr) extends Expr // | const x = e1; e2" + ] + }, + { + "cell_type": "markdown", + "id": "3753b5f9-3d1e-4ef3-9ca6-b016448b3fed", + "metadata": {}, + "source": [ + "Note that the above is the abstract syntax we consider for `ConstDecl`,\n", + "which is more flexible the concrete syntax for `const` allowed by\n", + "JavaScript (cf. )\n", + "\n", + "In this lab, we define a value environment as a map from variable names\n", + "to JavaScripty values, which we represent in Scala as a value of type\n", + "`Map[String, Expr]`. Note that representing variable names as Scala\n", + "`String`s here, and it is a representation invariant that the `Expr`s\n", + "must correspond to JavaScripty values." + ] + }, + { + "cell_type": "code", + "execution_count": 21, + "id": "74452c05", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">type</span> <span class=\"ansi-cyan-fg\">Env</span>\n", + "<span class=\"ansi-cyan-fg\">empty</span>: <span class=\"ansi-green-fg\">Env</span> = <span class=\"ansi-yellow-fg\">Map</span>()\n", + "defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">lookup</span>\n", + "defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">extend</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "type Env = Map[String, Expr]\n", + "val empty: Env = Map.empty\n", + "\n", + "def lookup(env: Env, x: String): Expr = env(x)\n", + "def extend(env: Env, x: String, v: Expr): Env = {\n", + " require(isValue(v))\n", + " env + (x -> v)\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "abf51752-104b-4fe7-b3bb-56f2b30c651d", + "metadata": {}, + "source": [ + "We provide the above value and function bindings to interface with the\n", + "Scala standard library for `Map[String, Expr]` and maintain this\n", + "representation invariant. You may use the Scala standard library\n", + "directly if you wish, but we recommend that you just use these\n", + "interfaces, as they are all that you need and give you the safety of\n", + "enforcing the representation invariant. The `empty` value represents an\n", + "empty value environment, the `lookup` function gets the value bound to\n", + "the variable named by a given string, and the `extend` function extends\n", + "a given environment with a new variable binding.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 7**</span> For this part of the\n", + "lab, extend your `eval` from\n", + "<a href=\"#exr-numbers-eval\" class=\"quarto-xref\">Exercise 1</a> for\n", + "variable uses (i.e., `Var`) and variable binding (i.e., `ConstDecl`). We\n", + "suggest you start by adding tests with variables uses and `const`\n", + "bindings to be able do test-driven development (see below)." + ] + }, + { + "cell_type": "code", + "execution_count": 22, + "id": "cc90dc11", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">eval</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "def eval(env: Env, e: Expr): Expr = ???" + ] + }, + { + "cell_type": "markdown", + "id": "2bb3563b-1d34-4f4b-9feb-2b2c8b6f28df", + "metadata": {}, + "source": [ + "### Testing\n", + "\n", + "In this lab, we have carefully defined the syntax of the JavaScripty\n", + "variant of interest, and we have defined its semantics to be defined to\n", + "be the same as JavaScript. Thus, you can write any JavaScript program\n", + "within the syntax defined above to create test cases for your `eval`\n", + "function. Any of the above JavaScript examples could be used as test\n", + "cases. In some cases, you may want to write abstract syntax trees\n", + "directly in Scala (i.e., values of type `Expr`). In other cases, you can\n", + "use the provided JavaScripty parser to translate concrete syntax (i.e.,\n", + "values of type `String`) into abstract syntax (i.e., values of type\n", + "`Expr`).\n", + "\n", + "<span class=\"theorem-title\">**Exercise 8 (Optional)**</span> We give\n", + "some exercises below to explore this subset of JavaScripty that you can\n", + "then use as test cases that you add to your `Lab2StudentSpec`.\n", + "\n", + "#### Basic Arithmetic Operations" + ] + }, + { + "cell_type": "markdown", + "id": "a2c70244-56b8-4945-b53d-4be38c6ed6e3", + "metadata": {}, + "source": [ + "This program defines two constants, `x` and `y`, and calculates their\n", + "sum. It then logs the result `sum` to the console." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "862e000e-d1a1-4a25-b8bb-1983badfb81e", + "metadata": {}, + "outputs": [], + "source": [ + "const x = 10;\n", + "const y = 5;\n", + "const sum = \n", + " // YOUR CODE HERE (replace undefined)\n", + " undefined\n", + ";\n", + "console.log(sum);" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "5db48d42-a357-4957-bdd2-4436e69d521a", + "metadata": {}, + "outputs": [], + "source": [ + "console.assert(sum === 15)" + ] + }, + { + "cell_type": "markdown", + "id": "369b9301-1017-497b-8175-0654a035b32e", + "metadata": {}, + "source": [ + "#### Conditional Expressions" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "b8ae58be-e5bd-4d13-a6eb-6d6fffbd7f2a", + "metadata": {}, + "outputs": [], + "source": [ + "const a = 10;\n", + "const b = 20;\n", + "const max = \n", + " // YOUR CODE HERE (replace undefined)\n", + " undefined\n", + ";" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "fe6cbe1e-fc0b-4965-a09a-38adcee24776", + "metadata": {}, + "outputs": [], + "source": [ + "console.assert(max === 20)" + ] + }, + { + "cell_type": "markdown", + "id": "32479c1c-d55e-4d89-a4aa-89f58c7397a3", + "metadata": {}, + "source": [ + "#### Unary and Binary Operations\n", + "\n", + "This program checks if a number is positive using a unary negation `-`\n", + "and a binary relational operator." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "01bed277-7e0a-4ebb-8f85-3bc60ca4637f", + "metadata": {}, + "outputs": [], + "source": [ + "const num = -5;\n", + "const isPositive =\n", + " // YOUR CODE HERE (replace undefined)\n", + " undefined\n", + ";" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "2547e992-8b43-4944-bce3-045f9a03807a", + "metadata": {}, + "outputs": [], + "source": [ + "console.assert(isPositive === false)" + ] + }, + { + "cell_type": "markdown", + "id": "36cab120-2f06-4f1b-a68a-e51ca556cf97", + "metadata": {}, + "source": [ + "#### Undefined\n", + "\n", + "This program demonstrates the correspondence between `undefined` in\n", + "JavaScript and `()`." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "1896f8d4-2fe1-4204-8405-a1a678c70ffe", + "metadata": {}, + "outputs": [], + "source": [ + "const r = console.log(\"Hello\");" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "b4138580-25dc-4101-9f30-968ad136a1ee", + "metadata": {}, + "outputs": [], + "source": [ + "console.assert(r === undefined)" + ] + }, + { + "cell_type": "markdown", + "id": "b97d1faf-fb1f-4626-b1c6-405e1fc11ee8", + "metadata": {}, + "source": [ + "## Submission\n", + "\n", + "If you are a University of Colorado Boulder student, we use Gradescope\n", + "for assignment submission. In summary,\n", + "\n", + "- [ ] Create a private GitHub repository by clicking on a GitHub\n", + " Classroom link from the corresponding Canvas assignment entry.\n", + "- [ ] Clone your private GitHub repository to your development\n", + " environment (using the `<> Code` button on GitHub to get the\n", + " repository URL).\n", + "- [ ] Work on this lab from your cloned repository. Use Git to save\n", + " versions on GitHub (e.g., `git add`, `git commit`, `git push` on the\n", + " command line or via VSCode).\n", + "- [ ] Submit to the corresponding Gradescope assignment entry for\n", + " grading by choosing GitHub as the submission method.\n", + "\n", + "You need to have a GitHub identity and must have your full name in your\n", + "GitHub profile in case we need to associate you with your submissions." + ] + } + ], + "metadata": { + "kernelspec": { + "display_name": "Scala", + "language": "scala", + "name": "scala" + }, + "language_info": { + "codemirror_mode": "text/x-scala", + "file_extension": ".sc", + "mimetype": "text/x-scala", + "name": "scala", + "nbconvert_exporter": "script", + "version": "2.13.4" + } + }, + "nbformat": 4, + "nbformat_minor": 5 +} |