prolog - 错误: Unhandled exception: Out of local stack - Prolog

Question

我试图在 Prolog 中编写一个简单版本的 length/3。

如果你看看 length/2 的标准实现，它如下所示:

length([], 0).
length([Head|Tail], N) :-
    length(Tail, N1),
    N is 1+N1.

虽然我的代码使用几乎相同的想法，但我收到错误“超出本地堆栈”，我认为这是由于深度递归而发生的。我不明白为什么。我的代码:

mylength(_, [], 0).
mylength([H1|T1], [H1copy|T1copy], N) :-
    mylength([H1|T1], [T1copy], N1),
    N is N1 + 1.

Answer 1

您的谓词mylength/3有以下问题。我假设你想以 mylength(+,-,-) 模式运行它。那么就是第一个参数不是降序的情况。

问题是第二个子句，其中第一个参数 [H1|T1]头部中的内容不变地传递给相同的第一个参数主体中的谓词，与 length/2 中发生的情况相反。结果在无限递归中，由于给定的第二个参数 [T1copy]才不是匹配第一个子句。

无限递归可能会导致内存耗尽，因为 for例如，每次调用都会为 H1copy 生成一个新变量。具体错误消息取决于 Prolog 系统。

再见

PS:已经发现可能有问题当查询谓词时。有人收到单例警告对于 H1copy .

但是例如在最新的 SWI-Prolog 版本中，本地堆栈错误将需要一些时间，因为SWI-Prolog 进行碳水化合物收集。 ^C 和 g 之后我明白了:

Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.1.16)
Copyright (c) 1990-2014 University of Amsterdam, VU Amsterdam

Action (h for help) ? goals

[552,959] mylength([1, 2, 3], [[]], _G40)
[552,958] mylength('<garbage_collected>', '<garbage_collected>', _G40)
[552,957] mylength('<garbage_collected>', '<garbage_collected>', _G40)
[552,956] mylength('<garbage_collected>', '<garbage_collected>', _G40)
[552,955] mylength('<garbage_collected>', '<garbage_collected>', _G40)

我猜上面的意思是目前我中断了 Prolog 解释器调用堆栈的深度已经是 552959，即一半一百万!

运行几分钟后，我得到以下信息SWI-Prolog 中的错误消息:ERROR: Out of local stack .