> "Don't be bothered with by the fact that the solutions end with "or false" here. It's a function of how the search algorithms work; the solver looked for more solutions, then failed. I'll admit, I don't totally understand why it only sometimes does this, but it's expected."
I think this is explained in The Power of Prolog[1] that the answers coming from Prolog are not printing text to a terminal, they are valid Prolog terms(/data/code). That's why the result uses the same `;` for OR as code does. Answer (x ; y ; false) is "query can be answered by x or y or no other answer found". (This would let you do meta-programming, reasoning about the results and rewriting the results in a LISPy data-as-code way, if you were more advanced than I am).
Prolog systems do optimisations to jump to the correct answer without searching, if they can, (e.g. database style indexing on the facts and rules) and in those cases there is no code left to search after showing the first answer, no need to prompt the user "should I search for more answers in the remaining code?", and so no need for an output "false" to say "I finished searching and found no more solutions".
This embodies why I don't like Prolog. Prolog's philosophy is that you should just write the predicates without thinking about how the engine works. But as soon as you do something actually complicated, you realize that the different optimization modes of the engine give different results, and shortly after that you'll find yourself in the "exhaustively try every possible combination until we get one that satisfies the predicates" mode, and your code will go from taking 1 second to run to taking 8 days.
And because you don't control the engine (you're not supposed to think about it, after all), there's nothing you can do but rewrite the whole thing in a traditional programming language.
> as soon as you do something actually complicated, you realize that the different optimization modes of the engine give different results
The same is true of SQL query planners. You can perform basic queries without understanding how your SQL engine of choice works under the hood, but if you want performance, you must understand how your DB works. SQL is just the interface.
This is different in kind from imperative programming languages (which are much closer in abstraction to the underlying machine architecture), but we rub along with SQL ok; why not Prolog?
Yeah, but the difference is that SQL provides a huge number of ways to solve the "My query got slow when it got complicated" problem. In Prolog, you have the cut operator, and when that stops working for your usecase, you're just SOL.
I relate to "I wrote it in Prolog, it works on a test example, it doesn't work on the full thing and I don't know if it will ever finish", and that was why I stopped my last attempt at Advent of Code in Prolog. It took me hours longer to make something which worked, it was more code, and it never finished on the full puzzle, and I was fed up and had no motivation or approach to discovering why.
But I think it's different in experience, but not different in kind, from knowing that in Java and C# and Python, string catenation in a loop will perform badly and generate a lot of garbage collection pressure, and you need to know about either StringBuilder or the pattern of making a List of chunks then converting to string once at the end, to get better performance. Or in PowerShell, Objects have more convenience but a lot more overhead than simple values and you have to reach for .NET Library functions for better performance. Neither of those is a problem in C, but not because C has solved those problems, but because C doesn't have any conveniences. Any language that has higher level conveniences, have them implemented in some way with some assumptions that will have tradeoffs that you need to understand to use it well, and the higher it is, the more things there are to know - but also the shorter convenience code you can write.
Still, though, the claim that all Prolog has is the cut operator is not right. If you write a linear list scan it will be O(N), and if you put two of them together it will be O(NxN) just like in any language, e.g:
member(X, Items),
member(Y, Items),
SWI Prolog has tabling (memoization)[1] which you can wrap around any predicate with one line, and the engine will cach the results for faster lookups. You can write this in other languages, e.g. with Python decorators, but you have to write it yourself instead of it being included.
SWI and Scryer have constraint solvers, which are basically another language embedded in Prolog using its programmable syntax, backed by a different search engine, that can solve numerical problems with constraint propagation much faster than with Prolog normal search - something that just isn't possible in other languages in the same way, only available as library code (e.g. Z3 constraint solver), and not a standard techniqe.
SWI Prolog has compare/3 and zcompare/3 e.g. "compare(Op, 4, 5)" will fill in the operator Op = < because four is less than five. You can then "do_thing(Op, Data)" and where do_thing/2 is different for less than, equal, and greater than, and because of first argument indexing on the operator, that can turn something that would have been a search through three branches into a determinstic single path, acting to cut the tree without using a cut operator, and without using if/elseif/else.
SWI Prolog ships with a graphical profiler, too: https://www.swi-prolog.org/pldoc/man?section=profile
[1] https://www.swi-prolog.org/pldoc/man?section=tabling-memoize
I somewhat disagree that you shouldn't be aware of how the engine works. The mechanics are quite simple. Prolog's horn clauses are combined in depth first search manner trying to proof that the negated goal is false.
However, most prolog books focus on rooting the declarative mindset because programmers are generally more familiar with imperative programming. But just as with SQL or lisp there are definitely good ways, bad ways and plain mistakes you can make when approaching a problem.
How is this different from other programming languages though?
One example I often think about is from Ken Silverman: "sub eax, 128" → "add eax, -128". So equivalent ways to write the same program may have different performance characteristics also depending on the tools that are applied. How many people could tell without trying which way to write this example is preferable?
The same phenomenon will be encountered in all kinds of languages, where engine and compiler improvements make existing code faster or slower.
In other languages, you can find the lines where the performance problems are and fix them without breaking the abstraction everywhere else.
I think this is very well phrased, and I would argue the same holds for Prolog too.
In my opinion, a key difference between Prolog and other languages in that regard is one of degree, not kind: Compared to other languages, addressing performance problems in Prolog engines tends to have far greater effects on Prolog programs, because so much is implicit (i.e., left to the engine).
If the performance problem is not in the engine, but in the program itself, then we will face the same questions with Prolog as with other languages: How to formulate the program better, is there a better approach altogether?
For example, earlier today an interesting question regarding performance was posted in the Scryer discussions:
https://github.com/mthom/scryer-prolog/discussions/3341
The comparison in this case is between Gecode and Scryer on a seemingly simple but nontrivial combinatorial task. What is the problem here? Most likely the Scryer engine itself can be improved. And also very likely, there are better ways to model the task, and also better search strategies, and these tend to have far greater performance impact than the base language, and these questions remain also if we change the base language.
In my opinion, these questions regarding different kinds of formulations tend to be more frequently associated with Prolog than with other languages because Prolog is more frequently used for complex tasks where it is not a priori clear how to even approach the problem.
> "How to formulate the program better, is there a better approach altogether?"
When I code an imperative Bubble Sort, a profiler can identify that function as a hotspot and I can Google "faster sort algorithm" and can understand relatively easily that the nested linear scans were taking the time. In recent years, Casey Muratori has become a prominent internet voice against naive use of "Object Oriented" (OOP) patterns, because using a lot of OOP inheritance and abstraction adds a little overhead here and there and everywhere, leading to poor overall performance with no single place to speed it up.
My Prolog code is closer to the OOP situation, especially when I try to express something with a DCG. It is easy to accidentally code non-deterministic searches in places where I did not expect, or desire them, in a way which makes the whole code describe a huge search space and there is no single place where the extra runtime is localised and no good way to incrementally improve the situation. The comparison in your link between Gecode and Scryer is illustrative; the author wrote a solution in Gecode which completed in 10 seconds. They spent "many hours" writing Prolog and they cannot get the code to finish on the large case, they don't understand why, and they have no way forwards except to ask the internet. Likely there is no single part which is slow in the way that Bubble Sort is slow, only "there may be better approaches altogether" - but how can the author help themselves find and move towards the better approaches? "Learn a faster sorting algorithm" is a practical, achievable, step forwards; "just be a better programmer" is an impassé.
The sticking point is that with OOP patterns, the question of "how do I become a better programmer?" often does not need any answer, because the layers of indirection are additive, each call adds some milliseconds, and that overall leads to a program that still works in a reasonable time, it merely feels sluggish or has a tedious delay. With Prolog, the calls can quickly become a combinatorial explosion of search space, leading to a program which does not finish at all, and thus the question needs an answer. With an imperative codebase a suggestion to "use a faster algorithm for this one task" is one step along a lifetime of gradually becoming a better programmer. With OOP abstractions, people can get results, solve problems, or be employed making slow web portals without ever improving or making highly performant code. With Prolog "You simply have to be a better programmer" before you can get any results at all on larger cases is a much steeper learning curve.
> Prolog's philosophy is that you should just write the predicates without thinking about how the engine works.
This is the definition of declarative programming[0].
Eh, no, admittedly this is a bit confusing but the ";" at the top-level is not the same as the ;/2 disjunction operator. At the top-level the ";" is just a switch to say "give me more". In most Prolog systems you can also press space for the same thing.
Whether a query will end with "false" or "true" really depends entirely on the query, and the predicates it's calling. So it depends on how a predicate is called. You just have to analyse the predicate in the good, old-fashioned way of eyballing it and maybe running it a couple of times to see why it fails or succeeds, and why it first succeeds and then fails like above.
This is really all down to determinism, which is to say, whether a predicate leaves behind a choice point or not. In this particular case, what's going on can be revealed by looking at the trace of the query. For the following, I loaded the Pokemon database from https://github.com/alexpetros/prologdex/blob/main/src/dex/po...) into SWI-Prolog and traced it like this:
[trace] 21 ?- type(Pokemon, water), type(Pokemon, ice).
Call: (15) dex:type(_2236, water) ? creep
Exit: (15) dex:type(squirtle, water) ? creep
Call: (15) dex:type(squirtle, ice) ? creep
Fail: (15) dex:type(squirtle, ice) ? creep
Redo: (15) dex:type(_2236, water) ? creep
Exit: (15) dex:type(wartortle, water) ? creep
Call: (15) dex:type(wartortle, ice) ? creep
Fail: (15) dex:type(wartortle, ice) ? abort
% Execution Aborted
In the second call... I mean this one:
Call: (15) dex:type(squirtle, ice) ? creep
[trace] 21 ?- type(Pokemon, water), type(Pokemon, ice).
type(Pokemon, ice)
type(squirtle, ice)
What happens when the engine finds a pokemon that is both water and ice? The first one in the database is dewogong, at which point the tracer goes like this:
Redo: (15) dex:type(_92, water) ? creep
Exit: (15) dex:type(dewgong, water) ? creep
Call: (15) dex:type(dewgong, ice) ? creep
Exit: (15) dex:type(dewgong, ice) ? creep
Pokemon = dewgong .
At that point the "." means I pressed "enter" and that's basically saying "no more thank you". I was getting a little impatient. If I had pressed ";" (or space) instead, we'd have a repeat of the previous pattern with successive failures until another water and ice pokemon was found. The next one in the database is cloyster, and so it goes.
That back-and-forth between success and failure goes on until we run out of pokemon. At some point the engine can't unify either goal of the top-level query with a fact in the database so the final result is "false"; because after succeeding a bunch of times, it can't succeed no more.
Honestly this is a fair question to have and I had to trace the query to be able to give a fair account of it so the advice to take it as "expected" is not that bad. Prolog is doing something mind-numbingly repetitive on the background and it's hard to follow it, so sometimes the best thing is to just run your program and see what it does, instead of trying to intuit it.
A while ago I was playing the romhack Run&Bun, which drastically ups the difficulty of Pokemon Emerald. Watching others play, most of the game was doing 'calcs': calculating how to approach a battle. This was done using a javascript frontend to a simulator, and a lot of excel sheets.
So I forked the calculator and added a Prolog wrapper so I could find solutions to battles based on the team of Pokemon that I caught. https://github.com/deosjr/runbuncalc/blob/master/main.pl
My runs died pretty early, but there are some notes here as I was implementing that are fun to read. I implemented each battle as a test case and let my solver find a solution, then amended the plan and commented on what actually happened. For example: https://github.com/deosjr/runbuncalc/blob/master/run10.pl#L2...
Very nice!
In the Scryer Prolog discussions, Alex has shared a few ideas and considerations for possible improvements to the Prolog code, including the use of metaprogramming to automatically generate more general relations:
https://github.com/mthom/scryer-prolog/discussions/3221
I hope for an interesting followup article!
Another very interesting Prolog program by Alex is factgraph.pl:
https://github.com/alexpetros/factgraph.pl
It's a Prolog implementation of the IRS Fact Graph, an application of Law as Code.
It continues to be immensely surprising to me that Joe Armstrong was able to write the initial Erlang implementation in Prolog. I wish I’d asked him about getting a copy of the source code.
What does this say about Forth? Not much except that it isn't for me.
Take Prolog. I know few things more insulting than having to code in
Prolog. Whereas Armstrong developed Erlang in Prolog and liked it much
better than reimplementing Erlang in C for speed. I can't imagine how
this could be, but this is how it was. People are different.
[0] https://yosefk.com/blog/my-history-with-forth-stack-machines...
Regarding distributed systems, I find Torbjörn Lager's recent work on Web Prolog particularly interesting. He recently posted about it here:
https://github.com/mthom/scryer-prolog/discussions/3322
and also in the course of a discussion on various approaches to implement concurrency in Prolog:
When i was in uni, the course teaching Prolog and Lisp was called "Artificial Intelligence for Engineers".
I’ve always heard the first wave of AI was all lisp. Why is that? Just cause it had superpowers over the other languages of the day?
I can see why someone would think prolog could bring an AI wave. Even after messing around with it for a few hours, I feel like there are things I could build in prolog that I couldn’t build in typescript.
Same!
Man, where was a post like this when I was struggling trying to learn Prolog, modelling something with knights and knaves...
Was initially nonplussed, but toward the end I realized the choice of pokemon for an example actually works out well for showing how prologue can solve problems. I’m now a bit curious about trying it out somewhere.
Prolog is actually a perfect fit for all kinds of adventure, role playing, strategy, and classic board/card games, with clauses representing game rules and facts representing the game state and universe in the most natural way.
Simple general-purpose opponents can be coded using just recursive backtracking search, while more advanced ones (supporting moves that need to destructively change state) can still be conveniently modelled by reifying facts and thereby enable backtracking over assert/retract-like Prolog DB modifications, as used in discrete combinatorial planners [1].
[1]: https://quantumprolog.sgml.net/container-planning-demo/part1...
All examples shown in the article can be ran with Datalog too (with stratified negation and arithmetic comparison), which has a clearer execution model and looks almost identical to Prolog. Prolog underneath is doing backtracking, while Datalog is finding a least fixed point of derived relations where iterating on data won't produce more relations, and is akind to SQL (but usually stronger because of recursion).
Ahem. "Prolog underneath" is doing SLD-Resolution implemented as a Depth-First Search with backtracking. Saying it's "doing backtracking" is really fudging quite a bit.
Datalog, instead, is "underneath" implementing a TP-Operator, a procedure that finds the fix-point of a Datalog program which happens to be the same as its Least Herbrand Model, which is what SLD-Resolution also finds, except that SLD-Resolution allows functions and does not guarantee termination, like Datalog does. The big advantage of a TP Operator is the termination guarantees and it can be implemented so that it's efficient, but it's still limited, and the fact that there are many different flavours of Datalog (with or without stratified negation, arithmetic, lists etc) is testament to the difficulty of improving on Prolog's efficiency without breaking its soundness or completeness. Or, like I always say, "sound, complete, efficient: choose two".
Importantly, Datalog is not Turing-complete though.
You can get Turing completeness by wrapping your datalog query in a while loop, so that's not particularly restrictive.
It’s surprisingly hard to design a useful language which isn’t Turing-complete, so it should be seen as a compliment, not a problem to fix
You can get Turing completeness by wrapping basically any math or logic system in a while loop, even arithmetic. So that doesn't tell us much about the restrictiveness of the overall system since I'd call "you can only use arithmetic" pretty damn restrictive.
In the case of Datalog, it not being Turing-complete is usually seen as a feature rather than restrictive.
Exactly :) It is terminating due to the LFP semantics I was pointing out, it's more akin to SQL than to Prolog. The article doesn't even show the usage of the Prolog cut (`!`).
And yet Prolog can express all examples in the article. For these kinds of problems, giving up TC is mostly a feature. And if you need more expressiveness, there's a lot of practical Datalog-ish systems that can recover Turing completeness (Flix, Formulog, parts of Souffle), while still being saner than SWI Prolog and co. for this type of work, as you generally don't have to care about atom order or search order in the same way. They act so much more predictably.
Nonplussed like initially surprised? It does not mean bored or nonchalant which many people seem to think, probably due to the non- prefix.
Interesting, it seems I learned/am using a modern American mutated version of the word.
https://www.broadlearners.com/t/understanding-the-meaning-of...
https://www.merriam-webster.com/grammar/whole-nother
https://old.reddit.com/r/etymology/comments/13s19j0/wtf_happ...
In my case, I was using it as almost a blend of the two meanings, something mostly meaning “unimpressed”, with a touch of “and a bit perplexed why such effort is going into this”. Basically a shoulder shrug and “okay…?”
I now find myself nonplussed, wondering if I should be using the word at all given it seems to have two opposite meanings.
I always wanted to read about logic programming, and this was a great introduction ! Thank you !
I'm not familiar with Pokemon universe :( Can somebody please explain Pokemon using Prolog?
One of the neat things about Prolog is that queries can be run both forwards and backwards, so I believe this article should already have you covered ;)
There is a lot more than only what they explain in that article (I don't know of any full implementation of Pokemon in Prolog, although there is an implementation in TypeScript).
For example, you can also switch out (to activate a different pokemon) instead of attacking (switching has priority over attacking, so if you switch out then the opponent's attack will hit your newly active pokemon).
There are also many calculations involved, and it can be helpful to know how most of them work.
Are there public tournaments of games like Pokemon where contestants have to compete with eachother using a specific class of algorithms (e.g., logic programming, neural nets, linear programming, etc.)?
If this is your article, you have a typo in learns_priority/3, "move_priority #> 0" should be "P #> 0".
Thank you!
Since you're here, I have a small question: Why use pokemon showdowns API directly and not https://pokeapi.co/ ?
> Then query it like so:
SELECT DISTINCT pokemon, special_attack
FROM pokemon as p
WHERE
p.special_attack > 120
AND EXISTS (
SELECT 1
FROM pokemon_moves as pm
WHERE p.pokemon_name = pm.pokemon_name AND move = 'freezedry'
)
AND EXISTS (
SELECT 1
FROM pokemon_types as pt
WHERE p.pokemon_name = pt.pokemon_name AND type = 'ice'
);
SELECT DISTINCT pokemon, special_attack
FROM pokemon as p
NATURAL JOIN pokemon_moves as pm
NATURAL JOIN pokemon_types as pt
WHERE
p.special_attack > 120 AND
pm.move = 'freezedry' AND
pt.type = 'ice'
;
It would, but it forces the requirement of DISTINCT. With the original, if there were declared PKs (pokemon_name is fine for the main table, with a composite for others), the semi-join (EXISTS) would eliminate the need for DISTINCT entirely.
I think. Doing this in my head, but you could verify it trivially with SQLite or any other RDBMS.
Love this use case, makes me want to implement something similar for Magic the Gathering. I love using scryfall, but I think a more cli first approach with descriptive rules would suffice much better for brewing in eternal formats like Commander with ever growing card pools. I mostly work off of keyword search.
This might be your jam. I should revisit this, most of it is unimplemented. But the parsing part was interesting, since MTG has such a codified language for explaining the rules. My idea here was to take a card's rules text from the official API and parse it into smth that can be used in the game, so you could keep up with new sets with implementation. The weird rule-breaking edge cases will always fail, but a large set of design space can fit, I think.
Somewhat related, check out https://github.com/wordbots/wordbots-parser, a digital card game where you write the cards and the engine parses them to determine what they do. It's fun to mess around with.
Hey, that's cool! I had the same idea too:
https://github.com/stassa/Gleemin
Although the code is nigh-on unreadable now ^_^@
>> The weird rule-breaking edge cases will always fail, but a large set of design space can fit, I think.
Well, in that case you just update the parser or the rules engine. That's precisely how M:tG Arena works and they 've managed to keep up with new sets at a pace never before seen in official M:tG engines. There was a time when writing an M:tG parser was considered impossible [1] and M:tG engines, both official and community ones, each had their own little DSL that they had to manually translate ability text into which could take months especially if the engine also had to be updated to use the new rules in a set. Eventually someone in Wizards realised this is just dumb and they did it the way you go about it above.
______________
[1] Source: my conversations with the folks behind Forge and other community-made M:tG engines.
Wow that is cool, thanks for that!
Your comment makes me want to do this for Yu-Gi-Oh!
I'm not as familiar with Magic, but I've always been curious if that community has tooling at a comparable level of maturity to Pokemon Showdown.
For Yu-Gi-Oh! You have ygopro
”I am about to describe the mechanics of a children’s video game in great detail”
Prolog must be an adult programming language :)
Are there pokémon with backtracking and unification traits? Those could do real Prolog!
Where "Getting C&D from Nintendo for a blog post" fits in?
That's very helpful & easy to follow.
Do you have an Odin tutorial that's as easy to digest?
Sol