7047


可算無限の結果すべてを列挙できるようなPrologの実装はあるのでしょうか？

例として自然数のペアを列挙するプログラムについて考えさせてください。  
もし、{(0,0), (0,1), (1,0), (0,2), (1,1), (2,0), ...}という順番で答えを列挙すれば、全てのペアを列挙できます。  
しかし、もし{(0,0), (0,1), (0,2), (0,3) ...}という以下のGNU
Prologと同じ順番で答えを列挙すると(1,1)のような結果を取り出すことができません。  
このような可算無限の結果を全て列挙するような研究、実装はあるのでしょうか？

[code]

    % cat nats.pl
    nat(0).
    nat(X1) :- nat(X), X1 is X + 1.
    
    pair_of_nats(X, Y) :- nat(X), nat(Y).
    % prolog
    GNU Prolog 1.3.0
    By Daniel Diaz
    Copyright (C) 1999-2007 Daniel Diaz
    | ?- ['nats.pl'].
    compiling /home/egi/prolog/nats.pl for byte code...
    /home/egi/prolog/nats.pl compiled, 4 lines read - 762 bytes written, 9 ms
    
    yes
    | ?- pair_of_nats(X,Y).
    
    X = 0
    Y = 0 ? ;
    
    X = 0
    Y = 1 ? ;
    
    X = 0
    Y = 2 ? ;
    
    X = 0
    Y = 3 ? 
    
[/code]


CC BY-SA 3.0
2015-02-10T05:38:47.270
6235
2015-02-24T21:11:32.527
8194
question
prolog
Prolog : 可算無限の結果を網羅的に列挙したい


以下は回答ではないのですが、興味深い内容ですので、それなりに書いてみたいと思います。

> このような可算無限の結果を全て列挙するような研究、実装はあるのでしょうか？

今現在、可算無限についてどの様な研究や実装が行われているのかは分かりません。  
無限を字義通りに解釈するなら、無限の出力を表示するには無限の時間がかかることになります。また、対象を有限の時間内で網羅できるのであれば、それは無限ではないという事になってしまいます。。。  
そうなりますと、結局は無限集合を(条件を付けて)有限化するしかないのではないかと思うわけです。例えば、上限値を設定するなどして、です。

[code]

    nat(0, _).
    nat(N, M) :- M > 0, nat(N1, M - 1), N is N1 + 1. 
    
    pair_of_nats(X, Y, XN, YN) :- nat(X, XN), nat(Y, YN), write((X, Y)), nl, fail.
    
    ?- pair_of_nats(X, Y, 3, 4).
    0,0
    0,1
     :
    1,0
    1,1
     :
    3,4
    false.
    
[/code]

しかし、これは有限な自然数同士の順列でしかない。。。それでは自然数全体ではどうしたら良いでしょうか。

**途中をざっくりと端折ってしまいましょう**

前述のコードを以下の様に変更して実行してみます。

[code]

    nat(0, _).
    nat(N, M) :- M > 0, nat(N1, M - 1), N is N1 + 1.
    
    pair_of_nats(X, Y, XN, YN) :-
      nat(X, XN), nat(Y, YN), write((X, Y)), nl,
      Y = YN, write((X, '↓')), nl, write((X, '∞')), nl, fail.
    
    pair_of_nats(X, Y) :- pair_of_nats(X, Y, 2, 2).
    pair_of_nats(_, _) :- write(('↓', '↓')), nl, write(('∞', '∞')), nl, fail.
    
    ?- pair_of_nats(X, Y).
    0,0
    0,1
    0,2
    0,↓
    0,∞
    1,0
    1,1
    1,2
    1,↓
    1,∞
    2,0
    2,1
    2,2
    2,↓
    2,∞
    ↓,↓
    ∞,∞
    false.
    
[/code]

「これは酷い」と思われるでしょう。 **その通りです** 。

余談ですが、言葉や記号というのは便利なものですね。限りのないモノ？を「無限」とか「Infinity」とか「∞」で括ってしまえるのですから。まぁ、「無限とは観念的なモノ(「概念」といえば良いのでしょうか)で現実に存在するわけではない云々」というのはその通りなのですが。


CC BY-SA 3.0
2015-02-11T06:35:49.217
6300
2015-02-11T07:59:11.463
2015-02-11T07:59:11.463
6235
answer


SWI-prolog での例ですが、when のような述語を使うことで遅延評価のようなことができます。  
それで、無限リストのようなものをつくることができます。  
質問を勘違いしてたらすみません。

[code]

    pair_list(X,Y, [Pair | Rest]) :-
        Pair = pair(X, Y),
        X == 0, X1 is Y + 1, Y1 is 0, when(nonvar(Rest), pair_list(X1,Y1, Rest)),!.
    pair_list(X,Y, [Pair | Rest]) :-
        Pair = pair(X, Y),
        X1 is X - 1, Y1 is Y + 1, when(nonvar(Rest), pair_list(X1,Y1, Rest)).
    
    list_test(N) :-
        pair_list(N, N, L),
        pair_print(L).
    
    %pair(0,3)が出現したら終了。
    pair_print([pair(0,3) | _]) :- !,
        write(pair(0,3)), nl.
    pair_print([Value | Rest]) :-
        write(Value), nl,
        pair_print(Rest).
    
[/code]

実行例

[code]

    1 ?- list_test(0).
    pair(0,0)
    pair(1,0)
    pair(0,1)
    pair(2,0)
    pair(1,1)
    pair(0,2)
    pair(3,0)
    pair(2,1)
    pair(1,2)
    pair(0,3)
    true.
    
[/code]


CC BY-SA 3.0
2015-02-11T11:57:06.193
6321
2015-02-11T11:57:06.193
5044
6235
answer


Prologですから、「集合の内包表記」を意味するデータ構造を持ち歩いて必要な場所で使うといったような意味でのデータ構造としては、無限のペアリストは表現する方法がない、と思います。この実装でてきる事といえば、ペア数の部分を切り取ってきたと思った時に、それが本当にペア数ならびの一部であるか検査するといった場合でしょう。

[code]

    ペア数の実装(0,0).
    ペア数の実装(X,Y) :-
    数を生成する(1,N),
    findall(M,between(0,N,M),L),
    重複順列(L,2,[X,Y]),
    N is X + Y.
    
    数を生成する(N,N).
    数を生成する(N_1,N) :-
    succ(N_1,N_2),
    数を生成する(N_2,N).
    
    重複順列(L,0,[]).
    重複順列(L,N,[A|R3]) :-
    N > 0,
    member(A,L),
    succ(N_1,N),
    重複順列(L,N_1,R3).
    
    %%%%%%%%%%%%%%%%%%%%
    
    ?- ペア数の実装(X,Y).
    X = Y, Y = 0 ;
    X = 0,
    Y = 1 ;
    X = 1,
    Y = 0 ;
    X = 0,
    Y = 2 ;
    X = Y, Y = 1 ;
    X = 2,
    Y = 0 ;
    X = 0,
    Y = 3 ;
    X = 1,
    Y = 2 ;
    X = 2,
    Y = 1 ;
    X = 3,
    Y = 0 ;
    X = 0,
    Y = 4 ;
    ・・・
    %%%%%%%%%%%%%%%%%%
    
    ?- ペア数の実装(X,Y),(2 is X+Y;X+Y>2,!,fail).
    X = 0,
    Y = 2;
    X = Y, Y = 1;
    X = 2,
    Y = 0;
    false.
    
[/code]


CC BY-SA 3.0
2015-02-16T23:25:20.513
6593
2015-02-17T13:14:20.577
2015-02-17T13:14:20.577
5175
5175
6235
answer


Prologは、その仕様として、解の探索をバックトラックを用いて深さ優先で行うことが定められています。そのため、Prologを自動定理証明系として見るとすると、Prologは完全性を持たないということになります。（つまり、求められない論理的帰結があるということです。）幅優先探索を行う処理系を作れば、それは完全性を持つことになります。([Prologの表示的意味論](https://github.com/suharahiromichi/doc/blob/master/cs_prolog_denotational_semantics.md))

_The Fun of Programming_ (Jeremy Gibbons and Oege de Moor
編、邦題『関数プログラミングの楽しみ』山下伸夫 訳)
第9章「論理プログラミングのためのコンビネータ」では、モナドを用いて論理プログラミングを実現する手法について述べていて、幅優先探索を行う技法についても言及があります。


CC BY-SA 3.0
2015-02-24T20:58:57.407
7047
2015-02-24T21:11:32.527
2015-02-24T21:11:32.527
3890
3890
6235
answer