ぼくがかんがえたさいきょうの10さつ

@natsutanさんが言ってたから考えました。数値計算篇。

1. 数値計算の常識

計算機の小数点と数学の実数は全く別物だということを忘れがち。
また所詮近似だからと言って誤差が野放しだと思っても大間違い。
過大評価も過少評価もいけません。
本当の数値計算のはなしをしよう..

2. HP-15C Advanced Functions Handbook

基本を押さえたら実践、の前に歴史から学ぼう。
HP-15Cという古の名機を手に、限られた資源の使い方を知る。
ちなみにこっちが本機のマニュアル。

3. Modern Fortran Explained

過去だけに囚われていては人類は進歩しない！
現代を生きよう、これが明日から諸君の武器となる。
Fortran2008に準拠した言語詳説。
配列演算も演算子オーバーロードもローカルビューもアリだ。

4. Fortran 77 応用ソフトウェア作成技法

これで準備は整った、戦争だ！と思った貴様は甘い！！
何故この時代にFortranがあるのかを少しは考えてみろ。
過去の遺産があるから仕方無くに決まってるだろうが！
静的解析が容易？Cと比較すればそうだろう..
だがな！だったらどうして強い型付けの関数型言語でない？
諸君の仕事がたとえ現代兵器でなされようとも、
戦場は弓矢や落とし穴といったベトコン仕込みの罠で一杯だ。
だからリストやツリーのデータ構造がどう定義出来るかなんて話じゃなく、
どうDOするのかってことを身体で憶えるんだ。

5. Theoretical Numerical Analysis

悪い兵士は居ない。居るのは馬鹿な指揮官だ。
武器や技術が幾ら凄かろうと正しい判断が伴わなければ無意味だ。
生き残りたければ各自が有能な指揮官となって戦わねばならん！
プログラムの意味論が領域理論やラムダ計算を基礎とするように、
数値計算もまた線形代数と関数空間を基礎としていることを知れ。

6. Numerical High Performance Computers

ようこそ戦場へ！！だがまだここは前線じゃない。
諸君にはこれより奥地の湿地帯で展開している部隊に物資を届けてもらう。
まずは我々がこれまでどのようにこの地で戦ってきたかを知ってもらおう。

7. Iterative Methods for Sparse Linear Systems

ヒーホー撃てば当たるぜ！！ここじゃあ何でもヤったモン勝ちよお！
新しい関数系や補間法、補空間なんでも構わねぇ、試せばザッツライト。
大体は何かに当たるからそれでオールクリアだ畜生めっ！！

8. Direct Methods for Sparse Linear Systems

よくここまで辿り着いたな、物資は確かに受け取った。礼を言うぞ。
諸君の勇気をたたえ、ここは一つとっておきの武器をくれてやろう。
コイツを使えば原理的にはどんな敵も倒せる、計算機が十分タフならな。
後方の奴らはこんなもん使えないとほざきやがるがそんなことはない。
コイツこそが使えるんだ！上手く使えば幾らだって速くなる！
では敵地に単独潜入している人物にこの封筒を届けてくれ。検討を祈る。

9. Graph Algorithms in the Language of Linear Algebra

オットあぶないぜ兄ちゃん、もう一歩で竹ヤリが飛び出してくらぁ。
ここは四方敵だらけの未踏の地さ、味方は他にゃあ居ないぜ。
フムなるほど、情報ありがとよ。
礼と言っちゃあなんだが、ここで知ったことを教えるよ。
グラフを線形代数で考えるんだ。
場合によっちゃあ必要なメモリサイズやアクセスパターンが分かる。
いつか役に立つかも知れねぇよ。

10. スーパーコンピュータを20万円で創る

そして伝説へ..


どうしてこうなった？
もっとFEMとか流行の粒子法とか方法論をカバーすれば良かったかも。
あと数値計算で大事な非線形へのアプローチとか。
数値計算と言えばNumerical Recipesも原著3版は良くなってるらしいです。
ただ個人的にああいったカタログみたいなの薦めるのは気が引けます。
基礎を知らないと、式を追ったところでよく分からないと思うので。

Reading The Craft of Prolog

The Craft of Prologを読んでProlog的テクニックを学ぼうという集りがありました。
高等魔術の教理と祭儀

当日つかったスライドです。本を読む上で道案内になれば幸いです。


スライドを見ながら、あーだこーだらむだと話していると大体16時過ぎには終わってしまったので、後はかなり自由なトーキングセッションとなってしまい、ハイ、その辺は準備が不十分だったなーと痛感しています。ごめんなさい。

ranhaさんが、式は戻り値ほしーと言ってましたがPrologは記号処理をしたいのであって数値計算をしたいわけじゃないのでソレです。つまり、

?- X = 1 + 1.
X = 1 + 1.

?- X is 1 + 1.
X = 2.

:- op(500, xfy, +).
:- op(500, yfx, -).
C is A + B :- prim_add(A, B, C).
C is A - B :- prim_sub(A, B, C).

ということになっていて、計算の開始を指示しているのはis/2述語です。導出が始まると+-*/などの演算子はラベルのようなもので、prim_add/3述語(これは仮想的な述語ですが)のような処理系のプリミティブにぶつかると値が決まるという感じです。is/2をユーザ定義で勝手に拡張しても良い(arithmetic_function/1などで追加出来ます)のですが、実際はisp/2やism/2などユーザ側で独自なis/2述語を定義します。多項式演算ライブラリなどの実装で使われる場合が多いです。

kinabaさんが穴のある構造を使ったのってもっと無いかなー、と言ってたのですが、それは僕も探しているので思い付いたら教えて欲しいです。

Deux ou trois choses que je sais le calcul

「計算」という言葉について考えてみる
ranhaさんが計算とは"何か"を思索をされていて、その答えは恐らくまだ誰も分からないのだけど、計算機科学に携わる者だけでなく、およそ計算機に関わる誰もが心の中では、その"何か"を思っていることだと思う。だから私も個人的な"何か"を述べよう。

"何か"って既にあるのかしら、まだ無いのかしら？という点は考える余地があると思う。既にあるのなら、私達の思索という行為は遺跡の発掘のように、文字通り「既に」あって私達の思索という領域を支配している仕掛けを見つけ出す作業に他ならない。それは個人を超えて普遍的な仕掛けだろう。だがもしまだ無いのなら、私達の思索の領域は不可逆な経験を経る事で、橋を渡るようにして別の思索の領域に到達することになる。その経験を知識や概念と呼ぶのであれば、個人の思索は死によって頂点(或いは最大不動点)に達するのだろう。いずれにしろ物理法則へと、私達の思索は漸近する。いやしかし物理法則は、現象へと漸近させていくのが科学者の使命ではないか、、この話はよそう。その"何か"が既にあるか、或いはまだ無いか、ともかく時間を超越して存在を認めよう。

"何か"を語るとはどういう事か？と、自覚的に考えてみよう。その"何か"を理解する状況とはどのように可能なのか。三つ挙げてみる。

一つ目は、あるsyntaxを使って構成したモデルが"何か"だと述べる状況だ。これに従えば、計算機上のプログラムはTuring完全な言語であれば書くことが可能であり、そして書かれたプログラムだけが計算なのである。つまりは、その言語の中に留まる限りにおいて牧歌的な楽園が約束される。一体なにを心配する必要があろう、"その言語"で思うがままに計算をするが良い。だがやがてサピア・ウォーフ仮説の生き証人となるであろう。たとえバイナリこそが真実だと言ったところで、事態は変わらないのである。

二つ目は、syntaxと独立して"何か"が存在し、しかるべき形式でsyntaxへと埋め込まれる。従って、プログラムはその言語の構造との対応として現われる。だから私達は、ある"何か"が必ずまた別の姿形をして存在(対応)すると信じるのである。カリー・ハワード同型対応はその真理の一端である。であれば、大きな圏Cで同型対応τによる商圏C/τを考えることが"何か"への道かもしれない。

三つ目は、計算は存在などしない。私達は存在しないものについて、沈黙しなければならない。一方で存在するものはただ存在し、それを指して"何か"だと述べるのだ。だから私達は何の断りもなく、対象を認め、対象への算術を認め、再帰した算術を認め、任意のNについての再帰を認め、しかし無限を認めない。

「標準的自然数の定義」占い
こういったメタりっくな語り口を考えるなら、ここで挙げられている本が足掛りになるはずだ。でも幾らヘヴィにメタっても、私達が自由に使いたい"何か"との隔りは決して小さなものではないだろう。だって論理で見た代数はあまりに不恰好だから、、

# the Group Axioms in FO
∀x,y. ∃z. ∀w. S(x,y,w)⇔w=z
∀x,y,z. ∃u,v. ∀w. S(x,y,u)∧S(u,z,w)∧S(y,z,v)→S(x,v,w)
∀x. S(x,e,x)
∀x. ∃y. S(x,y,e)

"何か"によって私達はどう考えるのか？この答えは、あまりに私的過ぎる。論理的計算は証明プロセスを指すのであり、それはけっきょく記号操作だ(としか私は思わない)。また関数的計算も、形式がλ式であれ何であれ、やはり記号操作になる(としか私は思わない)。それらの言語"だけ"で考えている限り、それ以上の手立てを持ち合せてはいない。ところが計算する対象が見えると、舞台は関係と集合の世界に移る(だから小さな圏に限って議論すれば良いのだと云われたら、私は頷くかもしれない)。だが集合の海から関係の網を手繰り寄せることにも限界を感じるとき、チクタクと時を刻むオートマトンの世界が見えてくる。そこはもう工場のラインだ。算術回路の稼働率を上げるためにフローを組み変える日々、ふとラインの上に目をやると、流れてきたのは懐しきλ記号である、、

数学的には純粋な関係である関数も、計算として私達が意識するときは操作になる。歴史を紐解けば、超関数はおろか初等関数も長きに渡り厚いベールに包まれた存在であり、それらの扱いは一つの技術だった。関数というカラクリを分解し、論理という形で純化するに至る発端はFourierにあるだろう。Fourier級数の発見は「真理を読んだ」と語る程の衝撃を持っていた。やがて収束の神秘を紐解く過程で位相の概念が生まれ、微分操作を含んだより大きなクラスの作用素が構成されて行った。佐藤幹夫はアブストラクト・ナンセンスで記述した超関数を指して「実際にも計算できるよ」と言った、それが代数解析学となった。関数空間の理論は、黒魔術だった技術を計算機で構成可能な対象へと翻訳した。ここには確かに、概念が私達の思索の領域を広げた歴史を見てとることが出来る。私達の"何か"を、或いは計算機の"何か"を、黒魔術から構成的な対象へと翻訳する概念の発見を、一体誰が否定できようか？

逆数学と二階算術
ある数学的な活動を許す設定を探ることは逆数学として試みられている。いまある数学は二階算術によって十分に可能なのだそうだ(分類はもっと細かいけど)。

ちなみに、この話にオチは無いのだけど、、

meta_predicate (1)

2009年に入ってからSWI-Prologの更新速度が凄まじい。昨年からJan Wielemakerが5.7.xをVMの設計レベルから修正しており、結果として5.6.xと比較すると格段に高速な処理系へと進化している。しかし5.7.xの真価はVMの置き換えではなく、meta_predicate及びその背後にある新しいモジュールシステムにあると言っても過言ではない。

Defining a meta-predicate
meta_predicateを用いた柔軟なモジュールシステムはQuintus Prolog(SICSに権利譲渡)に源流を求めることが出来る。その設計はPrologと非常に親和性の高い形で与えられており、既に当時からDe factoとして受け入れられたのではないかと思われる。次期ISOへの提案として1990年のWGで議題に乗っており、現行の処理系を見てもコンセンサスが得られている状況だ。とは言え、Prolog産業の層の薄さの所為かどうか、正確な実装は今日に至るもそれほど多く存在しない(フリーではSWIとYAPのみ？)のも事実である。

Prologの知識ベースの問題点として、名前空間の欠落が挙げられる。しかし単純に名前空間を切るだけではあまり意味が無い、単一化候補の探索領域が過少に評価される為である。今日的な言語が供える多態性やdelegate機構を実現するには、適当なシンボルについて複数の空間を結合する必要がある。Quintusの実装はこの問題に良いインターフェースを与えた。例えば汎用的なソートコード(C++で言うtemplate化されたソートアルゴリズム)と、事実ベース(C++で言う個々のクラス)ごとに比較述語(operator<)を別々に定義し、後からこれを結合したいとしよう。モジュールシステムを欠いたPrologでは=../2(univ演算子)とcall/1を組み併せてソートに利用する比較述語を渡してやる必要がある。事実ごとに異なる比較演算子を用意することはコードの肥大化にも繋がる。

モジュールシステムのあるPrologでは、述語や演算子に対して探すべきモジュールを変数として扱うことが出来る。個々のモジュールではインターフェース相当の基本演算子や述語を上書きし、別のタイミングでこれを結合する。本質的に高階な論理の記述が可能となる。例えば次のようなものである。

% mysort.pl
:- module(mysort, [mysort/2]). % エクスポートする述語を指定
:- meta_predicate mysort(:, :). % モジュール変数を(:)で宣言
mysort(Mod:[], Mod:[]).
mysort(Mod:[H|T], Mod:L) :-
                      partition(H, Mod:T, Mod:Less, Mod:Big),
                      mysort(Mod:Less, Mod:L1),
                      mysort(Mod:Big, Mod:L2),
                      append(L1, [H|L2], L).
partition(_, Mod:[], Mod:[], Mod:[]).
partition(X, Mod:[Y|L], Mod:[Y|L1], Mod:L2) :-
                      Mod:(Y < X), % 古いPrologでこのコードは通らない
                      partition(X, Mod:L, Mod:L1, Mod:L2).
partition(X, Mod:[Y|L], Mod:L1, Mod:[Y|L2]) :-
                      \+ Mod:(Y < X), % 記述は柔軟に可能
                      partition(X, Mod:L, Mod:L1, Mod:L2).

% mylist.pl
:- module(mylist, [length/2, (<)/2]).
:- redefine_system_predicate(length(_, _)). % システム述語を上書き
:- redefine_system_predicate(_ < _). % 上に同じ
length([], 0).
length([_|T], N) :- !,
                      length(T, N0),
                      N is N0 + 1.
[_name1, Age1] < [_name2, Age2] :- !, % 自然な記述が可能
                      user:(Age1 < Age2). % 必要に応じ呼び元の意味が使える

% test_case
:- use_module(mysort).
:- use_module(mylist).
:- mysort(mylist:[ [taro, 19], [hanako, 11], [jiro, 14] ], mylist:Sorted).
Sorted = [[hanako, 11], [jiro, 14], [taro, 19]]
true.

% invalid_case
:- mysort(mylist:[ [taro, 19], [hanako, 11], [jiro, 14] ], Sorted).
 T Call: (7) mysort:mysort(mylist:[[taro, 14], [hanako, 11], [jiro, 10]], _G1778)
 T Fail: (7) mysort:mysort(mylist:[[taro, 14], [hanako, 11], [jiro, 10]], user:_G1778)
false.

変数がどのモジュールに属するかを指定しなかった場合、userモジュールに単一化されていることに注意。これはHaskellが型推論にユーザの助けを必要とする事と同様(とまでは言えないが類似的)の理由による。この理論的背景が80年代に論理プログラミングの意味論として議論され、特に極小モデル理論が用いられた。

Term Reduction in Prolog

Prologで回文判定に出るような無限ループを避ける工夫は二つあって、一つはメタなルール操作を書く事、もう一つはグローバルなI/Oを行う事。実際に行うとなると、どちらも骨の折れる作業なので、これ意識せず行えるのはETが誇る到達点だと思われる。例えばメタなルール操作を行う場合、次のようにしてルール集合に対する適当な項書き換えを行う。ルール自体のセマンティクスは eval_rule/2 で実行されることとなる。

reduct([], _Ans) :- !.
reduct(T1, T3) :-
    get_rule(T1, E1, Rule),
    eval_rule(E2,  Rule),
    append(E1, E2, T2),
    !, reduct(T2, T3).
get_rule(S1, S3, r(rule1(X, Y), rule1(X, Z))) :-
    retrieve(S1, rule1(X, Y), S2),
    retrieve(S2, rule1(X, Z), S3).
eval_rule([Y = Z, rule1(X, Y)],
    r(rule1(X, Y), rule1(X, Z))).
retrieve(L1, E, L2) :-
    member(E, L1),
    delete(L1, E, L2).

?- reduct([rule1(X, Y), rule2(Y, Z), rule1(X, Z), rule0(Z)], Ans).
..

もう一つのグローバルなI/Oに手を出せば、これはもう完全な手続き型言語となる。循環ループかどうかを区別可能な量のフラグを用意して、特定の述語を経過するごとに assert/1 や retract/1 を実行する。問題の状態遷移に固有のパタンが事前に決定可能であるならば、そのパタンに限り、確実にループを離脱する事が可能となる。

ここで物言いが入るのは、これらが反則技じゃないのか？ということ。しかし前者は扱う集合の世界が二階になっているだけで、実行されているのはSLD導出と全く同じ内容である。後者についてはI/Oがフラグの上げ下げに限定されている事から、適当な広さのファクトテーブルが存在すれば、これもまたSLD導出で解決される。また別の非難としては、これらが全てランタイムであるというものだが、Prologユーザの視点ではコンパイルも知識ベース読み込みも、全てをランタイムに引きずり下してあるのであって、実行時にコンパイルもリンクも出来て非常に便利なのである。他の言語では実行時に出来る事など限られているのだから。

ET Seminar

ET seminar's slide
まず講師をされた alohakun さんに敬意を表したいと思います。自分の研究について7時間総攻撃というのは生半可な事ではないから。ETの全体像から例を踏まえて説明して下さったおかげで、魔術的だった部分が明くなりました。それはそれとしてETの理論が詳らかになったかと言うと、幾つか疑問が残ったのでメモしておきます。

Formalization of the Equivalent Transformation Computation Model Kiyoshi Akama and Ekawit Nantajeewarawat
この論文では、SLD導出で無限時間後に証明可能な回文問題を、ETが有限時間でどう解決するかという例が示されています。まず引き合いに出されているPrologの例ですが、

palindrome(X) :- reverse(X, X).
?- palindrome([1|X]), palindrome([2|X]).
X = [] ;
.. % Infinite Loop

という風に無限ループに陥ります。これがETでは、次のルールを適当なタイミングで適用する事により解決を図っています。

rv(*x, *y), rv(*x, *z) => {=(*y, *z)}, rv(*x, *y).

Prologユーザの目線で考えるとこれは明かにメタな言及で、実現するにはメタインタプリタのレイヤでアトムの操作が必要になりますから、メタ操作を意識せず実現というのは一つの到達点なのだと思います。ただPrologユーザはこれを弱点というより利点だと考えている場合が割りとあります(但し、高階型の支援が無い事はPrologの明かな欠点)。

さて気になるのはこのETルールの、仕様からの生成可能性や、仕様に対する正当性の証明です。Prologでも勝手にルールを与えて(変えて)構わないなら、先の回文問題の無限ループは回避出来ます。特に、最近このルールが自動導出出来るようになったという事で、その成果は大変興味深いので論文が待ち遠しいのですが、その自動導出プログラムはTuring Completeなのか？また入力に対して計算量のオーダーはどの程度なのか？ルールが持つプライオリティはどのように決定可能か？この辺りにアドバンテージがあると、ETがPrologの理論的限界の先にあるという気分も分かるのですが、現時点ではPrologのランタイムを分断して議論しているという印象を持ってしまいます(あくまで個人的に)。

というのも、特定の仕様Dに対して正当なETルールがどれほど存在するのかは、決定が非常に難しいと思うからです。もし数が無限個か、或いは決定出来ない場合、ルール集合に半順序関係を入れるなどしなければ、ルール導出プログラムや仕様に対する正当性の証明の停止性を決定出来ないと思うのです。そうなると、ここで"ET処理系に対するHow"が入ってくるのではないでしょうか？

以上の疑問が残るものの、仕様空間とプログラム空間を分けて議論する事は圏論で説明したら綺麗になりそうだし、多重集合の書き換え系はそれ自体が便利なのでどんどん開発を進めて欲しいし、仕様の如何によってはリッチ(古典的)な否定が定義出来るのかもしれなくて便利な気がするし、といった感じでAfter Workに期待です。

ET Seminar 2008 (3)

等価変換理論集中セミナー2008
表現したい状態の集合を論理式で圧縮することで、(状態数増加による開発の)困難を克服するという流れでPrologの狙いを説明して来た。仕様として想定される状態(今風に云えばテストケースに近いかもしれない)から実装を導くという方針もPrologでは重視されている。しかし実際にPrologで規模を伴なうプログラムの開発を行うと、思ったほど楽ではない事が体験出来る。ではPrologの問題点は何なのか。

まず特徴的なPrologの表現形式だが、これはS式と思っても構わない。

human(socrates).
≡ (human socrates)

die(X) :- human(X).
≡ (:- (die X) (human X))

また連続するアトムに対する結合性などは op/3 で演算子ごとに定義出来る。

% current_of(400, yfx, '/').
:- op(1100, yfx, '<').
X / _ / X < 'hello'.
≡ (< (/ (/ X _) X) 'hello')

プログラムがこのように単純な構造を持つため、ヘッドに適当なアトム列を想定する事で、表記については柔軟な対応が可能だと分かる。しかしマクロやDSLを実現するにはこれだけでは片手落ちなのである。

マクロによって表現されたプログラムは、当然そのプログラムが実行される前に実行可能な形式、つまりマクロが展開された形になっている必要がある。しかしPrologには述語を制御する仕様は存在してもランタイムを制御する仕様は(部分的にしか)無いため、マクロの実行というセマンティクスをプログラムに埋め込んでやる必要が出てくる。典型的なDOループマクロを見てみる。

:- op(1100, xfy, do).
(foreach(Elem, List) do Template) :- do_loop(List, iter(Elem, Template)).
do_loop([], _Template).
do_loop([Value|Rest], Template) :-
    copy_term(Template, Copy),
    Copy = iter(Value, Goals),
    call(Goals),
    do_loop(Rest, Template).

?- foreach(X, [1,2,3]) do write(X), nl.
  call foreach(G1, [1,2,3]) do write(G1), nl
  call do_loop([1|[2,3]], iter(G1, (write(G1), nl)))
    call copy_term(iter(G1, (write(G1), nl)), G2)
    exit copy_term(iter(G1, (write(G1), nl)), iter(G2, (write(G2), nl)))
    call iter(G2, (write(G2), nl)) = iter(1, G4)
    exit iter(1, (write(1), nl)) = iter(1, (write(1), nl))
    call call((write(1), nl))
1
    exit call((write(1), nl))
    call do_loop([2,3], iter(G1, (write(G1), nl)))
      call copy_term(iter(G1, (write(G1), nl)), G5)
      .. 

展開したマクロと元のテンプレートで変数が被らないよう(健全性)にする copy_temr/2や、変数束縛(マクロ展開)を指示するための =/2 による単一化、そしてクエリ(展開されたマクロ)を実行する call/1 といった具合で、完全に手作業なのである。これを柔軟性と呼ぶのは些か憚られるだろう。

二階の述語論理も同様の手法で実現される。

map_list(_Fn, [], []).
map_list(Fn, [X|Xs], [Y|Ys]) :-
    G =.. [Fn, X, Y],
    call(G),
    map(Fn, Xs, Ys).
inc(X, Y) :- Y is X + 1.

?- map(inc, [1,2,3], L).
L = [2,3,4].

高階論理の実現に言語拡張が必要無い分、楽だと云えなくもない。型の判別には functor/3 や atom/1 や number/1 や compound/1 や var/1 などが用意されているから、これらを利用することで高階論理の型チェックも出来ない事はない。しかし全てはランタイムの振舞いとしてプログラミングされるだけであり、よく整備してもライブラリとしてパッケージ化するのが限度となる。ちなみに高度な例としてはDefinite Clause Grammarがある。

ここで(当時の)論理型プログラミングが持つ根本的な問題点が浮かびあがってくる。状態の集合を論理的に述べる事は出来ても、高階論理を書く事が出来ても、それらは全て実行時の結果としてしか得ることが出来ない。抽象化というプロセスについては何の支援も行なってくれないのである。例えばタイピングをどの時点でどのように与えるかという問題にしても、他の言語は動的か静的、また或いはリテラルベースか即値ベースかなどの選択肢があるのに対し、Prologが出来ることは精々、

speak(cat, 'meow').
speak(dog, 'woof').

という程度なのである。これを簡単と捉えるのか、ただ具体的なレコードと見るのか？

斯くなる特徴(有利・不利は状況次第だろうが)をPrologはプログラマに強制させるという点が、実際の開発では大きな障害となる。だがPrologの問題点は言語仕様だけでなく、その実行セマティクスにもある。
(続く)

ET Seminar 2008 (2)

等価変換理論集中セミナー2008
プログラムと論理との対応を利用することで、状態数の爆発を効率的に抑制出来ないかというのが論理型言語の提案だと述べた。残念ながらこの提案に対して理論的な支援は(当初は)弱く、特に関数型言語やオブジェクト指向がモジュラリティを打ち出した事と比較すれば不利な状況だったと思われる。ではこの状況で論理型言語、特にPrologがどのように戦いを挑んだのか、論理的によく書けているプログラムとはどのようなものなのか。今回はリスト結合という簡単なプログラムを例に、これを考えてみる。

Prologの教科書で必ず解説されるリスト結合述語が append/3 である。

append([], [], []).
append([1], [2], [1,2]).
.. % 果てしなく続く
?- append([1,2], [3], X).
  call append([1,2], [3], X)
  exit append([1,2], [3], [1,2,3])
X = [1,2,3].

可能な限りこの記述を並べる事で、リストの結合がどのようなものか(what)は記述できる。しかしこの調子ではリスト中の値が決まり決まっていて不便である。

append([], [], []).
append([I1], [I2], [I1,I2]).
.. % 果てしなく続く
?- append([a,2], [c], X).
  call append([a,2], [c], X)
  exit append([a,2], [c], [a,2,c])
X = [a,2,c].

こうすると少しはましになるが依然として不便に変わりはない。何故これが不便なのかというと、可能な状態の数が非常に多く存在する(もっとも資源の都合で有限ではある)ため、これらをプログラミングするのは(文字通り)骨が折れるからである。ここで冒頭に掲げた主張が活きてくる、つまり状態の爆発を抑制出来る述語を考えれば善いのである。

個々の具体的なリストから離れ、リストという集合を分類してはどうか、というメタな視点に立つ。大雑把な括りで見れば、リストというのは空っぽかそうでないのかに分類出来る。そしてリストの結合について望む事は、一つは空っぽリストと任意のリストの結合は任意のリストになる事。

%            ____       ____
% X:NIL + Y:|____| = Y:|____|
%
append([], Y, Y).

もう一つは当然、空っぽではないリストと任意のリストの結合についての言及である。そこでリストの分類に少し補足を加え、空でないリストについて少し細かく見る必要がある。空でないのであれば、少くとも1つの要素と任意のリストで結合出来るはずである。だから先の要件は、空っぽでないリスト(=少くとも1つの要素と任意のリストを結合したリスト)と任意のリストの結合は、少くとも1つの要素と任意のリスト(=任意のリストと任意のリストを結合したリスト)の結合となる。

%     _        ___        ____       _         ___       ____
% (X:|_| + Xs:|___|) + Y:|____| = X:|_| + (Xs:|___| + Y:|____|)
%
append([X|Xs], Y, [X|Z]) :- append(Xs, Y, Z).

斯くて教科書的な append/3 が出来あがる。この二つの述語で、先程までは延々と書き連ねる必要のあった状態集合を被覆しきる。ちなみに論理型プログラミングを発案したAlain Colmerauerらは、この述語の発見に一ヶ月を要したそうである。それでは実行過程を確認してみる。

?- append([1,2,3], [4,5], Z).
  call append([1|[2,3]], [4,5], [_G1|_G2])
    call append([2|[3]], [4,5], [_G3|_G4])
      call append([3|[]], [4,5], [_G5|_G6])
        call append([], [4,5], _G7)
        exit append([], [4,5], [4,5])
      exit append([3|[]], [4,5], [3|[4,5]])
    exit append([2|[3]], [4,5], [2|[3|[4,5]]])
  exit append([1|[2,3]], [4,5], [1|[2|[3|[4,5]]]])
Z = [1,2,3,4,5].

ここで見る事が出来る実行過程は、状態集合とどのような関係にあるのか？それは状態集合を空間として見た場合の連続した経路の事で、Prologが探索型の言語だと言われる所以である。畢竟するところ論理型プログラミングの根底には、オートマトンを如何に効率良く圧縮するかという思想が見え隠れするのである。

逆に状態集合ではなく実行過程から論理型プログラミングを見てみると、個々のステップ(というのは実体化された述語)は状態と状態を繋ぐ線であり、これはつまり継続の断片である。実行の側から見れば、論理的なプログラムとは可能な状態群を巡回する継続の集合である。そして可能な状態の抽象度を下げていけば、やがてこれは論理回路の可能な入出力値の集合となり、継続は要素の写像で、少し抽象度を上げれば機械語に対応する。

ここで視点を戻して、状態集合に立ち帰る。人間の視覚上でリストの結合は、片方のお尻に片方の頭が接する状態だと考えた方が遥かに直感的であろう。そもそもリストが空かそうでないかの分類の上で結合操作を行なう人間はまず居ない。何故なら人間はリストをもっと大雑把に「ひと連なりのもの」と捉えているからである。このときに「ひと連なりのもの」集合は、先のリストの状態集合とどのような関係にあるのか？

% リストと「ひと連なりのもの」の対応例
 ____     ____ __      __
|____| = |____|__.. - |__..
          ____ _     _
       = |____|_| - |_|
          ____ ___      ___
       = |____|___.. - |___..

       .. 果てしなく続く

お尻の先をあやふやなままにしたものが「ひと連なりのもの」だと考えると、リストと一対一対応を取ることは出来ないが、少くとも(ひと連なりのもの集合からリスト集合へは)全射ではある。この大雑把な状態の分類を利用すれば、リストの結合は非常に簡単になる。

dl_append(X-Y, Y-Z, X-Z).
?- dl_append([1,2|Xs]-Xs, [3,4|Ys]-Ys, Z-[]).
  call dl_append([1,2|_G1]-_G1, [3,4|_G2]-_G2, _G3-[])
  exit dl_append([1,2|[3,4|[]]]-[3,4|[]], [3,4|[]]-[], [1,2|[3,4|[]]]-[])
Z = [1,2,3,4].

ご覧のようにルールすら無しに、リスト結合の状態集合を被覆する事が出来る。ちなみにこのようなリスト表現は差分リストと呼ばれ、Prologの常套手段となっている。
(続く)

ET Seminar 2008 (1)

等価変換理論集中セミナー2008
かねて切望されていた集中セミナーが開かれる運びとなった。取りまとめをされたshinh氏、講師を勤められるalohakun氏、会場を提供して頂いたサイボウズに感謝の意を示すと共に、微力ながら事前知識の整理をお手伝いしようかと思う。事前知識というのは、計算論における述語論理のチューリング完全性と等価変換という魅惑のパラダイス(？)、この両者の間に横たわっている「名状しがたきもの」の事である。

まずPrologの理論的背景と実際のプログラムの接点から始めよう。Robert Kowalskiが見出したSLD導出の話である。プログラムと証明の対応から確認する。

+----+----------------------+----------------------------------+
|    |プログラム            |証明                              |
+----+----------------------+----------------------------------+
|前提|is_human(socrates).   |is_human(socrates)は真            |
|    |die(X) :- is_human(X).|die(X)は真 または !is_human(X)は真|
+----+----------------------+----------------------------------+
|命題|?- die(X).            |die(X)は真 となるXは何か?         |
+----+----------------------+----------------------------------+
|過程|die(X)                |!die(X)と仮定                     |
|    |  is_human(X)         |ならば !is_human(X)は真           |
|    |  is_human(socrates)  |しかし !is_human(socrates)は矛盾  |
|    |X = socrates.         |X = socrates ならば die(X)は真    |
+----+----------------------+----------------------------------+

プログラムの各述語と証明の各命題に対応が見てとれる。ここでプログラムの各述語の形式をホーン節と呼び、述語論理における正リテラルが高々一つの論理式を指す。細かな対応を補足すると次のようになる。

   is_human(socrates).     % ファクト
≡ ⇒ is_human(socrates)
≡ is_human(socrates)      % ホーン節

   die(X) :- is_human(X).  % ルール
≡ is_human(X) ⇒ die(X)
≡ die(X) ∨ !is_human(X)  % ホーン節

   ?- die(X).              % クエリ
≡ die(X) ⇒
≡ !die(X)                 % ホーン節

Prologの挙動を証明と対応付けるアルゴリズムはSLD導出(Selective Linear Definite Resolutin)という名で与えられている。これはプログラムに対応するホーン節集合を考え、二重否定によって真となる部分集合を検索するアルゴリズムである。

集合: (die(X) ∨ !is_human(X)), is_human(socrates)
入力: !die(X)
step-0 入力を選択節とする
  選択節: !die(X)
step-1 集合より選択節を簡約化可能なホーン節を選択節に加える
  選択節: !die(X) ∧ (die(X) ∨ !is_human(X))
step-2 簡約化
  選択節: !is_human(X)
step-3 集合より選択節を簡約化可能なホーン節を選択節に加える
  選択節: !is_human(X) ∧ is_human(socrates)
step-4 簡約化
  選択節: NIL
step-5 選択節が空なので入力は真
  出力: NIL ≡ !!die(socrates)

このように(二重否定による肯定を許可)して述語論理とPrologの実行解釈が結びつく。さて実はここからが本題で、論理式とプログラムの対応が具体的に定まるのなら、膨れ上がっていく状態の制御(how)は論理(what)を使うことで相当に抑制できるのではないか、という提案が浮上して来る。特にSLD導出で現れる"選択"と"簡約"の処理を上手く作り込む事で、制御の負担が減るのではないかと期待したのである。この"選択"と"簡約"をバックトラックとユニフィケーションによって実現することは言うまでもない。
(続く)

Continuation on Prolog

Prologを実装するために継続を利用する事例は数有れど、その逆は稀有である。当然の話ではあるが、基本的にPrologのセマンティクス自体は継続が無ければ実現出来ない機構であるため、改めて継続を明示的に利用するケースはほとんど無いからである。だがしかし、もし敢えてそれに及ばなければならないとしたら、そんな場合のちょっとしたコツもある。

% call_ac/2
call_ac(Pred, Cont) :-
    Pred =.. [_|Args],           % 節に単一化される引数を補足しておく
    Pred,                        % 述語が評価される
    Cont =.. [cont, Args, Body], % 次の継続に現時点で単一化されている変数を渡す
    Body.                        % 先の述語で確定した変数で継続を実行

?- call_ac(fact(10, Ans),
           cont([X, Y],
                (write('fact '), write(X), write(' is '), write(Y), nl))).
fact 10 is 3628800

Ans = 3628800,
X   = 10,
Y   = 3628800.

残念ながら Scheme のように現在の継続を取得する述語は ISO-Prolog に存在しない（当然だが現在の継続そのものはスタックに積まれている、更に直前に選択した継続の予備 = バックトラック候補も別のスタックに一つ割当られている）ため、明示的に継続を渡す必要がある。call/cc の代わりに call with a continuation である。この作業はいうなれば Prolog の実行手順を再現しているようなもので、順番に述語を評価し、束縛された変数を次の述語に束縛する。このような数珠繋ぎの関係こそが逐次的な関係の論理的な意味づけなのだ。

ゆの in Prolog

元ネタが分からないし表示を眺めても楽しさが伝わらないのだが、とりあえずPrologでも書ける事を示す必要を感じたので。なお、組込み述語を書き換えているので実行には注意すること。

:- encoding(utf8).
:- redefine_system_predicate('<'(_, _)).
:- op(1100, yfx, '<').
% '<'/2
'<'(X/_/X, Msg) :- atom_concat('ひだまりスケッチx365 ', Msg, X).

?- X / _ / X < '来週も見てくださいね!'.

X = 'ひだまりスケッチx365 来週も見てくださいね!'.

もしかすると最も短いんじゃないだろうかと思うのだが。あと、'<'の方が顔に見えるのだが..

Cost of Exception on C++

A curious AIX crash
Yaccに見つかった年代物のバグと違い、こちらは現在でも或いは今だからこそ遭遇する類のバグである。C++を実際の開発で運用する場合には非常に多くのルールを設ける必要がある。それは開発者のメンタルモデルや仕様との接続といった上位のセマンティックスから、プログラムを実行する命令プロセッサやアーキテクチャなどの下位のセマンティックスまでに渡り、現実的には数多くの罠が仕掛けられたレースを駆け抜けて行くようである。冒頭のリンクは、下のレイヤで見つかった罠を如何にして潜り抜けたかという話である。

Filodejは複数のプラットフォームに対応したアプリケーションを開発している。ある日発見されたバグはAIXでのみ発現するものだった。それは次の部分でSEGVを起こした。

virtual T const& get( unsigned int id ) const
{   <------------ The crash was right here before anything happen
    if ( id < static_cast( m_values.size() ) )
        return get_internal( id );
    throw ExceptionNotFound( LOCARG, id, count() );
    UNREACHABLE_RETURN( T() );
}

- Filodej's Linux primerより
対応する命令列は次の箇所。

0x39927250  7c0802a6    mflr  r0            ;; Function call prologue routine
0x39927254  93e1fffc    stw   r31,-4(r1)
0x39927258  93c1fff8    stw   r30,-8(r1)
0x3992725c  93a1fff4    stw   r29,-12(r1)
0x39927260  9381fff0    stw   r28,-16(r1)
0x39927264  9361ffec    stw   r27,-20(r1)
0x39927268  9341ffe8    stw   r26,-24(r1)
0x3992726c  90010008    stw   r0,0x8(r1)
0x39927270  9421ed30    stwu  r1,-4816(r1)  ;; Here was the place of the segfault

疑惑は r1 の値か -4816(r1) の値に絞られる。C++で開発をしていると、この手の不具合は"割と"見られる症状である。例えばプログラムが pthread を利用している場合がそうだ。スレッドスタックの伸張時、スタックに割当てられたインスタンスオブジェクトに未初期化フィールドがあるとこの手のバグに遭遇する。しかし今回のケースでは違っていた。

AIXに限らず、現代的なOSではguard pageという不正アクセスの検知領域が存在する。先のプログラムは -4816(r1) がこのguard page内を参照したためにSEGVを投げていたのだ。では何故そこを参照したのか？最初に載せたC++のコードで、例外を投げる部分が問題だったのである。氏が備えをした例外は、発生時にヒープ割当てを起こさないためにスタックに確保したオブジェクトだった。そしてこれはワイドキャラクターの配列として実装されていた。この比較的大きな例外オブジェクトはAIXが用意するスタックサイズを飛び抜けてしまい、またそれがヒープ確保されないがために、明示的にguard pageを叩いたのだ。結果的に見れば、これはソフトウェアをクラックする常套手段でもある。

Ancient bugs on Yacc

New Otto malloc helps spot ancient bugs
OpenBSDの開発に多大な貢献（最近はFFS2対応）をしているOtto Moerbeekが、先ごろの c2k8 hackathon で新しいmallocの実装を試みていた。これはページサイズを1として(1/2, 1)の領域を割当てる。もし MALLOC_OPTIONS がG（guard pagesを有効にする）で無い場合でも、アドレスの実体は mmap(2) でランダム化されているため、割当てた領域より後ろへの参照をより確実に SEGV として捉えることが出来る。実装は上手く機能していると思われた。

ところがNikolay Sturmはsparc64上で巨大なC++プロジェクトをコンパイル時にエラーが出る事を発見する。調査を始めたOttoは、どうやら obj/cp/parse.c 内の yyparse() が悪さをしている事を突き止める。

Yacc (Wikipedia)はルール毎にアクションを記述し、ルールに適合した要素を使って結果を定義する。もしアクションの記述が無い場合には、暗黙的に次の記述が補われ、ルールに適合した要素が結果としてそのまま保持される。

{ $$ = $1; }

そして、これに該当する yyparse() 内の処理が次の二行である。

yym   = yylen[yyn];
yyval = yyvsp[1-yym];

ここで yym が 0 の場合、スタックに積まれた先頭の要素、つまりカレントポインタの一つ上のエントリーが yyval に代入される。

この処理は例えば次のようなテキストをパースするとちょっとした問題が発生する。

A: /* empty */ { foo(); };

期待される要素が無いために yyval にはゴミが代入される。実際にその要素は使われる事が無いため、多くの場合は大した問題にはならない。しかしもしスタックが上限値に近い場合、つまり氏の malloc が提供するあそび部分（未割当領域）を参照すると SEGV が発生する。実際、バグが確認されたのはC++コードのコンパイル時、24bytes 先の要素を参照しようとした時点で氏の malloc が確保していたのは 16bytes 先までだった。

振り返ると、このバグはsparc64のページサイズが 8k だったから発見された。Yaccの標準スタックサイズはC++の場合に 24bytes*200=4800bytes で、これはページサイズの半分より若干大きく、ページサイズより小さい。結果、ページの移動が発生することなく正しく SEGV が検知されたわけである。

氏はこの部分を過去に遡って調べた。すると1975年リリースのUNIX 6th editionにおいて、同様の二行が発見されたのだった。

yypv  =- yyr2[n];
yyval =  yypv[1];

まだ -= を =- と表記していた頃の産物である。

An Arithmetic with Polynomials

多項式を始めとする抽象化された代数上の演算では、記号処理に長けたLispやPrologが本領を発揮する。しかし代数表現の実装としてどのような構造を選ぶかによって、その難しさには大きな差が出る。例えば多項式の場合、恐らく一般的で経済的な表現形式はRisa/asirの採用している分散表現多項式である。これは変数と主項ごとに次数を、主項ごとに係数を行列として保持する形式である。

  3x^3*z+x^2*y^3-5x*y-x*z+2y^3+y+z^2-2
=  c | x  y  z
  ---+---------
   3 | 3  0  1
   1 | 2  3  0
  -5 | 1  1  0
  -1 | 1  0  1
   2 | 0  3  0
   1 | 0  1  0
   1 | 0  0  2
  -2 | 0  0  0

この形式のメリットは明白で、多項式の四則演算が簡便に実装出来る点にある。例えば加算は次数（xyz列）が一致する行の係数（c列）を足せばよい。また乗算は、乗数と被乗数の主項毎に次数行の加算と係数の乗算を行えばよい。減算と除算は逆である。乗算と除算に関しては、同じ主項を生成する場合があるので後から正規形に正す必要がある。ここで云う正規形とは主項を辞書式順序付けで並べた形式を指す。一般的に多項式の表現は一意ではないため（また理論上の取り扱いのため）、このような措置を取る必要がある。

以下にPrologでの加乗算 実装例を示す。

% ordinal/2
ordinal(_C1*L1, _C2*L2) :- ordinal_aux(L1, L2).
ordinal_aux([], []) :- !.
ordinal_aux([X|_], [Y|_]) :- X > Y, !.
ordinal_aux([X|Xs], [X|Ys]) :- !, ordinal_aux(Xs, Ys).
?- ordinal(1*[1, 0, 2],
           1*[1, 1, 1]).
fail.
?- ordinal(1*[0, 1, 2],
           1*[0, 0, 3]).
true.

% norm/2
norm([], []).
norm([C1*L1|R1], P) :-
    !, norm_aux(C1*L1, R1, C2, R3), norm(R3, R2),
    (C2 = 0 -> P = R2;
     P = [C2*L1|R2]).
norm_aux(C1*_L1, [], C1, []).
norm_aux(C1*L1, [C2*L1|R2], C3, R3) :-
    !, norm_aux(C1*L1, R2, C4, R3), C3 is C2 + C4.
norm_aux(T1, [T2|R2], C3, [T2|R3]) :-
    !, norm_aux(T1, R2, C3, R3).
?- norm([2*[1, 0, 1],-1*[1, 0, 1]], Ans).
Ans = [1*[1, 0, 1]].

% add/3
add([], [], []) :- !.
add([], R2, R2) :- !.
add(R1, [], R1) :- !.
add([C1*L|R1], [C2*L|R2], [C3*L|R]) :-
    !, plus(C1, C2, C3), add(R1, R2, R).
add([T1|R1], [T2|R2], [T1|R]) :-
    ordinal(T1, T2), !, add(R1, [T2|R2], R).
add([T1|R1], [T2|R2], [T2|R]) :-
    ordinal(T2, T1), !, add([T1|R1], R2, R).
?- add([ 2*[2, 0, 1], 1*[0, 1, 0],-3*[0, 0, 2],              4*[0, 0, 0]],
       [-1*[2, 0, 1], 1*[0, 1, 0],              2*[0, 0, 1],-2*[0, 0, 0]],
       Ans).
Ans = [1*[2, 0, 1], 2*[0, 1, 0], -3*[0, 0, 2], 2*[0, 0, 1], 2*[0, 0, 0]].

% mult/3
mult(P1, P2, P3) :- mult_aux(P1, P2, P), !, norm(P, P3).
mult_aux([], _R2, []).
mult_aux([T1|R1], R2, P) :-
    !, mult_aux1(T1, R2, P1), mult_aux(R1, R2, P2), append(P1, P2, P).
mult_aux1(_T1, [], []).
mult_aux1(C1*L1, [C2*L2|R2], [C3*L3|R3]) :-
    !, C3 is C1 * C2, mult_aux2(L1, L2, L3), mult_aux1(C1*L1, R2, R3).
mult_aux2([], [], []).
mult_aux2([X|Xs], [Y|Ys], [Z|Zs]) :-
    !, Z is X + Y, mult_aux2(Xs, Ys, Zs).
?- mult([1*[2], 1*[1], 1*[0]],
        [       1*[1],-1*[0]],
        Ans).
Ans = [1*[3],-1[0]].

Loop fusion

手続き型言語において、複数のループを一つにまとめる事はかなり初歩の部類に入る最適化である。一見まったく異なるループでもちょっとした変数変換で一つに出来る事に気付くのは、プログラミングを始めた頃に誰もが通る愉しみだろう。FORTRANなどのひたすらにループ（だけ）を工夫する言語では、この手の最適化はコンパイラがかなり面倒を見てくれる。だが最適化とは違う目的で、ループ融合を使う場合も存在する。

foreach (var elem in arr) { do something.. }
for (var i = 0; i < arr.length; ++i) { do something.. }
    ↓
for (var i = 0; i < arr.length; ++i) {
    var elem = arr[i];
    do something..
}

この手のアプローチは論理型言語であるPrologでも有効である、ばかりでなく別の利点も存在する。例えばリストの長さを求める述語 len/2 とリストの要素が何番目にあるのかを示す述語 nth/3 を見てみよう。

% len/2
len([], 0).
len([_|R], N) :- !, len(R, N0), N is N0 + 1.
% nth/3
nth([X|_], 1, X).
nth([_|R], N, X) :- !, N1 is N - 1, nth(R, N1, X).

?- len(L, 3).
L = [_G101, _G102, _G103].
?- nth([1,2,3], I, 2).
ERROR: is/2: Arguments are not sufficiently instantiated

代入演算子 is/2 は副作用を伴う述語であるため、未初期化変数を伴っての呼び出しは例外を送出する。失敗していない len/2 は、初期化後の呼び出しであるために単一化の双方向性が保たれている。そこで、両者を上手く融合してやれば nth/3 でも双方向性が維持出来ないかと考える。

len(L, N) :- len_aux(L, 1, N).
len_aux([], _I, 0) :- !.
len_aux([_], I, I).
len_aux([_|R], I, N) :- !, I1 is I + 1, len_aux(R, I1, N).
?- len([1,2,3], Len).
Len = 3.
?- len(List, 3).
List = [_G172, _G178, _G184].

どちらを近づけるかは恣意的ではあるが、リスト長が分かるのは要素を全て確認した後であることを考慮すれば、len/2 には個々の要素が何番目であったかの情報が既に含まれていると考える事も可能である。そこで len/2 を nth/3 に近づけていく。カウントアップ時に is/2 が例外を投げないように、今が何度目の呼び出しかを記録する。アリティと節頭部の形が変わった部分は、呼び出し元で補正する。あとは頭部の変数名を揃えると、二つの再帰は融合出来る。

nth(L, N, E) :- nth_aux(L, 1, N, E).
nth_aux([], _I, 0, _E) :- !.
nth_aux([E|_], N, N, E).
nth_aux([_|R], M, N, E) :- !, M1 is M + 1, nth_aux(R, M1, N, E).
?- nth([a, b, c], I, E).
I = 1,
E = a;
I = 2,
E = b;
I = 3,
E = c

だが注意しなければならないのは、これはあくまで小手先のテクニックに過ぎない点である。このように、一つの述語の中に複数の論理が混在することはあまり望ましくない。双方向性がいつでも必要となるわけではない。寧ろプログラムの開発過程では想像だにしない（仕様として把握しきれていない）実行パスを生み、デバッグを困難にする。必要だと判断する限りに留めるべきである。

Gates may be gone, but the walls and bars

It's not the Gates, it's the bars (BBC)
B.Gatesの退任について数多くの人がコメントを出しているが、これが最も面白いコメントだろう。MITのAIラボで頬を濡らしFSFを今なお牽引しているあのRichard Stallmanのコメントである。なんというか、これはまぁBBCくらいしか載せないだろうなと思わないでもない。以下訳文、かなりテキトー。

Bill Gatesの退任に気を注ぐばかりに、重要な事を見逃している。本当に問題なのはGatesじゃない、Microsoftでもない、非倫理的に制限を課してくるシステムであり、Microsoftやそれに類する多くのソフトウェア企業が顧客に虐げてきた行為である。

このように言ったら皆さんを驚かすかも知れませんね、だってコンピュータに興味を持つ多くの人々は
Microsoftに強い思い入れがあることでしょうから。ビジネスマンや飼い犬である政治家たちは多くのユーザを従えた帝国を築いた業績に賞賛を浴びせます。この分野の外に居る方々は、コンピュータを安く速くそして便利なGUIを用意してくれるMicrosoftの先進性を信頼しています。

Gatesの発展途上国に対する健康医療分野での慈善事業は、幾らかの人々から賛同を得ました。LA Times誌は彼の基金が年間5-10%を活動に投じ、残りを企業の研究開発に投じていると報じました。でもその企業はそういった途上国で非難を受け、時には問題視されている疑いもあります。

多くのコンピュータ関係者は格別にGatesとMicrosoftを嫌っています。山ほど理由があるのです。

「資金調達」
Microsoftは継続的に競合へ圧力をかけ、現に過去三度も有罪判決を受けています。二度目の判決に際して免責を働きかけたGeorge W.Bushは、2000年度の選挙においてMicrosoftから多額の資金提供を受けています。
多くのユーザが"Microsoft税"を嫌っています。リテール品のコンピュータを買うと、例えWindowsを使わなくともその代金を支払わされるのです。

またDigital Restrictions Managementという機能は、貴方のファイルに貴方が自由にアクセスすることを禁止するためのものですが、これは制限の増えたVistaの中でも飛びっきりの新機能です。

「不当な非互換性」
そして不当な非互換性、他のソフトウェアとの相互運用が妨げられる問題があります。このためにEUはMicrosoftにインタフェース仕様の公開を要求しました。これを受けてMicrosoftは今年、文書に関するごつくて不明瞭で実装不可能な特許付きのオープン仕様をISOに通すため、これれを支持する委員たちを標準化委員会に送り込みました。EUは現在この件を調査しています。

これらの行為はもちろん容認し難いことです、でもそれはただ別々に起こったというわけではないのです。これは多くの人々が気付いていないより深遠な問題がもたらしている症状なのです。独占的ソフトウェアという問題です。

Microsoftのソフトウェアはユーザを分け隔て不自由に縛り付けるライセンス下で配布されています。ユーザは他人とコピーを共有出来ないために分断されます。ユーザはプログラマが読書きの出来るソースコードが提供されないために不自由を被ります。

もし貴方がプログラマでソフトウェアを変更したいとしても、貴方も他の誰もそれが出来ないのです。もし貴方がビジネスマンで必要に適したソフトウェアに変更するためにプログラマを雇いたくとも、それは出来ません。貴方の友達とコピーを共有すれば、それがたとえ隣人との親睦行為であっても、彼らは貴方を"海賊"と呼ぶでしょう。

「不公平なシステム」
Microsoftは私たちが隣人にする慈善行為を、他の船を攻撃するような非道徳的行為だと看做します。重要なことはMicrosoftがこのような不平等な社会システムを促進してきたということです。コピーソフトを共有したユーザを叱責した悪名高い公開文書で、Gatesは個人的に認知されています。その文書はこんな趣旨の内容でした。

もし僕が君たちを分け隔て、不自由にする事を拒むならば、もうソフトウェアを書かないし君は二度と手にする事が出来ないだろう。　僕に明け渡すか、君が消え去るかだ！

「システムを変えよう」
Gatesが独占的ソフトウェアを発明しなかったとしても、他の数千という企業が同じことをするでしょう。それは間違っているのです、誰がやったとしても。Microsoft、Apple、Adobe、そして他の残りの企業が貴方にソフトウェアを提供してきます。そのソフトウェアを貴方が買うことで、彼らはより力を付けていくのです。役員や企業が変わることは大して重要ではないのです。このシステムを変えなければなりません。

それがフリーソフトウェア運動の全てなのです。「フリー」とは制限の無い自由、共有や改変が自由に出来るソフトウェアを書いたり公開する世界です。

私たちは自由のために、組織的な取組みを、ある者は報酬を得、またほとんどの者はボランティアで、活動しています。私たちは既にGNU/Linuxというフリーなオペレーティングシステムを完成させました。

1984年、私がフリーソフトウェア運動を始めた頃、Gatesの手紙にはほとんど気を止めませんでした。でも他にも幾つか似た要求が来たものですから次のように返事をしました。

貴方のソフトウェアが私たちを分け隔て不自由に縛り付けるなら、どうぞもう書かないで下さい。　それが無くっても私たちは上手く行ってます。コンピュータの別の使い方を見つけ、自由を守り通すでしょう。

1992年、Linuxカーネルの導入によってGNUオペレーティングシステムが完成した頃はまだ、それを利用出来るのはコンピュータウィザードに限られていました。今やGNU/Linuxはユーザフレンドリーで、スペインやインドの一部では学校の標準OSとなっています。数千万の人々が世界中でそれを使っています。貴方も使えるのです。

門は崩れ去ったかも知れませんが、Gatesが築いた独占的ソフトウェアの壁は未だ高くそびえています。この壁を取り壊すとき、私たちはより高みに上るのです。

Loop-macro on Prolog

Joachim Schiimpf, Logical Loops, in 18th International Conference ICLP 2002, Copenhagen, Denmark, pg 224-238, Springer-Verlag, 2002.
反復的な処理をPrologで記述する場合は再帰を使う。その際にはわりとお定まりの形式で幾つか述語を余計に用意してやる必要があり、書く方は若干の疎ましさを感じないわけでもない。LISP系言語であればマクロを利用してパターンを展開するであろうが、Prologも同様である。簡単な例を挙げると、次のような展開が欲しい。

% BEFORE
?- write('L: '), (foreach(X, L) do write(X), write(' ')).

% AFTER
temp_aux([]) :- !.
temp_aux([X | T]) :- !, write(X), write(' '), temp_aux(T).
?- write('L: '), temp_aux(L).

複数の処理をまとめて一回の反復処理とする為に、述語do/2の右辺は結合性を持つ必要がある。演算子テーブルには次のように登録する。

:- op(1100, xfy, do).

続いて反復の度に束縛の実体を変更する必要があるので、引数と展開する反復とをセットにして再帰処理に持たせてやる。

(foreach(E, L) do Template) :- !, do_loop(L, iter(E, Template)).

各反復はリストの中身を一つづつ取り出して、これを変数に束縛し、再帰する。

do_loop([], _Template) :- !.      % 終了条件
do_loop([Value | Rest], Template) :-
    !, copy_term(Template, Copy), % 反復毎に束縛する環境は複製する
    Copy = iter(Value, Goals),    % 単一化で引数にヘッドで取出した値を束縛
    call(Goals),                  % 処理を実行
    do_loop(Rest, Template).      % 再帰

反復処理のコピーに対して束縛を行う事がポイントである。copy_term/2は必ずユニークな変数を割り振ってくれるので、いわゆる健全なマクロが実現される。foreach/2はかなり単純な処理であるからメリットは弱いかもしれないが、for-macroも同様の手法で作成出来る。do/2を汎用化して色々な反復子を許可したい場合は次のような一般化を行うのが定石である。

(Spec do Template) :-
    get_spec(Spec, Env, Iterator), !,
    do_loop(Env, iter(Iterator, Template)).

get_spec(foreach(E, L), L, E)) :- !.
get_spec(for(Init, Cond, Succ), ..) % 若干複雑なので略

マクロがLISPの専売特許だと思うのは井の中の蛙である。しかしPrologの問題はパフォーマンスである。

効率的なProlog: 実践ガイド

Efficient Prolog: A Practical Guide (filetype:pdf)
こういったTips集が書籍でもネットでも手に入り辛くなっているのもProlog不人気の一因であろう。これを読むと論理的というより処理系の実装レベルの話に思えるかもしれない（事実そう書いてある）のだが、計算機の効率とは要はそういう事なのであって、Prologも他の言語と同様である。

``効率的なProlog: 実践ガイド''のまとめ

1.宣言的であると同様に手続き的に考える

時にはホーン節を手続き的に考えることで、無限ループを回避出来る
ancestor(A,C):-ancestor(A,B),ancestor(B,C). は宣言的には正しいが、
手続き的に読めば ancestor(A,B) が ancestor(A,C) と単一化してループする
ancestor(A,C):-parent(A,B),ancestor(B,C). は手続き的に正しい

2.狭く探す

a(X)が1000候補、b(X)が10候補の述語の場合
a(X),b(X) よりも b(X),a(X) の方が検索する幅が狭い

3.単一化で済ます

length(L,N),N=3 よりも length(L,3)
length(L,3) よりも has_tree([_,_,_])
後述する理由から単一化で処理する方が速い

4.assert/retractは避ける

知識ベースの変更は遅い、さらにプログラム全体の論理が変わり誤動作を生む
一時的な情報は引数に渡し、assertは知識ベースの拡張（学習）に使う

5.トークン化を理解する

Prologプログラムの内部表現は他の言語とかなり異なる
プログラムは知識ベースのデータであり、数値かアトムか構造で構成される
数値は整数/小数のバイナリ表現
構造は参照スロットの配列と配列の長さおよび配列の先頭への参照
アトムはシンボルテーブルに登録された表現文字列への参照（ハッシュキー）
特にアトムは同じ表現なら全て同じ参照で実装されるので、
f('This atom contains a long long sentence of which ..',
  'This atom contains a long long sentence of which ..',
  'This atom contains a long long sentence of which ..').
という構造は f(a,b,c) より小さな実装となる可能性が高い

6.ストリング処理は避ける

文字列は数値（ASCIIやUNICODEなど）のリストとして表現される
リストは構造の一種で "abc"=[97,98,99]=.(97,.(98,.(99,[]))) のように実装される
ただしリスト構造は多くの処理系で上手く実装（最適化）される

7.末尾再帰を使う

ゴールの最後かつ、候補の最後かつ、サブゴールの他の候補が無い所で再帰する
こうするとバックトラック用にスタックを消費することなく再帰出来る
カットを使うとなお良い

8.並びを気にする

f(a,x).
f(b,x).
f(c,x).
は
f(x,a).
f(x,b).
f(x,c).
より早い、これは末尾再帰述語のヘッドの並びにも影響する

9.モード宣言を使う

変数のインスタンス化の向きは、宣言出来るなら行う
:- mode capital_of(+,-).
capital_of(georgia,atlanta).

10.リストの頭で済ます

リストの効率が良いのは（直接参照が効く）先頭の要素に限る
そうでない部分の単一化はバックトラックの可能性がある
末尾再帰のつもりでそうなっていない場合に注意
有名な例はリストの逆順を定義する述語である
reverse([],[]).
reverse([H|T],Result):-reverse(T,ReversedT),append(ReversedT,[H],Result).
上記は末尾再帰でなくコンシングが多発する
fast_reverse(List1,List2):-fr(List1,[],List2).
fr([Head|Tail],SoFar,Result):-fr(Tail,[Head|SoFar],Result).
fr([],SoFar,SoFar).

11.コンシングを避ける

Prologに限った事ではないが、新しくオブジェクトを作るにはコストがかかる
append等のリスト処理で、再帰のたびにコンシングするのは非効率である
差分リスト f([a,b|X],X) を使うことでコンシングを回避出来る
差分リストとはLISPのRPLACDである、ただしRPLACA相当の作業はコンシングを起こす

12.まとめ

High-level languageでも最適化時にはLow-levelを考える

Zipper on Prolog

Zipper (Wikipedia)
非破壊な構成を取る場合に、単方向リストだけで全てを賄う事は難しい。リスト中の任意な部分に着目したいし、またその部分を入れ替えたリストが必要になる場合も多い。Zipperはそういったニーズに応えるデータ構造である。或いは非常に資源の限られたハードウェアで巨大なデータを取り扱う場合、オンメモリなページとその前後への参照に対して編集操作をログとして処理する手段は、古くからある一種のZipperだと云えよう。後者は過去の記憶サイズによって非破壊な情報量に限度が伴うことになる。

PrologもLisp同様にList操作に優れている。パターンマッチの自由度が高い分、より強力だと云える。しかしListだけでは流石に不自由があるのでZipper（やそれの亜種）を用意することは多い。この時に差分リストを使っておくと、割と効率の良い実装となるだろう。

% zipper/2
zipper([[PreHead | Pre], PreTail]:Cursor:[[Next | Rest], RestTail],
       [[Cursor, PreHead | Pre], PreTail]:Next:[Rest, RestTail]).
% create_zipper/2
create_zipper([Head | Rest],
              [[ZPreTail], ZPreTail]:Head:[ZRest, ZRestTail]) :-
    append(Rest, ZRestTail, ZRest).

?- create_zipper([1,2,3,4,5], Z0), zipper(Z0, Z1), zipper(Z1, Z2), zipper(ZX, Z2).
Z0 = [[_G700], _G700]:1:[[2, 3, 4|_G712], _G712],
Z1 = [[1, _G700], _G700]:2:[[3, 4|_G712], _G712],
Z2 = [[2, 1, _G700], _G700]:3:[[4|_G712], _G712],
ZX = [[1, _G700], _G700]:2:[[3, 4|_G712], _G712].

?- create_zipper([1,2,3,4,5], Z0), zipper(Z0, Z1), zipper(Z1, P:C:R), zipper(Z, P:1:R).
..
Z = [[1, _G808], _G808]:2:[[1, 4, 5|_G820], _G820].

ちなみにこの実装だとZipper以上の機能が利用出来る。というのは、先行する差分リストの末尾である本来のリストの先頭に要素を加える事も、後続する差分リストの末尾である本来のリストの末尾に要素を加える事も可能だからである。つまり実を言えばこれは、Prologでの可変長リングバッファーの実装である。

差分リスト

Prologの基本的なデータ構造としてリストが利用出来る、という話は間違ってはいないけれども美味しいところを取りこぼしているような気がしてしまう。何故ならPrologの強みは、自由な表記がそのままデータ構造（Structure）として利用可能な点にあるからである。そしてこのStructureは単一化の対象となる。だからマクロのような事も、インタプリタのような事も簡単に出来るわけである。という事を考えていると、リストを世間一般的な形だけで考えているそのこと自体がもったいないのではないかと思えてくる。

Prologのリストは標準的な書き方以外でも扱える。それが差分リストである。一般的な書き方をしたリストは、先頭の要素から順序的に要素を取り出す必要がある、と同時にそれがリストというStructureの定義であった。ところでリスト同士であればその前後を接続したとしてもリストである事は想像に難くあるまい。逆に言えば、リストを途中で切断して分かれたものはどちらもリストであるということだ。この観点から定義したリストが差分リストである。

% List A = X - Y, List B = Y - Z
% => List A+B = X - Y + Y - Z = X - Z

% diff_append/3
diff_append([Xs, Ys], [Ys, Zs], [Xs, Zs]).

?- diff_append([[1, 2 | X], X], [[3 | Y], Y], Z ).
X = [3 | Y],
Z = [[1, 2, 3 | Y], Y].

あえて手続き的な解釈をすると、リスト末尾に未初期化領域への参照を確保しておくことで、リストの連結を参照先の初期化として意味づける、という事である。こうすることでリストの連結は非常に高速になる、と同時にリストの表示が自由変数混じりとなるデメリット（と考えるかどうかは状況次第だが）もある。

差分リストを用いてクイックソートを実装してみるとこんな具合になる。クイックソートの処理の大部分が分類した大小要素の連結であることを想像すれば、差分リストの意義は推察されよう。

% diff_qsort/2
diff_qsort(X, Y) :- diff_qsort(X, Y, []).
% diff_qsort/3
diff_qsort([], S, S).
diff_qsort([H | T], S1, S2) :-
    partition(H, T, Low, High),
    diff_qsort(Low, Low1, Low2),
    diff_qsort(High, High0, High2),
    High1 = [H | High0],
    diff_append([Low1, Low2], [High1 | High2], [S1, S2]).

% partition/4
partition(_H, [], [], []).
partition(H, [E | T], [E | Low], High) :-
    E < H, !, partition(H, T, Low, High).
partition(H, [E | T], Low, [E | High]) :-
    partition(H, T, Low, High).

?- diff_qsort([8, 4, 1, 5, 6, 9, 0, 3, 2], Sorted).
Sorted = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].