While using PAIPROLOG in sbcl 0.9.4 I ran into something strange.
If I do the following:
(load (compile-file "package.lisp"))
(load (compile-file "auxfns.lisp"))
(load (compile-file "patmatch.lisp"))
(load (compile-file "unify.lisp"))
(load (compile-file "prolog.lisp"))
(use-package "PAIPROLOG")
(<- (likes Kim Robin))
(<- (likes Sandy Lee))
(<- (likes Sandy Kim))
(<- (likes Robin cats))
(<- (likes Sandy ?x) (likes ?x cats))
(<- (likes Kim ?x) (likes ?x Lee) (likes ?x Kim))
and then type the query:
(?- (likes ?x ?y) (likes ?y ?x))
I get the following output:
?Y = KIM
?X = SANDY;
?Y = SANDY
?X = KIM;
No.
which is expected. However, if I add the rule:
(<- (likes ?x ?x))
then the same query gives me:
?Y = KIM
?X = SANDY;
?Y = SANDY
?X = SANDY;
?Y = SANDY
?X = SANDY;
?Y = SANDY
?X = KIM;
?Y = SANDY
?X = SANDY;
?Y = ?X4216
?X = ?X4216;
No.
which has sandy liking sandy a bit too much and a gensym liking itself.
Is that what other prolog's would give for those rules or is something
amiss?
Thanks.
John wrote:
> While using PAIPROLOG in sbcl 0.9.4 I ran into something strange.
>
> If I do the following:
>
> (load (compile-file "package.lisp"))
> (load (compile-file "auxfns.lisp"))
> (load (compile-file "patmatch.lisp"))
> (load (compile-file "unify.lisp"))
> (load (compile-file "prolog.lisp"))
> (use-package "PAIPROLOG")
> (<- (likes Kim Robin))
> (<- (likes Sandy Lee))
> (<- (likes Sandy Kim))
> (<- (likes Robin cats))
> (<- (likes Sandy ?x) (likes ?x cats))
> (<- (likes Kim ?x) (likes ?x Lee) (likes ?x Kim))
Translated into regular Prolog, this is:
likes('Kim' , 'Robin').
likes('Sandy', 'Lee').
likes('Sandy', 'Kim').
likes('Robin', 'cats').
likes('Sandy', X) :- likes(X, 'cats').
likes('Kim', X) :- likes(X, 'Lee'), likes(X, 'Kim').
> and then type the query:
>
> (?- (likes ?x ?y) (likes ?y ?x))
>
> I get the following output:
>
> ?Y = KIM
> ?X = SANDY;
>
> ?Y = SANDY
> ?X = KIM;
>
> No.
Yup:
?- likes(X,Y), likes(Y, X), write(('X'=X, 'Y'=Y)), nl, fail.
X=Sandy, Y=Kim
X=Kim, Y=Sandy
(fail)
> which is expected. However, if I add the rule:
>
> (<- (likes ?x ?x))
>
> then the same query gives me:
>
> ?Y = KIM
> ?X = SANDY;
>
> ?Y = SANDY
> ?X = SANDY;
>
> ?Y = SANDY
> ?X = SANDY;
>
> ?Y = SANDY
> ?X = KIM;
>
> ?Y = SANDY
> ?X = SANDY;
>
> ?Y = ?X4216
> ?X = ?X4216;
>
> No.
>
> which has sandy liking sandy a bit too much and a gensym liking itself.
>
> Is that what other prolog's would give for those rules or is something
> amiss?
Nothing is amiss:
X=Sandy, Y=Kim
X=Sandy, Y=Sandy
X=Sandy, Y=Sandy
X=Kim, Y=Sandy
X=Sandy, Y=Sandy
X=_G399, Y=_G399
(fail)
Prolog gives you the most general unifier; and because you've got the
clause "likes(X, X)", you get the result X,X (or whatever other symbol
you want, e.g. _G399,_G399 or _X4216,_X4216).
>
> Thanks.
Paraphrasing Greenspun: Any sufficiently complicated Lisp program
contains an ad hoc informally-specified bug-ridden slow implementation
of half of Prolog.
[And vice-versa]
So, you might want to try the real thing at http://www.swi-prolog.org/
... or one of the others mentioned at
http://www.cs.kuleuven.ac.be/~remko/prolog/faq/files/faq.html#AEN36
[interesting extensions include constraints (SWI, Eclipse, others);
blackboarding (Bin-Prolog); tabling (XSB)].
<··············@gmail.com> schrieb im Newsbeitrag
·····························@g14g2000cwa.googlegroups.com...
> ...
> Paraphrasing Greenspun: Any sufficiently complicated Lisp program
> contains an ad hoc informally-specified bug-ridden slow implementation
> of half of Prolog.
> [And vice-versa]
> ...
But, if I understand things right, the Lisp Prolog works correctly?
Andreas ;)
Andreas Thiele wrote:
> But, if I understand things right, the Lisp Prolog works correctly?
Yes, these results are correct.
Thought experiment: if you had just this one rule
(admires ?a ?a)
and made this query
(?- (admires ?x ?y) (admires ?y ?x))
What would you expect for the result?
By the way, these questions are probably more natural for
comp.lang.prolog than comp.lang.lisp. There are a couple
obscure bugs in the PAIP Prolog code, but they are not
easy bugs to run into.
"Steven M. Haflich" <···@alum.mit.edu> writes:
> By the way, these questions are probably more natural for
> comp.lang.prolog than comp.lang.lisp. There are a couple
> obscure bugs in the PAIP Prolog code, but they are not
> easy bugs to run into.
On the assumption that the OP was talking about the update of the PAIP
Prolog code that I've made available, I believe the obscure bugs
(mostly involving the behaviour of the cut in conjunction and
disjunction) are fixed, and that the engine conforms to ISO semantics.
There are some relatively non-obscure bugs remaining, in mismatches
between the CL and Prolog stream concepts, in bagof and setof, and in
the non-ISO equivalence of functorial and list expressions.
Christophe
Christophe Rhodes wrote:
> On the assumption that the OP was talking about the update of the PAIP
> Prolog code that I've made available, I believe the obscure bugs
> (mostly involving the behaviour of the cut in conjunction and
> disjunction) are fixed, and that the engine conforms to ISO semantics.
> There are some relatively non-obscure bugs remaining, in mismatches
> between the CL and Prolog stream concepts, in bagof and setof, and in
> the non-ISO equivalence of functorial and list expressions.
I was referring to the code published by Norvig (including web updates).
I'm not familiar with your update, but will try to take a look at it
when I have a chace.
I'm the author of Allegro Prolog, which is based on the Norvig code but
``improved'' with various portable and nonportable optimizations. When
I last compared benchmarks with Norvig's, AP ran about 1.5x10^3 times
faster. I estimate about half (logarhythmically) of this improvement
is due to improvements in raw computer performance, and the other half
is due to code optimization. (Also, AP normally runs without consing...)
One of the bug I remember is a very obvious and easily-correctible
definition of if/2:
(<- (if ?test ?then) (if ?then ?else (fail)))
which obviously should be
(<- (if ?test ?then) (if ?test ?then (fail)))
But there are more fundamental issues with if and ISO compatibility.
ISO Prolog assigns rather weird semantics to if. If the ?pred clause
succeeds, it cuts all previous choice points within the rule containing
the if. This is quite different from cut itself, which cuts all
previous choice points within the entire functor call. (See the ISO
spec or the online manual for SWI Prolog for the ugly details.) I can
imagine the logic and convenience behind these semantics, but ugly
remains ugly even when convenient.
"Steven M. Haflich" <···@alum.mit.edu> writes:
> But there are more fundamental issues with if and ISO compatibility.
> ISO Prolog assigns rather weird semantics to if. If the ?pred clause
> succeeds, it cuts all previous choice points within the rule containing
> the if. This is quite different from cut itself, which cuts all
> previous choice points within the entire functor call. (See the ISO
> spec or the online manual for SWI Prolog for the ugly details.) I can
> imagine the logic and convenience behind these semantics, but ugly
> remains ugly even when convenient.
Given the context, I'd say "thinking" here, not "logic" :-)
--
/|_ .-----------------------.
,' .\ / | Free Mumia Abu-Jamal! |
,--' _,' | Abolish the racist |
/ / | death penalty! |
( -. | `-----------------------'
| ) |
(`-. '--.)
`. )----'
"Steven M. Haflich" <···@alum.mit.edu> writes:
> I'm the author of Allegro Prolog, which is based on the Norvig code but
> ``improved'' with various portable and nonportable optimizations. When
> I last compared benchmarks with Norvig's, AP ran about 1.5x10^3 times
> faster. I estimate about half (logarhythmically) of this improvement
> is due to improvements in raw computer performance, and the other half
> is due to code optimization.
Norvig's book was published in 1992; we're therefore eight folds of
Moore's law later, roughly. That would give a 2.5x10^2-fold
performance increase just from the hardware, at the simplest
calculation, but surely it's easy for you to actually measure the
effect of optimization -- just run the unmodified Norvig code on the
same hardware that you're measuring Allegro Prolog on.
> (Also, AP normally runs without consing...)
Presumably this is from declaring the success continuations and
unification data to have dynamic-extent? Have you run into cases
where stack space might become an issue?
> One of the bug I remember is a very obvious and easily-correctible
> definition of if/2:
>
> (<- (if ?test ?then) (if ?then ?else (fail)))
>
> which obviously should be
>
> (<- (if ?test ?then) (if ?test ?then (fail)))
Yes, of course. Actually, even before getting this far, various
things involving package discipline needed to be fixed in Norvig's
distribution: functions named CL:IGNORE, CL:SYMBOL and CL:DEBUG, for
instance.
> But there are more fundamental issues with if and ISO compatibility.
> ISO Prolog assigns rather weird semantics to if. If the ?pred clause
> succeeds, it cuts all previous choice points within the rule containing
> the if. This is quite different from cut itself, which cuts all
> previous choice points within the entire functor call. (See the ISO
> spec or the online manual for SWI Prolog for the ugly details.)
Indeed. This makes it impossible to implement the various control
contstructs with special choice point handling as ordinary predicates,
so ,/2, ;/2, ->/2 and ;/2 ->/2 (disjunction, conjunction, if-then and
if-then-else) as ordinary predicates. It's not terribly hard to
implement them properly, though (one needs to be a little careful
about call/1 as well).
Christophe
Christophe Rhodes wrote:
> Norvig's book was published in 1992; we're therefore eight folds of
> Moore's law later, roughly. That would give a 2.5x10^2-fold
> performance increase just from the hardware, at the simplest
> calculation, but surely it's easy for you to actually measure the
> effect of optimization -- just run the unmodified Norvig code on the
> same hardware that you're measuring Allegro Prolog on.
If Moore's Law is a doubling in number of transistors on a chip every
18 months, I get this result:
cl-user(8): (expt 2.0 (/ (- 2005 1992) 1.5))
406.37476
But this does not correlate exactly with processor speed. Roughly
doubling the number of transistors in a processor chip to take it
from 8 to 16 bits or from 16 to 32 or from 32 to 64 provides no
increase in speed, assuming the original word width was sufficient
such that no algorithmic efficiency is gained. Anyone know a reliable
estimate of processor _speed_ increase over time?
I've benchmarked Peter's original code, although some minor
modifications were necessary since that code is not _quite_ Common
Lisp code, making extraneous definitions of CL-package symbols as it
does. His original 1992 benchmark was about 740 LIPS. Running on
the fastest hardware currently at Franz I get 21.1 KLIPS on the zebra
puzzle, a factor of 28.5 speed increase. I get about 3.6e6 LIPS with
Allegro Prolog on the same hardware, about 170 times faster than the
PAIP code. It is about 1.5 times faster than SWI Prolog.
I won't pretend that these benchmarks are accurate or even
objectively fair, but I'll stand behind the rough magnitudes of
these comparisons.
> Presumably this is from declaring the success continuations and
> unification data to have dynamic-extent? Have you run into cases
> where stack space might become an issue?
Yes. Stack space isn't the direct problem, but dynamic-extent
data precludes tail call elimination.
So far as I have been able to determine, the standard for ISO Prolog
does not require tail call elimination, but most implementations do
provide it and many Prolog programs use tail recursion as a natural
idiom. (They resemble Scheme programmers in this regard, and both
differ from native CL programmers.) The dynamic-extent consing is
important enough as a speed optimization that I don't want to
abandon it, so I've been playing with a declaration that tells the
Prolog to Lisp translator not to do stack consing for a particular
functor/arity. I think this will be the best compromise to support
the occasional functor that needs to do deep tail recursion.
Standard Prolog functors such as member/2 that rely on tail
recursion are already internally coded using iteration.
Steven M. Haflich wrote:
> If Moore's Law is a doubling in ...
To respond to my own posting, I googled a lengthy and apparently
well-researched and well-written article on the history of Moore's
Law, its misunderstandings, and its extension to other dimensions
of computer performance. Quite an interesting read.
http://www.firstmonday.org/issues/issue7_11/tuomi/
The Lives and Death of Moore's Law by Ilkka Tuomi
John <········@mailinator.com> writes:
> While using PAIPROLOG in sbcl 0.9.4 I ran into something strange.
> [...]
> which is expected. However, if I add the rule:
>
> (<- (likes ?x ?x))
>
> then the same query gives me:
>
> ?Y = KIM
> ?X = SANDY;
>
> ?Y = SANDY
> ?X = SANDY;
>
> ?Y = SANDY
> ?X = SANDY;
>
> ?Y = SANDY
> ?X = KIM;
>
> ?Y = SANDY
> ?X = SANDY;
>
> ?Y = ?X4216
> ?X = ?X4216;
>
> No.
>
> which has sandy liking sandy a bit too much and a gensym liking itself.
>
> Is that what other prolog's would give for those rules or is something
> amiss?
I think so. It just says the truth: any x (let's name it X4216) likes x.
As for sandy, it is reaching the conclusions via different inferences.
Either use cuts to avoid generating duplicate conclusions,
or an unification phase to remove duplicate conclusions.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Until real software engineering is developed, the next best practice
is to develop with a dynamic system that has extreme late binding in
all aspects. The first system to really do this in an important way
is Lisp. -- Alan Kay