Reasoning about SLD time complexity in Prolog

[jjtolton]

For most programming languages I can typically understand complexity guarantees on most primitive operations. For example, adding to the head of a linked list is O(1) while inserting at the beginning of an array is at least O(n). I find it significantly more challenging to reason about time complexity in Prolog.

For example, in most languages, a nonlazy mapping operation such as maplist/2 or findall/3 would be O(n) in the size of the elements. However, since Prolog used a backtracking search, wouldn't the complexity actually be O(V+E) aka O(choicepoints)?

Or can you look at a logically linear operation and conclude linear time complexity?

I know some things are surprising, for instance that append/3 is apparently constant time in list concatenation? That's pretty unusual. Normally thats at least a linear scan of both lists.

On the other hand, 'length/2is probably anO(n)` operation as it is with linked lists, which is not bad but not ideal (but better than dealing with a complex object).

I know in general the idea is "just write good prolog and over time the implementation speed will get better", but I'd like to learn to understand it a little more deeply than that!

[UWN]

The notion of actual runtime complexity is far too complex to fathom. Think of unification and the "union-find" operation which in Scryer as in many current systems is approximated with the more costly refchains.

Counting inferences is more abstract and a bit easier. But you will have to consider various modes separately.

Normally that's at least a linear scan of both lists. (for append/3)

Not clear which both lists you are referring to. However, the second argument has no influence on the number of inferences performed. Whereas the first and third are solely responsible. And their size is not necessarily of influence. Think of

?- append([a|Xs], Ys, [b|Zs]).
   false.

Where also any instance thereof has constant cost, regardless of the sizes.

On the other hand, length/2 is probably an O(n) operation

Not clear which n you refer to. If the second argument is fixed, that limits also the operation.

But before you go into such details, better consider an even more abstract measure first. That is non-termination and termination. It's like counting inferences with the "numbers" finite and infinite. With the help of failure-slices you can approach these notions rapidly.

[jjtolton]

Speaking more abstractly, one thing I'm trying to do is to learn about how to talk to other engineers about Prolog, particularly about how to defend the choice of using Prolog. In the case of the this problem, if I were to do this on an interview, the natural follow-up question would be "what is the runtime complexity of the implementation".

Now it could be argued that interviews are artificial situations and highly subjective and so that situation doesn't matter. But if I were to suggest Prolog as a solution to technical clients or colleagues, they might be a bit concerned about investing in something, and so they will naturally have questions. "How well does it scale?" is a very natural question. There are many dimensions to scaling, including maintenance and implementation -- but they also want to know about "how well can it handle situation X"?

Let me give you a specific hypothetical situation.

Me: Prolog is a GREAT solution for X!
Them: How would you do it?
Me: Like this!
Them: Wow, that's cool. What's the runtime complexity?
Me: What runtime complexity do you want it to be?
Them: What do you mean?
Me: Well, Prolog abstracts control from the logic, so the complexity is really implementation specific.
Them: Ok... well, every language is turing complete, so theoretically the same argument applies to any language.
Me: That's true, except that most of the time that's just a trip down the turing tarpit. Prolog stands out for its unique metainterpreter facilities and if that's not enough, it has an incredibly powerful and easy to use parsing system in the form of DCGs which ship as part of the standard library. DCGs in Prolog are turing complete and incredibly easy to use, and allow arbitrary AST transformations. In fact, this sort of syntax directed translation was the original purpose of Prolog in the first place!
Them: Ok, I'm not sure I buy that. If Prolog is so good at that, why aren't more compilers written using Prolog?
Me: Well, there hasn't been an ISO-compliant, highly performant, freely available distribution of Prolog until recently.
Them: Define "highly performant".
Me: Well, uh, Scryer Prolog has a compact string representation that makes it ideal for parsing and text processing.
Them: So, can I use it for processing web scale data? Kafka event streams? Can I compile my 50GB code base with it? Can it handle my PostgreSQL data processing needs?
Me: Well, probably. I know some really smart people that use it! 😅

In other words, when it comes down to it, I can't (formally) justify the use of Prolog in a system, besides pointing to (a very few) examples and some engineering arguments that I can only half articulate.

Perhaps talking in terms of runtime complexity is not the best way to assess the usability of Prolog as part of a system architecture, but it is an easy apples-to-apples comparison. Without doing that, I'd need some other way to assess the use of Prolog in a system.

[UWN]

Same dialog about any constraint system (many of which are in their core Prolog based). And there complexity for typical problems is inherently much worse. Still the world operates on such systems.

[haijinSk]

for instance that append/3 is apparently constant time

Maybe this definition:

constantTimeAppend(H1-T1,T1-T2,H1-T2).

?- L1=[1,2,3|T1]-T1,L2=[4,5,6|T2]-T2,constantTimeAppend(L1,L2,Ls).
   L1 = [1,2,3,4,5,6|T2]-[4,5,6|T2], T1 = [4,5,6|T2], L2 = [4,5,6|T2]-T2, Ls = [1,2,3,4,5,6|T2]-T2.

---

"The power of the logic variable is best illustrated by difference lists and the ability in Prolog to concatenate lists in constant time and declaratively.

append(H1-T1,T1-T2,H1-T2).

This is one of gems of Prolog that will stay with everyone for a lifetime."

Pascal Van Hentenryck: Programmation Par Contraintes, 2023

https://bpb-us-w2.wpmucdn.com/sites.gatech.edu/dist/3/865/files/2023/10/AlainColmerauer.pdf

Also, my second source:

https://stackoverflow.com/questions/15028831/how-do-you-append-an-element-to-a-list-in-place-in-prolog

[jjtolton]

for instance that append/3 is apparently constant time

Maybe this definition:

constantTimeAppend(H1-T1,T1-T2,H1-T2).

?- L1=[1,2,3|T1]-T1,L2=[4,5,6|T2]-T2,constantTimeAppend(L1,L2,Ls).
   L1 = [1,2,3,4,5,6|T2]-[4,5,6|T2], T1 = [4,5,6|T2], L2 = [4,5,6|T2]-T2, Ls = [1,2,3,4,5,6|T2]-T2.

"The power of the logic variable is best illustrated by difference lists and the ability in Prolog to concatenate lists in constant time and declaratively.

append(H1-T1,T1-T2,H1-T2).

This is one of gems of Prolog that will stay with everyone for a lifetime."

Pascal Van Hentenryck: Programmation Par Contraintes, 2023

https://bpb-us-w2.wpmucdn.com/sites.gatech.edu/dist/3/865/files/2023/10/AlainColmerauer.pdf

Also, my second source:

https://stackoverflow.com/questions/15028831/how-do-you-append-an-element-to-a-list-in-place-in-prolog

Ah, I see, I think I was confused a bit, but this is the quote that was sticking in my mind.