Due: Friday, October 20th, 2023 11:59pm
Difficulty: ★★☆☆
Start with more_lazy.rhm.
Implement an interpreter with lazy evaluation and the following grammar:
<Exp> = <Number>
| <Symbol>
| <Exp> + <Exp>
| <Exp> * <Exp>
| fun (<Symbol>): <Exp>
| <Exp>(<Exp>)
| let <Symbol> = <Exp>: <Exp>
| (<Exp>)
| if <Exp> == 0 | <Exp> | <Exp>
| pair(<Exp>, <Exp>)
| fst(<Exp>)
| snd(<Exp>)That is, a language with single-argument functions and application, an if-zero conditional, and pair, fst, and snd operations. (The language does not include recursive bindings or records.) Unlike cons, the pair operation does not require its second argument to be a list (and we do not have an empty-list value, anyway). The if form has weakest precedence. The pair, fst, and snd forms have a precedence like function calls, but should be preferred by the parser over a function-call form, so they can be matched just before a function-call form in parse.
Implement your interpreter with the eager Shplait language, not a lazy language.
Evaluation of the interpreted langauge must be lazy. In particular, if a function never uses the value of an argument, then the argument expression should not be evaluated. Similarly, if the first or second part of a pair is never needed, then the first or second expression should not be evaluated. Even if the first or second part of a particular pair is used multiple times, the expression to compute the first or second part should be evaluated only once.
From the starting code, expand the parse function to support the new forms: if, pair, fst, and snd. Also, as in HW 4, provide an interp_expr function; the interp_expr wrapper for interp should take an expression and return either a number syntax object, 'function' for a function result, or 'pair' for a pair result. (Meanwhile, the interp function should never return the syntax object 'pair', just like the starting interp function never returns the syntax object 'function'.) Note that pair results must be distinct from function results, so you will need to modify interp and not just use encodings via parse.
check: interp_expr(parse('10'))
~is '10'
check: interp_expr(parse('10 + 17'))
~is '27'
check: interp_expr(parse('10 * 7'))
~is '70'
check: interp_expr(parse('(fun (x): x + 12)(1 + 17)'))
~is '30'
check: interp_expr(parse('let x = 0:
let f = (fun (y): x + y):
f(1) + (let x = 3:
f(2))'))
~is '3'
check: interp_expr(parse('if 0 == 0 | 1 | 2'))
~is '1'
check: interp_expr(parse('if 1 == 0 | 1 | 2'))
~is '2'
check: interp_expr(parse('pair(1, 2)'))
~is 'pair'
check: interp_expr(parse('fst(pair(1, 2))'))
~is '1'
check: interp_expr(parse('snd(pair(1, 2))'))
~is '2'
check: interp_expr(parse('let p = pair(1, 2):
fst(p) + snd(p)'))
~is '3'
check: interp_expr(parse('let f = (fun (x):
pair(x, x)):
fst(f(3)) + snd(f(4))'))
~is '7'
// Lazy evaluation:
check: interp_expr(parse('(fun (x): 0)(1 + (fun (y): y))'))
~is '0'
check: interp_expr(parse('let x = (1 + (fun (y): y)):
0'))
~is '0'
check: interp_expr(parse('fst(pair(3,
1 + (fun (y): y)))'))
~is '3'
check: interp_expr(parse('snd(pair(1 + (fun (y): y),
4))'))
~is '4'
check: interp_expr(parse('fst(pair(5,
// Infinite loop:
(fun (x): x(x))(fun (x): x(x))))'))
~is '5'
check: interp_expr(
parse(
// Use call-by-name mkrec, which
// is simpler than call-by-value:
'let mkrec = (fun (body_proc):
let fX = (fun (fX):
body_proc(fX(fX))):
fX(fX)):
let fib = mkrec(fun (fib):
// Fib:
fun (n):
if n == 0
| 1
| if (n + -1) == 0
| 1
| fib(n + -1) + fib(n + -2)):
// Call fib on 4:
fib(4)'
)
)
~is '5'
check: interp_expr(
parse(
// Use call-by-name mkrec, which
// is simpler than call-by-value:
'let mkrec = (fun (body_proc):
let fX = (fun (fX):
body_proc(fX(fX))):
fX(fX)):
let nats_from = mkrec(fun (nats_from):
// nats-from:
fun (n):
pair(n, nats_from(n + 1))):
let list_ref = mkrec(fun (list_ref):
// list_ref:
fun (n):
fun (l):
if n == 0
| fst(l)
| list_ref(n + -1)(snd(l))):
// Call list-ref on infinite list:
list_ref(4)(nats_from(2))'
)
)
~is '6'There’s no new implementation for this part. Just make sure that your interpreter is able to run the following two tests within a few seconds. If it takes tens of seconds or even more than a minute, then your interpreter is not lazy enough—probably because it re-interps the expression for a pair’s first or second part every time the first or second part is accessed, which turns the linear-time program into a quadratic-time program.
The handin server will not run this test, but we will check your implementation against this test when grading. It must produce the right answer within a few seconds.
check: interp_expr(
parse(
'let mkrec = (fun (body_proc):
let fX = (fun (fX):
body_proc(fX(fX))):
fX(fX)):
let nats_to = mkrec(fun (nats_to):
fun (n):
if n == 0
| pair(0, 0)
| let l = nats_to(n + -1):
pair(fst(l) + 1,
l)):
let sum = mkrec(fun (sum):
fun (n):
fun (l):
if n == 0
| 0
| fst(l) + sum(n + -1)(snd(l))):
sum(10000)(nats_to(10000))'
)
)
~is '50005000'
check: interp_expr(
parse(
'let mkrec = (fun (body_proc):
let fX = (fun (fX):
body_proc(fX(fX))):
fX(fX)):
let nats_to = mkrec(fun (nats_to):
fun (n):
if n == 0
| pair(0, 0)
| let l = nats_to(n + -1):
pair(l,
snd(l) + 1)):
let sum = mkrec(fun (sum):
fun (n):
fun (l):
if n == 0
| 0
| snd(l) + sum(n + -1)(fst(l))):
sum(10000)(nats_to(10000))'
)
)
~is '50005000'
| Last update: Thursday, November 9th, 2023mflatt@cs.utah.edu |