11 ms·

Solving Sudoku with Prolog (2016)

179 points by hjek 7y ago

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...
ggggtez 7y ago
Prolog is good for discrete search like this, mostly because it's just hiding the underlying search algorithm that other languages would be to be explicit about (but as a result, other languages can search more efficiently).
- segmondy 7y ago
  All computer science problems can be reduced to sorting & searching. ;-D
  - randomsearch 7y ago
    Is this really true? I was wondering about complexity analysis, for example.
    - iamgopal 7y ago
      Search to sort, sort to search, don't use random search.
    - ggggtez 7y ago
      No it's not true. I think if you called multiplication a sorting algorithm it would be really dishonest.
- jodrellblank 7y ago
  Other languages can search more efficiently if you write a more efficient search in them, but Prolog can search more efficiently if you write a more efficient search in it, too. "That's it. On backtracking, this generates increasingly longer lists Ls, and invokes p/1 only on lists of bounded length. Bamm! Iterative deepening. [..] asymptotically optimal under very general assumptions, and you can make it easily available in Prolog yourself. I guess mostly for this reason, the default execution strategy is kept extremely simple. When needed, you can easily implement other search strategies on top of it." - https://www.reddit.com/r/prolog/comments/47fchf/why_depthfirst_for_resolution/ https://www.reddit.com/r/prolog/comments/47fchf/why_depthfir...
segmondy 7y ago
Solving Sudoku smartly with Prolog. The nice thing with Prolog is that if you don't understand how to program but you understand the rules/logic of the problem. In this case you understand the rules of Sudoku, you can define the board and the rules and Prolog will brute force it for you. Harder to do in other languages.
alexbanks 7y ago
This was a final project in a course I took in college surveying programming languages. I thought Prolog was insanely interesting. Through most of the project I thought it was crazy, but when I finished it made excellent sense. Since then I've thought a lot about using Prolog for optimized job/task scheduling, but I've never had an actual need to do it.
justkez 7y ago
I did a module in my undergrad degree that used Prolog as the learning tool/language. At the time I didn't understand why Prolog was such a different paradigm (declarative); all I remember is feeling a true sense of joy writing prolog code and running it. I've never found/made up a reason to try it out since then and no language/system/paradigm has given me the same enjoyment since!
protomyth 7y ago
I love the embedded PostScript in the source code. Its always fun to see how other people write their code.
- triska 7y ago
  Thank you for noting this! PostScript is currently underappreciated, and I highly recommend learning it. Among many other uses, I like to use PostScript as a portable animation language to visualize search processes like in this case. Also, programming PostScript is great fun and in a sense quite timeless: In all likelihood, these definitions will work without change also in the distant future, because PostScript is so widely spread and frequently used. Newer graphics languages and concepts also take many ideas from PostScript, but PostScript is in my experience still the most fun and flexible of them, at least for a very large set of important use cases.
bluetwo 7y ago
Curious about 2 things: 1) Can it solve especially hard Sudoku puzzles? (ie, expert level where humans often get stuck) 2) Is there a resource somewhere that lists the types of Prolog problems that it excels at solving?
- hjek 7y ago
  1) Yes, and (when there is only one unique solution) it can apparently be found in Prolog without doing an search at all by using constraint logic programming. Check the video in the sudoku article. 2) I'm not the best at answering this as I'm quite new to Prolog, but I'll try. I'd say a) anything you'd use a general purpose programming languge for, b) anything you'd use SQL for, and c) anything that's too difficult to do in either of those. SWI Prolog[0] has a large standard library and feels very "batteries included". Perhaps what I wouldn't use it for is mobile apps..? (But then again, there's Tau Prolog[1] which could probably work in a Cordova app). [0]: http://www.swi-prolog.org/ http://www.swi-prolog.org/ [1]: http://tau-prolog.org/ http://tau-prolog.org/
  - taeric 7y ago
    I'm curious on your first point. There are puzzles that have multiple legal plays but only a single solution. In those, guessing/searching is basically required, right?
    - triska 7y ago
      A valid Sudoku puzzle is such that the given clues admit precisely one solution. Hence, if you somehow manage to take into account all the initially available information, then no search is required, because, in a sense, the given hints already narrow down the entire space of (ostensibly) possible assignments to a single one. There are constraint solvers that do this. For example, with the CLP(B) version based on BDDs that I mentioned, the solver internally constructs a Binary Decision Diagram (BDD) which is like a (ideally: more compact) truth table of all assignments that satisfy the requirements. Therefore, with the CLP(B) version I posted, search is never necessary for valid Sudoku puzzles, because they admit precisely one solution, and the constraint solver deduces this unique solution by reasoning about the decision diagram. There's a severe drawback to this: The BDD may be exponential in the number of variables. That's a problem, because there are dozens of variables in many Sudoku puzzles. In practice, we are often lucky, and the worst-case space requirements do not arise. For comparison, the CLP(FD/ℤ) formulation is based on constraint propagation that ensures a certain kind of consistency for all individual constraints in isolation, but not necessarily for the combination of all constraints, i.e., the problem as a whole. In practice, at least for Sudoku puzzles, this also often leads to finding the unique solution without any search. This may also be the case if only the minimum number of clues for a valid Sudoku puzzle (i.e., 17, per https://arxiv.org/abs/1201.0749 https://arxiv.org/abs/1201.0749) is specified, as the parent mentions. In general, search is still required. In the concrete case of (standard) Sudoku, the required search, if there is any at all, is typically very small, because the many constraints usually narrow down the entire space considerably. Reducing the amount of required search is the key attraction and goal of the consistency techniques that are used by constraint systems. The available systems differ in how much and how fast they are able to prune inconsistent values, leading to notions such as global consistency, domain consistency, bounds consistency etc. that give some indication of propagation strength.
OJFord 7y ago
I love the simplicity or prolog; I often think it/datalog would be great as a query language for applications. e.g. instead of Jira having its JQL or whatever, it would just have a prelude, then you'd write things like: my_team_working_on_it(ticket) :- assigned(ticket, user), on_team(user, team), on_team(current_user, team). Or to search for tickets assigned to you (like defining a board filter): assigned(_, current_user)
- elamje 7y ago
  Check out datomic database
  - fiddlerwoaroof 7y ago
    Also datascript
  - OJFord 7y ago
    Thought it rang a bell from a databases lecture - seems it 'extends' datalog: https://docs.datomic.com/cloud/whatis/data-model.html#datalog https://docs.datomic.com/cloud/whatis/data-model.html#datalo... Thanks for reminding me, must find an excuse to play with it!
pezo1919 7y ago
The only thing prevents me using prolog for proper tasks is not getting its IO: reading/writing files: csv, json. Any cool (video) tuts on it? I searched a lot but did not find anything "easy".
- hjek 7y ago
  Say you have a file, `foo.json`, with the content: {"foo":"bar"} Run `swipl` and first load the JSON library: ?- [library(http/json)]. true. Then open the file `foo.json` (in read mode) as Stream which JSON read translates to Term: ?- open('foo.json', read, Stream), json_read(Stream, Term). Stream = <stream>(0x557f0cbfb1c0), Term = json([foo=bar]). (Both instances of `Stream` are the same because of unification.) Say `foo.csv` containts: foo,bar Then go: ?- [library(csv)]. true. ?- csv_read_file("foo.csv",Rows). Rows = [row(foo, bar)]. Triska's videos are quite theoretical. Anne Ogborn has a lot of good real world programming tutorials[0]. Can highly recommend the web app tutorial[1]. I don't know any good videos that cover this. I'm happy to help with what I can though, and I've also found the ##Prolog IRC on Freenode helpful. [0]: http://www.pathwayslms.com/swipltuts/ http://www.pathwayslms.com/swipltuts/ [1]: http://www.pathwayslms.com/swipltuts/html/index.html http://www.pathwayslms.com/swipltuts/html/index.html
GavinMcG 7y ago
Peter Norvig's Sudoku solver using constrain propagation is a nice demonstration of the mini-Kanren approach.[0] I spoke at RubyConf a few years ago on the basics of logic programming and constraint propagation, and demoed a (poorly-coded) solver interface.[1] [0]https://norvig.com/sudoku.html https://norvig.com/sudoku.html [1]https://m.youtube.com/watch?v=f5Bi6_GOIB8 https://m.youtube.com/watch?v=f5Bi6_GOIB8
- triska 7y ago
  In my opinion, a key attraction of Prolog is the regularity of its syntax and the relation between its syntax and semantics. I mean not only homoiconicity, but something beyond that. For example, one of the first questions of Prolog beginners is usually: "Why does my predicate fail for a specific query?" Prolog allows us to mechanically find and give a minimal explanation why a query fails. We can do this by systematically generalizing the program and show a minimal fragment that still fails. We can mechanically generalize a program by using logic variables instead of concrete values, and by removing goals (i.e., constraints) from conjunctions. A key attraction of Prolog is that if you take any pure program, and replace any of the goals by true/0, you still get a valid and more general (or at least equally general) program. For example, take the Prolog program: my_list(Ls) :- Ls = [a,b|Rs], Ls = [a,c|Rs]. In this example, I am using trivial constraints (only (=)/2), and the mistake is quite obvious. But the point remains: We can remove and generalize any and all goals and give explanations why a query fails. For example, why does the most general query, i.e., ?- my_list(Ls)., fail? A possible explanation could like like this: my_list(Ls) :- Ls = [a,b|Rs], * Ls = [a,c|Rs]. here, I have used ( * )/1 to "generalize away" a goal, using a suitable definition of ( * )/1 like: :- op(920,fy, *). *_. The fact that the query then succeeds tells us that the second goal is, in a sense, a reason for the failure. No other language I have seen gives comparable guarantees and ways of debugging. For example, suppose I remove a single form in a miniKanren program. The result may no longer even constitute a valid program, and even if it does, I am not aware of any meaningful general property that can be said about the remaining program. The ability to systematically generate explanations like this seems to be quite unique to logic programming languages like Prolog.
maebert 7y ago
I can’t help but to feel delightfully nostalgic whenever I read about Prolog, thanks for writing this up. If you’re interested, I’ve created a set of Prolog exercises about 10 years ago when I was teaching this in college, including one for “advanced Sudoku”: https://github.com/maebert/prolog_puzzles/blob/master/readme.md#sudoku https://github.com/maebert/prolog_puzzles/blob/master/readme...
grandsui 7y ago
I immediately started sweating when I saw the title of this article as it instantly threw me back to my 3rd year 'Programming Languages and Paradigms' course where we had to do this for an assessment (except it was Jigsaw Soduku).
tmaly 7y ago
I would love to see Prolog implemented in hardware like the Lisp machines.
- tom_mellior 7y ago
  It's been done, though only in an academic setting: https://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/5991.html https://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/5991.html https://www.researchgate.net/publication/242056713_Special_or_general-purpose_hardware_for_Prolog_A_comparison https://www.researchgate.net/publication/242056713_Special_o... (sorry to link to ResearchGateKeeper, though somehow by closing the tab, deleting cookies, and opening the tab I managed to get it to give me the PDF without needing to log in, lol) https://www.sciencedirect.com/science/article/pii/S0743106696889813 https://www.sciencedirect.com/science/article/pii/S074310669... (Elsevier, urgh) I'm sure a bit of web searching will turn up more. It looks like having special purpose hardware for Prolog is useful, which I don't find too surprising. But if you make hardware, you need someone to give you money for it. As an aside, I wonder now much of the use of Lisp machines was non-academic. I know that there were actual commercial companies selling them, but where those mostly university spinoffs selling back to universities?
  - lispm 7y ago
    > It's been done, though only in an academic setting See the Melcom PSI computer from Mitsubishi. http://museum.ipsj.or.jp/en/computer/other/0009.html http://museum.ipsj.or.jp/en/computer/other/0009.html > As an aside, I wonder now much of the use of Lisp machines was non-academic. I know that there were actual commercial companies selling them, but where those mostly university spinoffs selling back to universities? I would think that roughly 10000 hardware Lisp machines were built (incl. embedded boards). Quite a lot went into research, but not just academic research, but also company R&D. Some machines were built as deployment machines and were used by military, government agencies (like NASA) and also commercial. Notable were for example the graphics systems by Symbolics which were widely used in high-end graphics for TV and animation studios. A lot of computer animated logos you were seeing in TV in the mid/end 80s were done with them. Examples: https://www.youtube.com/watch?v=Cwer_xKrmI4 https://www.youtube.com/watch?v=Cwer_xKrmI4 https://www.youtube.com/watch?v=n21FSKDjObg https://www.youtube.com/watch?v=n21FSKDjObg But there were a bunch of other early deployed applications on Lisp Machines: 3d cad (iCAD), American Express Authorizer (credit authorization expert system), scheduling for the Hubble Space Station, scheduling for power plant operations, seat allocation optimization for swissair, early military troop virtual reality training system, satellite image processing, ...
carapace 7y ago
Triska on the front page! Sweet. It was in large part thanks to "The Power of Prolog" that I was able to figure out a nice solution to the "Zebra" puzzle: /* Via https://www.metalevel.at/prolog/puzzles The "Zebra Puzzle" https://en.wikipedia.org/wiki/Zebra_Puzzle - There are five houses. - The Englishman lives in the red house. - The Spaniard owns the dog. - Coffee is drunk in the green house. - The Ukrainian drinks tea. - The green house is immediately to the right of the ivory house. - The Old Gold smoker owns snails. - Kools are smoked in the yellow house. - Milk is drunk in the middle house. - The Norwegian lives in the first house. - The man who smokes Chesterfields lives in the house next to the man with the fox. - Kools are smoked in the house next to the house where the horse is kept. - The Lucky Strike smoker drinks orange juice. - The Japanese smokes Parliaments. - The Norwegian lives next to the blue house. Now, who drinks water? Who owns the zebra? In the interest of clarity, it must be added that each of the five houses is painted a different color, and their inhabitants are of different national extractions, own different pets, drink different beverages and smoke different brands of American cigarets [sic]. One other thing: in statement 6, right means your right. */ :- use_module(library(clpfd)). house_next_to(H0, H1) :- abs(H0 - H1) #= 1. /* Thanks https://www.metalevel.at/prolog/puzzles */ puzzle(Vars) :- Vars = [GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse, Englishman, Spaniard, Ukrainian, Norwegian, Japanese, Dog, Snails, Fox, Horse, Zebra, Coffee, Tea, Milk, OrangeJuice, Water, OldGold, Kools, Chesterfields, LuckyStrike, Parliaments ], Vars ins 1..5, all_distinct([GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse]), all_distinct([Englishman, Spaniard, Ukrainian, Norwegian, Japanese]), all_distinct([Dog, Snails, Fox, Horse, Zebra]), all_distinct([Coffee, Tea, Milk, OrangeJuice, Water]), all_distinct([OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]), Englishman #= RedHouse, Spaniard #= Dog, Coffee #= GreenHouse, Ukrainian #= Tea, GreenHouse #= 1 + IvoryHouse, OldGold #= Snails, Kools #= YellowHouse, Milk #= 3, Norwegian #= 1, house_next_to(Chesterfields, Fox), house_next_to(Kools, Horse), LuckyStrike #= OrangeJuice, Japanese #= Parliaments, house_next_to(Norwegian, BlueHouse). /* Then to print out the solution after loading the program above use: puzzle([ GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse, Englishman, Spaniard, Ukrainian, Norwegian, Japanese, Dog, Snails, Fox, Horse, Zebra, Coffee, Tea, Milk, OrangeJuice, Water, OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]), label([ GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse, Englishman, Spaniard, Ukrainian, Norwegian, Japanese, Dog, Snails, Fox, Horse, Zebra, Coffee, Tea, Milk, OrangeJuice, Water, OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]). */ See also "Boring Sudoku": /* Boring Prolog Sudoku. */ :- use_module(library(clpfd)). puzzle(Vars) :- Vars = [ A11, A12, A13, A14, A15, A16, A17, A18, A19, A21, A22, A23, A24, A25, A26, A27, A28, A29, A31, A32, A33, A34, A35, A36, A37, A38, A39, A41, A42, A43, A44, A45, A46, A47, A48, A49, A51, A52, A53, A54, A55, A56, A57, A58, A59, A61, A62, A63, A64, A65, A66, A67, A68, A69, A71, A72, A73, A74, A75, A76, A77, A78, A79, A81, A82, A83, A84, A85, A86, A87, A88, A89, A91, A92, A93, A94, A95, A96, A97, A98, A99], Vars ins 1..9, all_distinct([A11, A12, A13, A14, A15, A16, A17, A18, A19]), all_distinct([A21, A22, A23, A24, A25, A26, A27, A28, A29]), all_distinct([A31, A32, A33, A34, A35, A36, A37, A38, A39]), all_distinct([A41, A42, A43, A44, A45, A46, A47, A48, A49]), all_distinct([A51, A52, A53, A54, A55, A56, A57, A58, A59]), all_distinct([A61, A62, A63, A64, A65, A66, A67, A68, A69]), all_distinct([A71, A72, A73, A74, A75, A76, A77, A78, A79]), all_distinct([A81, A82, A83, A84, A85, A86, A87, A88, A89]), all_distinct([A91, A92, A93, A94, A95, A96, A97, A98, A99]), all_distinct([A11, A21, A31, A41, A51, A61, A71, A81, A91]), all_distinct([A12, A22, A32, A42, A52, A62, A72, A82, A92]), all_distinct([A13, A23, A33, A43, A53, A63, A73, A83, A93]), all_distinct([A14, A24, A34, A44, A54, A64, A74, A84, A94]), all_distinct([A15, A25, A35, A45, A55, A65, A75, A85, A95]), all_distinct([A16, A26, A36, A46, A56, A66, A76, A86, A96]), all_distinct([A17, A27, A37, A47, A57, A67, A77, A87, A97]), all_distinct([A18, A28, A38, A48, A58, A68, A78, A88, A98]), all_distinct([A19, A29, A39, A49, A59, A69, A79, A89, A99]), all_distinct([A11, A21, A31, A12, A22, A32, A13, A23, A33]), all_distinct([A41, A51, A61, A42, A52, A62, A43, A53, A63]), all_distinct([A71, A81, A91, A72, A82, A92, A73, A83, A93]), all_distinct([A14, A24, A34, A15, A25, A35, A16, A26, A36]), all_distinct([A44, A54, A64, A45, A55, A65, A46, A56, A66]), all_distinct([A74, A84, A94, A75, A85, A95, A76, A86, A96]), all_distinct([A17, A27, A37, A18, A28, A38, A19, A29, A39]), all_distinct([A47, A57, A67, A48, A58, A68, A49, A59, A69]), all_distinct([A77, A87, A97, A78, A88, A98, A79, A89, A99]).
fjfaase 7y ago
I personally think it is a little overkill to use Prolog to solve sudokus, as there is a simple mapping of sudokus to exact covers. The resulting exact covers are rather small and can usually be solved within a fraction of a second using Knuth's Algorithm X, even for hard sudokus. http://www.iwriteiam.nl/D1009.html#9 http://www.iwriteiam.nl/D1009.html#9

179 points by hjek 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...

ggggtez 7y ago

Prolog is good for discrete search like this, mostly because it's just hiding the underlying search algorithm that other languages would be to be explicit about (but as a result, other languages can search more efficiently).

segmondy 7y ago
All computer science problems can be reduced to sorting & searching. ;-D
- randomsearch 7y ago
  Is this really true? I was wondering about complexity analysis, for example.
  - iamgopal 7y ago
    Search to sort, sort to search, don't use random search.
  - ggggtez 7y ago
    No it's not true. I think if you called multiplication a sorting algorithm it would be really dishonest.
jodrellblank 7y ago
Other languages can search more efficiently if you write a more efficient search in them, but Prolog can search more efficiently if you write a more efficient search in it, too. "That's it. On backtracking, this generates increasingly longer lists Ls, and invokes p/1 only on lists of bounded length. Bamm! Iterative deepening. [..] asymptotically optimal under very general assumptions, and you can make it easily available in Prolog yourself. I guess mostly for this reason, the default execution strategy is kept extremely simple. When needed, you can easily implement other search strategies on top of it." - https://www.reddit.com/r/prolog/comments/47fchf/why_depthfirst_for_resolution/ https://www.reddit.com/r/prolog/comments/47fchf/why_depthfir...

segmondy 7y ago

Solving Sudoku smartly with Prolog. The nice thing with Prolog is that if you don't understand how to program but you understand the rules/logic of the problem. In this case you understand the rules of Sudoku, you can define the board and the rules and Prolog will brute force it for you. Harder to do in other languages.

alexbanks 7y ago

This was a final project in a course I took in college surveying programming languages. I thought Prolog was insanely interesting. Through most of the project I thought it was crazy, but when I finished it made excellent sense. Since then I've thought a lot about using Prolog for optimized job/task scheduling, but I've never had an actual need to do it.

justkez 7y ago

I did a module in my undergrad degree that used Prolog as the learning tool/language. At the time I didn't understand why Prolog was such a different paradigm (declarative); all I remember is feeling a true sense of joy writing prolog code and running it. I've never found/made up a reason to try it out since then and no language/system/paradigm has given me the same enjoyment since!

protomyth 7y ago

I love the embedded PostScript in the source code. Its always fun to see how other people write their code.

triska 7y ago
Thank you for noting this! PostScript is currently underappreciated, and I highly recommend learning it. Among many other uses, I like to use PostScript as a portable animation language to visualize search processes like in this case. Also, programming PostScript is great fun and in a sense quite timeless: In all likelihood, these definitions will work without change also in the distant future, because PostScript is so widely spread and frequently used. Newer graphics languages and concepts also take many ideas from PostScript, but PostScript is in my experience still the most fun and flexible of them, at least for a very large set of important use cases.

bluetwo 7y ago

Curious about 2 things: 1) Can it solve especially hard Sudoku puzzles? (ie, expert level where humans often get stuck) 2) Is there a resource somewhere that lists the types of Prolog problems that it excels at solving?

hjek 7y ago
1) Yes, and (when there is only one unique solution) it can apparently be found in Prolog without doing an search at all by using constraint logic programming. Check the video in the sudoku article. 2) I'm not the best at answering this as I'm quite new to Prolog, but I'll try. I'd say a) anything you'd use a general purpose programming languge for, b) anything you'd use SQL for, and c) anything that's too difficult to do in either of those. SWI Prolog[0] has a large standard library and feels very "batteries included". Perhaps what I wouldn't use it for is mobile apps..? (But then again, there's Tau Prolog[1] which could probably work in a Cordova app). [0]: http://www.swi-prolog.org/ http://www.swi-prolog.org/ [1]: http://tau-prolog.org/ http://tau-prolog.org/
- taeric 7y ago
  I'm curious on your first point. There are puzzles that have multiple legal plays but only a single solution. In those, guessing/searching is basically required, right?
  - triska 7y ago
    A valid Sudoku puzzle is such that the given clues admit precisely one solution. Hence, if you somehow manage to take into account all the initially available information, then no search is required, because, in a sense, the given hints already narrow down the entire space of (ostensibly) possible assignments to a single one. There are constraint solvers that do this. For example, with the CLP(B) version based on BDDs that I mentioned, the solver internally constructs a Binary Decision Diagram (BDD) which is like a (ideally: more compact) truth table of all assignments that satisfy the requirements. Therefore, with the CLP(B) version I posted, search is never necessary for valid Sudoku puzzles, because they admit precisely one solution, and the constraint solver deduces this unique solution by reasoning about the decision diagram. There's a severe drawback to this: The BDD may be exponential in the number of variables. That's a problem, because there are dozens of variables in many Sudoku puzzles. In practice, we are often lucky, and the worst-case space requirements do not arise. For comparison, the CLP(FD/ℤ) formulation is based on constraint propagation that ensures a certain kind of consistency for all individual constraints in isolation, but not necessarily for the combination of all constraints, i.e., the problem as a whole. In practice, at least for Sudoku puzzles, this also often leads to finding the unique solution without any search. This may also be the case if only the minimum number of clues for a valid Sudoku puzzle (i.e., 17, per https://arxiv.org/abs/1201.0749 https://arxiv.org/abs/1201.0749) is specified, as the parent mentions. In general, search is still required. In the concrete case of (standard) Sudoku, the required search, if there is any at all, is typically very small, because the many constraints usually narrow down the entire space considerably. Reducing the amount of required search is the key attraction and goal of the consistency techniques that are used by constraint systems. The available systems differ in how much and how fast they are able to prune inconsistent values, leading to notions such as global consistency, domain consistency, bounds consistency etc. that give some indication of propagation strength.

OJFord 7y ago

I love the simplicity or prolog; I often think it/datalog would be great as a query language for applications. e.g. instead of Jira having its JQL or whatever, it would just have a prelude, then you'd write things like: my_team_working_on_it(ticket) :- assigned(ticket, user), on_team(user, team), on_team(current_user, team). Or to search for tickets assigned to you (like defining a board filter): assigned(_, current_user)

elamje 7y ago
Check out datomic database
- fiddlerwoaroof 7y ago
  Also datascript
- OJFord 7y ago
  Thought it rang a bell from a databases lecture - seems it 'extends' datalog: https://docs.datomic.com/cloud/whatis/data-model.html#datalog https://docs.datomic.com/cloud/whatis/data-model.html#datalo... Thanks for reminding me, must find an excuse to play with it!

pezo1919 7y ago

The only thing prevents me using prolog for proper tasks is not getting its IO: reading/writing files: csv, json. Any cool (video) tuts on it? I searched a lot but did not find anything "easy".

hjek 7y ago
Say you have a file, `foo.json`, with the content: {"foo":"bar"} Run `swipl` and first load the JSON library: ?- [library(http/json)]. true. Then open the file `foo.json` (in read mode) as Stream which JSON read translates to Term: ?- open('foo.json', read, Stream), json_read(Stream, Term). Stream = <stream>(0x557f0cbfb1c0), Term = json([foo=bar]). (Both instances of `Stream` are the same because of unification.) Say `foo.csv` containts: foo,bar Then go: ?- [library(csv)]. true. ?- csv_read_file("foo.csv",Rows). Rows = [row(foo, bar)]. Triska's videos are quite theoretical. Anne Ogborn has a lot of good real world programming tutorials[0]. Can highly recommend the web app tutorial[1]. I don't know any good videos that cover this. I'm happy to help with what I can though, and I've also found the ##Prolog IRC on Freenode helpful. [0]: http://www.pathwayslms.com/swipltuts/ http://www.pathwayslms.com/swipltuts/ [1]: http://www.pathwayslms.com/swipltuts/html/index.html http://www.pathwayslms.com/swipltuts/html/index.html

GavinMcG 7y ago

Peter Norvig's Sudoku solver using constrain propagation is a nice demonstration of the mini-Kanren approach.[0] I spoke at RubyConf a few years ago on the basics of logic programming and constraint propagation, and demoed a (poorly-coded) solver interface.[1] [0]https://norvig.com/sudoku.html https://norvig.com/sudoku.html [1]https://m.youtube.com/watch?v=f5Bi6_GOIB8 https://m.youtube.com/watch?v=f5Bi6_GOIB8

triska 7y ago
In my opinion, a key attraction of Prolog is the regularity of its syntax and the relation between its syntax and semantics. I mean not only homoiconicity, but something beyond that. For example, one of the first questions of Prolog beginners is usually: "Why does my predicate fail for a specific query?" Prolog allows us to mechanically find and give a minimal explanation why a query fails. We can do this by systematically generalizing the program and show a minimal fragment that still fails. We can mechanically generalize a program by using logic variables instead of concrete values, and by removing goals (i.e., constraints) from conjunctions. A key attraction of Prolog is that if you take any pure program, and replace any of the goals by true/0, you still get a valid and more general (or at least equally general) program. For example, take the Prolog program: my_list(Ls) :- Ls = [a,b|Rs], Ls = [a,c|Rs]. In this example, I am using trivial constraints (only (=)/2), and the mistake is quite obvious. But the point remains: We can remove and generalize any and all goals and give explanations why a query fails. For example, why does the most general query, i.e., ?- my_list(Ls)., fail? A possible explanation could like like this: my_list(Ls) :- Ls = [a,b|Rs], * Ls = [a,c|Rs]. here, I have used ( * )/1 to "generalize away" a goal, using a suitable definition of ( * )/1 like: :- op(920,fy, *). *_. The fact that the query then succeeds tells us that the second goal is, in a sense, a reason for the failure. No other language I have seen gives comparable guarantees and ways of debugging. For example, suppose I remove a single form in a miniKanren program. The result may no longer even constitute a valid program, and even if it does, I am not aware of any meaningful general property that can be said about the remaining program. The ability to systematically generate explanations like this seems to be quite unique to logic programming languages like Prolog.

maebert 7y ago

I can’t help but to feel delightfully nostalgic whenever I read about Prolog, thanks for writing this up. If you’re interested, I’ve created a set of Prolog exercises about 10 years ago when I was teaching this in college, including one for “advanced Sudoku”: https://github.com/maebert/prolog_puzzles/blob/master/readme.md#sudoku https://github.com/maebert/prolog_puzzles/blob/master/readme...

grandsui 7y ago

I immediately started sweating when I saw the title of this article as it instantly threw me back to my 3rd year 'Programming Languages and Paradigms' course where we had to do this for an assessment (except it was Jigsaw Soduku).

tmaly 7y ago

I would love to see Prolog implemented in hardware like the Lisp machines.

tom_mellior 7y ago
It's been done, though only in an academic setting: https://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/5991.html https://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/5991.html https://www.researchgate.net/publication/242056713_Special_or_general-purpose_hardware_for_Prolog_A_comparison https://www.researchgate.net/publication/242056713_Special_o... (sorry to link to ResearchGateKeeper, though somehow by closing the tab, deleting cookies, and opening the tab I managed to get it to give me the PDF without needing to log in, lol) https://www.sciencedirect.com/science/article/pii/S0743106696889813 https://www.sciencedirect.com/science/article/pii/S074310669... (Elsevier, urgh) I'm sure a bit of web searching will turn up more. It looks like having special purpose hardware for Prolog is useful, which I don't find too surprising. But if you make hardware, you need someone to give you money for it. As an aside, I wonder now much of the use of Lisp machines was non-academic. I know that there were actual commercial companies selling them, but where those mostly university spinoffs selling back to universities?
- lispm 7y ago
  > It's been done, though only in an academic setting See the Melcom PSI computer from Mitsubishi. http://museum.ipsj.or.jp/en/computer/other/0009.html http://museum.ipsj.or.jp/en/computer/other/0009.html > As an aside, I wonder now much of the use of Lisp machines was non-academic. I know that there were actual commercial companies selling them, but where those mostly university spinoffs selling back to universities? I would think that roughly 10000 hardware Lisp machines were built (incl. embedded boards). Quite a lot went into research, but not just academic research, but also company R&D. Some machines were built as deployment machines and were used by military, government agencies (like NASA) and also commercial. Notable were for example the graphics systems by Symbolics which were widely used in high-end graphics for TV and animation studios. A lot of computer animated logos you were seeing in TV in the mid/end 80s were done with them. Examples: https://www.youtube.com/watch?v=Cwer_xKrmI4 https://www.youtube.com/watch?v=Cwer_xKrmI4 https://www.youtube.com/watch?v=n21FSKDjObg https://www.youtube.com/watch?v=n21FSKDjObg But there were a bunch of other early deployed applications on Lisp Machines: 3d cad (iCAD), American Express Authorizer (credit authorization expert system), scheduling for the Hubble Space Station, scheduling for power plant operations, seat allocation optimization for swissair, early military troop virtual reality training system, satellite image processing, ...

carapace 7y ago

Triska on the front page! Sweet. It was in large part thanks to "The Power of Prolog" that I was able to figure out a nice solution to the "Zebra" puzzle: /* Via https://www.metalevel.at/prolog/puzzles The "Zebra Puzzle" https://en.wikipedia.org/wiki/Zebra_Puzzle - There are five houses. - The Englishman lives in the red house. - The Spaniard owns the dog. - Coffee is drunk in the green house. - The Ukrainian drinks tea. - The green house is immediately to the right of the ivory house. - The Old Gold smoker owns snails. - Kools are smoked in the yellow house. - Milk is drunk in the middle house. - The Norwegian lives in the first house. - The man who smokes Chesterfields lives in the house next to the man with the fox. - Kools are smoked in the house next to the house where the horse is kept. - The Lucky Strike smoker drinks orange juice. - The Japanese smokes Parliaments. - The Norwegian lives next to the blue house. Now, who drinks water? Who owns the zebra? In the interest of clarity, it must be added that each of the five houses is painted a different color, and their inhabitants are of different national extractions, own different pets, drink different beverages and smoke different brands of American cigarets [sic]. One other thing: in statement 6, right means your right. */ :- use_module(library(clpfd)). house_next_to(H0, H1) :- abs(H0 - H1) #= 1. /* Thanks https://www.metalevel.at/prolog/puzzles */ puzzle(Vars) :- Vars = [GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse, Englishman, Spaniard, Ukrainian, Norwegian, Japanese, Dog, Snails, Fox, Horse, Zebra, Coffee, Tea, Milk, OrangeJuice, Water, OldGold, Kools, Chesterfields, LuckyStrike, Parliaments ], Vars ins 1..5, all_distinct([GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse]), all_distinct([Englishman, Spaniard, Ukrainian, Norwegian, Japanese]), all_distinct([Dog, Snails, Fox, Horse, Zebra]), all_distinct([Coffee, Tea, Milk, OrangeJuice, Water]), all_distinct([OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]), Englishman #= RedHouse, Spaniard #= Dog, Coffee #= GreenHouse, Ukrainian #= Tea, GreenHouse #= 1 + IvoryHouse, OldGold #= Snails, Kools #= YellowHouse, Milk #= 3, Norwegian #= 1, house_next_to(Chesterfields, Fox), house_next_to(Kools, Horse), LuckyStrike #= OrangeJuice, Japanese #= Parliaments, house_next_to(Norwegian, BlueHouse). /* Then to print out the solution after loading the program above use: puzzle([ GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse, Englishman, Spaniard, Ukrainian, Norwegian, Japanese, Dog, Snails, Fox, Horse, Zebra, Coffee, Tea, Milk, OrangeJuice, Water, OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]), label([ GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse, Englishman, Spaniard, Ukrainian, Norwegian, Japanese, Dog, Snails, Fox, Horse, Zebra, Coffee, Tea, Milk, OrangeJuice, Water, OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]). */ See also "Boring Sudoku": /* Boring Prolog Sudoku. */ :- use_module(library(clpfd)). puzzle(Vars) :- Vars = [ A11, A12, A13, A14, A15, A16, A17, A18, A19, A21, A22, A23, A24, A25, A26, A27, A28, A29, A31, A32, A33, A34, A35, A36, A37, A38, A39, A41, A42, A43, A44, A45, A46, A47, A48, A49, A51, A52, A53, A54, A55, A56, A57, A58, A59, A61, A62, A63, A64, A65, A66, A67, A68, A69, A71, A72, A73, A74, A75, A76, A77, A78, A79, A81, A82, A83, A84, A85, A86, A87, A88, A89, A91, A92, A93, A94, A95, A96, A97, A98, A99], Vars ins 1..9, all_distinct([A11, A12, A13, A14, A15, A16, A17, A18, A19]), all_distinct([A21, A22, A23, A24, A25, A26, A27, A28, A29]), all_distinct([A31, A32, A33, A34, A35, A36, A37, A38, A39]), all_distinct([A41, A42, A43, A44, A45, A46, A47, A48, A49]), all_distinct([A51, A52, A53, A54, A55, A56, A57, A58, A59]), all_distinct([A61, A62, A63, A64, A65, A66, A67, A68, A69]), all_distinct([A71, A72, A73, A74, A75, A76, A77, A78, A79]), all_distinct([A81, A82, A83, A84, A85, A86, A87, A88, A89]), all_distinct([A91, A92, A93, A94, A95, A96, A97, A98, A99]), all_distinct([A11, A21, A31, A41, A51, A61, A71, A81, A91]), all_distinct([A12, A22, A32, A42, A52, A62, A72, A82, A92]), all_distinct([A13, A23, A33, A43, A53, A63, A73, A83, A93]), all_distinct([A14, A24, A34, A44, A54, A64, A74, A84, A94]), all_distinct([A15, A25, A35, A45, A55, A65, A75, A85, A95]), all_distinct([A16, A26, A36, A46, A56, A66, A76, A86, A96]), all_distinct([A17, A27, A37, A47, A57, A67, A77, A87, A97]), all_distinct([A18, A28, A38, A48, A58, A68, A78, A88, A98]), all_distinct([A19, A29, A39, A49, A59, A69, A79, A89, A99]), all_distinct([A11, A21, A31, A12, A22, A32, A13, A23, A33]), all_distinct([A41, A51, A61, A42, A52, A62, A43, A53, A63]), all_distinct([A71, A81, A91, A72, A82, A92, A73, A83, A93]), all_distinct([A14, A24, A34, A15, A25, A35, A16, A26, A36]), all_distinct([A44, A54, A64, A45, A55, A65, A46, A56, A66]), all_distinct([A74, A84, A94, A75, A85, A95, A76, A86, A96]), all_distinct([A17, A27, A37, A18, A28, A38, A19, A29, A39]), all_distinct([A47, A57, A67, A48, A58, A68, A49, A59, A69]), all_distinct([A77, A87, A97, A78, A88, A98, A79, A89, A99]).

fjfaase 7y ago

I personally think it is a little overkill to use Prolog to solve sudokus, as there is a simple mapping of sudokus to exact covers. The resulting exact covers are rather small and can usually be solved within a fraction of a second using Knuth's Algorithm X, even for hard sudokus. http://www.iwriteiam.nl/D1009.html#9 http://www.iwriteiam.nl/D1009.html#9