6.001 Recitation – May 9, 2003

RI: Konrad Tollmar

www.ai.mit.edu/~konrad/6001

• Memory Management

• Decompiling

1. Store lists in arrays

Memory consists of two arrays: “the-cars” and “the-cdrs”. Each cell stores the following: A number and a tag. For now, we have three tags:

1. Nx -- Number
2. Px -- Pointer to another cell
3. Ex -- NULL

Using this implementation of cons cells, (cons A B) does this:

1. Look for the next FREE location (i)
2. Store A at the-cars[i]
3. Store B at the-cdrs[i]
4. Return , a pointer to the new cons cell.

A/ Draw the box-and-pointer diagram starting from P5

	0	1	2	3	4	5	6	7	8	9	10
Cars	N3	N4	P0	N3	N5	P2	N2	N3	P1	N4
Cdrs	E0	E0	P4	P5	P0	P6	P5	P3	P3	N5

B / Save foo in memory

(define foo (map square (list 1 2 3)))

1.Build the list (1 2 3)

2.Build the list (1 4 9)

3.Define foo to be the latter list

There are no pointers to the list (1 2 3) anymore. It cannot be accessed. It is garbage. The memory should be recycled.

	0	1	2	3	4	5	6	7	8	9	10
Cars	N1	N2	N3	N1	N4	N9
Cdrs	P1	P2	E0	P4	P5	E0

2. GC – Stop & Copy

Garbage is anything that cannot have any influence on the future computation.

Everything else we need to keep around. We define the Root Set to be the set of all pointers in the machine registers and stack. The cells we might need are defined as those cells that can be reached by a succesion of car and cdr operations starting from the root set.

Stop & Copy

1.Split memory in half (Working memory and Copy memory).

2.Keep a free pointer to the free part of memory.

3.When Memory runs out, stop computation and begin garbage collection.

Do stop-and-copy on the following with Root Set = { P5 }:

	0	1	2	3	4	5	6	7	8	9	10
Cars	N3	N4	P0	N3	N5	P2	N2	N3	P1	N4	N2
Cdrs	E0	E0	P4	P5	P0	P6	P5	P3	P3	N5	E0

	0	1	2	3	4	5	6	7	8	9	10
Cars	P1	P3	N2	N3	N5
Cdrs	P2	P4	P0	E0	P3

3. GC – Mark & Sweep

• More compact than stop-and-copy.

• Must looks through all of memory, so it is fairly slow.

	0	1	2	3	4	5	6	7	8	9	10
Cars	N3	N4	P0	N3	N5	P2	N2	N3	P1	N4	N2
Cdrs	E0	E0	P4	P5	P0	P6	P5	P3	P3	N5	E0
	1	0	1	0	1	1	1	0	0	0	0