这个代码是尾递归的吗？

Question

我正在尝试为Prolog中的第6天AdventCode编写解决方案.(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中运行时,我得到"ERROR:Out of local stack".所以有一个堆栈溢出,但是当我查看代码时,它看起来像尾递归.add_light并且gen_lights是相互递归的; 不确定这是不是一个问题.

我尝试使用调试器检查调用,但显然SWI-Prolog在使用时关闭了尾调用优化trace,因此没有帮助.

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

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

Answer 1

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

您可以通过多种方式改进确定性。最丑陋和最容易出错的方法是 !/0在一些战略位置添加：要小心这一点，因为这会破坏代码的许多漂亮的声明属性。

稍微好一点，但也几乎总是声明性错误的是使用 if-then-else 等功能。

更安全、更通用的方法是使用clpfdzcompare/3约束等功能。