Several binding options for Variable in Prolog

Question

I want to bind a Variable to several atoms in such way that later it will be unifiable with one of those atoms. Intuitively it should work like this (assuming that ; is disjunction of possible values):

    ?- X = (apple; pear), X = apple.
    X = apple.

    ?- X = (apple; pear), X = apple, X = pear.
    false.

    ?- X = (apple; pear; orange), X = (apple; orange).
    X = (apple; orange).

    ?- X = (apple; orange), X = (pear; orange).
    X = orange. 

    ?- X = (apple; orange), X = pear.
    false. 

As u see this idea is close to the concept of type hierarchies. So, I wonder is there some built in (meta-)predicates which makes easy to do such kind of things, or if there is some common way using some sort of data structure to model this, or otherwise I have to build this kind of predicates from scratch?

Answer 1

As you see from other answers, there is a straight-forward way to express this with Prolog, using either disjunctions (leaving choice-points), or by explicitly reasoning about sets and their intersections.

Another way is to use constraints, which let you defer goals until more is known: You can for example map your atoms to integers, and then express a variable's membership to a set as its having a specific domain of integers, using CLP(FD) constraints. Alternatively, you can implement a custom constraint solver that reasons over atoms, using attributed variables or Constraint Handling Rules (CHR). The key advantage in both cases is that you gain more freedom to reorder your goals, and the constraint reasoning is implicitly invoked when further constraints are posted.

EDIT: As an example, consider using CLP(FD) constraints to solve your task. With at most minimal modifications, the following example works in SICStus, SWI, YAP and other systems. Depending on your Prolog system, you may need to import suitable libraries to use some of these predicates:

fruit_integer(apple,  0).
fruit_integer(pear,   1).
fruit_integer(orange, 2).

variable_fruits(Var, Fruits) :-
        maplist(fruit_integer, Fruits, Integers),
        foldl(domain_, Integers, 1..0, D),
        Var in D.

domain_(E, D0, D0 \/ E).

The key idea in this case is to map fruits to integers, so that you can use CLP(FD) constraints to express everything that holds.

Your example queries and answers::

?- variable_fruits(X, [apple,pear]), fruit_integer(apple, X).
X = 0.

?- variable_fruits(X, [apple,pear]), 
   fruit_integer(apple, X),
   fruit_integer(pear, X).
false.

?- variable_fruits(X, [apple,pear,orange]),
   variable_fruits(X, [apple,orange]).
X in 0\/2.

?- variable_fruits(X, [apple,orange]),
   variable_fruits(X, [pear,orange]).
X = 2.

?- variable_fruits(X, [apple,orange]),
   fruit_integer(pear, X).
false.

Obviously, you can use fruit_integer/2 also in the other direction, and convert such integers and domains back to lists of atoms. I leave this as an easy exercise.

It is for this reason that CLP(FD) constraints are called constraints over finite domains: All finite domains can be mapped to finite subsets of integers. Hence, CLP(FD) constraints are not only useful to express integer arithmetic in general, but also to reason about arbitrary finite sets. See clpfd for more information.

A few additional notes:

• All most widely used Prolog systems ship with CLP(FD) constraints, making your solution quite portable if you use them.
• Some Prolog systems ship with dedicated constraints solvers for sets. This may be worth looking into if your system supports this.
• CHR is a useful language for defining custom propagation rules and is well worth looking into especially for more complex tasks.
• Using the attributed variables interface directly will render your solution less portable, so I recommend you use one of the higher-level approaches instead. Try CLP(FD) first (since it is easiest to apply), then have a look at CHR, and only then consider implementing a custom solver.

Answer 2

Though in my answer it was not clear how the problem is related to type hierarchy, it was triggered by the latter, and one efficient solution is given in the paper: AN OPTIMIZED PROLOG ENCODING OF TYPED FEATURE STRUCTURES, GERALD PENN, 1999. where the Colmerauer's method is used and simply saying:

'apple or pear' = f(0,_,1,1).
'pear or orange' = f(0,0,_,1).
'orange or apple' = f(0,X,X,1).
'apple' = f(0,1,1,1).
'orange' = f(0,0,0,1).
'pear' = f(0,0,1,1)

and all these denotations obey prolog matching: 'apple or pear' subsumes 'apple' and 'pear', unifying 'apple or orange' with 'apple or pear' gives 'apple'.

Answer 3

Maybe you're are using the wrong syntax:

?- X = apple ; X = pear.
X = apple ;
X = pear.

but I would go with the suggestion by Will Ness.

Answer 4

You can just use member/2:

24 ?- member(X, [apple, pear]), member(X, [apple]).
X = apple ;
false.

25 ?- member(X, [apple, pear]), member(X, [apple]), member(X, [pear]).
false.

26 ?- member(X, [apple, pear, orange]), member(X, [apple, orange]).
X = apple ;
X = orange.

27 ?- member(X, [apple, orange]), member(X, [pear, orange]).
X = orange.

28 ?- member(X, [apple, orange]), member(X, [pear]).
false.

Or model this with lists of possible values, using intersection/3 to narrow the possibilities:

35 ?- _X1=[apple, pear], intersection(_X1, [apple], X2).
X2 = [apple].

36 ?- _X1=[apple, pear], intersection(_X1, [apple], _X2), 
                         intersection(_X2, [pear], X3).
X3 = [].

37 ?- _X1=[apple, pear, orange], intersection(_X1, [apple, orange], X2).
X2 = [apple, orange].

38 ?- _X1=[apple, orange], intersection(_X1, [pear, orange], X2).
X2 = [orange].

39 ?- _X1=[apple, orange], intersection(_X1, [pear], X2).
X2 = [].