Prolog (3)

簡易電卓を作成するとき、優先括弧に"(",")"という表記を使いました。実はPrologの仕様で(,)と.は自由なアトムとして使うことが出来ないからです。ところで、このダブルクオーテーションで囲んだ表記法ですが、一般的な言語では文字列リテラルと解釈されます。しかしPrologでは厳密な文字列型というオブジェクトは存在しません。一見文字列のようなこの値は、述語名や定数などと同様、小文字から始まるアトム型で、その別表記に過ぎません。同時に、データ上は数値リストとして扱うことが可能です。

リスト中に文字と数字が並ぶ際には上記の事を注意しなければいけません。

?- [X] = "(".
X = 40 ;
No

というように、リスト要素をマッチングして行くと思わぬところで単一化されてしまいます。これを除こうと思っても、実際に数値なのでnumber/1は使えません。但し[X]全体をマッチしてやればnumber/1はfalseとなります。

アトムの文字列表記が数値リスト(ASCII値となります)であることを利用して、シーザー暗号を作ってみましょう。変換部分はそのままです。

translate([], []).
translate([X|R], [X1|R1]) :-
    plus(X, 3, X1),
    translate(R, R1).

アトムとその文字列表記の変換にはatom_codes/2を利用します。他にもchar_code/2やnumber_codes/2などが仕様にあります。ちなみにこの述語の引数をどちらも変数にすると例外が発生しますから、暗号のエントリ述語はこんな風に書きました。

caesar(Flat, Unflat) :-
    ((nonvar(Flat),
      atom_codes(Flat, C1));
     (nonvar(Unflat),
      atom_codes(Unflat, C2))),
    translate(C1, C2),
    atom_codes(Flat, C1),
    atom_codes(Unflat, C2).

平文も暗号文も可逆入力ですが、なんだかちょっと冗長ですね :)

Prolog (2)

前回は四則演算だけ行う簡単な電卓を作成しました。四則演算だけと言っても、せめて'(',')'は使えないと不便ですので今回はあれを拡張していくプロセスを紹介します。

'(',')'で囲まれた数式は外の部分より先に計算しなければいけません（あーでもCall by Needな言語ではそうとも限らんでしょうけど）。ので、これを検知して区間を取り出してcalcに渡してやれば良いだけだよね、と考えます。

でも今回も天邪鬼をして、再帰的に毎回'(',')'を探して区間を抽出する方法を辞めるとしましょう。前回の実装では、数式リストを先頭から順番にマッチングしていくというステージを2回行っていました。もしこのステージ毎に先行計算区間の抽出を行うと馬鹿正直に計算量が増えます。リストを何度もスキャンするようなことはせずに、漢らしく（?）ステージごとに1パスで行く実装にします。

とは言うものの、最初はえらく手続き的で冗長な記述になってしまいました。スタックをパスごとにたらい回して計算するような事を書いたんですが、最初に言ってる漢らしさ（?）が感じられなかったので破り捨てました。でも絶対にどうしてもパス間で共有したい変数があったので、論理の起点を次のように変えてみました。

calc(Exp, Ans) :- calc0([], Exp, [Ans]).

calc0はcalc1とcalc2を制御する論理ですが、NILが渡されている最初の引数には演算して問題の無いTodo式（計算する式）が入ります。二つ目の引数は、まだ演算していないし中身もまだ見ていない数式が入ります。二つ目は継続点になるわけですが、前方からTodoに詰めて行くことで、継続位置は単調後退するようにすれば、計算量は固定長ですよね（定数がでかいのはさて置き）。最低限これだけの情報があれば、式をパースしつつ計算を回すことが出来ます。

まず具体的に演算を実行する部分です。具体的にってことは、継続位置が最後尾に来ているハズなので次のようになります。

% calc0/3
calc0(Todo, [], Ans) :- calc1(Todo, Tmp), calc2(Tmp, Ans).

続いて簡単なところを先に固めましょう。'(',')'が出てこない部分はそのままTodoに詰めます。これは単純。

calc0(Todo, [X | Cont], Ans) :-
    not(X = "("), not(X = ")"),
    append(Todo, [X], T1),
    calc0(T1, Cont, Ans).

では式をスキャンしていて'('が出てきたら、それまで続いていたTodoとは関係なく、先行して別途計算しないといけませんから、

calc0(Todo, ["(" | Cont], Ans) :-
    calc0([], Cont, A1),
    calc0(Todo, A1, Ans).

というようにして、後続の式をとりあえず新しい式としてcalc0に渡します。その答えを見て行く形にしようと思うのですが、ここでA1の中は')'の後にある式がそのまま"手付かず"で入っていなければなりません。そこで、

calc0(Todo, [")" | Cont], Ans) :-
    calc0([], Todo, A1),
    append(A, Cont, Ans).

として')'を発見したらそこまでのTodoを計算して、Todoの答えと')'以降の式を繋げた数式リストを返すよう書いてやります。'('にマッチングすると新しいcalcが計算されるということがポイント（同様のことをSchemeでやれば当然ながらクロージャを生成する感じですかね）。

これまでのコードをマージするとこんなかんじです。前回のロジックは一切変更していない点がポイントです。

?- calc([2,*,"(",1,+,"(",2,-,5,")",")",+,5], Ans).
Ans = 1 ;
No

正しい答えがただ1つ得られました。

このように、自分が欲しいと思う仕様を思い描いてみて、それが問題の全ての局面をカバーするよう、条件を網羅・記述（MECE... MECE... MECE...）していくのがPrologによるプログラミングのコツだと思います。