🚀 go-pugleaf

I have been examining various prolog implementations
and I see that all of them continue to use a trail stack
to record variable bindings that must be undone on
backtrack.

An entry on the trail
stack records the transition of a variable from unbound to bound.
From this I deduce that a variable will never appear
more than once on the trail stack at any given point in time.

If this deduction is true, then
it seems to me that one could replace the trail stack
by a trail chain threaded thru the variables in the heap
and in the environment (i.e., non-prototypical variables).

This would be implemented in the obvious way:
1. every variable has two parts: a binding value,
   and a trail chain pointer.
2. every environment (actually, only backtrack environments)
   have a pointer to the top of the chain at the point of
   the environment's creation.
3. trailing a variable consists of storing the current trail top
   into the trail pointer for the variable, and making the trail
   top point to this variable.  In other words, we link
   the variable into the front of the trail chain.
4. Untrailing just steps down the chain, unbinding the variables
   and setting their trail pointers to nil.

The cost over a trail stack is the doubling of space
used for variables and the time to link the variable into
the chain.  On a typical 32 bit machine, both of these costs
seem insignificant.

The advantage, of course, is that one of the prolog stacks
is eliminated, and that makes memory management simpler.

I assume that this idea has occurred to others,
but since none of the implementations I have seen use it,
I have a feeling that there is some obvious flaw.
If so, can someone please explain it to me?

Dennis Heimbigner
dennis@boulder.colorado.edu