7 ms·

I was wondering if anyone knows of a resource in the same vein as [1] or [2] but to implement a prolog interpreter instead of lisp. 1: https://github.com/kanak

I was wondering if anyone knows of a resource in the same vein as [1] or [2] but to implement a prolog interpreter instead of lisp. 1: https://github.com/kanaka/mal https://github.com/kanaka/mal 2: http://www.buildyourownlisp.com/ http://www.buildyourownlisp.com/

howerj 6y ago
I was hoping there would be something like this as well, all of the prolog interpreters out there are either too complex or do not explain how they work. I might have to write something myself as implementing your own (toy) interpreter is a good way to fully understand the concepts behind the language.
ookdatnog 6y ago
Perhaps not quite what you're looking for, but the free MIT book "Structure and Interpretation of Computer Programs" (https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book.html https://mitpress.mit.edu/sites/default/files/sicp/full-text/...) has a section on interpreting logic programs (section 4.4) in Scheme. I think it's sufficient to understand the semantics of Prolog, but I'm not sure how much of the rest of the book you'd need to read to understand that chapter (it's an amazing book though!) edit: to be clear, in the book you interpret a logic programming language with lisp-like syntax
gglitch 6y ago
I believe several of the canonical Lisp books implement a simple Prolog as an exercise. I’m pretty sure Norvig’s Paradigms of Artifical Intelligence Programming, pg's On Lisp, and Winston & Horn’s Lisp all do.
- Jtsummers 6y ago
  The relevant section of PAIP: https://github.com/norvig/paip-lisp/blob/master/docs/chapter11.md https://github.com/norvig/paip-lisp/blob/master/docs/chapter... Also worth exploring The Reasoned Schemer which teaches minikanren, which can be (and has been) implemented in many programming languages. It explores much of the same space as Prolog. I wrote most of a minikanren in Common Lisp while working through the book (someone else had already published a version to quicklisp which was better than what I made).
  - abecedarius 6y ago
    The PAIP implementation seems more practical than the other textbook Prologs I've seen like SICP's, while still quite small and clear.
    - Jtsummers 6y ago
      If you've never gone through PAIP, you're in for a treat. Most of the code is very practically written (I'd wager all, but it's been a while since I read/worked through it). Norvig writes good code, see also his website and many of the Python programs he's published over the years since he switched to it.
ethagnawl 6y ago
You could study core.logic: https://github.com/clojure/core.logic/tree/master/src/main/clojure https://github.com/clojure/core.logic/tree/master/src/main/c... I swear I'd bookmarked a resource that was more analogous to #2, but you may want to have a look at The Little Prover: https://mitpress.mit.edu/books/little-prover https://mitpress.mit.edu/books/little-prover
- tobmlt 6y ago
  Yep! Or go for miniKanren if you want something like core.logic, but outside of clojure. Will Byrd has a lot of documentation out there. (Scheme focus of course.) I think the easiest way for a programmer with a vanilla background to “get it” is here: https://codon.com/hello-declarative-world https://codon.com/hello-declarative-world
carapace 6y ago
Traditionally the WAM[1] has been the route, but see Paul Tarau's "A Hitchhiker’s Guide to Reinventing a Prolog Machine"[2]. Check out also Nils M Holm's "PROLOG Control in Six Slides"[3] [1] https://en.wikipedia.org/wiki/Warren_Abstract_Machine https://en.wikipedia.org/wiki/Warren_Abstract_Machine [2] https://www.cse.unt.edu/~tarau/research/2017/eng.pdf https://www.cse.unt.edu/~tarau/research/2017/eng.pdf [3] https://www.t3x.org/bits/prolog6.html https://www.t3x.org/bits/prolog6.html https://news.ycombinator.com/item?id=20591771 https://news.ycombinator.com/item?id=20591771 I don't know anything about it but there's "Prolog.c: a simple Prolog interpreter written in 200 LOC of C++ (2000) (cam.ac.uk)" https://news.ycombinator.com/item?id=12193694 https://news.ycombinator.com/item?id=12193694 http://www.cl.cam.ac.uk/~am21/research/funnel/prolog.c http://www.cl.cam.ac.uk/~am21/research/funnel/prolog.c
deleted 6y ago
[deleted]
bmitc 6y ago
There is The Reasoned Schemer. https://www.amazon.com/Reasoned-Schemer-MIT-Press/dp/0262535513 https://www.amazon.com/Reasoned-Schemer-MIT-Press/dp/0262535...
- agumonkey 6y ago
  I skimming through it. I wonder if people prefer this or kanren over good old prolog.
  - remexre 6y ago
    I definitely prefer miniKanren, but (with a small sample size) find that non-logic programmers have an easier time reading simple Prolog than equally-simple miniKanren.
inetsee 6y ago
It's not exactly what you're asking for, but there is "Racklog: Prolog-Style Logic Programming" https://docs.racket-lang.org/racklog/ https://docs.racket-lang.org/racklog/ which is "an embedding of Prolog-style logic programming in Racket". You could see how they added Prolog style logic functions to the Racket programming language.
DonaldFisk 6y ago
There's details on how to implement Prolog (in Common Lisp) in Peter Norvig's Paradigms of Artificial Intelligence: https://github.com/norvig/paip-lisp/blob/master/docs/chapter11.md https://github.com/norvig/paip-lisp/blob/master/docs/chapter... There's also Implementations of Prolog: https://archive.org/details/implementationso0000unse https://archive.org/details/implementationso0000unse (limited preview)
- jshprentz 6y ago
  Implementations of Prolog was published in 1984; its contents predate the Warren Abstract Machine. Pages 87-92 contain the article "The world's shortest Prolog interpreter?" by M. Nilsson of Uppsala University. The article describes and provides source code for a simple Lisp implementation of Prolog.
floxy 6y ago
You might like to check out Chapter 2 of "The Art of Prolog"; it has enough information to tell you how to make a bare-bones prolog interpreter.
hendler 6y ago
I see https://github.com/mthom/scryer-prolog https://github.com/mthom/scryer-prolog written in Rust?
i_don_t_know 6y ago
The closest thing that I know of is "Warren's Abstract Machine: A Tutorial Reconstruction" by Hassan Aït-Kaci. It's out of print but available as a PDF at http://wambook.sourceforge.net http://wambook.sourceforge.net
vram22 6y ago
I have not looked at your [1] or [2], but I seem to vaguely remember that either a PG book On Lisp or ANSI Common Lisp (wordplay accidental but retained about the "On", heh) or a Peter Norvig book (one of his two main ones) has a chapter or two on implementing Prolog interpreters. Edit: Oops. After posting my comment, just saw DonaldFisk's comment here: https://news.ycombinator.com/item?id=26244021 https://news.ycombinator.com/item?id=26244021 So Norvig's PAIP may be the book where I saw it. Edit 2: Also just saw gglitch's comment: https://news.ycombinator.com/item?id=26242603 https://news.ycombinator.com/item?id=26242603 which confirms my first surmise about both the PG and Norvig books containing it.

howerj 6y ago

I was hoping there would be something like this as well, all of the prolog interpreters out there are either too complex or do not explain how they work. I might have to write something myself as implementing your own (toy) interpreter is a good way to fully understand the concepts behind the language.

ookdatnog 6y ago

Perhaps not quite what you're looking for, but the free MIT book "Structure and Interpretation of Computer Programs" (https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book.html https://mitpress.mit.edu/sites/default/files/sicp/full-text/...) has a section on interpreting logic programs (section 4.4) in Scheme. I think it's sufficient to understand the semantics of Prolog, but I'm not sure how much of the rest of the book you'd need to read to understand that chapter (it's an amazing book though!) edit: to be clear, in the book you interpret a logic programming language with lisp-like syntax

gglitch 6y ago

I believe several of the canonical Lisp books implement a simple Prolog as an exercise. I’m pretty sure Norvig’s Paradigms of Artifical Intelligence Programming, pg's On Lisp, and Winston & Horn’s Lisp all do.

Jtsummers 6y ago
The relevant section of PAIP: https://github.com/norvig/paip-lisp/blob/master/docs/chapter11.md https://github.com/norvig/paip-lisp/blob/master/docs/chapter... Also worth exploring The Reasoned Schemer which teaches minikanren, which can be (and has been) implemented in many programming languages. It explores much of the same space as Prolog. I wrote most of a minikanren in Common Lisp while working through the book (someone else had already published a version to quicklisp which was better than what I made).
- abecedarius 6y ago
  The PAIP implementation seems more practical than the other textbook Prologs I've seen like SICP's, while still quite small and clear.
  - Jtsummers 6y ago
    If you've never gone through PAIP, you're in for a treat. Most of the code is very practically written (I'd wager all, but it's been a while since I read/worked through it). Norvig writes good code, see also his website and many of the Python programs he's published over the years since he switched to it.

ethagnawl 6y ago

You could study core.logic: https://github.com/clojure/core.logic/tree/master/src/main/clojure https://github.com/clojure/core.logic/tree/master/src/main/c... I swear I'd bookmarked a resource that was more analogous to #2, but you may want to have a look at The Little Prover: https://mitpress.mit.edu/books/little-prover https://mitpress.mit.edu/books/little-prover

tobmlt 6y ago
Yep! Or go for miniKanren if you want something like core.logic, but outside of clojure. Will Byrd has a lot of documentation out there. (Scheme focus of course.) I think the easiest way for a programmer with a vanilla background to “get it” is here: https://codon.com/hello-declarative-world https://codon.com/hello-declarative-world

carapace 6y ago

Traditionally the WAM[1] has been the route, but see Paul Tarau's "A Hitchhiker’s Guide to Reinventing a Prolog Machine"[2]. Check out also Nils M Holm's "PROLOG Control in Six Slides"[3] [1] https://en.wikipedia.org/wiki/Warren_Abstract_Machine https://en.wikipedia.org/wiki/Warren_Abstract_Machine [2] https://www.cse.unt.edu/~tarau/research/2017/eng.pdf https://www.cse.unt.edu/~tarau/research/2017/eng.pdf [3] https://www.t3x.org/bits/prolog6.html https://www.t3x.org/bits/prolog6.html https://news.ycombinator.com/item?id=20591771 https://news.ycombinator.com/item?id=20591771 I don't know anything about it but there's "Prolog.c: a simple Prolog interpreter written in 200 LOC of C++ (2000) (cam.ac.uk)" https://news.ycombinator.com/item?id=12193694 https://news.ycombinator.com/item?id=12193694 http://www.cl.cam.ac.uk/~am21/research/funnel/prolog.c http://www.cl.cam.ac.uk/~am21/research/funnel/prolog.c

deleted 6y ago

[deleted]

bmitc 6y ago

There is The Reasoned Schemer. https://www.amazon.com/Reasoned-Schemer-MIT-Press/dp/0262535513 https://www.amazon.com/Reasoned-Schemer-MIT-Press/dp/0262535...

agumonkey 6y ago
I skimming through it. I wonder if people prefer this or kanren over good old prolog.
- remexre 6y ago
  I definitely prefer miniKanren, but (with a small sample size) find that non-logic programmers have an easier time reading simple Prolog than equally-simple miniKanren.

inetsee 6y ago

It's not exactly what you're asking for, but there is "Racklog: Prolog-Style Logic Programming" https://docs.racket-lang.org/racklog/ https://docs.racket-lang.org/racklog/ which is "an embedding of Prolog-style logic programming in Racket". You could see how they added Prolog style logic functions to the Racket programming language.

DonaldFisk 6y ago

There's details on how to implement Prolog (in Common Lisp) in Peter Norvig's Paradigms of Artificial Intelligence: https://github.com/norvig/paip-lisp/blob/master/docs/chapter11.md https://github.com/norvig/paip-lisp/blob/master/docs/chapter... There's also Implementations of Prolog: https://archive.org/details/implementationso0000unse https://archive.org/details/implementationso0000unse (limited preview)

jshprentz 6y ago
Implementations of Prolog was published in 1984; its contents predate the Warren Abstract Machine. Pages 87-92 contain the article "The world's shortest Prolog interpreter?" by M. Nilsson of Uppsala University. The article describes and provides source code for a simple Lisp implementation of Prolog.

floxy 6y ago

You might like to check out Chapter 2 of "The Art of Prolog"; it has enough information to tell you how to make a bare-bones prolog interpreter.

hendler 6y ago

I see https://github.com/mthom/scryer-prolog https://github.com/mthom/scryer-prolog written in Rust?

i_don_t_know 6y ago

The closest thing that I know of is "Warren's Abstract Machine: A Tutorial Reconstruction" by Hassan Aït-Kaci. It's out of print but available as a PDF at http://wambook.sourceforge.net http://wambook.sourceforge.net

vram22 6y ago

I have not looked at your [1] or [2], but I seem to vaguely remember that either a PG book On Lisp or ANSI Common Lisp (wordplay accidental but retained about the "On", heh) or a Peter Norvig book (one of his two main ones) has a chapter or two on implementing Prolog interpreters. Edit: Oops. After posting my comment, just saw DonaldFisk's comment here: https://news.ycombinator.com/item?id=26244021 https://news.ycombinator.com/item?id=26244021 So Norvig's PAIP may be the book where I saw it. Edit 2: Also just saw gglitch's comment: https://news.ycombinator.com/item?id=26242603 https://news.ycombinator.com/item?id=26242603 which confirms my first surmise about both the PG and Norvig books containing it.