5/5 - (1 vote)

5/5 – (1 vote)

Topics Covered:

Let binding semantics
Scopes
Function calls

YOUR NAME HERE

Note: Please first run the TEST HELPER cell that defines the passed function below. Failing to run this cell will make it hard for you to check your work.

// TEST HELPER
def passed(points: Int) {
    require(points >=0)
    if (points == 1) print(s"Tests Passed (1 point)")
    else print(s"Tests Passed ($points points)") 
}

Problem 1: Multiple Simultaneous Let Bindings (15 points)

In class, we studied let bindings that assigned a “single” identifier to a “single” expression. Here, we will extend lettuce with multiple let bindings at the same time:

Example 1

let (x, y, z) = (10, 25.6, 30.3) in 
   x - y * z

The program computes 10 - 25.6 * 30.3.

Example 2

In multi-let binding, we treat all the assignments as happening “simultaneously”. For instance, the program

let (x, y, z) = (10, x, y - x) in 
  x - y * z

is disallowed since neither x nor y are in scope in the right hand side of the multi-let binding. Example 2 above produces an error value since x and y are out of scope on the right hand side of the assignment.

Example 3

let x = 15 in 
  let (x, y, z) = (x*x, -10 *x, -2*x) in 
     x + y + z

Note that the usage x*x, -10*x and -2*x refer back to let x = 15 definition. However, the usages x+y+z refer to the result of the “multi-let” binding. Verify that this program will evaluate to “45”.

Grammar of Lettuce

Let us extend a minimalistic subset of Lettuce by adding a MultiLet statement as shown below.

E x p r \Rightarrow | | | | | Const (D o u b l e) Ident (S t r i n g) Plus (E x p r, E x p r) Mult (E x p r, E x p r) Let (I d e n t, E x p r, E x p r) MultiLet (I d e n t *, E x p r *, E x p r) \leftarrow let (x1, .., xn) = (e1, \dots,en) in e Note: Number of identifiers n must match number of expressions n, or else evaluate to error

The scala definitions are given below.

sealed trait Expr
case class Const(d: Double) extends Expr
case class Ident(s: String) extends Expr
case class Plus(e1: Expr, e2: Expr) extends Expr
case class Mult(e1: Expr, e2: Expr) extends Expr 
case class Let(id: String, e1: Expr, e2: Expr) extends Expr
case class MultiLet(id: List[String], eList: List[Expr], e2: Expr) extends Expr

Semantics for MultiLet

Let us write down the semantic rules for a multilet statement:

eval (ei, env) = v i, v i \neq e r r o r, for i = 1, \dots, n, newenv = e n v \circ {x1 \mapsto v 1, \dots, xn \mapsto v n} eval (MultiLet([x1,..,xn], [e1,\dots,en], e2), env) = eval (e2, newenv) (multilet-ok)

The semantic rule above tells you to

Evaluate each of the expressions from e1, …, en under the environment env.
Next, if all the expressions above evaluated without an error, it tells you to update the map env by binding each xi to $v_{i}$ , the result of evaluating ei. You can use the Scala Map “++” operator to achieve this in one shot.
Finally, you should evaluate e2 under the new environment created.

For convenience, we write a single “generic” semantic rule that shows that if some argument ej evaluates to an error, the whole expression is erroneous.

eval (ei, env) = v i, v i \neq e r r o r, for i = 1, \dots, j - 1, e v a l (ej, env) = e r r o r eval (MultiLet([x1,..,xn], [e1,\dots,en], e2), env) = e r r o r (multilet-err-j)

Interpreter for MultiLet Statements

Implement an interpreter for the lettuce language with multi-let statements. Your interpreter does not need to “propagate” error: instead you should throw an IllegalArgumentException whenever an error is encountered.

Style Guide

Use of var/while/for loops in your solution below is disallowed.

sealed trait Value
case class NumValue(f: Double) extends Value
case object Error extends Value /* -- Do not return Error -- simply throw an new IllegalArgumentException whenever you encounter an erroneous case --*/

type Environment = Map[String, Value]

def evalExpr(e: Expr, env: Environment): Value = {
    
    e match {
        case Const(f) => NumValue(f)
        case Ident(x) => { 
            if (env.contains(x)) { 
                env(x)
            } else {
                throw new IllegalArgumentException("Not found identifier")
            }
        }
        case Plus(e1, e2) => {
            val v1 = evalExpr(e1, env)
            val v2 = evalExpr(e2, env)
            (v1, v2) match {
                case (NumValue(f1), NumValue(f2)) => NumValue(f1 + f2)
                case _ => throw new IllegalArgumentException("plus failed")
            }
        }
        case Mult(e1, e2) => {
            val v1 = evalExpr(e1, env)
            val v2 = evalExpr(e2, env)
            (v1, v2) match {
                case (NumValue(f1), NumValue(f2)) => NumValue(f1 * f2)
                case _ => throw new IllegalArgumentException("mult failed")
            }
        }
        case Let(x, e1, e2) => {
            ??? // YOUR CODE HERE
        }
        case MultiLet(xList, eList, e2) => {
            ??? // YOUR CODE HERE
        }
    }
   
}

//BEGIN TEST
/*
 let (x, y) = (10, 20) in 
    let x = y in 
      x +  x * y
*/
val x = Ident("x")
val y = Ident("y")
val let1 = Let("x", y, Plus(x, Mult(x, y)) )
val mlet1 = MultiLet( List("x", "y"), List(Const(10.0), Const(20.0)), let1)
val v = evalExpr(mlet1, Map.empty)
assert(v == NumValue(420.0), s"Test 1 failed expected: NumValue(420.0), obtained $v")

passed(5)
//END TEST

//BEGIN TEST
/*
 let (x, y) = (10, x) in 
    let x = y in 
      x +  x * y
*/
val x = Ident("x")
val y = Ident("y")
val let1 = Let("x", y, Plus(x, Mult(x, y)) )
val mlet1 = MultiLet( List("x", "y"), List(Const(10.0), x), let1)
try {
    val v = evalExpr(mlet1, Map.empty)
    assert(false, "Test 2 failed -- your code should detect a usage of x that is out of scope")
} catch {
    case e:IllegalArgumentException => { println("Illegal argument exception caught -- as expected!!") }
    case _ => {println("Wrong type of exception thrown")}
}

passed(5)
//END TEST

//BEGIN TEST
/*
let (x, y, z, w) = (10, 10, 10, 20 ) in 
  let () = () in 
    let w = w in 
       x *( y + w )
*/

val x = Ident("x")
val y = Ident("y")
val z = Ident("z")
val w = Ident("w")
val ten = Const(10.0)
val twenty = Const(20.0)
val innerLet2 = Let("w", w, Mult(x, Plus(y, w)))
val multiLet1 = MultiLet(Nil, Nil, innerLet2)
val e = MultiLet(List("x","y","z","w"), List(ten, ten, ten, twenty), multiLet1)
val v = evalExpr(e, Map.empty)
assert(v == NumValue(300.0), "Test2 Failed -- expected value NumValue(300.0), obtained value $v")

passed(5)
//END TEST

Problem 2: Translating Lettuce Into Scala (25 points)

In this problem, we will translate Lettuce programs into scala. We will consider the fragment of the language with Let bindings and if-then-else statements.

E x p r \Rightarrow | | | | | | | | | | | Const (D o u b l e) ConstTrue ConstFalse Ident (S t r i n g) Plus (E x p r, E x p r) Minus (E x p r, E x p r) Mult (E x p r, E x p r) Geq (E x p r, E x p r) And (E x p r, E x p r) Or (E x p r, E x p r) IfThenElse (E x p r, E x p r, E x p r) Let (S t r i n g, E x p r, E x p r)

The goal is to implement the function $translateIntoScala (e)$ that inputs a Lettuce Expr $e$ and outputs a string that is supposed to be a scala expression.

We provide semantics of the translation as below:

Note that the output of $translateIntoScala$ is a string.

translateIntoScala (Const (f)) = convertToString (f) (const)

Note that to convert a number to string in scala, use the ‘toString’ method.

translateIntoScala (Ident (x)) = x (ident)

translateIntoScala (ConstTrue) =” t r u e “ (true)

translateIntoScala (ConstFalse) =” f a l s e “ (false)

Note that when you translate subexpressions, you have to make sure to wrap them in curly braces so that things defined in the scope of one subexpression do not accidently fall into another. Please follow the conventions below with curly braces. Otherwise you will not pass the tests

translateIntoScala (e 1) = s 1, translateIntoScala (e 2) = s 2 translateIntoScala (Plus (e 1, e 2)) = {s 1} + {s 2} (plus)

translateIntoScala (e 1) = s 1, translateIntoScala (e 2) = s 2 translateIntoScala (Minus (e 1, e 2)) = {s 1} - {s 2} (minus)

translateIntoScala (e 1) = s 1, translateIntoScala (e 2) = s 2 translateIntoScala (Geq (e 1, e 2)) = {s 1} >= {s 2} (geq)

translateIntoScala (e 1) = s 1, translateIntoScala (e 2) = s 2 translateIntoScala (And (e 1, e 2)) = {s 1} & & {s 2} (and)

translateIntoScala (e 1) = s 1, translateIntoScala (e 2) = s 2 translateIntoScala (Or (e 1, e 2)) = {s 1} | | {s 2} (or)

translateIntoScala (e) = s, translateIntoScala (e 1) = s 1, translateIntoScala (e 2) = s 2 translateIntoScala (IfThenEllse (e, e 1, e 2)) = if ({s}) {s 1} e l s e {s 2} (ite)

translateIntoScala (e 1) = s 1, translateIntoScala (e 2) = s 2 translateIntoScala (Let (x, e 1, e 2)) = val x = {s 1} {s 2} (let)

Whitespaces (space, tab, returns) are ignored by our test cases.

sealed trait Expr
case class Const(f: Double) extends Expr
case object ConstTrue extends Expr
case object ConstFalse extends Expr
case class Ident(s: String) extends Expr
case class Plus(e1: Expr, e2: Expr) extends Expr
case class Minus(e1: Expr, e2: Expr) extends Expr
case class Mult(e1: Expr, e2: Expr) extends Expr
case class Geq(e1: Expr, e2: Expr) extends Expr
case class And(e1: Expr, e2: Expr) extends Expr
case class Or(e1: Expr, e2: Expr) extends Expr
case class IfThenElse(e1: Expr, e2: Expr, e3: Expr) extends Expr
case class Let(x:String, e1: Expr, e2: Expr) extends Expr

def translateIntoScala(e: Expr): String = { 
    ??? // YOUR CODE HERE
}

// PLEASE RUN THIS CELL BEFORE TESTING FURTHER
def cleanUpWhiteSpacesInString(st: String): String = 
    st.filterNot( _.isWhitespace )

val tst1 = """
val x = { { 1 } + { 3 } }
     {
        val y = { 2 }
        {
            val z = { 10 }
                { x } + { { y } * { z } }
        }
     }

"""
print(cleanUpWhiteSpacesInString(tst1))

def checkWhitespaceMunged(testName: String, s1: String, s2: String) : Boolean = {
    println(s"--- Test $testName ---")
    println("Your code returned:")
    println(s"$s1")
    println("Expected result:")
    println(s"$s2")
    cleanUpWhiteSpacesInString(s1) == cleanUpWhiteSpacesInString(s2)
}

//BEGIN TEST

val x = Ident("x")
val y = Ident("y")
val one = Const(1.0)
val two = Const(2.0)

val e1 = Plus(x, y)
val e1Expected = "{ x } + { y }"
val e1Translated = translateIntoScala(e1)
assert(checkWhitespaceMunged("e1", e1Translated, e1Expected), "Failed test for e1")
println("Test passed!")

val e2 = Plus(x, one)
val e2Expected = "{ x } + { 1.0 }"
assert(checkWhitespaceMunged("e2", translateIntoScala(e2), e2Expected), "Failed test for e2")
println("Test passed!")

val e3 = Minus(x, two)
val e3Expected = "{ x } - { 2.0 }"
assert(checkWhitespaceMunged("e3", translateIntoScala(e3), e3Expected), "Failed test for e3")
println("Test passed!")

val e4 = Plus(x, Minus(y, one))
val e4Expected = "{ x } + { { y } - {1.0} }"
val s4 = translateIntoScala(e4)
assert(checkWhitespaceMunged("e4", s4, e4Expected), "Failed test for e4")
println("Test passed!")

val e5 = And( Geq( x, y) , Geq(y, one))
val e5Expected = "{{x} >= {y}} && {{y} >= {1.0}}"
val s5 = translateIntoScala(e5)
assert(checkWhitespaceMunged("e5", s5, e5Expected), "Failed test for e5")
println("Test passed!")

val e6 = Or( Geq( Mult(x, y), Ident("z")) , Geq(y, one))
val e6Expected = "{{ {x} * {y}} >= {z}} || {{y} >= {1.0}}"
val s6 = translateIntoScala(e6)
assert(checkWhitespaceMunged("e6", s6, e6Expected), "Failed test for e6")
println("test passed!")

passed(10)

//END TEST

//BEGIN TEST
val x = Ident("x")
val y = Ident("y")
val one = Const(1.0)
val two = Const(2.0)
val e5 = And( Geq( x, y) , Geq(y, one))
val e5Expected = "{{x} >= {y}} && {{y} >= {1.0}}"
val iteExpr = IfThenElse(e5, one, y)
val iteExpected = s""" if ({$e5Expected}) {
    1.0
} else {
    y
}
"""
val iteTranslated = translateIntoScala(iteExpr)
println("iteTranslated = " + iteTranslated)
assert(checkWhitespaceMunged("itetest", iteTranslated, iteExpected), "Failed test for ite")
passed(5)
//END TEST

//BEGIN TEST
val x = Ident("x")
val y = Ident("y")
val one = Const(1.0)
val two = Const(2.0)
val e6 = Or( Geq( Mult(x, y), Ident("z")) , Geq(y, one))
val e6Expected = "{{ {x} * {y}} >= {z}} || {{y} >= {1.0}}"

val letExpr1 = Let("x", Const(10.0) , Plus(x, one))
val letExpr1Expected = """val x = { 10.0 } {
    { x } + { 1.0 } }
"""
val letExprTranslated1 = translateIntoScala(letExpr1)
assert(checkWhitespaceMunged("letExprTranslated1",letExprTranslated1, letExpr1Expected), "Failed test for letExpr1")


val letExpr2 = Let("x", letExpr1 , Let ("y", two, Plus(x, y)))
val letExprTranslated2 = translateIntoScala(letExpr2)
val letExprExpected2 = """ val x = {
                 	   
                val x = {
                 	   10.0
                }
                {
                 	  { x } + {1.0}
                }
            
                }
                {
                 	  
                val y = {
                 	   2.0
                }
                {
                 	  { x } + {y}
                }
            
                }
"""

assert(checkWhitespaceMunged("letExprTranslated2", letExprTranslated2, letExprExpected2), "Failed test for letExpr2")
passed(10)
//END TEST

Reviews

There are no reviews yet.

Only logged in customers who have purchased this product may leave a review.

Whatsapp Us

[SOLVED] Cspb 3155 : assignment 5

Problem 1: Multiple Simultaneous Let Bindings (15 points)

Example 1

Example 2

Example 3

Grammar of Lettuce

Semantics for MultiLet

Interpreter for MultiLet Statements

Style Guide

Problem 2: Translating Lettuce Into Scala (25 points)

Reviews

Whatsapp Us

[SOLVED] Cspb 3155 : assignment 5

Problem 1: Multiple Simultaneous Let Bindings (15 points)

Example 1

Example 2

Example 3

Grammar of Lettuce

Semantics for MultiLet

Interpreter for MultiLet Statements

Style Guide

Problem 2: Translating Lettuce Into Scala (25 points)

Reviews

Related products

[SOLVED] Programming Project for TCP Socket Programming

[SOLVED] MongoDB CRUD Faculty

[SOLVED] ASSIGNMENT 1: DATA STRUCTURES ADT MyStack

[SOLVED] Info 4604/5604 assignment #1: perceptron #1 1 (version 1.0)

[SOLVED] Individual Programming Assignment

[SOLVED] Implementing a Binary Search Tree