Specification of Compilation Algorithm for Psi-term Unification

The compilation algorithm unifies the statically known psi-term T with the contents of register Rt (which is known only at run-time). The compilation algorithm is described in terms of two sequences of instructions: the read stream and the write stream (see Fig. 2). After compilation is finished, the two streams are linked together into a single sequence with one jump instruction, prefixed with an init_test instruction (see Fig. 1). This sequence is then passed to the peephole optimizer.

A psi-term is a generalization of a Prolog term. A psi-term has a sort (corresponding to the main functor) which lives in a hierarchy (a lattice). Unification of sorts is a glb operation on the lattice. A psi-term may have any number of named fields ("features"), and features may be added at run-time. Therefore psi-terms do not have an arity. A psi-term may have cycles and sharing between subterms.

Terminology for the algorithm: Each occurrence of a subterm (even a coreferenced one) is considered as a separate psi-term. A coreference class is a set of occurrences that are linked by equality constraints. The first member of a coreference class that is encountered in a depth-first traversal of a term is called the representative member. Coreferences are handled by the judicious placement of unify instructions (see Fig. 3).

Unification compilation is done in 60 lines and peephole optimization in 80 lines. Together with 110 lines of utility routines, this results in 250 lines of Life code. This includes a naive register allocator which maps each subterm occurrence to a different register.

Figure 1: Compile psi-term T at level 0

			       |
			   init_test
			       |
			----------------
			|  Read stream |
			----------------
			       |
			    jump(L)
			       |
			----------------
			| Write stream |
			----------------
			       |
			   label(L)
			       |

Figure 2: Compile psi-term T at level l

Notation:

f = a feature (field name) of T.
s = the rootsort (main functor) of T.
l = nesting level of the term.
Rt = register containing a pointer to T.
Rf = register containing a pointer to T.f.
L, L' = code labels.

Insert the following instructions into the read and write code streams:

			    Read stream			  Write stream

-----------------------------------------------------------------------------
                                |                             |
For the rootsort of T:      intersect_sort(Rt,s)          set_sort(Rt,s)
                                |                             |
-----------------------------------------------------------------------------


-----------------------------------------------------------------------------
For all features f of T:	|			      |
			    test_feature(Rt,f,Rf,L,l) --> label(L)
				|			  push_cell(Rf)
				|			  set_feature(Rt,f,Rf)
				|			      |
			   -----------------------------------------
			   |   Compile psi-term T.f at level l+1   |
			   -----------------------------------------
				|			      |
			    label(L') <------------------ write_test(l,L')
				|			      |
			   -----------------------------------------
			   |   Handle possible coreference of T.f  |
			   -----------------------------------------
				|			      |
-----------------------------------------------------------------------------

Figure 3: Handle possible coreference of T.f

Notation:

Rc = register containing a pointer to the representative member of the coreference class containing T.f (if it exists).

-----------------------------------------------------------------------------
				|			      |
If T.f is in a coreference  unify(Rf,Rc)		  unify(Rf,Rc)
class, but is *not* the		|			      |
representative member:		|			      |
				|			      |
-----------------------------------------------------------------------------