From: Joachim Schimpf <joachim.schimpf_at_...269...>

Date: Mon, 28 Mar 2011 16:30:16 +1100

Date: Mon, 28 Mar 2011 16:30:16 +1100

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. -- JoachimReceived on Mon Mar 28 2011 - 05:30:28 CEST

*
This archive was generated by hypermail 2.2.0
: Mon Jul 09 2018 - 02:05:29 CEST
*