3 ms·
>> Implementing Prolog however is trivial in Lisp, so many textbooks used it as an intermediate level exercise. I've heard this kind of thing before- but it's
by YeGoblynQueenne 8y ago
>> Implementing Prolog however is trivial in Lisp, so many textbooks used it as
an intermediate level exercise.
I've heard this kind of thing before- but it's not true. What is usually
implemented in Lisp textbooks, is not Prolog. It's a logic programming loop
with pattern matching, sure, though I'm not even sure it's unification (i.e.
Turing-complete pattern matching) rather than regular expression matching.
Even the SICP book makes sure to call the language it implements the "query
language", rather than Prolog. The whole point of Prolog is to use the syntax
and semantics of first order logic as a programming language. You can't have
Prolog without the representation of programs as Horn clauses, any more than
you can have Lisp without S-expressions.
And those "trivial" implementations you note, don't do that- they implement a
logic programming loop, but retain the full syntax of Lisp. That's why they
are "trivial" to implement- and that's why they are not Prolog.
- lispm 8y ago> What is usually implemented in Lisp textbooks, is not Prolog When a Lisp textbook says it implements Prolog, it implements it with unification. See for example Paradigms of AI Programming, by Peter Norvig - the chapters on implementing a Prolog compiler...
- YeGoblynQueenne 8y agoMy mistake. I don't think I've read that book.
- varjag 8y agoNo, they do implement Horn clauses, it's not really super hard. Had it as a homework long long ago. Syntax is irrelevant, and it's not like Prolog has complicated grammar if you want to go for canonical syntax anyway.
- YeGoblynQueenne 8y agoOh, syntax is important. Otherwise, I can implement Lisp in Prolog trivially, by rewriting each function of arity n, by hand, as a predicate of arity n+1 (the extra argument binding to the output of the function). After that, I wouldn't even need to write an explicit Lisp interpreter- my "Lisp" program would simply be executed as ordinary Prolog. I believe that if I were to suggest this as a honest-to-God way to implement Lisp in Prolog, any decent Lisper would be up in arms and accusing me of cheating. And yet, this is pretty much the approach taken by the Lisp textbooks we're discussing. Their "Prolog interpreters" cannot parse Prolog syntax, therefore programs must be given to them as Lisp. Then, because Lisp is not an automated theorem prover, one must be implemented, accepting the Lisp pretending to be Prolog. That's not a trivial implementation of Prolog- it's an incomplete implementation. Yes, Prolog has very simple syntax: everything is a Horn clause, plus some punctuation. That's simpler even than Lisp. You keep saying how simple Prolog is to implement, as if it was a bad thing. According to the article above, the simplicity of Lisp is where its power comes from. Well, Prolog is simpler.
- lispm 8y ago> Otherwise, I can implement Lisp in Prolog trivially, by rewriting each function of arity n, by hand, as a predicate of arity n+1 (the extra argument binding to the output of the function) Programming languages don't consist only of functions. Lisp is no exception. > Their "Prolog interpreters" cannot parse Prolog syntax, therefore programs must be given to them as Lisp. There are Lisp-based Prolog implementations which can parse Edinburgh syntax and have a Lisp syntax variant. I have a version of LispWorks, which does that. But the syntax is just a surface - the Lisp-based Prolog does unification, etc. just as a typical Prolog implementation. It supports the same ideas of adding, retracting facts and etc. The MAIN difference between REAL Prolog implementations and most Lisp-based is that the real Prolog implementations provide a much more sophisticated version of the Prolog language (and more of the typical Prolog library one would expect) and some have extensive optimizations and native code compilers - thus they are usually quite a bit faster. Interested Lisp users are usually only looking for the reasoning features of Prolog (to include those in directly in programs) and not in the specific Prolog syntax. Sometimes, also to have Prolog-based parsing techniques in a Lisp program.
- YeGoblynQueenne 8y ago>> There are Lisp-based Prolog implementations which can parse Edinburgh syntax and have a Lisp syntax variant. I was talking specifically about the Prolog implementations given as exercises in Lisp textbooks. Those, usually, are incomplete, in the ways that I describe above. LispWorks for instance, seems to be a commercial product, so I'd expect it to be more complete. I don't expect a Prolog-as-a-Lisp-exercise to go full-on and implement the Warren Abstract Machine. But, equally, I think the insistence of the other commenter, varjag, to the simplicity and even triviality of implementing Prolog as an exercise in Lisp textbooks is due to the fact that those exercises only implement the trivial parts. >> Interested Lisp users are usually only looking for the reasoning features of Prolog (to include those in directly in programs) and not in the specific Prolog syntax. Sometimes, also to have Prolog-based parsing techniques in a Lisp program. That's my intuition also- as encoded in the addendum to Greenspun's tenth rule. Tongue in cheek and all :)