Implementing the 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.