CS 136 Tutorials - Spring 2007

Tutorials »

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:

    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
  4. Philosophical Questions

Last modified on Wednesday, 09 January 2019, at 14:31 hours.