Previous Up Next

18.11  Details of the Execution Mechanism

18.11.1  Particularities of Waking by Unification

Goals that are suspended on the inst or bound waking conditions are woken by unifications of their suspending variables. One suspending variable can be responsible for delaying several goals, on the other hand one goal can be suspended on several suspending variables (as alternative waking conditions). This means that when one suspending variable is bound, several delayed goals may be woken at once. The order of executing woken suspended goals does not necessarily correspond to the order of their suspending. It is in fact determined by their priorities and is implementation-dependent within the same priority group.

The waking process never interrupts unifications and/or a sequence of simple goals. Simple goals are a subset of the built-ins and can be recognised by their call_type flag as returned by get_flag/3, simple goals having the type external. Note also that some predicates, e.g., is/2, are normally in-line expanded and thus simple, but can be regular when inlining is suppressed, e.g., by the pragma(noexpand) directive.

ECLiPSe treats simple predicates (including unification) always as a block. Delayed goals are therefore woken only at the end of a successful unification and/or a sequence of simple goals. If a suspending variable is bound in a simple goal, the suspended goals are woken only at the end of the last consecutive simple goal or at the clause end. If the clause contains simple goals at the beginning of its body, they are considered part of the head (extended head) and if a suspending variable is bound in the head unification or in a simple predicate in the extended head, the corresponding delayed goals are woken at the end of the extended head.

A cut is also considered a simple goal and is therefore always executed before waking any pending suspended goals. This is important to know especially in the situations where the cut acts like a guard, immediately after the clause neck or after a sequence of simple goals. If the goals woken by the head unification or by the extended head are considered as constraints on the suspending variables, the procedure will not behave as expected. For example

filter(_P,[],[]) :- !.
filter(P,[N|LI],[N|NLI]) :-
        N mod P =\= 0,
filter(P,[N|LI],NLI) :-

delay integers(_, List) if var(List).
integers(_, []).
integers(N, [N|Rest]) :-
        N1 is N + 1,
        integers(N1, Rest).

?- integers(2, Ints), filter(2, Ints, [X1,X2]).

The idea here is that integers/2 fills a list with integers on demand, i.e., whenever new list elements appear. The predicated filter/3 removes all integers that are a multiple of P. In the example query, the call to integers/2 initially delays. When filter/3 is called, Ints gets instantiated in the head unification of the second clause of filter/3, which will wake up integers/2. However, since the second clause of filter/3 has an extended head which extends up to the cut, integers/2 will not actually be executed until after the cut. Therefore, N is not yet instantiated at the time of the arithmetic test and causes an error message.

The reason why delayed goals are woken after the cut and not before it is that neither of the two possibilities is always the intended or the correct one, however when goals are woken before the cut, there is no way to escape it and wake them after, and so if a nondeterministic goal is woken, it is committed by this cut which was most probably not intended. On the other hand, it is always possible to force waking before the cut by inserting a regular goal before it, for example true/0, so the sequence

true, !

can be viewed as a special cut type.

As a consequence, the example can be fixed by inserting true at the beginning of the second clause. However, a preferable and more robust way is using the if-then-else construct, which always forces waking suspended goals before executing the condition. This would also be more efficient by avoiding the creation of a choice point:

filter(P,[N|LI],LL) :-
        (N mod P =\= 0 ->
                LL = [N|NLI],
                filter(P, LI, NLI)

18.11.2  Cuts and Suspended Goals

The cut relies on a fixed order of goal execution in that it discards some choice points if all goals preceding it in the clause body have succeeded. If some of these goals delay without being woken before the cut, or if the head unification of the clause with the cut wakes any nondeterministic delayed goal, the completeness of the resulting program is lost and there is no clean way to save it as long as the cut is used.

The user is strongly discouraged to use non-local cuts together with coroutining, or to be precisely aware of their scope. The danger of a cut is twofold:

Previous Up Next