Re: [eclipse-clp-users] External procedure constraints

Mick Hallward wrote:
> Hi all,
> 
> I have a question about external procedures 
> (my apologies if the information can already
> be found in the manual or in the tutorial;
> I've searched both a good deal but couldn't
> get anywhere). The question is this: is it
> possible for a constraint to be an external
> procedure call? For instance, can I have 
> something like this: 
> 
> foo(X,Y) :- [X]:: 0 .. 100, X #>=20, X #\= 26, g(X,Y), indomain(X).
> 
> Suppose here that g(X,Y) is an arbitrary external 
> function (e.g. a function written in C or whatever)
> that relates X and Y. When I call foo, will an appropriate 
> value for X will be selected, according to the "normal" 
> constraints  X #>=20, X #\= 26 AND also according
> to the "external" relation g? 

I think we first have to clarify some terminology here.  You are
using procedure, constraint, function, relation.  So let's see:


'procedure'
-----------
Let's not use that word here (although I'm aware that the manual
sometimes uses 'procedure' instead of 'predicate' when talking
about the behaviour rather than the logical semantics).


'relation' and 'predicate'
--------------------------
You can of course talk about the 'relation' g/2 that you want to
hold between X and Y.  But to keep things uniform, let's say that
we want the 'predicate' g/2 to be satisfied for X and Y (in other
words, the predicate defines or describes the relation).
In Prolog, an example definition for such a predicate could be:

    g(3,7).
    g(9,1).
    g(4,5).

and there are basically two ways of using this definition:

(a) for _testing_ concrete tuples of values, giving true/false answers:

    ?- g(3,4).
    No (0.00s cpu)
    ?- g(4,5).
    Yes (0.00s cpu)

(b) for (nondeterministically) _generating_ valid value tuples:

    ?- g(X,Y).
    X = 3
    Y = 7
    Yes (0.00s cpu, solution 1, maybe more) ? ;
    X = 9
    Y = 1
    Yes (0.00s cpu, solution 2, maybe more) ? ;
    X = 4
    Y = 5
    Yes (0.00s cpu, solution 3)


'function'
----------
I see two uses of the word 'function' in this context:

(a) the 'characteristic function' f_g(X,Y)->bool of a predicate/relation,
which yields true when the predicate g(X,Y) is satisfied.  This is something
you can easily implement as an ECLiPSe 'external', but it can only be
used for the _testing_ scenario above.

(b) you could consider a 'directed' version of the predicate g(X,Y) where,
say, X is always given, and you compute Y from X, i.e. a function f_g(X)->Y.
This means, we consider a function as a restricted form of predicate,
where one argument is defined as the output, while the others are input.
This can be implemented easily as an 'external', as long as this restricted
predicate is really a mathematical function, i.e. has a unique result.


'constraint'
------------
Logically, a constraint is the same as a predicate or a relation.

However, in ECLiPSe, we use the word 'constraint' only when we are talking
about a predicate implementation that does something more sophisticated
than the _testing_ or _generating_ that we saw above.
For example, the library(propia) allows you to turn the above definition
of g/2 into an active constraint, as follows:

    ?- g(X,Y) infers ic.
    X = X{[3, 4, 9]}
    Y = Y{[1, 5, 7]}
    Delayed goals:
        g(X{[3, 4, 9]}, Y{[1, 5, 7]}) infers most
    Yes (0.00s cpu)

You see that this neither gives you a final true/false result, nor
does it generate concrete (X,Y) tuples.  Instead, it extracts _some_
information, e.g. the fact that X can only take values 3,4 or 9.
It does not, however, make it explicit that (3,1) is an invalid
tuple - this is left until a later stage in the execution.

This kind of behaviour is more difficult to achieve via an 'external',
because the external then needs to know how to deal with variables
(rather than concrete numerical values), and variable domains.
That said, many of the built-in constraints are in fact implemented
as externals, but they use lower-level knowledge of the data structures
of e.g. the ic-library.



To return to your original scenario:

> foo(X,Y) :- [X]:: 0 .. 100, X #>=20, X #\= 26, g(X,Y), indomain(X).

Let's trace how this is executed:

?- foo(X,Y).
  (1) 1 CALL  foo(X, Y)   %> creep
  (2) 2 CALL  '::_body'([X], 0 .. 100, eclipse)   %> skip
  (2) 2 EXIT  '::_body'([X{0 .. 100}], 0 .. 100, eclipse)   %> skip
  (3) 2 CALL  20 - X{0 .. 100} #=< 0   %> skip
  (3) 2 EXIT  20 - X{20 .. 100} #=< 0   %> skip
  (4) 2 CALL  -(26) + X{20 .. 100} #\= 0   %> skip
  (4) 2 EXIT  -(26) + X{[20 .. 25, 27 .. 100]} #\= 0   %> skip
  (5) 2 CALL  g(X{[20 .. 25, 27 .. 100]}, Y)   %>

The last line shows that your external for g/2 would be called with both
arguments being variables.  Unless you have built a smart 'constraint-style'
implementation for g/2, this won't work.


However, if you move the call to g/2 behind the indomain/1, the situation
is different:

> foo(X,Y) :- [X]:: 0 .. 100, X #>=20, X #\= 26, indomain(X), g(X,Y).

?- foo(X,Y).
  (1) 1 CALL  foo(X, Y)   %> creep
  (2) 2 CALL  '::_body'([X], 0 .. 100, eclipse)   %> skip
  (2) 2 EXIT  '::_body'([X{0 .. 100}], 0 .. 100, eclipse)   %> skip
  (3) 2 CALL  20 - X{0 .. 100} #=< 0   %> skip
  (3) 2 EXIT  20 - X{20 .. 100} #=< 0   %> skip
  (4) 2 CALL  -(26) + X{20 .. 100} #\= 0   %> skip
  (4) 2 EXIT  -(26) + X{[20 .. 25, 27 .. 100]} #\= 0   %> skip
  (5) 2 CALL  indomain(X{[20 .. 25, 27 .. 100]})   %> skip
  (5) 2 *EXIT  indomain(20)   %> skip
  (8) 2 CALL  g(20, Y)   %>

Since the indomain(X) picks actual values for X, the first argument of g/2
is now instantiated, and if you have a functional implementation f_g(X)->Y,
then you could now compute Y from X (or fail if there is no such Y).


If you have g/2 implemented as a test only, i.e. f_g(X,Y)->bool, then you
would also need to generate values for Y _before_ you can apply the test, so:

> foo(X,Y) :- [X,Y]:: 0 .. 100, X #>=20, X #\= 26, indomain(X), indomain(Y), g(X,Y).

?- foo(X,Y).
  (1) 1 CALL  foo(X, Y)   %> creep
  (2) 2 CALL  '::_body'([X, Y], 0 .. 100, eclipse)   %> skip
  (2) 2 EXIT  '::_body'([X{0 .. 100}, Y{0 .. 100}], 0 .. 100, eclipse)   %> skip
  (3) 2 CALL  20 - X{0 .. 100} #=< 0   %> skip
  (3) 2 EXIT  20 - X{20 .. 100} #=< 0   %> skip
  (4) 2 CALL  -(26) + X{20 .. 100} #\= 0   %> skip
  (4) 2 EXIT  -(26) + X{[20 .. 25, 27 .. 100]} #\= 0   %> skip
  (5) 2 CALL  indomain(X{[20 .. 25, 27 .. 100]})   %> skip
  (5) 2 *EXIT  indomain(20)   %> skip
  (8) 2 CALL  indomain(Y{0 .. 100})   %> skip
  (8) 2 *EXIT  indomain(0)   %> skip
  (11) 2 CALL  g(20, 0)   %>

The external for g is now called with two numeric argument, and can simply
return true or false.

Of course you see immediately that this is a poor approach ("generate and test"
rather than "constrained search"), as you would need to test all the 80*101
combinations of X and Y in order to find the valid ones among them.


To summarize: yes, externals can be real 'constraints', but that's quite hard
to implement.  Externals only for testing or directional/functional computation
are easy, but don't give you the desirable behaviour of actively cutting down
the search space.

To give you a suggestion for how to proceed, it would be useful to know what
kind of relation your g/2 is, and why you were thinking that an implementation
as an external might be a good idea.  It is probably possible to set up active
standard constraints based on some information returned by your externals.


-- Joachim