>> Two decades after its creation, Lisp had become, according to the famous
Hacker’s Dictionary, the “mother tongue” of artificial intelligence research.
More precisely, Lisp became the "mother tongue" of AI research in the United
States. Europe and Japan, which at the time also had a significant output
into AI research, instead used Prolog as a lingua franca.
This is interesting to note, because a common use of Lisp in AI was (is?) to
write an interpreter for a logic programming language and then use that
interpreter to perform inference tasks as required (this approach is evident,
for example, in Structure and Interpretation of Computer Programs, which
devotes chapter 4.3 to the development of a logic programming language, the
query language, which is basically Prolog with Lisp parentheses).
Hence the common response, by Prolog programmers, to Greenspun's tenth rule,
that:
Any sufficiently complicated Lisp program contains an ad-hoc,
informally-specified, bug-ridden, slow implementation of Edinburgh Prolog.
> This is interesting to note, because a common use of Lisp in AI was (is?) to write an interpreter for a logic programming language and then use that interpreter to perform inference tasks as required
Not sure how you come to that conclusion. Literally none of the notable Lisp AI programs (ELIZA, STUDENT, SHRDLU, AM, EURISKO, MICYN) had anything to do with reimplementing Prolog.
Implementing Prolog however is trivial in Lisp, so many textbooks used it as an intermediate level exercise.
It's the response to Greenspun's tenth rule that mentions Prolog explicitly.
My previous comment states that AI programs written in Lisp implemented an
interpreter for a logic programming language, unspecified. Although to be
fair, that usually means "an informally-specified, ad-hoc, bug-ridden, slow
implementation of Prolog" (1).
Now, my knowledge of Eliza, Shrdlu, etc is a little limited (I've never read
the source, say; btw, have you?) but let's see. Wikipedia is my friend, below.
According to wikipedia MYCIN was a backwards chaining expert system. That
means a logic programming loop, very likely a resolution-based theorem prover,
or, really, (1).
ELIZA was first implemented in MAD-SLIP, which, despite the name was not a
Lisp variant (although it was a list-processing language). STUDENT is
actually part of ELIZA- it's one of the two scripts that came with the
original implementation, by Wizenbaum. The other script is DOCTOR, which is
the one more often associated with ELIZA (it's the psychoanalyst). If I
understand correctly, STUDENT solves logic problems, so I'm guessing it
incorporates an automated theorem prover; so basically, (1).
Eurisko was written in a frame-based (think OOP) representation language
called RLL-1, the interpeter for which was written in Lisp.
SHRDLU was written in Lisp and MicroPlanner an early logic programming
language (with forward chaining, if memory serves). In the event, (1) was not
necessary, as MicroPlanner was already all that- and more!
The Automated Mathematician (AM) was indeed written in Lisp, but I don't know
anything about its implementation. However, from the description on its
wikipedia page it appears to have included a very basic inference procedure
and a rule-base of heuristics. Sounds like a case of (1) to me.
MYCIN is a fuzzy logic inference engine, among the first ones. Would love to see that implemented in period-true Prolog, but tbh won't hold my breath.
RLL-1 and Microplanner are domain-specific languages, traditional Lisp approach to building complex applications. Fact is both were written in Lisp, that's just sophistry.
Neither AM nor EURISKO would map naturally to unification with their very special heuristic-driven task prioritizing and scheduling algorithms.
I don't know what "period-true Prolog" is. You can still run programs found in
Prolog textbooks from the 1970's in modern Prolog interpreters- just like with
Lisp.
>> Fact is both were written in Lisp, that's just sophistry.
I don't see the sophistry. If I implement Lisp in Prolog, the interpreter may be Prolog, but the programs it then evaluates are Lisp.
I don't see why unification would be an impediment in implementing any
heuristics or scheduling algorithms.
Period-true as in from 1970s. There were attempts to build fuzzy Prolog dialects in late 1980s, although it seems not particularly successful.
> If I implement Lisp in Prolog, the interpreter may be Prolog, but the programs it then evaluates are Lisp.
But it does not implement Lisp in Prolog. It implements a domain specific language in Lisp in a time proven manner. Googling "DSL Lisp" will give you probably hundreds of references. I did it before for my own projects and my "languages" even had no name. I could call it VARLANG-22 or whatever, but unless I told you all you'd see is some Lisp code.
> I don't see why unification would be an impediment in implementing any heuristics or scheduling algorithms.
It does not bring anything to the table there, because that's not how those systems work. Not every project is a first order predicate logic expression, as incredible as it sounds.
We're in a weird situation here. In this thread, you're arguing that a programming language implemented in Lisp, which retains the syntax of Lisp, is a DSL, and so still just Lisp; but in the other thread, you're arguing that Prolog implemented in Lisp, with the syntax of Lisp, is not a DSL, but Prolog.
I recognise that the above comes across as an attempt at sophistry, again, but I sincerely think you are not being objective, with this line of thinking.
>> 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.
> 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...
No, 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.
Oh, 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.
> 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.
>> 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 :)
Lisp books, especially in AI Programming, have implemented various Logics - predicate logic based programming like standard Prolog is just one. Peter Norvig has a relative extensive example how to implement Prolog and how to compile it. Others concentrate on some other logic calculus. It's not surprising that various books have different depths in showing how to implement various embedded languages. In case of Norvig's implementation, others have used in their application.
It has nothing to do with Greenspun at all. Lisp and then Common Lisp was used in many AI programming frameworks and these integrated various paradigms: rule systems, various logics, objects, frames, constraints, semantic networks, fuzzy logic, relational, ... Lisp was explicitly designed for this - there is nothing accidental about it. It is one of the main purposes of Lisp in AI Programming to enable experiments and implementations of various paradigms. That means that these frameworks EXPLICLTY implement something like predicate logics or other logics. These features are advertized and documented.
Greenspun claimed that complex C++ programs more or less ACCIDENTALLY implement half of a Lisp implementation, because the large enough implementations need these features: automatic memory management, runtime loading of code, dynamic data structures like lists and trees, runtime scripting, saving and loading of state, configuration of software, a virtual machine, ... These programs implement some random subsets of what a Common Lisp system may provide, but they don't implement Common Lisp or its features directly. Most C++ developers don't know that these features actually exist in Lisp and they don't care. Similar the Java VM implements some stuff one could find in a Smalltalk or Lisp system: virtual machine, code loading, managed memory, calling semantics, ...
Well, the addendum to Greenspun's tenth rule works even if the ad-hoc etc implementation of half of Prolog is not accidental.
Like I say, it's tongue in cheek. I think (hope) programmers are somewhat over having any serious arguments about which language is "best" at this point in time. Although perhaps my own comments in this thread disagree. I am a little embarrassed about that.
> Their "Prolog interpreters" cannot parse Prolog syntax, therefore programs must be given to them as Lisp
Unless the project has a clear requirement to re-use unmodified/untranslated Prolog code, or to produce code that will be shared with Prologs, this would only be a disadvantage. The Prolog syntax as such has no value; it is all in the semantics.
> Then, because Lisp is not an automated theorem prover, one must be implemented, accepting the Lisp pretending to be Prolog.
Also, Lisp isn't a virtual machine, so one must be implemented. There is a compiler routine which pretends to be Lisp, accepting the special forms and translates them into executable code. It's just a big cheat.
> 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.
If you had quote and macros and such working in this manner, just with the f(x, y) style syntax, that would be a valid implementation. There is a convenience to the (f x y) syntax, but the semantics is more important.
We can have infix syntax in Lisp as a separate module that works independently of a given DSL.
Separation of concerns/responsibilities and all that.
I'm guessing they were trying to entice the Japanese market. If I have that right, it must have all been around the time of the Fifth Generation Computer Project, which aimed to create an architecture that would run a massively parallelisable logic programming language natively.
That eventually imploded and took logic programming and, I think, the whole of symbolic AI with it. I think Symbolics, selling a very expensive computer running Lisp natively, failed soon after?
That must have been a brutal time to be involved in AI research.
Even if that is true, it's probably an issue of low severity, since that Greenspunned Prolog will probably be used for a very specific task in the overall application, not as the master glue to hold it all together. (Though we can't rule that out, of course). Also, there have been some decent inference systems written in Lisp; they can just be used off the shelf.
I would say that Prolog as a standalone language is silly: an entire programming language developed from the ground up, with numerous details such as I/O and memory management, just for the sake of supporting a logic programming DSL.
Writing all this stuff from scratch for every domain-specific language is very unproductive, and has the effect of segregating all those languages into their own sandboxes that are hard to integrate into one application.
I've assisted with the teaching of Prolog at my university (as a TA) and the first task is usually something like the append/3 predicate (used to append two lists, or split them, etc).
Last year, the end-of-term exercise involved the farmer-wolf-goat-cabbage problem, which can be (and was) solved just fine with Prolog's built-in depth-first search.
I think though you may be talking of forward chaining, rather than depth-first search? That is, indeed a classic exercise in Prolog.
More precisely, Lisp became the "mother tongue" of AI research in the United States. Europe and Japan, which at the time also had a significant output into AI research, instead used Prolog as a lingua franca.
This is interesting to note, because a common use of Lisp in AI was (is?) to write an interpreter for a logic programming language and then use that interpreter to perform inference tasks as required (this approach is evident, for example, in Structure and Interpretation of Computer Programs, which devotes chapter 4.3 to the development of a logic programming language, the query language, which is basically Prolog with Lisp parentheses).
Hence the common response, by Prolog programmers, to Greenspun's tenth rule, that: