We collect the necessary type declarations here for convenience:

typedef unsigned char uchar;
struct env;
typedef unsigned long long int nis;
typedef uchar * cp;
typedef struct{struct env * e; cp c;} fun;
typedef struct val pf(nis);
typedef struct val {uchar tag; union{nis i; fun f; pf * p;} u;} val;
// tag=0 for i; tag=1 for f; tag=2 for p.
typedef struct env {val v; struct env * out;} env;
typedef struct {cp c; env * e;} Fcont;
typedef struct {env * v; env * e;} Acont; // we hold a val v in an env!
typedef struct cnt {char tag; union {Fcont f; Acont a;} c; struct cnt * C;} cnt;
// tag= [0 for Fcont, 1 for Acont.]
typedef union {env e; cnt c;} gws;

I just now recalled why mark and sweep was used rather than the simpler and more obvious reference count mechanism. Reference counts do not find and recover the space occupied by isolated loops of linked structures. A purely functional language, such as our λ calculus can produce no loops for lack of any structure mutating side-effects. I now know no reason to implement a classic GC algorithm and the remainder of this page may thus lead to no code.

We consider mark and sweep garbage collection here. Our version is type savvy; it considers the type and thereby knows how to find the pointers internal to an object that it is considering.

The type gws is the space allocated to either a continuation or an environ. A pointer to a gws is always in a context that determines the choice between env and cnt, except during the sweep phase of gc. cnt structures are never reclaimed by gc; they are explicitly freed by program logic as in stack logic. These structures must be examined in the mark phase, however, to locate the accessible env values. Instead of using C's stack we track deferred goals by reversing pointers as we explore tree branches. I used this technique in 1961 on a LISP interpreter for the 6600. Subsequently Herb Schorr wrote a paper on the idea. Herb did not learn it from me.

Only the cnt and the variable c hold references to a cnt and this chain is like the traditional stack, except the frames are not contiguous. The scan phase must pass over the chain in just one direction taking detours thru the pure env trees rooted at each cnt. These trees are not disjoint and we must thus mark each env and avoid processing it twice. As we explore env trees how do we get back to the root without a stack? Suppose that node A (a env) points to node B which we find first starting from A. Suppose further that B points to C. As we proceed to C we put A’s address where we found