CS 5510 Homework 8

Due: Thursday, November 3rd, 2011 10:45am

Part 1 – Stepping through Evaluation

Assuming the fae-k.rkt interpreter, show how the following expression would evaluate when parsed and starting with an empty substitution and continuation:

   {{fun {f} {- {f 1} 3}}
    {fun {x} {+ x x}}}

Show how it would evaluate by writing down each call to interp and continue that will happen, including all of the arguments. When showing FAEs, write them in concrete syntax (as if they are implicitly wrapped by parse) instead of FAE instances. Feel free to define use abbreviations.

There will be 11 calls to interp and 9 calls to continue.

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

As an example, if the expression were the simpler

 {{fun {x} x} 2}

then the trace would be 7 steps total:

  interp expr = {{fun {x} x} 2}
         ds   = (mtSub)
         k    = (mtK)
  
  interp expr = {fun {x} x}
         ds   = (mtSub)
         k    = (appArgK 2 (mtSub) (mtK))
  
  continue k  = (appArgK 2 (mtSub) (mtK))
           v  = (closureV 'x x (mtSub))
  
  interp expr = 2
         ds   = (mtSub)
         k    = (doAppK (closureV 'x x (mtSub)) (mtK))
  
  continue k  = (doAppK (closureV 'x x (mtSub)) (mtK))
           v  = (numV 2)
  
  interp expr = x
         ds   = (aSub 'x (numV 2) (mtSub))
         k    = (mtK)
  
  continue k  = (mtK)
           v  = (numV 2)

Of course, you could get the answer by tracing interp and continue to show arguments and results. Do not run interp on the expression for you assignment, though, until you are ready to check your answer.

Part 2 – Simulating Garbage Collection

Suppose a garbage-collected interepreter uses the following three kinds of records:

• Tag 1: a record containing two pointers
• Tag 2: a record containing one integer and one pointer
• Tag 3: a record containing two integers

The interpreter has one register, which always contains a pointer, and a memory pool of size 30. The allocator/collector is a two-space copying collector, so each space is of size 15. Records are allocated consecutively in to-space, starting from the first memory location, 0.

The following is a snapshot of memory just before a collection where all memory has been allocated:

• Register: 6
• To space: 1 0 9 1 3 0 2 8 0 3 1 1 3 7 7

What are the values in the register and the new to-space (which is also addressed starting from 0) after collection? Assume that unallocated memory in to-space contains 0.