CS 5510 Homework 6

Due: Monday, October 26th, 2009 9:40am

Part 1 – Improving Assignment

Start with bcfae.ss. In the starting program, the representation of the store grows every time that a box's content is modified with setbox. Change the implementation of setbox so that the old value of the box is dropped (i.e., replaced with the new value) instead of merely hidden by the outside-in search order of store-lookup.

Example:

  (test (interp (parse '{{fun {b}
                          {seqn
                           {setbox b 2}
                           {openbox b}}}
                         {newbox 1}})
                (mtSub)
                (mtSto))
        (v*s (numV 2)
             (aSto 1 (numV 2) (mtSto))))

Part 2 – Sequences

Generalize seqn to allow one or more sub-expressions, instead of exactly two sub-expressions.

  <BCFAE> = ...
          | {seqn <BCFAE> <BCFAE>*}

Example:

  (test (interp (parse '{{fun {b}
                          {seqn
                           {setbox b {+ 2 (openbox b}}}
                           {setbox b {+ 3 (openbox b}}}
                           {setbox b {+ 4 (openbox b}}}
                           {openbox b}}}
                         {newbox 1}})
                (mtSub)
                (mtSto))
        (v*s (numV 10)
             (aSto 1 (numV 10) (mtSto))))

Part 3 – Records

Add rec and get forms for records as in HW3, and also add a set form that modifies the value of a record field:

  <BCFAE> = ...
          | {rec {<id> <BCFAE>}*}
          | {get <BCFWAE> <id>}
          | {set <BCFWAE> <id> <BCFAE>}

A rec form allocates a new record. A get form accesses from the record produced by the sub-expression the value of the field named by the identifier. A set form changes within the record produced by the first sub-expression the value of the field named by the identifer; the value of the second sub-expression determines the field's new value, and that value is also the result of the set expression.

Also extend parse and define the usual interp-expr, which takes an expression and interprets it with an empty initial environment and empty initial store, and returns either a number, 'func, 'box, or 'record (without returning the store).

Examples:

  (test (interp-expr (parse '{{fun {r}
                                {get r x}}
                              {rec {x 1}}}))
        1)

  (test (interp-expr (parse '{{fun {r}
                                {seqn
                                  {set r x 5}
                                  {get r x}}}
                              {rec {x 1}}}))
        5)

  (test (interp-expr (parse '{{{{{fun {g}
                                   {fun {s}
                                     {fun {r1}
                                       {fun {r2}
                                         {+ {get r1 b}
                                            {seqn
                                              {{s r1} {g r2}}
                                              {+ {seqn
                                                   {{s r2} {g r1}}
                                                   {get r1 b}}
                                                 {get r2 b}}}}}}}}
                                 {fun {r} {get r a}}}            ; g
                                {fun {r} {fun {v} {set r b v}}}} ; s
                               {rec {a 0} {b 2}}}                ; r1
                              {rec {a 3} {b 4}}}))               ; r2
        5)