Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Truthful abstract measure for run time cost of a Prolog goal

Tags:

In the following, I am only considering pure Prolog programs. This means that I am not talking about side-effects and OS calls that leave the realm of logic to do something that cannot be observed from within Prolog.

There is a well-known abstract measure for the run time cost of a Prolog program: The number of logical inferences. By "abstract", I mean that this measure is independent of any particular Prolog implementation and actual concrete hardware. It is a measure in the sense that it gives us some information about the time it will take to execute a program. We can even specify the performance of Prolog systems to some extent by stating their number of inferences per second (LIPS), and this is so widely used that one can call it a traditional measure of system performance. Traditionally, this number is measured by a particular benchmark, but the general notion of "number of inferences" of course extends to other, more complex Prolog programs too.

However, as far as I understand, this particular (dare I say: concrete) abstract measure does not tell the whole truth in the following important sense:

For any given Prolog goal G, let us denote with t(G) : T→R the actual execution time of G on a given Prolog system on particular hardware, i.e. a function from Herbrand terms to the real numbers. Let us call a measure α : T→R truthful iff t(G) ≈ α(G) for all G, in the sense that the values differ by a factor that is bounded by a constant for all goals G and all "realistic" types of hardware (I must leave this last point slightly underspecified, but I am assuming here for simplicity that the same Prolog implementation performs roughly in the same way on "typical" hardware. I know that this is not actually the case, and the same implementation can exhibit drastically different characteristics on different types of hardware. If so, limit the definition to a subset of hardware types where the implementation runs "roughly" the same.)

As far as I know, the number of logical inferences is in general not a truthful measure of the actual execution time of a Prolog goal, in particular because the time it takes to perform unifications is not measured by it. One can construct cases where the difference between this measure and the actual execution time is no longer bounded by a constant.

Therefore, my question: Is there a truthful abstract measure for the run time of a Prolog goal? If it does not exist in general, please specify a meaningful subset of Prolog programs where such a measure can be defined. For example, by restricting the types of unifications that can occur.

This question is of high practical importance for example when using Prolog to implement smart contracts: In such cases, you want to abstractly measure how long it takes to run a Prolog program, even if your program runs on different machines that need to be in agreement about the time it takes running it, and yet you want to preserve the possibility of future improvements to the concrete implementation technology. Therefore, the measure should only depend on the actually given program, not on any concrete features of the implementation, such as the number of memory cells that are accessed.