De?nition of Garbage

This question asks you to think about garbage collection in Lisp and compare our de?nition of garbage in the text to the one given in McCarthy's 1960 paper on Lisp. McCarthy's de?nition is written for Lisp speci?cally, whereas our de?nition is stated generally for any programming language. Answer the question by comparing the de?nitions as they apply to Lisp only. Here are the two de?nitions.

Garbage, our de?nition: At a given point in the execution of a program P, a memory location m is garbage if no continued execution of P from this point can access location m.

Garbage, McCarthy's de?nition: "Each register that is accessible to the program is accessible because it can be reached from one or more of the base registers by a chain of car and cdr operations. When the contents of a base register are changed, it may happen that the register to which the base register formerly pointed cannot be reached by a car-cdr chain from any base register. Such a register may be considered abandoned by the program because its contents can no longer be found by any possible program."

(a) If a memory location is garbage according to our de?nition, is it necessarily garbage according to McCarthy's de?nition? Explain why or why not.

(b) If a location is garbage according to McCarthy's de?nition, is it garbage by our de?nition? Explain why or why not.

(c) There are garbage collectors that collect everything that is garbage according to McCarthy's de?nition. Would it be possible to write a garbage collector to collect everything that is garbage according to our de?nition? Explain why or why not.