Typed Feature Structures

Typed Feature Structures a la Carpenter are available in DyALog (in an experiemental way). They extend standard Feature Structures by considering that (1) feature structure functors are types in some type hierarchy, (2) features are inherited from type to subtype and (3) feature values must satisfy type constraints.

For instance, list.def specify a small hierarchy for TFS corresponding to lists.

     bot sub [atom,list].
         atom sub [].
         list sub [e_list,ne_list].
             e_list sub [].
             ne_list sub [] intro [hd:atom,tl:list].
     

This description says that bot is the most general type with subtypes atom and list. Similarly, list has two subtypes e_list (for empty list) and ne_list (for non empty list). ne_list introduces two new features, namely hd and tl whose most general type should be respectively atom and list.

The set of features associated with type is given by all features introduced by type and its super types. A feature may be introduced again by type with a more specific type.

Any tfs built on type may be instanciated to a new tfs built on a subtype of type. For instance, list{} generalizes both e_list{} and ne_list{hd=>atom{},tl=>list{}}.

Subsumption checking as well as unification have therefore to be extended to handle type shifting. This is done by linking executable with a C library generated from the description file.

Actually, the generated C library need also to be dl-opened by the compiler to extend program reading and performs some immediate unifications.

Let suppose we want to use the following implementation of append:

     %> cat tfs_append.pl
     
     append(e_list{}, Y::list{}, Y).
     
     append( A::tl=>X,Y::list{}, B::tl=>Z) :-
             A .> hd .= B.> hd,
             append(X,Y,Z).
     
     ?-X=tl=>tl=>e_list{},Y=tl=>_,append(X,Y,Z).
     

In file tfs_append.pl, Y::list{} denotes immediate unification performed by the compiler between Y and list{}. Notation tl=>X introduces the most general tfs with feature tl bound to X, i.e. ne_list{hd=>atom{},tl=>X::list{}}. Expression A .> hd .= B .> hd is an alternate way to specify the unifiability of values given as feature pathes: here, we unify value of feature hd of tfs A with value of feature hd of tfs B.

To compile tfs_append.pl, we first need to generate the C library from list.def.

     %> tfs2lib list.def
     

The resulting library is called liblist.so.0. It will used by the compiler to be able to correctly read tfs_append.pl and linked with the executable to extend unification and subsumption.

     %> dyacc -tfs list tfs_append.pl -o tfs_append
     

Both the compiler (dyalog) and the executable (tfs_append) should be able to locate library liblist.so.0, either by moving the library in some known library directory or by setting, for instance, the environment variable LD_LIBRARY_PATH.

An alternate way is to use the option -libtool <libtoo_pgm> for both tfs2lib and dyacc.

     %> tfs2lib list.def -libtool libtool
     %> dyacc -tfs list -libtool libtool tfs_append.pl -o tfs_append
     

The library is now called liblist.la and is actually a shell wrapper to the true library.