Homework #10: Marking the heap
Out: Friday, March 29th, Due: Friday, April 5th, 5:00pm

Many garbage collection algorithms start with a marking phase where they traverse the heap and find which objects which are reachable from some set of roots. Examples of roots include global variables and local variables in the current environment. In this assignment you will write a simple simulation of marking a heap.

The language for this homework is:

#lang plait


Some general hints:
  1. In addition to lists, this assignment uses vectors, and sets. The following functions may be useful: set-add, set-member?, set-union, vector-ref, where the set data structure are those we developed in Tutorial 7.
  2. One of the points of this assignment is to solve a not completely trivial problem without using mutation. A natural technique is to pass an extra parameter and provide an updated version of a value to recursive calls (i.e. like we do for tail recursion).
  3. Probably the easiest way to traverse the heap is [Depth First Search](https://en.wikipedia.org/wiki/Depth-first_search)
  4. In order to track which objects have been discovered you probably need to define one or more helper functions with an extra parameter of a set/list/vector of known objects.


The steps below give you the skeleton of the assignment (that you are required to use).
  1. Use the following type declarations to define an abstract representation of a heap. Each heap location either has a list of indices (locations of referenced objects) or is a primitive value.
    (define-type Object
      [object (refs : (Listof Number))]
    (define-type-alias Heap (Vectorof Object))
    (define-type-alias LocSet (Setof Number))
  2. Write a function search-one-root that searches the heap for a single root. Your function should have the following type.
    (has-type search-one-root : (Number Heap -> LocSet))
  3. Here is some test data and tests for search-one-root
    (define heap1
       (object (list 1 2))
       (object (list 2))))
    (define heap2
       (object (list 0 1))
       (object (list 2))
       (object (list 0))))
    (test (search-one-root 0 heap1) (set 0 1 2))
    (test (search-one-root 1 heap1) (set 1))
    (test (search-one-root 0 heap2) (set 0 1 2))
    (test (search-one-root 1 heap2) (set 0 1 2))
  4. Write a function find-live with the following type signature
    (has-type find-live : ((Listof Number) Heap -> LocSet))
    The purpose of find-live is to find the locations of all objects reachable from a given set of roots. Here are some tests for find-live
    (test (find-live '(1) heap1) (set 1))
    (test (find-live '(0) heap1) (set 0 1 2))
    (test (find-live '(1 2) heap2) (set 0 1 2))
  5. As always, make sure you have enough tests for your code. The automated coverage testing is a minimal requirement.
  6. Finally, define minutes-spent as usual.