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).
baby-heap% class
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.
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).
set! operation to
the baby-heap% class?
baby-heap% class? Why can DrScheme do this?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.