[Bratmon]

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.

[lll-o-lll]

> 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?

[Bratmon]

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.

[jodrellblank]

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

[repelsteeltje]

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.

[triska]

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.

[Bratmon]

In other languages, you can find the lines where the performance problems are and fix them without breaking the abstraction everywhere else.

[triska]

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.

[jodrellblank]

> "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.

[AdieuToLogic]

> 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].

0 - https://en.wikipedia.org/wiki/Declarative_programming

[bmitc]

What is your alternative suggestion?