5 ms·

How big an undertaking would it be to implement a Prolog interpreter?

by bemmu 16y ago

mbowcock 16y ago
I believe a prolog-like interpreter is created in the book The Reasoned Schemer. It's on my book shelf but haven't had the time to work through it.
- silentbicycle 16y ago
  It's called "mini-kanren", see also William Byrd's thesis. Or wait for swannodette to show up. :) He's writing a Clojure port: http://github.com/swannodette/logos http://github.com/swannodette/logos
vilhelm_s 16y ago
Depending on how large a fragment of Prolog you want to implement, it can be quite simple. SICP chapter 4.4 (http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-29.html#%_sec_4.4 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-29.html...) describes a simple interpreter written in Scheme for a Prolog-flavoured languge (without cut, and also no parser). For an even more dramatically simplified version, I wrote a extremely toy interpreter in about a hundred lines of SML: http://everything2.com/title/continuation+passing+style http://everything2.com/title/continuation+passing+style Or of course, you can implement it in a single line of Prolog. :)
- silentbicycle 16y ago
  Strictly speaking, SICP's amb implements nondeterminism (via backtracking), not Prolog. Prolog also needs unification (a more powerful form of pattern-matching), at the very least. (EDIT: Forgot about the next section, with Logic Programming.) Many Lisp books implement Prolog. Try PAIP and/or On Lisp. PAIP puts more time into implementing it well, but On Lisp covers the main ideas. I recommend both, regardless.
  - vilhelm_s 16y ago
    Amb is in SICP section 4.3 ("Nondeterministic computing"), section 4.4. is called "Logic Programming" and is implemented using streams rather than amb. I agree that On Lisp, which does it via amb, is also nice!
    - silentbicycle 16y ago
      You're right - I forgot about section 4.4. Made a note of that.
samdk 16y ago
Creating a simple, inefficient Prolog interpreter (that has most of the core functionality) is pretty easy (as far as implementing languages goes), especially if you're using another functional language to do it. I think it can be done in 100-200 lines of Haskell or ML pretty easily (although I haven't actually implemented one myself). Implementing an efficient Prolog involves implementing the Warren Abstract Machine (WAM) [0]. I just implemented a very small and restricted subset of the WAM with a friend for a class final, and doing that is much harder. (Largely because there's not a whole lot in the way of documentation, and even the book that's supposed to serve as a WAM tutorial [1] is light/vague on some of the trickier implementation details.) [0] http://en.wikipedia.org/wiki/Warren_Abstract_Machine http://en.wikipedia.org/wiki/Warren_Abstract_Machine [1] http://wambook.sourceforge.net/ http://wambook.sourceforge.net/
- silentbicycle 16y ago
  The WAM isn't the final word on efficient Prolog implementation, it was just a major improvement at the time. See the theses Peter Van Roy links to here (http://lambda-the-ultimate.org/classic/message1618.html#11082 http://lambda-the-ultimate.org/classic/message1618.html#1108...), one of which is his. Another major direction for practical Prolog implementation is constraint programming. I've been studying that off-and-on for a while, and Daniel Diaz's papers on clp(FD) (http://cri-dist.univ-paris1.fr/diaz/publications/ http://cri-dist.univ-paris1.fr/diaz/publications/) and adding CLP to the WAM seem to be a good intro.
  - swannodette 16y ago
    As silentbicycle mentions below grin, I enjoy pointing out miniKanren as a purely functional approach to building a Prolog-like system. Even at ~200 LOC the original Scheme is surprisingly efficient. My optimized Clojure version at ~1000 LOC is already closing in on SWI-Prolog on logic programs that involve a lot of unification and uninstantiated variables (such as the classic Zebra puzzle). The high water marks for efficient Prolog implementations are Peter Van Roy's work on Aquarius and The Mercury Programming Language.
    - 16y ago
WildUtah 16y ago
Among the basic Prolog interpreters is the one in the later chapters of our patron Paul Graham's On Lisp, available online for free. Graham writes it with Common Lisp macros and macro-based continuations all in about 100 expertly described and lovingly documented lines of CL. Very educational, if not so practical.
steveklabnik 16y ago
I did it for a class assignment once. In Java.
- bemmu 16y ago
  How much time did you spend on it etc?
  - steveklabnik 16y ago
    This was like 3 years ago, so I don't exactly remember, but it was something like a month-long assignment. So I started it like 3 or 4 days before, and coded furiously. The professor has taken down the course website, or I'd point you right to the assignment. Really, my sibling commenters have described it well: it's probably between 200-600 LOC, getting a simple implementation is easy but getting a performant one is hard, etc.

How big an undertaking would it be to implement a Prolog interpreter?

by bemmu 16y ago

How big an undertaking would it be to implement a Prolog interpreter?

I believe a prolog-like interpreter is created in the book The Reasoned Schemer. It's on my book shelf but haven't had the time to work through it.

silentbicycle 16y ago
It's called "mini-kanren", see also William Byrd's thesis. Or wait for swannodette to show up. :) He's writing a Clojure port: http://github.com/swannodette/logos http://github.com/swannodette/logos

vilhelm_s 16y ago

Depending on how large a fragment of Prolog you want to implement, it can be quite simple. SICP chapter 4.4 (http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-29.html#%_sec_4.4 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-29.html...) describes a simple interpreter written in Scheme for a Prolog-flavoured languge (without cut, and also no parser). For an even more dramatically simplified version, I wrote a extremely toy interpreter in about a hundred lines of SML: http://everything2.com/title/continuation+passing+style http://everything2.com/title/continuation+passing+style Or of course, you can implement it in a single line of Prolog. :)

silentbicycle 16y ago
Strictly speaking, SICP's amb implements nondeterminism (via backtracking), not Prolog. Prolog also needs unification (a more powerful form of pattern-matching), at the very least. (EDIT: Forgot about the next section, with Logic Programming.) Many Lisp books implement Prolog. Try PAIP and/or On Lisp. PAIP puts more time into implementing it well, but On Lisp covers the main ideas. I recommend both, regardless.
- vilhelm_s 16y ago
  Amb is in SICP section 4.3 ("Nondeterministic computing"), section 4.4. is called "Logic Programming" and is implemented using streams rather than amb. I agree that On Lisp, which does it via amb, is also nice!
  - silentbicycle 16y ago
    You're right - I forgot about section 4.4. Made a note of that.

samdk 16y ago

Creating a simple, inefficient Prolog interpreter (that has most of the core functionality) is pretty easy (as far as implementing languages goes), especially if you're using another functional language to do it. I think it can be done in 100-200 lines of Haskell or ML pretty easily (although I haven't actually implemented one myself). Implementing an efficient Prolog involves implementing the Warren Abstract Machine (WAM) [0]. I just implemented a very small and restricted subset of the WAM with a friend for a class final, and doing that is much harder. (Largely because there's not a whole lot in the way of documentation, and even the book that's supposed to serve as a WAM tutorial [1] is light/vague on some of the trickier implementation details.) [0] http://en.wikipedia.org/wiki/Warren_Abstract_Machine http://en.wikipedia.org/wiki/Warren_Abstract_Machine [1] http://wambook.sourceforge.net/ http://wambook.sourceforge.net/

silentbicycle 16y ago
The WAM isn't the final word on efficient Prolog implementation, it was just a major improvement at the time. See the theses Peter Van Roy links to here (http://lambda-the-ultimate.org/classic/message1618.html#11082 http://lambda-the-ultimate.org/classic/message1618.html#1108...), one of which is his. Another major direction for practical Prolog implementation is constraint programming. I've been studying that off-and-on for a while, and Daniel Diaz's papers on clp(FD) (http://cri-dist.univ-paris1.fr/diaz/publications/ http://cri-dist.univ-paris1.fr/diaz/publications/) and adding CLP to the WAM seem to be a good intro.
- swannodette 16y ago
  As silentbicycle mentions below grin, I enjoy pointing out miniKanren as a purely functional approach to building a Prolog-like system. Even at ~200 LOC the original Scheme is surprisingly efficient. My optimized Clojure version at ~1000 LOC is already closing in on SWI-Prolog on logic programs that involve a lot of unification and uninstantiated variables (such as the classic Zebra puzzle). The high water marks for efficient Prolog implementations are Peter Van Roy's work on Aquarius and The Mercury Programming Language.
  - 16y ago

WildUtah 16y ago

Among the basic Prolog interpreters is the one in the later chapters of our patron Paul Graham's On Lisp, available online for free. Graham writes it with Common Lisp macros and macro-based continuations all in about 100 expertly described and lovingly documented lines of CL. Very educational, if not so practical.

steveklabnik 16y ago

I did it for a class assignment once. In Java.

bemmu 16y ago
How much time did you spend on it etc?
- steveklabnik 16y ago
  This was like 3 years ago, so I don't exactly remember, but it was something like a month-long assignment. So I started it like 3 or 4 days before, and coded furiously. The professor has taken down the course website, or I'd point you right to the assignment. Really, my sibling commenters have described it well: it's probably between 200-600 LOC, getting a simple implementation is easy but getting a performant one is hard, etc.