Noeud: Typed Feature Structures, Noeud « Next »: Tree Adjoining Grammars, Noeud « Previous »: Directives, Noeud « Up »: Top
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.