LISP source of Prolog systems
Antti J Ylikoski
code of some Prolog interpreters. I'm interested in the implementation
of Prolog (in LISP).
I in principle know Mats Carlsson's YAQ and Carlsson-Kenneth Kahn's
LM-PROLOG, but I have not found the (public domain) source code of those
in the 'Net. I have the files of the "Principles of Artificial
Intelligence Programming" by Norvig in my hands, that is an excellent
book, and it contains both a Prolog system and a good discussion of
knowledge representation.
regards;; Antti J Ylikoski
Helsinki, Finland, the E.U.
jb
wrote:
The Implementation of Prolog (Princeton Series in Computer Science)
[Gebundene Ausgabe]
Patrice Boizumault
Patrice Boizumault (Autor)
› Besuchen Sie die Patrice Boizumault Amazon Seite
Finden Sie alle Bücher, Informationen zum Autor
und mehr.
Suchergebnissen für diesen Autor
Sind Sie ein Autor? Erfahren Sie mehr über Author Central
(Autor), Ara M. Djamboulian (Autor), Jamal Fattouh (Autor)
From the amazon review:
If, for some reason :-), you have to write a Prolog interpreter
in a normal imperative language (C, C++, Pascal, VB), stay away from
this book: the author adopted LISP as the implementation language!
ftp.cs.cmu.edu:/user/ai/lang/prolog/impl/prolog/boiz_pl/
Mats Carlsson
wrote:
> Could somebody inform me where I gould get the public domain LISP source
> code of some Prolog interpreters. I'm interested in the implementation
> of Prolog (in LISP).
>
> I in principle know Mats Carlsson's YAQ and Carlsson-Kenneth Kahn's
> LM-PROLOG, but I have not found the (public domain) source code of those
> in the 'Net.
LM-Prolog is indeed free and Google gives several hits with download
links and everything. The links are slightly dated, but here is one
that works:
http://www.sics.se/~matsc/lm-prolog.tar.gz
--Mats
Chip Eastham
The notices for LM-Prolog do indicate it is "free"
to copy and distribute, though this is perhaps not
"public domain" as the OP asks. Also the notices
state that as a ZetaLISP implementation, LM-Prolog
makes significant use of extensions not available
in Common LISP, and concludes it would be difficult
to port to Common LISP.
Another Prolog-in-LISP that might be worth a look:
http://www.cs.bham.ac.uk/research/projects/poplog/freepoplog.html
Although targeted to Linux, directions are given
there for getting it to run under Windows. It
appears that Poplog is being actively maintained.
regards, chip
Jan Burse
Lm-Prolog looks like a fine original thing. But what
about the papers/technical reports surounding it,
I didn't find them somewhere to download, i.e. some
preprints or some such.
Bye
Mats Carlsson
You've got to be kidding. We did that work nearly 30 years ago. LaTeX,
Word etc. were not invented then, or just barely. I don't have the
files any more.
--Mats
Jan Burse
What happened to:
A Prolog interpreter, YAQ <Carlsson> has been implemented to run
under Lispf3. YAQ uses a lispish S-notation for Prolog expressions.
?
Bye
Jan Burse
>
> What happened to:
>
> A Prolog interpreter, YAQ <Carlsson> has been implemented to run
> under Lispf3. YAQ uses a lispish S-notation for Prolog expressions.
>
> ?
I found a mention of it here:
http://ftp.csd.uu.se/pub/papers/reports/
But the links on it don't work.
k...@kymhorsell.com
[...]
> It's long gone, I don't even have the tapes any more.
> Not that I think it would do you much good. I remember clocking it at
> 4 lips.
[...]
It's ambiguous in the (historical) context whether you mean lips or klips. :)
--
R Kym Horsell <k...@kymhorsell.com>
If your ideas are any good you'll have to ram them down people's throats.
-- Howard Aiken
Antti J Ylikoski
> Not that I think it would do you much good. I remember clocking it at
> 4 lips.
>
> have it printed on the back side of his business card:
>
> @incollection{DBLP:books/eh/campbell84/Nilsson84,
> author = {Martin Nilsson},
> title = {The World's Shortest Prolog Interpreter?},
> booktitle = {Implementations of Prolog},
> year = {1984},
> pages = {87-92},
> bibsource = {DBLP, http://dblp.uni-trier.de}
> }
>
> A piece of trivia: I was the main maintainer of LISP F3, later F4, for
> some time.
> We would send half-inch tapes to anyone who would sign our Non
> Proliferation Treaty.
> --Mats
I converted the YAQ to run under VAX/BSD VMUNIX Franz Lisp, (compiled of
course) and actually got it to run at about 200 LIPS.
This necessitated some extensive LISP surgery such as declaring lots of
functions inline (or whatever was the corresponding incantation in Franz
Lisp.) I still recall that I discovered that the functions prove and
unify could not be declared inline..... I thought that it would be nice
to have a short look at that old work. But only a short one.... SICSTus
Prolog is a zillion times more interesting, and the academic license is
not very expensive.
kind regards, A. J. Y.
Mats Carlsson
> Mats Carlsson <matsc560...@gmail.com> wrote:
>
> [...]> It's long gone, I don't even have the tapes any more.
> > Not that I think it would do you much good. I remember clocking it at
> > 4 lips.
>
> [...]
>
> It's ambiguous in the (historical) context whether you mean lips or klips. :)
I do mean 4 lips, not 4 klips. --Mats
PS. LISP F3/F4 were LISP interpreters written in Fortran 4.
k...@kymhorsell.com
> On Oct 25, 8:25?pm, k...@kymhorsell.com wrote:
>> Mats Carlsson <matsc560...@gmail.com> wrote:
>> [...]> It's long gone, I don't even have the tapes any more.
>> > 4 lips.
>> [...]
>> It's ambiguous in the (historical) context whether you mean lips or klips. :)
> I do mean 4 lips, not 4 klips. --Mats
Thanks for the clarification. :)
> PS. LISP F3/F4 were LISP interpreters written in Fortran 4.
Well I see we have a FORTRAN-basher in our midst! :P
Not a complete explanation. I guess the LISP implementation itself
must have not cut enough corners. I've seen plenty of things written
in fortran -- not the least FORTRAN compilers -- that had
a reasonable performance against similar hand-written asm
(yes, young readers, people used to write a lot of things in assembler
in past centuries).
4 LIPS is truly a record as far as I can tell. Congrats. :)
Ulrich Neumerkel
>You may have better luck with Martin Nilsson's interpreter. He used to
>have it printed on the back side of his business card:
>
>@incollection{DBLP:books/eh/campbell84/Nilsson84,
> title =3D {The World's Shortest Prolog Interpreter?},
> booktitle =3D {Implementations of Prolog},
> year =3D {1984},
> pages =3D {87-92},
> bibsource =3D {DBLP, http://dblp.uni-trier.de}
>}
Doesn't this use one of those unification algorithms where Peter Norvig's
observation applies?
Correcting a widespread error in unification algorithms.
Software Practice and Experience, 21, 2, 231-233, February, 1991.
Jan Burse
What a mess, hopefully lisp soon dies out.
LoL, the error is based on the omission of a performance
killer. Namely **before** you unify x and y, you have to
dereference them.
The solution presented by norvig doesn't look so good
to me. Its structure is such that equal is called twice,
once in unify and once in unify-variable.
Also it is quite convoluted to do the dereferencing
only inside unify-variable, and for both arguments.
I would simply do it before the cond in unify.
Finally in a practical setting a unification algorithm
should not be fully recursive, but instead it should
be implemented in a loop, so that you do not recurse for
the last argument of a compound.
Maybe some lisps will be able to turn the given unify
into a loop, since it is tail recursive. But if not
you run into the danger of stack overflow, already for
simple examples (*).
Bye
(*)
Try something like
?- factorial(s(s(...n...)),X), factorial(s(s(...n...)),Y), X=Y.
Jan Burse
Maybe the problem is that whenever something goes into print,
it goes wrong. For example the algorithm given by
Ait-Kaci, Hassan, "Warren's Abstract Machine:
A Tutorial Reconstruction", MIT Press, Cambridge, MA. 1991.
Is not very optimal on the following grounds:
- To much stack pushing
Instead of pushing all arguments of a compound
you can push the compound and an index.
- Wrong order of stack pushing
It is better to push in reverse order, otherwise
implicit loop is on first argument, which is bad
for long lists represented by (.)/2 functor.
But in the bind(d1,d2), you can put some smarts, like
variable ordering.
Best Regards
k...@kymhorsell.com
[...]
> Doesn't this use one of those unification algorithms where Peter Norvig's
> observation applies?
Oh, wow! SPE at something like $200 per issue was dropped in 80s cost-cutting
bingees by any college library or CS dept I was near, so had not heard of
this one.
k...@kymhorsell.com
[...]
> LoL, the error is based on the omission of a performance
> killer. Namely **before** you unify x and y, you have to
> dereference them.
I can be a bit more subtle than than, depending on representation.
If an "unbound variable" is represented by a special ptr
and a pointer-to-bound-variable (sometimes also used to point
to general terms on the heap) is something else, at some unexpected
point the code probably does only a literal equal, forgets the ptr
tags, and presumes the invariant "everything is always derefed" is good.
In a microcoded paralell unify engine (sitting in the bus of a 6 MHz AT)
I was working on in the mid 80s (aborted CS PhD#2 :) I tried to maintain
such an invariant. But my exhaustive testset kept throwing up failures.
So it was a matter of hacking derefs on the args at the start of the
unify microcode. Fixed the problems, but then turned out to chew up
10-20% of the clock cycles. Well, the h/w was pipelined after all
so I added a little delta-t to the latency time in the documentation. :)
Antti J Ylikoski
I have an Acer laptop with a 2-core 64-bit CPU running at 2.2 GHz, 4 GB
of RAM and 500 GB of hard disk space.
Earlier, I had installed a Sun VirtualBox and installed a Linux system
to run under the VirtualBox. This is a nice way to run Linux software
such as GNU Smalltalk, SBCL or Poplog if one doesn't want to dedicate
one's PC solely to Linux.
So I downloaded and installed the free Poplog. It looks like a very
strong AI tool. I have not yet programmed with the Poplog system, I
have only been reading the documentation. The UK computer science would
deserve to be better known here at the roof of Battlestar Tellus.....
Unfortunately, the Sun VirtualBox crashed with the error message
LOADED_TOO_MUCH .... I lost the entire Poplog system I had downloaded.
regards, Antti J Ylikoski
Helsinki, Finland, the EU
Chip Eastham
Hi, Antti:
Ouch! May I ask what version of VirtualBox you
were using, and what OS hosted the VirtualBox?
It seems to be still getting support from Sun/
Oracle, in contrast to other open source stuff
like Java and OpenSolaris.
You have a fair amount of disk space on that
laptop. I've not jumped into virtualization,
taking instead the low road of dual booting.
Is it safe? I appreciate your reporting.
regards, chip
Antti J Ylikoski
Hello Chip!!!
I'm using the newest from the 'Net downloadable version of the Oracle VM
VirtualBox. It tells me that it is Version 3.2.10 r66523.
The host operating system was Microsoft Windows 7.
Today I have been fighting for three hours in order to get the hard disk
of an Acer Ferrari 1100 laptop configured for two Linux partitions --
and failed. Finally I installed Linux so that I let the installment
process format and use the entire hard disk with only one big partition.
But my bleak experience with disk partitioning is not so readily
generalizable. I have been using partitioned Microsoft Windows (TM)
PC:s for years with no problems whatsoever, but they were divided into
partitions at the factory together with the factory installed Windows
(TM) operating systems.
BTW I think the Microsoft Windowses (TM) are really good software
systems. I have been using them regularly from the times of the MS-DOS
and the Windows 3.11, and never experienced any problems -- except some
three incidents when the application programs were bugged and actually
made the Windows partially crash. (Without totally becoming confused.)
kind regards, Antti J Ylikoski
Helsinki, Finland, the E.U.
Antti J Ylikoski
Here I answer myself .... (Talking to myself? Isn't that considered
odd? :-) )
I had an unused Acer Ferrari 1100 laptop with a 2-core AMD Turion64
2.3GHz processor, 4GB of RAM and 250GB of hard disk. I installed the
newest Ubuntu Linux into that machine -- and downloaded and installed
the Poplog system.
I did not install the Poplog under the andLinux, but followed the
instructions in the URL:
http://www.cs.bham.ac.uk/research/poplog/latest-poplog/
for installing the Poplog under a Linux system.
There is on error in those www instructions -- it says that there are
script files there for downloading and installing the whole system --
but in addition to running those scripts it is necessary to install four
packages by hand, namely:
sudo apt-get install build-essential
sudo apt-get install csh
sudo apt-get install libxext-dev
sudo apt-get install linxt-dev
and after installing those 4 ones, runnning the shell script file
./INSTALL_BHAM_POPLOG or something like that will bring the entire
system up and working.
The Poplog is a highly interesting combination of a Common LISP system,
a Prolog system and a high-level symbolic AI language called Pop11.
* Is that LISP a full scale CLtL2 Common LISP? (I only checked, did not
extensively test.)
* Is the Prolog a standard Prolog? (I only had a look at it.)
* How about some good books on the Pop11?
kind regards, Mr Antti J Ylikoski
Helsinki, Finland, the E.U.
DjaméSeddah
<antti.y...@elisanet.fi> said:
Hi,
I don't know if the question still stands but I remember finding a
prolog interpreter written in the xlisp dialect in the XLisp src
distribution that was available for Atari ST and Windows PC circa
1997-1998. As far as i know that was public domain stuff.
Good luck finding that (maybe on the old atari michigan archive)
and actually I just found it there :)
it's the file PROLOG.LSP in
http://www.umich.edu/~archive/atari/Languages/xlisplsp.arc
Djam�
ps: never actually used it below father X something, 15 years ago...
here the code for those without any arc unarchiver.
;; The following is a tiny Prolog interpreter in MacLisp
;; written by Ken Kahn and modified for XLISP by David Betz.
;; It was inspired by other tiny Lisp-based Prologs of
;; Par Emanuelson and Martin Nilsson.
;; There are no side-effects anywhere in the implementation.
;; Though it is VERY slow of course.
(defun prolog (database &aux goal)
(do () ((not (progn (princ "Query?") (setq goal (read)))))
(prove (list (rename-variables goal '(0)))
'((bottom-of-environment))
database
1)))
;; prove - proves the conjunction of the list-of-goals
;; in the current environment
(defun prove (list-of-goals environment database level)
(cond ((null list-of-goals) ;; succeeded since there are no goals
(print-bindings environment environment)
(not (y-or-n-p "More?")))
(t (try-each database database
(cdr list-of-goals) (car list-of-goals)
environment level))))
(defun try-each (database-left database goals-left goal environment level
&aux assertion new-enviroment)
(cond ((null database-left) nil) ;; fail since nothing left in database
(t (setq assertion
(rename-variables (car database-left)
(list level)))
(setq new-environment
(unify goal (car assertion) environment))
(cond ((null new-environment) ;; failed to unify
(try-each (cdr database-left) database
goals-left goal
environment level))
((prove (append (cdr assertion) goals-left)
new-environment
database
(+ 1 level)))
(t (try-each (cdr database-left) database
goals-left goal
environment level))))))
(defun unify (x y environment &aux new-environment)
(setq x (value x environment))
(setq y (value y environment))
(cond ((variable-p x) (cons (list x y) environment))
((variable-p y) (cons (list y x) environment))
((or (atom x) (atom y))
(cond ((equal x y) environment)
(t nil)))
(t (setq new-environment (unify (car x) (car y) environment))
(cond (new-environment (unify (cdr x) (cdr y) new-environment))
(t nil)))))
(defun value (x environment &aux binding)
(cond ((variable-p x)
(setq binding (assoc x environment :test #'equal))
(cond ((null binding) x)
(t (value (cadr binding) environment))))
(t x)))
(defun variable-p (x)
(and x (listp x) (eq (car x) '?)))
(defun rename-variables (term list-of-level)
(cond ((variable-p term) (append term list-of-level))
((atom term) term)
(t (cons (rename-variables (car term) list-of-level)
(rename-variables (cdr term) list-of-level)))))
(defun print-bindings (environment-left environment)
(cond ((cdr environment-left)
(cond ((= 0 (nth 2 (caar environment-left)))
(prin1 (cadr (caar environment-left)))
(princ " = ")
(print (value (caar environment-left) environment))))
(print-bindings (cdr environment-left) environment))))
;; a sample database:
(setq db '(((father madelyn ernest))
((mother madelyn virginia))
((father david arnold))
((mother david pauline))
((father rachel david))
((mother rachel madelyn))
((grandparent (? grandparent) (? grandchild))
(parent (? grandparent) (? parent))
(parent (? parent) (? grandchild)))
((parent (? parent) (? child))
(mother (? parent) (? child)))
((parent (? parent) (? child))
(father (? parent) (? child)))))
;; the following are utilities
(defun y-or-n-p (prompt)
(princ prompt)
(eq (read) 'y))
;; start things going
(prolog db)
;;;EOF
Waldek Hebisch
>
> The Poplog is a highly interesting combination of a Common LISP system,
> a Prolog system and a high-level symbolic AI language called Pop11.
>
> * Is that LISP a full scale CLtL2 Common LISP? (I only checked, did not
> extensively test.)
Yes. Note that now people want ANSI Lisp and compared to ANSI CLtL2
misses a few functions (notably READ-SEQUENCE).
> * Is the Prolog a standard Prolog? (I only had a look at it.)
> * How about some good books on the Pop11?
>
There is Pop11 primer by Aaron Sloman (included in the distribution, so
you should already have it). I have adapted ``How to think like a
computer scientist'' by Allen B. Downey to Pop11:
http://www.math.uni.wroc.pl/~p-wyk4/metody2007/thinkCS/thinkCS_1-19.pdf
http://www.math.uni.wroc.pl/~p-wyk4/metody2007/thinkCS/thinkCSpop11_0.7.1-19.tar.gz
For viewing you need only .pdf, .tar.gz contains Latex sources. Rather
elementary, but if you are experienced in other languages it may
be still of some use to see how to write things in Pop11.
There is Gazdar and Mellish book about NLP programming, it has versions
for Lisp, Prolog and Pop11.
--
Waldek Hebisch
heb...@math.uni.wroc.pl