Path: utzoo!attcan!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!munnari.oz.au!lee From: lee@munnari.oz.au (Lee Naish) Newsgroups: comp.lang.prolog Subject: Re: co-routining Message-ID: <6311@munnari.oz.au> Date: 19 Dec 90 07:56:20 GMT References: <8203@icot32.icot.or.jp> Sender: news@cs.mu.oz.au Reply-To: lee@munmurra.UUCP (Lee Naish) Distribution: comp Organization: Comp Sci, University of Melbourne Lines: 93 In article <8203@icot32.icot.or.jp> hawley@icot32.icot.or.jp (David John Hawley) writes: >In article chikayama@icot.or.jp writes: >>In article 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