Prologプログラミング: 自然数を定義する


Prolog の変わったプログラム例として, 自然数とその上の演算を定義するプログラムを紹介します.

自然数の定義

自然数 0, 1, 2, 3, ... を Prolog の項を使って 0, s(0), s(s(0)), s(s(s(0))), ... で表すことにします. つまり s(X) は X+1 を表す項です.

すると「 X が自然数である」ことを表す述語 nat(X) は次のように書けます.


    nat(0).
    nat(s(X)) :- nat(X).
このプログラムは引数に与えられた項が自然数になっているかどうかを チェックすることもできますし, 引数に変数を与えると,バックトラックするたびに 自然数を順番に生成することもできます.

    | ?- nat(s(s(0))).    /* s(s(0)) は自然数か? */
    yes
    | ?- nat(X).          /* X に自然数を生成する */
    X = 0 ? ;
    X = s(0) ? ;
    X = s(s(0)) ? ;
    (以下略)
練習問題1
「 X が偶数である」を表す述語 even(X) を定義せよ. ヒント: 0 は偶数です.また X が偶数なら s(s(X)) も偶数です.
練習問題2
「 X が奇数である」を表す述語 odd(X) を定義せよ.

足し算の定義

次に足し算を定義してみましょう. 足し算は次のように再帰的に定義できます.

    x+y = y            (x=0のとき)
        = s(x1+y)      (x=s(x1)のとき)
この定義に基づいて, 「 X+Y=Z である」ことを表す述語 plus(X, Y, Z) を定義してみます.

    plus(0, Y, Y).
    plus(s(X), Y, s(Z)) :- plus(X, Y, Z).
このプログラムは,与えられた 2つの自然数の和を求めることもできますし, 与えられた自然数を 2つの自然数の和に分解することもできます.

    | ?- plus(s(0), s(s(0)), Z).  /* 1+2 を求める */
    Z = s(s(s(0))) ? 
    | ?- plus(X, Y, s(s(0))).     /* X+Y=2 となる X, Y を求める */
    X = 0,
    Y = s(s(0)) ? ;
    X = s(0),
    Y = s(0) ? ;
    X = s(s(0)),
    Y = 0 ? ;
    no
さらに plus(X, Y, Z) の X と Z を与えれば, 引き算を計算するのにも使えます. ただし X > Z のときは,当然ともいえますが,失敗します.

    | ?- plus(s(0), Y, s(s(s(0)))).  /* 3-1 を求める */
    Y = s(s(0)) ? 
    | ?- plus(s(s(0)), Y, s(0)).     /* 1-2 を求める */
    no
また「 X が Y 以下である」を表す述語 le(X, Y) は次のように 定義できます.

    le(X, Y) :- plus(X, _, Y).
練習問題3
「 X は Y より小さい」を表す述語 lt(X, Y) を定義せよ.

掛け算の定義

次に掛け算を定義してみましょう. 掛け算は次のように再帰的に定義できます.

    x*y = 0            (x=0のとき)
        = (x1*y)+y     (x=s(x1)のとき)
この定義に基づいて, 「 X*Y=Z である」ことを表す述語 times(X, Y, Z) を定義してみます.

    times(0, _, 0).
    times(s(X), Y, Z) :- times(X, Y, Z1), plus(Z1, Y, Z).
このプログラムは,与えられた 2つの自然数の積を求めることもできますし, 与えられた自然数を 2つの自然数の積に分解することもできます. ただし,分解の最後で無限ループに入ってしまいます.

    | ?- times(s(s(0)), s(s(0)), Z).  /* 2*2 を求める */
    Z = s(s(s(s(0)))) ? 
    | ?- times(X, Y, s(s(0))).        /* X*Y=2 となる X, Y を求める */
    X = s(0),
    Y = s(s(0)) ? ;
    X = s(s(0)),
    Y = s(0) ? ;      /* この後,無限ループで止まらなくなる */
これは,再帰呼び出し times(X, Y, Z1) のときに, すべての引数が未定義になることが原因です. もともと 1 番目の引数 X についてだけ再帰的に定義したので, 他の引数についてうまくいくとは限らないわけです.

分解についても, ちゃんと止まるようにプログラムを書換えることもできますが, かなり技巧的なので,ここではこれ以上の説明はしません.

割り算の定義

次に割り算を定義してみましょう.

次の述語 quot(X, Y, Q, R) は X を Y で割った商 Q と余り R を求めます.


    quot(X, Y, 0, X) :- lt(X, Y).
    quot(X, Y, s(Q), R) :- plus(Y, X1, X), quot(X1, Y, Q, R).
実行すると次のようになります.

    | ?- quot(s(s(s(s(s(0))))), s(s(s(0))), Q, R).
    Q = s(0),
    R = s(s(0)) ? 

素数

自然数 N が素数であるのは, N が 2 以上で,かつ 2 から N-1 までのどんな自然数でも割り切れないときです.

そこで,まず N が 2 から M までのどんな自然数でも割り切れないことを 表す述語 df(M, N) を定義します. この述語を使うと,素数であるかどうかを判定する述語 prime は 次のように定義できます.


    prime(s(X)) :- df(X, s(X)).
述語 df は次のように再帰的に定義できます.

    df(M,N) <--> true                   (M=1のとき)
            <--> dnd(M,N) /\ df(M-1,N)  (M>1のとき)
ここで dnd(M, N) は N が M で割り切れないことを表します.

述語 df を Prolog で書くと次のようになります.


    df(s(0), _).
    df(s(s(M)), N) :- dnd(s(s(M)), N), df(s(M), N).
また N が M で割り切れないことは quot(N, M, _, s(_)) で確かめることが できますから,述語 dnd は次のようになります.

    dnd(M, N) :- quot(N, M, _, s(_)).
では,どんな自然数が素数かを調べて見ましょう.

    | ?- nat(N), prime(N).
    N = s(s(0)) ? ;                                  /* 2 */
    N = s(s(s(0))) ? ;                               /* 3 */
    N = s(s(s(s(s(0))))) ? ;                         /* 5 */
    N = s(s(s(s(s(s(s(0))))))) ? ;                   /* 7 */
    N = s(s(s(s(s(s(s(s(s(s(s(0))))))))))) ? ;       /* 11 */
    N = s(s(s(s(s(s(s(s(s(s(s(s(s(0))))))))))))) ? ; /* 13 */
    .....
うまく動いているようです.バンザイ!
最初に戻る 前へ