高级编程

一个简单的求和程序

xxxxxxxxxx
7
1
sum_to(1, 1).
2
sum_to(N, R) :-
3
    N1 is N - 1,
4
    sum_to(N1, R1),
5
    R is N + R1.
6

7
?- sum_to(3,X).

运行结果是

xxxxxxxxxx
15
1
?- sum_to(3,X).
2
X = 6 ;
3
ERROR: Stack limit (1.0Gb) exceeded
4
ERROR:   Stack sizes: local: 1.0Gb, global: 30Kb, trail: 1Kb
5
ERROR:   Stack depth: 11,183,606, last-call: 0%, Choice points: 3
6
ERROR:   In:
7
ERROR:     [11,183,606] user:sum_to(-11183593, _7882)
8
ERROR:     [11,183,605] user:sum_to(-11183592, _7902)
9
ERROR:     [11,183,604] user:sum_to(-11183591, _7922)
10
ERROR:     [11,183,603] user:sum_to(-11183590, _7942)
11
ERROR:     [11,183,602] user:sum_to(-11183589, _7962)
12
ERROR: 
13
ERROR: Use the --stack_limit=size[KMG] command line option or
14
ERROR: ?- set_prolog_flag(stack_limit, 2_147_483_648). to double the limit.
15
?- 

原因是当运行到sum_to(1, R)的时候，尽管sum_to(1, 1)已经提供解，但是sum_to(N, R)的第二个定义还会运行，称为回溯(Backtracking)。

糟糕的是：这个运行是无法终止的。

解决前面的问题可以用剪切(Cut)技术，将程序改为

xxxxxxxxxx
7
1
sum_to(1, 1) :- !.
2
sum_to(N, R) :-
3
    N1 is N - 1,
4
    sum_to(N1, R1),
5
    R is N + R1.
6

7
?- sum_to(3,X).

剪切技术体现在"!"上, 相应的运行结果是：

xxxxxxxxxx
4
1
?- sum_to(3,X).
2
X = 6.
3

4
?- 

如果不用剪切技术, 还有另外一种解决方案，就是加入一句"\+(N = 1)"：

xxxxxxxxxx
6
1
sum_to(1, 1).
2
sum_to(N, R) :-
3
    \+(N = 1),
4
    N1 is N - 1,
5
    sum_to(N1, R1),
6
    R is N + R1.

运行结果是：

xxxxxxxxxx
5
1
?- sum_to(3,X).
2
X = 6 ;
3
false.
4

5
?- 

一个飞鸟的例子

xxxxxxxxxx
15
1
bird(sparrow).
2
bird(eagle).
3
bird(duck).
4
bird(crow).
5
bird(ostrich).
6
bird(puffin).
7
bird(swan).
8
bird(albatross).
9
bird(starling).
10
bird(owl).
11
bird(kingfisher).
12
bird(thrush).
13

14
can_fly(ostrich):- fail.
15
can_fly(X):-bird(X).

xxxxxxxxxx
2
1
?- can_fly(ostrich).
2
true.

要纠正这个错误，可以使用cut with failure组合，改为

xxxxxxxxxx
2
1
can_fly(ostrich):- !,fail.
2
can_fly(X):-bird(X).

再运行就对了

xxxxxxxxxx
2
1
?- can_fly(ostrich).
2
false.

考虑以下两种方法实现阶乘：

xxxxxxxxxx
5
1
fact_simple(0, 1):- !.
2
fact_simple(N, F) :- 
3
  N1 is N-1, 
4
  fact_simple(N1, F1),
5
  F is N*F1.

xxxxxxxxxx
2
1
?- fact_simple(16, F).
2
F = 720.

Prolog系统需要维持一个不断增长的堆栈。

使用加速器(Accumulator)，避免维护堆栈。

xxxxxxxxxx
6
1
fact_acc(N, F) :- fact_acc(N, 1, F).
2
fact_acc(0, Acc, Acc):- !.
3
fact_acc(N, Acc0, F) :- 
4
  N1 is N-1, 
5
  Acc is Acc0 * N, 
6
  fact_acc(N1, Acc, F).

xxxxxxxxxx
2
1
?- fact_acc(6, F).
2
F = 720.

无加速器版的实现不断调用自己完成计算，而有加速器版的实现使用Acc作为加速变量(中间变量).

计算Fibonacci数列

xxxxxxxxxx
8
1
fib(1,1):- !.
2
fib(2,1):- !.
3
fib(S,N) :-
4
  A is S-1,
5
  B is S-2,
6
  fib(A,C),
7
  fib(B,D),
8
  N is C+D.

xxxxxxxxxx
2
1
?- fib(38,X).
2
X = 39088169.

xxxxxxxxxx
8
1
fibo(N,F):-
2
  N > 0,
3
  fibacc(N,0,1,F).
4
fibacc(1,_,F,F):- !.
5
fibacc(N,A1,A2,F) :-
6
  N1 is N-1,
7
  Acc is A1+A2,
8
  fibacc(N1,A2,Acc,F).

xxxxxxxxxx
2
1
?- fibo(38,X).
2
X = 39088169.

加速效果在N=38的时候已经很明显，不用加速器运行时间很长，而使用加速器非常快。