PEREIRA@SRI-AI.ARPA@sri-unix.UUCP (08/19/83)
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