使用 DCG 的斐波那契

Question

我正在尝试在 prolog 中使用 DCG 创建斐波那契数列。我有这个作为初学者，但我不知道为什么代码没有被执行。

下面是代码：

fib --> [0], [1].
fib --> [X, Y], {Z is X + Y}, [Z].

我收到一个错误，指出变量未充分实例化。我知道这个解决方案距离最终解决方案还很远，但是我只是在努力理解为什么这是不可能的。任何建议和意见将不胜感激！

Answer 1

效率不高，但时间短：

% Seed with initial 2 values
fib(1, 0) --> [0, 1].
% Get previous 2 values, then sum them
fib(S, P1) --> fib(P1, P2), { S is P1 + P2 }, [S].

swi-prolog 中的结果：

?- phrase(fib(F, _), L).
F = 1,
L = [0, 1] ;
F = 1,
L = [0, 1, 1] ;
F = 2,
L = [0, 1, 1, 2] ;
F = 3,
L = [0, 1, 1, 2, 3] ;
F = 5,
L = [0, 1, 1, 2, 3, 5] ;
F = 8,
L = [0, 1, 1, 2, 3, 5, 8] ;
F = 13,
L = [0, 1, 1, 2, 3, 5, 8, 13]
...

Answer 2

我同意@brebs的观点，即在没有DCG参数的情况下做到这一点是很困难的；如果第一个调用从列表中消耗了

[0,1]

，则下一个不带参数和输入的调用不会添加任何内容，并且会中断。

我能得到的最接近的是推回符号：

nextFib, [B,C] --> [A,B], { C is A+B }.

fib --> nextFib, ([] | fib).

其行为如下：

?- phrase(fib, [0,1|Fs], Rest).
Rest = [1, 1|Fs] ;
Rest = [1, 2|Fs] ;
Rest = [2, 3|Fs] ;
Rest = [3, 5|Fs] ;
Rest = [5, 8|Fs] ;
Rest = [8, 13|Fs] ;
Rest = [13, 21|Fs] ;
Rest = [21, 34|Fs] ;
...

这不是正确的输出，它正在消耗

[A,B]

并丢弃它们，将

[B,C]

推入输入，我们正在查看它们未消耗的情况。但正在以某种方式经历斐波那契数列。

---

为了收集它们而不是丢弃它们，我们又需要一个论证：

nextFib(A), [B,C] --> [A,B], { C is A+B }.

fib([F|Fs]) --> nextFib(F), ([] | fib(Fs)).

然后：

?- phrase(fib(Fibs), [0,1|Fs], _).
Fibs = [0|_1682] ;
Fibs = [0, 1|_1360] ;
Fibs = [0, 1, 1|_1366] ;
Fibs = [0, 1, 1, 2|_1372] ;
Fibs = [0, 1, 1, 2, 3|_1378] ;
Fibs = [0, 1, 1, 2, 3, 5|_1384] ;
Fibs = [0, 1, 1, 2, 3, 5, 8|_1390] ;
Fibs = [0, 1, 1, 2, 3, 5, 8, 13|_1396] ;
Fibs = [0, 1, 1, 2, 3, 5, 8, 13, 21|_1402] ;