Functional Descriptions vs. First-order Terms

To conclude the characterization of FDs as a data-structure, it is useful to contrast functional unification (FU) with the more well known structural unification (SU) as used in PROLOG for example, and to distinguish FDs from the first-order terms used in SU.

The most important difference is that functional unification is not based on order and length. Therefore, {a:1, b:2} and {b:2, a:1} are equivalent in FU but not in SU, and {a:1} and {b:2, a:1} are compatible in FU but not in SU (FDs have no fixed arity). The following quote from Knight summarizes the distinction between feature structures and the first order terms used in SU:

• Substructures are labeled symbolically, not inferred by argument position.

• Fixed arity is not required.

• The distinction between function and argument is removed.

• Variables and coreference are treated separately. [#!Knight (!#,#!p.105)!#]

A comparison between the FD notation and the first-order term notation illustrates these differences. The following FD and first-order term can be used to represent the fact that Steve builds a crane that is 2 lbs and 4 feet high:

	((process build)
	 (agent Steve)
	 (object ((concept crane)
                   (weight 2)
                   (height 4))))

	build(Steve, Crane(C1, 2, 4))

⁴

Contrasting these two notations for the same example illustrates the differences:

• Symbolic labels for substructures: the arguments, that is the agent and the medium, are clearly labeled in the feature structure notation. In particular, a term like Crane(C1, 2, 4) is particularly difficult for a human to interpret.

• Fixed arity: features can be added at will to an FD. FDs are used to represent partial information. This is not the case for first-order terms. If the knowledge representation changes to include width to crane descriptions, in addition to weight and height, all the terms need to be updated, since Crane(n, w, h) is not compatible with Crane(n, w, h, l). The FD notation is always partial and leaves the possibility of adding new features as needed.

• Function and argument: first-order terms have a head (the function) which plays a central role in the unification process. This is not the case in FDs. All information plays the same role.⁵

• Variables and coreference: in standard unification, a variable is used to mean two distinct things: that the value of the role is unknown (there are no constraints on it), and that the value of the role is the same as all other objects referred to with the same variable. So for example, in a term such as like(X, X), the use of the variable X means that we don't know who likes whom, and that it is known that the agent and the object of like must be the same objects. The distinction between these two functions of variables is best explained in [#!Ait-kaci!#]. In FDs, coreference and unspecification are represented by two different syntactic devices: variables are features which are unspecified (they simply do not appear in the FD, or appear with an empty value), coreference is handled with paths. For example, to express the constraint that the medium of like must refer to the same object as its agent, the following FD can be used:

     ((process like)
      (agent {object}))