$B!]!]!]!]"*(BDance in the Dark
$B"*(BRacing Horse$B!]!]!]!]!]"*(BHail to Reason
$B!C!@(B Father Lineage $B",(B
$B!C(B $B!]!]"*(BStud Horse$B!]!]!]!](B
$B!C(B $B!C(B Name
$B!C(B $B!]!]!]"*(BSunday Science
$B!C(B Mother Name
$B!]!]"*(B Mare$B!]!]!]!]"*(BDancing Queen
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$B!%(B
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.
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 $B!@(B $B!?(B $B!@(B Isometric Right Angle Triangle $B!@(B $B!?(B Triangle $B!C(B bot
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,
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
Let us assume we have two types X,Y$B!$(Band we unify in LiLFeS :
For example$B!$(B in the above figure
X = Y
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.
> ?- 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.
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] $B!@(B $B!?(B Poker's Hand $B!C(B bot
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'$B!%(B If 'Poker's Hand' has some feature A then it will also be inherited only once in 'StraightFresh'.
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$B!$(B Feature Structure unification will be
First the top level unification of 'Straight' and 'Fresh' will be performed$B!%(B The result of this will be 'StraightFresh'$B!$(B The resultant Feature Structures will be
|~Straight ~| |_Minimum Value:10 _||~Fresh ~| |_Stud:Speed _|
Next, Feature Structure associated with each Feature will be unified$B!%(B Feature 'Minimum Value''s Feature Structure will be '10'$B!$(B Feature 'Stud''s Feature Structure will be 'Speed'$B!%(BThus the final unification result will be:
|~StraightFresh ~| | Minimum Value:10 | |_Stud:bot _||~StraightFresh ~| | Minimum Value:bot | |_Stud:Speed _|
|~StraightFresh ~| | Minimum Value:10 | |_Stud:Speed _|
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:
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:bot _||~example ~| | A:bot | | B:$2 bot | |_C:$2 _|
|~example ~| | A:$1 bot | | B:$1 | |_C:$1 _ |$B!!(B
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$B!$(Ba 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.