COS 320, Spring 2000. Programming Assignment

Programming Assignment 5: Garbage Collection

In this assignment you will create a copying garbage collector for a modified version of the Fun language interpreter. 

Type checking

  1. Copy /u/cos320/chap5/* and /u/cos320/chap5/*/* into a new directory as5.  (The code has been rearranged to put a big chunk of code in the subdirectory called fun and the subdirectory called tests.  Make sure you copy everything.)
  2. If you have your own working copies of the parser, lexer, etc from assignments 2, 3 and 4 you may use them for this assignment.  If you don't have working versions, then use the ones we provide.
  3. Your main job is to implement memory management for the Fun language interpreter.  The interpreter is substantially more complicated than what you have seen before because it now operates using an explicit machine memory.  The machine memory has several parts, each of which corresponds to the real memory you would find in a machine.  You will want to look through the interfaces to these files and understand how they work.  Part of the assignment is to understand the new interpreter well enough so that you will be able to extend it with garbage collection.
  4. As usual, compile by invoking CM.make();.
  5. You can test your code by running Interp.test "".
  6. Submit by running submit 5 <all files>.
  7. Additional challenge:  a garbage collector operates when there is no space left to use.  Therefore, in principle, your gc function should run in a constant amount of space.  ML is not a particularly good language when it comes to writing constant-space programs (which is why garbage collectors are always written in C --- ah ha, so C is good for something!).  Try to write your garbage collector so it operates in constant space.  I will not give you extra credit for this one because it is not too hard.
  8. Extra credit:  instead of a simple to-space/from-space collector, write a generational collector with two generations, each of which does copying collection.  Make sure to implement the write barrier properly.  This may take substantial modification to the basic infrastructure.  I have not done it yet.  I don't know!  Note:  We will record any extra credit separately from the rest of the grades.  In the end, it may help boost your grade a notch if you are on the borderline, or it might not.