CS 5510 Homework 8

Due: Friday, October 29th, 2010 11:59pm

Stepping through Evaluation

Using the BCFAE interpreter show how the following expression would evaluate when parsed and starting with an empty substitution and store:

   {{fun {b}
         {seqn
           {setbox b {newbox 5}}
           {openbox {openbox b}}}}
     {newbox 2}}

Show how it would evaluate by writing down each call to interp that will happen, including the arguments. For each call, show the result that it produces — which may be after nested calls to interp.

You can use the following abbreviations:

There will be 12 calls to interp.

Use DrRacket to handin a plain text file for your answer.

As an example, if the expression were

 {{fun {b} b}
  {newbox 2}}

then the trace would be 5 steps:

  eval expr = (parse '{{fun {b} b} {newbox 2}})
       ds   = (mtSub)
       st   = (mtSto)

  . eval expr = (parse '{fun {b} b})
         ds   = (mtSub)
         st   = (mtSto)

  . result = (v*s (closureV 'b (parse 'b)) (mtSto))

  . eval expr = (parse '{newbox 2})
         ds   = (mtSub)
         st   = (mtSto)

  .. eval expr = (parse '2)
          ds   = (mtSub)
          st   = (mtSto)

  .. result = (v*s (numV 2) (mtSto))

  . result = (v*s (boxV 1) (aSto 1 (numV 2) (mtSto)))

  . eval expr = (parse 'b)
         ds   = (aSub 'b (boxV 1) (mtSub))
         st   = (aSto 1 (numV 2) (mtSto)) = S_1

  . result = (v*s (boxV 1) S_1)
  
  result = (v*s (boxV 1) S_1)

where the leading dots show nesting to help you connect calls to interp with their results.

Of course, you could get the answer by adding printing commands to interp to show arguments and results. In fact, the trace library function can do that for you (although it currently prints argument values in a strange way):

 (require racket/trace)
 (trace interp)
 (interp (parse '{{fun {b} b} {newbox 2}}) (mtSub) (mtSto))

Do not run interp on the expression for you assignment, though, until you are ready to check your answer.