The next two sections, covering the constraint logic programming and phrase structure components of ALE, simply describe how to write ALE programs and how they will be executed. Discussion of interacting with the system itself follows the description of the programming language ALE provides.
The definite logic programming language built into ALE is a constraint logic programming (CLP) language, where the constraint system is the attribute-value logic described above. Thus, it is very closely related to both Prolog and LOGIN. Like Prolog, definite clauses may be defined with disjunction, negation and cut. The definite constraints of ALE are executed in a depth-first, left to right search, according to the order of clauses in the database. ALE performs last call optimization, but does not perform any clause indexing.
Those familiar with Prolog should have no trouble adapting that
knowledge to programming with definite clauses in ALE. The only
significant difference is that first-order terms are replaced with
descriptions of feature structures.
While it is not within the scope of this user's guide to detail the logic programming paradigm, much less CLP, this section will explain all that the user familiar with logic programming needs to know to exploit the special features of ALE. For background, the user is encouraged to consult Sterling and Shapiro (1986) with regard to general logic programming techniques, most of which are applicable in the context of ALE, and Aït-Kaci and Nasr (1986) for more details on programming with sorted feature structures. For more advanced material on programming in Prolog with a compiler, see O'Keefe (1990). The general theory of CLP is developed in a way compatible with ALE in Höhfeld and Smolka (1988). Of course, since ALE is literally an implementation of the theory found in Carpenter (1992), the user is strongly encouraged to consult Chapter 14 of that book for full theoretical details.
The syntax of ALE's logic programming component is broadly similar to that of Prolog, with the only difference being that first-order terms are replaced with attribute-value logic descriptions. The language in which clauses are expressed in ALE is given in BNF as:
<clause> ::= <literal> if <goal>.
<literal> ::= <pred_sym>
| <pred_sym>(<desc_seq>)
<desc_seq> ::= <desc>
| <desc>,<desc_seq>
<goal> ::= true
| <literal>
| (<goal>,<goal>)
| (<goal>;<goal>)
| (<desc> =@ <desc>)
| !
| (\+ <goal>)
| prolog(<prolog_goal>)
Just as in Prolog, predicate symbols must be Prolog atoms. This is a
more restricted situation than the definite clause language discussed
in Carpenter (1992), where literals were also represented as feature
structures and described using attribute-value logic. Also note that
ALE requires every clause to have a body, which might simply be
the goal true. There must be whitespace around the
if operator, but none is required around the conjunction comma,
the disjunction semicolon, the cut symbol !, or the
unprovability symbol 
+. Parentheses, in general, may
be dropped and reconstructed based on operator precedences. The
precedence is such that the comma binds more tightly than the
semicolon, while the unprovability symbol binds the most tightly.
Both the semicolon and comma are right associative.
The operational behavior of ALE is nearly identical to Prolog with respect to goal resolution. That is, it evaluates a sequence of goals depth-first, from the left to right, using the order of clauses established in the program. The only difference arises from the fact that, in Prolog, literals can't introduce non-determinism. In ALE, due to the fact that disjunctions can be nested inside of descriptions, additional choice points might be created both in matching literals against the heads of clauses and in expanding the literals within the body of a clause. In evaluating these choices, ALE maintains a depth-first left to right strategy.
We begin with a simple example, the member/2 predicate:
member(X,hd:X) if
true.
member(X,tl:Xs) if
member(X,Xs).
As in Prolog, ALE clauses may be read logically, as
implications, from right to left. Thus the first clause above states
that X is a member of a list if it is the head of a
list . The second clause states that X is a member of
a list if X is a member of the tail of the list, Xs. Note
that variables in ALE clauses are used the same way as in
Prolog, due to the notational convention of our description language.
Further note that, unlike Prolog, ALE requires a body for every
clause. In particular, note that the first clause above has the
trivial body true . The compiler is clever enough to
remove such goals at compile time, so they do not incur any run-time
overhead.
Given the notational convention for lists built into ALE, the above program could equivalently be written as:
member(X,[X|_]) if
true.
member(X,[_|Xs]) if
member(X,Xs).
But recall that ALE would expand [X|_] as
(hd:X,tl:_). Not only does ALE not support anonymous variable
optimizations, it also creates a conjunction of two descriptions,
where hd:X would have sufficed. Thus the first method is not
only more elegant, but also more efficient.
Due to the fact that lists have little hierarchical structure, list manipulation predicates in ALE look very much like their correlates in Prolog. They will also execute with similar performance. But when the terms in the arguments of literals have more interesting taxonomic structure, ALE actually provides a gain over Prolog's evaluation method, as pointed out by Aït-Kaci and Nasr (1986). Consider the following fragment drawn from the syllabification grammar in the appendix, in which there is a significant interaction between the inheritance hierarchy and the definite clause less_sonorous/2:
segment sub [consonant,vowel].
consonant sub [nasal,liquid,glide].
nasal sub [n,m].
n sub [].
m sub [].
liquid sub [l,r].
l sub [].
r sub [].
glide sub [y,w].
y sub [].
w sub [].
vowel sub [a,e,i]
a sub [].
e sub [].
i sub [].
less_sonorous_basic(nasal,liquid) if true.
less_sonorous_basic(liquid,glide) if true.
less_sonorous_basic(glide,vowel) if true.
less_sonorous(L1,L2) if
less_sonorous_basic(L1,L2).
less_sonorous(L1,L2) if
less_sonorous_basic(L1,L3),
less_sonorous(L3,L2).
For instance, the third clause of less_sonorous_basic/2, being
expressed as a relation between the types glide and vowel,
allows solutions such as less_sonorous_basic(w,e), where
glide and vowel have been instantiated as the particular
subtypes w and e. This fact would not be either as
straightforward or as efficient to code in Prolog, where relations
between the individual letters would need to be defined. The loss in
efficiency stems from the fact that Prolog must either code all 14
pairs represented by the above three clauses and type hierarchy, or
perform additional logical inferences to infer that w is a
glide, and hence less sonorous than the vowel e. ALE, on
the other hand, performs these operations by unification, which, for
types, is a simple table look-up.
All in all, the three clauses for less_sonorous_basic/2 given
above represent relations between 14 pairs of letters. Of course, the
savings is even greater when considering the transitive closure of
less_sonorous_basic/2, given above as less_sonorous/2, and
would be greater still for a type hierarchy involving a greater degree
of either depth or branching.
While we do not provide examples here, suffice it to say that cuts , negation , conjunction and disjunction work exactly the same as they do in Prolog. In particular, cuts conserve stack space representing backtracking points, disjunctions create choice points and negation is evaluated by failure, with the same results on binding as in Prolog.
The definite clause language also allows arbitrary prolog goals, using the predicate, prolog(<prolog_goal>) . This is most useful when used with the Prolog predicates, assert and retract , which provide ALE users with access to the Prolog database, and with I/O statements (these are quite useful for debugging definite clauses). Because of the way in which ALE compiles definite clauses, side effects created by prolog hooks may not occur properly in cases where a clause can never succeed. For example, with the following two definitions:
p if
prolog(write('blah')).
q if
p,
foo((X,a),(X,b)).
If a and b are not unifiable, the clause for q can
never succeed. In ALE, not only will it not succeed, but the
message 'blah' will not be printed either. This is because
ALE checks the descriptions of subgoals (like the one for foo)
before it actually calls the subgoals in cases such as this. This
behaviour will be corrected in a future version. Until then, the user
may need to add extra subgoals to avoid this. We can rewrite the above
predicates as:
p if
prolog(write('blah')).
q if
p,
q2(X,Y),
foo(X,Y).
q2((X,a),(X,b)) if true.
for example, to remedy this particular case.
Should prolog_goal contain a variable that has been instantiated to an ALE feature structure, this will appear to Prolog as ALE's internal representation of that feature structure. Feature structures can be asserted and retracted, however, without regard to their internal structure. The details of ALE's internal representation of feature structures can be found in Carpenter (1993).
Another side effect of not directly attaching inequations to feature structures is that if a feature structure with inequations is asserted and a copy of it is later instantiated from the Prolog database or retracted, the copy will have lost the inequations. For this reason, asserting feature structures with inequations should be avoided.
There is a special literal predicate, =@ , used with
infix notation, which is true when its arguments are token-identical.
As with inequations, which forbid token-identity, the =@
operator is of little use unless multiply occurring variables are used
in its arguments' descriptions. Note, however, that while inequations
(=\=) and equations (==) are part of the description
language, =@ is a definite clause predicate, and cannot be used
as a description. It is more important to note that while the
negation of the structure-identity operator (==), namely the
inequation (=\=), is monotonic when interpreted persistently,
the negation of the token-identity operator ( =@), achieved by
using it inside the argument of the \+ operator, is
non-monotonic, and thus its use should be avoided.
It is significant to note that clauses in ALE are truly definite in the sense that only a single literal is allowed as the head of a clause, while the body can be a general goal. In particular, disjunctions in descriptions of the arguments to the head literal of a clause are interpreted as taking wide scope over the entire clause, thus providing the effect of multiple solutions rather than single disjunctive solutions. The most simple example of this behavior can be found in the following program:
foo((b;c)) if true. bar(b) if true. baz(X) if foo(X), bar(X).Here the query foo(X) will provide two distinct solutions, one where X is of type b, and another where it is of type c. Also note that the queries foo(b) and foo(c) will succeed. Thus the disjunction is equivalent to the two single clauses:
foo(b) if true. foo(c) if true.In particular, note that the query baz(X) can be solved, with X instantiated to an object of type b. In general, using embedded disjunctions will usually be more efficient than using multiple clauses in ALE, especially if the disjunctions are deeply nested late in the description. On the other hand, cuts can be inserted for control with multiple clauses, making them more efficient in some cases.
The type constraints mentioned in the last chapter can also incorporate relational constraints defined by definite clauses, with the optional operator goal . Consider the following example from HPSG:
word cons W
goal (single_rel_constraint(W),
clausal_rel_prohibition(W)).
In this example, the constraint from the description language is
simply the variable W, which is used to match any feature
structure of type word. That feature structure is then passed
as an argument to the two procedural attachments
single_rel_constraint/1 and clausal_rel_prohibition/1,
which each represent a principle from HPSG which governs words
(among other objects). Notice that the goal, when non-literal, must
occur within parentheses.
While every type constraint must have a description, procedural attachments are optional. If they do occur, they occur after the description. The syntax is given in BNF as:
<cons_spec> ::= <type> cons <desc>
| <type> cons <desc>
goal <goal>