2 ms·

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 bas

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.

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.