More about GC and Joy

I mentioned that my machine is written in and leaves GC to Oberon. It would be possible to implement memory pools, one for each kind of object. When a new intBox (object containing an integer) is needed one is taken from the intBox pool. Only if the pool is empty is a new intBox allocated in Oberon. The problem with the pool approach is that once allocated, memory can be reused only for the same kind of object. A program that fills memory with discarded integers and then tries to allocate millions of strings is going to fail even though the same program would have worked perfectly with no collection, since when memory filled up an Oberon collection would have been triggered. But Oberon can't collect objects in a pool, since they are not garbage from Oberon's point of view. It might be interesting to see the garbage left by programs, though. I have written a garbage compactor. It doesn't reuse memory.

Actually "pop" is the only op rewritten to compact garbage so far.

Here is "pop" :

PROCEDURE pop*(VAR stack: Box);
BEGIN
stack := stack.next
END pop;

compacting "pop" :

PROCEDURE pop*(VAR stack: Box);
VAR
a: Box;
BEGIN
a := stack.next;
stack.next := garbage;
garbage := stack;
stack := a
END pop;

Demonstration of compaction:

program:
[ 1 [ dup 1 plus ] 4 times ]
output:
5 4 3 2 1
garbage:
EMPTY BOX

program:
[ 1 [ dup 1 plus ] 4 times [ pop ] 4 times ]
output:
1
garbage:
2 3 4 5 EMPTY BOX

program:
[ 1 [ dup 1 plus ] 4 times [ pop ] 4 times ]
output:
1
garbage:
2 3 4 5 2 3 4 5 EMPTY BOX

Here is the dictionary object used by the parser printed out:

73 "dup" dup
196 "plus" plus
78 "mul" mul
44 "minus" minus
64 "mod" mod
67 "div" div
105 "i" i
120 "concat" concat
187 "swap" swap
62 "map" map
34 "times" times
207 "if" if
79 "pop" pop
46 "quote" quote
188 "noop" noop
16 "infra" infra
179 "cons" cons
150 "uncons" uncons
47 "empty" empty
192 "zero" zero
107 "define" define
24 "equal" equal
61 "dip" dip
252 "reverse" reverse

Here's a definition:

program:
[ [ dup mul ] "square" define ]
output:
[ dup mul ]
garbage:
2 3 4 5 2 3 4 5 EMPTY BOX

The dictionary now prints an extra entry: 145 "square" dup mul
Notice that the garbage is persistent. The garbage is like an antistack: if it makes you think of a Stirling engine and thermodynamics, you are not the first person this has occurred to. (Probably Henry Baker was.)

GC Redux

Soren Renner — 2000-09-07 18:18:52