Implementation of Unification

The unification operator takes two feature structures as input and returns a single merged feature structure if successful or a failure signal if the inputs are not compatible.

A notable aspect of this algorithm is that rather than constructing a new feature structure with the unified information from the two arguments, it destructively alters the arguments so that in the end they point to exactly the same information. Thus, the result of a successful call to the unification operator consists of suitably altered versions of the arguments.

Unification data structures

To facilitate the destructive merger aspect of the algorithm, we add a small complication to the DAGs used to represent the input feature structures: feature structures are represented by DAGs with additional edges, or fields. Specifically, each feature structure consists of two fields: a content field and a pointer field. The content field may be null or contain an ordinary feature structure. Similarly, the pointer field may be null or contain a pointer to another feature structure. If the pointer field of the DAG is null, then the content field of the DAG contains the actual structure to be processed. If, on the other hand, the pointer field is non-null, then the destination of the pointer represents the actual feature structure to be processed. The merger aspects of unification are achieved by the alteration of the pointer field of DAGs during processing.

def unify(f1-orig, f2-orig):
	f1 = f1-orig
	f2 = f2-orig
	if(f1 ==f2):
		f1.pointer = f2
		return f2
	else if(f1 == None):
		f1.pointer = f2
		return f2
	else if(f2==None):
		f2.pointer = f1
		return f1
	else if(f1 != None and f2 != None):
		f2.pointer = f1
		for feature_2 in f2.feature:
			present = False
			for feature_1 in f1.feature:
				if(feature_1 == feature_2):
					present = True
			for feature_1 in f1.feature:
				if(present == False):
					f1.feature += feature_2
					if (unify(feature_1.value, feature_2.value)== "failure"):
						return "failure"
		return f1
	else:
		return "failure"

P.S. To collaborate to the creation of the algorithm you can subscribe to this repo by emailing my at the email in the Contacts page.