Next: Domain Terms Up: Finite Domains and Exclusions Previous: Finite Domains and Exclusions


Characteristic for logic programming (LP) is its uniform variable concept: the single construct of logical variables is usable in different modes (input, output, or mixed). However, mainly for efficiency (control) reasons, committed-choice languages have compromised this uniformity: they distinguish modes at the user level (e.g., `read-only' annotations). Similarly, finite domains, which turned out to be most useful in constraint systems [16], can entail a compromised variable concept: they introduce `domain' variables separately from logical variables, limiting which variables may be unified with which kind of term (e.g., domain variables must not be bound to logical variables).

The latter problem leads us to the issue of extending LP languages by a clean construct for finite domains (generally, types), deeply integrated with existing LP constructs. In other words, we come to this basic question: Is there a method of optional, predeclaration-free, variable domain restriction (generally, variable typing) fully in the spirit of logical variables? This can be answered affirmatively by applying the following principle: Instead of introducing a new kind of variable with an associated domain (type) and a possible value, regard the domain (type) as an initial value. A domain value can then be successively constrained or specialized (e.g. by intersecting it with other domain terms) until it ultimately fails or becomes an ordinary value. (The empty domain is identified with failure, the singleton domain with its single element.)

The `type-as-value' principle will also be applied to a new type-like construct, namely finite exclusions, complementary to finite domains. An exclusion term specifies the values that cannot be assigned to a variable. It becomes specialized on unification with other exclusions (here performing union!), fails when unified with one of its argument values, and transmutes to an ordinary value unequal to any of its arguments. (The empty exclusion is identified with success.)

On domain-exclusion unification the exclusion values are set-theoretically subtracted from the domain values. Thus, while a domain corresponds to a disjunction of solved equalities, an exclusion corresponds to a conjunction of solved disequalities, where `solved' stands for single-variable constraints. General disequality constraints were introduced to LP by PROLOG II/III [4]. By considering only the special case of solved (dis)equalities we can regard constraints as typed logical variables: all their value specializations can be handled as part of the unification routine of LP languages, without need for the goal-delaying mechanisms on which constraint languages are often based.

After having established finite domains and exclusions as values of variables, we will show that they may also be used `anonymously' anywhere a term can occur (e.g. as top-level arguments of clauses). The final step then is to allow domain and exclusion terms also as values returned by functions of functional LP extensions such as RELFUN [2]. Altogether, domains and exclusions become first-class citizens of cleanly extended relational, functional, and relational-functional languages.

Next: Domain Terms Up: Finite Domains and Exclusions Previous: Finite Domains and Exclusions

Harold Boley & Michael Sintek (