Implementation of Unification
June 5, 2021 § Leave a comment
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.