5 ms·

> 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 interpret

by 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 ago
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.
- le-mark 8y ago
  Thanks for taking the time to break that down.
- varjag 8y ago
  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.
  - YeGoblynQueenne 8y ago
    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.
    - varjag 8y ago
      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.
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 ago
    My mistake. I don't think I've read that book.
- varjag 8y ago
  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.
  - YeGoblynQueenne 8y ago
    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. Well, Prolog is simpler.

by varjag 8y ago

deleted 8y ago

[deleted]

YeGoblynQueenne 8y ago

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.

le-mark 8y ago
Thanks for taking the time to break that down.
varjag 8y ago
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.
- YeGoblynQueenne 8y ago
  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.
  - varjag 8y ago
    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.

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 ago
  My mistake. I don't think I've read that book.
varjag 8y ago
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.
- YeGoblynQueenne 8y ago
  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. Well, Prolog is simpler.