8 ms·

P-99: Ninety-Nine Prolog Problems

129 points by kick 7y ago

archielc 7y ago
Scala's adaptation of this (S-99): http://aperiodic.net/phil/scala/s-99/ http://aperiodic.net/phil/scala/s-99/
wruza 7y ago
I like the idea of walking around Prolog sometimes. But often it is used against its seemingly main purpose. What do lists do there? Prolog should be cool at tasks like: Pierre is french and never met a guy from 2nd floor at the stairs, Joe has french friend who smokes, Bob likes Alice and living under the roof, and Alice can’t stand cigarettes (and Bob); can Alice live in the same house if it has only 3 floors? Lists though seem so unnatural to logic problems, the same way they emulate integers with lists in ‘too abstract’ lisps.
- slig 7y ago
  Anyone looking for a good time can search for "zebra puzzles" or "logic puzzles" and try to solve them using Prolog.
- hahajk 7y ago
  One application that seems to me like it should be a natural fit for Prolog is building a (human) schedule: class goes from 8-4, a student cannot take two classes simultaneously, Joe is not available on Wednesdays, etc. I forget the specifics but every implementation of such a schedule tends up using lists and explicit recursion, (which I think is unpleasant in Prolog) In fact, most moderately complex solutions of any problem I’ve seen fall back on lists and explicit recursion. (I thought I was using Prolog to avoid all that!) That’s probably a shortcoming of the language.
  - maweki 7y ago
    If you have such constraints, why not use a proper constraint system? Prolog is in a (sometimes not so) sweet spots in terms of exploring search spaces. For a problem like you've described, just write a SAT instance and be done with it. And if you don't know how large your solution/search space is (even a bound), then there's no alternative to creating lists and giving recursion hints.
    - overlords 7y ago
      Most prolog implementations have finite domain constraints and constraint handling rules, so you can work with constraints if that's more natural.
  - JadeNB 7y ago
    Indeed, some of the early history of Prolog is in Hewitt's PLANNER: https://en.wikipedia.org/wiki/Planner_(programming_language)#The_genesis_of_Prolog https://en.wikipedia.org/wiki/Planner_(programming_language)... .
- andreasscherman 7y ago
  Correct me if I'm wrong, haven't written a lot of Prolog, but I think most optimisation-based problems are suitable for modelling using Prolog. Scheduling, time tabling, allocation problems such as knapsack problem or bin packing, etc. Some of these problems can be quite tricky to write regular code for, but just stating the constraints and letting Prolog plan/solve it can be simpler.
- gmfawcett 7y ago
  I like the idea of using Java sometimes. But why does it have numbers and arithmetic? Java should be great at tasks like, "cats are a kind of animal", or "my drawing program can draw both squares and circles." Arithmetic seems so unnatural in an object-oriented language. ;-) Perhaps Prolog isn't ideally suited to a lot of programming problems -- that's a personal decision to make -- but it's silly to wonder why a general-purpose programming language would have general-purpose data structures.
- tempguy9999 7y ago
  What do you actually suggest we use instead of lists? Which from my ancient memory of prolog, are just the equivalent of cons cells, so come naturally to prolog. Edit: from https://en.wikipedia.org/wiki/Prolog_syntax_and_semantics#Data_types https://en.wikipedia.org/wiki/Prolog_syntax_and_semantics#Da... "Lists are defined inductively: The atom [] is a list. A compound term with functor . (dot) and arity 2, whose second argument is a list, is itself a list. There exists special syntax for denoting lists: .(A, B) is equivalent to [A|B]. For example, the list .(1, .(2, .(3, []))) can be written (edit: cut for clarity) as [1,2,3]."
- mrighele 7y ago
  Lists allow to express certain constraints in more natural way, like "John has three cats at least one of which is male" or "I want a list of all the people that have at least three friends in common". You don't have to use lists, but that means code duplication and low maintainability (i.e. instead of stating a condition and "repeating" for all the element of the list, you have to duplicate it explicitly). It is not so much different from a regular language in this regard: you can write Java without using lists and use a variable for every single element, but who wants to do that ?
  - wruza 7y ago
    I didn’t think about it that way. Nice insight, thank you and all commenters here for your explanations!
- colanderman 7y ago
  Nah lists are great in Prolog. You can do all the fun recursion and matching stuff that you can do in functional languages, without extra syntax, and you can throw logic variables into them, so you can get tail recursion no matter which direction you build your list. The thing to keep in mind about Prolog is that it's not really a logic language so much as a structural language. All operations are defined in terms of terms, so, cyclic terms aside, you can't really have non-structural "infinite" values like you can in a true logic language like TLA+ or SMT2, where infinite vectors with no defined underlying representation are the norm. You could in theory add something like that to Prolog, but you'd be defining a new fundamental type and make it a different language.
  - tempguy9999 7y ago
    "The thing to keep in mind about Prolog is that it's not really a logic language [...]" WWWut? Eh??? Come again? Plz esspalin.
    - colanderman 7y ago
      Prolog isn't based on first-order logic or anything. Its "logic" is just whatever falls out of its search mechanism and term unification. So e.g. you can't say things like "forall X: P" and expect anything useful to happen. (There's no way to express "forall X" without some finite domain for X, and there's no way in standard prolog to apply P to those uninstantiated Xs.) Whereas languages like SMT2 and TLA+ are true logic languages in that you can express such abstract statements. You can, and people often do, write an entire meaningful and useful SMT2 program without once mentioning a concrete term. (With TLA+ this is less common due to the focus of its tooling being more on search than deduction.) The solver will apply various tactics to deduce the truth/falsity of your stated theorems. On the contrary, Prolog does this only in a limited sense, defined exactly by the scope of its search and unification mechanisms. You can't write a meaningful Prolog program without writing concrete terms or term structures. (With the possible exception of playing tricks with dif/2.) (There are Prolog constraint-solving extensions which basically use Prolog syntax as a frontend to a true logic engine. They're neat and I love them, because Prolog syntax is great, but my original statement applies only to core Prolog.) TLDR: true logic languages let you talk about infinities; core Prolog does not.
- excursionist 7y ago
  One big feature of Prolog that relies on lists are DCGs (Definite Clause Grammars)[0]. Lists are such a ubiquitous data structure that not having them in a language would just be painful. https://en.wikipedia.org/wiki/Definite_clause_grammar https://en.wikipedia.org/wiki/Definite_clause_grammar
  - tom_mellior 7y ago
    Right. Developing natural language parsers was one of the main motivations for the development of Prolog. Natural language sentences are lists. List processing is something Prolog is excellent at. It's even better at it than functional languages because more things can be expressed in a tail-recursive way.
  - JadeNB 7y ago
    DCGs unsugar into lists, but the very fact that there's a non-list-based syntax (although lists are used for terminals, that could easily be avoided) shows that lists aren't actually essential. One has to pick some basic data structure, and lists are good for it, but they're not essential. (For example, one could use a lambda-calculus-based formalism, and then, if desired, encode lists in it in the usual way; or, as Prolog actually does it, encode lists as terms, as tempguy9999 (https://news.ycombinator.com/item?id=21772069 https://news.ycombinator.com/item?id=21772069) points out.
- plumeria 7y ago
  Think of lists as a way to collect multiple possible values of a computation. See: https://www.schoolofhaskell.com/school/starting-with-haskell/basics-of-haskell/13-the-list-monad https://www.schoolofhaskell.com/school/starting-with-haskell...
pgtan 7y ago
Just make sure, solutions work in both directions.
nitnelave 7y ago
An example of a small Prolog program used in a perfect use-case: the advent of code of this year. https://github.com/nitnelave/advent_of_code_2019/tree/master/04 https://github.com/nitnelave/advent_of_code_2019/tree/master... I'm doing the advent of code in a different language every day, and since the day 4 was about some constraint resolution, Prolog was the perfect tool there.
- tom_mellior 7y ago
  Nice. As a hint, you can unify free variables, i.e., variables not bound to anything. Future bindings of those variables will respect the equality. This means that you could write your password/1 predicate as something more like: password(X) :- length(X, 6), has_2_equal_consecutive_digits(X), has_6_digits(X), is_value_in_range(X), digits_are_increasing(X). That is, even before filling the list with digits, you would already have captured the constraint that two digits will have to be consecutive. Then, while instantiating the list inside has_6_digits/1, something like 134567 would never even be generated, and you wouldn't need to test it for being in range and having increasing digits.
- Tankenstein 7y ago
  Amazing, am doing the same, also chose prolog for day 4. Ended up with quite different code though: https://uku.dev/posts/advent-of-languages-day-4-prolog https://uku.dev/posts/advent-of-languages-day-4-prolog
quotemstr 7y ago
No.
dontchooseanick 7y ago
Obligatory fun clones : * 99_Ninety-Nine_Lisp_Problems http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/func... * Ninety-Nine_Haskell_Problems https://wiki.haskell.org/H-99:_Ninety-Nine_Haskell_Problems https://wiki.haskell.org/H-99:_Ninety-Nine_Haskell_Problems * Ninety-Nine_Erlang_Problems https://github.com/joelchelliah/ninety-nine_erlang_problems/blob/master/README.md https://github.com/joelchelliah/ninety-nine_erlang_problems/... * ... Rust https://github.com/MaskRay/99-problems-rust?files=1 https://github.com/MaskRay/99-problems-rust?files=1
simplify 7y ago
Prolog / Datalog are beautiful languages. They should be in the repertoire of more programmers.
doodle_111 7y ago
Cjx
photon_lines 7y ago
If anyone is interested in implementing a mini prolog interpreter...I made a toy one in python which you can find here: https://github.com/photonlines/Python-Prolog-Interpreter https://github.com/photonlines/Python-Prolog-Interpreter
krispyfi 7y ago
I tried using Prolog for Advent of Code last year. It went okayish, but I seem to recall that some things were unreasonably hard, such as reading from non-Prolog-syntax files. I should give it another try this year. Maybe I missed something obvious.

129 points by kick 7y ago

Scala's adaptation of this (S-99): http://aperiodic.net/phil/scala/s-99/ http://aperiodic.net/phil/scala/s-99/

I like the idea of walking around Prolog sometimes. But often it is used against its seemingly main purpose. What do lists do there? Prolog should be cool at tasks like: Pierre is french and never met a guy from 2nd floor at the stairs, Joe has french friend who smokes, Bob likes Alice and living under the roof, and Alice can’t stand cigarettes (and Bob); can Alice live in the same house if it has only 3 floors? Lists though seem so unnatural to logic problems, the same way they emulate integers with lists in ‘too abstract’ lisps.

slig 7y ago
Anyone looking for a good time can search for "zebra puzzles" or "logic puzzles" and try to solve them using Prolog.
hahajk 7y ago
One application that seems to me like it should be a natural fit for Prolog is building a (human) schedule: class goes from 8-4, a student cannot take two classes simultaneously, Joe is not available on Wednesdays, etc. I forget the specifics but every implementation of such a schedule tends up using lists and explicit recursion, (which I think is unpleasant in Prolog) In fact, most moderately complex solutions of any problem I’ve seen fall back on lists and explicit recursion. (I thought I was using Prolog to avoid all that!) That’s probably a shortcoming of the language.
- maweki 7y ago
  If you have such constraints, why not use a proper constraint system? Prolog is in a (sometimes not so) sweet spots in terms of exploring search spaces. For a problem like you've described, just write a SAT instance and be done with it. And if you don't know how large your solution/search space is (even a bound), then there's no alternative to creating lists and giving recursion hints.
  - overlords 7y ago
    Most prolog implementations have finite domain constraints and constraint handling rules, so you can work with constraints if that's more natural.
- JadeNB 7y ago
  Indeed, some of the early history of Prolog is in Hewitt's PLANNER: https://en.wikipedia.org/wiki/Planner_(programming_language)#The_genesis_of_Prolog https://en.wikipedia.org/wiki/Planner_(programming_language)... .
andreasscherman 7y ago
Correct me if I'm wrong, haven't written a lot of Prolog, but I think most optimisation-based problems are suitable for modelling using Prolog. Scheduling, time tabling, allocation problems such as knapsack problem or bin packing, etc. Some of these problems can be quite tricky to write regular code for, but just stating the constraints and letting Prolog plan/solve it can be simpler.
gmfawcett 7y ago
I like the idea of using Java sometimes. But why does it have numbers and arithmetic? Java should be great at tasks like, "cats are a kind of animal", or "my drawing program can draw both squares and circles." Arithmetic seems so unnatural in an object-oriented language. ;-) Perhaps Prolog isn't ideally suited to a lot of programming problems -- that's a personal decision to make -- but it's silly to wonder why a general-purpose programming language would have general-purpose data structures.
tempguy9999 7y ago
What do you actually suggest we use instead of lists? Which from my ancient memory of prolog, are just the equivalent of cons cells, so come naturally to prolog. Edit: from https://en.wikipedia.org/wiki/Prolog_syntax_and_semantics#Data_types https://en.wikipedia.org/wiki/Prolog_syntax_and_semantics#Da... "Lists are defined inductively: The atom [] is a list. A compound term with functor . (dot) and arity 2, whose second argument is a list, is itself a list. There exists special syntax for denoting lists: .(A, B) is equivalent to [A|B]. For example, the list .(1, .(2, .(3, []))) can be written (edit: cut for clarity) as [1,2,3]."
mrighele 7y ago
Lists allow to express certain constraints in more natural way, like "John has three cats at least one of which is male" or "I want a list of all the people that have at least three friends in common". You don't have to use lists, but that means code duplication and low maintainability (i.e. instead of stating a condition and "repeating" for all the element of the list, you have to duplicate it explicitly). It is not so much different from a regular language in this regard: you can write Java without using lists and use a variable for every single element, but who wants to do that ?
- wruza 7y ago
  I didn’t think about it that way. Nice insight, thank you and all commenters here for your explanations!
colanderman 7y ago
Nah lists are great in Prolog. You can do all the fun recursion and matching stuff that you can do in functional languages, without extra syntax, and you can throw logic variables into them, so you can get tail recursion no matter which direction you build your list. The thing to keep in mind about Prolog is that it's not really a logic language so much as a structural language. All operations are defined in terms of terms, so, cyclic terms aside, you can't really have non-structural "infinite" values like you can in a true logic language like TLA+ or SMT2, where infinite vectors with no defined underlying representation are the norm. You could in theory add something like that to Prolog, but you'd be defining a new fundamental type and make it a different language.
- tempguy9999 7y ago
  "The thing to keep in mind about Prolog is that it's not really a logic language [...]" WWWut? Eh??? Come again? Plz esspalin.
  - colanderman 7y ago
    Prolog isn't based on first-order logic or anything. Its "logic" is just whatever falls out of its search mechanism and term unification. So e.g. you can't say things like "forall X: P" and expect anything useful to happen. (There's no way to express "forall X" without some finite domain for X, and there's no way in standard prolog to apply P to those uninstantiated Xs.) Whereas languages like SMT2 and TLA+ are true logic languages in that you can express such abstract statements. You can, and people often do, write an entire meaningful and useful SMT2 program without once mentioning a concrete term. (With TLA+ this is less common due to the focus of its tooling being more on search than deduction.) The solver will apply various tactics to deduce the truth/falsity of your stated theorems. On the contrary, Prolog does this only in a limited sense, defined exactly by the scope of its search and unification mechanisms. You can't write a meaningful Prolog program without writing concrete terms or term structures. (With the possible exception of playing tricks with dif/2.) (There are Prolog constraint-solving extensions which basically use Prolog syntax as a frontend to a true logic engine. They're neat and I love them, because Prolog syntax is great, but my original statement applies only to core Prolog.) TLDR: true logic languages let you talk about infinities; core Prolog does not.
excursionist 7y ago
One big feature of Prolog that relies on lists are DCGs (Definite Clause Grammars)[0]. Lists are such a ubiquitous data structure that not having them in a language would just be painful. https://en.wikipedia.org/wiki/Definite_clause_grammar https://en.wikipedia.org/wiki/Definite_clause_grammar
- tom_mellior 7y ago
  Right. Developing natural language parsers was one of the main motivations for the development of Prolog. Natural language sentences are lists. List processing is something Prolog is excellent at. It's even better at it than functional languages because more things can be expressed in a tail-recursive way.
- JadeNB 7y ago
  DCGs unsugar into lists, but the very fact that there's a non-list-based syntax (although lists are used for terminals, that could easily be avoided) shows that lists aren't actually essential. One has to pick some basic data structure, and lists are good for it, but they're not essential. (For example, one could use a lambda-calculus-based formalism, and then, if desired, encode lists in it in the usual way; or, as Prolog actually does it, encode lists as terms, as tempguy9999 (https://news.ycombinator.com/item?id=21772069 https://news.ycombinator.com/item?id=21772069) points out.
plumeria 7y ago
Think of lists as a way to collect multiple possible values of a computation. See: https://www.schoolofhaskell.com/school/starting-with-haskell/basics-of-haskell/13-the-list-monad https://www.schoolofhaskell.com/school/starting-with-haskell...

pgtan 7y ago

Just make sure, solutions work in both directions.

nitnelave 7y ago

An example of a small Prolog program used in a perfect use-case: the advent of code of this year. https://github.com/nitnelave/advent_of_code_2019/tree/master/04 https://github.com/nitnelave/advent_of_code_2019/tree/master... I'm doing the advent of code in a different language every day, and since the day 4 was about some constraint resolution, Prolog was the perfect tool there.

tom_mellior 7y ago
Nice. As a hint, you can unify free variables, i.e., variables not bound to anything. Future bindings of those variables will respect the equality. This means that you could write your password/1 predicate as something more like: password(X) :- length(X, 6), has_2_equal_consecutive_digits(X), has_6_digits(X), is_value_in_range(X), digits_are_increasing(X). That is, even before filling the list with digits, you would already have captured the constraint that two digits will have to be consecutive. Then, while instantiating the list inside has_6_digits/1, something like 134567 would never even be generated, and you wouldn't need to test it for being in range and having increasing digits.
Tankenstein 7y ago
Amazing, am doing the same, also chose prolog for day 4. Ended up with quite different code though: https://uku.dev/posts/advent-of-languages-day-4-prolog https://uku.dev/posts/advent-of-languages-day-4-prolog

quotemstr 7y ago

No.

dontchooseanick 7y ago

Obligatory fun clones : * 99_Ninety-Nine_Lisp_Problems http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/func... * Ninety-Nine_Haskell_Problems https://wiki.haskell.org/H-99:_Ninety-Nine_Haskell_Problems https://wiki.haskell.org/H-99:_Ninety-Nine_Haskell_Problems * Ninety-Nine_Erlang_Problems https://github.com/joelchelliah/ninety-nine_erlang_problems/blob/master/README.md https://github.com/joelchelliah/ninety-nine_erlang_problems/... * ... Rust https://github.com/MaskRay/99-problems-rust?files=1 https://github.com/MaskRay/99-problems-rust?files=1

simplify 7y ago

Prolog / Datalog are beautiful languages. They should be in the repertoire of more programmers.

doodle_111 7y ago

Cjx

photon_lines 7y ago

If anyone is interested in implementing a mini prolog interpreter...I made a toy one in python which you can find here: https://github.com/photonlines/Python-Prolog-Interpreter https://github.com/photonlines/Python-Prolog-Interpreter

krispyfi 7y ago

I tried using Prolog for Advent of Code last year. It went okayish, but I seem to recall that some things were unreasonably hard, such as reading from non-Prolog-syntax files. I should give it another try this year. Maybe I missed something obvious.