Hacker News Reader

Comment by emmanueloga_ | Hacker News Reader

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

2: http://www.buildyourownlisp.com/

View on HN

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

[2] https://www.cse.unt.edu/~tarau/research/2017/eng.pdf

[3] https://www.t3x.org/bits/prolog6.html 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

http://www.cl.cam.ac.uk/~am21/research/funnel/prolog.c

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/...) 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

You could study core.logic: 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

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

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/chapter...

There's also Implementations of Prolog: https://archive.org/details/implementationso0000unse (limited preview)

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.

It's not exactly what you're asking for, but there is "Racklog: Prolog-Style Logic Programming" 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.

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

which confirms my first surmise about both the PG and Norvig books containing it.

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

There is The Reasoned Schemer.

https://www.amazon.com/Reasoned-Schemer-MIT-Press/dp/0262535...

I skimming through it. I wonder if people prefer this or kanren over good old prolog.

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.

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.

The relevant section of PAIP: 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).

The PAIP implementation seems more practical than the other textbook Prologs I've seen like SICP's, while still quite small and clear.

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.

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

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.

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.

Reply on news.ycombinator.com