Types and Features

Japanese version


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
     ----→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.

Fig 3.3 Example of Type Hierarchy
Equilateral  Isometric Right Angle
   \      /         \
   Isometric    Right Angle Triangle
          \        /

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
For example, in the above figure
> ?- X = Triangle, X = Isometric.
X: Isometric
> ?- X = Isometric, X = Right Angle Triangle.
X: Isometric Right Angle Triangle
> ?- X = Equilateral, X = Right Angle Triangle.
If no common subtype exists, the function fails. Since 'bot' is supertype of all types, unification will always succeed and unification of bot with X will always be X.

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.


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 

Fig 3.4 Example of Feature
Straight[Minimum Value]  Fresh[Stud]
              \          /
               Poker's Hand

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            _|
First the top level unification of 'Straight' and 'Fresh' will be performed. The result of this will be 'StraightFresh', The resultant Feature Structures will be 
|~StraightFresh         ~|
| Minimum Value:10       |
|_Stud:bot              _|
|~StraightFresh         ~|
| Minimum Value:bot      |
|_Stud:Speed            _|
Next,  Feature Structure associated with each Feature will be unified. Feature 'Minimum Value''s Feature Structure will be  '10', Feature 'Stud''s Feature Structure will be 'Speed'.Thus the final unification result will be:
|~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     _|
When Feature A is unified, since A and B feature's are shared and also B and C feature's are shared the result of unification will be 


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


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. 

Prev: Getting Started Next: Grammar
Table of Contents LiLFeS Documents LiLFeS Home Page Tsujii Lab.