Types and Features

Contents

• Feature Structure
• Type Hierarchy
• Type Unification
• Feature
• Unification
• Structure Sharing
• Misc

Feature Structure

Feature Structure(FS) is a Directed Graph, in which all the nodes and edges have an associated name. The name associated with a node is called Type and the name associated with a edge is called Feature. The types of edges or attributes that can be associated with a node are determined uniquely by the Type.

Figure 3.1 Example of Feature Structure

Name −−−−→Dance in the Dark ｜ Lineage →Racing Horse−−−−−→Hail to Reason ｜＼ Father Lineage ↑ ｜ −−→Stud Horse−−−− ｜ ｜ Name ｜ −−−→Sunday Science ｜ Mother Name −−→ Mare−−−−→Dancing Queen ｜ Lineage −−−→Northern Dancer

The left most node 'Racing Horse' (with the arrow in front) is a special node called the Root node. Every Feature Structure must have a Root node. 'Hail to Reason' is connected to by two edges. This type of structure is called Structure Sharing．

Since it is difficult and time consuming to represent the feature structures by drawing graphs, the following representation called as Attribute-Value Matrix (AVM) is used.

Figure 3.2 AVM Representation of Example Feature Structure

|~Racing Horse ~| | Name: Dance in the Dark | | Lineage:$1 Hail to Reason | | |~Stud Horse ~| | | Father:| Name: Sunday Science | | | |_Lineage:$1 _| | | |~Mare ~| | | Mother:| Name: Dancing Queen | | |_ |_Lineage:Northern Dance_| _|

That figure represents the same structure than the previous one.  The part encircled is a Feature Structure. $1 is an example of   Structure Sharing. LiLFeS displays the Feature Structure in the above format.

Type Hierarchy

A type have a structure hierarchy. For example, for the types of triangles, we could write the next structure hierarchy.

The lines above represent the supertype-subtype relation. In the figure above, the lower direction is the supertype and the upper direction is subtype. All types, (except 'bot') have necessarily at least one supertype.  In LiLFes,  'bot'(bottom, predefined),  is the supertype of of all the types.

Type Unification

The operation between different data types is defined as unification. As can be easily seen from the above figure, the process of finding the common parent or subtype is called as Unification. It is also called as LUB(Least Upper Bound).

Let us assume we have two types X,Y，and we unify in LiLFeS :

X = Y

> ?- X = Triangle, X = Isometric. X: Isometric > ?- X = Isometric, X = Right Angle Triangle. X: Isometric Right Angle Triangle > ?- X = Equilateral, X = Right Angle Triangle. no

In LiLFeS Type Hierarchy, the unification must always always be LUB i.e., it does not allow type types having common multiple subtypes, that too with no supertype-subtype relation. For example, in the above figure, it is not possible to define a new supertype for Isometric and Right Angle triangle, which makes LiLFeS more rigid, error-free  and efficient compared to PROLOG.

Feature

Each node can have Feature associated. If a supertype has a feature all children will have the feature inherited. When a node has multiple supertype(s) with the same feature, it will be inherited only once. In LiLFeS it is not possible to define the same name more than two times.

Values in brackets are Feature 

Here, if we define 'Straight' and 'Fresh' to have a supertype called  'StraightFresh' then it will have two features  'Minimum Value' and 'Stud automatically derived'． If 'Poker's Hand' has some feature A then it will also be inherited only once in 'StraightFresh'.

Feature Structure Unification

Feature Structure unification starts from the root type. If it succeeds then each of the children are unified recursively till all the nodes are successful resulting in successful unification.

In Poker's Hand example， Feature Structure unification will be 

|~Straight ~| |_Minimum Value:10 _| |~Fresh ~| |_Stud:Speed _|

|~StraightFresh ~| | Minimum Value:10 | |_Stud:bot _| |~StraightFresh ~| | Minimum Value:bot | |_Stud:Speed _|

|~StraightFresh ~| | Minimum Value:10 | |_Stud:Speed _|

Structure Sharing

Feature Structure can be thought of as a graph. Unlike a tree, multiple edges can point to a single node, which is refered to as Structure Sharing. In our First Example , node 'Hail to Reason' is sharing structure and while displaying it in AVM, dag $x (where x is number) is used and only expanded in once and suppressed in other places. Unification of shared structures is also possible. For example unification of the following:

|~example ~| | A:$1 bot | | B:$1 | |_C:bot _| |~example ~| | A:bot | | B:$2 bot | |_C:$2 _|

|~example ~| | A:$1 bot | | B:$1 | |_C:$1 _ |

Miscellaneous

LiLFeS can handle lists in the same way than PROLOG.

> ?- X = [1, 2, 3]. X: < 1, 2, 3 >

Lists are also Feature Structure. The type of the list is 'list', and have as direct subtypes 'cons' and 'nil' and 'cons' have the features 'hd' and 'tl'. 'hd' would be the equivalent to 'car' in LISP and 'tl' to 'cdr'. Thus the above will be represented in Feature Structure as:

|~cons ~| | hd:1 | | |~cons ~| | | | hd:2 | | | tl:| |~cons ~| | | | | tl:| hd:3 | | | |_ |_ |_tl:nil_|_|_|

List being a Feature Structure can also contains structure sharing.. For example, in the next example，a alternating infinite series of 1, 2 can be represented:

> ?- X = [1, 2 | X]. X: [$1] < 1, 2 | [$1] ... >

In LiLFeS, predicates, feature names, etc. can also be treated as Feature Structures.