CS 3520 Homework 8

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.

Part 1 — Boxes

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

Part 2 — Extra Credit: Box Assignment

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