CS 5510 Homework 5

Due: Thursday, October 6th, 2011 10:45am

Part 1 – Improving Assignment

Start with bcfae.rkt. 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

Extend the interpreter to support the construction of records with named fields, and to support field selection from a record:

  <BCFAE> = ...
          | {record {<id> <BCFAE>}*}
          | {get <BCFAE> <id>}

Adding records means that the language now has four kinds of values: numbers, functions, boxes, and records. At run-time, an error may occur because a record is misused as a number or function, a number or function is supplied to get, or a record supplied to get does not have the named field, and so on. Your error message for the last case should include the words "no such field", otherwise you can make up your own error messages (or just let primitive error checking handle problems, such as trying to add a record to a number).

Expressions within a record form should be evaluated when the record form itself is evaluated. For example,

  {{fun {b}
     {{fun {r}
        {seqn
         {setbox b 1}
         {get r a}}}
      {record {a {openbox b}}}}}
   {newbox 0}}

should produce 0, not 1, because {openbox b} is evaluated when the record expression is evaluated, not when the get expression is evaluated.

For homework purposes, we don't want to nail down the representation of a record value, because there are many choices. The examples below therefore use interp-expr, which you should define as a wrapper on interp that takes just an BCFAE and produces just a number if interp produces a number, the symbol 'function if interp produces a closure, the symbol 'box if interp produces a box, or the symbol 'record if interp produces a record value.

Examples:

  (test (interp-expr (parse '{record {a 10} {b {+ 1 2}}}))
        'record)
  (test (interp-expr (parse '{get {record {a 10} {b {+ 1 2}}} b}))
        3)
  (test/exn (interp-expr (parse '{get {record {a 10}} b})))
            "no such field")
  (test (interp-expr (parse '{get {record {r {record {z 0}}}} r}))
        'record)
  (test (interp-expr (parse '{get {get {record {r {record {z 0}}}} r} z}))
        0)

Part 4 – Mutable Records

Add a set form that modifies the value of a record field:

  <BCFAE> = ...
          | {set <BCFAE> <id> <BCFAE>}

Evaluation of a record expression allocates a location for each of its fields. A get expression accesses from the record produced by the sub-expression the value in the location of the field named by the identifier. A set form changes the value in the location for a field; the value of the second sub-expression inset determines the field's new value, and that value is also the result of the set expression.

Examples:

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

  (test (interp-expr (parse '{{fun {r}
                                {seqn
                                  {set r x 5}
                                  {get r x}}}
                              {record {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
                               {record {a 0} {b 2}}}             ; r1
                              {record {a 3} {b 4}}}))            ; r2
        5)