CS 136 Tutorials - Spring 2007

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.


Last modified on Friday, 19 August 2011, at 18:05 hours.