Definite Clauses

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 clauses 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.^5.1Those 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 differences being that first-order terms are generally replaced with attribute-value logic descriptions, and a different language of block conditionals for co-routining (see p. ). The language in which clauses are expressed in ALE is given in BNF as:

  <clause> ::= <literal> if <goal>.

  <literal> ::=  <pred_sym>
              |  <pred_sym>(<seq(desc)>)

  <goal> ::= true
           | <literal>
           | (<goal>,<goal>)
           | (<goal>;<goal>)
           | (<desc> =@ <desc>)
           | (<cut_free_goal> -> <goal>)
           | (<cut_free_goal> -> <goal> ; <goal>)
           | !
           | (\+ <goal>)
           | prolog(<prolog_goal>)
           | when(<cond>,<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 or shallow cut symbols !,->, or the unprovability symbol $\setminus$+. 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, terms cannot 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:^5.2

  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.^5.3All 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, shallow 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 perhaps 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, which can be quite useful for debugging definite clauses.

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 and Penn (1996), and briefly on p. .

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. In general, passing feature structures with inequations to Prolog hooks should be avoided.

Because the enforcement of extensionality is delayed in ALE, a variable which is instantiated to an extensionally typed feature structure and then passed to a prolog hook may also not reflect token identities as a result of extensionality. Provided that there are no inequations (to which the user does not have direct access), this can be enforced within the hook by calling the ALE internal predicate extensionalise(FS,[]).

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 path 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.