gerdeman@clio.las.uiuc.edu (02/07/89)
On this same topic, I have noticed some peculiar features of 'findall' in TI-Prolog. I don't know whether these are standard or peculiar to Texas Instrument. First: Why does 'findall not require existential quantification at all? The manual doesn't say anything at all about this. Second: why does 'findall' change variable names? For example consider the following perverse little procedure: ?-findall(X,member(X,[Y,Z],S). X = _54 Y = _98 Z = _111 S = [209,201] At first I thought this was just an annoying quirk but then I discovered that this feature is useful for copying in the following peculiar program: copy(X,Y):- findall(Z,Z=X,[Y]). This procedure turns out to be much faster than the copy program given in Sterling and Shapiro (which uses assert and retract). I used this copy procedure in my own implementation of a PATR style parser and it sped things up by an order of magnitude. Then I discovered that this explicit copying is not necessary since any destructive procedure embedded inside of 'findall' will fail to have destructive consequences. For example 'graph_unify/3' (for DAG unification) normally binds variables in its input arguments but non_destructive_unify(A,B,A_u_B):- findall(X,graph_unify(A,B,X),A_u_B). Does anyone out there know why this works? ---- Dale Gerdemann University of Ill Dept Linguistics
lang@pearl.PRC.Unisys.COM (Francois-Michel Lang) (02/08/89)
In article <16400003@clio> gerdeman@clio.las.uiuc.edu writes: > >On this same topic, I have noticed some peculiar features >of 'findall' in TI-Prolog. I don't know whether these are >standard or peculiar to Texas Instrument. > >First: Why does 'findall not require existential quantification >at all? The manual doesn't say anything at all about this. I don't know anything about TI-Prolog specifically, but I'm pretty sure that the `standard' definitions of findall/3 given in the literature (e.g., in Clocksin & Mellish and Sterling & Shapiro) all treat free vars in the second arg as existentially quantified. As Richard has pointed out, these `standard' definitions tend also to suffer from the insidious problem of not being able to distinguish the term which is asserted to mark the bottom of the stack of solutions from terms which are asserted as solutions. > >Second: why does 'findall' change variable names? For example consider >the following perverse little procedure: > >?-findall(X,member(X,[Y,Z],S). > > X = _54 > Y = _98 > Z = _111 > S = [209,201] This is bizarre...Any TI people out there? Even if S = [209,201] is supposed to be S = [_209,_201] that still seems weird. ---------------------------------------------------------------------------- Francois-Michel Lang Paoli Research Center, Unisys Corporation lang@prc.unisys.com (215) 648-7256 Dept of Comp & Info Science, U of PA lang@cis.upenn.edu (215) 898-9511
gerdeman@clio.las.uiuc.edu (02/09/89)
/* Written 2:57 pm Feb 7, 1989 by rar@DEIMOS.ADS.COM in clio:comp.lang.prolog */ /* ---------- "existential quantification in bagof" ---------- */ => E.g., given the DB => => foo(1,2,3,4). => foo(2,3,4,5). => foo(3,4,5,6). => foo(4,5,6,7). => => I can do => => | ?- T = p(X,Y,Z), setof(First, T^foo(First,X,Y,Z), Set). => => T = p(X,Y,Z), => X = _79, => Y = _94, => Z = _109, => First = _132, => Set = [1,2,3,4] => => I'd be curious to find out if other Prologs work like this. This is how it works in TI-Prolog. But how about 'findall'? I think this is the peculiar case. See my response to the original existential quantification question. -- Dale Gerdemann U of Ill Dept of Linguistics
gerdeman@clio.las.uiuc.edu (02/10/89)
Yes 209 and 201 should be _209 and _201. It occurred to me that I should have given a more extended example of this behavior of 'findall'. Consider the following: ?- findall(X,member(X,[Y,Z,Y],S). X = _54 Y = _98 Z = _111 S = [_230,_222,_214] Here the variables are not only replaced, they're not even replaced consistently. Serious bugs are imaginable. But in the following case, the variables are replaced consistently: ?- findall(X,X = [Y,Z,Y],S). X = _54 Y = _84 Z = _97 S = [[_193,_195,_193]] This behavior is potentially useful. But, is it intended? Does any other Prolog work this way, or is TI-Prolog unique? -- Dale Gerdemann University of Ill Dept. of Linguistics
wengert@clio.las.uiuc.edu (02/13/89)
/* Written 2:18 pm Feb 6, 1989 by gerdeman@clio.las.uiuc.edu in clio:comp.lang.prolog */ On this same topic, I have noticed some peculiar features of 'findall' in TI-Prolog. I don't know whether these are standard or peculiar to Texas Instrument. First: Why does 'findall not require existential quantification at all? The manual doesn't say anything at all about this. Second: why does 'findall' change variable names? For example consider the following perverse little procedure: ?-findall(X,member(X,[Y,Z],S). X = _54 Y = _98 Z = _111 S = [209,201] At first I thought this was just an annoying quirk but then I discovered that this feature is useful for copying in the following peculiar program: copy(X,Y):- findall(Z,Z=X,[Y]). This procedure turns out to be much faster than the copy program given in Sterling and Shapiro (which uses assert and retract). I used this copy procedure in my own implementation of a PATR style parser and it sped things up by an order of magnitude. Then I discovered that this explicit copying is not necessary since any destructive procedure embedded inside of 'findall' will fail to have destructive consequences. For example 'graph_unify/3' (for DAG unification) normally binds variables in its input arguments but non_destructive_unify(A,B,A_u_B):- findall(X,graph_unify(A,B,X),A_u_B). Does anyone out there know why this works? ---- Dale Gerdemann University of Ill Dept Linguistics /* End of text from clio:comp.lang.prolog */
fuchs@unizh.UUCP (fuchs) (02/14/89)
In article <16400005@clio> gerdeman@clio.UUCP writes: > >This behavior is potentially useful. But, is it intended? Does any other >Prolog work this way, or is TI-Prolog unique? > It is not as the following queries and answers of LPA MacProlog 2.5 demonstrate. How about other Prologs? :- findall(X, on(X, [Y, Z, Y]), S) N#1 X=_901,Y=_902,Z=_903,S=[_1020, _1022, _1024] :- findall(X, X=[Y, Z, Y], S) N#1 X=_900,Y=_901,Z=_902,S=[[_1019, _1021, _1019]]
wengert@clio.las.uiuc.edu (02/17/89)
Arity Prolog, given the call findall(X,member(X,[Y,Z]),S). responds X = _0034 Y = _0048 Z = _005C S = [_00FC,00EC] This is the same result you find surprising on the TI. What you seem to be surprised by is the different variables in the list formed in S. Arity says, "The findall predicate is similar to bagof, except that any free variable is assumed to be existentially quantified." Given that, the above response strikes me as perfectly logical. Think of what the query is. It asks: What would I find if I looked for anything that was a member of a list which contained something followed by something? The answer: You would get something and something. The fact that these are different variables in the answer points out the fact that bound variables in a different scope are not to be identified even if they are typographically the same. In logic classes it is important to explain that (Ex)policeman(x) and (Ex)murderer(x) does not given the conclusion that some policeman is a murderer. It is safer, therefore, to write (Ex)policeman(x) and (Ey)murderer(y). If, therefore, you had a list containing some policeman followed by some policeman (Ex)policeman(x),(Ey)policeman(y), and then you asked what you would find in that list, the answer: (Ev)policeman(v), (Ew)policeman(w) would be correct. Since Prolog does not include the quantifiers indicating scope, the use of divergent variables is almost required. bob wengert wengert@clio.las.uiuc.edu