5 ms·

Prolog really blows my mind. I recently released a match-burning logic puzzle app[1] based on a mensa calendar puzzle I saw and it took me a while to develop a

by umvi 7y ago

Prolog really blows my mind. I recently released a match-burning logic puzzle app[1] based on a mensa calendar puzzle I saw and it took me a while to develop an (imperfect) solver algorithm in C#. Someone then told me that the general class of these puzzles is called "Thermometer Puzzles" and that there are a ton of Prolog-based solvers[2] out there. This class of puzzle is not mentioned in the article, but I'm truly amazed at how versatile Prolog is at solving logic puzzles with so little code. I'm guessing the Prolog compiler is super complex compared to, say, a C compiler to be able to give developers that much power. [1] https://play.google.com/store/apps/details?id=com.umvirate.embergram https://play.google.com/store/apps/details?id=com.umvirate.e... [2] https://github.com/zettca/ist.lp.thermometers/blob/master/thermometers.pl https://github.com/zettca/ist.lp.thermometers/blob/master/th...

derefr 7y ago
> I'm guessing the Prolog compiler is super complex compared to, say, a C compiler to be able to give developers that much power. Nah. Both Prolog and C do a very similar step: they walk through call-sites and function signatures in your code and check them for compatibility with each-other in a way that can constrain both the call and the function, or they fail to make a match and they rewind and try again with other constraints. The only difference is that C is only doing this unification for the types of the parameters, whereas Prolog is doing it for the parameter values. Any programming language that has static types but also has an “auto” variable type, where the type is deduced from the use-def and def-use chains that statement live in, is doing absolutely everything Prolog does, and just not exposing the power of it to you. (Hindley-Milner is an even more advanced constraint-solver than Prolog is.) (Though, to be clear, if you can program in the type system, as you can in C++, then you do get an exposure to that power, and can write many backtracking algorithms with it.)
- YeGoblynQueenne 7y ago
  If I understand correctly, Hindley-Milner type inference performs unification but not resolution. So I don't think the above is correct. I don't think there's any language that has built-in SLD-resolution theorem proving that isn't a logic programming language. And Prolog is not really a constraint solver. Constraint Logic Programming languages have been implemented in Prolog but the concept of "constraint" is not built-in to Prolog.
  - dreamcompiler 7y ago
    Prolog has constraints but they're limited to "equality" for some notion of that word. Constraint solvers and constraint extensions to Prolog broaden that considerably.
    - YeGoblynQueenne 7y ago
      Do you mean the equality predicates, like ==/2 or =:=/2 etc, or do you mean unification? I dont' really think of unification as a constraint but, I don't know, maybe you have a point.
      - dreamcompiler 7y ago
        Yes I was talking about unification. When you can expand what unification means and program how it works, you have a real constraint system.
- tom_mellior 7y ago
  > Nah. Both Prolog and C do a very similar step: they walk through call-sites and function signatures in your code and check them for compatibility with each-other in a way that can constrain both the call and the function, C type checking does not "constrain the call and the function". It looks at existing, fixed types (not constraints on types) and fails or succeeds. I may be misunderstanding you, can you explain in more depth what you mean? > or they fail to make a match and they rewind and try again with other constraints. I don't think C compilers ever backtrack during type checking. Again, maybe I'm misunderstanding what you mean? > The only difference is that C is only doing this unification for the types of the parameters, whereas Prolog is doing it for the parameter values. Other big differences include the fact that the C compiler does this at compile time as a preparation for execution, while in Prolog this is most of execution; the fact that Prolog has logic variables; the fact that Prolog has arbitrary nested structures that can be unified; the fact noted above that Prolog does backtracking; and, in general, the big difference that Prolog is nothing like C at all. > Any programming language that has static types but also has an “auto” variable type, where the type is deduced from the use-def and def-use chains that statement live in, is doing absolutely everything Prolog does, and just not exposing the power of it to you. (Hindley-Milner is an even more advanced constraint-solver than Prolog is.) AFAIK plain Hindley-Milner does only unification but not backtracking, so I would call it strictly less powerful than Prolog. If we assume a backtracking version of Hindley-Milner, we might call it equally powerful to Prolog. I don't see at all how you can claim that it's "more advanced" than Prolog, though. > (Though, to be clear, if you can program in the type system, as you can in C++, then you do get an exposure to that power, and can write many backtracking algorithms with it.) I don't know enough about the intricacies of C++ template metaprogramming, but I'm not under the impression that it exposes backtracking as a primitive the way that Prolog does. (Modulo the trivial observation that C++ templates are known to be Turing complete, so you should be able to implement your own backtracking in them.)
DannyB2 7y ago
If you want to know how to build a Prolog . . . When I learned Common Lisp, I devoured the available textbooks in 1989 and for a few years after. A book from the early 1990s is: Paradigms of AI Programming: Case Studies in Common Lisp. By Peter Norvig (now employed by Google) The book first teaches you Common Lisp, which isn't that difficult to pick up. But that itself is a transformative experience. Then the book shows you how to build a number of amazing things using Common Lisp. It starts IIRC, with pattern matching. Term rewriting. Unification matching. Then you proceed to build a few things like: 1. A program that solves high school style algebra word problems. 2. A "prolog" (but expressed in Lisp syntax) that is a "hair's breadth" (in the author's words) from real prolog. This book was mind blowing. A revelation. Insightful. Learning Lisp (even from other textbooks before the one I mention here) was a transformative experience. But this single book stands out in providing so many amazing ideas expressed in Lisp. Other Lisp texts I had read taught me things like playing two-player zero sum games (TicTacToe, Checkers, Reversi). I abstracted the technique to have a single re-usable AI engine implementing the Minimax with Alpha-Beta pruning, and then different layers on top of that which implemented different games (as listed earlier) by defining a game board, move generator and board scoring function. One Lisp textbook I had from the late 1980s showed a program to plan movements of a robot arm to manipulate blocks according to english like commands. All of these amazingly sophisticated things take up very little Lisp code. Often only a few pages. The journey of learning Lisp, with a really good textbook, is an amazing learning experience. Learning Lisp will change the way you think about code for the rest of your entire life. I can confidently say that having learned Lisp starting in about 1986 and dabbling with it through 1993. The initial learning comes quickly. But you will play with this new toy for a long time. Another book (The Elements of Artificial Intelligence Using Common Lisp) introduced me to the A-star search. I've used that technique, in Java, to build a "solver" for a game sometimes called "Traffic Jam" or "Unblock Me".
- tsuru 7y ago
  The first book, commonly referred to by its acronym PAIP, is available online for free from the author: https://github.com/norvig/paip-lisp https://github.com/norvig/paip-lisp I think there is ongoing effort to update it for better accessibility.
mthom 7y ago
> I'm guessing the Prolog compiler is super complex compared to, say, a C compiler to be able to give developers that much power. They're not that complex. I'm writing one from scratch right now: http://github.com/mthom/scryer-prolog http://github.com/mthom/scryer-prolog Speaking of constraint solvers, the author of Power of Prolog, Markus Triska, is now in the process of porting his clp(ℤ) constraint solver over to my system, having already ported his boolean constraint solver, clp(B). They are quite complex, but it helps that they're written entirely in Prolog.
- carapace 7y ago
  FWIW, there's this paper that "[takes] a fresh, 'clean-room' look at implementing Prolog by deriving its translation to an executable representation and its execution algorithm from a simple Horn Clause meta-interpreter." "A Hitchhiker’s Guide to Reinventing a Prolog Machine" Paul Tarau https://www.cse.unt.edu/~tarau/research/2017/eng.pdf https://www.cse.unt.edu/~tarau/research/2017/eng.pdf Slides: https://software.imdea.org/Conferences/CICLOPS2017/files/tarau_ciclops17.pdf https://software.imdea.org/Conferences/CICLOPS2017/files/tar...
  - mthom 7y ago
    Thanks!
ggggtez 7y ago
Prolog is just a glorified depth first search. Seriously it's not magic.
- jodrellblank 7y ago
  tbh it was a lot more fun when I thought it was magic.
  - DannyB2 7y ago
    Learning the magician's trick always results in the disappointing feeling: oh, so that's all there is to it.
avmich 7y ago
Norvig constructs a version of Prolog in his book - https://github.com/norvig/paip-lisp https://github.com/norvig/paip-lisp , see ch.11 Here - https://github.com/prolog8/awkprolog https://github.com/prolog8/awkprolog - is an interesting example of Prolog written in AWK. Not too long and neither too dense code.

by umvi 7y ago

derefr 7y ago

> I'm guessing the Prolog compiler is super complex compared to, say, a C compiler to be able to give developers that much power. Nah. Both Prolog and C do a very similar step: they walk through call-sites and function signatures in your code and check them for compatibility with each-other in a way that can constrain both the call and the function, or they fail to make a match and they rewind and try again with other constraints. The only difference is that C is only doing this unification for the types of the parameters, whereas Prolog is doing it for the parameter values. Any programming language that has static types but also has an “auto” variable type, where the type is deduced from the use-def and def-use chains that statement live in, is doing absolutely everything Prolog does, and just not exposing the power of it to you. (Hindley-Milner is an even more advanced constraint-solver than Prolog is.) (Though, to be clear, if you can program in the type system, as you can in C++, then you do get an exposure to that power, and can write many backtracking algorithms with it.)

YeGoblynQueenne 7y ago
If I understand correctly, Hindley-Milner type inference performs unification but not resolution. So I don't think the above is correct. I don't think there's any language that has built-in SLD-resolution theorem proving that isn't a logic programming language. And Prolog is not really a constraint solver. Constraint Logic Programming languages have been implemented in Prolog but the concept of "constraint" is not built-in to Prolog.
- dreamcompiler 7y ago
  Prolog has constraints but they're limited to "equality" for some notion of that word. Constraint solvers and constraint extensions to Prolog broaden that considerably.
  - YeGoblynQueenne 7y ago
    Do you mean the equality predicates, like ==/2 or =:=/2 etc, or do you mean unification? I dont' really think of unification as a constraint but, I don't know, maybe you have a point.
    - dreamcompiler 7y ago
      Yes I was talking about unification. When you can expand what unification means and program how it works, you have a real constraint system.
tom_mellior 7y ago
> Nah. Both Prolog and C do a very similar step: they walk through call-sites and function signatures in your code and check them for compatibility with each-other in a way that can constrain both the call and the function, C type checking does not "constrain the call and the function". It looks at existing, fixed types (not constraints on types) and fails or succeeds. I may be misunderstanding you, can you explain in more depth what you mean? > or they fail to make a match and they rewind and try again with other constraints. I don't think C compilers ever backtrack during type checking. Again, maybe I'm misunderstanding what you mean? > The only difference is that C is only doing this unification for the types of the parameters, whereas Prolog is doing it for the parameter values. Other big differences include the fact that the C compiler does this at compile time as a preparation for execution, while in Prolog this is most of execution; the fact that Prolog has logic variables; the fact that Prolog has arbitrary nested structures that can be unified; the fact noted above that Prolog does backtracking; and, in general, the big difference that Prolog is nothing like C at all. > Any programming language that has static types but also has an “auto” variable type, where the type is deduced from the use-def and def-use chains that statement live in, is doing absolutely everything Prolog does, and just not exposing the power of it to you. (Hindley-Milner is an even more advanced constraint-solver than Prolog is.) AFAIK plain Hindley-Milner does only unification but not backtracking, so I would call it strictly less powerful than Prolog. If we assume a backtracking version of Hindley-Milner, we might call it equally powerful to Prolog. I don't see at all how you can claim that it's "more advanced" than Prolog, though. > (Though, to be clear, if you can program in the type system, as you can in C++, then you do get an exposure to that power, and can write many backtracking algorithms with it.) I don't know enough about the intricacies of C++ template metaprogramming, but I'm not under the impression that it exposes backtracking as a primitive the way that Prolog does. (Modulo the trivial observation that C++ templates are known to be Turing complete, so you should be able to implement your own backtracking in them.)

DannyB2 7y ago

If you want to know how to build a Prolog . . . When I learned Common Lisp, I devoured the available textbooks in 1989 and for a few years after. A book from the early 1990s is: Paradigms of AI Programming: Case Studies in Common Lisp. By Peter Norvig (now employed by Google) The book first teaches you Common Lisp, which isn't that difficult to pick up. But that itself is a transformative experience. Then the book shows you how to build a number of amazing things using Common Lisp. It starts IIRC, with pattern matching. Term rewriting. Unification matching. Then you proceed to build a few things like: 1. A program that solves high school style algebra word problems. 2. A "prolog" (but expressed in Lisp syntax) that is a "hair's breadth" (in the author's words) from real prolog. This book was mind blowing. A revelation. Insightful. Learning Lisp (even from other textbooks before the one I mention here) was a transformative experience. But this single book stands out in providing so many amazing ideas expressed in Lisp. Other Lisp texts I had read taught me things like playing two-player zero sum games (TicTacToe, Checkers, Reversi). I abstracted the technique to have a single re-usable AI engine implementing the Minimax with Alpha-Beta pruning, and then different layers on top of that which implemented different games (as listed earlier) by defining a game board, move generator and board scoring function. One Lisp textbook I had from the late 1980s showed a program to plan movements of a robot arm to manipulate blocks according to english like commands. All of these amazingly sophisticated things take up very little Lisp code. Often only a few pages. The journey of learning Lisp, with a really good textbook, is an amazing learning experience. Learning Lisp will change the way you think about code for the rest of your entire life. I can confidently say that having learned Lisp starting in about 1986 and dabbling with it through 1993. The initial learning comes quickly. But you will play with this new toy for a long time. Another book (The Elements of Artificial Intelligence Using Common Lisp) introduced me to the A-star search. I've used that technique, in Java, to build a "solver" for a game sometimes called "Traffic Jam" or "Unblock Me".

tsuru 7y ago
The first book, commonly referred to by its acronym PAIP, is available online for free from the author: https://github.com/norvig/paip-lisp https://github.com/norvig/paip-lisp I think there is ongoing effort to update it for better accessibility.

mthom 7y ago

> I'm guessing the Prolog compiler is super complex compared to, say, a C compiler to be able to give developers that much power. They're not that complex. I'm writing one from scratch right now: http://github.com/mthom/scryer-prolog http://github.com/mthom/scryer-prolog Speaking of constraint solvers, the author of Power of Prolog, Markus Triska, is now in the process of porting his clp(ℤ) constraint solver over to my system, having already ported his boolean constraint solver, clp(B). They are quite complex, but it helps that they're written entirely in Prolog.

carapace 7y ago
FWIW, there's this paper that "[takes] a fresh, 'clean-room' look at implementing Prolog by deriving its translation to an executable representation and its execution algorithm from a simple Horn Clause meta-interpreter." "A Hitchhiker’s Guide to Reinventing a Prolog Machine" Paul Tarau https://www.cse.unt.edu/~tarau/research/2017/eng.pdf https://www.cse.unt.edu/~tarau/research/2017/eng.pdf Slides: https://software.imdea.org/Conferences/CICLOPS2017/files/tarau_ciclops17.pdf https://software.imdea.org/Conferences/CICLOPS2017/files/tar...
- mthom 7y ago
  Thanks!

ggggtez 7y ago

Prolog is just a glorified depth first search. Seriously it's not magic.

jodrellblank 7y ago
tbh it was a lot more fun when I thought it was magic.
- DannyB2 7y ago
  Learning the magician's trick always results in the disappointing feeling: oh, so that's all there is to it.

avmich 7y ago

Norvig constructs a version of Prolog in his book - https://github.com/norvig/paip-lisp https://github.com/norvig/paip-lisp , see ch.11 Here - https://github.com/prolog8/awkprolog https://github.com/prolog8/awkprolog - is an interesting example of Prolog written in AWK. Not too long and neither too dense code.