Skip to content

Latest commit

 

History

History
145 lines (101 loc) · 4.72 KB

3.md

File metadata and controls

145 lines (101 loc) · 4.72 KB
Raw

PA3: Garbage collection

In this assignment, you'll extend your Grumpy virtual machine to perform garbage collection.

                                                   /--------------\
                                                   |     GC       | <-- PA3
                                                   \--------------/
                                                         |||
                /-------------\                    /--------------\
<filename.s> => |    assem    | => <filename.o> => |     vm       | => program's result
                \-------------/                    \--------------/
                     ^| PA1                              ^| PA2

NOTE: This is a pair assignment like PA2.

  1. Only one partner need submit.
  2. Make sure your README contains both partners' names.

VM Revisited

Make sure your VM from the previous assignment is in working order. If you need help getting a working VM, contact Alex at [email protected].

Garbage Collection

Extend your VM from PA2 to perform copying garbage collection. Refer to Appel 13 and to the lecture notes if you forget exactly how copying collection works.

Your VM extended with copy garbage collection will have the same interface as your VM from PA2 except that it may additionally perform garbage collections during the execution of a program. In particular, it should:

  1. Accept the name of a GrumpyVM bytecode <filename.o> as its first command-line argument;
  2. Execute the file, possibly triggering one or more garbage collections;
  3. Print the program's result to stdout using the textual encoding described in PA2 (Vi32(-3) for the integer -3, etc.).

Steps 1 and 3 are performed by the provided template code, but you are responsible for step 2. To make it easy for us to test your garbage collector, we ask that you additionally follow these guidelines:

  1. Your VM should trigger a garbage collection exactly when the program attempts to Alloc an object that would not fit in the heap. For example, if the heap is occupied by 1000 of 1024 possible values (1024 values being the size of the heap as specified in PA2), and the program attempts to allocate an object of size 25 values, your VM must trigger a garbage collection.

  2. On each garbage collection, your VM must print to stderr (NOTE: not stdout!) exactly the following metadata:

GC start: heap_size = X values
GC end: heap_size = Y values

where X is the number of values in the heap right before the collection and Y is the number of values after.

  1. If your VM cannot complete an allocation even after a GC, your VM should exit with a nonzero error code (by throwing an error via Result<,> type). Make sure, in this case, that you've printed intermediate GC statistics to stderr as directed above (that is, those generated by GCs before your VM ran out of memory).

Testing

To test your solution, run your vm on one of the following four test cases:

tests/fact2.o
tests/heap.o
tests/heap2.o
tests/heap3.o

Example: The command:

> ./vm tests/heap3.o 2> gc-stats

should produce output:

Vi32(10)

on stdout.

The 2> redirects stderr to file gc-stats which should contain exactly the text:

GC start: heap_size = 1012 values
GC end: heap_size = 103 values

The program we used to generate tests/heap3.o was:

(fun f (x i32) -> i32
  (cond (== x (/ 3 1))
    3
    (seq (alloc 100 false) (f (- x 1)))))
    
(fun g (x i32) -> i32
  (let a (alloc 1 (alloc 100 10))
    (seq (f 15)
         (get (get a 0) 50))
    ))
%
(g 0)

You can decipher this program by reading the GrumpyIR Documentation.

An example program on which your garbage-collected VM should fail is tests/fact2.o. Try running:

> ./vm tests/fact2.o

Your VM should print to stderr the statistics:

GC start: heap_size = 1010 values
GC end: heap_size = 1010 values

but then immediately exit with a nonzero error code because the GC failed to free enough heap space to complete the allocation. Our VM produces:

> ./vm tests/fact2.o
> echo $?
101

The program that generated fact2.o was:

(fun fact (x i32) -> i32
  (let a (alloc 100 0) 
       (seq (set a 0 x)
            (let y (get a 0)
                   (cond (== 0 y) 1 (* y (fact (- y 1))))))))
%
(fact 12)

Submission

  1. To submit your project, commit to pa3-gc on or before the due date.
  2. Thoroughly test your code (we expect at least 3 unit tests)
  3. Submit the repo URL to Blackboard.

To begin the assignment, click on this link: https://classroom.github.com/a/bkcYNmHY

Pair Programming

You are permitted (though not required) to work with up to one other person on this assignment.