prolog - 这段代码是尾递归的吗？

Question

我正在尝试在 Prolog 中为 AdventCode 第 6 天编写解决方案。 ( http://adventofcode.com/day/6 )

以前，我编写了一个动态创建和替换谓词的解决方案，以跟踪灯光。不出所料，它相当慢，所以我决定尝试使用更“函数式”的风格来编写它；即创建一个包含所有灯的列表，然后操作该列表。

我正在尝试构建初始列表，该列表由一百万个元素组成，每个元素为 light(X, Y, Status) .我想我会从一个列表开始 [light(0, 0, off)] ，然后为其添加新术语。为此，我查看列表的第一个元素，然后确定下一个元素应该是什么，然后添加它。重复。

我有一个谓词 next_light/2这需要一盏灯并确定下一个灯(要预先准备)应该是什么。如果不再需要添加灯光，则返回 done :

next_light(light(X, Y, _), NextLight) :-
    X < 999,
    NextX is X + 1,
    NextLight = light(NextX, Y, off).
next_light(light(999, Y, _), NextLight) :-
    Y < 999,
    NextY is Y + 1,
    NextLight = light(0, NextY, off).
next_light(light(999, 999, _), done).

然后我尝试使用以下代码构建列表:

init_lights(Lights) :-
    gen_lights([light(0, 0, off)], Lights).

gen_lights(Lights, AllLights) :-
    [Light|_] = Lights,
    next_light(Light, NextLight),
    add_light(Lights, NextLight, AllLights).

add_light(Lights, done, Lights).
add_light(Lights, NextLight, AllLights) :-
    gen_lights([NextLight|Lights], AllLights).

但是，当我运行 init_lights(L) 时在 SWI-Prolog 中，我收到“错误:超出本地堆栈”。所以有一个堆栈溢出，但是当我查看代码时，它看起来是尾递归的。 add_light和 gen_lights是相互递归的；不知道这是否有问题。

我尝试使用调试器检查调用，但显然 SWI-Prolog 在使用 trace 时关闭了尾调用优化，所以这没有帮助。

(作为记录，当我将代码更改为使用 3 而不是 999 作为最大坐标时， init_lights(L) 似乎生成了正确的列表，并且没有挂起或导致堆栈溢出。)

我可能忽略了一些东西，但我没有看到它。欢迎任何提示! ^_^

Answer 1

您非常接近解决方案:您的子句是尾递归的，但尾递归优化仅在代码确定性时才有帮助!在您的代码中，next_light/2留下选择点，因为编译器无法判断哪些情况是互斥的，因此在尾递归调用后无法回收帧。

您可以通过多种方式改进确定性。最丑陋和最容易出错的方法是添加 !/0在一些重要的地方:小心这一点，因为这会破坏你的代码的许多很好的声明性属性。

使用 if-then-else 之类的功能要好一些，但也几乎总是声明性错误。

一种更安全、更通用的方法是使用像 zcompare/3 这样的特性。与 clpfd约束。