7 ms·

Thank you very much for the publicity, I greatly appreciate your interest! Prolog is extremely well-suited for solving combinatorial tasks like Sudoku puzzles,

by triska 7y ago

Thank you very much for the publicity, I greatly appreciate your interest! Prolog is extremely well-suited for solving combinatorial tasks like Sudoku puzzles, and also for tough practical challenges such such as timetabling, scheduling and allocation tasks on an industrial scale. The key feature that makes Prolog so efficient and frequently used for such tasks is constraint propagation, provided via libraries or as a built-in feature in many Prolog system. Fast and efficient constraint propagation is often an important reason for buying a commercial Prolog system. In this example, I am using CLP(FD/ℤ), constraint logic programming over finite domains/integers, the amalgamation of constraint programming (CP) and logic programming (LP), which blend especially seamlessly. I have uploaded a short video that shows how it works for Sudoku puzzles: https://www.metalevel.at/prolog/videos/sudoku https://www.metalevel.at/prolog/videos/sudoku If you are interested in constraint solving, a few related videos may also be useful: https://www.metalevel.at/prolog/videos/n_queens https://www.metalevel.at/prolog/videos/n_queens https://www.metalevel.at/prolog/videos/knights_and_knaves https://www.metalevel.at/prolog/videos/knights_and_knaves https://www.metalevel.at/prolog/videos/map_colouring https://www.metalevel.at/prolog/videos/map_colouring These videos are all work in progress, and they may be replaced by better versions at any time. However, the links above will always point to the latest version. Enjoy!

aidos 7y ago
I studied prolog years ago at university and more recently rediscovered the power of solvers (like SCIP). Is not really thought about how the 2 crossed over before. How does prolog compare to a solver these days?
- triska 7y ago
  The primary attraction of CLP, i.e., the combination of constraint programming (CP) and logic programming (LP), is that you get a full-blown programming language (most frequently: Prolog) and in addition seamlessly integrated solvers (over integers, rational numbers, Herbrand terms etc.). CP can of course be hosted on — or provided as library for — other languages too. However, it blends in most seamlessly with a logic programming language like Prolog as its host language. Regarding efficiency, the top-of-the-line Prolog systems provide many of the most efficient and most sophisticated algorithms for combinatorial optimization tasks that are commercially used. See for example the customers page of SICStus Prolog for several interesting applications: https://sicstus.sics.se/customers.html https://sicstus.sics.se/customers.html
  - nmadden 7y ago
    CLP shares some similarity with Satisfiability Modulo Theories (SMT). Is there much overlap in how they are used in practice? When would you reach for SMT over CLP?
SilasX 7y ago
I'm not sure if this is a well-formed question, but ... how does this approach compare to solving such problems with general SAT-solvers? Don't the latter allow you to use techniques that search the space more efficiently? Or is it hot-swappable in some sense? Could you take Prolog and have it solve a CP problem with a SAT solver doing the work under the hood?
- triska 7y ago
  The question is perfectly well-formed! It is, however, very broad, and I try to answer it very broadly. First, SAT solvers are powerful and efficient. SAT is one of the most studied problems in CS, both from a theoretical and practical perspective. Donald Knuth dedicates a huge portion of The Art of Computer Programming to exactly this topic. For example, quoting from https://www-cs-faculty.stanford.edu/~knuth/news.html https://www-cs-faculty.stanford.edu/~knuth/news.html: Satisfiability is far from an abstract exercise in understanding formal systems. Revolutionary methods for solving such problems emerged at the beginning of the twenty-first century, and they've led to game-changing applications in industry. These so-called “SAT solvers” can now routinely find solutions to practical problems that involve millions of variables and were thought until very recently to be hopelessly difficult. I highly recommend this as a profound treatment of the subject for readers at all levels of expertise. Second, SAT solvers can be combined seamlessly with Prolog. In Prolog terminology, SAT is CLP(B), constraint logic programming over Boolean variables. From the perspective of a Prolog application programmer, you simply state what must hold about the variables, using Prolog predicates like conjunction, disjunction etc., you state which variables must be 1 and which must be 0 etc. Internally, a Prolog system may invoke an external SAT solver, or implement its own version of SAT solving, to find a satisfying assignment. Both approaches exist in the literature and in practice. For example, see A Pearl on SAT Solving in Prolog by Jacob M. Howe and Andy King: http://www.staff.city.ac.uk/~jacob/solver/ http://www.staff.city.ac.uk/~jacob/solver/ As another approach and reference, I have put together a small page about a different CLP(B) system that internally uses Binary Decision Diagrams (BDDs) to solve SAT instances: https://www.metalevel.at/clpb/ https://www.metalevel.at/clpb/ Third and finally, SAT is a comparatively low-level approach for expressing combinatorial tasks. Perfectly doable (for example, by automatic translation/compilation to SAT), but still low-level. That does not mean that it's inadequate. In fact, some aspects of the "true structure" of a problem may reveal themselves and allow an efficient solution only at that low level. It is perfectly possible to express Sudoku as a SAT problem, using CLP(B). For example: sudoku(Rows) :- length(Rows, 9), maplist(same_length(Rows), Rows), maplist(row_booleans, Rows, BRows), maplist(booleans_distinct, BRows), transpose(BRows, BColumns), maplist(booleans_distinct, BColumns), BRows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is], blocks(As, Bs, Cs), blocks(Ds, Es, Fs), blocks(Gs, Hs, Is). blocks([], [], []). blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :- booleans_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]), blocks(Ns1, Ns2, Ns3). booleans_distinct(Bs) :- transpose(Bs, Ts), maplist(card1, Ts). card1(Bs) :- sat(card([1],Bs)). row_booleans(Row, Bs) :- same_length(Row, Bs), maplist(cell_boolean, Row, Bs). cell_boolean(Num, Bs) :- length(Bs, 9), sat(card([1],Bs)), element(Num, Bs, 1). But the general point remains: Working - for example - with integers or Herbrand terms, or rational numbers etc., is more high-level and a more natural fit for many combinatorial tasks of practical relevance, and often allows also more efficient and more complete propagation, because more of the high-level structure of a task can be taken into account.
deleted 7y ago
[deleted]
bcrosby95 7y ago
I've toyed with trying to use Prolog for procedural map generation in my hobby RPG game. The idea is to feed it a high level human designed map and let it fill in the details. Not sure if you have any thoughts on if it might be suitable for something like that or not.
- triska 7y ago
  In general, Prolog is extremely well suited for tasks where partial information needs to be taken into account. The presence of logic variables, i.e., "true" variables in the sense of logic, is one of the defining characteristics of logic programming languages like Prolog. In comparison, what other programming languages call a "variable", is not really a variable but just some concrete value. In contrast, a logic variable truly stands for anything at all and may be bound to any term (in its domain). For this reason, Prolog is especially well suited for data that has "holes" in it. For example, Prolog was successfully used to investigate the folding structure of DNA, where hypotheses were available about some aspects, but the overall structure of parts was yet unknown. A Prolog specification allows to "leave out" parts of the specification that are unknown. Hence, a map generation task where some constraints are specified sounds like a very nice project and potentially great application for a logic programming language. Enjoy!
  - hjek 7y ago
    It's interesting how Prolog has no concept of 'null' as such; just fresh variables whose value we don't know (yet). No more null pointer exceptions!
    - harperlee 7y ago
      In fact, in some domains (such as SQL), ‘null’ stands for values we dont know: https://modern-sql.com/concept/three-valued-logic https://modern-sql.com/concept/three-valued-logic
      - hjek 7y ago
        Yes, looks like SQL got that right as well. I think Prolog is the answer to the question: What if the full stack was relational; not just the database?
hjek 7y ago
I've truly enjoyed all the Prolog videos on your channel[0]. I had to program a timetabling system where each event had a specific set of requirements, and your article and video about solving sudokus and the n-queens helped me grasp the problem. I have only been using Prolog for a month, but I could not go back to Lisp now (at least not without MiniKanren). There's still plenty of stuff I don't understand about Prolog, but it feels very expressive and powerful even with just a superficial understanding of the language. Thank you so much for your work! Your teaching materials are very accessible for beginners. Hope you will one day make a video about DCGs (Definite Clause Grammars). I wonder if reading Noam Chomsky will help my understanding of them? Since we are on Hacker News, I think it's interesting to look at PG's experience with Prolog, which unfortunately hasn't been as rewarding as mine: > There are features, most notably Prolog-style pattern-matching, that seem to promise great savings in length, but turn out only to be useful for writing a few basic sequence operations like append, remove, and so on. Prolog is a great language for writing append; after that it's all downhill.[1] > A way of expressing programs that was more abstract, but made your programs longer, would not be very enticing. (This is not just a hypothetical example. It happens in Prolog.)[2] From watching your videos, it's easy to see how concise Prolog programs are though. I find that my own Prolog programs also tend to be extremely brief (compared to Lisp or SQL). [0]: https://invidio.us/channel/UCFFeNyzCEQDS4KCecugmotg https://invidio.us/channel/UCFFeNyzCEQDS4KCecugmotg [1]: http://www.paulgraham.com/arcchallenge.html http://www.paulgraham.com/arcchallenge.html [2]: http://www.paulgraham.com/arcll1.html http://www.paulgraham.com/arcll1.html
- triska 7y ago
  Thank you very much for your kind words! I greatly appreciate your feedback, and I am very glad that you benefit from the videos! Also, I would like to take this opportunity to thank you all collectively for your thoughtful participation in this thread, your comments and endorsements. Your feedback, encouragement and insights are making this work especially worthwhile!
- abecedarius 7y ago
  > more abstract, but made your programs longer There are a few main reasons for Prolog code to come out longer than Lisp: - Prolog style is mostly first order -- there's not a direct equivalent of lambda. - Mutation is also used less. - There's an equivalent of Lisp macros, but it's also less common. - You don't nest function calls, but pass common named arguments instead. So I can see where he was coming from. On the other hand I'd guess he had his Prolog experience before constraint logic programming was well supported, and certainly before MiniKanren which gives back the conveniences of Lisp and helps you take the pure-declarative subset further.
new4thaccount 7y ago
Thanks for your hard work. I really want to like Prolog, but I often don't know how to fit it into an actual system of use. My field is power systems which involves solving numerical problems with large sparse matrices and very large scale optimization problems (millions of constraints) using LP and MIP solvers. The first class of problems can be easily solved with tools like Matlab, Fortran, Python, Julia, C++...etc. The optimization problems can be solved with any language that has a library to talk to a solver. Prolog is really cool, but I doubt it could solve problems of that size even if given days, much less a few minutes. I'd love to be proven wrong, but it seems like it really excels at these small toy problems. Could you enlighten my ignorance on how it can be used on larger scale problems? Thanks in advance!
- hjek 7y ago
  I haven't used Prolog at that scale myself, but I'll just add completely unsubstantiated hearsay from the ##Prolog IRC on FreeNode: Someone reported no problems using SWI Prolog for running queries on "59 million facts". It might also be worth checking Triska's video about n-queens[0] where the last 2/3 is all about optimising the search and using different labelling strategies. Don't know if it's relevant for your problem, but memoization is also a thing in Prolog[1] like in other languages. Maybe not the answer you're looking for. Is your system relatively simple to describe? Then we can give it a try... [0]: https://invidio.us/watch?v=l_tbL9RjFdo https://invidio.us/watch?v=l_tbL9RjFdo [1]: https://swish.swi-prolog.org/example/tabling.swinb https://swish.swi-prolog.org/example/tabling.swinb
  - new4thaccount 7y ago
    59M sounds pretty sweet! I'll check out Triska's videos when I pick up my Prolog book on writing a text adventure again. It's pretty much the only Prolog book that helps walk me through it without the theory. I do like theory, but I need a high level overview first before I can make sense of anything. The basics of the system are very easy to describe, but realistic system implementations are waaay more complex and have hundreds of pages of solver code and SQL packages. A very simple example on a tiny system would be the below: https://www.juliaopt.org/notebooks/Dvorkin%20-%20Power%20systems%20-%20Economic%20dispatch%20and%20Unit%20commitment.html https://www.juliaopt.org/notebooks/Dvorkin%20-%20Power%20sys...

by triska 7y ago

aidos 7y ago

I studied prolog years ago at university and more recently rediscovered the power of solvers (like SCIP). Is not really thought about how the 2 crossed over before. How does prolog compare to a solver these days?

triska 7y ago
The primary attraction of CLP, i.e., the combination of constraint programming (CP) and logic programming (LP), is that you get a full-blown programming language (most frequently: Prolog) and in addition seamlessly integrated solvers (over integers, rational numbers, Herbrand terms etc.). CP can of course be hosted on — or provided as library for — other languages too. However, it blends in most seamlessly with a logic programming language like Prolog as its host language. Regarding efficiency, the top-of-the-line Prolog systems provide many of the most efficient and most sophisticated algorithms for combinatorial optimization tasks that are commercially used. See for example the customers page of SICStus Prolog for several interesting applications: https://sicstus.sics.se/customers.html https://sicstus.sics.se/customers.html
- nmadden 7y ago
  CLP shares some similarity with Satisfiability Modulo Theories (SMT). Is there much overlap in how they are used in practice? When would you reach for SMT over CLP?

SilasX 7y ago

I'm not sure if this is a well-formed question, but ... how does this approach compare to solving such problems with general SAT-solvers? Don't the latter allow you to use techniques that search the space more efficiently? Or is it hot-swappable in some sense? Could you take Prolog and have it solve a CP problem with a SAT solver doing the work under the hood?

triska 7y ago
The question is perfectly well-formed! It is, however, very broad, and I try to answer it very broadly. First, SAT solvers are powerful and efficient. SAT is one of the most studied problems in CS, both from a theoretical and practical perspective. Donald Knuth dedicates a huge portion of The Art of Computer Programming to exactly this topic. For example, quoting from https://www-cs-faculty.stanford.edu/~knuth/news.html https://www-cs-faculty.stanford.edu/~knuth/news.html: Satisfiability is far from an abstract exercise in understanding formal systems. Revolutionary methods for solving such problems emerged at the beginning of the twenty-first century, and they've led to game-changing applications in industry. These so-called “SAT solvers” can now routinely find solutions to practical problems that involve millions of variables and were thought until very recently to be hopelessly difficult. I highly recommend this as a profound treatment of the subject for readers at all levels of expertise. Second, SAT solvers can be combined seamlessly with Prolog. In Prolog terminology, SAT is CLP(B), constraint logic programming over Boolean variables. From the perspective of a Prolog application programmer, you simply state what must hold about the variables, using Prolog predicates like conjunction, disjunction etc., you state which variables must be 1 and which must be 0 etc. Internally, a Prolog system may invoke an external SAT solver, or implement its own version of SAT solving, to find a satisfying assignment. Both approaches exist in the literature and in practice. For example, see A Pearl on SAT Solving in Prolog by Jacob M. Howe and Andy King: http://www.staff.city.ac.uk/~jacob/solver/ http://www.staff.city.ac.uk/~jacob/solver/ As another approach and reference, I have put together a small page about a different CLP(B) system that internally uses Binary Decision Diagrams (BDDs) to solve SAT instances: https://www.metalevel.at/clpb/ https://www.metalevel.at/clpb/ Third and finally, SAT is a comparatively low-level approach for expressing combinatorial tasks. Perfectly doable (for example, by automatic translation/compilation to SAT), but still low-level. That does not mean that it's inadequate. In fact, some aspects of the "true structure" of a problem may reveal themselves and allow an efficient solution only at that low level. It is perfectly possible to express Sudoku as a SAT problem, using CLP(B). For example: sudoku(Rows) :- length(Rows, 9), maplist(same_length(Rows), Rows), maplist(row_booleans, Rows, BRows), maplist(booleans_distinct, BRows), transpose(BRows, BColumns), maplist(booleans_distinct, BColumns), BRows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is], blocks(As, Bs, Cs), blocks(Ds, Es, Fs), blocks(Gs, Hs, Is). blocks([], [], []). blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :- booleans_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]), blocks(Ns1, Ns2, Ns3). booleans_distinct(Bs) :- transpose(Bs, Ts), maplist(card1, Ts). card1(Bs) :- sat(card([1],Bs)). row_booleans(Row, Bs) :- same_length(Row, Bs), maplist(cell_boolean, Row, Bs). cell_boolean(Num, Bs) :- length(Bs, 9), sat(card([1],Bs)), element(Num, Bs, 1). But the general point remains: Working - for example - with integers or Herbrand terms, or rational numbers etc., is more high-level and a more natural fit for many combinatorial tasks of practical relevance, and often allows also more efficient and more complete propagation, because more of the high-level structure of a task can be taken into account.

deleted 7y ago

[deleted]

bcrosby95 7y ago

I've toyed with trying to use Prolog for procedural map generation in my hobby RPG game. The idea is to feed it a high level human designed map and let it fill in the details. Not sure if you have any thoughts on if it might be suitable for something like that or not.

triska 7y ago
In general, Prolog is extremely well suited for tasks where partial information needs to be taken into account. The presence of logic variables, i.e., "true" variables in the sense of logic, is one of the defining characteristics of logic programming languages like Prolog. In comparison, what other programming languages call a "variable", is not really a variable but just some concrete value. In contrast, a logic variable truly stands for anything at all and may be bound to any term (in its domain). For this reason, Prolog is especially well suited for data that has "holes" in it. For example, Prolog was successfully used to investigate the folding structure of DNA, where hypotheses were available about some aspects, but the overall structure of parts was yet unknown. A Prolog specification allows to "leave out" parts of the specification that are unknown. Hence, a map generation task where some constraints are specified sounds like a very nice project and potentially great application for a logic programming language. Enjoy!
- hjek 7y ago
  It's interesting how Prolog has no concept of 'null' as such; just fresh variables whose value we don't know (yet). No more null pointer exceptions!
  - harperlee 7y ago
    In fact, in some domains (such as SQL), ‘null’ stands for values we dont know: https://modern-sql.com/concept/three-valued-logic https://modern-sql.com/concept/three-valued-logic
    - hjek 7y ago
      Yes, looks like SQL got that right as well. I think Prolog is the answer to the question: What if the full stack was relational; not just the database?

hjek 7y ago

I've truly enjoyed all the Prolog videos on your channel[0]. I had to program a timetabling system where each event had a specific set of requirements, and your article and video about solving sudokus and the n-queens helped me grasp the problem. I have only been using Prolog for a month, but I could not go back to Lisp now (at least not without MiniKanren). There's still plenty of stuff I don't understand about Prolog, but it feels very expressive and powerful even with just a superficial understanding of the language. Thank you so much for your work! Your teaching materials are very accessible for beginners. Hope you will one day make a video about DCGs (Definite Clause Grammars). I wonder if reading Noam Chomsky will help my understanding of them? Since we are on Hacker News, I think it's interesting to look at PG's experience with Prolog, which unfortunately hasn't been as rewarding as mine: > There are features, most notably Prolog-style pattern-matching, that seem to promise great savings in length, but turn out only to be useful for writing a few basic sequence operations like append, remove, and so on. Prolog is a great language for writing append; after that it's all downhill.[1] > A way of expressing programs that was more abstract, but made your programs longer, would not be very enticing. (This is not just a hypothetical example. It happens in Prolog.)[2] From watching your videos, it's easy to see how concise Prolog programs are though. I find that my own Prolog programs also tend to be extremely brief (compared to Lisp or SQL). [0]: https://invidio.us/channel/UCFFeNyzCEQDS4KCecugmotg https://invidio.us/channel/UCFFeNyzCEQDS4KCecugmotg [1]: http://www.paulgraham.com/arcchallenge.html http://www.paulgraham.com/arcchallenge.html [2]: http://www.paulgraham.com/arcll1.html http://www.paulgraham.com/arcll1.html

triska 7y ago
Thank you very much for your kind words! I greatly appreciate your feedback, and I am very glad that you benefit from the videos! Also, I would like to take this opportunity to thank you all collectively for your thoughtful participation in this thread, your comments and endorsements. Your feedback, encouragement and insights are making this work especially worthwhile!
abecedarius 7y ago
> more abstract, but made your programs longer There are a few main reasons for Prolog code to come out longer than Lisp: - Prolog style is mostly first order -- there's not a direct equivalent of lambda. - Mutation is also used less. - There's an equivalent of Lisp macros, but it's also less common. - You don't nest function calls, but pass common named arguments instead. So I can see where he was coming from. On the other hand I'd guess he had his Prolog experience before constraint logic programming was well supported, and certainly before MiniKanren which gives back the conveniences of Lisp and helps you take the pure-declarative subset further.

new4thaccount 7y ago

Thanks for your hard work. I really want to like Prolog, but I often don't know how to fit it into an actual system of use. My field is power systems which involves solving numerical problems with large sparse matrices and very large scale optimization problems (millions of constraints) using LP and MIP solvers. The first class of problems can be easily solved with tools like Matlab, Fortran, Python, Julia, C++...etc. The optimization problems can be solved with any language that has a library to talk to a solver. Prolog is really cool, but I doubt it could solve problems of that size even if given days, much less a few minutes. I'd love to be proven wrong, but it seems like it really excels at these small toy problems. Could you enlighten my ignorance on how it can be used on larger scale problems? Thanks in advance!

hjek 7y ago
I haven't used Prolog at that scale myself, but I'll just add completely unsubstantiated hearsay from the ##Prolog IRC on FreeNode: Someone reported no problems using SWI Prolog for running queries on "59 million facts". It might also be worth checking Triska's video about n-queens[0] where the last 2/3 is all about optimising the search and using different labelling strategies. Don't know if it's relevant for your problem, but memoization is also a thing in Prolog[1] like in other languages. Maybe not the answer you're looking for. Is your system relatively simple to describe? Then we can give it a try... [0]: https://invidio.us/watch?v=l_tbL9RjFdo https://invidio.us/watch?v=l_tbL9RjFdo [1]: https://swish.swi-prolog.org/example/tabling.swinb https://swish.swi-prolog.org/example/tabling.swinb
- new4thaccount 7y ago
  59M sounds pretty sweet! I'll check out Triska's videos when I pick up my Prolog book on writing a text adventure again. It's pretty much the only Prolog book that helps walk me through it without the theory. I do like theory, but I need a high level overview first before I can make sense of anything. The basics of the system are very easy to describe, but realistic system implementations are waaay more complex and have hundreds of pages of solver code and SQL packages. A very simple example on a tiny system would be the below: https://www.juliaopt.org/notebooks/Dvorkin%20-%20Power%20systems%20-%20Economic%20dispatch%20and%20Unit%20commitment.html https://www.juliaopt.org/notebooks/Dvorkin%20-%20Power%20sys...