2011-11-27

"On Lisp" Paul Graham 著

前書きには「既にLispに親しんでいることを前提としている」とある。「けして泥酔した初心者は手を出さないでください!」と聞こえてくるが、これも怖いもの見たさというものか。慣れない言語を読んでいると不思議な感覚に見舞われる。それは、片言の外国語を喋る時の感覚に似ていることだ。文法を考えずに、とりあえず知っている単語を並べてみる。これぞリスト型言語の極意というものか。プログラミング言語を学習するのに、構文を意識せずに読んでいるのも珍しい。これぞ構文のない言語と言われる所以か。
まずは、立ち読みから始める。釘付けになったのは、後方で紹介される実装例で、継続、マルチプロセス、非決定性アルゴリズ、そしてオブジェクト指向言語を装うCLOSである。しかもマクロで実装してやがる。驚くべきは、この古典言語がこれらの機能を具えられるほどの拡張性が既にあったということだ。これは、Lispを度外視してもじっくり読んでみたい。ついに衝動には勝てず、買ってしまうのであった。

本書の特徴は、半分以上がマクロ機能に割かれることである。これはプログラミング言語の書籍では珍しいのではないか。Lispはマクロ機能が強力だと聞くが、なるほど、なかなかの感動ものだ。関数型言語なのでもちろん関数についても書かれているが、あくまでも基本という位置づけでしかない。
「あるプログラミング言語のエッセンスを一文で伝えるのは難しいが、John Foderaroの言葉はかなりそれに近い。: Lispはプログラム可能なプログラミング言語である。」
独自の言語をLispで書いて、その言語でプログラムする。まさに「On Lisp!」というわけか。この本の不思議なところは、コードがたくさん埋め込まれているわりには、抽象的に眺められることである。ユーザ定義のマクロや関数が、あたかも組み込み構文や組み込み関数であるかのように映る。逆に言えば、ネーミングのセンスが悪ければ、たちまち読みづらいプログラムになる。それは、どんなプログラミング言語でも同じだけど...
Lispが強力なのは、様々な機能が集合体となっているからだという。動的メモリの割り当て、ガベージコレクション、実行時型指定、オブジェクトとしての関数、リストを生成する組み込みパーサ、リスト表現を受け付けるコンパイラ、インタラティブな環境などなど...しかし、これらの機能は切り売りされる。近年のプログラミング言語はLispの特徴を多く取り入れている。

マクロと言えば...アセンブラ言語から馴染んできたアル中ハイマーな古代人は強力な武器として崇めていた。もう20年ぐらい前になろうか、おいらは小規模なマイコン用プログラムを書いていた。16KBから32KB程度のもので、リアルタイムOSを導入するには大袈裟な規模だ。当時は「組込み系」なんて言葉も使っていなかった。この世界でもC言語が台頭しつつあったが、コンパイル効率が悪いために冗長度が大きく、メモリ資源に制約のある小規模システムでは致命的となる。構文解析や最適化の癖に合わせてコーディングルールを決めたりしたものだ...
アセンブラ言語の経験があれば、関数とマクロの実装の違いはすぐにイメージできるだろう。関数の実装は、変数の退避などが割り込み処理と似ていて結構面倒だ。CPUが持つ汎用レジスタに役割の規則を作ったりと、なにかと神経を使う。引数はC言語ユーザが嫌うポインタで渡す方が楽だったりする。その点、マクロは単純に展開されるだけなので、関数呼び出しのオーバヘッドがない。だが、呼ばれるたびに展開され、メモリを消費するので頻繁には使えない。また、余計な姿を隠蔽するのが得意なだけに、変数の束縛範囲まで曖昧にしてしまう。ただ、関数を呼び出すためのメッセージ役を与えると癖になる。要するに、マクロの主な役割は翻訳としての機能であった。
この点、Lispは呼び出し側から見てマクロと関数を区別しない。これだけでも強力な要因となりうる。おまけに、マクロ内の変数名が重複しないように、ローカル変数の生成機能(with-gensyms)まである。マクロでは変数名でいつも悩まされるので、うれしい機能だ。
更に、アセンブラ言語レベルでオブジェクト指向っぽいこともやっていた。オブジェクト指向なんて言葉も知らない時代だ。クラスのような雛形を関数で実装するとインスタンスになってしまうので、マクロの方が相性がいい。それは、本書で紹介されるCLOSでも味わえる。変数のアクセスは、マクロメッセージを経由し、set/get系で抽象化できる。カプセル化の概念も知らずに自然に変数を隠蔽していたような気がする。上位階層から眺めると、マクロメッセージが並んだ独自の言語に見える。まさに「On アセンブラ!」というわけだ。
しかし、アセンブラ言語はCPUのシリーズよって方言があるのが厄介である。そして、時代はC言語系へと流れていった。それでも、プリミティブな部分だけ言語に依存させ、マクロで隠蔽するやり方を好むのは変わらない。ちなみに、その頃からの弊害か?いまだに継承の概念は実装のイメージがしずらく、好きになれないけど。
...アル中ハイマーのマクロのイメージとは、こんなもんだ。しかーし、Lispのマクロ機能はそんな比ではない。頭は既にKernel Panic !!!

1. ボトムアップデザイン
どんなプログラミング言語を使ってもボトムアップで記述することはできる。ただ、Lispはそれをこなせる最も自然な器で、開発当初から拡張可能なように設計されてきたという。言語の大半は関数の集合体であるが、それらはユーザ定義のものと区別しない。関数もまたデータと区別されず、Lisp全体がリスト型データ構造となっている。
「ユーザがLispコードを生成するLisp関数を書けるということだ。」
ところで、人間が思考する上で言語の役割は大きい。思考を明確にしたければ、自己を操る言語で書き下ろしてみることだ。分かっているつもりでも、実際に記述してみると、案外分かっていなかったことに気づかされる。自然言語には、思考を整理し客観的な視点を与える役割がある。それは、プログラミング言語でも原理は同じであろう。実装できないものを仕様に盛り込んでも空論に終わる。ならば、プロトタイプを実際に書いてみる方が手っ取り早い。ウォーターフォール・モデルのような思考の一方向性が行き詰まりやすいことは、多くの設計者が知っている。デザインは書いているうちに進化していく。計画で最も重要なのは柔軟性ということになろうか。
本書は、Lispを柔軟性に最適な言語としながら、同時にLispユーザが堕落する可能性を指摘している。それは、言語とアプリの相性に敏感になり過ぎて、他の言語では柔軟性が得られないと思い込んでしまうことだ。なるほど、言語を宗教的に崇めると、逆に思考の柔軟性が奪われるというわけか。人類が絶対的な価値観に到達できないからには、万能で完璧な言語を編み出すことはできないだろう。誰もが英語かぶれになれば、人間社会の思考は英語的になる。言語は手段に過ぎないが、精神と結びつくとこれほど強力な武器もない。よって、個人の肌に合った言語を模索するしかあるまい。

2. 関数型プログラミング
関数型プログラミングが抽象化の可能性を大きくするのは、関数型を返り値とすることができ、関数型を引数に渡せるという特徴があるからであろうか。だから、無理やり一行に収められる。暗号文っぽくなるけど。関数がデータオブジェクトになりうるからには、オブジェクトはそれを呼び出す方法も提供される。Lispでは、それをapply関数が担うようだ。定義した関数をオブジェクトに対応させるために通常 #'オペレートを使うという。

 > (apply #'(lambda (x y) (+ x y)) '(1 2))

apply関数は、引数にリストを渡している。これが気に入らなければ、funcallを使えばいい。
 > (funcall #'+ 1 2)

「関数プログラミングとは、副作用ではなく、値を返すことで動作するプログラムを書くことだ。」
関数の基本的な思想は、副作用を期待するのではなく、返り値のためにあると考えるという。そして、引数に変更を加える関数を「破壊的」と呼び、意識的に区別される。普通のプログラミング言語では返り値は基本的に一つであろう。多値を返す場合はポインタで参照することになる。これが副作用を使う理由になる。破壊的にしたくなければ、ポインタを入力用と出力用で分けるといった面倒なことをやる。
一方、Lispはリスト型データ構造をしているので、もともと返り値に多値が想定されている。しかも、破壊的思想を避ける方向にあるという。尚、「多値」という言葉が使われるが、ここでは集合体のようなデータ構造を意味し、論理学的な多値と意味が違うので注意されたし。
また、関数型プログラミングは命令型プログラミングの裏返しだという。
「関数型プログラムでは、それが欲しがるものを求める。命令型プログラムでは、何をすべきかの指示を求める。」
自分で目的を考えるか、指示されないと動けないとの違いか?まるで現代社会を皮肉っているような。ただ、Lispにだって命令型のように書くことができる。それが幸か不幸かは別にして。
関数型では、一般的に初期値を与えない変数を書く習慣がないという。それだけでも危険度は違う。命令型では、初期値のない変数を書くのは普通に行われる。初期値を与えるように努力したところで、抜けてもエラーが起こるわけでもない。だが、Lispでは問題が起こるという。関数型で最初にトラブることは、命令型では最後にトラブると指摘している。関数の呼び出しは、その呼び出し自身が支配するオブジェクトを完全に書き換えることができるという。
「関数呼び出しは、返り値として受け取るオブジェクトを支配するが、引数として渡されるオブジェクトを支配しない。」
これがLispの慣習だという。ここでは副作用を持つ関数を作ってはならないと言っているのではない。そういう習慣がないというだけで、必要ならば意識して作るということだ。破壊的な関数がトラブルの元になりやすいのも事実で、破壊的にしたければ、setqなどで確実に明示すればいい。

3. マクロ
「マクロ定義とは実質的にLispコードを生成する関数だ - つまりプログラムを書くプログラムだ。」
Lispコードがコンパイルされる時、パーサがソースを読んで出力をコンパイラに送る。パーサの出力は、Lispのオブジェクトのリストから成るという。
驚くのは次だ!なんとマクロはパーサとコンパイラの間の中間形式を操作できるというのだ。コンパイラが読む情報を書き換えられるということは、コンパイラを書き換えられるのと同じではないか。マクロを展開するプログラム自身がマクロであってもいいわけだ。Lispの正体とはマクロ言語なのか?なんとも自己矛盾に陥りそうな再帰的仕組みにも映る。だから、再帰的アルゴリズムと相性がいいのか?多くのプログラミング言語でマクロ機能は搭載されるが、これはマクロの概念を超越していそうだ。実際、Lispのマクロは式を返すし、関数のように振舞う。
構造化プログラミングの推進者は、マクロを避ける傾向にあるという。それは、マクロがどこででも使われることと、その不可視性にあろうか。そういえば、C言語を導入した頃、マクロよりも構文を強く意識するようになり、まず関数で実装することを考えるような気がする。実際、ハウツウ本の例題が関数の実装で溢れている。関数とマクロの使い方が違うとなれば、分けて管理したくもなる。
だが、その区別がなくなりメモリ消費などの制約から解放されるとなれば、話は変わる。とはいえ、マクロにだって欠点が少なからずある。気になるのは、単に展開される仕組みなだけに、再帰的処理では自己矛盾を引き起こすことと、変数の束縛である。関数はレキシカルな領域に独自の世界を作るが、マクロは展開されるだけなので呼び出し側の環境を破壊する恐れがある。本書は、マクロを使って再帰的処理の書き方も紹介してくれるが、そこまでしなくても...変数の束縛では、letやprogなどの特殊形式を用いれば、恐れるほどではない。

4. 継続
継続とは、動作中のプログラムを凍結すること。Lispには、プログラムの状態を保持し、後に再開できる能力があるという。デバッグのための拡張機能が、この古き言語に既にあったというのか。
Schemeが、Common Lispと大きく異なる点の一つに、継続を明示的にサポートする機能があるそうな。Schemeでは、継続は関数と同格のファーストクラスオブジェクトで、クロージャの一般化と解釈できるという。ここでいうクロージャとは、関数とそれが生成された時点で見えていたレキシカル変数へのポインタをまとめたもの。
もしかして、継続の実装はガベージコレクションと同格なのか?などと想像してしまう。具体的には、call-with-current-continueation という組み込みオペレータで継続にアクセスできるらしい。

 (call-with-current-continueation
   (lambda (cc)
  ...))

関数と同格だから、どこにでも埋め込めそう。パフォーマンスも落ちるんだろうなぁ...

5. 非決定性アルゴリズム
日常生活における非決定性とは、ごく自然体である。ほとんど目的もなく気まぐれで行動しているのだから。これぞ人工知能の世界か。尚、Lisp開発者のマッカーシー先生は、「人口知能」という言葉の提唱者でも広く知られる。1980年代、AIブームが起こった。その代表的言語といえば、Prologであろうか。大学のゼミでも専攻している奴らがいた。もっともソフトグループと称しながら、ソフトボールに励んでいたようだが...
本書は、埋め込み言語としてPrologの実装例が紹介される。しかし、プログラムというものは目的意識から生じるものだ。非決定性という不確実性にどう立ち向かうのか?そのアルゴリズムは極めて単純で、その基本機能は、選択と失敗、そして未来計算で抽象化される。具体的には、chooseとfail、あるいはcutというオペレータの実装だ。そして、失敗と判断された経験の蓄積情報のデータ構造が鍵を握る。その処理は、蓄積情報が繰り返し検索され、パターンマッチングとその再帰的処理が根幹となることが想像できる。まさにLispの得意技か。データのツリー構造がパターンマッチングと適合することも味合わせてくれる。だが、経験が多く蓄積されるほど、判断に要する処理時間も長くなり、実用性から遠ざかるだろう。そこで、未来計算をいかに合理的に行うかが問題となる。経路検索を合理化するならば、情報はある程度まとめたい。プログラム的にはメモリを解放したい。では、どのタイミングで情報を捨てるのか?これは確率的な問題であり、用途に応じて決定されることになろう。つまり、cutとは「直感」の実装なのか?人間の思考なんて二分岐の繰り返しであって、その要素は、選択と後悔、そして未来への期待ぐらいなものか。

6. CLOS (Common Lisp Object System)
Common Lispには、オブジェクト指向プログラムを書くためのオペレータが揃っているという。それが、CLOSだ。もともとLispには、オブジェクトの属性でカプセル化の性質があり、ポリモーフィズムも、親から属性とメソッドを継承する性質も備わっているという。なのでLispをオブジェクト指向言語だと説く風潮があるそうな。その時代に名前がなかっただけのことか?
CLOSは、素のLispにオブジェクト指向の流れを組み込んで、形を整えたものだという。ただ、多重継承となると厄介なようだ。オブジェクト指向でも多重継承は混乱の元となる。
本書は、オブジェクト指向言語Lispを強調するために、わざわざCLOSを使わずにオブジェクト指向の実装例を披露してくれる。だが、酔っ払いは素直にCLOSに目を奪われる。
クラスの定義にdefclass、インスタンス生成にmake-instanceを使う。インスタンス変数やメソッドに相当するものにスロットがあるが、CLOSでは、スロットとメソッドを区別するようだ。defclassでスロットをセットで宣言し、メソッド定義にはdefmethodを用いる。なるほど、まったく違和感がない。

 -- GNU CLISP 2.48 での実行例 --
 :accessor は、スロットへのアクセスメソッド
 :initform は、初期値の指定
 :initarg は、引数シンボルの指定

 [1]> (defclass circle ()
        ((radius :accessor circle-radius :initform 1 :initarg :radius)
          (center :accessor circle-center :initform '(1 . 1) :initarg :center)))
 [2]> (defmethod area ((c circle))
        (* pi (expt (circle-radius c) 2)))
 [3]> (defmethod move ((c circle) dx dy)
        (incf (car (circle-center c)) dx)
        (incf (cdr (circle-center c)) dy)
        (circle-center c))
 [4]> (setf ins_circle (make-instance 'circle :radius 2 :center '(2 . 2)))
 [5]> (area ins_circle)
  12.566370614359172954L0
 [6]> (move ins_circle 2 3)
  (4 . 5)

==== ちょっと気になる技をメモしておく ====
1. 複数の返り値を受け取る方法
multiple-value-bind を使うと、複数の返り値を受け取ることができるという。

 > (multiple-value-bind (int frac) (truncate 26.21875) (list int frac))
 (26 0.21875)

2. コンパイルの過激なテクニック
Lispの関数は、個々でもファイル単位でもコンパイルできるという。必要に応じて関数を個別にコンパイルできるというのだ。λ式ですら。こんな過激な行為はやらないだろうけど、ちょっと感動してしまう。

 > (compile 'bar '(lambda (x) (+ x 2)))

3. ダイナミックスコープ
Lispの特徴として、ちょっと気になるのにダイナミックスコープがある。それは、前記事に「初めての人のためのLISP」でも取り上げた。だが、本書の印象はちょっと違う。
Lispコミュニティでは、ダイナミックスコープを廃止する傾向にあるようだ。Common Lispでは、普通はレキシカルスコープになるらしい。クロージャを実現するには、関数と変数束縛がセットになっている必要がある。Common Lispでもクロージャが浸透していると言ってくれる。これは安心させてくる。前記事は、古典的な流れを紹介していたのかもしれない。
また、マクロで弱点になる変数捕捉の対策として、with-gensymsという便利なマクロを紹介してくれる。その実装まで記されるが、既に組み込まれているようだ。ただし、clispとCommon Lispでは仕様が違うみたい。
 Common Lisp : (defmacro with-gensyms (syms &body body) ...)
 clisp : (defmacro with-gensyms (prefix syms &body body) ...)

4. 末尾再帰のテクニック
再帰関数で関数呼び出しの後に行うべき作業が残っていない場合、すなわち、再帰呼び出しの値が即座に返される場合の関数を末尾再帰と呼ぶそうな。再帰関数でよくやるのが、再帰呼び出しの後、何か処理をして値を返すといったことである。しかし、Common Lispコンパイラは、末尾再帰の関数をループに変換するので、末尾再帰を使うのが望ましいという。これでパフォーマンスも向上しそうな予感がする。現在のCommon Lispコンパイラは、C言語と同等かそれ以上の速いコードが得られるそうな。

5. SchemeとCommon Lispの相違点
  1. Common Lispが、symbol-valueとsymbol-functionを区別するのに対して、Schemeは区別しない。Schemeでは、変数は関数でもオブジェクトでもいいので、#'やfuncallが必要ない。
  2. Schemeの名前空間は一つ。だから、代入オペレータが個別にdefunやsetqのように存在しなくていい。代わりに、definとset!がある。グローバル変数は、definで定義しないと、set!で値を設定できない。
  3. Schemeでは、関数はdefinで定義される。defvarだけでなくdefunの役割もある。
  4. Common Lispでは関数の引数は左から順に評価するが、Schemeでは評価順は意図的に未定義。
  5. Schemeでは、tとnil の代わりに、#tと#fがある。
  6. condやcaseでデフォルト節は、Common Lispではtを使うのに、Schemeは、elseを使う。
  7. いくつかの組み込みオペレータの名前が違う。conspは、pair?、nullは、null?、mapcar は、ほぼmapに対応。ちなみに、Lispでは判定文の末尾にpを付ける慣習があるらしいが、「初めての人のためのLISP」では、Schemeのような新参者はpの代わりに?を使うと書かれていた。
...ちょうど目の前にGuileがあるので触れてみたが、道は遠い!

6. メソッドの結合
CLOSでは、基本メソッドと補助メソッドで区別している。基本メソッドとは、普通にユーザが定義するメソッドのこと。補助メソッドには、before, after, around がある。なんとなく、awkのBEGIN ENDの構文に似ているような。

例題)
「Perhaps ... in some sense」の中に任意の文字列を埋め込む。
「Does the King believe that...」の後ろの任意の文字列を埋め込んで、yes/noで答える。
----------------------------------------------------------
#! /usr/bin/clisp

(defclass speaker nil nil)
(defmethod speak ((s speaker) string)
  (format t "~A" string))

(defclass intellectual (speaker) nil)
(defmethod speak :before ((i intellectual) string)
  (princ "Perhaps "))
(defmethod speak :after ((i intellectual) string)
  (princ " in some sense") (terpri))

(defclass courtier (speaker) nil)
(defmethod speak :around ((c courtier) string)
  (format t "Does the King believe that ~A? " string)
  (if (eq (read) 'yes)
    (if (next-method-p) (call-next-method))
    (format t "Indeed, it is a preposterous idea.~%"))
  'bow)

;(speak (make-instance 'intellectual) "life is not what it used to be")
(setf ins_intellectual (make-instance 'intellectual))
(speak ins_intellectual "life is not what it used to be")

;(speak (make-instance 'courtier) "kings will last")
(setf ins_courtier (make-instance 'courtier))
(speak ins_courtier "kings will last")
----------------------------------------------------------
まず、aroundメソッドを評価し、その中で、next-method-p と、call-next-method が評価される。続いて、beforeメソッド、基本メソッド、afterメソッドの順に評価される。関数の返り値は、aroundメソッドの返り値となる。一番外側にaroundメソッドの殻があって、その中にbeforeとafterメソッドがあって、核の部分に基本メソッドがあるような三重構造のイメージか。これを「メソッドの結合」と呼ぶそうな。なかなかおもしろい機能だ。対話式プログラムを書く時に使えそう。
また、あるクラスにおいて、すべての基本メソッドの返り値の和を求める例が紹介される。ほぉぉ...

2011-11-20

"初めての人のためのLISP[増補改訂版]" 竹内郁雄 著

先月(2011年10月)スティーブ・ジョブズが亡くなって、世間の話題をさらった感があるが、同月に言語界の巨匠が亡くなって、それなりに業界を賑わしている。C言語の開発者デニス・リッチーと、Lispの考案者ジョン・マッカーシーである。カーニハンとリッチー共著の「THE C PROGRAMMING LANGUAGE」(原書)が、本棚に懐かしく並ぶ。
さてLispだが、ずーっと前から触れてみたいと考え、ようやく今年になって少し触れてみた。ポール・グレアム氏の著書「ハッカーと画家」の影響である。そこには、Lispを学べば実際にLispプログラムを作ることがなくても良いプログラマになれると熱く語られていた。だが、いまいち踏み切れない。いかんせん他のプログラミング言語と見た目が違う。S式とかいうヘンテコな宣教師が「カッコカッコ...コッカコッカ」と呪文を唱えれば、カッコの奥からletとかいう控えめな教職者がlambdaとかいう名もない浮浪者に見返り(返り値)をねだってやがる。鬱陶しい奴らだ。今日ではプログラミング言語も多様化しているし、わざわざこの古い言語に立ち返らなくても...という意識がどこかにある。プログラマでもないし。
そんなある日、本屋を散歩していると、一つの宣伝文句に目が留まる。
「道はnilを生ず。nilはアトムを生じ、アトムはS式を生じ、S式は万物を生ず。」
これは、老子の言葉「道は一を生ず。一は二を生じ、二は三を生じ、三は万物を生ず。」をもじっている。nil(ニル)とは、煮ても焼いても食えないやつだ。それは一般的なプログラミング言語のnullに相当し、空っぽを意味する。哲学風に言えば、無形化したもの、空虚なもの、実体を失ったもの、とでも言ってやるか。つまり、無から実が生じると言っているわけだ。孫子の兵法の基本原理「虚実の理」を匂わせれば、泥酔者はイチコロよ!

人間社会が仮想化へ邁進すれば、人間の価値観までも実体から乖離していく。ものづくりの世界では、あらゆるハードウェアがソフトウェア化し、いまや何に価値が生じるかも想像できない。そして、自己の実存にすら確信が持てなくなり、何にすがって生きればいいのかも難しくなる。高度な利便性と溢れる情報量が人々を惑わせ、無形化した何かに恐怖する羽目になろうとは。精神は実体である肉体から離れていく。まるで現実逃避するかのように。いや、仮想化社会だからこそ、逆に精神の内に見出す実体的な何かが必要なのかもしれん。実際、周囲の若い技術者たちには哲学的な観点からシステム思想を考える人が増えてきた。その一方で、システム思想に適合しない流用資産を持ち込んで、開発期間が短縮できるなどという夢想を押し付けるオヤジたちにうんざりする。まさにLispは、データの本質とは何か?とデータ構造の観点から哲学的実体を問うているような気がする。

かつて、プログラマはコードの書き方にエレガントさを感じ、そこに生き甲斐を求めてきた。今日では、データ構造のエレガントさがコード効率を高める。おいらは、データ型の宣言が厳格なものを好む傾向がある。昔は、適度に厳格な仕様がなかったからだ。近年の動的言語では、型宣言がそこそこ緩やかで、ダックタイピング的な特徴があるのはありがたい。
こうして振り返ってみると、無意識にデータとコードを区別して思考している。例えば、関数の構文では、関数本体と引数を区別している。むかーし、メモリ管理方式にセグメントという概念があり、コードセグメント、データセグメント、スタックセグメントで分けていた。おまけにエクストラセグメントなんてものもあったけか。こうした時代に生きた人間には、コードとデータを分けて思考する慣習がどこかに残っているかもしれない。
しかし、だ。Lispは、もっと古い時代から存在するにもかかわらず、プログラムとデータを区別しない。Program as data !これは、いかに実装されるかを想像してみれば当たり前のことだけど。プログラムだろうがデータだろうが、メモリに格納された状態は「アドレス + データ」という単純な構造をしている。関数をcallしたところで、関数の実体が存在するポインタを参照するだけのこと。関数の中身の逐次処理は、順序付きのデータコンテナで構成されたリスト型データと捉えることができる。引数では、値そのものを格納するか、値の存在するポインタを格納するかの違いがあっても、同じくリスト型で抽象化できる。ちょっと視点を変えて、関数が返す値はデータなのだから、関数自体をデータの一種と捉えても不都合はない。データにしても、データそのものを返すquote関数の結果と捉えれば同じく抽象化できる。
そして、リスト型データを配列風にカッコで表現すれば、関数も引数と同列にカッコの中に含まれ、データの多重構造は必然的にカッコの多重記述になる。なるほど、S式はLispポインタに他ならないというわけか。カッコカッコ...コッカコッカという呪文そのものが、リスト型データの合理性を表しているということか。Lispはよく関数型言語と言われるが、その特徴はリスト型データ構造の方がはるかに本質的なのかもしれない。
...と結論づけるのは浅はかで、別の書籍を読むと、実は命令型プログラムの裏返しとして重要な意味があるらしい。それは次回扱うとして、今宵はリスト型を味わうことに主眼を置くとしよう。理屈が見えてくれば、呪文への抵抗感が薄れていく。ありがたや!ありがたや!

本書は、プログラムとデータが相互に立場を変え得ることが、フォン・ノイマン型アーキテクチャの本質だと主張する。その思考は機械語的ですらある。なるほど、Lispはハードウェアと相性が良さそうだ。実際に、機械語でどのように振る舞うか想像しながらプログラムを書く人も少なくなかろう。特に、組み込み系ではそういう傾向が強い。
余談だが、電子回路設計では、ソフトウェア化が進みハードウェア記述言語(HDL)を用いる。そして、更なるシステム設計の効率化を進め、C言語系と連携した上流設計を目指す。ただ、昔からハード屋さんがソフトウェア化を叫べば、やたらとC言語化するものだと考えがちだ。特にC++系を崇める風潮がある。動作合成ツールでは、ひたすらC言語系を用いて動作レベルを記述しようと躍起になる。おまけに、回路の知識がまったくない人に、"Hello world !"プログラムが書ければ回路設計ができると勘違いさせて、現場を混乱させる。
その一方で、システム業界では言語の多様化が進み、C言語系にこだわる事例が減っている。そもそもC言語とHDLの相性がいいのかも疑問だ。Lispの方がはるかにHDLと相性がいいのではないか、と思う今日この頃であった。

1. 動的束縛の言語
「Lispはプログラムの実行時まで呼び出すべき変数のデータ型や関数の実体が決まらない動的束縛の言語である。」
動的束縛は、解釈実行型かつ program as data であることとほぼ同義だという。コンパイラでは速度性能の観点から、プログラム形式に静的な宣言を取り込もうとする傾向がある。そうなると、Lispのような動的言語は時代遅れとされるかもしれない。だが、ハードウェア性能が向上すると、その場で解釈しながら実行できる言語がもてはやされる。そういえば、インタプリタという用語をとんと聞かなくなった。実行ニュアンスがちょっと違うかなぁ。
また、ソフトウェアが大規模化すれば、トップダウンで要求仕様をしっかり決めないとプログラムが書けないという風潮がある。しかし、ボトムアップでプロトタイプをすぐに書けるというのは大きな魅力だ。トップダウンで構成された大規模なプログラムを、アップデートすることは面倒である。近年、システムを停止しないままアップデートすることが求められ、プログラムを動的に管理する必要がある。
ところで、動的といえば、Lisp言語の歴史そのものがまさに動的であるという。ようやく、Common Lisp と Scheme の二大方言に落ち着きつつあるようだが、永久に動的であり続けるのかもしれない。ちなみに、ガベージ・コレクションを最初に実装したのが、Lisp1.5 だそうな。現在では、Java, Python, Rubyなど多くの言語システムで実装されている。いわばゴミ集めの機能だが、これを言語システムで持つ必要があるのは、動的言語の宿命であろうか。

2. S式とM式
言語の最大の目的は、意味論的な機能を果たすことであろう。自然言語の優位性は、人間の感情を取り込むところにある。一方、コンピュータでは、感情を排除し一義的に処理する能力が求められる。しかも、コンパクトに記述するとなれば、そのほとんどの機能は数学的な表現となろう。
初期のプログラムは、関数表記に近いM式(Meta Expression)で書くものとされたらしい。M式とは、S式(Symbolic Expression)を引数として扱う表記で、例えばこんな感じ。

 length[x] = [null[x] → 0; t → add1[length[cdr[x]]]]

んー、見る気がしない!
もともとS式は、データやプログラムの内部表現を書くための低レベルの表記法だったという。例えばバイナリダンプのような。やがてM式は廃れるが、カッコだらけのS式が一般受けしなかったのは言うまでもない。
「Lisp嫌いは、S式をLispのよい特徴を覆い隠す必要悪と考えているらしい。」
S式は前置記法によく適合するだけでなく、言語意味論を簡単に乗せることができるという。それは二つのデータ、すなわちリストとアトムで構成される。リストはデータのペアを表わし、アトムはその素材である数字や文字列を表す。アトムはこれ以上分解できない物質の原子のようなもので、リストはアトムのペアで構成される分子のようなものというわけ。リストの表現は、アトムを羅列してカッコでくくったもので、コンマなどの区切りはない。リストの基本は二進木構造にあり、並べられたアトムはその順番に意味を持つ。そして、S式だけが yes か no を答える。もっとも、yesは T(true)、noは nil となる。言語学的には、必要最小限の情報量を与えているということはできそうだ。人間の判断力の根幹とは、まさに素材と選択肢、つまりはアトムとリストにあるのではないか!ちと大袈裟か。

3. ちょいとリスト型を味わう!
Lispの発明者マッカーシー先生は、リストの一番目の要素を、car と呼んだそうな。そして、1個以上の要素を持つリストから car を除いた残りのリストを cdr と呼んだそうな。
carとは、Contents of the Address part of Register number の略、
cdrとは、Contents of the Decrement part of Register number の略。そんなウンチクはどうでもええ。ちなみに、car を head 、cdr を tail と呼ぶ人もいるそうな。
それでは、ちょうど目の前に、GNU CLISP 2.48があるので遊んでみよう!
car関数を評価すると...

 (car (goo choky pah))
 *** - EVAL: undefined function GOO
 The following restarts are available:
 USE-VALUE :R1 Input a value to be used instead of (FDEFINITION 'GOO).
 RETRY :R2 Retry
 STORE-VALUE :R3 Input a new value for (FDEFINITION 'GOO).
 ABORT :R4 Abort main loop

goo が評価できる関数ならば答えが返ってくるのだろうが、そうは問屋が卸さない。関数の引数が関数であってもいいのだ。
 (car '(goo choky pah))
と引用符を付けると、リスト(goo choky pah) に対するcar が評価されて、gooが返ってくる。んー、引用符の使い方に意義があるのかぁ。
引用符を用いるのは記法上の便法で、Lispがデータの皮を食ってしまうという。なんじゃそりゃ!
 (+ 1 2 3 4 5) は、 (+ '1 '2 '3 '4 '5) と書いても同じ。
 (car '(a b c)) を評価すると、aを返す。
 (cdr '(a b c)) を評価すると、(b c)を返す。
リストを作る時は、cons関数を使う。
 (cons 'x '(y z)) を評価すると、(x y z)を返す。cons関数は carや cdr の逆関数と解釈できそうだ。
アトムの判定には、atom関数を使う。
 (atom '(x y)) を評価すると、nilを返す。アトムではなくリストというわけか。
 (atom nil) を評価すると、Tを返す。nilはアトムというわけか。
また、辞書の語彙を増やすのに、set関数がある。
 (set 'A 'aho)
A と aho に引用符を付けて関数の引数と評価している。
よく見かけるのに、setq(set quote)という関数もどきがある。
 (setq A 'aho)
Aに引用符を付けずに関数の引数と評価させて、自動的にうまいことやっているわけか。尚、このような評価を特別扱いするものを、「特殊形式」と呼ぶらしい。
関数が数値や文字と同じようにアトムとして扱われるだけに、その評価も統一性がある。ただ、直観的に左側のアトムの評価が鍵を握っている。更に、第一引数に特殊な意味を持つ場合があることにも注意したい。感覚的には、他の言語では文法に注意するが、Lispではアトムの評価の順番に注意すればよさそうだ。
ちなみに、CLISPを終了する時も(exit) とカッコを付けないと終了しない。(quit)も同じ。
 (atom 'exit) を評価すると、Tを返す。コマンドもアトムというわけか。
これだけでもリスト型言語であることが味わえる。

4. 再帰的思考に威力あり!
ここで、リストの長さ(アトムの数)を求める関数を作ってみよう。

 (defun lengthc (x)
   (cond ((null x) 0)
     (t (1+ (lengthc (cdr x)))) ))

 (lengthc '(aa bb cc)) を評価すると、3を返す。

リストの長さは、空リストなら0、そうでなければcdrの長さに1を足していく。これが、Lisp風の再帰的思考だそうな。
これを通常のプログラム風に思考すると、次のようになる。
(1) カウンタ値をリセット。
(2) リストが空ならば、そのままカウンタ値を返す。
(3) xを元のx のcdrに置き換えてカウンタに1を足す。そして、(2)に戻る(loop)。
これをLispでも書けなくはない。

 (defun lengthd (x)
   (prog (count)
        (setq count 0)
  loop  (cond ((null x) (return count)))
        (setq x (cdr x))
        (setq count (1+ count))
        (go loop) ))

尚、Lispには、progという特殊形式が用意されていて、(prog(x y z)...)で、ローカル変数を宣言できる。loopから抜ける時の値は、returnで返す。
更に、do文を使えば軽快になる。

 (defun lengthe (x)
   (do ((count 0 (1+ count)))
     ((null x) count)
     (setq x (cdr x)) ))

こうして比較してみると、Lispは再帰的思考に威力を発揮することが見えてくる。しかし、昔から計算機的な思考は再帰法なんか使わずに、BasicやFortran風に goto, do, loop が主流であった。Lispの基本的な思考は再帰的であるために数学の匂いを強く感じさせ、これが敬遠される理由だったという。それだけではないだろうけど。再帰が深まるとリストの長さに比例したメモリを消費するが、従来のプログラム思考では、変数count だけの領域でいい。かつてはハードウェア資源に制約がある場合がほとんどだった。物理的な制約からも、再帰的な思考は避けられていた。そういえば、オブジェクト指向という言葉が登場したあたりからであろうか。gotoプログラム撲滅運動が始まった。単純な繰り返しならば、loopラベルで明記できるが、ラベルが乱立すれば、たちまちスパゲッティ状態になる。検証も思いっきりやりずらく、ブランチカバレッジを真面目に見ようものなら頭が痛い。ただ、人間の一般的な思考方法において、再帰的思考は馴染まないかもしれない。再帰だろうがloopだろうが、精神ってやつは自己循環論に陥りやすく、おまけに自己矛盾に悩みながら精神病を患うのは同じか。

5. lisp の核はコンパクト!
  1. nil、数、文字列は、評価するとそれ自身を返す。
  2. シンボルの評価値はその時点での環境によって決まる。
  3. シンボルの評価値は、第0要素を関数、第1要素以下を引数と見なし、左から順に評価する。ただし、次の、4. 5. を除いて。ちなみに、関数を引数リストに適用(apply)すると言うらしい。まさしく、apply関数はこれをやっている。
  4. リストの第0要素が次のものであった場合、第1要素以降をどう処理するかは、第0要素により異なる。quote, cond, setq, prog, progn, go, let, let*, if, do, do*, defun, defmacro, functionなどは、第1要素以降を闇雲に評価せず、引数の評価を各自がきめ細かくコントロールする。例えば、quoteは第1要素を評価しないでそのまま返す。
  5. リストの第0要素がマクロであった場合、第1要素以下を評価せずにマクロの本体に渡す。そして、マクロ本体が返してきた値をその場でもう一度評価する。
実は、4.の中の特殊形式にも、Common Lispではマクロとされるものがあるそうな。例えば、condやdoなど。

6. ちょいと気になるスコープルール
動的スコープが用意されているのにちょっと警戒する。これは言語仕様の根本的な問題となろう。動的スコープを野放しにすれば、他の言語派から迫害を受けるに違いない。そこで、しかるべき非局所的な変数に限るという意図があるという。letやdoは変数を束縛する機能を持っている。
確かに、システムの中で常識的な変数をグローバルに参照できる方が、効率が良い場合がある。変数を参照するだけのメッセージ関数を用意するのも面倒だ。
動的スコープの変数は、special変数と呼ばれ、非局所的に宣言して、*で囲む慣習があるそうな。例えば、*standard-input* といったもの。最初から動的スコープと分かっているやつは、宣言する必要もないらしい。静的スコープの良さは、分かりやすさを求めるというより、ミスを防ぐことを重点に置く。ミスを回避して分かりやすくなるのであれば、動的スコープもありか。実は名前空間が適度というのは非常にありがたい。ただ、適度というのがくせものだけど。いずれにせよ、自由が野放しにされるのは危険であろう。その意味で大人の言語と言えるかもしれない。
Common Lisp では、名前空間をシンボル・パッケージ、あるいは単にパッケージと呼ぶそうな。標準装備されているパッケージは、lisp, user, keyword, sysytem の4つだという。lisp にはcarやcondなど一般的に使われるシンボルが、user にはユーザ定義のシンボルが入っている。system にはLispの言語処理系が内部で使用するだけで一般公開されないシンボルが入っている。ほんで、残りがkeyword。
lisp:car に対して、ユーザが、user:car や keyword:car を作ってもいい。文脈がはっきりしていれば、パッケージ名は省略できる。ただし、keywordだけは特別扱いされ、例えば、keyword:direction は、:direction と書けるそうな。

7. prog と let
progは、4つの基本機能を統合した特殊形式だという。、
(1) ローカル変数を宣言する。
(2) goによって繰り返しや飛び越しを可能にする。
(3) 計算の途中でreturnで強制的に値を返す。
(4) 不定個の式を上から順に評価する。

(4)の機能は、progn という形式も用意されている。
 (progn 式1 式2 式3)
ただ、頻繁に複数式が用いられるので、progと書いてもprognと解釈されるのが一般的だという。
(4) だけなら、progn と書けば複数式が強調される。
(1) と(4) だけなら、letを使うとよい。変数宣言と式の逐次評価機能だけに的を絞ったのがletで、return不要で気分爽快!

8. Lispの得意な分野
Lispは、データ構造が配列や連想リストなどで構成されている場合に威力を発揮するであろう。すぐさま思い浮かべるのは、行列式などの数値演算や、画像処理などの空間処理を扱うような分野である。本書は、自然言語やプログラミング言語の言語処理、あるいはデータベースのような分野でも威力を発揮するとしている。
ちなみに、配列では、setqよりも抽象化されたsetfを使うのがよいという。Common Lispで推奨されるのは、setfだそうな。配列要素へのアクセスには、aref(array reference)が用意されている。
本書は、データ構造が伸び縮みする例題として、キューとスタックの実装を取り上げている。キュー(待ち行列)はFIFO構造、スタックはLIFO構造をしている。キューの制御例では、DeQ/EnQ、スタックの制御例では、Push/Popがお馴染みで、通信系の回路設計に携わると必ず登場する技術だ。
また、ツリー構造の例題として、Jpegなどの圧縮フォーマットで用いられるハフマン符号化を取り上げている。そういえば、むかーしFAX系の通信システムでハフマン符号の回路設計にも携わった。
...などと、Lispを初めて使うはずなのに、なにやら懐かしいものを感じる。これがデジャヴってやつか?

2011-11-13

"通信の数学的理論" Claude E. Shannon 著

情報理論の父と呼ばれるクロード・E・シャノン。コンピュータ工学や通信工学に携わる人で、この名を知らない人はモグリだろう。この業界の設計をやっているにもかかわらず、彼の書籍に触れたことがないのは面目ない!言い訳するなら、チューリングやノイマンに比べると、ちょっと地味な印象があるかなぁ...

1948年、シャノンは記念碑的論文「通信の数学的理論」を発表した。本書は、その論文にワレン・ウィーバーの解説文を付して刊行されたものである。シャノンが工学の分野に貢献したことは言うまでもないが、ウィーバーは一般的な情報としても抽象化できると指摘している。つまり、情報の本質である信憑性や意味性においても、この理論が適合できるというわけだ。確かに、シャノンが提唱する情報エントロピーの概念は、通信技術のみならず情報社会の哲学的意義にも影響を与えてきた。情報量といえば、単純にメッセージの長さで捉えがちであるが、シャノンは伝達における情報量を、選択肢の自由度あるいはあいまい度で定義した。情報量は、選択肢の数に依存するのではなく、選択肢の確率に依存するということである。いくつかの選択肢の確率が公平に近づけば、結果予測が困難となる。それは、選択する側から見れば自由度が拡がることを意味し、予測する側から見ればあいまい度が増すことを意味する。これが情報エントロピーの基本的な考え方である。
また、情報の誤りを是正するための冗長性は、伝送系の能力に依存するとした。これは、伝送系の能力を超える符号化は不可能ということを意味し、ひいては符号理論の意義を唱えていると言えよう。
情報理論は、情報伝達という観点から言語学や社会学との関わりも深い。いや、あらゆる学問において専門に特化した合理的な表記法が考案され、表現に関わるものすべて情報理論に関わると言っていい。実際、プログラムの逐次処理が分岐構造を基礎とし、あらゆるリスク管理や社会政策などが現象の確率と優先度によって構築されている。マスコミ報道や風評流布の類いが世間を惑わす原理も、基本的には誤り訂正やノイズの原理と同じである。この時、選択肢の確率は情報の信憑性と捉えることができるし、欺瞞や誤謬あるいは精神不安など、判断を歪ませるものすべてがノイズと捉えることができる。更に、伝送系の能力は解析能力に通ずるところがあり、能力を超えた情報量はむしろ有害となろう。情報は多すぎても少なすぎても混乱を招く。そして、情報理論には「知らぬが仏」の原理が働くというわけさ。

本書に示される通信システムのモデルは6つの要素で構成される。あのお馴染みのやつだ。
 「情報源 → 送信機 → 通信路 + 雑音源 → 受信機 → 受信者」
シャノンの思考には、基本的に「通信とは、本質的にデジタルである」というのがあるそうな。ここでいうデジタルとは、情報の離散的性質を意味する。コンピュータやインターネットなどで扱うデータはデジタル量であり、その周辺を取り巻く伝送路や記憶媒体には必ず誤り率を有する。この性質は自然法則として受け入れられ、今日のデジタル技術は標本化定理や符号理論によって支えられている。通信システムの保証は誤り訂正能力で決まり、通信路の限界はビットの概念を指標としている。
しかし、人間が認識する情報は、本来的に音声や映像といった連続性であり、極めてアナログ的である。人間は、現在の瞬間的現象に対して未来予測と過去の経験から認識能力を発揮する。つまり、線形性であることが望ましい。数学的に言えば、時間の関数とエネルギー分布として捉えることができる。本書は、このアナログ的な連続量を重ね合わせの原理で、関数の集合と関数のアンサンブルとして波動的に捉える。そして、原理的には連続情報も離散情報と同じ形で抽象化できると結論づけている。

1. ビットの概念と情報エントロピー
選択肢で最も単純な形は二者択一である。複数の選択肢は二択の多重化と考えればいい。二つの状態は、工学的には、回路の開閉、リレーの接点、トランジスタのオンオフなど電流が流れるか流れないかで実現でき、数学的には、0と1で符号化できる。したがって、選択動作を繰り返せば状態は2のべき乗で増加し、情報量を2を底とする対数で扱うと便利である。ジョン・W・テューキィは、2進数情報の単位として、binary digit を縮めた語「bit」を提案した。
ビットの概念では基本的にあらゆる状態が公平に扱われるが、現実には確率的に捉える必要がある。例えば、言語システムでは最初の単語に続く単語が文法的にある程度決まっている。次に続く状態の確率が高い場合は省略もできるが、逆に確率が低い場合は単語を増やしてでも明示する必要がある。これは伝送系にノイズが紛れる原理と似ていて、受信側は正確な情報を予測することになり、ノイズの確率過程を分析することになる。よく知られる確率過程には、現在の状態だけで予測できるようなマルコフ過程がある。例えば、コイン投げで表と裏の出る確率が5割で予測できるようなもの。あるいは、標本数を適当に増やすことによって予測できるようなエルゴード過程がある。例えば、世論調査のようなもの。これらには離散的な記号を続けて選ぶという原理がある。こうした確率的傾向による情報量の変化が符号理論の概念を生んだ。すなわち、情報量とは、情報の正確性やあいまい度といったエントロピー的な量であるということが言えよう。自由度が増せば、それだけ符号化も複雑になる。
実際のエントロピーとエントロピー最大値との比は、情報源の「相対エントロピー」と呼ばれるという。例えば、相対エントロピーが0.8だとすると、メッセージを構成する記号の選択に関して、情報源が80%の自由を有するということである。そして、1から相対エントロピーを引いた量が冗長度ということになる。
ちなみに、本書は英語の冗長度を約50%と推定している。ただし、8文字の文字列の統計的構造について調べたもので、実際の英語の冗長度はもう少し高いらしい。満足のいくクロスワードパズルを作るためには、言語が少なくとも50%の自由度、または相対エントロピーを有しなければならないという。自由度が少なければ、単純なパズルしか作れないからおもしろくないというわけだ。
しかし、工学と言語学では考え方に大きな違いがある。それは、情報の意味するもの、意図するものに関係なく、すべての情報に対して公平に扱うという難題に立ち向かうことになる。そして、情報の効率性から、可変長データなどのデータ構造自体にも工夫が必要となる。

2. 情報量
各状態がそれぞれ、P1, P2, ..., Pn の確率で選ばれるとすると、情報量Hは次のようになるという。

 H = -[ P1 log(P1) + P2 log(P2) + ... + Pn log(Pn) ] = -Σ(Pi log(Pi))

ここで、logの底は本質的にはなんでもいいのだろうが、デジタル量として扱うには底を2とすればいい。例えば、二つの確率(P1, P2)があるとすると、二つの確率が等しければ情報量Hは最大値となるが、二つの確率が偏れば情報量Hは小さくなる。
 H = - {1/2 log2(1/2) + 1/2 log2(1/2)} = 1
 H = - {1/4 log2(1/4) + 3/4 log2(3/4)} = 0.81128
社会的認識と照らしあわせれば、公平とは自由を意味し、選択を誘導するということは自由を迫害するということであろうか。だが、政治の世界では、平等と自由はすこぶる相性が悪い。

3. 伝送能力
通信路の容量は、記号の数ではなく情報量によって表され、それは伝達能力と言うことができる。そして、通信効率を高めるために符号理論がある。
ここで、ノイズが存在しないと仮定し、情報源からの信号をH(bit/s)、通信路の容量をC(bit/s)とすると、次の定理が導かれる。

「送信機が行う符号化法を適切なものにすることで、ほぼ C/H の平均伝送速度で通信路を通して記号を送ることができる。しかし、どんなに符号化を工夫しても、伝送速度が C/H を超えることは絶対にない。」

したがって、通信路の設計では、伝送速度の経済性と符号化時間の損失とのバランスをとること考え、C/H を指標としながら折り合いをつけることになる。更に、ノイズの存在が符号理論を複雑化させ、冗長度を増加させる。ただ、ノイズも確率として扱うことによって、情報の全体を相対エントロピーとして扱うことはできそうだ。
ここで、H(x)を情報源のエントロピーまたは情報量、H(y)を受信信号のエントロピーまたは情報量とする。そして、Hy(x)を受信信号が分かっている時の情報源の不確かさ、Hx(y)を送信信号が分かっている時の受信信号の不確かさ、とすると次式が成り立つという。

 H(x) - Hy(x) = H(y) - Hx(y)

この式で注目したいのは、情報の不確かさも重要な情報になるということである。例えば、ノイズフィルタを設計する時、ノイズ特性を強調して、その反転をフィルタ特性として用いることがある。逆の視点から眺めれば、ノイズ自体が貴重な情報源となりうるわけだ。
通信路の容量が意味するものは、有益な情報を伝送できる最大能力、あるいは最大転送速度ということになろうか。そして、符号効率は、有害な不確かさ、H(x) - C を上回る性能が求められることになる。H > C ならば符号化は不可能ということは明らかだが、これが符号理論の概念を根本的に支えている。したがって、符号能力は確率分布から計算されるエントロピーから得られ、符号の冗長性は誤り率とのトレードオフの関係にある。

4. 連続情報
これまでは記号や文字などの離散的な情報を扱ってきた。では、音楽や映像のようなエネルギーが連続的に変化するような情報については通信理論はどうなるのだろうか?拡張された理論は数学的に非常に複雑にならざるを得ないが、本質的なことは変わらないという。まず、連続情報は時間的変化をともなうので、その基本形は次のようになる。

 f(t) = sin (t + θ)

この時、正弦波か余弦波かは位相で抽象化できるのでどちらでもいい。むしろ連続で押し寄せる波と位相の関係が重要なのだ。連続情報では、この形の関数がほとんど無限に存在するという極めて複雑な事情がある。つまり、fk(t) = {f1(t), f2(t), ...} といった関数の集合体として扱わなければならないという絶望的な状況だ。よって、工学的には、周波数帯域を限定して有限体として捉え、離散基底に持ち込むのが現実的ということになろうか。この集合体の中で、位相のずれになんらかの法則性を見出すことができれば、基本関数の巡回性と見なして、ガロア理論的な思考も試せるかもしれない。複雑系をエネルギー分布として統計量で扱う思考は、社会学が風評や世論の変化を近似的に分析するのと似ている。つまり、群(群集)分析だ。
今、fk(t) (k = 1, 2, ..., n) の確率分布関数を p(x) = {P1(x), P2(x), ..., Pn(x)} とすると、連続分布のエントロピーは連続区間の積分で定義される。

 H = -∫p(x) log p(x) dx (ただし、積分区間は±無限)

この形は、離散情報と基本的に同じである。更に、連続信号の通信路の理論は、周波数帯における重ね合わせの原理で周波数スペクトラムとして扱い、通信機の平均電力Pで議論される。そして、シャノンが定義したホワイトノイズ電力をNとすると、周波数帯域幅Wでの通信路の最大容量Cを与える公式が導かれる。

 C = W log( (P + N)/N )

ここでも、logの底は本質的にはなんでもいいのだろう。この公式は、離散性から連続性に抽象度を高めたというよりは、現実的な解を示したという印象が残る。まさに、現実の世界を生きる工学という分野の醍醐味と言えよう。

2011-11-06

"ガロア理論入門" Emile Artin 著

線形代数と出会ったのは大学の初頭教育であろうか。落ちこぼれスプレーを浴びせかけられた、あの忌々しい記憶が蘇える。おまけに、この書が入門レベルというからイヤになる。
ところで、「線形」ってなんだ?学生時代から疑問を持ち続け、いまだ答えが見つからない。用語辞典をググれば、それなりの答えが氾濫するが、どれもしっくりとしない。連続体と関係がありそうなことや、写像関係が維持されそうなことは、なんとなく分かる。過去とのしがらみを持つもの、あるいは予測可能なもの、こうしたものは、すべて線形なのだろうか?そもそも人間は、過去、現在、未来の流れの中でしか認識能力を発揮できない。では逆に、非線形ってなんだ?カオスのような現象のことか?人間には予測できない、あるいは認識できない領域にあるということか?だとすると、人間の能力で、認識できる領域と認識できない領域を区別するとはどういうことか?認識能力の境界を認識する???...などと思考が自己循環を続けたままなのだ。本書はまさに自己循環論を語っているように思えてならない。

ガロア理論と言えば、体論や群論の世界である。それは代数学の延長上にあり、線形代数と集合論が結びついた世界とでも言おうか。代数学とは、その名が示す通り数を文字に置き換えて抽象化する学問である。その対象は数(かず)であり、それは自然数から始まった。だが、減算や除算を行うと、自然数の体系からはみだすという欠点を曝す。算術によって系が閉じられない現象は、数の概念を自然数、整数、有理数、実数、複素数へと拡張させてきた。そして、方程式を解きたいという欲望が、いっそう抽象度を高める。代数学は、結合法則や交換法則、あるいは単位元や逆元を持つか、といった性質を考察する方向へと舵をとるのだった。連立方程式は、変数の数だけ方程式の数が存在しなければ解けない。その係数の羅列をベクトル空間や行列式で捉えた時、多次元の概念と結びつく。こうして線形代数が構築されてきた。そこには、非可換な世界が広がる。つまり、交換法則すら成り立たないものまで抽象化したのだ。この現象が意味するものとは、そぅ、物事を掛ける(賭ける)順番、やる順番が違うと、おのずと結果も変わってくるということである。したがって、酔っ払いの目には、非可換性は非可逆性、つまりはエントロピーに通ずるものを感じる。抽象化の波はまだまだおさまらない。体や群が登場すると、ベクトル空間や集合体までも呑み込んだ。もはや数の概念を超越している。四則演算に支配される構造ならば、なんでもありだ。
本書には、拡大体、分解体、部分体、可換群(アーベル群)、巡回群、可解群など、頭痛のしそうな用語で埋め尽くされる。そして、累乗根を考察しながら円周等分多項式の既約性を証明し、方程式を解くための必要十分条件に迫る。その結果、5次以上の方程式の累乗根はない、という「アーベルの定理」が導かれる。更に、幾何学の問題「コンパスと定規による作図」に対する代数学的解釈が示される。
ここにはガロア群の正体なるものが明かされるわけだが、一度や二度読んだぐらいでは頭の中に入ってこない。ほとんどの定理を鵜呑みする羽目になり、酒飲みの域に達っするには程遠い...

物事の本質を解析しようとすれば、それを構成する基本成分に分解してみようと試みるだろう。自然数では素因数分解し、方程式では既約多項式に因数分解する。そこで問題になるのが、どこまで純粋な要素に分解できるか?どこまで既約となりうるか?である。ちょうど物理学が、どこまで素粒子なのか?を問うかのように...
例えば、この方程式は、実数系ではこれ以上因数分解できない。
 f(x) = x^2 + 1
だが、複素数系であれば、更に因数分解できる。
 f(x) = (x + i)(x - i)
つまり、扱う系によって既約の定義も変わってくるわけだ。そして、四則演算の可能な系における最も抽象度の高い既約とは何か?が問われることになる。その抽象レベルで語った時、はじめて方程式を解くための必要十分条件が見えてくる。しかし、体論や群論を扱う才能豊かな人たちは、そんな定義は暗黙のうちに議論を進めやがる。数学者たちには、共通の抽象認識といったものが見えるのだろうか?
ところで、四則演算を習ったのは小学校であった。第五の演算とも言われるモジュロ演算を学んだのは、それよりずっと先で高校だったか?大学だったか?割った余りという観点から除算の一部と言えなくもないが、その本質はむしろ巡回性にあるだろう。日常を支配する暦は永遠に一週間を繰り返す。人間は10進数で物事を考えながら金の計算に執心し、商品の値段が桁上がりした途端に目くじらを立てる。コンピュータは2進数で四則演算を抽象化し、数字列をシフトするだけで乗算や除算をこなす。これらすべて巡回性で説明できるのだ。ちなみに、コンピュータ技術者は16進数で年齢を誤魔化すらしいが、モジュロ演算が人類の永遠の夢を叶えるだろう。
さらに、モジュロ演算は、暗号アルゴリズムや符号理論などで大活躍している。解析学で登場するフーリエ変換も、数学の直交性を利用した巡回性の成分で分解する。いずれにせよ、巡回範囲は、それぞれの世界で合理的に、あるいは都合よく設定されているに過ぎない。
では、巡回性を抽象化するとどうなるのか?本書では、自己同型群が巡回群になるという議論が盛んに行われる。人間社会で四則演算が馴染むというのは特異現象であって、宇宙法則では巡回演算の方がはるかに自然的なのかもしれない。もしかして、ガロア理論は抽象化の果てに自己循環論があると主張しているのか?

1. 体
体とは、ひとことで言えば、乗法と加法の二つの演算が定義されている集合である。これだけなら単純だが、その概念は意外とイメージしづらい。本書は、初心者に「複素数体の部分集合で、四則で閉じたものをモデルにして読みはじめてもよい」と助言してくれる。ということで、複素数系のベクトル空間を思い浮かべてみよう。
実数系も体の一つと言えそうだが、異質な点が二つあるという。それは、乗法の可換性を仮定しないことと、有限個の要素からなる場合もあるということである。非可換性については行列式でイメージできる。すなわち、乗法において交換法則が成り立たないということだ。有限個の要素というのがイメージしずらいが、先へ進むと見えてくる。線形従属や線形独立によって決定される次元(行列の階数)との関係を意識する必要があるが、やがてモジュロ演算のような巡回性を想定することになる。この有限体というあたりにガロア体の正体が隠されていそうだ。
そして、体とは、正確にはこういうことらしい。

「体とは、まず加法についてのアーベル群をなし、次に零を除いた残りが乗法について群をなし、しかも2つの群演算が分配法則によって結びつけられている集合である。」

アーベル群とは、可換群のこと。ちなみに、乗法が可換であるような体を「可換体」と呼び、可換性が成り立たない場合を「斜体」と呼ぶそうな。アーベルは可換群だけを想定したようだが、ガロアは非可換群もあると考えたようだ。

2. 拡大体と分解体
体Eの部分集合Kが、Eで定義された加法と乗法で体をなす時、EをKの「拡大体」と呼び K ⊂ E で表す。また、拡大体の次数を (E/K) で表す。そして、三つの体において K ⊂ B ⊂ E ならば、(E/K) = (B/K)(E/B) が成り立つという。Bを「中間体」と呼ぶ。
更に、K ⊂ E の時、Kの代数的なEの要素αの既約多項式 f(x) を定義して観察すると、おもしろい性質がある。

「(K(α)/K) = deg f(x) = nであり、K(α)はK上の 1, α, α^2, ..., α^(n-1) によって生成される」
ただし、degは多項式の次数を表す。

ここには、拡大体や部分体と多項式との重要な関係があるというわけか。つまり、体における要素の関係を考察するには、多項式、特に同型写像を考察すればいいということらしい。また、K内の多項式 f(x) の根をすべてKに付加した体を、f(x) の「分解体」と呼んでいる。要素が増えるのに分解体なの?既に拡大体と分解体の言葉の綾で混乱している。...挫折の予感か?

3. 群の指標
本書は、体の定義は明示されるのに、群となると途端に難しくなる。それも定義ではなく指標として示される。

「体Eから体E'の中への相異なるn個の同型写像 σ1, σ2, ..., σn があり、Eの部分体Kの要素 a に対してはつねに σ1(a) = σ2(a) = ... = σn(a) であるとき、不等式(E/K) ≧ n がなりたつ」

特に、Kのすべての要素を不変にするEの自己同型写像の全体が群になるという。これが群の指標ということらしい。
ここで、「不変」という言葉が気になる。恒等写像を仮定すると、Eの要素 a がそのまま a に対応するのだから、自己同型写像になるのは自然だろう。
σi(a) = σ1(a) = a (ただし、i = 0, 1, ..., n) となるところから、不変という名が付けられたという。おまけに、恒等写像でもないのに、Eの部分体となる σ1, σ2, ..., σn の要素の集合を「不変体」と呼んでいる。ちょっと無理がないか?
更に、乗法群における自己同型写像の条件が示される。
例えば、乗法群G、体Kとすると、GからKへの写像σが、Gの任意の要素α, βに対して以下を満たすとしている。

 σ(αβ) = σ(α)σ(β) (ただし、Gの任意の要素aに対して、σ(a) ≠ 0)

自己同型写像が群であるというのは分かるような気がする。だが、それで体に対して抽象度は上がっているのか?それは、次の正規拡大体で薄っすらと見えてくる。...そんな気がするだけかも。

4. 正規拡大体
群の指標を不変体と絡ませて進化させる。

「σ1, σ2, ..., σn が体Eの自己同型写像の群Gをつくるとき、Kをそれに関する不変体とすれば (E/K) = n である。」

体Kの拡大体Eがあり、KがEの自己同型写像をつくるような有限群Gの不変体になっている時、「正規拡大体」と呼んでいる。有限群GはKの自己同型群ということか。ガロア理論の基本定理とは、「正規拡大体の中間体と自己同型群の部分群との間に一対一の対応がある」ということらしい。体の拡大を群に結びつけるという意味では、群の方が抽象度が高そうだが、これって自己循環に陥っていないか?
また、EがKの正規拡大体であるための条件は、EがK内のある分離多項式の分解体になっていることだという。自己同型写像はその根の対応によって定まるという。
ここで示される例題は分かりやすい。

Kを有理数体とし、Eを多項式 x^4 - 2 の分解体とする。
この多項式は有理数体では解を持たないが、複素数体においては四つの解を持つ。
 4√2, -4√2, i4√2, -i4√2
ただ、分解体をつくる時は、これらの根を用いる必要はないという。
まず、x^4 - 2 は、Kにおいて既約であるので、次数4から次のようになる。
 (K(4√2) / K) = 4
次に、K(4√2) は実数体であり、これを中間体として用いる。
多項式 x^2 + 1 は、K(4√2) において既約であるので、同じく次数2から次のようになる。
 (E / K(4√2)) = 2
よって、こうなる。
 (E / K) = (K(4√2) / K)(E / K(4√2)) = 8

分離多項式の分解体ということでEは正規拡大体であり、8個の自己同型写像を持つことが分かるというわけだ。ここには、K上の多項式の解が拡大体Eの中に見つかれば、すべての解が拡大体に含まれるという思考がある。すなわち、方程式の解を見つけるためには、正規拡大体において自己同型写像があるかどうかを考察すればよさそうだ。...勝手な解釈だけど。

5. 有限体と巡回群
有限次元では、分離拡大体は単純拡大体になるという。そして、中間体が有限個であることが単純拡大体であるための必要十分条件だという。単純拡大体とは、なんのことはない、1つの要素を付加して得られる拡大体のこと。
有限体Kにおける多項式 f が重根をもつための必要十分条件は、その分解体Eにおいて多項式 f とその導関数 f' とが共通根を持つことだという。この条件は、f と f' が有限体Kにおいて、1以上の次数を持つ共通因数をもつことと同値だという。そりゃ、もとが有限体であれば、その拡大体も中間体も有限体であろうし、そうでなければ同型写像とはならないだろう。ただ、おもしろいことに、有限体の正規拡大体である自己同型群は巡回群になるというのだ。
「体の乗法群の任意の有限部分群Sは巡回群である。」
そこまで単純化できるとは、にわかに信じがたい。この定理は、アーベル群の二つの性質がもとになっているという。
一つは、「位数 c が最大になる要素Cが存在すれば、任意の要素の位数は c の約数である」ということ。位数とは元の個数。
もう一つは、「有限生成のアーベル群の基底定理」である。
有限生成のアーベル群とは、部分群 G1, G2, ..., Gk の直積という極めて単純な構造をしている。なるほど、有限部分群は巡回部分群の直積ということになりそうだ。...確信はないけど。

6. 1の累乗根と円周等分多項式
今、任意の体K、その拡大体の要素εを多項式 x^n - 1 の根とする。
「1の累乗根」とは、x^n - 1 = 0 の解のことで、次数n個の解を持つことになる。ちなみに、自然数体において、n乗するまで解が得られない場合、1のn乗根はεのn乗根となり、特に「1の原始累乗根」と呼ぶそうな。まさしく原始的というわけか。
しかし、複素数体においては、次のように解が得られる。
 ε = exp(2πi/n) = cos(2π/n) + isin(2π/n)
これは、{1, ε, ε^2, ..., ε^(n-1)} の有限巡回群である。
円周等分多項式とは、1の累乗根に関する多項式で、ここでは、Φn(x)とする。d が n の約数とすると、x^d - 1 は、x^n - 1 の約数である。よって、1のd乗根は1のn乗根の中に含まれる。そして、しばしば次の形で表されるという。
 x^n - 1 = ΠΦd(x)
つまり、多項式 x^n - 1 は、有理数体において円周等分多項式の積として既約分解されるということらしい。特に、標数nが素数pのとき、1の累乗根の個数は「オイラーのφ関数」で与えられるという。すなわち、円周多項式Φn(x)は、オイラーの関数Φ(n)の次数を持つということになる。そして、次の結果を得るという。
 (E/K) ≦ Φ(n)
位数 p-1 の巡回群になるというわけか。
...ここは、オイラーのΦ関数の知識がないと読みづらいところか、とりあえず鵜呑みにしておこう。だが、もうヤバい!脳は飽和状態へと達し、ネーター等式、クンマー体と流しながら、鵜呑み量(酒飲み量)が増えていく。

7. 方程式の可解性とガロア群
方程式を代数的に解くということは、累乗根を得るということである。ここでやっと、方程式におけるガロア理論の自己同型群の役割が明らかになる。

「f(x)が累乗根で解けるために必要十分な条件は、そのガロア群Gが可解なことである。」

可解群とは...
「群Gの部分群の減少列、G = G0 ⊃ G1 ⊃ G2 ⊃ ... ⊃ Gs = 1 が存在して、Giは、Gi-1の正規部分群の有限列で、i = 1, 2, ..., s に対して商群 Gi-1/Gi がアーベル群である」

そして、素数の累乗 p^n を位数に持つ群は、すべて可解であるという。
ここで、体Kにおいて、Kiを体の増加列、最終の体がFであるとする。
 K = K0 ⊂ K1 ⊂ K2 ⊂ ... ⊂ Ks = F
Kの拡大体Fが累乗根による拡大体であるとは、i = 1, 2, ..., s に対して、Ki = Ki-1i) であり、多項式 αが、x^ni - ai の形の Ki-1 内の根であることだという。
すなわち、Ki-1 上で Kが正規拡大体で、その自己同型群がアーベル群であれば解けるということのようだ。
更に、f(x) をK内の多項式で重根を持たないとし、Eを f(x) の分解体とする。
 f(x) = (x - α1)(x - α2)...(x - αn)
α1, α2, ..., αn は、Eの生成要素。
K上のEの自己同型群をGとすると、Gの要素σは、α1, α2, ..., αn で定まる。
だが、σは、α1, α2, ..., αn の並べ替えに写像し、Gはn個の要素の置換群になると考えてよいという。この時の群Gが「ガロア群」と呼ばれるものらしい。そして、次の定理が導かれる。

「K上n次の一般多項式のガロア群は、対称群Snである。Kが標数0で n ≧ 5ならば、n次の一般方程式は累乗根で解けない。」

素数次の既約方程式のガロア群Gが可解ならばGは線形であり、更に、任意の線形群は可解ということのようだ。...んー、置換群になるまでの仮定が、にわかに信じがたい。雰囲気だけだなぁ...

8. コンパスと定規による作図問題に対する代数的解釈
ユークリッド幾何学の作図問題が議論される。それは、「正多角形が作図できるための条件」と「角が三等分できるための条件」と「デロス島の問題」である。コンパスと定規によって作図可能ということは、有限回の操作で直線や円弧に分解できるということである。言い換えれば、ベクトルにおけるスカラー(ベクトル空間におけるノルム)と、円周等分多項式で分解できるということである。さすがにここまでガロア群を議論すれば、作図の対象は必ず有理数体でなければならないので、その限界を予感させてくれる。
例えば、半径1の円に内接する正n角形を作図する場合。
体Kは有理数体Qで、ε = cos(2π/n) + isin(2π/n) を解くのと同じである。つまり、正規拡大体である E = Q(ε) の次数を調べればいいということになる。そして、作図可能な正多角形の条件が素数を絡めて示されるのだが。...んー!ここまできてもやっぱり鵜呑みかぁ。
同じように、角の三等分とデロス島の問題も作図は不可能ということが導かれる。デロス島の問題とは、「アポロ神は、それまでの立方体の祭壇を、立方体状のままで倍の量にせよと要求された。」これは、立方体の一辺の長さを1として、3√2 を作図しなければならない。つまり、拡大体 F = Q(3√2) において解くことになる。だが、x^3 - 2 は有限体Qで既約であるから (F/K) = 3 であり、そのような作図は不可能となる。...おぉー!やっと鵜呑みから酒飲みの領域を見つけた。