Total noob, here, using a Lisp implementation of Prolog (AllegroCL's, to
be precise) in case anything looks odd.
Given:
(<-- (gcf ?x ?y ?f)
(is ?f (gcd ?x ?y))) ;; is/2 let's me use Lisp in the second arg
(<-- (> ?x ?y)
(lispp (> ?x ?y))) ;; some more embedded Lisp
Applying the above, we test a hardcoded pair (12 1nd 15) to see if they
have gcf > 1:
(?- (gcf 15 12 ?x)
(= ?x ?y)
(> ?y 1))
?X = 3
?Y = 3
No.
Fine. But now:
(?- (gcf 15 12 ?x)
(= ?x ?y)
(> ?y 1)
(= ?x ?y))
No.
The duplication of the line (in the real world case from which this was
distilled) was inadvertent and has been corrected, but I am still
curious as to why it causes the rule to fail. Is this proper Prolog, or
should I make a bug report to the vendor?
kt
ps. duh, it just occurred to me to grab a prolog somewhere and try
something similar in pure prolog. will do. kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
On Jan 16, 12:39 pm, Ken Tilton <···········@optonline.net> wrote:
> Total noob, here, using a Lisp implementation of Prolog (AllegroCL's, to
> be precise) in case anything looks odd.
>
> Given:
>
> (<-- (gcf ?x ?y ?f)
> (is ?f (gcd ?x ?y))) ;; is/2 let's me use Lisp in the second arg
>
> (<-- (> ?x ?y)
> (lispp (> ?x ?y))) ;; some more embedded Lisp
>
> Applying the above, we test a hardcoded pair (12 1nd 15) to see if they
> have gcf > 1:
>
> (?- (gcf 15 12 ?x)
> (= ?x ?y)
> (> ?y 1))
>
> ?X = 3
> ?Y = 3
>
> No.
>
> Fine. But now:
>
> (?- (gcf 15 12 ?x)
> (= ?x ?y)
> (> ?y 1)
> (= ?x ?y))
>
> No.
>
> The duplication of the line (in the real world case from which this was
> distilled) was inadvertent and has been corrected, but I am still
> curious as to why it causes the rule to fail. Is this proper Prolog, or
> should I make a bug report to the vendor?
>
> kt
>
> ps. duh, it just occurred to me to grab a prolog somewhere and try
> something similar in pure prolog. will do. kt
>
> --http://www.theoryyalgebra.com/
>
> "In the morning, hear the Way;
> in the evening, die content!"
> -- Confucius
It looks like a bug to me. I'd try to simplify
the test case before submitting it to the vendor.
In particular, if the failure can be elicited
without making any call to a user-defined goal
such as "gcf", then it becomes easier for the
vendor to duplicate the problem and resolve.
regards, chip
Chip Eastham wrote:
> On Jan 16, 12:39 pm, Ken Tilton <···········@optonline.net> wrote:
>
>>Total noob, here, using a Lisp implementation of Prolog (AllegroCL's, to
>>be precise) in case anything looks odd.
>>
>>Given:
>>
>>(<-- (gcf ?x ?y ?f)
>> (is ?f (gcd ?x ?y))) ;; is/2 let's me use Lisp in the second arg
>>
>>(<-- (> ?x ?y)
>> (lispp (> ?x ?y))) ;; some more embedded Lisp
>>
>>Applying the above, we test a hardcoded pair (12 1nd 15) to see if they
>>have gcf > 1:
>>
>>(?- (gcf 15 12 ?x)
>> (= ?x ?y)
>> (> ?y 1))
>>
>>?X = 3
>>?Y = 3
>>
>>No.
>>
>>Fine. But now:
>>
>>(?- (gcf 15 12 ?x)
>> (= ?x ?y)
>> (> ?y 1)
>> (= ?x ?y))
>>
>>No.
>>
>>The duplication of the line (in the real world case from which this was
>>distilled) was inadvertent and has been corrected, but I am still
>>curious as to why it causes the rule to fail. Is this proper Prolog, or
>>should I make a bug report to the vendor?
>>
>>kt
>>
>>ps. duh, it just occurred to me to grab a prolog somewhere and try
>>something similar in pure prolog. will do. kt
>>
>>--http://www.theoryyalgebra.com/
>>
>>"In the morning, hear the Way;
>> in the evening, die content!"
>> -- Confucius
>
>
> It looks like a bug to me. I'd try to simplify
> the test case before submitting it to the vendor.
> In particular, if the failure can be elicited
> without making any call to a user-defined goal
> such as "gcf", then it becomes easier for the
> vendor to duplicate the problem and resolve.
>
> regards, chip
OK, I'll submit an IR.
That gcf /is/ necessary, or at least simply starting with:
(= ?x 3)
...makes everything work as expected.
thx, kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
On Jan 16, 1:20 pm, Ken Tilton <···········@optonline.net> wrote:
> Chip Eastham wrote:
> > On Jan 16, 12:39 pm, Ken Tilton <···········@optonline.net> wrote:
>
> >>Total noob, here, using a Lisp implementation of Prolog (AllegroCL's, to
> >>be precise) in case anything looks odd.
>
> >>Given:
>
> >>(<-- (gcf ?x ?y ?f)
> >> (is ?f (gcd ?x ?y))) ;; is/2 let's me use Lisp in the second arg
>
> >>(<-- (> ?x ?y)
> >> (lispp (> ?x ?y))) ;; some more embedded Lisp
>
> >>Applying the above, we test a hardcoded pair (12 1nd 15) to see if they
> >>have gcf > 1:
>
> >>(?- (gcf 15 12 ?x)
> >> (= ?x ?y)
> >> (> ?y 1))
>
> >>?X = 3
> >>?Y = 3
>
> >>No.
>
> >>Fine. But now:
>
> >>(?- (gcf 15 12 ?x)
> >> (= ?x ?y)
> >> (> ?y 1)
> >> (= ?x ?y))
>
> >>No.
>
> >>The duplication of the line (in the real world case from which this was
> >>distilled) was inadvertent and has been corrected, but I am still
> >>curious as to why it causes the rule to fail. Is this proper Prolog, or
> >>should I make a bug report to the vendor?
>
> >>kt
>
> >>ps. duh, it just occurred to me to grab a prolog somewhere and try
> >>something similar in pure prolog. will do. kt
>
> >>--http://www.theoryyalgebra.com/
>
> >>"In the morning, hear the Way;
> >> in the evening, die content!"
> >> -- Confucius
>
> > It looks like a bug to me. I'd try to simplify
> > the test case before submitting it to the vendor.
> > In particular, if the failure can be elicited
> > without making any call to a user-defined goal
> > such as "gcf", then it becomes easier for the
> > vendor to duplicate the problem and resolve.
>
> > regards, chip
>
> OK, I'll submit an IR.
>
> That gcf /is/ necessary, or at least simply starting with:
>
> (= ?x 3)
>
> ...makes everything work as expected.
>
> thx, kt
>
> --http://www.theoryyalgebra.com/
>
> "In the morning, hear the Way;
> in the evening, die content!"
> -- Confucius
Another "simplification" to try is removing the
inequality test, (> ?y 1), between the two
equality tests. It's conceivable that the
inequality test, by forcing "evaluation" of
its expressions, has an unintended side-effect
on variable ?y.
regards, chip
Chip Eastham wrote:
> On Jan 16, 1:20 pm, Ken Tilton <···········@optonline.net> wrote:
>
>>Chip Eastham wrote:
>>
>>>On Jan 16, 12:39 pm, Ken Tilton <···········@optonline.net> wrote:
>>
>>>>Total noob, here, using a Lisp implementation of Prolog (AllegroCL's, to
>>>>be precise) in case anything looks odd.
>>
>>>>Given:
>>
>>>>(<-- (gcf ?x ?y ?f)
>>>> (is ?f (gcd ?x ?y))) ;; is/2 let's me use Lisp in the second arg
>>
>>>>(<-- (> ?x ?y)
>>>> (lispp (> ?x ?y))) ;; some more embedded Lisp
>>
>>>>Applying the above, we test a hardcoded pair (12 1nd 15) to see if they
>>>>have gcf > 1:
>>
>>>>(?- (gcf 15 12 ?x)
>>>> (= ?x ?y)
>>>> (> ?y 1))
>>
>>>>?X = 3
>>>>?Y = 3
>>
>>>>No.
>>
>>>>Fine. But now:
>>
>>>>(?- (gcf 15 12 ?x)
>>>> (= ?x ?y)
>>>> (> ?y 1)
>>>> (= ?x ?y))
>>
>>>>No.
>>
>>>>The duplication of the line (in the real world case from which this was
>>>>distilled) was inadvertent and has been corrected, but I am still
>>>>curious as to why it causes the rule to fail. Is this proper Prolog, or
>>>>should I make a bug report to the vendor?
>>
>>>>kt
>>
>>>>ps. duh, it just occurred to me to grab a prolog somewhere and try
>>>>something similar in pure prolog. will do. kt
>>
>>>>--http://www.theoryyalgebra.com/
>>
>>>>"In the morning, hear the Way;
>>>> in the evening, die content!"
>>>> -- Confucius
>>
>>>It looks like a bug to me. I'd try to simplify
>>>the test case before submitting it to the vendor.
>>>In particular, if the failure can be elicited
>>>without making any call to a user-defined goal
>>>such as "gcf", then it becomes easier for the
>>>vendor to duplicate the problem and resolve.
>>
>>>regards, chip
>>
>>OK, I'll submit an IR.
>>
>>That gcf /is/ necessary, or at least simply starting with:
>>
>> (= ?x 3)
>>
>>...makes everything work as expected.
>>
>>thx, kt
>>
>>--http://www.theoryyalgebra.com/
>>
>>"In the morning, hear the Way;
>> in the evening, die content!"
>> -- Confucius
>
>
> Another "simplification" to try is removing the
> inequality test, (> ?y 1), between the two
> equality tests. It's conceivable that the
> inequality test, by forcing "evaluation" of
> its expressions, has an unintended side-effect
> on variable ?y.
Thx. It turns out that simply repeating the rule is enough to surface
what turned out to be a long-standing but undiscovered bug in the
implementation.
cheers, kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
Den Thu, 17 Jan 2008 07:29:11 -0800 skrev Chip Eastham:
[snip long quote]
>> thx, kt
>>
>> --http://www.theoryyalgebra.com/
>>
>> "In the morning, hear the Way;
>> in the evening, die content!"
>> -- Confucius
>
> Another "simplification" to try is removing the inequality test, (> ?y
> 1), between the two equality tests. It's conceivable that the
> inequality test, by forcing "evaluation" of its expressions, has an
> unintended side-effect on variable ?y.
>
> regards, chip
How about _trimming quotes_ every once in a while and inserting your
reply in a place where, oh dunno, it makes sense and has some context, as
opposed to under the signature? Not to mention that your newsreader is
broken and mangles the separator, inserting sigs in the quoted body.
Maciej
On 16 Jan, 17:39, Ken Tilton <···········@optonline.net> wrote:
> Total noob, here, using a Lisp implementation of Prolog (AllegroCL's, to
> be precise) in case anything looks odd.
>
> Given:
>
> (<-- (gcf ?x ?y ?f)
> (is ?f (gcd ?x ?y))) ;; is/2 let's me use Lisp in the second arg
>
> (<-- (> ?x ?y)
> (lispp (> ?x ?y))) ;; some more embedded Lisp
>
> Applying the above, we test a hardcoded pair (12 1nd 15) to see if they
> have gcf > 1:
>
> (?- (gcf 15 12 ?x)
> (= ?x ?y)
> (> ?y 1))
>
> ?X = 3
> ?Y = 3
>
> No.
>
> Fine. But now:
>
> (?- (gcf 15 12 ?x)
> (= ?x ?y)
> (> ?y 1)
> (= ?x ?y))
>
> No.
>
> The duplication of the line (in the real world case from which this was
> distilled) was inadvertent and has been corrected, but I am still
> curious as to why it causes the rule to fail. Is this proper Prolog, or
> should I make a bug report to the vendor?
>
> kt
>
> ps. duh, it just occurred to me to grab a prolog somewhere and try
> something similar in pure prolog. will do. kt
>
> --http://www.theoryyalgebra.com/
>
> "In the morning, hear the Way;
> in the evening, die content!"
> -- Confucius
This is what I get under Qi Prolog.
Qi 2007, Copyright (C) 2001-2007 Mark Tarver
www.lambdassociates.org
version 9.0 (Turbo-E)
(0-) (defprolog
"gcf(X,Y,F) :- is(F, (gcd X Y)).
gter(X, Y) :- when((> X Y)).
kenny(X) :- gcf(15,12,X), =(X,Y), gter(Y,1), =(X,Y).")
[gcf* gter* kenny*]
(1-) (define gcd
X Y -> (GCD X Y))
======> Warning:
the following variables are free in gcd: GCD;
gcd
(2-) (ask [kenny X])
X = 3
More? (y/n) y
run time 0 seconds
5 logical inferences
infinite LIPS
false
Mark
Mark Tarver wrote:
> On 16 Jan, 17:39, Ken Tilton <···········@optonline.net> wrote:
>
>>Total noob, here, using a Lisp implementation of Prolog (AllegroCL's, to
>>be precise) in case anything looks odd.
>>
>>Given:
>>
>>(<-- (gcf ?x ?y ?f)
>> (is ?f (gcd ?x ?y))) ;; is/2 let's me use Lisp in the second arg
>>
>>(<-- (> ?x ?y)
>> (lispp (> ?x ?y))) ;; some more embedded Lisp
>>
>>Applying the above, we test a hardcoded pair (12 1nd 15) to see if they
>>have gcf > 1:
>>
>>(?- (gcf 15 12 ?x)
>> (= ?x ?y)
>> (> ?y 1))
>>
>>?X = 3
>>?Y = 3
>>
>>No.
>>
>>Fine. But now:
>>
>>(?- (gcf 15 12 ?x)
>> (= ?x ?y)
>> (> ?y 1)
>> (= ?x ?y))
>>
>>No.
>>
>>The duplication of the line (in the real world case from which this was
>>distilled) was inadvertent and has been corrected, but I am still
>>curious as to why it causes the rule to fail. Is this proper Prolog, or
>>should I make a bug report to the vendor?
>>
>>kt
>>
>>ps. duh, it just occurred to me to grab a prolog somewhere and try
>>something similar in pure prolog. will do. kt
>>
>>--http://www.theoryyalgebra.com/
>>
>>"In the morning, hear the Way;
>> in the evening, die content!"
>> -- Confucius
>
>
>
> This is what I get under Qi Prolog.
>
> Qi 2007, Copyright (C) 2001-2007 Mark Tarver
> www.lambdassociates.org
> version 9.0 (Turbo-E)
>
> (0-) (defprolog
>
> "gcf(X,Y,F) :- is(F, (gcd X Y)).
> gter(X, Y) :- when((> X Y)).
>
> kenny(X) :- gcf(15,12,X), =(X,Y), gter(Y,1), =(X,Y).")
> [gcf* gter* kenny*]
>
> (1-) (define gcd
> X Y -> (GCD X Y))
> ======> Warning:
> the following variables are free in gcd: GCD;
> gcd
>
> (2-) (ask [kenny X])
>
> X = 3
>
> More? (y/n) y
>
> run time 0 seconds
> 5 logical inferences
> infinite LIPS
> false
Thanks. A little leashing indicates the second occurrence of (= ?x ?y)
causes (as best my poor understanding of Prolog allows) ACL Prolog to go
looking for a second value to bind to ?x, so I see it backtracing into
gcf and then failing... why is that? gcf (now) looks like this:
(<-- (gcf ?x ?y ?f)
(lisp ?f (gcd ?x ?y)))
That is a little more succinct than the original, with no effect on the
issue at hand. All invocations have ?x and ?y bound and ?f unbound.
Seems to me the next clause should always be able to bind ?f.
back to the doc....
kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
On 16 Jan, 19:50, Ken Tilton <···········@optonline.net> wrote:
> Mark Tarver wrote:
> > On 16 Jan, 17:39, Ken Tilton <···········@optonline.net> wrote:
>
> >>Total noob, here, using a Lisp implementation of Prolog (AllegroCL's, to
> >>be precise) in case anything looks odd.
>
> >>Given:
>
> >>(<-- (gcf ?x ?y ?f)
> >> (is ?f (gcd ?x ?y))) ;; is/2 let's me use Lisp in the second arg
>
> >>(<-- (> ?x ?y)
> >> (lispp (> ?x ?y))) ;; some more embedded Lisp
>
> >>Applying the above, we test a hardcoded pair (12 1nd 15) to see if they
> >>have gcf > 1:
>
> >>(?- (gcf 15 12 ?x)
> >> (= ?x ?y)
> >> (> ?y 1))
>
> >>?X = 3
> >>?Y = 3
>
> >>No.
>
> >>Fine. But now:
>
> >>(?- (gcf 15 12 ?x)
> >> (= ?x ?y)
> >> (> ?y 1)
> >> (= ?x ?y))
>
> >>No.
>
> >>The duplication of the line (in the real world case from which this was
> >>distilled) was inadvertent and has been corrected, but I am still
> >>curious as to why it causes the rule to fail. Is this proper Prolog, or
> >>should I make a bug report to the vendor?
>
> >>kt
>
> >>ps. duh, it just occurred to me to grab a prolog somewhere and try
> >>something similar in pure prolog. will do. kt
>
> >>--http://www.theoryyalgebra.com/
>
> >>"In the morning, hear the Way;
> >> in the evening, die content!"
> >> -- Confucius
>
> > This is what I get under Qi Prolog.
>
> > Qi 2007, Copyright (C) 2001-2007 Mark Tarver
> >www.lambdassociates.org
> > version 9.0 (Turbo-E)
>
> > (0-) (defprolog
>
> > "gcf(X,Y,F) :- is(F, (gcd X Y)).
> > gter(X, Y) :- when((> X Y)).
>
> > kenny(X) :- gcf(15,12,X), =(X,Y), gter(Y,1), =(X,Y).")
> > [gcf* gter* kenny*]
>
> > (1-) (define gcd
> > X Y -> (GCD X Y))
> > ======> Warning:
> > the following variables are free in gcd: GCD;
> > gcd
>
> > (2-) (ask [kenny X])
>
> > X = 3
>
> > More? (y/n) y
>
> > run time 0 seconds
> > 5 logical inferences
> > infinite LIPS
> > false
>
> Thanks. A little leashing indicates the second occurrence of (= ?x ?y)
> causes (as best my poor understanding of Prolog allows) ACL Prolog to go
> looking for a second value to bind to ?x, so I see it backtracing into
> gcf and then failing... why is that? gcf (now) looks like this:
>
> (<-- (gcf ?x ?y ?f)
> (lisp ?f (gcd ?x ?y)))
>
> That is a little more succinct than the original, with no effect on the
> issue at hand. All invocations have ?x and ?y bound and ?f unbound.
> Seems to me the next clause should always be able to bind ?f.
>
> back to the doc....
>
> kt
>
> --http://www.theoryyalgebra.com/
>
> "In the morning, hear the Way;
> in the evening, die content!"
> -- Confucius- Hide quoted text -
>
> - Show quoted text -
I would say you have a bug in ACL Prolog. Btw what is the role of
Prolog in your app (just curious)?
Mark
Mark Tarver wrote:
> On 16 Jan, 19:50, Ken Tilton <···········@optonline.net> wrote:
>
>>Mark Tarver wrote:
>>
>>>On 16 Jan, 17:39, Ken Tilton <···········@optonline.net> wrote:
>>
>>>>Total noob, here, using a Lisp implementation of Prolog (AllegroCL's, to
>>>>be precise) in case anything looks odd.
>>
>>>>Given:
>>
>>>>(<-- (gcf ?x ?y ?f)
>>>> (is ?f (gcd ?x ?y))) ;; is/2 let's me use Lisp in the second arg
>>
>>>>(<-- (> ?x ?y)
>>>> (lispp (> ?x ?y))) ;; some more embedded Lisp
>>
>>>>Applying the above, we test a hardcoded pair (12 1nd 15) to see if they
>>>>have gcf > 1:
>>
>>>>(?- (gcf 15 12 ?x)
>>>> (= ?x ?y)
>>>> (> ?y 1))
>>
>>>>?X = 3
>>>>?Y = 3
>>
>>>>No.
>>
>>>>Fine. But now:
>>
>>>>(?- (gcf 15 12 ?x)
>>>> (= ?x ?y)
>>>> (> ?y 1)
>>>> (= ?x ?y))
>>
>>>>No.
>>
>>>>The duplication of the line (in the real world case from which this was
>>>>distilled) was inadvertent and has been corrected, but I am still
>>>>curious as to why it causes the rule to fail. Is this proper Prolog, or
>>>>should I make a bug report to the vendor?
>>
>>>>kt
>>
>>>>ps. duh, it just occurred to me to grab a prolog somewhere and try
>>>>something similar in pure prolog. will do. kt
>>
>>>>--http://www.theoryyalgebra.com/
>>
>>>>"In the morning, hear the Way;
>>>> in the evening, die content!"
>>>> -- Confucius
>>
>>>This is what I get under Qi Prolog.
>>
>>>Qi 2007, Copyright (C) 2001-2007 Mark Tarver
>>>www.lambdassociates.org
>>>version 9.0 (Turbo-E)
>>
>>>(0-) (defprolog
>>
>>> "gcf(X,Y,F) :- is(F, (gcd X Y)).
>>> gter(X, Y) :- when((> X Y)).
>>
>>> kenny(X) :- gcf(15,12,X), =(X,Y), gter(Y,1), =(X,Y).")
>>>[gcf* gter* kenny*]
>>
>>>(1-) (define gcd
>>> X Y -> (GCD X Y))
>>>======> Warning:
>>>the following variables are free in gcd: GCD;
>>>gcd
>>
>>>(2-) (ask [kenny X])
>>
>>>X = 3
>>
>>>More? (y/n) y
>>
>>>run time 0 seconds
>>>5 logical inferences
>>>infinite LIPS
>>>false
>>
>>Thanks. A little leashing indicates the second occurrence of (= ?x ?y)
>>causes (as best my poor understanding of Prolog allows) ACL Prolog to go
>>looking for a second value to bind to ?x, so I see it backtracing into
>>gcf and then failing... why is that? gcf (now) looks like this:
>>
>>(<-- (gcf ?x ?y ?f)
>> (lisp ?f (gcd ?x ?y)))
>>
>>That is a little more succinct than the original, with no effect on the
>>issue at hand. All invocations have ?x and ?y bound and ?f unbound.
>>Seems to me the next clause should always be able to bind ?f.
>>
>>back to the doc....
>>
>>kt
>>
>>--http://www.theoryyalgebra.com/
>>
>>"In the morning, hear the Way;
>> in the evening, die content!"
>> -- Confucius- Hide quoted text -
>>
>>- Show quoted text -
>
>
> I would say you have a bug in ACL Prolog. Btw what is the role of
> Prolog in your app (just curious)?
Suppose you want to help a student with a problem by solving for them
one that has all the salient characteristics of their problem. The
functional requirement is "make a new problem just like this problem
only different". If we randomly choose new numbers, we will likely not
get a similar problem. Consider:
5/12 * 18/5
Now, having solved that problem thus:
5*6*3 / 6*2*5 ; merge and factor out gcf
3/2 ; cancel like factors
...and having all the details of the solution available (transformations
and results and operands of each) we can try building a new problem that
is the same. My current approach is to define methods dispatched on each
transformation ID, eg (eql 'mrg-n-factor), and have anyone who cares
offer constraints, such as any original numerator/denominator pair being
co-prime (or they could just simplify that before multiplying, which
would be a fine problem but a different kind of problem, which would be
not fine).
Long experience tells me this is a devilish problem to get right, and
the downside is truly horrific random problems. I may yet have to role
my own unifier, but with Prolog just sitting there...
kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
From: Paul Tarvydas
Subject: Re: Nooby stumped by effect of repeated rule
Date:
Message-ID: <fmlm00$59d$1@aioe.org>
I've got a debugged version of PAIP (if you want it, ask me ; also, I have
an alpha version of a WAM written in CL patterned closely on Hassan
Ait-Kaci's tutorial, if someone wants to continue debugging it...).
To (begin to) answer your question, here is what my PAIP compiles your
top-level queries to:
This:
(?- (gcf 15 12 ?x) (= ?x ?y) (>> ?y 1))
compiles to:
(DEFUN TOP-LEVEL-QUERY/0 (CONT)
(LET ((?X (?)))
(GCF/3 '15
'12
?X
#'(LAMBDA ()
(>>/2 ?X '1 #'(LAMBDA () (SHOW-PROLOG-VARS/2 '("?X" "?Y")
(LIST ?X ?X) CONT)))))))
While this:
(?- (gcf 15 12 ?x) (= ?x ?y) (>> ?y 1) (= ?x ?y))
compiles to:
(DEFUN TOP-LEVEL-QUERY/0 (CONT)
(LET ((?X (?))) (GCF/3 '15 '12 ?X #'(LAMBDA () (>>/2 ?X '1 #'(LAMBDA ()
NIL))))))
I.E. the PAIP compiler 'optimizes' the second query to fail.
Likewise:
(?- (= ?x ?y) (= ?x ?y))
compiles to:
(DEFUN TOP-LEVEL-QUERY/0 (CONT) NIL)
Why? I don't know, yet...
pt
on swi-prolog:
1 ?- X = Y, X = Y.
X = Y
could it be that the first and second ?y somehow refer to different
variables? (this would be a bug IMHO). What happens if instead of ?y
you use an anonymous variable? (that would be _ in Prolog I think,
don't know in your implementation...)
AS
Paul Tarvydas wrote:
> I've got a debugged version of PAIP (if you want it, ask me ; also, I have
> an alpha version of a WAM written in CL patterned closely on Hassan
> Ait-Kaci's tutorial, if someone wants to continue debugging it...).
>
> To (begin to) answer your question, here is what my PAIP compiles your
> top-level queries to:
>
>
> This:
> (?- (gcf 15 12 ?x) (= ?x ?y) (>> ?y 1))
>
> compiles to:
>
> (DEFUN TOP-LEVEL-QUERY/0 (CONT)
> (LET ((?X (?)))
> (GCF/3 '15
> '12
> ?X
> #'(LAMBDA ()
> (>>/2 ?X '1 #'(LAMBDA () (SHOW-PROLOG-VARS/2 '("?X" "?Y")
> (LIST ?X ?X) CONT)))))))
>
>
> While this:
>
> (?- (gcf 15 12 ?x) (= ?x ?y) (>> ?y 1) (= ?x ?y))
>
> compiles to:
>
> (DEFUN TOP-LEVEL-QUERY/0 (CONT)
> (LET ((?X (?))) (GCF/3 '15 '12 ?X #'(LAMBDA () (>>/2 ?X '1 #'(LAMBDA ()
> NIL))))))
>
> I.E. the PAIP compiler 'optimizes' the second query to fail.
>
> Likewise:
> (?- (= ?x ?y) (= ?x ?y))
>
> compiles to:
> (DEFUN TOP-LEVEL-QUERY/0 (CONT) NIL)
>
> Why? I don't know, yet...
>
Ah, thx, could be relevant since ACL Prolog began from Norvig's.
Well, luckily that was a mistake having the same clause in twice, I'll
get on with my life (which might eventually lead to borrowing your alpha
WAM).
kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
From: Paul Tarvydas
Subject: Re: Nooby stumped by effect of repeated rule
Date:
Message-ID: <fmlum8$3mt$1@aioe.org>
It *seems* that there is a simple case missing from Norvig's table in
section 12.4 "Improving the Compilation of Unification" (pg. 402).
Case 1a should be a test for (= ?x ?x) resulting in T and no new bindings.
Adding this line
((eq x y) (values t bindings)) ; 1a same variable - pt
as the second case in the COND of compile-unify-variable appears to fix the
problem. More extensive testing may be required :-).
pt
ps. on page 354, Norvig states that a variable should always match itself,
but one needs to be careful not to bind the variable to itself, e.g.
(?x . ?x) (which results in infinite looping during lookup). The ((eql x
y) bindings) line appears on page 354, but was (apparently) missed on page
403, even though he mentions the problem and the need for care on page 401.
Paul Tarvydas wrote:
> It *seems* that there is a simple case missing from Norvig's table in
> section 12.4 "Improving the Compilation of Unification" (pg. 402).
>
> Case 1a should be a test for (= ?x ?x) resulting in T and no new bindings.
Is this relevant in my case, where I repeated (= ?x ?y) twice? I gather
yes in this case since you report that it cures.
>
> Adding this line
>
> ((eq x y) (values t bindings)) ; 1a same variable - pt
>
> as the second case in the COND of compile-unify-variable appears to fix the
> problem. More extensive testing may be required :-).
Nah, let's ship. What are users for if not testing?
Thx, I have passed your sleuthing along to Franz in case they are not
monitoring c.l.l today to make sure I am earning the kickbacks.
kt
>
> pt
>
> ps. on page 354, Norvig states that a variable should always match itself,
> but one needs to be careful not to bind the variable to itself, e.g.
> (?x . ?x) (which results in infinite looping during lookup). The ((eql x
> y) bindings) line appears on page 354, but was (apparently) missed on page
> 403, even though he mentions the problem and the need for care on page 401.
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
From: Paul Tarvydas
Subject: Re: Nooby stumped by effect of repeated rule
Date:
Message-ID: <fmm0hn$9hp$1@aioe.org>
Ken Tilton wrote:
>
>
> Paul Tarvydas wrote:
>> It *seems* that there is a simple case missing from Norvig's table in
>> section 12.4 "Improving the Compilation of Unification" (pg. 402).
>>
>> Case 1a should be a test for (= ?x ?x) resulting in T and no new
>> bindings.
>
> Is this relevant in my case, where I repeated (= ?x ?y) twice? I gather
> yes in this case since you report that it cures.
Yep. I set a breakpoint and followed it around for:
(?- (= ?x ?y) (= ?x ?y))
which is a simplification of your original problem.
(Which, before my fix, compiled to FAIL).
pt
Paul Tarvydas wrote:
> Ken Tilton wrote:
>
>
>>
>>Paul Tarvydas wrote:
>>
>>>It *seems* that there is a simple case missing from Norvig's table in
>>>section 12.4 "Improving the Compilation of Unification" (pg. 402).
>>>
>>>Case 1a should be a test for (= ?x ?x) resulting in T and no new
>>>bindings.
>>
>>Is this relevant in my case, where I repeated (= ?x ?y) twice? I gather
>>yes in this case since you report that it cures.
>
>
> Yep. I set a breakpoint and followed it around for:
>
> (?- (= ?x ?y) (= ?x ?y))
>
> which is a simplification of your original problem.
>
> (Which, before my fix, compiled to FAIL).
>
Coolio. Thx for digging into this.
kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
Ken Tilton wrote:
>
>
> Paul Tarvydas wrote:
>
>> Ken Tilton wrote:
>>
>>
>>>
>>> Paul Tarvydas wrote:
>>>
>>>> It *seems* that there is a simple case missing from Norvig's table in
>>>> section 12.4 "Improving the Compilation of Unification" (pg. 402).
>>>>
>>>> Case 1a should be a test for (= ?x ?x) resulting in T and no new
>>>> bindings.
>>>
>>>
>>> Is this relevant in my case, where I repeated (= ?x ?y) twice? I gather
>>> yes in this case since you report that it cures.
>>
>>
>>
>> Yep. I set a breakpoint and followed it around for:
>>
>> (?- (= ?x ?y) (= ?x ?y))
>>
>> which is a simplification of your original problem.
>>
>> (Which, before my fix, compiled to FAIL).
>>
>
> Coolio. Thx for digging into this.
Franz indicates this is a known bug with a provisional patch in need of
further testing. They note that the bug has existed for fifteen years
without being noticed (ok, someone beat me to it by two months), which I
take as a great compliment. Unless they meant... uh-oh.
:)
kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
Ken Tilton wrote:
> Ken Tilton wrote:
>>
>> Paul Tarvydas wrote:
>> Coolio. Thx for digging into this.
>
> Franz indicates this is a known bug with a provisional patch in need of
> further testing. They note that the bug has existed for fifteen years
> without being noticed (ok, someone beat me to it by two months), which I
> take as a great compliment.
As Ken says, we have discussed this offline (on Franz support).
The failure of
(<- (test ?x ?y) (= ?x ?y) (= ?x ?y))
is a bug both in Norvig's PAIP implementation and in Allegro Prolog
which derives from it. I will eventually get around to fixing it
(and will of course send the fixes to Peter, assuming they can be
adapted to his original implementation) along with another bug or two
I've found over the years. But I want to point out that these bugs
only affect rather odd, atypical code, otherwise they wouldn't have
required 15 years to encounter.
Allegro Prolog derives directly from Norvig's excellent development
in PAIP, but has been extended according to various application needs
(it is used in the query engine for the AllegroGraph RDF database)
and has profited greatly in efficiency by being able to exploit various
nonportable capabilities of one particular implementation. In
particular, ACL Prolog achieves 4 MLIPS on the zebra problem, which is
between 1 and 2 orders of magnitude faster than Norvig's original (on
the same hardware), and also manages to run essentially without consing.
I haven;t studied the analyses of the bug that appear earlier in this
thread, but I don't think they are correct. Prolog = is not implemented
as a functor; rather, the compiler `inlines' it when doing a Prolog
compile. If the arguments are variables it binds the variables
together in the `bindings' list and continues the compilation with that
equality in effect. Norvig's bug is that the compile-time and run-time
unifications don't keep track of each other properly.
This would probably be easier to fox than to describe cogently...
Steven M. Haflich wrote:
> Ken Tilton wrote:
>
>> Ken Tilton wrote:
>>
>>>
>>> Paul Tarvydas wrote:
>>> Coolio. Thx for digging into this.
>>
>>
>> Franz indicates this is a known bug with a provisional patch in need
>> of further testing. They note that the bug has existed for fifteen
>> years without being noticed (ok, someone beat me to it by two months),
>> which I take as a great compliment.
>
>
> As Ken says, we have discussed this offline (on Franz support).
> The failure of
>
> (<- (test ?x ?y) (= ?x ?y) (= ?x ?y))
>
> is a bug both in Norvig's PAIP implementation and in Allegro Prolog
> which derives from it. I will eventually get around to fixing it
> (and will of course send the fixes to Peter, assuming they can be
> adapted to his original implementation) along with another bug or two
> I've found over the years. But I want to point out that these bugs
> only affect rather odd, atypical code, otherwise they wouldn't have
> required 15 years to encounter.
Indeed, and I have apologized to Steve for not having mentioned up front
that I was just making the report FTI (for their information -- well,
hmmm, I probably copped to having the duplicated the clause --
anyway...) and that I had cleaned up my code and already moved on. This
may have been because I had noticed something in the ACL prolog doc
encouraging IRs.
The punch line is that Steve provided two options, eval and run slower
and simply call the compiler on the form and run faster. I be doing the
latter, ten times faster with compiling, and all of that is the compiling.
Meanwhile it has occurred to me that I can take the standard problems
and precompile out a lisp form in its own little text file and then
compile it so "textbook" problems will clone fast. Only when cloning
students work to help them by example will we truly need the on-the-fly
scripting of prolog queries to solve to clone novel problems.
kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
From: Paul Tarvydas
Subject: Re: Nooby stumped by effect of repeated rule
Date:
Message-ID: <fmojmp$omf$1@aioe.org>
Steven M. Haflich wrote:
> Prolog = is not implemented
> as a functor; rather, the compiler `inlines' it when doing a Prolog
> compile.
Yes, that's exactly where I suggested the fix should go. The inlining
compile-time unifier is the function "compile-unify-variable". The fix has
to precede the call to "find-anywhere" in that function.
> Norvig's bug is that the compile-time and run-time
> unifications don't keep track of each other properly.
The compile-time unification mistakenly fails (due to find-anywhere) if the
variables are one in the same. The inliner thinks that it has a case "11"
on its hands, ie. ?x against f(?x), without first weeding out the ?x eq ?x
case - and compiles this into an immediate failure.
pt
Paul Tarvydas wrote:
> Steven M. Haflich wrote:
>
>> Prolog = is not implemented
>> as a functor; rather, the compiler `inlines' it when doing a Prolog
>> compile.
>
> Yes, that's exactly where I suggested the fix should go. The inlining
> compile-time unifier is the function "compile-unify-variable". The fix has
> to precede the call to "find-anywhere" in that function.
>
>> Norvig's bug is that the compile-time and run-time
>> unifications don't keep track of each other properly.
>
> The compile-time unification mistakenly fails (due to find-anywhere) if the
> variables are one in the same. The inliner thinks that it has a case "11"
> on its hands, ie. ?x against f(?x), without first weeding out the ?x eq ?x
> case - and compiles this into an immediate failure.
I think your analysis is going in the right direction, but i caution
that the bug may be a little more pervasive than you think. The first
indication I have about this bug was a few months ago when a customer
reported a case that reduced to this:
cl-user(16): (?- (= (a ?x c) (a (d) ?x)))
?x = c
I'm not sure this case is subsumed by your analysis, but this kind of
thing is very hard to think about. Actually, it's easy to think about,
but it is hard to think about while maintaining any confidence in the
thought process... That's why, despite this egregious bug, I really
respect Norvig's thought process.
If you devise any fix for the Norvig code befor I have time to do so,
I'd appreciate hearing about it. But make sure it corrects the above
example as well.
On Jan 19, 4:51 am, "Steven M. Haflich" <····@alum.mit.edu> wrote:
> cl-user(16): (?- (= (a ?x c) (a (d) ?x)))
> ?x = c
>
> I'm not sure this case is subsumed by your analysis, but this kind of
Yes, a quick test shows that my suggested fix does not address the
above problem.
At the moment, I think that these are two separate bugs (Kenny's
problem vs. the above snippet) - but, we'll see...
> thing is very hard to think about. Actually, it's easy to think about,
After seeing the above example, I now understand your earlier
comments.
> but it is hard to think about while maintaining any confidence in the
> thought process... That's why, despite this egregious bug, I really
> respect Norvig's thought process.
This is simply "compiler optimization" thinking. 99.99% of the
optimization cases are "obvious". The other 0.0001% of cases show up
some time later.
> If you devise any fix for the Norvig code before I have time to do so,
> I'd appreciate hearing about it. But make sure it corrects the above
> example as well.
OK.
pt
From: Paul Tarvydas
Subject: Re: Nooby stumped by effect of repeated rule
Date:
Message-ID: <fn0dfi$rmf$1@aioe.org>
I believe that these were two separate bugs and, I propose fixes for both
(see lines below marked with "pt").
The first bug (from my perspective :-) was Kenny's
(?- (= ?x ?y) (= ?x ?y))
and is solved by adding case 1a - checking for ?x eq ?x.
The second bug devolves to:
(?- (= (?x c) ((d) ?x)))
and is caused by an error in the optimization table of section 12.4 (page
402 in my copy of paip).
Case #10 involves unification of two (or more) variables, yet the "bindings"
column shows only one new binding. The table should show bindings of
(?x . ?x) and (?y . ?y). Case #10 deals with the unbound variable ?x, as
opposed to case #7 which deals with an already-bound variable (?arg1).
The compiler compiles (?- (?x c) ((d) ?x) by first unifying the two heads ?x
and (d), which is case #10. It is at this point that the original
table/code "forgets" to mark ?x as "bound" (i.e. by adding (?x . ?x) to the
bindings). When the tail is unified - c and ?x - the compiler sees that ?x
is "still unbound" and merrily compiles new binding code for it.
The proposed fix consists of breaking case 10 from case 7 and adding
(?x . ?x) to the bindings in case 10 (by calling bind-variables-in for ?x).
And, then, we notice that Norvig left an optimization on the table. In this
example, "(d)" is a constant (contains no variables), but Norvig's code
misses this case because the code checks for (consp y1) without also
checking whether y1 is manifestly constant. His code marks the last clause
of the cond as being case #9 but fails to note that it is only a sub-case
of case #9.
So, the proposed fix adds a check for manifest constant lists in the same
place as case 7&10 are weeded out. I've marked this check as case #9a.
Thankfully, the function "compile-unify-variable" has a fairly strong
precondition - X is always a variable (bound or unbound) - and, so it is
possible to think about each of the cases without getting too wooly.
Please do let me know if you agree. I know from experience that fixing
someone else's optimization code can cause new bugs to appear...
pt
(defun compile-unify-variable (x y bindings)
"X is a variable, and Y may be."
(let* ((xb (follow-binding x bindings))
(x1 (if xb (cdr xb) x))
(yb (if (variable-p y) (follow-binding y bindings)))
(y1 (if yb (cdr yb) y)))
(cond ; Case:
((or (eq x '?) (eq y '?)) (values t bindings)) ; 12
((eq x y) (values t bindings)) ; 1a same
variable - pt
((not (and (equal x x1) (equal y y1))) ; deref
(compile-unify x1 y1 bindings))
((find-anywhere x1 y1) (values nil bindings)) ; 11
((consp y1) ; 7,10,9a
(if (and (null xb) ; x unbound - pt
(not (has-variable-p y1))) ; y is a constant
list - pt
(values 't (extend-bindings x1 y1 bindings)) ; 9a - pt
(values `(unify! ,x1 ,(compile-arg y1 bindings))
(bind-variables-in y1
(if (null xb)
(bind-variables-in x1 bindings) ;
10 - pt
bindings))))) ; 7
((not (null xb))
;; i.e. x is an ?arg variable
(if (and (variable-p y1) (null yb))
(values 't (extend-bindings y1 x1 bindings)) ; 4
(values `(unify! ,x1 ,(compile-arg y1 bindings))
(extend-bindings x1 y1 bindings)))) ; 5,6
((not (null yb))
(compile-unify-variable y1 x1 bindings))
(t (values 't (extend-bindings x1 y1 bindings)))))) ; 8,9
test cases:
(?- (= (?x c) ((d) ?x)))
(?- (= ((d) ?x) (?x c)))
(?- (= (?x (d)) ((d) ?x)))
(?- (= ?x 1) (= (?x c) ((d) ?x)))
(?- (= ?x ?y) (= ?x ?y))
(?- (= ((?y) ?x) (?x c)))
(?- (= ((?y) ?x) (?x (c))))