mat*_*mat 10 prolog abstract-interpretation
在下面,我只考虑纯 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程序所需的时间,即使您的程序在需要达成协议的不同机器上运行关于运行它的时间,但是你希望保留未来改进具体实现技术的可能性.因此,该度量应仅取决于实际给定的程序,而不取决于实现的任何具体特征,例如访问的存储器单元的数量.
小智 2
复杂性度量的问题在这里得到了充分体现。但嘴唇仍然是一个有用的测量方法。你不会得到：
LIPS ~ TIME
但你得到：
LIPS * DEPTH * COUNT ~ TIME
其中深度是运行时术语深度的度量，它影响统一的时间成本，而计数是子句数量的度量，它影响统一的数量，包括不导致推理的失败。
它与您所说的加法需要一个时间步长是相同的抽象，但事实上我们知道两个大数相加的时间取决于大数的大小。在这里，条款和从句扮演了 bignums 的角色。
有用吗？绝对是的！例如，如果您有两种算法，并且看到深度和计数相同，您可以用嘴唇来比较它们。