Prolog でメモをしながらフィボナッチ数を計算する

いつものように処理系は GNU Prolog です。

コード

fib.prolog を次のように用意します。

:- dynamic(fib/2).

fib(1, 1) :- !.
fib(2, 1) :- !.
fib(N, F) :-
  N1 is N - 1,
  N2 is N - 2,
  fib(N1, F1),
  fib(N2, F2),
  F is F1 + F2,
  asserta((fib(N, F) :- !)).

実行

GNU Prolog を起動します。

$ gprolog
GNU Prolog 1.4.5 (64 bits)
Compiled Jul 14 2018, 19:58:18 with clang
By Daniel Diaz
Copyright (C) 1999-2018 Daniel Diaz
| ?- 

コードを読み込みます。

| ?- ['fib.prolog'].

(1 ms) yes

計算します。

| ?- fib(5, F).

F = 5

yes

ここで clause/2 を使って fib/2 の定義の状態を確認します。

findall/3 を利用して任意の N と F の組み合わせに対して fib/2 で定義されているものを集めています。

| ?- findall((N, F), clause(fib(N, F), _Body), NFS).

NFS = [(5,5),(4,3),(3,2),(1,1),(2,1),(_,_)]

yes

コードでは変数を受けて計算をするケース以外では N = 1, F = 1, N = 2, F = 1 という組み合わせしか定義していませんが、fib(5, F) の実行後は N = 5, F = 5, N = 4, F = 3, N = 3, F = 2 という定義が存在していることがわかります。

さらに fib(10, F) を計算して様子を確認します。

| ?- fib(10, F).

F = 55

yes
| ?- findall((N, F), clause(fib(N, F), _Body), NFS).

NFS = [(10,55),(9,34),(8,21),(7,13),(6,8),(5,5),(4,3),(3,2),(1,1),(2,1),(_,_)]

yes

N = 10, F= 55 までの定義が増えていることがわかります。

retractall/1 ですべての定義を取り消します。

| ?- retractall(fib(_, _)).

yes

この状態で確認すると、すべての定義が消えていることがわかります。

| ?- findall((N, F), clause(fib(N, F), _Body), NFS).

NFS = []

yes

fib/2 を呼び出しても受理されません。

| ?- fib(2, F).

no

再びコードを読み込み定義の内容を確認します。

| ?- ['fib.prolog'].                                

(1 ms) yes
| ?- findall((N, F), clause(fib(N, F), _Body), NFS).

NFS = [(1,1),(2,1),(_,_)]

yes

最初の状態に戻りました。

解説

dynamic/2

dynamic/2 ディレクティブで fib/2 を動的に定義することを宣言しています。dynamic/2 で指定しなくても述語を動的に定義することはできますが、そのばあい fib(1, 1) :- ! といった記述も動的に定義する必要があります。

asserta/1

asserta/1 で動的に述語を定義しています。 asserta((fib(N, F) :- !)) の内側の括弧は fib(N, F) :- ! の部分が一つの引数とわかるようにするためのもので、省略することはできません。 asserta/1 は一連の定義の先頭にあたらしい定義を追加します。 ですので fib(5, F) を実行した後は次のように記述されたのと同じ状態になっています。

fib(5,5) :- !.
fib(4,3) :- !.
fib(3,2) :- !.
fib(1,1) :- !.
fib(2,1) :- !.
fib(N, F) :-
  % 略

よく似た assertz/1 は末尾に定義を追加します。

いつか読むはずっと読まない：Prolog Programming for Artificial Intelligence

1986 年に発行された「Prolog Programming for Artificial Intelligence」を二分冊した邦訳本。 一冊目を昨年入手して読んでいますが、改めて Prolog のおもしろさに気付かされます。

Prologへの入門 (PrologとAI)

AIプログラミング (PrologとAI)

二冊目は未だ入手できず。