Name: CSCI3155: Assignment 8 Solved
SKU: 48387
Price: 40.00 USD
Availability: InStock

Description

5/5 - (3 votes)

In [ ]:

Name: WRITE YOUR NAME HERE

In [ ]:

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

Problem 1 (20 points): CPS Style Transformation

Reimplement the programs below in the CPS style.

A (10 points)

Convert helloUp, doubleUp and mainFun into the CPS functions helloUp_k, doubleUp_k, mainFun_k. They should take continuations that are of type String => String.

def helloUp(x: String): String = {
    "Hello " + x
}

def doubleUp(x: String): String = {
    x + x
}

def mainFun(x: String): String = {
    doubleUp(helloUp(x) + "World")
}

In [ ]:

??? // YOUR CODE HERE

In [ ]:

//BEGIN TEST
assert(helloUp_k("World", x => x) == "HelloWorld", "Test 1, Set 1 Failed" )
assert(doubleUp_k("World", x => x) == "WorldWorld", "Test 2 Set 1 Failed" )
assert(mainFun_k("Donkey", x => x) == "HelloDonkeyWorldHelloDonkeyWorld", "Test 3 Set 1 Failed")
passed(5)
//END TEST

In [ ]:

//BEGIN TEST
assert(helloUp_k("Hello", x => ("*"+x+"*")) == "*HelloHello*", "Test 1, Set 2 Failed")
assert(doubleUp_k("HelloWorld", x => ("*"+x+"*")) == "*HelloWorldHelloWorld*", "Test 2, Set 2 Failed")
assert(mainFun_k("Cruel", x => ("*"+x+"*")) == "*HelloCruelWorldHelloCruelWorld*", "Test 3, Set 2 Failed")
passed(5)
//END TEST

B (10 points)

Convert the following program into CPS.

def util(x: Int):String = {
    val v1 = 2 * x
    v1.toString
}

def fun1(x: String): Int = {
    val v1 = util(x.toInt)
    v1.toInt
}

def fun2(x: String): String = {
    util(x.toInt)
}

def mainFun(x: String): Int = {
    val v1 = fun2(x)
    val v2 = fun1(x)
    val v3 = v1.length
    v2 - v3
}

To enable this create a polymorphic versions of each function.

def util_k[T](x: Int, k: String => T): T
def fun1_k[T](x: String, k: Int => T):T
def fun2_k[T] (x: String, k: String => T):T 
def mainFun_k[T](x: String, k: Int => T ):T

In [ ]:

def util_k[T] (x: Int, k: String => T):T = {
    ??? // YOUR CODE HERE
}

def fun1_k[T](x: String, k: Int => T):T = {
    ??? // YOUR CODE HERE
}
def fun2_k[T] (x: String, k: String => T):T = {
    ??? // YOUR CODE HERE
}
def mainFun_k[T](x: String, k: Int => T ):T = {
    ??? // YOUR CODE HERE
}

In [ ]:

assert(util_k(10, _ + "d") == "20d", "Test 1 failed")
assert(util_k(21, Some[String]) == Some("42"), "Test 2 failed")
passed(4)

In [ ]:

assert(fun1_k("10", Some[Int]) == Some(20), "Test 1 failed")
assert(fun2_k("-6", _ + "3sdf") == "-123sdf", "Test 2 failed")
passed(2)

In [ ]:

//BEGIN TEST
mainFun_k[Unit]("217", println)
mainFun_k[Unit]("5000", println)
mainFun_k[Unit]("0", println)
assert(mainFun_k[String]("217", x=>(x.toString)) == "431", "Test 2, Set 1 Failed")
assert(mainFun_k[Int]("217", x=>x) == 431, "Test 3, Set 1 Failed")
assert(mainFun_k[Int]("5000", x=>x) == 9995, "Test 4, Set 1 Failed")
assert(mainFun_k[List[Int]]("5000", x => List(x)) == List(9995), "Test 5, Set 1 Failed")
passed(4)
//END TEST

Problem 2 (25 points): Regular Expression Pattern Matching and Continuations

Consider the problem of pattern matching regular expressions. The grammar for regular expressions are given as

$\begin{array}{rcl} \mathbf{RegExpr} & \rightarrow & \text{Atom}(String) \\ & | & \text{Or}(\mathbf{RegExpr}, \mathbf{RegExpr}) \\ & | & \text{Concat} (\mathbf{RegExpr}, \mathbf{RegExpr}) \\ & | & \text{KleeneStar}( \mathbf{RegExpr} ) \\ & | & \text{And} (\mathbf{RegExpr}, \mathbf{RegExpr}) \\ \end{array}$ Given a string, $s$ and regular expression $r$ , we wish to define a function $\mathbf{Matches}(r, s)$ which returns a tuple $(v_1, j)$

Wherein $v_1$ is either $true$ if some <em>prefix</em> of the string $s$ matches the expression $r$ or $false$ otherwise.
If $v_1 = true$ , then $j$ denotes the position where the match ends, such that $j \geq 0$ and $j < \text{length}(s)$ . In other words, the substring $s(0), \ldots, s(j)$ matches the regular expression $r$ .
If $false$ , we will simply set $j = -1$ .

We will use operational semantics rules to define $\mathbf{Matches}$ .

Atom

$\newcommand\semRule[3]{\begin{array}{c} #1 \\ \hline #2 \\ \end{array} (\text{#3}) }$$$$\semRule{ s(0,\ldots, j) = t }{ \mathbf{Matches}(\texttt{Atom(t)}, s) = (true, j)}{atom-match}$ $\semRule{ t\ \text{is not a prefix of}\ s }{ \mathbf{Matches}(\texttt{Atom(t)}, s) = (false, -1)}{atom-no-match}$

Or

$\semRule{ \mathbf{Matches}(\texttt{r1}, s) = (v_1, j_1),\ \mathbf{Matches}(\texttt{r2}, s) = (v_2, j_2) }{ \mathbf{Matches}(\texttt{Or(r1, r2)}, s) = (v_1\ \textit{or}\ v_2, \max(j_1, j_2))}{or-match}$

Concat

$\semRule{ \mathbf{Matches}(\texttt{r1}, s) = (true, j_1),\ \mathbf{Matches}(\texttt{r2}, s(j_1+1,\ldots, n)) = (true, j_2) }{ \mathbf{Matches}(\texttt{Concat(r1, r2)}, s) = (true, j_1+j_2+1)}{concat-match}$ $\semRule{ \mathbf{Matches}(\texttt{r1}, s) = (false, -1) }{ \mathbf{Matches}(\texttt{Concat(r1, r2)}, s) = (false, -1)}{concat-no-match-1}$ $\semRule{ \mathbf{Matches}(\texttt{r1}, s) = (true, j_1),\ \ \mathbf{Matches}(\texttt{r2}, s) = (false, -1) }{ \mathbf{Matches}(\texttt{Concat(r1, r2)}, s) = (false, -1)}{concat-no-match-2}$

Kleene Star

$\semRule{ \mathbf{Matches}(\texttt{r}, s) = (true, j_1),\ n = \text{length}(s),\ \mathbf{Matches}(\texttt{KleeneStar(r)}, s(j+1,\ldots,n) ) = (true, j_2) }{ \mathbf{Matches}(\texttt{KleeneStar(r)}, s) = (true, j_1+j_2+1) }{kleene-star-match}$ $\semRule{ \mathbf{Matches}(\texttt{r}, s) = (false, -1) }{ \mathbf{Matches}(\texttt{KleeneStar(r)}, s) = (true, -1) }{kleene-star-no-match}$ The Kleene-star-no-match rule looks very strange on first sight. But really, it is trying to say that any string matches the Kleene star of a regular expression. However, if the inner regular expression does not match, the Kleene star matches trivially with a match of length 0.

A (10 points)

Complete the code below for evaluating the semantics above.

In [ ]:

sealed trait RegExp
case class Atom(s: String) extends RegExp
case class Or(r1: RegExp, r2: RegExp) extends RegExp
case class Concat(r1: RegExp, r2: RegExp) extends RegExp
case class KleeneStar(r1: RegExp) extends RegExp

def isPrefixOf(t: String, s: String) = {
    /* If string t is a prefix of s, then return true,
       else return false
       */
    s.startsWith(t)
}

def evalRegexp(r: RegExp, s: String ): (Boolean, Int) = r match {
    case Atom(t) => {
        ??? // YOUR CODE HERE
    }
    
    case Or(r1, r2) => {
        val (v1, j1) = evalRegexp(r1, s)
        val (v2, j2) = evalRegexp(r2, s)
        ((v1||v2), math.max(j1, j2) )
    }
    
    case Concat(r1, r2) => {
        ??? // YOUR CODE HERE
    }
    
    case KleeneStar(rHat) => {
        val (v1, j1) = evalRegexp(rHat, s)
        if (v1) {
            val (v2, j2) = evalRegexp(KleeneStar(rHat), s.substring(j1+1, s.length))
            (true, j1+1+j2)
        } else {
            (true, -1)
        }
    }
    
    
}

In [ ]:

//BEGIN TEST
assert( evalRegexp(Atom("hello"), "helloworld") == (true, 4) , "Test 1 failed")
assert(evalRegexp(Atom("hello"), "Helloworld") == (false, -1), "Test 2 failed")
assert(evalRegexp(Or(Atom("hello"), Atom("Hellow")), "Helloworld") == (true, 5), "Test 3 failed")
passed(4)
//END TEST

In [ ]:

//BEGIN TEST
assert(evalRegexp(KleeneStar(Atom("H")), "Helloworld") == (true, 0), "Test 4 failed")
assert(evalRegexp(Concat(Atom("hell"), Atom("owor")), "helloworld") == (true, 7), "Test 5 failed")
passed(3)
//END TEST

In [ ]:

//BEGIN TEST
assert(evalRegexp(Concat( Or( Atom("what"), Or(Atom("why"), Atom("when") )), KleeneStar(Or(Atom("what"), Atom("why") ))), "whatwhywhatwhatwhatwhywhenwhere") == (true, 21), "Test 6 failed")
passed(3)
//END TEST

B (15 points)

Reimplement the interpreter in the CPS so that all recursion happens at the tail position.

In [ ]:

def isPrefixOf_k[T](t: String, s: String, k: Boolean => T): T = {
    /* If string t is a prefix of s, then return true,
       else return false
       */
    ??? // YOUR CODE HERE
}

def evalRegexp(r: RegExp, s: String): (Boolean, Int) = {
    /*-- 
         This has been deliberately placed so that you 
         should not be using evalRegexp for 
         this problem.
     --*/
    
    ???
}

def evalRegexp_k[T](r: RegExp, s: String, k: (Boolean, Int) => T ): T = r match {
    case Atom(t) => {
        isPrefixOf_k(t, s, v => {
            ??? // YOUR CODE HERE
        })    
    }
    
    case Or(r1, r2) => {
        evalRegexp_k(r1, s, (v1:Boolean, j1:Int)=> {
            evalRegexp_k(r2, s.substring(j1+1, s.length), (v2:Boolean, j2: Int) => {
                k((v1 || v2), math.max(j1,j2))    
            })
        })
    }
    
    case Concat(r1, r2) => {
        ??? // YOUR CODE HERE
    }
    
    case KleeneStar(rHat) => {
        evalRegexp_k(rHat, s, (v1: Boolean, j1: Int) => {
                ??? // YOUR CODE HERE
        })
        
    }
    
    
}

In [ ]:

//BEGIN TEST
assert( evalRegexp_k[Int](Atom("hello"), "helloworld", (x: Boolean, y: Int) => {y} ) == 4, "Test 1 failed")
assert( evalRegexp_k[Boolean](Atom("hello"), "Helloworld", (x: Boolean, y: Int) => {x} ) == false, "Test 2 failed")
passed(5)
//END TEST

In [ ]:

//BEGIN TEST
assert( evalRegexp_k[String](Or(Atom("hello"), Atom("Hellow")), "Helloworld", (x: Boolean, y: Int) => {y.toString} ) == "5", "Test 2 failed")
passed(5)
//END TEST

In [ ]:

//BEGIN TEST
assert(evalRegexp_k(KleeneStar(Atom("H")), "HHHHHelloworld", (x: Boolean, y: Int) => (x,y)) == (true, 4), "Test 4 failed")
assert(evalRegexp_k(Concat(Atom("hell"), Atom("owor")), "helloworld", (x: Boolean, y: Int) => (y)) == 7, "Test 5 failed")
assert(evalRegexp_k(Concat( Or( Atom("what"), Or(Atom("why"), Atom("when") )), KleeneStar(Or(Atom("what"), Atom("why") ))), "whatwhywhatwhatwhatwhywhenwhere", (x: Boolean, y:Int) => (x, y)) == (true, 21), "Test 6 failed")
passed(5)
//END TEST

Problem 3 (20 points)

In this problem, you are asked to write the eval function for Lettuce using CPS style. Here is the stripped down grammar for Lettuce expressions.

In [ ]:

sealed trait Expr
case class Const(v: Double) extends Expr // Expr -> Const(v)
case class Ident(s: String) extends Expr // Expr -> Ident(s)
// Arithmetic Expressions
case class Plus(e1: Expr, e2: Expr) extends Expr // Expr -> Plus(Expr, Expr)
// Boolean Expression
case class Geq(e1: Expr, e2: Expr) extends Expr // Expr -> Bool(Expr, Expr)
//If then else
case class IfThenElse(e: Expr, eIf: Expr, eElse: Expr) extends Expr
//Let bindings
case class Let(s: String, defExpr: Expr, bodyExpr: Expr) extends Expr
//Function definition
case class FunDef(param: String, bodyExpr: Expr) extends Expr
// Function call
case class FunCall(funCalled: Expr, argExpr: Expr) extends Expr

In [ ]:

sealed trait Value
type Environment = Map[String, Value]
case class NumValue(d: Double) extends Value
case class BoolValue(b: Boolean) extends Value
case class Closure(x: String, body: Expr, env: Environment) extends Value

You are asked to implement an eval function using CPS transformation.

In [ ]:

case class ErrorException(msg: String) extends Exception

def evalExpr_cps[T](e: Expr, env: Environment, k: Value => T): T = e match {
    case Const(d) => {
        ??? // YOUR CODE HERE
    }
    case Ident(x) => {
        if (env contains x) {
            ??? // YOUR CODE HERE
        } else {
            throw new ErrorException(s"Unknown identifier $x")
        }
    }
    
    case Plus(e1, e2) => {
        evalExpr_cps(e1, env, (v1) => {
            evalExpr_cps(e2, env, (v2) => {
                (v1, v2) match {
                    case (NumValue(d1), NumValue(d2)) => k(NumValue(d1+d2))
                    case _ => throw new ErrorException(s"Trying to add non-numerical")
                }
            })
        })
    }
    
    case Geq(e1, e2) => {
        ??? // YOUR CODE HERE
    }
    
    case IfThenElse(e, e1, e2) => {
        
        evalExpr_cps(e, env, (v) => {
                v match {
                    case BoolValue(true) => {
                        ??? // YOUR CODE HERE
                    }
                    case BoolValue(false) => {
                        ??? // YOUR CODE HERE
                    } 
                    case _ => {
                        throw new ErrorException("Condition is not a boolean")
                    }
                }
        })
    }
    
    case Let(x, e1, e2) => {
        evalExpr_cps(e1, env, (v) => {
            ??? // YOUR CODE HERE
        })
    }
    
    case FunDef(x, e) => {
        ??? // YOUR CODE HERE
    }
    
    case FunCall(e1, e2) => {
        evalExpr_cps(e1, env, (v)=> {
            v match {
                case Closure(param, body, closureEnv) => {
                     ??? // YOUR CODE HERE
                }
                case _ => {
                    throw new ErrorException("function call on something that is not a function")
                }
            } 
        })
    }
    
}

In [ ]:

val p1 = 
    Let("square",                                // let square = 
         FunDef("x", Plus(Ident("x"), Ident("x"))),  //    function (x) x + x
         FunCall(Ident("square"), Const(10)) //     in  square(10)
       )

assert( evalExpr_cps(p1, Map.empty, x => x) == NumValue(20.0), "Test 1 passed")
passed(6)

In [ ]:

val x = Ident("x")
val y = Ident("y")
val fdef_inner = FunDef("y", Plus(x, Plus(y, y)))
val fdef_outer = FunDef("x", fdef_inner)
val call_expr = FunCall(FunCall(Ident("sq1"), x), y)
val sq1_call = Let("sq1", fdef_outer, call_expr)
val lety = Let("y", Const(15), sq1_call)
val letx = Let("x", Const(10), lety)
val p2 = letx

assert(evalExpr_cps(p2, Map.empty, x => x) == NumValue(40.0))
passed(7)

In [ ]:

val x = Ident("x")
val y = Ident("y")
val iteExpr = IfThenElse(Geq(x, y), Plus(x, Plus(x,y)), Plus(y, Plus(x,x)))
val fdef_inner = FunDef("y", iteExpr)
val fdef_outer = FunDef("x", fdef_inner)
val call_expr = FunCall(FunCall(Ident("sq1"), x), y)
val sq1_call = Let("sq1", fdef_outer, call_expr)
val lety = Let("y", Const(15), sq1_call)
val letx = Let("x", Const(10), lety)
val p3 = letx

assert(evalExpr_cps(p3, Map.empty, x => x) == NumValue(35.0))
passed(7)

assgn8-xrnnxt.zip

CSCI3155: Assignment 8 Solved

If Helpful Share:

Description

Problem 1 (20 points): CPS Style Transformation

A (10 points)

B (10 points)

Problem 2 (25 points): Regular Expression Pattern Matching and Continuations

Atom

Or

Concat

Kleene Star

A (10 points)

B (15 points)

Problem 3 (20 points)

Related products

CSCI 3155: Lab Assignment 4 Solved

CSCI 3155: Lab Assignment 5 Solved

CSCI 3155: Lab Assignment 2 Solved