Embedding Prolog in Haskell

Luke once pointed to Peter Norvig's embedding of Prolog in Lisp as an example of the power of the language, and asked whether (or if) it could be done in Haskell. I said I would think about it, but never got around to working out the details.

Well, it turns out it's been done, and the essential bits are quite simple and intuitive, though macros would help to hide some of the abstract syntax-looking stuff (not apparent from the paper's append example).

J. M. Spivey and S. Seres. Embedding Prolog in Haskell. In Proceedings of Haskell '99 (E. Meijer, ed.), Technical Report UU-CS-1999-28, Department of Computer Science, University of Utrecht.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Last time

Same subject mentioned here in the past (the links to older messages end up with Seres's paper).

The Fun of Programming includes a chapter on the same topic (using a slightly different technique, IIRC).

Prolog in Javascript

Also mentioned before: Prolog in Javascript. Apparently Prolog is pretty easy to implement, it's only 15k, parser included. Look up the unify function in the source!

Update: That was an old version, new version is here.