CS 136 Tutorials - Spring 2007

Tutorial 6: Simulating Computer Memory (June 8)

In today's tutorial, we will simulate the heap part of a computer's memory in Scheme. This will be done using PLT Scheme's object/class system and the new concept of vectors. Then we will use this object to convince ourselves that append! is more space-efficient than append. The new concepts in this tutorial come from lecture module 6 (see Handouts).

  1. Implementing the baby-heap% class
  2. Recall from lecture that the part of memory called the "heap" can be thought of as an array of numbered blocks, each of which may or may not contain some information. The number of some block is the address of that block in memory, and we usually store information on the type of data stored in some block in the block that immediately precedes it.

    To simulate this construct, we will create the class baby-heap%. Our heap will be simpler in the fact that it will only contain two types of data: numbers and cons pairs. The class has one initialization variable, size, which indicates the size of our memory (i.e. the total number of blocks). The block of memory itself will be represented by a vector called memory. We will also need a single integer, next-free which specifies the address of the next free (i.e. uninitialized) block in memory.

    We will also have a private struct, mem-loc, with just one field, address. This will be the return type for many operations, and will allow us (and the user) to distinguish between a number and an address to the memory of a specific baby-heap% object.

    The baby-heap% class should support the following operations:

    • empty?: mem-loc → true/false
    • num?: mem-loc → true/false
    • cons?: mem-loc → true/false
    • empty: → mem-loc
    • make-num: number → mem-loc
    • cons: mem-loc mem-loc → mem-loc
    • get-num: mem-loc → number
    • first: mem-loc → mem-loc
    • rest: mem-loc → mem-loc
    • set-first!: mem-loc mem-loc →
    • set-rest!: mem-loc mem-loc →

    Most of these should be self-explanatory; they work the same as the normal Scheme functions we know and love, only within the framework of our own memory block. Possible exceptions are make-num and get-num. The former consumes a number, allocates some memory for that number, and returns the address of that number in the heap. The latter takes an address and returns the number that's stored in that location.

    As an illustration of how the class should work, take the following function, which computes the length of a list stored in a given baby-heap% object:

    ;bheap-length: baby-heap mem-loc -> number
    (define (bheap-length bheap lst)
      (cond [(send bheap empty? lst) 0]
            [else (add1 (bheap-length bheap
                                      (send bheap rest lst)))]))
    (define bh (make-object baby-heap% 1024))
    (define example-list
      (send bh cons (send bh make-num 1)
                    (send bh cons (send bh make-num 2)
                                  (send bh cons (send bh make-num 3)
                                                (send bh empty)))))
    (bheap-length bh example-list) ; returns 3
    (send bh set-rest! example-list (send bh empty))
    (bheap-length bh example-list) ; returns 1

    Implement the baby-heap% class.

  3. Testing memory usage
    • Write two functions, bheap-append and bheap-append!, each of which takes a baby-heap% object and two lists in that heap, and takes the appropriate action analogous to the normal Scheme functions.

    • Show that bheap-append! is more memory-efficient than bheap-append. To do this, set up two different baby-heap% objects of the same size, and in each one make two lists of the same size. Then show that calling append! in the first environment succeeds, while append in the other environment generates an out-of-memory error (you have to choose the sizes of everything cleverly).

  4. Philosophical Questions
    • Why wouldn't it make sense to add a set! operation to the baby-heap% class?
    • Why would it be impossible to write a garbage collector within the baby-heap% class? Why can DrScheme do this?
    • What are the equivalent functions to make-num amd get-num in normal Scheme? Why did we have to write these?

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