Here is a tested version of the code that uses reference counts and the unbounded stack. I see no advantage to conventional garbage collection here. Since our language has no way of mutating structures there can be no loops and thus reference counting should provide simple and efficient storage reclamation.

In the stack version of the run-time, environs (envs) are the only type that is allocated on our ‘heap’ which is actually an array. Each env points to an older env or points to nothing. Each env includes a val which includes a pointer to an env if its .tag is 1. Each env has a field refcnt which is a count of the references thereto. In C the size of a struct is a multiple of coarsest grained field therein. This makes the size of a env 20 instead of 16 for the C version. When an env is passed to eval (by ‘going to top’), eval is expected to ‘consume’ the value and thus free it if a refcnt goes to 0. Any pointers in the val returned are already counted.

A few changes spilled into h.h and m.c which are hereby segregated into the directory upc; other modules are shared with the non-GC version. I compile using the shell command
source makea for repl2, and source makeb for repl2x. b.c takes after ../up/b.c to which these notes apply.

We compute 88 steps in 5 sec if we use (p(P(r8)(r8))) as the ‘Client’ in the last expression here. (p(P(r8)(r6))) (=86) exhausts 100000 cells with repl2 and repl2x without space reclamation. We are clearly reclaiming space.

There remain a few self-diagnostics in the program. Any output line beginning with ‘F’ signals a fatal interpreter bug.

I don't see an impediment that prevents a compiler from using tail call optimization. I think gcc does not provide tail call optimization. Perhaps I will try to find out why gcc does not.

Conceptual Problem

There is a tension between ideas. The idea of reference counts seems simple at first, but which references do you count? Certainly references in inaccessible (abandoned) heap blocks are not counted. What about dead variables? By ‘dead’ here I mean that the program counter points to code that does not progress to using the value in that variable. To keep to a simpler definition of reference count I might put the value 0 into dead variables, and then perhaps remove such commands after debugging, but leaving comments in their place.

We might declare that at labels top, and dstn, the counts are by the simple definition, including references via local variables e, v and c. By ‘e’ here I mean that cell that gets a value upon entering routine eval.

So far the code is designed with the idea that eval consumes its e argument in the sense that it decrements the count in block referenced by th 2nd argument. I think I have not unified these two ways of thinking.

Actually we make the first env point to the env named dummy which points to itself. Hopefully dummy is never accessed. (Rethink!)