Regions and Memory Management

There are a wide variety of algorithms to chose from when implementing garbage collection for a speci?c language. In this problem, we examine one algorithm for ?nding garbage in pure Lisp (Lisp without side effects) based on the concept of regions. Generally speaking, a region is a section of the program text. To make things simple, we consider each function as a separate region. Region-based collection reclaims garbage each time program execution leaves a region. Because we are treating functions as regions in this problems, our version of region-based collection will try to ?nd garbage each time a program returns from a function call.

(a) Here is a simple idea for region-based garbage collection:

When a function exits, free all the memory that was allocated during execu- tion of the function.

However, this is not correct as some memory locations that are freed may still be accessible to the program. Explain the ?aw by describing a program that could possibly access a previously freed piece of memory. You do not need to write more than four or ?ve sentences; just explain the aspects of an example program that are relevant to the   question.

(b) Fix the method in part (a) to work correctly. It is not necessary for your method to ?nd all garbage, but the locations that are freed should really be garbage. Your answer should be in the following form:

When a function exits, free all memory allocated by the function except....

Justify your answer. (Hint: Your statement should not be more than a sentence or two. Your justi?cation should be a short paragraph.)

(c) Now assume that you have an correctly functioning region-based garbage col- lector. Does your region-based collector have any advantages or disadvantages over a simple mark-and-sweep collector?

(d) Could a region-based collector like the one described in this problem work for impure Lisp? If you think the problem is more complicated for impure Lisp, brie?y explain why. You may consider the problem for C instead of for impure Lisp if you like, but do not give an answer that depends on speci?c properties of C such as pointer arithmetic. The point of this question is to ex- plore the relationship between side effects and a simple form of region-based collection.