4 % The contents of this file are subject to the Cisco-style Mozilla Public
6 % in compliance with the License.  You may obtain a copy of the License
15 % The Initial Developer of the Original Code is  Cisco Systems, Inc.
36 The core feature is the ability to suspend the execution of a goal
40 prerequisites for the implementation of constraint propagation
60 % details of waking, cut
70 It is the set of all goals that must be satisfied.
71 The computation typically starts with a resolvent consisting only of the
75 match a clause head with an instance of the clause body, i.e., a
76 sequence of sub-goals),
77 and eventually terminates with one of the trivial goals
104 Suspended goals form the part of the resolvent which is
111 {\eclipse} currently supports a fixed range of 12 different priorities,
114 Figure \ref{figresolv} shows the structure of the resolvent.
116 member of the resolvent. As execution proceeds, active goals may be
122 \caption{Structure of the resolvent}
128 The case that a subgoal remains suspended (delayed) at the end of the
136 the control aspect of the program.  The solution would usually be to either
138 The aim is to get the delayed goals out of the suspended state and
140 As a rule of thumb, goals will not suspend when all their arguments are
142 variables are instantiated at the end of computation will typically not
154 Instead of succeeding or failing, they will suspend when their arguments
165 query is true or false. The goal remains delayed and we have a case of
168 about delayed goals at the end of the computation).
201 Note that more powerful versions of these constraints exist in other
222 The command line toplevel then prompts and offers to print a list of
225 of the Delayed Goals Viewer, which can be used to look at all delayed goals
226 or a filtered subset of them.
242 The semantics of delay clauses is thus cleaner than many alternative
253 with the normal clauses of the predicate they belong to.
265 The operational semantics of the delay clauses is as follows:
268 If one of the delay clauses succeeds, the call is suspended,
272 The mechanism of executing a delay clause is similar to normal Prolog
275 \item the unification of the goal with the delay clause head is not the usual
283 For example, the head of the delay clause
298 The reason for using pattern matching instead of unification
299 is to avoid a possible mixing of meta-level control with the
304 The form of the head of a delay clause is not restricted.
312 \item it should contain at least one of the following subgoals:
330 A predicate that checks if its argument is a proper list of integers.
385 executed with the call \notation{?- p(a, b)} of course succeeds and the call
391 used instead of \notation{if} in the delay clause. To indicate this error,
392 the compiler complains about redefinition of the built-in predicate
400 While delay-clauses are an elegant, declarative way of specifying how
418 as soon as one of the conditions specified in the \about{CondList}
420 This list contains specifications of the form
424 to denote that as soon as one of the variables in the term \about{Vars}
429 The condition \about{Cond} can be the name of a system-defined waking condition,
436 means that as soon as one (or both) of the variables \about{X}, \about{Y}
439 These variables are also called the \defnotion{suspending variables} of the
443 \about{Cond} can also be the specification of a suspension list
444 defined in one of currently loaded library attributes. For example, when the
445 interval solver library lib(ic) is loaded, either of
449 [A,B]->ic:(min of ic)
453 of the domain of either \about{A} or \about{B} are updated
456 Another admissible form of condition \about{Cond} is
508 The usual purpose of suspending a goal is to wait and resume it later
514 in the priority queue of woken goals and as soon as it becomes
519 variable instantiation, or a modification of a variable's
533 can be used with any variable. They are, in order of increasing generality:
572 the goal will wake up as soon as the first of them occurs:
582 It is not possible to specify a conjunction of conditions directly!
605 A more eager implementation of \predspec{succ/2} would delay only until
623 and wake up as soon as either of them gets instantiated.
625 Waiting for groundness of a term can be done in a way similar to the
630 we re-suspend on one of the remaining variables. The following predicate
644 which tests a term for groundness and returns one of its variables
654 Sometimes it is interesting to wake a goal when the number of variables
665 also wakes when any two of the variables in the condition specification get
667 Using this property, we can improve the implementation of
685 This gives us the desirable behaviour of failing as soon as possible:
704 variable can become more constrained.  In the presence of constraints,
711 The purpose of the \notation{constrained} waking condition is to make it
714 of constrained-ness makes it possible to write generic libraries
718   Examples of such libraries are \libspec{branch_and_bound},
731 which is the generic way of telling the system that a variable has been
748 This now works with any library that implements a notion of constrainedness,
772 waking conditions for the type of variable that they implement.
788 by using one of the following syntactic forms:
792 [A, B]->ic:(min of ic)
795 Using these conditions, we can define a more specialised form of
878 It is provided as a way to postpone the triggering of a goal as much
879 as possible. This trigger is pulled just before the end of
882 \item end of toplevel execution;
897 An example is a goal that originally woke on modifications of the upper
898 bound of an interval variable. If the variable gets instantiated to its
916 do not enforce this. To provide maximum flexibility of use,
917 the functionalities of suspending and waking/scheduling are
925 A suspension represents a goal that is part of the resolvent.
928 The components of a suspension are:
941         This indicates the current position of the suspension within
952 Suspension lists are either stored in an attribute of
992 denotes the process of both scheduling and eventual execution.
1037 Extract any of the information contained in the suspension:
1038 \about{Name} can be one of
1046 of a suspension can be changed using this primitive.
1047 If the priority of a sleeping suspension is changed,
1050 priority has no effect, except for future schedulings of demons
1058 change the semantics of the program.
1066 The system keeps track of all created suspensions and it
1073 and to detect floundering of the query given to the {\eclipse} top-level loop.
1081 Suspensions are attached to variables by means of the attribute mechanism.
1085 Suspensions can then be inserted into one or several of those lists using
1090 suspension list of all attributed variables occurring in \about{Vars}.
1091 The current module specifies which of the attributes will be taken.
1102 insert_suspension(Vars, Susp, inst of suspend, suspend)
1106 list of the (system-predefined) \notation{suspend}
1107 attribute of all variables that occur in \about{Vars}, and
1110 insert_suspension(Vars, Susp, max of fd, fd)
1113 would insert the suspension into the \notation{max} list of the finite-domain
1114 attribute of all variables in \about{Vars}.
1119 each of them,
1127 Finally, the \about{Index}'th argument of the attribute
1129 \about{Susp} is inserted at the beginning of this list.
1143 For those suspension lists, initialization and waking is taken care of
1146 For the implementation of user-defined suspension lists,
1151     Initializes argument \about{Position} of \about{Attribute} to an empty
1154     Appends the first of two suspension lists (argument
1155     \about{Pos1} of
1157     the end of the second (argument \about{Pos2} of \about{Attr2}). NOTE: The
1161     argument position \about{Pos} of \about{Attr}. The suspension list can be
1179 A single suspension or a list of suspensions can be attached to a
1194 Suspended goals are woken by submitting at least one of the suspension lists
1198 A suspension list can be passed to the scheduler by either of the predicates
1208 Note, however, that scheduling a suspension by means of
1232 variant of the \predspec{report/1} example from above:
1248 To do so, it suspends on some or all of those variables.
1254 To better support this type of goals, {\eclipse} provides a special type
1255 of predicate, called a \defnotion{demon}. A predicate is turned into a
1263 the body of each demon clause.
1265 suspended part of the resolvent, and an identical one
1272 let it remember its own suspension in one of its arguments.
1303 The priority of the currently executing goal can be determined
1316 If its scheduling priority is higher than the priority of the currently
1317 executing goal, then the execution of the current goal
1321 with priority higher than that of the current goal.
1324 priority determining the order of execution, and the run_priority determining
1325 the atomicity of execution.
1330 by means of
1371 (default 2), which usually make the use of
1376 \subsection{Choice of Priorities}
1383 of the program and always succeed, e.g., display routines, consistency
1398 a lot of processing, e.g., complicated disjunctive
1404 \item [toplevel goal (12)]  the default priority of the user program.
1497 \section{Details of the Execution Mechanism}
1501 \subsection{Particularities of Waking by Unification}
1505 conditions are woken by unifications of their
1512 The order of executing woken suspended goals does not necessarily correspond
1513 to the order of their suspending. It is in fact determined by their
1517 of simple goals.
1519 Simple goals are a subset of the built-ins and
1530 Delayed goals are therefore woken only at the end of a successful
1531 unification and/or a sequence of simple goals.
1533 goals are woken only at the end of the last consecutive simple
1535 If the clause contains simple goals at the beginning of its
1536 body, they are considered part of the head (\defnotion{extended head})
1539 delayed goals are woken at the end of the extended head.
1547 a sequence of simple goals.
1575 of \about{P}. In the example query, the call to \predspec{integers/2} initially
1579 of the second clause of \predspec{filter/3}, which will wake up
1581 since the second clause of \predspec{filter/3} has an extended head which
1585 Therefore, \about{N} is not yet instantiated at the time of the arithmetic test
1589 it is that neither of the two possibilities is always the intended
1604 beginning of the second clause.
1608 This would also be more efficient by avoiding the creation of a choice point:
1628 %It is important to mention here the influence of non-logical predicates,
1630 %on the execution of delayed goals.
1633 relies on a fixed order of goal execution in that it discards
1636 If some of these goals delay without being woken before the cut,
1637 or if the head unification of the
1639 the completeness of the resulting program is lost
1641 %In a restricted class of procedures the system raises an exception
1642 %to signal that there has been an interaction of cut with delayed
1651 coroutining, or to be precisely aware of their scope.
1652 The danger of a cut is twofold:
1654 \item Delaying \emph{out of} the scope of a cut:
1656 (or children of these calls) delay. When they are then woken later,
1657 they may cause the whole execution to fail instead of just the
1660 \item Delaying \emph{into} the scope of a cut:
1661 the head unification of a clause with cuts can wake delayed goals.
1662 If they are nondeterministic, the cut in the body of the waking clause
1667 %to print a warning whenever a cut in one of the above two conditions
1673 \section{Simulating the Delay-Primitives of other Systems}
1690 The block declarations of SICStus Prolog can be easily expressed
1701 The transcription of ``when declarations'' from NU-Prolog
1719 there are no syntactic restrictions on the head of a delay clause,
1722 programming with (a subset of) built-ins.
1723 In general, it is a matter of taste whether specifying delay-conditions
1725 However, the semantics of delay clauses is certainly more intuitive in

Indexes created Fri Jun 14 05:58:36 MDT 2024