CS 3520 Homework 8

Due: Wednesday, October 30th, 2019 11:59pm

Difficulty:  ★★★☆

Part 1 — Boxes

Start with 5.rkt and add box, unbox, and box?:

  <Exp> = ...
        | {box <Exp>}
        | {unbox <Exp>}
        | {box? <Exp>}

The 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).

Examples:

  (reset!)
  (ntest (interpx (compile
                   (parse `{unbox {unbox {box {box 3}}}})
                   mt-env)
                  empty-env
                  (init-k))
         3)
  
  (reset!)
  (ntest (interpx (compile
                   (parse `{box? 3})
                   mt-env)
                  empty-env
                  (init-k))
         1)
  
  (reset!)
  (ntest (interpx (compile
                   (parse `{box? {box 3}})
                   mt-env)
                  empty-env
                  (init-k))
         0)
  
  (reset!)
  (ntest (interpx (compile
                   (parse `{box? {lambda {x} {box x}}})
                   mt-env)
                  empty-env
                  (init-k))
         1)
  
  (reset!)
  (ntest (interpx (compile
                   (parse
                    `{{lambda {mkrec}
                        {{{lambda {chain}
                            {lambda {unchain}
                              ;; Make a chain of boxes, then traverse
                              ;; them:
                              {{unchain 13} {chain 13}}}}
                          ;; Create recursive chain function:
                          {mkrec
                           {lambda {chain}
                             {lambda {n}
                               {if0 n
                                    1
                                    {box {chain {+ n -1}}}}}}}}
                         ;; Create recursive unchain function:
                         {mkrec
                          {lambda {unchain}
                            {lambda {n}
                              {lambda {b}
                                {if0 n
                                     b
                                     {unbox {{unchain {+ n -1}} b}}}}}}}}}
                      ;; mkrec:
                      {lambda {body-proc}
                        {{lambda {fX}
                           {fX fX}}
                         {lambda {fX}
                           {body-proc {lambda {x} {{fX fX} x}}}}}}})
                   mt-env)
                  empty-env
                  (init-k))
         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!)
  (ntest (interpx (compile
                   (parse `{{lambda {b}
                              {{lambda {z}
                                 {unbox b}}
                               {set-box! b {+ {unbox b} 1}}}}
                            {box 3}})
                   mt-env)
                  empty-env
                  (init-k))
         4)