Looking for a small CL Prolog
Erik Naggum
| I'm looking for a Common Lisp Prolog-like package with the following
| features:
|
| 1. The cut primitive
| 2. Fully interpreted so I can make rapid dynamic changes to the database
| 3. At least a bit flexible and extensible
|
| I don't care about the syntax. Any help appreciated, because otherwise
| I'll have to write it myself. If anybody has any ideas, please could
| they let me know either here or directly at S.N.K...@open.ac.uk.
I haven't gotten as far in the book as to tell whether it is what you want,
but Peter Norvig's {Paradigms of Artificial Intelligence Programming, Case
Studies in Common Lisp} includes a small Prolog engine as part of its vast
array of code and examples. I generally recommend this book for both style
and contents.
(hi from dm863i.)
#<Erik>
--
sufficiently advanced political correctness is indistinguishable from sarcasm
Stuart Watt
1. The cut primitive
2. Fully interpreted so I can make rapid dynamic changes to the database
3. At least a bit flexible and extensible
I don't care about the syntax. Any help appreciated, because otherwise
I'll have to write it myself. If anybody has any ideas, please could they
let me know either here or directly at S.N.K...@open.ac.uk.
Regards, Stuart
--
Stuart Watt; Human Cognition Research Laboratory, Open University,
Walton Hall, Milton Keynes, MK7 6AA, UK.
Tel: +44 1908 654513; Fax: +44 1908 653169.
WWW: http://kmi.open.ac.uk/~stuart/stuart.html
Bruno Haible
> I'm looking for a Common Lisp Prolog-like package with the following features:
>
> 1. The cut primitive
> 2. Fully interpreted so I can make rapid dynamic changes to the database
> 3. At least a bit flexible and extensible
>
> I don't care about the syntax.
Take a look at the CMU AI repository, directory
user/ai/lang/prolog/impl/prolog/.
If you want something really small, you may take my xp-prolog, in
ma2s2.mathematik.uni-karlsruhe.de:/pub/lisp/clisp/packages/xp-prolog.tar.z .
> Any help appreciated, because otherwise I'll have to write it myself.
It is not that difficult. Xp-prolog was written in two days. Could be a
homework in an AI class.
Bruno Haible
hai...@ma2s2.mathematik.uni-karlsruhe.de
Andrew G Bachmann
Erik Naggum <er...@naggum.no> wrote:
>[Stuart Watt]
>| I'm looking for a Common Lisp Prolog-like package with the following
>| features:
>|
>| 1. The cut primitive
>| 2. Fully interpreted so I can make rapid dynamic changes to the database
>| 3. At least a bit flexible and extensible
>|
>but Peter Norvig's {Paradigms of Artificial Intelligence Programming, Case
>Studies in Common Lisp} includes a small Prolog engine as part of its vast
>array of code and examples. I generally recommend this book for both style
>and contents.
>
I have an improvement which can significantly make your life easier
if you plan to do any sort of major work with norvig's implementation
of prolog. Essentially, these changes will remove unnecessary frames
from the stack. Here's a sample predicate (not intended to be useful,
good prolog, etc.):
(<- (p ?arg1 ?arg2) (= ?arg2 a) ! (q ?arg1))
(<- (p ?arg1 ?arg2) (= ?arg2 b) ! (r ?arg2))
Here's the norvig version:
(defun p/2 (?arg1 ?arg2 cont)
(let ((old-trail (fill-pointer *trail*)))
(if (unify! ?arg2 'a)
(progn (q/1 ?arg1 cont)
(return-from p/2 nil)))
(undo-bindings! old-trail)
(if (unify! ?arg2 'b)
(r/1 ?arg1
#'(lambda nil
(progn (s/1 ?arg1 cont) (return-from p/2 nil)))))))
Here's my version:
(defun p/2 (?arg1 ?arg2 cont)
(let ((old-trail (fill-pointer *trail*)))
(when
(catch 'cut-reached
(if (unify! ?arg2 'a)
(throw 'cut-reached t)))
(q/1 ?arg1 cont)
(return-from p/2 nil))
(undo-bindings! old-trail)
(when
(catch 'cut-reached
(if (unify! ?arg2 'b)
(r/1 ?arg1
#'(lambda nil (throw 'cut-reached t)))))
(s/1 ?arg1 cont)
(return-from p/2 nil))))
The necessary changes are as follows:
(def-prolog-compiler-macro fail (goal body cont bindings in-cut-form)
(declare (ignore goal body cont bindings in-cut-form))
nil)
(def-prolog-compiler-macro true (goal body cont bindings in-cut-form)
(declare (ignore goal))
(multiple-value-bind (body cut-form)
(compile-body body cont bindings in-cut-form)
(values body cut-form)))
(def-prolog-compiler-macro = (goal body cont bindings in-cut-form)
"Compile a goal which is a call to =."
(let ((args (args goal)))
(if (/= (length args) 2)
:pass ;; decline to handle this goal
(multiple-value-bind (code1 bindings1)
(compile-unify (first args) (second args) bindings)
(multiple-value-bind (body cut-form)
(compile-body body cont bindings1 in-cut-form)
(values
(compile-if code1 body)
cut-form))))))
;;Then the most work here:
(defun compile-body (body cont bindings &optional (in-cut-form nil))
"Compile the body of a clause."
(cond
((null body)
(if in-cut-form
(values `(throw 'cut-reached t) `(funcall ,cont))
`(funcall ,cont)))
((eq (first body) '!) ;***
(values `(throw 'cut-reached t)
(compile-body (rest body) cont bindings nil)))
((and (not in-cut-form) (member '! body))
(multiple-value-bind (body cut-form)
(compile-body body cont bindings t)
`(when (catch 'cut-reached
,body)
,cut-form
(return-from ,*predicate* nil))))
(t (let* ((goal (first body))
(macro (prolog-compiler-macro (predicate goal))))
(multiple-value-bind (macro-val cut-form)
(if macro
(funcall macro goal (rest body) cont bindings in-cut-form))
(if (and macro (not (eq macro-val :pass)))
(values macro-val cut-form)
(multiple-value-bind (bound-body cut-form)
(when (not (null (rest body)))
(compile-body (rest body) cont
(bind-new-variables bindings goal) in-cut-form))
(values
`(,(make-predicate (predicate goal)
(relation-arity goal))
,@(mapcar #'(lambda (arg)
(compile-arg arg bindings))
(args goal))
,(if (null (rest body))
cont
`#'(lambda ()
,bound-body)))
cut-form))))))))
This may not be the best way to do this, and I have my own dispositions
as to length of procedures, etc, but it works quite well, and kudos to
norvig for extensionality.
other hints:
Use the deref-copy from the book that only traverses the tree.
If you need assert, retract, email me, because I have done these.
Also, I have an implementation of the (extremely kooky) prolog <
relation, sort, and several others. If you do a lot of retraction,
_don't_ have your lisp compiler compile the run-time rules, because
the speed will be slower this way.
Andrew Bachmann - Northwestern University - Institute for Learning Sciences
<a href="http://web.eecs.nwu.edu/~andy/>My Home Page</a>
Nonstandard disclaimer: Don't let anyone else take credit for what I say;
My opinions and my ideas are my own, thank you.
Stuart Watt
hai...@ma2s2.mathematik.uni-karlsruhe.de (Bruno Haible) wrote:
> Take a look at the CMU AI repository, directory
> user/ai/lang/prolog/impl/prolog/.
>
> If you want something really small, you may take my xp-prolog, in
> ma2s2.mathematik.uni-karlsruhe.de:/pub/lisp/clisp/packages/xp-prolog.tar.z .
I had a look in the CMU AI repository , but I didn't find quite what I was
looking for. xp-prolog is exactly what I was looking for, and I wish I'd
known about it earlier. In the end, I spent the two days, so I've got
something that is very like xp-prolog, but a bit bigger and a lot slower.
I might well switch to xp-prolog if time permits.
In the longer term, always assuming I'm still employed in 3 months time, I
plan to use our ultimate Prolog debugging expertise to build a small
Windows-based Prolog environment for novices. So, I'm going to keep tags
on Common Lisp Prolog interpreters in the meantime.
In article <19950505T1...@naggum.no>, Erik Naggum <er...@naggum.no>
wrote:
> I haven't gotten as far in the book as to tell whether it is what you want,
> but Peter Norvig's {Paradigms of Artificial Intelligence Programming, Case
> Studies in Common Lisp} includes a small Prolog engine as part of its vast
> array of code and examples. I generally recommend this book for both style
> and contents.
Hi again Erik. Yes, I know Peter Norvig's book, and I like it lots too.
But he adds the cut in the compiler, which makes it comprehensible. The
cut actually makes sense when you generate Lisp code from the clauses! I
wanted to dynamically compose databases at run time (don't ask me why) so
the compiler option was out as I'd need to recompile *everything all the
time*. If you go the interpreter option you need catch and throw and all
those nasties, but you can do strange things like this.
Thanks everybody for the help and responses on this. I'm pleased how many
small Prologs there are, and how many Lisp people supply them.