Lambda the Ultimate

inactiveTopic Embedding Prolog in Haskell
started 8/6/2002; 3:03:46 AM - last post 8/8/2002; 1:05:21 AM
jon fernquest - Embedding Prolog in Haskell  blueArrow
8/6/2002; 3:03:46 AM (reads: 2021, responses: 8)
Embedding Prolog in Haskell
The distinctive merit of the declarative reading of logic programs is the validity of all the laws of reasoning supplied by the predicate calculus with equality.... This paper lists a number of common laws, and proves their validity for the standard (depth-first search) procedural reading of Prolog. They also hold for alternative search strategies, e.g. breadth-first search. Our proofs of the laws are based on the standard algebra of functional programming, after the strategies have been given a rather simple implementation in Haskell.

Yet another embedded Prolog. What applications, if any, could these minimalistic, embedded logic programming systems have? Or do they only have academic and pedagogical importance? There are almost too many to list:

Posted to Logic/Declerative by jon fernquest on 8/6/02; 3:05:42 AM

Ehud Lamm - Re: Embedding Prolog in Haskell  blueArrow
8/6/2002; 3:58:57 AM (reads: 1238, responses: 0)
A seen on LtU

Noel Welsh - Re: Embedding Prolog in Haskell  blueArrow
8/6/2002; 4:59:46 AM (reads: 1223, responses: 1)
Re: What applications, if any, could these minimalistic, embedded logic programming systems have?

In my limited experience Prolog is a great tool for a very small set of problems. And it's an absolute pooch for a great many problems! So it makes sense to embed it in a more general purpose language. At Edinburgh it seemed that a lot of Prolog work used TCL (ick!) as the general purpose language around Sictus Prolog.

Ehud Lamm - Re: Embedding Prolog in Haskell  blueArrow
8/6/2002; 8:02:03 AM (reads: 1258, responses: 0)
Another way to achieve unifcation of declerative and other language features can be seen in Mercury and Mozart-Oz (pun intended).

It's not language embedding, it's concept embedding(TM).

Darius Bacon - Re: Embedding Prolog in Haskell  blueArrow
8/6/2002; 10:34:58 AM (reads: 1204, responses: 0)
Norvig's _Paradigms of AI Programming_ has a couple chapters of natural-language processing code using definite clause grammars, implemented with a Prolog-to-Lisp compiler embedded in Lisp. You might say it should just use Prolog, but Lisp has convenient stuff, too, and it all seems to work pretty well together.

jon fernquest - Re: Embedding Prolog in Haskell  blueArrow
8/7/2002; 2:52:11 AM (reads: 1173, responses: 0)
Prolog operators are a syntax feature missing from many embeddings and also the feature that makes most complex prolog programs compact and understandable, e.g. the interpreters in Computational Intelligence. I'm thinking here of lambda operators when you're building up sentence meaning in lambda expressions during DCG parsing or prolog meta-interpreters that interpret let's say "--->" clauses like those in the Story Generator I just made a posting about.

I found Norvig's prolog interpreter the easiest of them all to understand, but every embedded prolog seems to have a different S-expression syntax which I think makes them less re-usable. Getting to the point where you can think in a given syntax and program in it, takes time, and adds to the overhead of using an embedded prolog.

scruzia - Re: Embedding Prolog in Haskell  blueArrow
8/7/2002; 9:14:49 AM (reads: 1146, responses: 1)
Since many readers (including myself) are unfamiliar with the term "DCG parsing", I looked around a bit ... the first few entries in a google search for that term are not helpful at all, but this one is a nice intro:

For those who just need an expansion, Prolog's "DCG"s are "Definite Clause Grammars", a built-in Prolog mechanism for working with grammars.

Ehud Lamm - Re: Embedding Prolog in Haskell  blueArrow
8/7/2002; 9:31:13 AM (reads: 1197, responses: 0)
I think we had some links about DCGs. You should look around.

DCGs can be quite cool (I think we had a link to a course on DSLs, that used Prolog and DCGs to do some nice things).

jon fernquest - Re: Embedding Prolog in Haskell  blueArrow
8/8/2002; 1:05:21 AM (reads: 1123, responses: 0)
Here's an online tutorial that has some stuff on DCG's and Building Parse Trees for an expression grammar, since the basic DCG will only tell you whether the list of strings satisfies the grammar.

DCG's are also the natural language parsing formalism with the longest unbroken history.

The tradition starts with Schieber and Pereira's classic Prolog and Natural Language Analysis that culminates in a English question answering program in DCG: "Talk". (code available at CMU AI Repository)

Covington's book builds on Pereira and Schieber and adds a simple system for unification of untyped feature structures.

Alan Black, Robin Cooper, Ian Lewin (1993) Prolog and Natural Language Semantics: Notes for AI3/4 Computational Semantics, also builds on Pereira and Schieber adding semantics and Discourse Representation Theory (DRT) and also has an analysis of Pereira's Chat-80 question answering program.

The most recent addition to the tradition is a set of online books on computational semantics.