Complexity of ISO Prolog predicates

by

tl;dr: No and no.

Let’s start with sort/2 which ideally would need n ld(n) comparisons. Fine, but how long does one comparison take? Let’s try this out:

tails(Es0, [Es0|Ess]) :-
   Es0 = [_|Es],
   tails(Es, Ess).
tails([],[[]]).

call_time(G,T) :-
   statistics(runtime,[T0|_]),
   G,
   statistics(runtime,[T1|_]),
   T is T1 - T0.

| ?- between(12,15,I), N is 2^I, length(L,N),maplist(=(a),L),
     tails(L,LT), call_time(sort(LT,LTs), Tms).

On SICStus 4.3.1 and SWI 7.1.28

I = 12, N = 4096,   Tms_SICS =   680,  Tms_SWI =   3332
I = 13, N = 8192,   Tms_SICS =  2800,  Tms_SWI =  14597
I = 14, N = 16384,  Tms_SICS = 11300,  Tms_SWI =  63656
I = 15, N = 32768,  Tms_SICS = 45680,  Tms_SWI = 315302

By duplicating the size we can easily estimate what the runtime will be. If it duplicates as well, it is linear, and if it quadruples it is quadratic. Clearly both have at least quadratic runtime.

Describing the precise runtime in an abstract manner might be possible, but it is very difficult to ensure that everything is fine. In any case, it is next-to-impossible to mandate a concrete promise in a standard document. Also, it is very difficult to validate such claims.

The best abstract measure might be the number of inferences, often they can be easily observed. See the largest integer or factors. But again, this is only an abstract measure – so something has been torn away, abstraxit. It might very well be the case that the key features have been torn away too.

In general, the ISO standard ISO/IEC 13211-1:1995 core, does not mandate any guarantee for runtime complexities which are clearly out of scope.
It mentions explicitly in a note that also resource limits are out of scope:

1 Scope

….

NOTE — This part of ISO/IEC 13211 does not specify:

a) the size or complexity of Prolog text that will exceed the
capacity of any specific data processing system or language
processor, or the actions to be taken when the corresponding
limits are exceeded;
…

Always remember that a technical standard is a precondition to ensure that a system is fit for some purpose. It is not a sufficient condition. See the example under Purpose in this answer for a somewhat extreme example.

More Related Contents:

  1. What is the difference between ‘ and ” in Prolog?
  2. Safer type tests in Prolog
  3. Meaning of instantiation mode indicators in arguments of Prolog predicates
  4. ‘if’ in prolog?
  5. GNU Prolog assert error
  6. Prolog map procedure that applies predicate to list elements
  7. Definition of a path/trail/walk
  8. Definition of Reflexive Transitive Closure
  9. Most general higher-order constraint describing a sequence of integers ordered with respect to a relation
  10. Reification of term equality/inequality
  11. Prolog successor notation yields incomplete result and infinite loop
  12. Finding Unique Items in a List
  13. Prolog: a person is a sibling of himself?
  14. What is the logical ‘not’ in Prolog?
  15. Stack overflow in Prolog DCG grammar rule: how to handle large lists efficiently or lazily
  16. Using a constrained variable with `length/2`
  17. Einsteins Riddle Prolog
  18. Explanation of a Prolog algorithm to append two lists together
  19. list of the values in the leaf nodes of binary tree T
  20. Shuffle in prolog
  21. reversible “binary to number” predicate
  22. Using \==/2 or dif/2
  23. Converting Terms to Atoms preserving variable names in YAP prolog
  24. Good beginners material on Prolog [closed]
  25. Prolog append with cut operator
  26. Understanding Difference Lists
  27. Define graph in Prolog: edge and path, finding if there is a path between two vertices
  28. PROLOG: Determining if elements in list are equal if order does not matter
  29. Features of good Prolog code? [closed]
  30. How to define (and name) the corresponding safe term comparison predicates in ISO Prolog?

Leave a Comment