Due: Wednesday, November 8th, 2023 11:59pm
Difficulty: ★★★☆
Your solution will start with 5.rhm. However, you should think of an addition to 5.rhm as being a translation of an addition to lambda_k.rhm. So, it’s a good idea to first implement part 1 in lambda_k.rhm, and then translate to 5.rhm.
Start with and add box, unbox, and is_box:
<Exp> = .... | box(<Exp>) | unbox(<Exp>) | is_box(<Exp>)
The is_box form returns 0 if the result of its argument expression is a box, 1 if it’s not a box. Even so, your interpreter can assume that the argument to unbox is always a box (which is consistent with other forms in the initial interpreter, such as the way that + assumes that its arguments are numbers).
Test coverage: To achieve test coverage, you are allowed to simply comment out the error cases in move and update, since triggering those requires extreme measures. If you need a program that runs out of memory, you can use the Moe program let f = (fun (f): 1 + f(f)): f(f).
Examples:
reset() N check: interpx(compile(parse('unbox(unbox(box(box(3))))'), mt_env), empty_env, init_k()) ~is 3 reset() N check: interpx(compile(parse('is_box(3)'), mt_env), empty_env, init_k()) ~is 1 reset() N check: interpx(compile(parse('is_box(box(3))'), mt_env), empty_env, init_k()) ~is 0 reset() N check: interpx(compile(parse('is_box(fun (x): box(x))'), mt_env), empty_env, init_k()) ~is 1 reset() N check: interpx(compile( parse( 'let mkrec = (fun (body_proc): (fun (fX): fX(fX))(fun (fX): body_proc(fun (x): fX(fX)(x)))): let chain = mkrec(fun (chain): fun (n): if n == 0 | 1 | box(chain(n + -1))): let unchain = mkrec(fun (unchain): fun (n): fun (b): if n == 0 | b | unchain(n + -1)(unbox(b))): // Make a chain of boxes, then traverse them: unchain(13)(chain(13))' ), mt_env), empty_env, init_k()) ~is 1
CS 3520 and CS 6520 students can complete this exercise for extra credit, but it is not required.
Add set_box:
<Exp> = .... | set_box(<Exp>, <Exp>)
You can make set_box return whatever you like, and your interpreter can assume that the first argument to set_box is always a box.
reset() N check: interpx(compile(parse('let b = box(3): let dummy = set_box(b, 4): unbox(b)'), mt_env), empty_env, init_k()) ~is 4 reset() N check: interpx( compile( parse( 'let mkrec = (fun (body_proc): (fun (fX): fX(fX))(fun (fX): body_proc(fun (x): fX(fX)(x)))): let chain = mkrec(fun (chain): fun (n): if n == 0 | 1 | box(chain(n + -1))): // Make a chain of boxes in a box: let bx = box(chain(13)): let unchain = mkrec( fun (unchain): fun (n): if n == 0 | unbox(bx) | let dummy = set_box(bx, unbox(unbox(bx))): unchain(n + -1)): // Walk through the chain of boxes, but pass the box // argument in `bx` instead of as a regular argument unchain(13)' ), mt_env), empty_env, init_k()) ~is 1
Last update: Thursday, November 9th, 2023mflatt@cs.utah.edu |