The usual purpose of suspending a goal is to wait and resume it later when more information about its arguments is available. In Logic Programming, this is usually the case when certain events related to variables occur. When such an event occurs, the suspended goal is passed to the waking scheduler which puts it at the appropriate place in the priority queue of woken goals and as soon as it becomes first in the queue, the suspended goal is executed.
The event which causes a suspended goal to be woken is usually related to one or more variables, for example variable instantiation, or a modification of a variable’s attribute. However, it is also possible to trigger suspension with symbolic events not related to any variable.
There are three very general standard waking conditions which can be used with any variable. They are, in order of increasing generality:
- inst:
- wake when a variable gets instantiated;
- bound:
- wake when a variable gets instantiated or bound to another variable;
- constrained:
- wake when a variable gets instantiated or bound to another variable or becomes otherwise constrained.
Each condition subsumes the preceding, more specific ones.
To wake a goal when a variable gets instantiated, the inst condition is used. For example the following code suspends a goal until variable X is instantiated:
?- suspend(writeln(woken(X)), 0, X->inst). X = X There is 1 delayed goal. Yes (0.00s cpu)
If this variable is later instantiated (bound to a non-variable), the goal executes in a data-driven way:
?- suspend(writeln(woken(X)), 0, X->inst), X = 99. woken(99) X = 99 Yes (0.00s cpu)
If we specify several instantiation conditions for the same goal, the goal will wake up as soon as the first of them occurs:
?- suspend(writeln(woken(X,Y)), 0, [X,Y]->inst), X = 99. woken(99, Y) X = 99 Y = Y Yes (0.00s cpu)
It is not possible to specify a conjunction of conditions directly!
Let us now suppose we want to implement a predicate succ/2, such that succ(X, Y) is true when Y is the next integer after X. If we want the predicate to act as a lazy test, we must let it suspend until both variables are instantiated. This can be programmed as follows:
succ_lazy(X, Y) :-
( var(X) -> suspend(succ_lazy(X,Y), 0, X->inst)
; var(Y) -> suspend(succ_lazy(X,Y), 0, Y->inst)
; Y =:= X+1
).
The conjunctive condition “wait until X and Y are instantiated” is implemented by first waiting for X’s instantiation, then waking up and re-suspending waiting for Y’s instantiation.
A more eager implementation of succ/2 would delay only until a single variable argument is left, and then compute the variable from the nonvariable argument:
succ_eager(X, Y) :-
( var(X) ->
( var(Y) ->
suspend(succ_eager(X,Y), 0, [X,Y]->inst)
;
X is Y-1
)
;
Y is X+1
).
Here, we suspend only in the case that both arguments are variables, and wake up as soon as either of them gets instantiated.
Waiting for groundness of a term can be done in a way similar to the way succ_lazy/2 waited for both arguments to be instantiated: we pick any variable in the nonground term and wait for its instantiation. If this happens, we check whether other variables remain, and if yes, we re-suspend on one of the remaining variables. The following predicate waits for a term to become ground, and then calls arithmetic evaluation on it:
eval_lazy(Expr, Result) :-
( nonground(Expr, Var) ->
suspend(eval_lazy(Expr,Result), 0, Var->inst)
;
Result is Expr
).
We have used the built-in predicate nonground/2 which tests a term for groundness and returns one of its variables if it is nonground. Note also that in this implementation the same eval_lazy/2 goal gets woken and re-suspended possibly many times. See section 18.9 below for how to address this inefficiency.
Sometimes it is interesting to wake a goal when the number of variables among its arguments is reduced. This happens not only when a variable disappears due to instantiation, but also when two variables get unified (the result being a single variable). Consider the succ_eager/2 predicate above: we know that a goal like succ_eager(X,X). must always fail because an integer cannot be equal to its successor. However, the above implementation does not detect this case until X gets instantiated.
The bound waking condition subsumes the inst condition, but also wakes when any two of the variables in the condition specification get unified with each other (aliased). Using this property, we can improve the implementation of succ_eager/2 as follows:
succ_eager1(X, Y) :-
( var(X) ->
( var(Y) ->
X \== Y,
suspend(succ_eager1(X,Y), 0, [X,Y]->bound)
;
X is Y-1
)
;
Y is X+1
).
This gives us the desirable behaviour of failing as soon as possible:
?- succ_eager1(X, Y), X = Y. No (0.00s cpu)
Note that the built-in predicate ∼=/2 is a similar case and uses the bound waking condition for the same reason.
In plain Prolog, variable instantiation is the only way in which a single variable can become more constrained. In the presence of constraints, there are other ways. The most obvious example are variable domains: when a variable’s domain gets reduced, the variable becomes more constrained. This means that a delayed goal that previously still had a chance to succeed, could now have become impossible to satisfy, and should therefore be checked again.
The purpose of the constrained waking condition is to make it possible to wake a suspended goal whenever a variable becomes more constrained in a general sense. Having this general notion of constrained-ness makes it possible to write generic libraries that do interesting things with constraints and constrained variables without their implementation having to be linked to a particular constraint-solver3.
The constrained waking condition subsumes the bound condition (which in turn subsumes the inst condition). While goals suspended on the inst and bound conditions are woken implicitly by the unification routine, libaries which implement domain variables are responsible for notifying the system when they constrain a variable. They do so by invoking the built-ins notify_constrained/1 and wake/0 which is the generic way of telling the system that a variable has been constrained.
The simplest application using the constrained condition is a little debugging support predicate that prints a variable’s current partial value (e.g., domain) whenever it changes:
report(X) :-
( var(X) ->
writeln(constrained(X)),
suspend(report(X), 1, X->constrained) % (re)suspend
;
writeln(instantiated(X))
).
This now works with any library that implements a notion of constrainedness, e.g., the interval solver library(ic):
?- report(X), X :: 1..5, X #> 2, X #< 4.
constrained(X)
constrained(X{1 .. 5})
constrained(X{3 .. 5})
instantiated(3)
X = 3
Yes (0.01s cpu)
The report/1 predicate is woken when the domain is initally attached to X, whenever the domain gets reduced, and finally when X gets instantiated.
Constraint-solver libraries typically define additional, specialised waking conditions for the type of variable that they implement. For instance, the interval solver lib(ic) defines the following conditions:
- min:
- wake when the minimum domain value changes;
- max:
- wake when the maximum domain value changes;
- hole:
- wake when the domain gets a new hole;
- type:
- wake when the variable type changes from real to integer.
Obviously, these conditions only make sense for domain variables that are created by the lib(ic) library, and are mainly useful for implementing extensions to this library, e.g., new constraints. The library-defined waking conditions can be used with suspend/3 by using one of the following syntactic forms:
[A, B]->ic:min [A, B]->ic:(min of ic)
Using these conditions, we can define a more specialised form of the above report/1 predicate which only wakes up on the specified ic-domain changes:
report_ic(X) :-
( var(X) ->
writeln(newdomain(X)),
suspend(report_ic(X), 1, [X->ic:min,X->ic:max,X->ic:hole])
;
writeln(instantiated(X))
).
The behaviour is similar to above, the predicate wakes up on every domain change:
?- X::1..5, report_ic(X), X#> 2, X #< 4.
newdomain(X{1 .. 5})
newdomain(X{3 .. 5})
instantiated(3)
X = 3
Yes (0.00s cpu)
Note that we now have to set up the delayed goal after the variable already has a domain. This is because the ic-specific waking conditions can only be used with ic-variables,4 not with domain-less generic variables.
Although waking conditions for a goal are usually related to variables within the goal’s arguments, it is also possible to specify symbolic waking conditions which are unrelated to variables. These are called triggers and are identified simply by an arbitrary name (an atom). Goals can be suspended on such triggers, and the trigger can be pulled explicitly by program code in particular circumstances. By combining triggers with the event mechanism (chapter 14) it is even possible to wake goals in response to synchronous or asynchronous events.
A goal is suspended on a trigger using the syntax trigger(Name) in suspend/3 as in the following example:
?- suspend(writeln(woken), 0, trigger(happy)). There is 1 delayed goal. Yes (0.00s cpu)
The built-in trigger/1 can then be used to wake the goal:
?- suspend(writeln(woken), 0, trigger(happy)), trigger(happy). woken Yes (0.00s cpu)
Of course, symbolic triggers can be used together with other waking conditions to specify alternative reasons to wake a goal.
There is one system-defined trigger called postponed. It is provided as a way to postpone the triggering of a goal as much as possible. This trigger is pulled just before the end of certain encapsulated executions, like
A suspension should be attached to the postponed trigger only when
An example is a goal that originally woke on modifications of the upper bound of an interval variable. If the variable gets instantiated to its upper bound, there is no need to wake the goal (since the bound has not changed), but the variable (and with it the waking condition) disappears and the goal may be left orphaned.