[SOLVED] 代写 


|#

#| In this assignment, you’ll be implementing an interpreter for a small language of arithmetic expressions, called Grumpy0. The syntax of this language follows “S-expression” form, and is given by the following BNF grammar:

Unary Operators
u ::== neg #negate a number (not a boolean)

Binary Operators
b ::== + #add two numbers
| – #subtract two numbers
| * #multiply two numbers
| / #divide two numbers
| and #boolean conjunction
| or#boolean disjunction

Values:
v ::== true
| false
| n #a number (one or more integers in the range [0-9])

Expressions:
e ::== v #a value
| x #an identifier
| (u e) #unary op u applied to expression e
| (b e1 e2) #binary op b applies to e1, e2
| (cond e1 e2 e3) #if e1 then e2, else e3
| (let x e2 e3) #let x = the value of e2 in e3 (in which x may appear free)

For example, here’s a valid Grumpy0 program, in concrete syntax:

(let x 3
(let y 4
(+ x y)))

As you might expect, this program evaluates to 7.
|#

#| EXERCISE I starts below, around line 230. Between here and there, I’ve included a parser combinator library (like the one we saw in class) which I recommend you use to complete the first exercise.

### START PARSER COMBINATOR LIBRARY ###

|#

data Unit:
| tt
end

data Error :
| Ok(t :: T)
| Err(msg :: String)
end

# a parser is a function from States to new States paired with Error values. Typically, we’ll instantiate State as String (the input to the parser) and T as the result of parsing, typically an expression in abstract syntax.
data Parser :
| mkParser(f :: (State -> {State; Error }))
end

fun run-parser (p :: Parser , init :: State) -> {State; Error }:
cases(Parser) p:
| mkParser(f) => f(init)
end
end

fun ret (t :: T) -> Parser :
mkParser(lam(s): {s; Ok(t)} end)
end

fun bind (p :: Parser , f :: (A -> Parser )) -> Parser :
mkParser(
lam(s):
{intermediate-s; r} = run-parser(p, s)
cases(Error) r:
| Ok(a) => run-parser(f(a), intermediate-s)
| Err(msg) => {intermediate-s; Err(msg)}
end
end)
end

fun signal (msg :: String) -> Parser :
mkParser(lam(s): {s; Err(msg)} end)
end

fun get () -> Parser :
mkParser(lam(s): {s; Ok(s)} end)
end

fun set-state (s :: State) -> Parser :
mkParser(lam(_): {s; Ok(tt)} end)
end

# drop the first n characters of the input string,
# returning value t.
fun drop(n :: Number) -> Parser :
if n < 0: signal(“drop: n < 0”)else: mkParser(lam(s): if n > string-length(s):
{s; Err(“drop: not enough chars”)}
else:
{string-substring(s, n, string-length(s)); Ok(tt)}
end
end)
end
end

fun string(k :: String) -> Parser :
bind(get(), lam(s):
if string-length(s) < string-length(k):signal(“string: not enough chars”)else: if string-substring(s, 0, string-length(k)) == k:drop(string-length(k))else: signal(“string: no match”)endendend)endfun seq (p1 :: Parser , p2 :: Parser ) -> Parser :
bind(p1, lam(_): p2 end)
end

fun either (p1 :: Parser , p2 :: Parser ) -> Parser :
mkParser(
lam(s):
{new-s; r} = run-parser(p1, s)
cases(Error) r:
| Ok(t1) => {new-s; Ok(t1)}
| Err(msg) => run-parser(p2, s)
end
end)
end

fun epsilon() -> Parser :
string(“”)
end

fun succeed () -> Parser :
mkParser(lam(s): {s; Ok(tt)} end)
end

fun star (p :: Parser ) -> Parser :
either(bind(p, lam(_): star(p) end), succeed())
end

fun plus (p :: Parser ) -> Parser :
seq(p, star(p))
end

fun spaces() -> Parser :
star(string(” “))
end

fun keyword(k :: String) -> Parser :
seq(spaces(), seq(string(k), spaces()))
end

fun parens (p :: Parser ) -> Parser :
seq(keyword(“(“), bind(p, lam(t): seq(keyword(“)”), ret(t)) end))
end

fun take-while (f :: (A -> Boolean), l :: List ) -> List :
cases(List) l:
| empty => empty
| link(x, rest) =>
if f(x):
link(x, take-while(f, rest))
else:
empty
end
end
end

fun drop-while (f :: (A -> Boolean), l :: List ) -> List :
cases(List) l:
| empty => empty
| link(x, rest) =>
if f(x):
drop-while(f, rest)
else:
link(x, rest)
end
end
end

fun is-ascii(i :: Number) -> Boolean:
((65 <= i) and (i <= 90)) or ((97 <= i) and (i <= 122))endfun is-numeric(i :: Number) -> Boolean:
(48 <= i) and (i <= 57)end# return the longest sequence of characters (from the beginning) # satisfying a predicate `f`. # removing the sequence from the input string. # # returns an error if the longest such sequence has length 0.fun eat(f :: (Number -> Boolean)) -> Parser :
bind(get(), lam(s):
points = string-to-code-points(s)
ok-chars = take-while(f, points)
if ok-chars.length() > 0:
seq(set-state(string-from-code-points(drop-while(f, points))),
ret(string-from-code-points(ok-chars)))
else:
signal(“eat: no valid string”)
end
end)
end

# return the longest sequence of ASCII alphabetic characters from the beginning
# of the string
fun alphas() -> Parser :
eat(is-ascii)
end

# return the longest sequence of ASCII numeric [0-9] characters from the beginning
# of the string
fun numerics() -> Parser :
eat(is-numeric)
end

### END PARSER COMBINATOR LIBRARY ###

#| 1. EXERCISE I: In the first part of the assignment, your job is to write a program, `parse`, that translates Grumpy0 programs (expressed in concrete syntax as Strings) into the abstract syntax given below.

We suggest that you use the parser combinators described in class and given to you above (they will make your life a lot easier).

This exercise is nontrivial (meaning it may take you while!). Here’s how we suggest you get started:

– First, read through the Grumpy0 abstract syntax given below. Make sure you understand how the abstract syntax (as encoded by the algebraic datatypes for Exp, Val, Ternop, etc.) corresponds to the Grumpy0 BNF given above. As a warmup exercise (not graded), try translating the example program above into abstract syntax by hand.

– Second, read the provided test cases given at the end of the `parse` function.

– Third, write down a strategy for decomposing the `parse` function into a series of smaller functions, perhaps one each for unops, binops, etc. You might even write down the names of these functions along with their types, perhaps including a few test cases even before you begin coding.

– Fourth and finally, begin writing `parse`.

Once you’re satisfied with your solution for EXERCISE I, move on to the last exercise (EXERCISE II) below.
|#

#| Grumpy0 Abstract Syntax |#

data Unop:
| neg
end

data Binop:
| add
| sub
| mul
| div
| conj
| disj
end

data Val:
| num(n :: Number)
| bool(b :: Boolean)
end

data Exp:
| val(v :: Val)
| id(x :: String)
| unexp(u :: Unop, e :: Exp)
| binexp(b :: Binop, e1 :: Exp, e2 :: Exp)
| cond(e1 :: Exp, e2 :: Exp, e3 :: Exp)
| letx(x :: String, e1 :: Exp, e2 :: Exp)
end

#example expressions
ex1 = val(num(3))
ex2 = val(num(100))
ex3 = val(bool(true))
ex4 = val(bool(false))
ex5 = binexp(add, ex1, ex2)
ex6 = binexp(sub, ex1, ex2)
ex7 = binexp(mul, ex1, ex2)
ex8 = binexp(div, ex1, ex2)
ex9 = binexp(mul, ex8, ex8)
ex10 = binexp(mul, ex7, ex5)
ex11 = binexp(add, id(“x”), id(“y”))

ex20 = unexp(neg, val(num(100)))
ex21 = unexp(neg, (binexp(sub, val(num(5)), val(num(5)))))

ex30 = letx(“x”, val(num(3)), id(“x”))
ex31 = letx(“yzw”, binexp(add, val(num(4)), id(“x”)), id(“x”))
ex32 = letx(“x”, binexp(add, val(num(4)), binexp(add, id(“x”), id(“x”))),
binexp(mul, id(“x”), id(“y”)))

fun unop() -> Parser :
seq(keyword(“neg”), ret(neg))
end

fun unary-exp() -> Parser :
parens(bind(unop(), lam(u):
bind(parse-exp(), lam(e):
ret(unexp(u, e)) end)
end))

end
fun val-exp():
either(num1-exp(),bool-exp())
end
fun num1-exp() -> Parser :
bind(spaces(), lam(u):
bind(numerics(), lam(s):
cases(Option) string-to-number(s):
|some(n) => ret(val(num(n)))
|none => signal(“error”)
end
end)
end)
end
fun bool-exp() -> Parser :
bind(spaces(), lam(u):
bind(alphas(), lam(s):
if s == “true”: ret(val(bool(true)))
else if s == “false”: ret(val(bool(false)))
else: signal(“no bool”)
end
end)
end)
end

fun letx-exp() -> Parser :
parens(bind(either(seq(keyword(“let x”), ret(“x”)), seq(keyword(“let yzw”), ret(“yzw”))), lam(u):
bind(parse-exp(), lam(s):
bind(parse-exp(), lam(z):
if u == “x”: ret(letx(u, s, z))
else if u == “yzw”: ret(letx(u, s, z))
else: signal(“error”)
end
end)
end)
end))
end
fun binexp-exp() -> Parser :
either(add-exp(), either(sub-exp(), either(mul-exp(), either(id-exp(), div-exp()))))
end

fun add-exp() -> Parser :
parens(bind(seq(keyword(“+”), ret(add)), lam(u):
bind(parse-exp(), lam(s):
bind(parse-exp(), lam(z):
ret(binexp(u,s,z))
end)
end)

end))
end

fun sub-exp() -> Parser :
parens(bind(seq(keyword(“-“), ret(sub)), lam(u):
bind(parse-exp(), lam(s):
bind(parse-exp(), lam(z):
ret(binexp(u,s,z))
end)
end)

end))
end
fun mul-exp() -> Parser :
parens(bind(seq(keyword(“*”), ret(mul)), lam(x):
bind(parse-exp(), lam(s):
bind(parse-exp(), lam(z):
ret(binexp(x,s,z))
end)
end)
end))
end
fun div-exp() -> Parser :
parens(bind(seq(keyword(“/”), ret(div)), lam(u):
bind(parse-exp(), lam(s):
bind(parse-exp(), lam(z):
ret(binexp(u,s,z))
end)
end)
end))
end

fun id-exp() -> Parser :
bind(spaces(), lam(u):
bind(either(seq(keyword(“x”), ret(“x”)),seq(keyword(“y”), ret(“y”))), lam(s :: String):
if s == “x”: ret(id(s))
else if s == “y”: ret(id(s))
else: signal(“error”)
end
end)
end)
end
fun parse-exp():
either(val-exp(),
either(unary-exp(),
either(binexp-exp(), letx-exp())))
end

fun parse(s :: String) -> Error :
{new-s; r} = run-parser(parse-exp(), s)
r
where:
#values
parse(“3″) is Ok(ex1)
parse(” 3″) is Ok(ex1)
parse(“3 “) is Ok(ex1)
parse(“100″) is Ok(ex2)
parse(” 100 “) is Ok(ex2)
parse(“true”) is Ok(ex3)
parse(” true”) is Ok(ex3)
parse(“false “) is Ok(ex4)

#binexps
parse(“(+ 3 100)”) is Ok(ex5)
parse(“(- 3 100)”) is Ok(ex6)
parse(“(* 3 100)”) is Ok(ex7)
parse(“(* 3 100 )”) is Ok(ex7)
parse(“(/ 3 100)”) is Ok(ex8)
parse(“(* (/ 3 100) (/ 3 100))”) is Ok(ex9)
parse(“(* (* 3 100) (+ 3 100))”) is Ok(ex10)
parse(“( * ( *3 100) (+ 3 100 ))”) is Ok(ex10)
parse(“(+ x y)”) is Ok(ex11)

#unexps
parse(“(neg 100)”) is Ok(ex20)
parse(“(neg (- 5 5))”) is Ok(ex21)

#let expressions
parse(“(let x 3 x)”) is Ok(ex30)
parse(“( let yzw (+ 4 x) x)”) is Ok(ex31)
parse(”( let x (+ 4 (+ x x)) (*xy) )”) is Ok(ex32)
end

#| 2. EXERCISE II: Implement an interpreter for the Grumpy0 language.

That is, define a function `interp` that takes an initial state (mapping identifiers to their possible values) and an expression, and returns the result of evaluating that expression to a value.

Like EXERCISE I, this exercise is a bit time consuming, and perhaps a bit daunting at first. I suggest you break it down as we did in EXERCISE I:

– First, make sure you understand the task itself (you can check your understanding by reading the test cases given below the function and making sure you understand why they’re correct).

– Second, think about how to break the problem down into smaller functions that, say, interpret just particular kinds of expressions. For example, you might define a function that only knows how to interpret binary operations that are applied to two Vals (not Exps). Then, the overall `interp` function might call this function after first evaluating the binary operations arguments from Exps to Vals.

– Third and finally, start coding!

Note that as in EXERCISE I, you’ll be returning an Error type in this exercise, but this time specialized to Val instead of Exp. Note also that evaluation may fail at various points (say, for instance, you’re evaluating a program that tries to add the boolean “false” to an integer). You’ll need to make sure to deal with failure appropriately (by checking for failure of intermediate or recursive computations and appropriately threading such failures to the return result of the overall function). We suggest you use the Error monad to streamline your code, just as we did in class.
|#

type State = (String -> Error )

init-state = lam(x :: String): Err(string-append(x, ” is unbound”)) end

fun lookup(s :: State, x :: String) -> Error :
s(x)
end

fun upd(s :: State, x :: String, new-val :: Val) -> State:
lam(y :: String):
if string-equal(x, y): Ok(new-val)
else: s(y)
end
end
end

fun err-ret (t :: T) -> Error :
Ok(t)
end

fun err-bind (m :: Error , f :: (A -> Error )) -> Error :
cases(Error) m:
| Ok(a) => f(a)
| Err(msg) => Err(msg)
end
end

fun interp(s :: State, e :: Exp) -> Error :
cases(Exp) e:
| unexp(u, e1) => err-bind(interp(s, e1), lam(x :: Val): #interpret e1 in state s
cases(Unop) u: #case analysis on unary operator
| neg => cases(Val) x: #case analysis on the interpreted value x
| num(y) => Ok(num(-1 * y))
| bool(y) => Err(“not a number”) #cannot negate a bool value
end
end
end)
| val(x) =>
cases(Val) x:
| num(y) => Ok(num(y))
| bool(y) =>
if y == true: Ok(bool(true))
else if y == false: Ok(bool(false))
else: Err(“no boolean”)
end
end
| binexp(b, e1, e2) => err-bind(interp(s, e1), lam(k :: Val):
err-bind(interp(s, e2), lam(m :: Val):
cases(Binop) b:
| add => cases(Val) k:
| num(y) =>
cases(Val) m:
| num(l) =>
Ok(num(y + l))
| bool(l) =>
Err(“not a number”)
end
| bool(y) =>
Err(“not a number”)
end
| sub =>
cases(Val) k:
| num(y) =>
cases(Val) m:
| num(l) =>
Ok(num(y – l))
| bool(l) =>
Err(“not a number”)
end
| bool(y) =>
Err(“not a number”)
end
| mul =>
cases(Val) k:
| num(y) =>
cases(Val) m:
| num(l) =>
Ok(num(y * l))
| bool(l) =>
Err(“not a number”)
end
| bool(y) =>
Err(“not a number”)
end
| div => cases(Val) k:
| num(y) =>
cases(Val) m:
| num(l) =>
Ok(num(y / l))
| bool(l) =>
Err(“not a number”)
end
| bool(y) =>
Err(“not a number”)
end
end
end)
end)

| else => Err(“not implemented yet”) #Fill in the rest of the case analysis here
end
end

fun run(s :: String) -> Error :
err-bind(parse(s), lam(e): interp(init-state, e) end)
end

fun is-err (e :: Error ) -> Boolean:
cases(Error) e:
| Ok(_) => false
| Err(_) => true
end
end

# These tests provide evidence that your interpreter is working properly.

check “interp(…)”:
interp(init-state, ex1) is Ok(num(3))
interp(init-state, ex2) is Ok(num(100))
interp(init-state, ex3) is Ok(bool(true))
interp(init-state, ex4) is Ok(bool(false))
interp(init-state, ex5) is Ok(num(103))
interp(init-state, ex6) is Ok(num(-97))
interp(init-state, ex7) is Ok(num(300))
interp(init-state, ex8) is Ok(num(0.03))
interp(init-state, ex9) is Ok(num(0.0009))
interp(init-state, ex10) is Ok(num(30900))
interp(init-state, ex11) satisfies is-err
interp(init-state, ex20) is Ok(num(-100))
interp(init-state, ex21) is Ok(num(0))
interp(init-state, ex30) is Ok(num(3))
interp(init-state, ex31) satisfies is-err
interp(init-state, ex32) satisfies is-err
end

# These tests provide evidence that your parser and interpreter are both working properly.

check “run(…)”:
run(“3”) is Ok(num(3))
run(“true”) is Ok(bool(true))
run(“(* 3 4)”) is Ok(num(12))
run(“(let x 3 4)”) is Ok(num(4))
run(“(let x 3 (* x true))”) satisfies is-err
run(“(4 * 5)”) satisfies is-err
run(“(* true false)”) satisfies is-err
run(“(and true false)”) is Ok(bool(false))
run(“(or (or true false) false)”) is Ok(bool(true))
run(“(let x 5 (* x x))”) is Ok(num(25))
run(“(LET x 5 (* x x))”) satisfies is-err
run(“(let x 4 (let x 5 (* x x)))”) is Ok(num(25))
run(“(+ (let x 0 (+ x x)) 0)”) is Ok(num(0))
run(“(/ (let x 0 0) (let x 0 x))”) satisfies is-err
run(“(let x (let x (+ 3 4) x) (* x x))”) is Ok(num(49))
run(“(* x 4)”) satisfies is-err
#more tests to be added here
end