Nooby stumped by effect of repeated rule

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

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

On Jan 16, 1:20 pm, Ken Tilton <kennytil...@optonline.net> wrote:
> Chip Eastham wrote:
> > On Jan 16, 12:39 pm, Ken Tilton <kennytil...@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 <kennytil...@optonline.net> wrote:
>
>>Chip Eastham wrote:
>>
>>>On Jan 16, 12:39 pm, Ken Tilton <kennytil...@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