Name: [SOLVED] Cspb 3155: assignment 7
Brand: Assignment Chef
SKU: 45707
Price: 25 USD
Availability: InStock
Rating: 5 (1 reviews)

5/5 - (1 vote)

5/5 – (1 vote)

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")
}

??? // YOUR CODE HERE

//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

//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

??? // YOUR CODE HERE

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

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

//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

R e g E x p r \to | | | | Atom (S t r i n g) Or (R e g E x p r, R e g E x p r) Concat (R e g E x p r, R e g E x p r) KleeneStar (R e g E x p r) And (R e g E x p r, R e g E x p r)

Given a string, $s$ and regular expression $r$ , we wish to define a function $M a t c h e s (r, s)$ which returns a tuple $(v_{1}, j)$

Wherein $v_{1}$ is either $t r u e$ if some prefix of the string $s$ matches the expression $r$ or $f a l s e$ otherwise.
If $v_{1} = t r u e$ , then $j$ denotes the position where the match ends, such that $j \geq 0$ and $j < length (s)$ . In other words, the substring $s (0), \dots, s (j)$ matches the regular expression $r$ .
If $f a l s e$ , we will simply set $j = - 1$ .

We will use operational semantics rules to define $M a t c h e s$ .

Atom

s (0, \dots, j) = t M a t c h e s (Atom(t), s) = (t r u e, j) (atom-match)

t is not a prefix of s M a t c h e s (Atom(t), s) = (f a l s e, - 1) (atom-no-match)

Or

M a t c h e s (r1, s) = (v 1, j 1), M a t c h e s (r2, s) = (v 2, j 2) M a t c h e s (Or(r1, r2), s) = (v 1 or v 2, max (j 1, j 2)) (or-match)

Concat

M a t c h e s (r1, s) = (t r u e, j 1), M a t c h e s (r2, s (j 1 + 1, \dots, n)) = (t r u e, j 2) M a t c h e s (Concat(r1, r2), s) = (t r u e, j 1 + j 2 + 1) (concat-match)

M a t c h e s (r1, s) = (f a l s e, - 1) M a t c h e s (Concat(r1, r2), s) = (f a l s e, - 1) (concat-no-match-1)

M a t c h e s (r1, s) = (t r u e, j 1), M a t c h e s (r2, s) = (f a l s e, - 1) M a t c h e s (Concat(r1, r2), s) = (f a l s e, - 1) (concat-no-match-2)

Kleene Star

M a t c h e s (r, s) = (t r u e, j 1), n = length (s), M a t c h e s (KleeneStar(r), s (j + 1, \dots, n)) = (t r u e, j 2) M a t c h e s (KleeneStar(r), s) = (t r u e, j 1 + j 2 + 1) (kleene-star-match)

M a t c h e s (r, s) = (f a l s e, - 1) M a t c h e s (KleeneStar(r), s) = (t r u e, - 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.

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)
        }
    }
    
    
}

//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

//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

//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.

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_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
        })
        
    }
    
    
}

//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

//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

//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

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 7

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)

Reviews

Related products

[SOLVED] Minesweeper Game using SFML/C++

[SOLVED] Assignment 2 – Implementing fscanf

[SOLVED] Build a Playlist using Single Linked List in C

[SOLVED] CS4455 Unity 3D All Milestones

[SOLVED] Implementing a Binary Search Tree

[SOLVED] P4 Minesweeper Game using SFML/C++ ( Dec/2022 )