notes.org 2.0 KB
5.3 Storage Allocation & Garbage Collection
we'll assume that our register machine is equipped with a list-structured memory
this is useful but not realistic
we will look at how it's implemented. how do we represent the "box-and-pointer" structure of lisp pairs using the storage and addressing of typical computing machines.
there are two considerations:
-
how to represent it
-
how to manage memory as computation continues
lisp will be constantly creating new data objects, not all computers have infinite memory. therefore lisp has automatic storage allocation. in this case, garbage collection.
5.3.1 memory as vectors
conventional computer memory can be thought of as an array of cubbyholes. each cubby has a unique name–its address. memory systems offer two functions:
-
one that fetches data from some location
-
one that assigns new data to some location
there must be some way to treat memory itself as data. the list structure is one technique of address arithmetic.
we will model memory as a VECTOR
a vector is a compound data object with elements that can be accessed by an integer index in constant time
(vector-ref vector n) (vector-set! vector n value)
we will imagine computer memory is divided up into two vectors, the-cars and the-cdrs
there also must be some way to deal with primitive data, and a way to identify its type. for this, we tag pointers with the datum's type.
two objects are (eq?) if they have the same pointer
character strings are stored in the obarray, where each string is stored only once.
5.3.2 maintaining the illusion of infinite memory
5.3.1 solves the implementation of list structure… if we have infinite memory!
the technique of garbage collection used here is "stop-and-copy"
it shifts memory back and forth between working memory and free memory, copying the useful stuff to free memory and leaving the crap behind in what is now the old working memory
abandoned objects are tagged with a "broken heart"