ProFIT: Prolog with Features, Inheritance and Templates 
Gregor Erbach 
Universit~t des Saarl~ndes 
Computerlinguistik 
D-66041 Saarbrficken, Germany 
e-mail: erbach~col i. uni-sb, de 
URL : http ://coli. uni-sb, de/~ erbach/ 
Abstract 
ProFIT is an extension of Standard Pro- 
log with Features, Inheritance and Tem- 
plates. ProFIT Mlows the programmer 
or grammar developer to declare an in- 
heritance hierarchy, features and tem- 
plates. Sorted feature terms can be used 
in ProFIT programs together with Pro- 
log terms to provide a clearer descrip- 
tion language for linguistic structures. 
ProFIT compiles all sorted feature terms 
into a Prolog term representation, so 
that the built-in Prolog term unification 
can be used for the unification of sorted 
feature structures, and no special uni- 
fication algorithm is needed. ProFIT 
programs are compiled into Prolog pro- 
grams, so that no meta-interpreter is 
needed for their execution. ProFIT thus 
provides a direct step from grammars de- 
veloped with sorted feature terms to Pro- 
log programs usable for practical NLP 
systems. 
1 Introduction 
There are two key ingredients for building an NLP 
system: 
• a linguistic description 
• a processing model (parser, generator etc.) 
In the past decade, there have been diverging 
trends in the area of linguistic descriptions and in 
the area of processing models. Most large-scale 
linguistic descriptions make use of sorted feature 
formalisms, 1 but implementations of these for- 
malisms are in general too slow for building prac- 
tically usable NLP systems. Most of the progress 
in constructing efficient parsers and generators 
has been based on logic grammars that make use 
1Sorted feature structures are sometimes referred 
to as typed feature structures, e.g. in Carpenter's 
"Logic of Typed Feature Structures." We follow the 
usage in Logic Programming and the recent HPSG 
literature. 
of ordinary prblog terms. We provide a general 
tool that brings together these developments by 
compiling sorted feature terms into a Prolog term 
representation, so that techniques from logic pro- 
gramming and logic grammars can be used to pro- 
vide efficient processing models for sorted feature 
grammars. 
In this introductory section, we discuss the ad- 
vantages of sorted feature formalisms, and of the 
logic grammar paradigm, and show how the two 
developments can be combined. The following 
sections describe the ProFIT language which pro- 
vides sorted feature terms for Prolog, and its im- 
plementation. 
1.1 Grammar Development in Sorted 
Feature Formalisms 
Sorted feature formalisms are often used for the 
development of large-coverage grammars, because 
they are very well suited for a structured descrip- 
tion of complex linguistic data. Sorted feature 
terms have several advantages over Prolog terms 
as a representation langauge. 
1. They provide a compact notation. Features 
that are not instantiated can be omitted; 
there is no need for anonymous variables. 
2. Features names are mnemonic, argument po- 
sitions are not. 
3. Adding a new feature to a sort requires 
one change in a declaration, whereas adding 
an argument to a Prolog functor requires 
changes (mostly insertion of anonymous vari- 
ables) to every occurence of the functor. 
4. Specification of the subsort relationship is 
more convenient than constructing Prolog 
terms which mirror these subsumption rela- 
tionships. 
Implementations of sorted feature formalisms 
such as TDL (Krieger and Sch~ifer, 1994), ALE 
(Carpenter, 1993), CUF (DSrre and Dorna, 1993), 
TFS (Emele and Zajac, 1990) and others have 
been used successfully for the development and 
testing of large grammars and lexicons, but they 
may be too slow for actual use in applications 
180 
because they are generally built on top of Pro- 
log or LISP, and can therefore not be as efficient 
as the built-in unification of Prolog. There are 
a few logic programming langauges, such as LIFE 
(Ait-Kaci and Lincoln, 1989) or Oz (Smolka et al., 
1995), that provide sorted feature terms, but no 
commercial implementations of these languages 
with efficient compilers are yet available. 
1.2 Efficient Processing based on Logic 
Grammars 
Much work on efficient processing algorithms has 
been done in the logic grammar framework. This 
includes work on 
• Compiling grammars into efficient parsers 
and generators: compilation of DCGs into 
(top-down) Prolog programs, left-corner 
parsers (BUP), LR parsers, head-corner 
parsers, and semantic-head driven genera- 
tors. 
• Use of recta-programming for self-monitoring 
to ensure generation of unambiguous utter- 
ances (Neumann and van Noord, 1992) 
• Work in the area of Explanation-Based 
Learning (EBL) to learn frequently used' 
structures (Samuelsson, 1994) 
• Tabulation techniques, from the use of well- 
formed substring tables to the latest devel- 
opments in Earley deduction, and memoing 
techniques for logic programming (Neumann, 
1994) 
• Work based on Constraint Logic Program- 
ming (CLP) to provide processing models for 
principle-based grammars (Matiasek, 1994) 
• Using coroutining (dif, freeze etc.) to provide 
more efficient processing models 
• Partial deduction techniques to produce more 
efficient grammars 
• Using Prolog and its indexing facilities to 
build up a lexicon database 
Since much of this work involves compilation of 
grammars into Prolog programs, such programs 
can immediately benefit from any improvements 
in Prolog compilers (for example the tabulation 
provided by XSB Prolog can provide a more effi- 
cient implementation of charts) which makes the 
grammars more usable for NLP systems. 
1.3 Combining Logic Grammars and 
Sorted Feature Formalisms 
It has been noted that first-order Prolog terms 
provide the equivalent expressive power as sorted 
feature terms (Mellish, 1992). For example, 
Carpenter's typed feature structures (Carpenter, 
1992) can easily be represented as Prolog terms, if 
the restriction is given up that the sort hierarchy 
be a bounded complete partial order. 
Such compilation of sorted feature terms into 
Prolog terms has been successfully used in the 
Core Language Engine (CLE) (Alshawi, 1991) and 
in the Advanced Linguistic Engineering Platform 
(ALEP), (Alshawi et al., 1991). 2 ProFIT ex- 
tends the compilation techniques of these systems 
through the handling of multi-dimensional inher- 
itance (Erbach, 1994), and makes them generally 
available for a wide range of applications by trans- 
lating programs (or grammars) with sorted feature 
terms into Prolog programs. 
ProFIT is not a grammar formalism, but rather 
extends any grammar formalism in the logic gram- 
mar tradition with the expressive power of sorted 
feature terms. 
2 The ProFIT Language 
The set of ProFIT programs is a superset of Pro- 
log programs. While a Prolog program consists 
only of definite clauses (Prolog is an untyped lan- 
guage), a ProFIT program consists of datatype 
declarations and definite clauses. The clauses of a 
ProFIT program can make use of the datatypes 
(sorts, features, templates and finite domains) 
that are introduced in the declarations. A ProFIT 
program consists of: 
• Declarations for sorts 
• Declarations for features 
• Declarations for templates 
• Declarations for finite domains 
• Definite clauses 
2.1 Sort Declarations 
In addition to unsorted Prolog terms, ProFIT al- 
lows sorted feature terms, for which the sorts and 
features must be declared in advance. 
The most general sort is top, and all other sorts 
must be subsorts of top. Subsort declarations 
have the syntax given in (1). The declaration 
states that all Subi are subsorts of Super, and 
that all Subi are mutually exclusive. 
Super >\[Sub,,..., (1) 
It is also possible to provide subsorts that are 
not mutually exclusive, as in (2), where one sub- 
sort may be chosen from each of the "dimensions" 
connected by the * operator (Erbach, 1994). 
Super > \[Subl.l,...,Subl.n\] * 
: (2) 
\[Subk.l,..., Subk.m\] 
Every sort must only be defined once, i.e. it 
can appear only once on the left-hand side of the 
connective >. 
2Similar, but less efficient compilation schemes are 
used in Hirsh's P-PATR (Hirsh, 1986) and Coving- 
ton's GULP system (Covington, 1989). 
181 
The sort hierarchy must not contain any cycles, 
i.e. there must be no sorts A and B, such that 
A#B, andA> B> A. 
The immediate subsorts of top can be declared 
to be extensional. Two terms which are of an 
extensional sort are only identical if they.have a 
most specific sort (which has no subsort), and if 
all features are instantiated to ground terms. If a 
sort is not declared as extensional, it is intensional. 
Two intensional terms are identical only if they 
have been unified. 
2.2 Feature Declarations 
Unlike unsorted feature formalisms (such as PATR- 
II), where any feature can be added to any struc- 
ture, ProFIT follows the notion of appropriate- 
ness in Carpenter's logic of typed feature struc- 
tures (Carpenter, 1992), and introduces features 
for particular sorts. For each sort, one must de- 
clare which features are introduced by it. The 
features introduced by a sort are inherited by all 
its subsorts, which may also introduce additional 
features. A feature must be introduced only at 
one most general sort. This makes it possible to 
provide a notation in which the sort name can be 
omitted since it can be inferred from the use of a 
feature that is appropriate for that sort. 
This notion of appropriateness is desirable for 
structuring linguistic knowledge, as it prevents the 
ad-hoc introduction of features, and requires a 
careful design of the sort and feature hierarchy. 
Appropriateness is also a prerequisite for compila- 
tion of feature terms into fixed-arity Prolog terms. 
Each feature has a sortal restriction for its 
value. If a feature's value is only restricted to be of 
sort top, then the sortal restriction can be omit- 
ted. The syntax of feature declarations is given in (3). 
Sort intro \[Feature1 : Restrl, 
: (3) 
Feature, : Restrn\]. 
The following declaration defines a sort bi- 
nary_tree with subsorts leaf and internaLnode. 
The sort binary tree introduces the feature label 
and its subsort adds the features lefl_daughler and 
right_daughter. If a sort has subsorts and intro- 
duces features, these are combined in one declara- 
tion. 
binary_tree > Ileal, internal_node\] 
intro \[label\]. 
int ernal_node 
intro \[left_daughter:binary_tree, 
right_daught er: binary_tree\]. 
2.3 Sorted Feature Terms 
On the basis of the declarations, sorted feature 
terms can be used in definite clauses in addition to 
and in combination with Prolog terms. A Prolog 
term can have a feature term as its argument, and 
a feature can have a Prolog term as its value. This 
avoids potential interface problems between dif- 
ferent representations, since terms do not have to 
be translated between different languages. As an 
example, semantic representations in first-order 
terms can be used as feature values, but do not 
need to be encoded as feature terms. 
Sorted feature terms consist of a specification 
of the sort of the term (4), or the specification of 
a feature value (5), or a conjunction of terms (6). 
A complete BNF of all ProFIT terms is given in 
the appendix. 
< Sort (4) 
Feature ! Value (5) 
Term ~ Term (6) 
The following clauses (based on HPSG) state 
that a structure is saturated if its subcat value 
is the empty list, and that a structure satisfies 
the Head Feature Principle (hfp) if its head fea- 
tures are identical with the head features of its 
head daughter. 3 Note that these clauses provide 
a concise notation because uninstantiated features 
can be omitted, and the sorts of structures do not 
have to be specified explicitly because they can be 
infered from use of the features. 
saturated ( synsem ! local ! cat ! subcat ! <elist ). 
hfp ( synsem ! local ! cat ! head ! X 
dtrs ! head_dr r ! synsem ! local ! cat ! head ! X ). 
Note that conjunction also provides the possi- 
blity to tag a Prolog term or feature term with a 
variable (Var ~ Term). 
2.4 Feature Search 
In the organisation of linguistic knowledge, feature 
structures are often deeply embedded, due to the 
need to group together sets of features whose value 
can be structure-shared. In the course of grammar 
development, it is often necessary to change the 
"location" of a feature in order to get the right 
structuring of information. 
Such a change of the '~feature geometry" makes 
it necessary to change the path in all references 
to a feature. This is often done by introducing 
templates whose sole purpose is the abbreviation 
of a path to a feature. 
ProFIT provides a mechanism to search for 
paths to features automatically provided that the 
sortal restrictions for the feature values are strong 
enough to ensure that there is a unique minimal 
path. A path is minimal if it does not contain any 
repeated features or sorts. 
3These clauses assume appropriate declarations for 
the sort elist, and for the features synsem, local, 
cat, subcat, head, dtrs and head_dtr. 
182 
The sort from which to start the feature search 
must either be specified explicitly (7) or implicitly 
given through the sortal restriction of a feature 
value, in which case the sort can be omitted and 
the expression (8) can be used. 
Sort >>> Feature ! Term (7) 
>>> Feature ! Term (8) 
The following clause makes use of feature search 
to express the Head Feature Principle (hfp). 
hfp( sign>>>head !X 
dtrs!head_dtr} >>>head!X ). 
While this abbreviation for feature paths is new 
for formal description languages, similar abbrevi- 
atory conventions are often used in linguistic pub- 
lications. They are easily and unambiguously un- 
derstood if there is only one unique path to the 
feature which is not embedded in another struc- 
ture of the same sort. 
2.5 Templates 
The purpose of templates is to give names to 
frequently used structures. In addition to being 
an abbreviatory device, the template mechanism 
serves three other purposes. 
• Abstraction and interfacing by providing a 
fixed name for a value that may change, 
• Partial evaluation, 
• Functional notation that can make specifica- 
tions easier to understand. 
Templates are defined by expressions of the 
form (9), where Name and Value can be arbitrary 
ProFIT terms, including variables, and template 
calls. There can be several template definitions 
with the same name on the left-hand side (rela- 
tional templates). Since templates are expanded 
at compile time, template definitions must not be 
recursive. 
Name := Value, (9) 
Templates are called by using the template 
name prefixed with © in a ProFIT term. 
Abstraction makes it possible to change data 
structures by changing their definition only at one 
point. Abstraction also ensures that databases 
(e.g. lexicons) which make use of these abstrac- 
tions can be re-used in "different kinds of appli- 
cations where different datastructures represent 
these abstractions. 
Abstraction through templates is also useful for 
defining interfaces between grammars and pro- 
cessing modules. If semantic processing must 
access the semantic representations of different 
grammars, this can be done if the semantic mod- 
ule makes use of a template defined for each gram- 
mar that indicates where in the feature structure 
the semantic information is located, as in the fol- 
lowing example for HPSG. 
semantics (synsem ! local !cont ! Sem) : = Sem. 
Partial evaluation is achieved when a structure 
(say a principle of a grammar) is represented by 
a template that gets expanded at compile time, 
and does not have to be called as a goal during 
processing. 
We show the use of templates for providing 
functional notation by a simple example, in which 
the expression ©first(X) stands for the first ele- 
ment of list X, and ~rest(X) stands for the tail 
of list X, as defined by the following template def- 
inition. 
first(\[First J Rest\]) := First. 
rest(\[FirstlRest\]) := Rest. 
The member relation can be defined with the 
following clauses, which correspond very closely 
to the natural-language statement of the member 
relation given as comments. Note that expansion 
of the templates yields the usual definition of the 
member relation in Prolog. 
Y, The first element of a list 
~, is a member of the list. 
member (@first (List), List). 
~, Element is a member of a list 
Y, if it is a member of the rest of the list 
member(Element,List) :- 
member (Element, @rest (List)). 
The expressive power of an n-place template is 
the same as that of an n+l place fact. 
2.6 Disjunction 
Disjunction in the general case cannot be encoded 
in a Prolog term representation. 4 Since a general 
treatment of disjunction would involve too much 
computational overhead, we provide disjunctive 
terms only as syntactic sugar. Clauses containing 
disjunctive terms are compiled to several clauses, 
one for each consistent combination of disjuncts. 
Disjunctive terms make it possible to state facts 
that belong together in one clause, as the follow- 
ing formulation of the Semantics Principle (s em_p) 
of HPSG, which states that the content value of a 
head-adjunct structure is the content value of the 
adjunct daughter, and the content value of the 
other headed structures (head-complement, head- 
marker, and head-filler structure) is the content 
value of the head daughter. 
sem_p ( (<head_adj 
>>>cont!X ~ >>>adj dtr!>>>cont!X ) 
or 
( ( <head_comp 
or <head_marker 
or <head_filler 
) ~ 
>>>coat !Y ~ >>>head_dtr !>>>coat !Y ) 
). 
For disjunctions of atoms, there exists a Prolog 
term representation, which is described below. 
4see the complexity analysis by Brew (Brew, 1991). 
183 
2.7 Finite Domains 
For domains involving only a finite set of atoms as 
possible values, it is possible to provide a Prolog 
term representation (due to Colmerauer, and de- 
scribed by Mellish (Mellish, 1988)) to encode any 
subset of the possible values in one term. 
Consider the agreement features person (with 
values 1, 2 and 3) and number (with values sg 
and pl). For the two features together there 
are six possible combinations of values (l&;sg, 
2&sg, 3&sg, l&pl, 2&pl, 3&pl). Any subset of 
this set of possible values can be encoded as one 
Prolog term. The following example shows the 
declaration needed for this finite domain, and 
some clauses that refer to subsets of the possi- 
ble agreement values by making use of the logi- 
cal connectives " (negation), & (conjunction), or 
(disjunction).5 
agr fin_dom \[1,2,3\] * \[sg,pl\]. 
verb(sleeps,3&sg). 
verb(sleep, -(3&sg)). 
verb(am, l&sg). 
verb(is, 3&sg). 
verb(are, 2 or pl). 
np('I' , l&sg) . 
np(you, 2~agr). 
This kind of encoding is only applicable to do- 
mains which have no coreferences reaching into 
them, in the example only the agreement features 
as a whole can be coreferent with other agreement 
features, but not the values of person or number 
in isolation. This kind of encoding is useful to 
avoid the creation of choice points for the lexicon 
of languages where one inflectional form may cor- 
respond to different feature values. 
2.8 Cyclic Terms 
Unlike Prolog, the concrete syntax of ProFIT al- 
lows to write down cyclic terms by making use of 
conjunction: 
x & ~(x). 
Cyclic terms constitute no longer a theoretical 
or practical problem in logic programming, and al- 
most all modern Prolog implementations can per- 
form their unification (although they can't print 
them out). Cyclic terms arise naturally in NLP 
through unification of non-cyclic terms, e.g., the 
Subcategorization Principle and the Spec Princi- 
ple of HPSG. 
ProFIT supports cyclic terms by being able to 
print them out as solutions. In order to do this, 
SThe syntax for finite domain 
terms is Terra,Domain. However, when atoms from a 
finite domains are combined by the conjunction, dis- 
junction and negation connectives, the specification 
of the domain can be omitted. In the example, the 
domain must only be specified for the value 2, which 
could otherwise be confused with the integer 2. 
the dreaded occur check must be performed. Since 
this must be done only when results are printed 
out as ProFIT terms, it does not affect the run- 
time performance. 
3 From ProFIT terms to Prolog 
terms 
3.1 Compilation of Sorted Feature Terms 
The compilation of sorted feature terms into a 
Prolog term representation is based on the follow- 
ing principles, which are explained in more detail 
in (Mellish, 1988; Mellish, 1992; Schgter, 1993; 
Erbach, 1994). 
• The Prolog representation of a sort is an in- 
stance of the Prolog representation of its su- 
persorts. 
• Features are represented by arguments. If a 
feature is introduced by a subsort, then the 
argument is added to the term that further 
instantiates its supersort. 
• Mutually exclusive sorts have different func- 
tots at the same argument position, so that 
their unification fails. 
We illustrate these principles for compiling 
sorted feature terms into Prolog terms with an 
example from aPse. The following declaration 
states that the sort sign has two mutually ex- 
clusive subsorts lexical and phrasal and intro- 
duces four features. 
sign > \[lexical,phrasal\] 
intro \[phon, 
synsem, 
qstore, 
retrieved\]. 
In the corresponding Prolog term representa- 
tion below, the first argument is a variable whose 
only purpose is being able to test whether two 
terms are coreferent or whether they just happen 
to have the same sort and the same values for all 
features. In case of extensional sorts (see section 
2.1), this variable is omitted. The second argu- 
ment can be further instantiated for the subsorts, 
and the remaining four arguments correspond to 
the four features. 
$s ign (Var, LexPhras, Phon, Synsem, qstore, Retriev) 
The following declaration introduces two sort 
hierarchy "dimensions" for subsorts of phrasal, 
and one new feature. The corresponding Prolog 
term representation instantiates the representa- 
tion for the sort sign further, and leaves argument 
positions that can be instantiated further by the 
subsorts of phrasal, and for the newly introduced 
feature daughters. 
phrasal > \[headed,non_headed\] * \[decl,int,rel\] 
intro \[daughters\]. 
184 
$sign(yar, $phrasal(Phrasesort,Clausesort,Dtrs), 
Phon, 
Synsem, 
Qstore, 
Retrieved) 
3.2 Compilation of Finite Domains 
The compilation of finite domains into Prolog 
terms is performed by the "brute-force" method 
described in (Mellish, 1988). A finite domain with 
n possible domain elements is represented by a 
Prolog term with n + 1 arguments. Each domain 
element is associated with a pair of adjacent argu- 
ments. For example, the agreement domain agr 
from section 2.7 with its six elements (l&sg, 2&sg, 
3&sg, l~:pl, 2~:pl, 3&pl) is represented by a Pro- 
log term with seven arguments. 
Sagr(1,A,B,C,D,E,O) 
Note that the first and last argument must be 
different. In the example, this is achieved by in- 
stantiation with different atoms, but an inequal- 
ity constraint (Prolog I\['s dif) would serve the 
same purpose. We assume that the domain el- 
ement l~zsg corresponds to the first and second 
arguments, 2&sg to the second and third arguem- 
nts, and so on, as illustrated below. 
Sagr( 1 , h , B , C , D , E , 0 ) 
lsg 2sg 3sg lpl 2pl 3pl 
A domain description is translated into a Pro- 
log term by unifying the argument pairs that are 
excluded by the description. For example, the 
domain description 2 or pl excludes l&sg and 
3&sg, so that the the first and second argument 
are unified (l~sg), as well as the third and fourth 
(3&sg). 
$agr(1,1,X,X,D,E,0) 
When two such Prolog terms are unified, the 
union of their excluded elements is computed by 
unificatation, or conversely the intersection of the 
elements which are in the domain description. 
The unification of two finite domain terms is suc- 
cessful as long as they have at least one element 
in common. When two terms are unified which 
have no element in common, i.e., they exclude all 
domain elements, then unification fails because all 
arguments become unified with each other, includ- 
ing the first and last arguments, which are differ- 
ent. 
4 Implementation 
ProFIT has been implemented in Quintus and Sic- 
stus Prolog, and should run with any Prolog that 
conforms to or extends the proposed ISO Prolog 
standard. 
All facilities needed for the development of ap- 
plication programs, for example the module sys- 
tem and declarations (dynamic, multifile etc.) are 
supported by ProFIT. 
Compilation of a ProFIT file generates two 
kinds of files as output. 
1. Declaration files that contain information for 
compilation, derived from the declarations. 
2. A program file (a Prolog program) that con- 
tains the clauses, with all ProFIT terms com- 
piled into their Pro\]og term representation. 
The program file is compiled on the basis of 
the declaration files. If the input and output of 
the program (the exported predicates of a mod- 
ule) only make use of Prolog terms, and feature 
terms are only used for internal purposes, then the 
program file is all that is needed. This is for ex- 
ample the case with a grammar that uses feature 
terms for grammatical description, but whose in- 
put and output (e.g. graphemic form and logical 
form) are represented as normal Prolog terms. 
Declarations and clauses can come in any or- 
der in a ProFIT file, so that the declarations can 
be written next to the clauses that make use of 
them. Declarations, templates and clauses can be 
distributed across several files, so that it becomes 
possible to modify clauses without having to re- 
compile the declarations, or to make changes to 
parts of the sort hierarchy without having to re- 
compile the entire hierarchy. 
Sort checking can be turned off for debug- 
ging purposes, and feature search and handling 
of cyclic terms can be turned off in order to speed 
up the compilation process if they are not needed. 
Error handling is currently being improved to 
give informative and helpful warnings in case of 
undefined sorts, features and templates, or cyclic 
sort hierarchies or template definitions. 
For the development of ProFIT programs and 
grammars, it is necessary to give input and out- 
put and debugging information in ProFIT terms, 
since the Pro\]og term representation is not very 
readable. ProFIT provides a user interface which 
* accepts queries containing ProFIT terms, and 
translates them into Prolog queries, 
• converts the solutions to the Prolog query 
back into ProFIT terms before printing them 
out, 
• prints out debugging information as ProFIT 
terms. 
When a solution or debugging information is 
printed out, uninstantiated features are omit- 
ted, and shared structures are printed only once 
and represented by variables on subsequent oc- 
curences. 
A pretty-printer is provided that produces a 
neatly formatted screen output of ProFIT terms, 
and is configurable by the user. ProFIT terms can 
also be output in IATEX format, and an interface 
to the graphical feature editor Fegramed is fore- 
seen. 
185 
In order to give a rough idea of the efficiency 
gains of a compilation into Prolog terms instead 
of using a feature term unification algorithm im- 
plemented on top of Prolog, we have compared 
the runtimes with ALE and the Eisele-DSrre al- 
gorithm for unsorted feature unification for the 
following tasks: (i) unification of (unsorted) fea- 
ture structures, (ii) unification of inconsistent fea- 
ture structures (unification failure), (iii) unifica- 
tion of sorts, (iv) lookup of one of I0000 feature 
structures (e.g. lexical items), (v) parsing with 
an HPSG grammar to provide a mix of the above 
tasks. 
The timings obtained so far indicate that 
ProFIT is 5 to 10 times faster than a system which 
in~plements a unification algorithm on top of Pro- 
log, a result which is predicted by the studies of 
SchSter (SchSter, 1993) and the experience of the 
Core Language Engine. 
The ProFIT system and documentation are 
available free of charge by anonymous ftp (server: 
ftp.coli.uni-sb.de, directory: pub/profit). 
5 Conclusion 
ProFIT allows the use of sorted feature terms in 
Prolog programs and Logic Grammars without 
sacrificing the efficiency of Prolog's term unifi- 
cation. It is very likely that the most efficient 
commercial Prolog systems, which provide a ba- 
sis for the implementation of NLP systems, will 
conform to the proposed ISO standard. Since the 
ISO standard includes neither inheritance hierar- 
chies nor feature terms (which are indispensible 
for the development of large grammars, lexicons 
and knowledge bases for NLP systems), a tool 
like ProFIT that compiles sorted feature terms 
into Prolog terms is useful for the development of 
grammars and lexicons that can be used for ap- 
plications. ProFIT is not a grammar formalism, 
but rather aims to extend current and future for- 
malisms and processing models in the logic gram- 
mar tradition with the expressive power of sorted 
feature terms. Since the output of ProFIT com- 
pilation are Prolog programs, all the techniques 
developed for the optimisation of logic programs 
(partial evaluation, tabulation, indexing, program 
transformation techniques etc.) can be applied 
straightforwardly to improve the performance of 
sorted feature grammars. 
6 Acknowledgements 
This work was supported by 
• The Commission of the European Com- 
munities through the project LRE-61-061 
"Reusable Gratnmatical Resources", where it 
has been (ab-)used in creative ways to proto- 
type extensions for the ALEP formalism such 
as set descriptions, linear precedence con- 
straints and guarded constraints (Manand- 
hat, 1994; Manandhar, 1995). 
* Deutsche Forschungsgemeinschaft, Special 
Research Division 314 "Artificial Intelli- 
gence - Knowledge-Based Systems" through 
project N3 "Bidirectional Linguistic Deduc- 
tion" (BiLD), where it is used to compile 
typed feature grammars into logic grammars, 
for which bidirectional NLP algorithms are 
developed, and 
• Cray Systems (formerly PE-Luxembourg), 
with whom we had fruitful interaction con- 
cerning the future development of the ALEP 
system-. 
Some code for handling of finite domains was 
adapted from a program by Gertjan van Noord. 
Wojciech Skut and Christian Braun were a great 
help in testing and improving the system. Thanks 
to all the early users and ~-testers for discover- 
ing bugs and inconsistencies, and for providing 
feedback and encouragement. Special thanks for 
service with a smiley :-). 
References 
Hassan A'it-Kaci and Patrick Lincoln. 1989. Life, 
a naturM language for natural language. T. A. 
Informations, 30(1-2):37 - 67. 
H. Alshawi, D. J. Arnold, R. Backofen, D. M. 
Carter, J. Lindop, K. Netter, :I. Tsujii, and 
H. Uszkoreit. 1991. Eurotra 6/1: Rule for- 
mMism and virtual machine design study -- Fi- 
nal report. Technical report, SRI International, 
Cambridge. 
Hiyan Alshawi, editor. 1991. The Core Language 
Engine. MIT Press. 
Chris Brew. 1991. Systemic classification and its 
efficiency. Computational Linguistics, 17(4):375 
- 408. 
Bob Carpenter. 1992. The logic of typed feature 
structures. Cambridge Tracts in Theoretical 
Computer Science. Cambridge University Press, 
Cambridge. 
Bob Carpenter, 1993. ALE Version ~: User Man- 
ual. University of Pittsburgh. 
Michael Covington. 1989. GULP 2.0: an exten- 
sion of Prolog for unification-based grammar. 
Technical Report AI-1989-01, Advanced Com- 
putational Methods Center, University of Geor- 
gia. 
Jochen DLrre and Michael Dorna. 1993. CUF - 
A formalism for linguistic knowledge represen- 
tation. In Jochen DLrre, editor, Computational 
Aspects of Constraint-Based Linguistic Descrip- 
tion. Deliverable RI.P.A. DYANA-2 - ESPRIT 
Basic Research Project 6852. 
186 
Martin Emele and R4mi Zajac. 1990. Typed 
unification grammars. In Proceedings of the 
13th International Conference on Computa- 
tional Linguistics, Helsinki. 
Gregor Erbach. 1994. Multi-dimensional inheri- 
tance. In H. Trost, editor, Proceedings of KON- 
VENS '9.~, pages 102 - 111, Vienna. Springer. 
Susan Beth Hirsh. 1986. P-PATth A compiler 
for unification-based grammars. Master's the- 
sis, Stanford University, Stanford, CA. 
Draft ISO Standard for the Prolog language, 
ISO/IEC JTC1 SC22 WG17 Nl10 "Prolog: 
Part 1, General core". 
Hans-Ulrich Krieger and Ulrich Schlfer. 
1994. 7-79£--a type description language for 
constraint-based grammars. In Proceedings of 
the 15th International Conference on Computa- 
tional Linguistics, COLING-94, Kyoto, Japan. 
Suresh Manandhar. 1994. An attributive logic 
of set descriptions and set operations. In 32nd 
Annual Meeting of the Association for Compu- 
tational Linguistics (A CL), pages 255 - 262, Las 
Cruces, NM. 
Suresh Manandhar. 1995. Deterministic con- 
sistency checking of LP constraints. In Sev- 
enth Conference of the European Chapter of 
the Association for Computational Linguistics 
(EA CL), Dublin. 
Johannes Matiasek. 1994. Conditional con- 
straints in a CLP-based HPSG implementation. 
In Harald Trost, editor, KONVENS '94, pages 
230 - 239, Vienna. 
Christopher S. Mellish. 1988. hnplementing sys- 
temic classification by unification. Computa- 
tional Linguistics, 14(1):40-51. 
Christopher S. Mellish. 1992. Term-encodable de- 
scription spaces. In D. R. Brough, editor, Logic 
Programming: New Frontiers, pages 189 - 207. 
Intellect, Oxford. 
Giinter Neumann and Gertjan van Noord. 1992. 
Self-monitoring with reversible grammars. In 
Proceedings of the 14th International Confer- 
ence on Computational Linguistics, Nantes, F. 
Giinter Neumann. 1994. A Uniform Computa- 
tional Model for Natural Language Parsing and 
Generation. Ph.D. thesis, Universitit des Saar- 
landes, Saabriicken. 
Christer Samuelsson. 1994. Fast Natural- 
Language Parsing Using Explanation-Based 
Learning. Ph.D. thesis, The Royal Institute of 
Technology and Stockholm University, Stock- 
holm. 
Andreas P. SchSter. 1993. Compiling feature 
structures into terms: A case study in Prolog. 
Technical Report RP-55, University of Edin- 
burgh, Centre for Cognitive Science. 
Gert Smolka, Martin Henz, and J6rg Wiirtz. 
1995. Object-oriented concurrent constraint 
programming in Oz. In P. van Hentenryck and 
V. Saraswat, editors, Principles and Practice of 
Constraint Programming, chapter 2, pages 27- 
48. The MIT Press. 
Appendix: BNF for ProFIT Terms 
PFT := <Sort 
Feature!PFT 
PFT & PFT 
PROLOGTEKM 
FINDOM 
@Template 
, FFT 
'' PFT 
>>>Feature!PFT 
Sort>>>Feature!PFT 
PFT or PFT 
\[I. 
\[2. 
\[3 
\[4 
Is 
\[6 \['z 
\[8 
\[9 
\[10. 
\[11. 
FINDOM := FINDOM@FiniteDomainName 
I -FINDOM 
I FINDOM & FINDOM 
\[ FINDOM or FINDOM 
\[ Atom 
Term of a sort Sort \] 
Feature-Value pair \] 
Conjunction of terms \] 
Any Prolog term \] 
Finite Domain term, BNF see below \] 
Template call \] 
Quoted term, is not translated \] 
Double-quoted, main functor not translated \] 
Search for a feature \] 
short for <Sort • >>>Feature!PFT \] 
Disjunction; expands to multiple terms \] 
187 
