是否可以编写一个避免无限递归的序言解释器？
Is it possible to write a prolog interpreter that avoids infinite recursion?
主要特点
我最近一直在寻找具有特定功能集的 Prolog 元解释器，但我开始发现我不具备处理它的理论知识。
特点如下：
- 深度优先搜索。
- 以与经典解释器相同的方式解释任何非递归 Prolog 程序。
- 保证突破任何无限递归。这很可能意味着打破图灵完备性，我同意这一点。
- 只要递归的每一步都降低了表达式的复杂度，就继续求值。更具体地说，我希望允许谓词调用自身，但我想防止子句能够调用自身的类似或更复杂的版本。
显然，(3) 和 (4) 是我遇到的问题。我不确定这两个功能是否兼容。我什至不确定是否有一种方法可以定义复杂性，使得 (4) 具有逻辑意义。
在我的研究中，我遇到了“不可避免的模式”的概念，我相信它提供了一种方法来确保特征 (3)，只要特征 (4) 具有格式良好的定义。
我特别想知道这种解释器是否已被证明是不可能的，如果没有，过去是否对类似的解释器进行了理论或具体工作。
额外功能
如果可以实现以上功能，我还有一些额外的功能要添加，如果您也能告诉我这些功能的可行性，将不胜感激:
- 系统地表征和描述这些递归，这样，当检测到一个递归时，可以调用与这种特定形式的递归相匹配的用户定义的谓词或子句。
- 检测导致组合选择呈指数增长的模式，阻止评估，并以与步骤 (5) 相同的方式表征它们，以便它们可以由内置或用户定义的谓词处理。
例子
这是一个简单的谓词，在除了最简单的情况之外的所有情况下，在普通的 Prolog 解释器中显然会导致无限递归。这个解释器应该能够在最多 PSPACE 中对其进行评估（而且，我相信，如果 (6) 可以实现的话，最多 P），同时仍然给出相关结果。
eq(E, E).
eq(E, F):- eq(E,F0), eq(F0,F).
eq(A + B, AR + BR):- eq(A, AR), eq(B, BR).
eq(A + B, B + A).
eq(A * B, B * A).
eq((A * B) / B, A).
eq(E, R):- eq(R, E).
预期结果示例：
?- eq((a + c) + b, b + (c + a)).
true.
?- eq(a, (a * b) / C).
C = b.
提供的示例可能会证明这种解释器很有用，这一事实提示我这样的解释器可能是不可能的，但是，如果是的话，我希望能够理解是什么让它不可能（例如，（3）+（4）是否减少到停机问题？是（6）NP？）。
如果你想保证终止，你可以保守地假设任何输入目标都是非终止的，除非使用可判定的证明程序证明不是这样。基本上，定义一些你知道停止的小 class 目标，并随着时间的推移用聪明的想法扩展它。
这里是三个例子，分别保证或强制三种不同类型的终止（另见Power of Prolog chapter on termination）：
- existential-existential：在可能出现分歧之前至少得到一个答案
- universal-existential: 没有分叉但可能有无限个分叉，所以目标可能不是普遍终止
- universal-universal：经过有限步后，每一个答案都会得到，所以特别是答案一定是有限个
在下文中，假设 halts(Goal) 正确测试了 existential-existential 终止的目标。
Existential-Existential
这使用 halts/1 来证明适度 class 目标的存在终止。当前的求值器eval/1只是回退到底层引擎：
halts(halts(_)).
eval(Input) :- Input.
:- \+ \+ halts(halts(eval(_))).
safe_eval(Input) :-
halts(eval(Input)),
eval(Input).
?- eval((repeat, false)).
C-c C-cAction (h for help) ? a
abort
% Execution Aborted
?- safe_eval((repeat, false)).
false.
可选但强烈推荐的目标指令 \+ \+ halts(halts(eval(_))) 确保当 eval 上的 运行 应用于任何内容时 halts 将始终停止。
将问题拆分为终止检查器和评估器的好处是两者是解耦的：您可以使用任何您想要的评估策略。 halts 可以通过更高级的方法逐渐扩充，以扩展 class 允许的目标，从而腾出 eval 来做同样的事情，例如基于 static/runtime 模式分析、传播失败等的子句重新排序 eval 本身可以通过改进 halts 理解的终止属性来扩展允许目标的 class。
一个警告 - 使用 meta-logical 谓词（如 var/1 的输入可能会破坏目标指令。也许一开始只是不允许这样的谓词，然后随着时间的推移，当您发现安全的使用模式时再次放宽限制。
Universal-Existential
此示例使用 meta-interpreter，改编自 Power of Prolog chapter on meta-interpreters，以 p运行e 关闭无法证明存在终止的分支：
eval(true).
eval((A,B)) :- eval(A), eval(B).
eval((A;_)) :- halts(eval(A)), eval(A).
eval((_;B)) :- halts(eval(B)), eval(B).
eval(g(Head)) :-
clause(Head, Body),
halts(eval(Body)),
eval(Body).
所以这里我们是销毁分支，而不是拒绝评估目标。
为了提高效率，您可以首先简单地评估输入目标并构建 per-branch 组访问子句主体（使用例如 clause/3），并且仅在以下情况下调用 halts您将要重新访问同一分支中的一个子句。
Universal-Universal
上面的meta-interpreter至少排除了所有的发散分支，但仍可能有无数个单独终止的分支。如果我们想确保通用终止，我们可以在输入 eval 之前再次执行所有操作，如 existential-existential 变体：
...
:- \+ \+ halts(halts(\+ \+ eval(_))).
...
safe_eval(Input) :-
halts(\+ \+ eval(Input)),
eval(Input).
所以我们只是添加了通用量化。
您可以尝试的一件有趣的事情是 运行ning halts 本身使用 eval。这可能会产生加速、更好的终止属性或质量上的新功能，但当然需要根据 eval 的语义编写目标指令和 halts。例如。如果你删除双重否定，那么 \+ \+ 将不会普遍量化，如果你传播错误或以其他方式不符合默认的 left-to-right 策略，那么 (goal, false) 通用终止测试（PoP chapter on termination) 也行不通。
主要特点
我最近一直在寻找具有特定功能集的 Prolog 元解释器，但我开始发现我不具备处理它的理论知识。
特点如下：
- 深度优先搜索。
- 以与经典解释器相同的方式解释任何非递归 Prolog 程序。
- 保证突破任何无限递归。这很可能意味着打破图灵完备性，我同意这一点。
- 只要递归的每一步都降低了表达式的复杂度，就继续求值。更具体地说，我希望允许谓词调用自身，但我想防止子句能够调用自身的类似或更复杂的版本。
显然，(3) 和 (4) 是我遇到的问题。我不确定这两个功能是否兼容。我什至不确定是否有一种方法可以定义复杂性，使得 (4) 具有逻辑意义。
在我的研究中，我遇到了“不可避免的模式”的概念，我相信它提供了一种方法来确保特征 (3)，只要特征 (4) 具有格式良好的定义。
我特别想知道这种解释器是否已被证明是不可能的，如果没有，过去是否对类似的解释器进行了理论或具体工作。
额外功能
如果可以实现以上功能，我还有一些额外的功能要添加，如果您也能告诉我这些功能的可行性，将不胜感激:
- 系统地表征和描述这些递归，这样，当检测到一个递归时，可以调用与这种特定形式的递归相匹配的用户定义的谓词或子句。
- 检测导致组合选择呈指数增长的模式，阻止评估，并以与步骤 (5) 相同的方式表征它们，以便它们可以由内置或用户定义的谓词处理。
例子
这是一个简单的谓词，在除了最简单的情况之外的所有情况下，在普通的 Prolog 解释器中显然会导致无限递归。这个解释器应该能够在最多 PSPACE 中对其进行评估（而且，我相信，如果 (6) 可以实现的话，最多 P），同时仍然给出相关结果。
eq(E, E).
eq(E, F):- eq(E,F0), eq(F0,F).
eq(A + B, AR + BR):- eq(A, AR), eq(B, BR).
eq(A + B, B + A).
eq(A * B, B * A).
eq((A * B) / B, A).
eq(E, R):- eq(R, E).
预期结果示例：
?- eq((a + c) + b, b + (c + a)).
true.
?- eq(a, (a * b) / C).
C = b.
提供的示例可能会证明这种解释器很有用，这一事实提示我这样的解释器可能是不可能的，但是，如果是的话，我希望能够理解是什么让它不可能（例如，（3）+（4）是否减少到停机问题？是（6）NP？）。
如果你想保证终止，你可以保守地假设任何输入目标都是非终止的，除非使用可判定的证明程序证明不是这样。基本上，定义一些你知道停止的小 class 目标，并随着时间的推移用聪明的想法扩展它。
这里是三个例子，分别保证或强制三种不同类型的终止（另见Power of Prolog chapter on termination）：
- existential-existential：在可能出现分歧之前至少得到一个答案
- universal-existential: 没有分叉但可能有无限个分叉，所以目标可能不是普遍终止
- universal-universal：经过有限步后，每一个答案都会得到，所以特别是答案一定是有限个
在下文中，假设 halts(Goal) 正确测试了 existential-existential 终止的目标。
Existential-Existential
这使用 halts/1 来证明适度 class 目标的存在终止。当前的求值器eval/1只是回退到底层引擎：
halts(halts(_)).
eval(Input) :- Input.
:- \+ \+ halts(halts(eval(_))).
safe_eval(Input) :-
halts(eval(Input)),
eval(Input).
?- eval((repeat, false)).
C-c C-cAction (h for help) ? a
abort
% Execution Aborted
?- safe_eval((repeat, false)).
false.
可选但强烈推荐的目标指令 \+ \+ halts(halts(eval(_))) 确保当 eval 上的 运行 应用于任何内容时 halts 将始终停止。
将问题拆分为终止检查器和评估器的好处是两者是解耦的：您可以使用任何您想要的评估策略。 halts 可以通过更高级的方法逐渐扩充，以扩展 class 允许的目标，从而腾出 eval 来做同样的事情，例如基于 static/runtime 模式分析、传播失败等的子句重新排序 eval 本身可以通过改进 halts 理解的终止属性来扩展允许目标的 class。
一个警告 - 使用 meta-logical 谓词（如 var/1 的输入可能会破坏目标指令。也许一开始只是不允许这样的谓词，然后随着时间的推移，当您发现安全的使用模式时再次放宽限制。
Universal-Existential
此示例使用 meta-interpreter，改编自 Power of Prolog chapter on meta-interpreters，以 p运行e 关闭无法证明存在终止的分支：
eval(true).
eval((A,B)) :- eval(A), eval(B).
eval((A;_)) :- halts(eval(A)), eval(A).
eval((_;B)) :- halts(eval(B)), eval(B).
eval(g(Head)) :-
clause(Head, Body),
halts(eval(Body)),
eval(Body).
所以这里我们是销毁分支，而不是拒绝评估目标。
为了提高效率，您可以首先简单地评估输入目标并构建 per-branch 组访问子句主体（使用例如 clause/3），并且仅在以下情况下调用 halts您将要重新访问同一分支中的一个子句。
Universal-Universal
上面的meta-interpreter至少排除了所有的发散分支，但仍可能有无数个单独终止的分支。如果我们想确保通用终止，我们可以在输入 eval 之前再次执行所有操作，如 existential-existential 变体：
...
:- \+ \+ halts(halts(\+ \+ eval(_))).
...
safe_eval(Input) :-
halts(\+ \+ eval(Input)),
eval(Input).
所以我们只是添加了通用量化。
您可以尝试的一件有趣的事情是 运行ning halts 本身使用 eval。这可能会产生加速、更好的终止属性或质量上的新功能，但当然需要根据 eval 的语义编写目标指令和 halts。例如。如果你删除双重否定，那么 \+ \+ 将不会普遍量化，如果你传播错误或以其他方式不符合默认的 left-to-right 策略，那么 (goal, false) 通用终止测试（PoP chapter on termination) 也行不通。