偽クフ語解読器をPrologで書く。

偽クフ語とはなにか。

「白と黒のとびら」第11章をご参照ください。

本当はコード上も●と○の列で表現したかったのですが、あつかいがめんどうだったので●を 1 に○を 0 に置き換えてコードしています。 処理系はいつものように GNU-Prolog です

解読器

% 偽クフ語解読器
% decode.prolog

% 規則

% 1. S -> U 011 U (U 'ならば' U)
s(LHS, RHS) :-
  append(U1, [0'0, 0'1, 0'1 | U2], LHS),
  u(U1, T_U1),
  u(U2, T_U2),
  append(T_U1, ['ならば' | T_U2], RHS).

% 2. S -> M 01 U (M 'は' U)
s(LHS, RHS) :-
  append(M, [0'0, 0'1 | U], LHS),
  m(M, T_M),
  u(U, T_U),
  append(T_M, ['は' | T_U], RHS).

% 3. U -> M V
u(LHS, RHS) :-
  append(M, V, LHS),
  m(M, T_M),
  v(V, T_V),
  append(T_M, T_V, RHS).

% 4. U -> M 1 V (M 'に' V)
u(LHS, RHS) :-
  append(M, [0'1 | V], LHS),
  m(M, T_M),
  v(V, T_V),
  append(T_M, ['に' | T_V], RHS).

% 5. U -> M 1 M V (M 'に' M V)
u(LHS, RHS) :-
  append(M1, [0'1 | M2V], LHS),
  append(M2, V, M2V),
  m(M1, T_M1),
  m(M2, T_M2),
  v(V, T_V),
  append(T_M2, T_V, T_M2V),
  append(T_M1, ['に' | T_M2V], RHS).

% 6. U -> U 111 U (U 'そして' U)
u(LHS, RHS) :-
  append(U1, [0'1, 0'1, 0'1 | U2], LHS),
  u(U1, T_U1),
  u(U2, T_U2),
  append(T_U1, ['そして' | T_U2], RHS).

% 7. M -> A N
m(LHS, RHS) :-
  append(A, N, LHS),
  a(A, T_A),
  n(N, T_N),
  append(T_A, T_N, RHS).

% 8. M -> N
m(N, T_N) :-
  n(N, T_N).

% 9. M -> M 010 M (M 'か' M)
m(LHS, RHS) :-
  append(M1, [0'0, 0'1, 0'0 | M2], LHS),
  m(M1, T_M1),
  m(M2, T_M2),
  append(T_M1, ['か' | T_M2], RHS).

% 10. V -> 動詞のいずれか
v("1001", ['見た']).
v("1010", ['変わる']).
v("10100", ['変える']).
v("0011", ['昇る']).
v("1100", ['降りる']).
v("1101", ['留まる']).

% 11. N -> 名詞のいずれか
n("11010", ['１月']).
n("101010", ['２月']).
n("111010", ['３月']).
n("1001010", ['４月']).
n("1011010", ['５月']).
n("1101010", ['６月']).
n("00", ['満月']).
n("11", ['新月']).
n("1101", ['時']).
n("11100", ['希望']).
n("000", ['白']).
n("010", ['黄色']).
n("001", ['薄緑色']).
n("111", ['黒']).
n("101", ['紫色']).
n("110", ['青']).
n("00000", ['無']).
n("0111", ['上']).
n("1000", ['下']).
n("1111", ['ここ']).
n("0100", ['人']).

% 12. A -> 形容詞のいずれか
a("00000", ['正しい']).
a("00010", ['白い']).
a("01010", ['黄色い']).
a("00110", ['薄緑色の']).
a("11110", ['黒い']).
a("10110", ['紫色の']).
a("11010", ['青い']).

% 「クレージュ・レザン兄弟遺稿集（下） レザンの詩集」
poem("文 1", "00010001001011010110100111011110011").
poem("文 2", "11010110101011010").
poem("文 3", "10110111001011011110011").
poem("文 4", "110101101101011010").
poem("文 5", "000100001010110111001011011110011").
poem("文 6", "11110111001011101110100111011110011").
poem("文 7", "11010111101011010").
poem("文 8", "001100001011110111001011011110011").
poem("文 9", "00010001001011001110100111100011100").
poem("文10", "110101100101011010").
poem("文11", "000100001000110001001011100011100").
poem("文12", "111101101010110111001011100011100").
poem("文13", "01010001001011011110011").
poem("文14", "1101011101011010").
poem("文15", "101101101000110001001011011110011").
poem("文16", "000001001011100011100").
poem("文17", "110101110101011010").
poem("文18", "00000010001111111101").

% 結果を表示するための述語
show_sentence((Title, T)) :-
  format("~s ~p~n", [Title, T]).

% 解読した結果をすべて表示する
main :-
  findall(
    (Title, T),
    (poem(Title, S), s(S, T)),
    TS
  ),
  maplist(show_sentence, TS).

実行

第12章にあるように、それぞれの文は一意に決定できないので一つの文に対して複数の解読結果を出力しています。

$ gprolog --consult-file decode.prolog --entry-goal main --query-goal halt
文 1 [白い,満月,見た,ならば,黄色,に,変える,そして,上,に,昇る]
文 1 [満月,か,満月,見た,ならば,黄色,に,変える,そして,上,に,昇る]
文 1 [白,に,白,見た,ならば,黄色,に,変える,そして,上,に,昇る]
文 2 [時,は,２月,に,変わる]
文 2 [青い,新月,は,黄色,に,変わる]
文 2 [新月,か,新月,は,黄色,に,変わる]
文 3 [紫色の,新月,見た,ならば,上,に,昇る]
文 4 [時,は,紫色の,紫色,変わる]
文 4 [時,は,５月,に,変わる]
文 5 [満月,か,満月,か,紫色の,新月,見た,ならば,上,に,昇る]
文 5 [白い,満月,か,紫色の,新月,見た,ならば,上,に,昇る]
文 5 [満月,か,満月,か,紫色の,新月,見た,ならば,上,に,昇る]
文 5 [白,に,白,か,紫色の,新月,見た,ならば,上,に,昇る]
文 6 [黒い,新月,見た,ならば,紫色,に,変える,そして,上,に,昇る]
文 7 [時,は,３月,に,変わる]
文 8 [薄緑色の,満月,か,黒い,新月,見た,ならば,上,に,昇る]
文 8 [満月,に,下,か,黒い,新月,見た,ならば,上,に,昇る]
文 8 [薄緑色,に,白,か,黒い,新月,見た,ならば,上,に,昇る]
文 8 [薄緑色の,満月,か,ここ,は,青,か,青,に,黒,昇る]
文 8 [薄緑色の,満月,か,ここ,は,青,か,時,に,新月,昇る]
文 9 [白い,満月,見た,ならば,薄緑色,に,変える,そして,下,に,降りる]
文 9 [白い,満月,見た,ならば,満月,に,青,見た,そして,白,に,降りる]
文 9 [満月,か,満月,見た,ならば,薄緑色,に,変える,そして,下,に,降りる]
文 9 [満月,か,満月,見た,ならば,満月,に,青,見た,そして,白,に,降りる]
文 9 [白,に,白,見た,ならば,薄緑色,に,変える,そして,下,に,降りる]
文 9 [白,に,白,見た,ならば,満月,に,青,見た,そして,白,に,降りる]
文10 [時,は,４月,に,変わる]
文10 [青い,青,は,黄色,に,変わる]
文10 [新月,か,青,は,黄色,に,変わる]
文11 [満月,か,満月,か,薄緑色の,満月,見た,ならば,下,に,降りる]
文11 [白い,満月,か,薄緑色の,満月,見た,ならば,下,に,降りる]
文11 [満月,か,満月,か,薄緑色の,満月,見た,ならば,下,に,降りる]
文11 [白,に,白,か,薄緑色の,満月,見た,ならば,下,に,降りる]
文11 [満月,か,白い,満月,に,下,見た,ならば,下,に,降りる]
文11 [満月,か,満月,か,満月,に,下,見た,ならば,下,に,降りる]
文11 [白い,満月,か,満月,に,下,見た,ならば,下,に,降りる]
文11 [満月,か,満月,か,満月,に,下,見た,ならば,下,に,降りる]
文11 [満月,か,白い,薄緑色,に,白,見た,ならば,下,に,降りる]
文11 [満月,か,満月,か,薄緑色,に,白,見た,ならば,下,に,降りる]
文11 [白い,満月,か,薄緑色,に,白,見た,ならば,下,に,降りる]
文11 [満月,か,満月,か,薄緑色,に,白,見た,ならば,下,に,降りる]
文12 [黒い,新月,か,紫色の,新月,見た,ならば,下,に,降りる]
文12 [黒い,時,か,時,に,見た,ならば,下,に,降りる]
文13 [黄色い,満月,見た,ならば,上,に,昇る]
文13 [黄色,に,白,見た,ならば,上,に,昇る]
文14 [時,は,１月,に,変わる]
文15 [紫色の,新月,か,薄緑色の,満月,見た,ならば,上,に,昇る]
文15 [紫色の,新月,か,満月,に,下,見た,ならば,上,に,昇る]
文15 [紫色の,新月,か,薄緑色,に,白,見た,ならば,上,に,昇る]
文16 [無,見た,ならば,下,に,降りる]
文17 [新月,は,上,か,紫色,変わる]
文17 [時,は,青い,紫色,変わる]
文17 [時,は,新月,か,紫色,変わる]
文17 [時,は,６月,に,変わる]
文17 [青い,黒,は,黄色,に,変わる]
文17 [新月,か,黒,は,黄色,に,変わる]
文18 [正しい,人,は,ここ,に,留まる]
文18 [正しい,人,は,新月,に,新月,留まる]
| ?- halt.

Prolog たのしい。

いつか読むはずっと読まない：0 と 1 の Prolog

書籍のページ で第1章が公開されていますので、興味のある方はどうぞ。

白と黒のとびら: オートマトンと形式言語をめぐる冒険