dennis@boulder.UUCP (10/30/87)
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