| HN Mirror

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),

If you can put your lookups into a Trie instead of a list, they will be faster. SWI Prolog ships with libraries for Tries, Association Lists, Red-Black trees, and other things. Fundamentally, code with functions and scopes and branches is tree-shaped, and code describes tree-shaped execution patterns (see the beginnings of Structure and Interpretation of Computer Programs, SICP, I think), and Prolog "cut" trims branches from the tree, but if you rewrite your code so it doesn't describe branches of the tree that you don't want to execute, then you don't need to cut them and your code has less runtime (in any language).

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