Samenvatting hoofdstuk 6: Automatisch Geheugenbeheer

Hoofdstuk 6: automatisch
geheugenbeheer
1 Motivatie
• Registermachines: beperkt aantal registers (= geheugen)
o Normaal: cons, lijsten … → passen niet in registers → bovenop registers ook een
blikje RAM gebruiken
▪ Eindig: efficiënt mee omspringen en dingen die de rest van het programma
niet meer kunnen beïnvloeden, opruimen
▪ Stukjes geheugen die niet meer nodig zijn vrijmaken
➢ Verschillende algoritmes voor: “Stop en copy”

2 Van lijst-gebaseerd naar fysiek geheugen




• Geheugenmodel van Scheme omvormen naar geheugenmodel computer = reeks individueel
adresseerbare cellen
• Pointer = variabele met als waarde het adres van een geheugencel
• The-cars en the-cdrs staan hier onder elkaar maar staan in het echt gewoon naast elkaar
• Getypeerde pointers want we gebruiken een aantal bits van de pointer om een type bij te
houden.

1

, 2.1 Waarden voorstellen als getypeerde pointers




(define BIAS 1000)
(define NMBR-prefix 1)
(define PAIR-prefix 2)
(define NULL-prefix 3)
(define MASK-prefix 4)

(define NMBR (* NMBR-prefix BIAS))
(define PAIR (* PAIR-prefix BIAS))
(define NULL (* NULL-prefix BIAS))
(define MASK (* MASK-prefix BIAS))

(define (PREFIX val)
(quotient (abs val) BIAS))

(define (VALUE val)
(remainder (abs val) BIAS))

(define (MAKE prefix val)
(+ prefix val))

(define (number? val)
(eq? (PREFIX val) NMBR-prefix))

(define (pair? val)
(eq? (PREFIX val) PAIR-prefix))

(define (null? val)
(eq? (PREFIX val) NULL-prefix))

(define (MASK? val)
(eq? (PREFIX val) MASK-prefix))

2.2 Fysieke voorstelling van paren
(define FREE 0)
Eerste vrije entry in de 2 vectoren met cars en cdrs
(define SIZE 9)

(define THE-CARS (make-vector SIZE NULL))
NULL = null-pointer
(define THE-CDRS (make-vector SIZE NULL))



2