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

Hi Joachim,

Many thanks for the detailed answer. 

Let me try to explain why I was thinking about using externals.

There is a software system, call it S, that tries to 
find "good" values for a number of parameters p_1,..,p_n
(mostly integers/reals). To do that, S calls a number
of algorithms A_1,...,A_k with concrete values for the
parameters p_i. It observes what outputs it gets from
each algorithm. Then it tries different values
for p_i, running again the algorithms on the new values;
and so on. It continues randomly "trying" different
values for p_i until the results obtained from the
algorithms are deemed good enough. I intuitively 
thought (but might well have been wrong) that it 
may be possible to explicitly encode the "logic"
(so to speak) of what constitutes good enough values 
for the parameters via proper Eclipse constraints;
and then call in the algorithms dynamically (as
externals) to generate the needed output values. 

Whether or not this would at all speed up the search, 
I don't know. There are two notions of cost here: the cost
of running the various algorithms A_j, and the
cost of trying different values for the parameters
by expanding the search tree. It's the latter part
that I thought might be improvable by constraint
search, b/c currently it's done in a willy-nilly
fashion. But maybe I was wrong. From your answer
it seems that using Eclipse+externals would probably 
degenerate into a similarly inefficient generate+test
approach. I'll have to think a bit more about it
(any suggestions/feedback would be appreciated).
Thanks again!


--- On Mon, 3/28/11, Joachim Schimpf <joachim.schimpf_at_monash.edu> wrote:

> From: Joachim Schimpf <joachim.schimpf_at_monash.edu>
> Subject: Re: [eclipse-clp-users] External procedure constraints
> To: eclipse-clp-users_at_lists.sourceforge.net
> Date: Monday, March 28, 2011, 1:30 AM
> 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
> 
> 
> 
> 
> 
> ------------------------------------------------------------------------------
> Enable your software for Intel(R) Active Management
> Technology to meet the
> growing manageability and security demands of your
> customers. Businesses
> are taking advantage of Intel(R) vPro (TM) technology -
> will your software 
> be a part of the solution? Download the Intel(R)
> Manageability Checker 
> today! http://p.sf.net/sfu/intel-dev2devmar
> _______________________________________________
> ECLiPSe-CLP-Users mailing list
> ECLiPSe-CLP-Users_at_lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
>