20 ms·
>> Two decades after its creation, Lisp had become, according to the famous Hacker’s Dictionary, the “mother tongue” of artificial intelligence research. More
by YeGoblynQueenne 8y ago
>> 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.
- varjag 8y ago> 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.
- deleted 8y ago[deleted]
- YeGoblynQueenne 8y agoIt'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.
- le-mark 8y agoThanks for taking the time to break that down.
- varjag 8y agoMYCIN 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.
- YeGoblynQueenne 8y agoI 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.
- varjag 8y agoPeriod-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.
- 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 agoSymbolics had a Prolog compiler for their Lisp Machines, with optimized microcode for the processor. It also supported japanese...
- YeGoblynQueenne 8y agoI'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.
- zeveb 8y ago> That must have been a brutal time to be involved in AI research. They don’t call it the AI Winter because it was fun!
- kazinator 8y agoEven 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.
- YeGoblynQueenne 8y agoA DSL? The first order predicate calculus, a DSL? I don't think we're really on the same page here.
- marcosdumay 8y agoTo be fair, the first task of any AI project in Prolog is to implement a different search algorithm. So I don't seem much gain (or loss).
- YeGoblynQueenne 8y agoI'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.