Path Compression

[Code]
As feature structures get updated, reference chains get very long with certain signatures and thus may become slower to process. ALE remedies this situation by performing an operation called path compression to reduce the size of reference chains before an edge is added to a chart and before a feature structure is output to the user. The predicate fully_deref/4 is responsible for path compression. In fully_deref(RefIn,SVsIn,RefOut,SVsOut), RefIn and SVsIn are the input reference (or Tag) and sort values respectively, and RefOut and SVsOut will be the output reference and sort values. The path compression algorithm of fully_deref/4 is described in Table 1.1.

Table 1.1: Path-compression algorithm

Condition	Action
RefIn is a variable	RefIn = fully(RefOut,SVsOut)-SVsOut, run fully_deref/4 on arguments of RefIn
RefIn is not a variable	if RefIn == fully(Ref,_), then this means that RefIn has already been processed by fully_deref/4; thus, RefOut = Ref and SVsOut = SVs
	if RefIn == Ref-SVs, then call fully_deref(Ref,SVs,RefOut,SVsOut).

As an example, consider the following:

| ?- fully_deref(Tag1-s1(Tag2-t2-t3,Tag3-t4-t5),
                 SVsIn,TagOut,SVsOut).

Tag1 = fully(TagOut,s1(_A-t2,_B-t4))-s1(_A-t2,_B-t4),
Tag2 = fully(_A,t2)-t2,
Tag3 = fully(_B,t4)-t4,
SVsOut = s1(_A-t2,_B-t4)

The result of running path-compression on

Tag1-s1(Tag2-t2-t3,Tag3-t4-t5)

is TagOut-SVsOut. The reason for using fully/2 is that we want to know if a path has already been compressed or not due to cycles in the feature structure that it represents.