4 ms·

Something I would like to be able to understand/know/study is how logic programming languages are implemented and how their runtime looks like.

c-cube 10y ago
you can start by looking for "warren abstract machine" (usually shortened as WAM). It's an intermediate format for compiling prolog programs (sets of Horn clauses, that is, rules). It makes every operation very explicit, including unification (to match the current goal against each rule's conclusion) and backtracking (to enumerate solutions; this involves stacks, unsurprisingly). I think most state of the art prolog implementations are then able to compile this format to native code. Of course prolog also requires that the runtime has a GC (to collect dead terms) and that it can dynamically add/remove rules, use reflection to observe the shape of a term, etc. https://en.wikipedia.org/wiki/XSB https://en.wikipedia.org/wiki/XSB is an implementation to which Warren contributes, with additional features such as tabling (a powerful form of memoization that avoids many infinite recursions).
hyperion2010 10y ago
http://www.amzi.com/articles/prolog_under_the_hood.htm http://www.amzi.com/articles/prolog_under_the_hood.htm I find this article very helpful when it comes to understanding how Prolog actually works.
- smarx007 10y ago
  http://archive.is/RSzu http://archive.is/RSzu
pg314 10y ago
Section 4.4 in Structure and Implementation of Computer Programs [1] presents an implementation of a Prolog-like logic programming language in Scheme. It is very instructive to contrast it to the meta-circular evaluator of Scheme in that same book to see the similarities and differences. Paradigms of Artificial Programming by Norvig also contains a chapter implementing Prolog in Common Lisp. The code can be found at [2]. [1] https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-29.html#%_sec_4.4 https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-29.htm... [2] http://norvig.com/paip/prolog.lisp http://norvig.com/paip/prolog.lisp
- exDM69 10y ago
  Here [0] is a video link to SICP lecture 8A about Logic Programming, which accompanies the section 4.4. It's an excellent lecture! [0] https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/video-lectures/8a-logic-programming-part-1/ https://ocw.mit.edu/courses/electrical-engineering-and-compu...
abhirag 10y ago
You should have a look at https://mitpress.mit.edu/books/reasoned-schemer https://mitpress.mit.edu/books/reasoned-schemer

c-cube 10y ago

you can start by looking for "warren abstract machine" (usually shortened as WAM). It's an intermediate format for compiling prolog programs (sets of Horn clauses, that is, rules). It makes every operation very explicit, including unification (to match the current goal against each rule's conclusion) and backtracking (to enumerate solutions; this involves stacks, unsurprisingly). I think most state of the art prolog implementations are then able to compile this format to native code. Of course prolog also requires that the runtime has a GC (to collect dead terms) and that it can dynamically add/remove rules, use reflection to observe the shape of a term, etc. https://en.wikipedia.org/wiki/XSB https://en.wikipedia.org/wiki/XSB is an implementation to which Warren contributes, with additional features such as tabling (a powerful form of memoization that avoids many infinite recursions).

hyperion2010 10y ago

http://www.amzi.com/articles/prolog_under_the_hood.htm http://www.amzi.com/articles/prolog_under_the_hood.htm I find this article very helpful when it comes to understanding how Prolog actually works.

smarx007 10y ago
http://archive.is/RSzu http://archive.is/RSzu

pg314 10y ago

Section 4.4 in Structure and Implementation of Computer Programs [1] presents an implementation of a Prolog-like logic programming language in Scheme. It is very instructive to contrast it to the meta-circular evaluator of Scheme in that same book to see the similarities and differences. Paradigms of Artificial Programming by Norvig also contains a chapter implementing Prolog in Common Lisp. The code can be found at [2]. [1] https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-29.html#%_sec_4.4 https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-29.htm... [2] http://norvig.com/paip/prolog.lisp http://norvig.com/paip/prolog.lisp

exDM69 10y ago
Here [0] is a video link to SICP lecture 8A about Logic Programming, which accompanies the section 4.4. It's an excellent lecture! [0] https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/video-lectures/8a-logic-programming-part-1/ https://ocw.mit.edu/courses/electrical-engineering-and-compu...

abhirag 10y ago

You should have a look at https://mitpress.mit.edu/books/reasoned-schemer https://mitpress.mit.edu/books/reasoned-schemer