Copy Link
Add to Bookmark
Report
AIList Digest Volume 1 Issue 047
AIList Digest Wednesday, 24 Aug 1983 Volume 1 : Issue 47
Today's Topics:
Request - AAAI-83 Registration,
Logic Programming - PARLOG & PROLOG & LISP Prologs
----------------------------------------------------------------------
Date: 22 Aug 83 16:50:55-PDT (Mon)
From: harpo!eagle!allegra!jdd @ Ucb-Vax
Subject: AAAI-83 Registration
Article-I.D.: allegra.1777
Help! I put off registering for AAAI-83 until too late, and now I
hear that it's overbooked! (I heard 7000 would-be registrants and
1500 places, or some such.) If you're registered but find you can't
attend, please let me know, or if you have any other suggestions, feel
free.
Cheers, John ("Something Wrong With My Planning Heuristics")
DeTreville Bell Labs, Murray Hill
------------------------------
Date: 23 Aug 83 1337 PDT
From: Diana Hall <DFH@SU-AI>
Subject: PARLOG
[Reprinted from the SCORE BBoard.]
Parlog Seminar
Keith Clark will give a seminar on Parlog Thursday, Sept. 1 at 3 p.m
in Room 252 MJH.
PARLOG: A PARALLEL LOGIC PROGRAMMING LANGUAGE
Keith L. Clark
ABSTRACT
PARLOG is a logic programming language in the sense that
nearly every definition and query can be read as a sentence of
predicate logic. It differs from PROLOG in incorporating parallel
modes of evaluation. For reasons of efficient implementation, it
distinguishes and separates and-parallel and or-parallel evaluation.
PARLOG relations are divided into two types: and-relations
and or-relations. A sequence of and-relation calls can be evaluated
in parallel with shared variables acting as communication channels.
Only one solution to each call is computed.
A sequence of or-relation calls is evaluated sequentially but
all the solutions are found by a parallel exploration of the different
evaluation paths. A set constructor provides the main interface
between and-relations and or-relations. This wraps up all the
solutions to a sequence of or-relation calls in a list. The solution
list can be concurrently consumed by an and-relation call.
The and-parallel definitions of relations that will only be
used in a single functional mode can be given using conditional
equations. This gives PARLOG the syntactic convenience of functional
expressions when non-determinism is not required. Functions can be
invoked eagerly or lazily; the eager evaluation of nested function
calls corresponds to and-parallel evaluation of conjoined relation
calls.
This paper is a tutorial introduction and semi-formal
definition of PARLOG. It assumes familiarity with the general
concepts of logic programming.
------------------------------
Date: Thu 18 Aug 83 20:00:36-PDT
From: PEREIRA@SRI-AI.ARPA
Subject: There are Prologs and Prologs ...
In the July issue of SIGART an article by Richard Wallace describes
PiL, yet another Prolog in Lisp. The author claims that his
interpreter shows that "it is easy to extend Lisp to do what Prolog
does."
It is a useful pedagogical exercise for Lisp users interested in logic
programming to look at a simple, clean implementation of a subset of
Prolog in Lisp. A particularly illuminating implementation and
discussion is given in "Structure and Implementation of Computer
Programs", a set of MIT lecture notes by Abelson and Sussman.
However, such simple interpreters (even the Abelson and Sussman one
which is far better than PiL) are not a sufficient basis for the claim
that "it is easy extend Lisp to do what Prolog does." What Prolog
"does" is not just to make certain deductions in a certain order, but
also MAKE THEM VERY FAST. Unfortunately, ALL Prologs in Lisp I know of
fail in this crucial aspect (by factors between 30 and 1000).
Why is speed such a crucial aspect of Prolog (or of Lisp, for that
matter)? First, because the development of complex experimental
programs requires MANY, MANY experiments, which just could not be done
if the systems were, say, 100 times slower than they are. Second,
because a Prolog (Lisp) system needs to be written mostly in Prolog
(Lisp) to support the extensibility that is a central aspect of modern
interactive computing environments.
The following paraphrase of Wallace's claim shows its absurdity: "[LiA
(Lisp in APL) shows] that is easy to extend APL to do what Lisp does."
Really? All of what Maclisp does? All of what ZetaLisp does?
Lisp and Prolog are different if related languages. Both have their
supporters. Both have strengths and (serious) weaknesses. Both can be
implemented with comparable efficiency. It is educational to to look
both at (sub)Prologs in Lisp and (sub)Lisps in Prolog. Let's not claim
discoveries of philosopher's stones.
Fernando Pereira
AI Center
SRI International
------------------------------
Date: Wed, 17 Aug 1983 10:20 EDT
From: Ken%MIT-OZ@MIT-MC
Subject: FOOLOG Prolog
[Reprinted from the PROLOG Digest.]
Here is a small Prolog ( FOOLOG = First Order Oriented LOGic )
written in Maclisp. It includes the evaluable predicates CALL,
CUT, and BAGOF. I will probably permanently damage my reputation
as a MacLisp programmer by showing it, but as an attempt to cut
the hedge, I can say that I wanted to see how small one could
make a Prolog while maintaining efficiency ( approx 2 pages; 75%
of the speed of the Dec-10 Prolog interpreter ). It is actually
possible to squeeze Prolog into 16 lines. If you are interested
in that one and in FOOLOG, I have a ( very ) brief report describing
them that I can send you. Also, I'm glad to answer any questions
about FOOLOG. For me, the best is if you send messages by Snail Mail,
since I do not have a net connection. If that is uncomfortable, you
can also send messages via Ken Kahn, who forwards them.
My address is:
Martin Nilsson
UPMAIL
Computing Science Department
Box 2059
S-750 02 UPPSALA, Sweden
---------- Here is a FOOLOG sample run:
(load 'foolog) ; Lower case is user type-in
; Loading DEFMAX 9844442.
(progn (defpred member ; Definition of MEMBER predicate
((member ?x (?x . ?l)))
((member ?x (?y . ?l)) (member ?x ?l)))
(defpred cannot-prove ; and CANNOT-PROVE predicate
((cannot-prove ?goal) (call ?goal) (cut) (nil))
((cannot-prove ?goal)))
'ok)
OK
(prove (member ?elem (1 2 3)) ; Find elements of the list
(writeln (?elem is an element))))
(1. IS AN ELEMENT)
MORE? t ; Find the next solution
(2. IS AN ELEMENT)
MORE? nil ; This is enough
(TOP)
(prove (cannot-prove (= 1 2)) ; The two cannot-prove cases
MORE? t
NIL
(prove (cannot-prove (= 1 1))
NIL
---------- And here is the source code:
; FOOLOG Interpreter (c) Martin Nilsson UPMAIL 1983-06-12
(declare (special *inf* *e* *v* *topfun* *n* *fh* *forward*)
(special *bagof-env* *bagof-list*))
(defmacro defknas (fun args &rest body)
`(defun ,fun macro (l)
(cons 'progn (sublis (mapcar 'cons ',args (cdr l))
',body))))
; ---------- Interpreter
(setq *e* nil *fh* nil *n* nil *inf* 0
*forward* (munkam (logior 16. (logand (maknum 0) -16.))))
(defknas imm (m x) (cxr x m))
(defknas setimm (m x v) (rplacx x m v))
(defknas makrecord (n)
(loop with r = (makhunk n) and c for i from 1 to (- n 2) do
(setq c (cons nil nil))
(setimm r i (rplacd c c)) finally (return r)))
(defknas transfer (x y)
(setq x (prog1 (imm x 0) (setq y (setimm x 0 y)))))
(defknas allocate nil
(cond (*fh* (transfer *fh* *n*) (setimm *n* 7 nil))
((setq *n* (setimm (makrecord 8) 0 *n*)))))
(defknas deallocate (on)
(loop until (eq *n* on) do (transfer *n* *fh*)))
(defknas reset (e n) (unbind e) (deallocate n) nil)
(defknas ult (m x)
(cond ((or (atom x) (null (eq (car x) '/?))) x)
((< (cadr x) 7)
(desetq (m . x) (final (imm m (cadr x)))) x)
((loop initially (setq x (cadr x)) until (< x 7) do
(setq x (- x 6)
m (or (imm m 7)
(imm (setimm m 7 (allocate)) 7)))
finally (desetq (m . x) (final (imm m x)))
(return x)))))
(defknas unbind (oe)
(loop with x until (eq *e* oe) do
(setq x (car *e*)) (rplaca x nil) (rplacd x x) (pop *e*)))
(defknas bind (x y n)
(cond (n (push x *e*) (rplacd x (cons n y)))
(t (push x *e*) (rplacd x y) (rplaca x *forward*))))
(lap-a-list '((lap final subr) (hrrzi 1 @ 0 (1)) (popj p) nil))
; (defknas final (x) (cdr (memq nil x))) ; equivalent
(defknas catch-cut (v e)
(and (null (and (eq (car v) 'cut) (eq (cdr v) e))) v)))
(defun prove fexpr (gs)
(reset nil nil)
(seek (list (allocate)) (list (car (convq gs nil)))))
(defun seek (e c)
(loop while (and c (null (car c))) do (pop e) (pop c))
(cond ((null c) (funcall *topfun*))
((atom (car c)) (funcall (car c) e (cdr c)))
((loop with rest = (cons (cdar c) (cdr c)) and
oe = *e* and on = *n* and e1 = (allocate)
for a in (symeval (caaar c)) do
(and (unify e1 (cdar a) (car e) (cdaar c))
(setq inf* (1+ *inf*)
*v* (seek (cons e1 e)
(cons (cdr a) rest)))
(return (catch-cut *v* e1)))
(unbind oe)
finally (deallocate on)))))
(defun unify (m x n y)
(loop do
(cond ((and (eq (ult m x) (ult n y)) (eq m n)) (return t))
((null m) (return (bind x y n)))
((null n) (return (bind y x m)))
((or (atom x) (atom y)) (return (equal x y)))
((null (unify m (pop x) n (pop y))) (return nil)))))
; ---------- Evaluable Predicates
(defun inst (m x)
(cond ((let ((y x))
(or (atom (ult m x)) (and (null m) (setq x y)))) x)
((cons (inst m (car x)) (inst m (cdr x))))))
(defun lisp (e c)
(let ((n (pop e)) (oe *e*) (on *n*))
(or (and (unify n '(? 2) (allocate) (eval (inst n '(? 1))))
(seek e c))
(reset oe on))))
(defun cut (e c)
(let ((on (cadr e))) (or (seek (cdr e) c) (cons 'cut on))))
(defun call (e c)
(let ((m (car e)) (x '(? 1)))
(seek e (cons (list (cons (ult m x) '(? 2))) c))))
(defun bagof-topfun nil
(push (inst *bagof-env* '(? 1)) *bagof-list*) nil)
(defun bagof (e c)
(let* ((oe *e*) (on *n*) (*bagof-list* nil)
(*bagof-env* (car e)))
(let ((*topfun* 'bagof-topfun)) (seek e '(((call (? 2))))))
(or (and (unify (pop e) '(? 3) (allocate) *bagof-list*)
(seek e c))
(reset oe on))))
; ---------- Utilities
(defun timer fexpr (x)
(let* ((*rset nil) (*inf* 0) (x (list (car (convq x nil))))
(t1 (prog2 (gc) (runtime) (reset nil nil)
(seek (list (allocate)) x)))
(t1 (- (runtime) t1)))
(list (// (* *inf* 1000000.) t1) 'LIPS (// t1 1000.)
'MS *inf* 'INF)))
(eval-when (compile eval load)
(defun convq (t0 l0)
(cond ((pairp t0) (let* (((t1 . l1) (convq (car t0) l0))
((t2 . l2) (convq (cdr t0) l1)))
(cons (cons t1 t2) l2)))
((null (and (symbolp t0) (eq (getchar t0 1) '/?)))
(cons t0 l0))
((memq t0 l0)
(cons (cons '/? (cons (length (memq t0 l0))
t0)) l0))
((convq t0 (cons t0 l0))))))
(defmacro defpred (pred &rest body)
`(setq ,pred ',(loop for clause in body
collect (car (convq clause nil)))))
(defpred true ((true)))
(defpred = ((= ?x ?x)))
(defpred lisp ((lisp ?x ?y) . lisp))
(defpred cut ((cut) . cut))
(defpred call ((call (?x . ?y)) . call))
(defpred bagof ((bagof ?x ?y ?z) . bagof))
(defpred writeln
((writeln ?x) (lisp (progn (princ '?x) (terpri)) ?y)))
(setq *topfun*
'(lambda nil (princ "MORE? ")
(and (null (read)) '(top))))
------------------------------
Date: Wed, 17 Aug 1983 10:14 EDT
From: Ken%MIT-OZ@MIT-MC
Subject: A Pure Prolog Written In Pure Lisp
[Reprinted from the PROLOG Digest.]
;; The following is a tiny Prolog interpreter in MacLisp
;; written by Ken Kahn.
;; It was inspired by other tiny Lisp-based Prologs of
;; Par Emanuelson and Martin Nilsson
;; There are no side-effects in anywhere in the implementation
;; Though it is very slow of course.
(defun Prolog (database) ;; a top-level loop for Prolog
(prove (list (rename-variables (read) '(0)))
;; read a goal to prove
'((bottom-of-environment)) database 1)
(prolog database))
(defun prove (list-of-goals environment database level)
;; proves the conjunction of the list-of-goals
;; in the current environment
(cond ((null list-of-goals)
;; succeeded since there are no goals
(print-bindings environment environment)
;; the user answers "y" or "n" to "More?"
(not (y-or-n-p "More?")))
(t (try-each database database
(rest list-of-goals) (first list-of-goals)
environment level))))
(defun try-each (database-left database goals-left goal
environment level)
(cond ((null database-left)
()) ;; fail since nothing left in database
(t (let ((assertion
;; level is used to uniquely rename variables
(rename-variables (first database-left)
(list level))))
(let ((new-environment
(unify goal (first assertion) environment)))
(cond ((null new-environment) ;; failed to unify
(try-each (rest database-left)
database
goals-left
goal
environment level))
((prove (append (rest assertion) goals-left)
new-environment
database
(add1 level)))
(t (try-each (rest database-left)
database
goals-left
goal
environment
level))))))))
(defun unify (x y environment)
(let ((x (value x environment))
(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))
(and (equal x y) environment))
(t (let ((new-environment
(unify (first x) (first y) environment)))
(and new-environment
(unify (rest x) (rest y)
new-environment)))))))
(defun value (x environment)
(cond ((variable-p x)
(let ((binding (assoc x environment)))
(cond ((null binding) x)
(t (value (second binding) environment)))))
(t x)))
(defun variable-p (x) ;; a variable is a list beginning with "?"
(and (listp x) (eq (first x) '?)))
(defun rename-variables (term list-of-level)
(cond ((variable-p term) (append term list-of-level))
((atom term) term)
(t (cons (rename-variables (first term)
list-of-level)
(rename-variables (rest term)
list-of-level)))))
(defun print-bindings (environment-left environment)
(cond ((rest environment-left)
(cond ((zerop
(third (first (first environment-left))))
(print
(second (first (first environment-left))))
(princ " = ")
(prin1 (value (first (first environment-left))
environment))))
(print-bindings (rest environment-left) environment))))
;; a sample database:
(setq db '(((father jack ken))
((father jack karen))
((grandparent (? grandparent) (? grandchild))
(parent (? grandparent) (? parent))
(parent (? parent) (? grandchild)))
((mother el ken))
((mother cele jack))
((parent (? parent) (? child))
(mother (? parent) (? child)))
((parent (? parent) (? child))
(father (? parent) (? child)))))
;; the following are utilities
(defun first (x) (car x))
(defun rest (x) (cdr x))
(defun second (x) (cadr x))
(defun third (x) (caddr x))
------------------------------
End of AIList Digest
********************
