Solutions to Tutorial 6
"Philosophical Questions"
In tutorial 6, we simulated a computer's heap memory
with a Scheme class baby-heap%. The third part of the tutorial
posed some "philosophical questions" to test your understanding of the
underlying concepts.
Here are some discussions on those questions. Of course these
are not the only correct answers, and in fact I probably haven't
explained everything as clearly as possible. If you have more questions, or
you don't understand something here, you are encouraged to attend consulting
hours with the tutor or office hours with the professor.
- Why wouldn't it make sense to add a
set! operation to
the baby-heap% class?
In Scheme, we can only call set! on variable names, not memory
locations. This is why, for example, it is impossible to write a
make-empty! method which consumes a list and modifies that list
to be the empty list. (For more on this, see e.g. the section on writing
remove-odds! in
Tutorial 2.)
Since our baby-heap% class only contains memory locations for
cons pairs and for numbers, there is no notion of variable names within the
class. So there are no variable names to set!!
- Why would it be impossible to write a garbage collector within the
baby-heap% class? Why can DrScheme do this?
In order to write a garbage collector, we have to be able to tell first of
all what is "garbage" and what isn't. Since a piece of memory is
considered "garbage" whenever it is no longer reachable, this would involve
knowing all the memory addresses pointed to by any active variable in the
environment. But (again), since we have no notion of variables within the
baby-heap% class, there is no way of determining what memory
locations in our heap are still reachable and which ones aren't. So it would be
impossible to write a garbage collector from within the baby-heap%
class.
- What are the equivalent functions to
make-num
amd get-num in normal Scheme? Why did we have to write these?
Of course there are no equivalents to these functions in Scheme. The reason
we had to write them for our baby-heap% class has to do with the
basic question of what is a number in Scheme. When we write anything in
Scheme, whether it be a number like "5.2", a symbol, a string, or even a cons
pair, we are really asking Scheme to allocate that object in memory (if it isn't
there already), and then internally the Scheme interpreter uses a pointer
into the relevant memory location to store the number/symbol/etc. that we
typed in.
In our baby-heap% class, we were essentially working at a
"lower level" than we normally do in Scheme, by actually using memory addresses
to represent numbers, rather than handling all this internally somehow. This is
the reason for the need to
explicitly convert between numbers and memory addresses with
the make-num and get-num functions. The point is that,
in regular Scheme, these two function calls are essentially being made each time
we use a number, but it's all handled "behind the scenes" so we don't have to
worry about it.
|