►Principles of Programming Languages
▼Assignments
•12 — Garbage Collection
7.7.0.3
    ← prev  up  next → 

12 — Garbage Collection

You may turn in your solution before the original due date. Due Tuesday, 14 April Thursday, 16 April, 6am

The purpose of this homework problem is to understand the principles of automatic memory management implementations.

Delivery Deliver your solutions in a folder called 12 in your github repo:

        

        12 /

           xdriverxrun

           Other/

           ITests/

             [0-9]-in.json

             [0-9]-out.json

A name ending in / is a folder, and indentation means “contained in the closest folder listed above the current name.”

Programming Task

Step 0 Repair your CESK implementation so that your mutator works properly.

Note You may modify your mutator in place and link to it from your directory for this homework.

Step 1 Design the program find_roots, which determines all locations in the C, E, and K registers.

Step 2 Design a heap data structure that is parameterized over the size of the finite store implementations. Note If your programming language does not have finite arrays, limit the size of the store programmatically.

Step 3 Design a garbage collector for your CESK machine.

Note A student asked how many store locations an array may consume. To be on the safe side, assume an array of size n may consume n + 2 locations.

Testing Task Write the test harness xrun. Its job is to run the CESK machine on programs delivered via STDIN and to produce the result of the run to SDTOUT.

Create ten tests for xrun. Place them in ITests/. A test consists of two files: N-in.json and N-out.json for N in [0 .. 9]:

  • An input file in ITests contains a single JSON object with two fields: "space" and "program". The first one specifies the size of the heap with a positive JSON integer. The second one specifies a While program. Here is a simplistic example:

          

          {"space" : 12,

           "program" :

            [["vec", "x", "=", [1, 2, 3]],

             "in",

             [ ["x", 0], "=", [ ["x", 1], "+", 42] ],

             ["x", 0] ] }

          

  • An output file in ITests contains the same kinds of results as your test harness for 11 — CESK plus the error message out of space.

Recall JSON: Simplicity and Complexity.

    ← prev  up  next →