|#
#| 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
data Parser
| mkParser(f :: (State -> {State; Error
end
fun run-parser
cases(Parser) p:
| mkParser(f) => f(init)
end
end
fun ret
mkParser(lam(s): {s; Ok(t)} end)
end
fun bind
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
mkParser(lam(s): {s; Err(msg)} end)
end
fun get
mkParser(lam(s): {s; Ok(s)} end)
end
fun set-state
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
bind(p1, lam(_): p2 end)
end
fun either
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
mkParser(lam(s): {s; Ok(tt)} end)
end
fun star
either(bind(p, lam(_): star(p) end), succeed())
end
fun plus
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
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
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
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
Reviews
There are no reviews yet.