CS 2420-20 Homework 19

Due: Tuesday, April 3rd, 2012 9:10am

Part 0 – Two-Space 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 pointer and one integer
• Tag 3: a record containing one integer

The interpreter has one register, which always contains a pointer, and a memory pool of size 22. The allocator/collector is a two-space copying collector, so each space is of size 11. 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: 8
• To space: 1 3 8 3 0 2 3 7 2 0 8

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.

Handin your answer as gc.txt.

Part 1 – Testing Numbers

As usual...

Start with miniracket6.zip.

Add support for booleans as values and expressions, and also add an iszero form that has a single sub-expression.

Part 2 – Adding Conditionals

Add an if form to the language.

Handin your revised main.c (for new tests), eval.c, print.c, struct.c, struct.h, continue.c, continue.h, and gc.c.

Here’s an example from recent homework solutions that you might use to test your additions:

  symbol* fib = make_symbol("fib");
  tagged* fib_var = (tagged*)fib;
  tagged *fib_func
    = make_func(n,
                make_branch(make_iszero(n_var),
                            one,
                            make_branch(make_iszero(make_minus(n_var, one)),
                                        one,
                                        make_plus(make_app(fib_var,
                                                           make_minus(n_var,
                                                                      one)),
                                                  make_app(fib_var,
                                                           make_minus(n_var,
                                                                      two))))),
                NULL);
  
  hash_table* fib_d = make_dict();
  
  hash_set(fib_d, fib, fib_func);
  
  check_num_val(eval(make_app(fib_var, make_num(6)), NULL, fib_d),
                13);