Ken%MIT-OZ%MIT-MC@sri-unix.UUCP (04/05/84)
Regarding the recent discussion about whether in building a
Prolog system one should write a compiler first and write
the interpreter in Prolog or write the interpreter in some
other language and then bring up a compiler in Prolog.
First, what one should NOT do is develop the interpreter and
compiler seperately and then try to put them together. I
originally wrote the LM-Prolog interpreter and later Mats
Carlsson wrote a compiler for the same Prolog dialect. Much
later we decided to put the systems together. We started
with a simple interface between the two systems and it
became more and more hairy with time. Finally, we decided
to do a drastic re-write of both systems so that they no
longer needed an interface.
As some of you may know, I've been trying to compile Prolog
programs without using a Prolog compiler. The idea is to
use partial evaluation as a means of specializing the Prolog
interpreter for different Prolog programs. Within the last
week I've gotten the system to start to work. I've
specialized the interpreter to run "=", "member",
"concatenate", and "naive-reverse". The specialized
interpreters are between 4 and 6 times faster than ordinary
interpretation. "member" runs about 50% faster than compiled
LM-Prolog. "concatenate" is about the same speed. (With
some more work it can be about 15% faster). This is
especically encouraging since the LM-Prolog compiler is very
good and performs many optimizations. The time to
specialize these predicates is about 1 or 2 cpu minutes on a
Cadr Lisp Machine. The size of the specialized interpreters
is about the same as the corresponding compiled predicates.
The reason that "compiled code" is only 4 to 6 times faster is
that the interpreter is very fast. For DEC-20 Prolog a
factor of 20 is not uncommon between compiled and
interpreted. This is because the DEC-20 interpreter is
slow. Jonas Barklund here in Uppsala wrote a Prolog
interpreter in assembler for the DEC-20 and its about 3
times faster than the DEC-20 interpreter.
The following is from Mats Carlsson:
Re: On Three Ways Of Copying Prolog Terms And Their Speed.
O'Keefe wanted to see some timings for various methods for
copying terms in LM-Prolog. Copy2 and copy3 do not translate
well into LM-Prolog since conses are our only functors.
Instead we wrote copy4 as the "natural" translation of
copy2/copy3 and copy5 using the bag trick. Copy5 really
translates to nothing but a call to a copying routine written
in Lisp. We got these figures:
Example 0 1 4
copy1 34 40 130
copy4 2,8 16,8 179
copy5 1,7 4,6 38
Times are in milliseconds and the examples were run on a
CADR.
[I would like to point out that only copy5 works on circular
terms (infinite trees). The overhead for this capability is
at most 2%. copy1 could work for circular terms but we
decided that it was not worth the trouble supporting
database assertions containing circular terms. copy4 would
need to be re-written if it were to handle circularity.
--Ken Kahn]
Here is the source code:
;;; Mode:LISP; Package:PROLOG; Options:((EXECUTION COMPILED))
(define-predicate |copy| :(options (type dynamic)))
(define-predicate copy1
((copy1 ?old ?new)
(assert ((|copy| ?old)))
(retract ((|copy| ?new)))
(cut)))
(define-predicate fast-identical
:(options (compile-method open))
((fast-identical ?x ?y) (lisp-predicate (eq '?x '?y) :dont-invoke)))
(define-predicate fast-variable
:(options (compile-method open))
((fast-variable ?x) (lisp-predicate (value-cell-p '?x) :dont-invoke)))
(define-predicate associative
((associative ?new ?old ?vars)
(cases ((fast-variable ?vars) (= ?vars ((?old . ?new) . ?)))
((= ?vars ((?old1 . ?new1) . ?vars1))
(cases ((fast-identical ?old ?old1) (= ?new ?new1))
((associative ?new ?old ?vars1)))))))
(define-predicate copy4
((copy4 ?old ?new ?vars)
(fast-variable ?old)
(cut)
(associative ?new ?old ?vars))
((copy4 (?x . ?y) (?a . ?b) ?vars)
(cut)
(copy4 ?x ?a ?vars)
(copy4 ?y ?b ?vars))
((copy4 ?x ?x ?)))
(define-predicate copy5
((copy5 ?old ?new)
(lazy-bag-of (?new) ?old)))
(define-predicate example
((example 0 (or (and a b) c)))
((example 1 ((copy4 (?x . ?y) (?a . ?b) ?vars)
(copy4 ?x ?a ?vars)
(copy4 ?y ?b ?vars))))
((example 4 (and (<-> (true ?p) (t w0 ?p))
(<-> (t ?w1 (and ?p1 ?p2)) (and (t ?w1 ?p1) (t ?w1 ?p2)))
(<-> (t ?w1 (or ?p1 ?p2)) (or (t ?w1 ?p1) (t ?w1 ?p2)))
(<-> (t ?w1 (-> ?p1 ?p2)) (-> (t ?w1 ?p1) (t ?w1 ?p2)))
(<-> (t ?w1 (<-> ?p1 ?p2)) (<-> (t ?w1 ?p1) (t ?w1 ?p2)))
(<-> (t ?w1 (~ ?p1)) (~ (t ?w1 ?p1)))
(<-> (t ?w1 (know ?a1 ?p1)) (all ?w2 (-> (k ?a1 ?w1 ?w2)(t ?w2 ?p1))))
(k ?a1 ?w1 ?w1)
(-> (k ?a1 ?w1 ?w2) (k ?a1 ?w2 ?w3) (k ?a1 ?w1 ?w3))
(-> (k ?a1 ?w1 ?w2) (k ?a1 ?w1 ?w3) (k ?a1 ?w2 ?w3))
(<-> (t ?w1 (know ?a ?p)) (all ?w2 (-> (k ?a ?w1 ?w2)(t ?w2 ?p))))))))
(define-predicate time-n-times
((time-n-times ?n ?predication)
(no-clock-interrupts)
(time-and-print (n-times ?n ?predication))))
(define-predicate n-times
((n-times ?n ?predication)
(bag-of ? ? (repeat ?n) ?predication)))
(define-predicate copy-benchmark
((copy-benchmark ?i)
(example ?i ?example)
(prove-once (time-n-times 10. (copy1 ?example ?)))
(prove-once (time-n-times 10. (copy4 ?example ? ?)))
(prove-once (time-n-times 10. (copy5 ?exaple ?)))))