ted@nmsu.edu (Ted Dunning) (12/07/90)
i have two questions about prologs which contain a freeze/2 predicate such as sicstus prolog. 1) how can one delay a goal until _either_ of two variables are instantiated? something like this could be done by the following, freeze(X,Y,G) :- freeze(X,G), freeze(Y,G). but this has the nasty consequence that G is called twice. note that freeze(X,freeze(Y,G)) does _not_ work since Y may instantiated before X, and i want G to be called in that case, too. 2) how can freeze/2 be used to do co-routining? does this require a modification of what is normally taken to be co-routining?
chik@icot.or.jp (Chikayama Takashi) (12/07/90)
In article <TED.90Dec6145517@aiaia.nmsu.edu> ted@nmsu.edu (Ted Dunning) writes: |1) how can one delay a goal until _either_ of two variables are |instantiated? A standard technique is: freeze(X, Y, G) :- freeze(X, V=go), freeze(Y, V=go), freeze(V, G). |2) how can freeze/2 be used to do co-routining? does this require a |modification of what is normally taken to be co-routining? The same technique as in concurrent logic languages like Concurrent Prolog, Parlog or Guarded Horn Clauses is available. See, for example: Ehud Shapiro and Akikazu Takeuchi "Object Oriented Programming in Concucrrent Prolog" in Ehud Shapiro ed. "Concurrent Prolog Collected Papers", Vol. 2 The MIT Press ISBN 0-262-19267-5 Takashi Chikayama
hawley@icot32.icot.or.jp (David John Hawley) (12/07/90)
In article <TED.90Dec6145517@aiaia.nmsu.edu> ted@nmsu.edu (Ted Dunning) writes: > > >i have two questions about prologs which contain a freeze/2 predicate >such as sicstus prolog. > >1) how can one delay a goal until _either_ of two variables are >instantiated? How about: ?- freeze(X,foo(Flag,G)), freeze(Y,foo(Flag,G)). foo(Flag,G) :- var(Flag), !, Flag=done, G. foo(_,_). By continuations you can do this to an arbitrarily complex delay condition. I think. >2) how can freeze/2 be used to do co-routining? does this require a >modification of what is normally taken to be co-routining? Don't know. I use a concurrent logic language :-). Speaking of which, our local cll (KL1) runs 3 times slower than our local Prolog (ESP) on the same hardware. If anyone can answer the above question (2), maybe (s)he can comment on the performance hit of doing heavy freeze-based coroutining in Prolog. David Hawley
lhe@yang (Lars-Henrik Eriksson) (12/07/90)
In article <TED.90Dec6145517@aiaia.nmsu.edu>, ted@nmsu (Ted Dunning) writes: > > >i have two questions about prologs which contain a freeze/2 predicate >such as sicstus prolog. > >1) how can one delay a goal until _either_ of two variables are >instantiated? > >something like this could be done by the following, > >freeze(X,Y,G) :- freeze(X,G), freeze(Y,G). > >but this has the nasty consequence that G is called twice. Try freeze(X, Y, G) :- freeze(X, Flag = 1), freeze(Y, Flag = 1), freeze(Flag, G). > >2) how can freeze/2 be used to do co-routining? does this require a >modification of what is normally taken to be co-routining? To implement coroutining in a producer-consumer context, use the following general scheme. start :- consume(X), produce(X). produce([]) :- ......./* Stop condition */. produce([X|Y]) :- ......./* Construct X*/, produce(Y). consume(X) :- freeze(X, consume1(X)). consume1([]). consume1([X|Y]) :- ......./* Use X */, consume(Y). In Sicstus prolog you can instead of the consume/consume1-pair write :- wait consume/1. consume([]). consume([X|Y]) :- ......./* Use X */, consume(Y). which is cleaner. -- Lars-Henrik Eriksson Internet: lhe@sics.se Swedish Institute of Computer Science Phone (intn'l): +46 8 752 15 09 Box 1263 Telefon (nat'l): 08 - 752 15 09 S-164 28 KISTA, SWEDEN
mark@adler.philosophie.uni-stuttgart.de (Mark Johnson) (12/07/90)
/* Here's a utility predicate freeze/3 for prologs like SICSTUS and BNR
* which have freeze/2. It uses a ``shared variable'' which is bound
* when one of the frozen goals is run. It's easy to generalize this
* to arrange for Goal to be called once whenever *any* variable appearing
* in a term (or list) is bound.
*
* But what I don't know how to do is the following: define a predicate
* delay(Term, Goal) which calls Goal when Term is further instantiated,
* possibly by unifying distinct variables occuring in Term.
* Any ideas?
*
* Mark Johnson
*/
freeze(X, Y, Goal) :- % Delay Goal until either X or Y is bound
freeze(X, freeze_helper(SharedVar, Goal)),
freeze(Y, freeze_helper(SharedVar, Goal)).
freeze_helper(SharedVar, _) :- % If SharedVar is bound
nonvar(SharedVar), % then the frozen goal
!. % has already been run.
freeze_helper(done, Goal) :- % Bind SharedVar
call(Goal). % and call Goal.
test :-
freeze(X, Y, write('Frozen goal activated')),
X = a,
Y = b.chik@icot.or.jp (Chikayama Takashi) (12/17/90)
In article <MARK.90Dec7130758@adler.philosophie.uni-stuttgart.de> mark@adler.philosophie.uni-stuttgart.de (Mark Johnson) writes: * But what I don't know how to do is the following: define a predicate * delay(Term, Goal) which calls Goal when Term is further instantiated, * possibly by unifying distinct variables occuring in Term. * Any ideas? * * Mark Johnson What's wrong with "freeze"ing a goal which, in addition to calling the main "Goal", will traverse the data structure the variable is instantiated to, hooking up the same goal to all the variables in the structure on its way? For example: delay(Term, Goal) :- freeze(Term, (Goal, traverse(Term, Goal))). traverse(X, Goal) :- var(X), !, freeze(X, Goal). traverse(X, Goal) :- functor(X, _, N), traverse_args(N, X, Goal). traverse_args(0, _, _) :- !. traverse_args(N, X, Goal) :- arg(N, X, Xn), traverse(Xn, Goal), N1 is N-1, traverse_args(N1, X, Goal). which will execute as: | ?- delay(X, write(X)), X = f(Y,Z), Y = [a], Z = b. f(_92,_108)f([a],_343)f([a],b) This calls "write" three times and I guess that's exactly what you want. Or do you want something completely different? Takashi Chikayama ICOT
hawley@icot32.icot.or.jp (David John Hawley) (12/18/90)
In article <CHIK.90Dec17194110@icot21.icot.or.jp> chikayama@icot.or.jp writes: >In article <MARK.90Dec7130758@adler.philosophie.uni-stuttgart.de> mark@adler.philosophie.uni-stuttgart.de (Mark Johnson) writes: > > * But what I don't know how to do is the following: define a predicate > * delay(Term, Goal) which calls Goal when Term is further instantiated, > * possibly by unifying distinct variables occuring in Term. > * Any ideas? >What's wrong with "freeze"ing a goal which, in addition to calling the >main "Goal", will traverse the data structure the variable is >instantiated to, hooking up the same goal to all the variables in the >structure on its way? For example: (context: SICStus Prolog) The problem with this is when you "unify distinct variables occuring in Term" to each other. The only predicate I know of that can capture such events is dif/2 (a sound implementation of \==), but I can't see how to use it to do what the first author wants. On the other hand freeze/2 waits for "instantiations", i.e. it doesn't trap Var=Var. David Hawley <munch> <munch> <munch>
lee@munnari.oz.au (Lee Naish) (12/19/90)
In article <8203@icot32.icot.or.jp> hawley@icot32.icot.or.jp (David John Hawley) writes: >In article <CHIK.90Dec17194110@icot21.icot.or.jp> chikayama@icot.or.jp writes: >>In article <MARK.90Dec7130758@adler.philosophie.uni-stuttgart.de> mark@adler.philosophie.uni-stuttgart.de (Mark Johnson) writes: >> >> * But what I don't know how to do is the following: define a predicate >> * delay(Term, Goal) which calls Goal when Term is further instantiated, >> * possibly by unifying distinct variables occuring in Term. >> * Any ideas? >>What's wrong with "freeze"ing a goal... > >(context: SICStus Prolog) The problem with this is when you "unify >distinct variables occuring in Term" to each other. The only predicate >I know of that can capture such events is dif/2 (a sound implementation >of \==), but I can't see how to use it to do what the first author wants. I once hacked up something in MU-Prolog which waited until a term was further instantiated. It was used for a tracing utility which printed the value of variables in a goal whenever they were further instantiated. Here is an example of a coroutining perm/2 running backwards: ?- vtrace(perm(X, [1, 2])). X = [X_153|Y_153] X = [1|Z_153] X = [1, X_234|Y_234] X = [1, 2|Z_234] X = [1, 2] X = [1, 2] ; FAIL FAIL FAIL FAIL X = [X_203, B_206|L_206] X = [X_203, 1|Y_203] X = [2, 1|Z_203] X = [2, 1] X = [2, 1] ; FAIL FAIL FAIL X = [2, B_206|L_206] FAIL FAIL FAIL fail. ?- The MU-Prolog had a limit on the number of distinct variables it could handle. In NU-Prolog you can implement delay/2 by using =/2 inside if. This is treated in a similar way to inequality, delaying until sufficiently instantiated (not necessarily ground): % Call Goal when Term becomes futher instantiated % (even two vars being unified). Calls Goal % immediately if Term is ground (should be an error?). % % BUG: might not wake if var is bound to a term of % the form 'Really different!'(Integer). % This can be fixed quite simply using another % goal which wakes if any var is bound to a nonvar % but I doubt that its worth bothering. delay(Term, Goal) :- listOfVars(Term, Vars), sort(Vars, UniqueVars), % remove duplicates list_of_diff(UniqueVars, 42, DiffEls), (if UniqueVars = DiffEls then % unlikely, unless UniqueVars = [] call(Goal) else call(Goal) ). % Returns list of the same length as first arg. % Each element differs from all others; and % hopefully all other terms in the program. % Second arg is an arbitrary integer seed. list_of_diff([], _, []). list_of_diff(_.Us, N, 'Really different!'(N).Ns) :- N1 is N + 1, list_of_diff(Us, N1, Ns). Its probably possible to write a much neater solution in Sepia, since the basic delaying primitive in Sepia allows (in)equality checking. NU-Prolog if= also allows quantifiers, making it more powerful in some ways. For example, the NU-Prolog interpreter uses it to delay until one term is subsumed by another term or the two terms do not unify. lee
micha@ecrc.de (Micha Meier) (12/19/90)
In article <8203@icot32.icot.or.jp> hawley@icot32.icot.or.jp (David John Hawley) writes: >In article <CHIK.90Dec17194110@icot21.icot.or.jp> chikayama@icot.or.jp writes: >>What's wrong with "freeze"ing a goal which, in addition to calling the >>main "Goal", will traverse the data structure the variable is >>instantiated to, hooking up the same goal to all the variables in the >>structure on its way? For example: > >(context: SICStus Prolog) The problem with this is when you "unify >distinct variables occuring in Term" to each other. The only predicate >I know of that can capture such events is dif/2 (a sound implementation >of \==), but I can't see how to use it to do what the first author wants. >On the other hand freeze/2 waits for "instantiations", i.e. it doesn't >trap Var=Var. The problem is not only with binding a variable to another one, but also to delay a goal whose structure is not fixed, i.e. the variables to delay on have to be extracted from it at run-time. In my opinion, freeze/2 is not well suited for this. Although it can be used for that, the resulting program does not look neither declarative nor readable. In SEPIA it is possible to specify whether a goal is woken only by the instantiation of a variable or even by its binding, possibly to another variable. The delay condition is expressed using delay clauses in the form delay Pred if Condition. Condition has the form of a normal clause body, and it can contain the predicates var/1, nonground/1, \==/2 and user-defined external predicates. When var/1 and nonground/1 are used, the goal is woken only by instantiating the appropriate variable because the system knows that it would re-delay with a mere variable binding. When \==/2 is used, on the other hand, the goal is woken even by a variable binding. The choice of the predicates allowed in the body of a delay clause seems deliberate, but in fact it is not. Although we initially intended to allow any Prolog predicates in the body of a delay clause, we changed the design because this approach would imply serious semantic problems, namely mixing meta- and object-level computation. Since we wanted the delay clauses to be efficient, we decided to restrict the allowed conditions to these three, and it turned out that for most of the 'normal' applications, this is more than enough. For a more advanced usage, e.g. to implement constraints, it is much more difficult to isolate what conditions will be used, and that's why we allow the users to write their own conditions in C and add them as external predicates to Sepia. The user can in fact specify a very complex delay conditions, for example specify that the goal should delay when first called, unless it contains less than N variables, but whenever any of its variables is bound, it will be woken and it will continue, even if it has less than N variables. To anyone who is interested: the binary of SEPIA is available to universities for a nominal fee of ~$200 (for any number of machines) together with a graphical system for X and sunview and now also with the high-level debugging tool OPIUM. --Micha -- E-MAIL micha@ecrc.de MAIL Micha Meier ECRC, Arabellastr. 17 8000 Munich 81 Germany