prolog - Prolog 目标运行时间成本的真实抽象度量

Question

在下文中，我仅考虑纯 Prolog 程序。这意味着我并不是在谈论副作用和操作系统调用，这些副作用和操作系统调用会离开逻辑领域去做一些无法从 Prolog 内部观察到的事情。

对于 Prolog 程序的运行时间成本，有一个众所周知的抽象度量:逻辑推理的数量。我所说的“抽象”是指该措施独立于任何特定的 Prolog 实现和实际的具体硬件。它是一个度量，因为它为我们提供了一些有关执行程序所需时间的信息。我们甚至可以通过陈述每秒推理次数 (LIPS) 来在某种程度上指定 Prolog 系统的性能，而且它的使用如此广泛，以至于人们可以将其称为系统性能的传统衡量标准。传统上，这个数字是通过特定的基准来衡量的，但“推理数量”的一般概念当然也可以扩展到其他更复杂的 Prolog 程序。

但是，据我了解，这种特殊的(我敢说:具体)抽象措施并没有在以下重要意义上说明全部真相:

对于任何给定的 Prolog 目标 G，让我们用 t(G) 表示:T→R 在特定硬件上的给定 Prolog 系统上 G 的实际执行时间，即从 Herbrand 项到实数的函数。让我们将一个测度称为 α :T→R 真实 iff t(G) ≈ α(G)所有 G，从某种意义上说，对于所有目标 G 和所有“现实”类型的硬件，这些值的差异取决于一个受常数限制的因子(我必须稍微未指定最后一点，但我为简单起见，我在这里假设相同的 Prolog 实现在“典型”硬件上的执行方式大致相同。我知道实际情况并非如此，并且相同的实现在不同类型的硬件上可能表现出截然不同的特征。如果是这样，将定义限制为硬件类型的子集，其中实现运行“大致”相同。)

据我所知，逻辑推理的数量通常不是 Prolog 目标实际执行时间的真实衡量标准，特别是因为时间执行统一所需的时间并不是由它来衡量的。人们可以构建这样的情况:该度量与实际执行时间之间的差异不再受常数限制。

因此，我的问题是:对于 Prolog 目标的运行时间是否有一个真实的抽象度量？如果一般不存在，请指定 Prolog 程序的一个有意义的子集，其中可以定义此类度量。例如，通过限制可能发生的统一类型。

这个问题具有很高的实际重要性，例如在使用 Prolog 实现智能合约时:在这种情况下，您想要抽象地测量运行 Prolog 程序需要多长时间，即使您的程序运行在不同的机器上，需要就运行时间达成一致，但您希望保留 future 改进具体实现技术的可能性。因此，该度量应该仅取决于实际给定的程序，而不取决于实现的任何具体特征，例如访问的存储单元的数量。

Answer 1

复杂性度量问题全面开花 here 。但嘴唇仍然是一个有用的测量方法。你不会得到:

LIPS ~ TIME

但是你得到:

LIPS * DEPTH * COUNT ~ TIME

其中深度是运行时术语深度的度量，它影响统一的时间成本，而计数是子句数量的度量，它影响统一的数量，包括不导致推理的失败。

这与您所说的加法需要一个时间步长是相同的抽象，但事实上我们知道两个 bignum 相加的时间取决于 bignum 的大小。在这里，条款和从句扮演了 bignums 的角色。

有用吗？绝对是的!例如，如果您有两种算法，并且看到深度和计数相同，您可以用嘴唇来比较它们。