レベル: 初級 川合史朗, Writer, ITmedia
2007年 5月 25日 前回に引き続き、Scheme言語の処理系、Gaucheを開発している川合史朗氏が、クロージャの機能を検証し、関数型言語とオブジェクト指向言語の関係について解説していきます。今回は、クロージャとオブジェクトのより深淵を探求します。
抽象化ツールとしてのクロージャ
C++的なオブジェクトの世界では、オブジェクトの実体とは「ひとかたまりの構造体としてメモリ上に置かれたインスタンス変数の値」にすぎません。オブジェクトのポインタを取れば、それは事実上、その構造体へのポインタを持っていることになります。クロージャを「関数」中心で見ていると、その実体は「オブジェクト」の実体とは異質なもののように思えるでしょう。
たしかにクロージャのナイーブな「実装」は、関数ポインタと環境へのポインタをくっつけたものです。しかし、クロージャをそのように実装する「必要」はありません。
クロージャの実装戦略
C++的オブジェクトは、その歴史的いきさつ（端的に言えばC言語との互換性確保）のゆえに、インスタンス変数がメモリ上にひとかたまりで存在し、またその寿命もオブジェクト自身の寿命と一致する必要があります。たとえそのインスタンス変数が、ほんの一部のメソッドからしか触れられていなくても、あるいは一時的にしか使われなくても、です。C++の基になったCの構造体が、抽象的な複合型を表現するだけでなく、メモリ上のレイアウトの指定にも使われていた名残と言えます。
これに対しクロージャは、その中から参照している変数がどこに存在しても構いません（クロージャ自身が生きている間、本体から見えさえすれば）。例えば、初期化後に変更されないと分かっているローカル変数は、その初期化値をクロージャ内にコピーすることで消去可能です。mapに渡すクロージャのように、生存期間がローカル環境より短いことがはっきりしている場合は、ローカルスタックに置くこともできます。そして何より、クロージャが使われる個所が静的に（つまり、式を読み込んで内部ツリーに展開した時点で）すべて判明している場合は、本体をインライン展開してしまうことでクロージャそのものの存在を消去することさえ可能なのです。
部品としてのクロージャ
これらクロージャの最適化戦略は、関数型言語かいわいでは20～30年ほど前に盛んに研究されたことで、いまでは暗黙の了解となっています。そのため、関数型言語のプログラマーはクロージャを書くときに、オブジェクトを「作っている」という感覚（例えばCのmallocや、C++/Javaのnewを呼ぶような感覚）をほとんど持ちません。結果として「何か」がアロケートされてしまうことはありますが、それは（1）どうやっても避けられないアロケーションか、もしくは（2）コンパイラが手を抜いているか、のいずれかなので、気にしても仕方がない*のです。
関数型言語のプログラマーにとっては、クロージャとはむしろ「穴の空いたコードのブロック」です。穴は仮引数であり、用途に応じて実際の値を埋め込む個所です。コードに似たようなパターンを見つけると、変化する部分を穴にして、共通部分を関数としてくくり出します。そして変化する部分を、実引数として与えてやるのです。
実例を見てみましょう。与えられた数の集合numbersをすべて足した値を返す関数sum-of-numbersは、リスト1のように書けます。一方、与えられた数の集合から、ある数値より大きいものだけを選ぶ関数more-thanは、リスト2のように書けます*。
リスト1 与えられた数の集合numbersをすべて足した値を返す関数sum-of-numbers
(define (sum-of-numbers numbers)
(define (loop sum nums)
(if (null? nums)
sum
(loop (+ (car nums) sum) (cdr nums))))
(loop 0 numbers))
|
リスト2 与えられた数の集合から、ある数値より大きいものだけを選ぶ関数more-than
(define (more-than n numbers)
(define (loop out nums)
(if (null? nums)
out
(loop (if (> (car nums) n)
(cons (car nums) out)
out)
(cdr nums))))
(loop '() numbers))
|
このように、ローカル関数loopで再帰するのは非常によく見るパターンです。両者を見比べると、リスト3のような共通構造があると分かります。本体内で変化する部分は、<初期値>と<経過と（car nums）を使った式>の部分のみです。それらを穴として引数で渡すことにすれば、共通構造を関数としてくくり出すことができます（リスト4）。
リスト3 sum-of-numbersとmore-thanの共通構造
(define (名前 numbers)
(define (loop 経過 nums)
(if (null? nums)
経過
(loop <経過と(car nums)を使った式>
(cdr nums))))
(loop <初期値> numbers))
|
リスト4 sum-of-numbersとmore-thanの共通構造を関数としてくくり出した部品fold
(define (fold proc seed lis)
(define (loop seed lis)
(if (null? lis)
seed
(loop (proc seed (car lis)) (cdr lis))))
(loop seed lis))
|
この部品foldに、変化する部分を外から与えてやることで、元のsum-of-numbersとmore-thanを再構成できます*（リスト5）。これはほんの一例に過ぎません。同様にして、クロージャとはあらゆる個所で式を「部品化」してゆく手段なのです。
リスト5 再構成したsum-of-numbersとmore-than
(define (sum-of-numbers numbers)
(fold (lambda (sum elt) (+ sum elt)) 0 numbers))
(define (more-than n numbers)
(fold (lambda (out elt)
(if (> elt n) (cons elt out) out))
'() numbers))
|
そもそも、基本的な部品化の手段であるローカル変数という概念自体を、Schemeの言語仕様はクロージャを用いて定義しています。ローカル変数x、yを導入するリスト6の式は、定義上、x、yを仮引数とするクロージャを作って直ちに初期値10、20を実引数として呼び出しているのと等価とされています（リスト7）。
リスト6 ローカル変数x、yを定義する式（letという構文）
(let ((x 10) ← 変数xに10を束縛（xを定義）
(y 20)) ← 変数yに20を束縛（yを定義）
(sqrt (+ (* x x) (* y y))))
|
リスト7 let構文の定義による、リスト6のプログラムの「意味」
((lambda (x y) (sqrt (+ (* x x) (* y y))))
10 20)
|
もちろん、多くのScheme処理系はlet構文を処理するためにクロージャの実体をアロケートしたりはしません（処理効率が悪くなるためです）。ただし、このようにクロージャを介した定義を行っておけば、クロージャ最適化のアルゴリズムを一様に適用できます。
クロージャによるオブジェクトの実装も同様です。プログラムの字面通りにクロージャの実体が生成される必要はありません。「クロージャによって（オブジェクトなどを）定義すれば、一般的な意味解析を適用できるようになる」という事実が、関数型のアプローチからは極めて有用なのです。
クロージャ最適化の実際
さて、ここまでの話は、「クロージャの使用を追跡して、しっかり最適化してくれる賢い処理系が理論上作成可能である」という話でした。では、現実の処理系はどこまで賢いのでしょうか。
先に述べたように、どこまで最適化を追究するかはほかの要素とのトレードオフになり、処理系の設計方針に依存します。ソースを直接読んで実行するタイプのスクリプト処理系では、最適化時間も実行時に影響を与えるため、あまりアグレッシブな最適化は行えないでしょう。一方バッチコンパイルして実行する処理系ならば、かなり突っ込んだ解析を行えます。
Schemeスクリプト処理系Gaucheでの最適化
例えばSchemeスクリプト処理系Gaucheは、本稿執筆時のバージョン0.8.7では1つのトップレベル関数内における簡単な依存性解析と最適化を行っています。どのような最適化が行われたかを簡潔に知る方法は残念ながらないのですが、Gaucheはソースを内部VM用にコンパイルするので、その結果をのぞくことで見当をつけることができます。
リスト4で定義したfoldのコンパイル結果を、Gaucheの組み込み関数disasmで逆アセンブルしてみましょう*（実行例1）。ここではVMのインストラクションの詳細な説明を省きますが、foldの中でローカルに定義していたクロージャloopが展開され、ジャンプ命令（LOCAL-ENV-JUMP）を使った単なるループになっている雰囲気は分かると思います。
実行例1 リスト4のfoldのGaucheによるコンパイル結果
gosh> (disasm fold)
main_code (name=fold, code=0x886aea0, size=22, const=0, stack=23):
args: #f
0 LREF1-PUSH ; seed
1 LREF0-PUSH ; lis
2 LOCAL-ENV(2) ; (loop seed lis)
3 LREF0 ; lis
4 BNNULL 8 ; (null? lis)
6 LREF1 ; seed
7 RET
8 PRE-CALL(2) 15
10 LREF1-PUSH ; seed
11 LREF0 ; lis
12 CAR-PUSH ; (car lis)
13 LREF12 ; proc
14 CALL(2) ; (proc seed (car lis))
15 PUSH
16 LREF0 ; lis
17 CDR-PUSH ; (cdr lis)
18 LOCAL-ENV-JUMP(1) 3 ; (loop (proc seed (car lis)) (cdr lis))
20 RET
21 RET
|
一方、リスト5のmore-thanを逆アセンブルしてみると、関数が2つ（main_codeとinternal_closure_0）に分けられているのが見て取れます（実行例2）。main_code内にあるCLOSURE命令が、コード列internal_closure_0とその時点での環境を一緒にしてクロージャを作成する命令です。Gaucheはグローバルな関数をまたいだ最適化を（まだ）行わないため、このケースではクロージャの実体がアロケートされてしまいます。
実行例2 リスト5のmore-thanのGaucheによるコンパイル結果
gosh> (disasm more-than)
main_code (name=more-than, code=0x9e79ca0, size=7, const=2, stack=6):
args: #f
0 CLOSURE #<lambda 0> ;
(lambda (out elt) (if (> elt n) (cons el ...
2 PUSH
3 CONSTN-PUSH
4 LREF0-PUSH-GREF-TAIL-CALL(3) #<identifier user#fold>;
(fold (lambda (out elt) (if (> elt n) (c ...
6 RET
internal_closure_0 (name=#f, code=0x9e7be60, size=10, const=0 stack=1):
args: #f
0 LREF0-PUSH ; elt
1 LREF11 ; n
2 BNGT 8 ; (> elt n)
4 LREF0-PUSH ; elt
5 LREF1 ; out
6 CONS ; (cons elt out)
7 RET
8 LREF1 ; out
9 RET
|
ではもっと賢い処理系を見てみましょう。2006年時点では、Scheme界の最適化処理系で名高いのはジェフリー・シスカインド（Jeffrey Mark Siskind）によるStalin*です。Stalinは、シスカインド氏が本業の傍ら、もっぱら個人で使うために開発している処理系のため開発ペースが速いとはいえませんが、実行時性能の高さには定評があります（ただし、その突っ込んだ最適化のために、コンパイル時間が数十分におよぶこともあるのですが）。
Stalinは、標準関数もひっくるめたプログラム全体の依存性解析と型推論を行い、徹底的に最適化されたコードを出力するコンパイラです。Stalinによってどこまでの最適化が可能なのか、実際に処理系を入手して試してみました。なおStalinはCを介してネイティブコードを出力するのですが、gcc-4系列ではgcc自身の最適化ルーチンが終了しなくなるので、gcc-3系列を用いて処理系をビルドする必要があります。
例えばFedora Coreでは、compat-gcc-32パッケージをインストールすることによって、gcc32という名前でgcc-3.2.3が起動できます。stalinをビルドするには、makefileの冒頭にあるCCの定義を、
のように書き換えた上で、シェルスクリプトbuildを走らせてください。
なお、テストのためにクロージャベースのオブジェクトを使った、簡単なプログラムを用意しました（リスト8）。Stalinはまだdefine-syntax構文*をサポートしていないので、本稿の最初に示したdispatchルーチンを手で書いてやる必要があります。また、大括弧[]も認識しないようです。
リスト8 クロージャベースのオブジェクトを使ったテスト用プログラム
(define (make-point x y)
(define (dispatch msg)
(case msg
((get-x) (lambda () x))
((get-y) (lambda () y))
((set-x) (lambda (nx) (set! x nx)))
((set-y) (lambda (ny) (set! y ny)))))
dispatch)
(let ((the-point (make-point 111 222)))
((the-point'set-x) 333)
(display ((the-point 'get-x)))
(display ((the-point 'get-y)))
)
|
さて、リスト8の内容をpoint.scmというファイルに保存して、stalinを起動します。「-k」オプションで中間コードとなるCファイルを消さないように指示しました。また、そのCファイルを調べやすいように、幾つかの「-O」オプションを指定し、ランタイムチェックをoffにしました。
$ stalin -k -On -Ob -Om -Or -Ot point.scm
|
これで中間コードであるpoint.cと実行バイナリであるpointが作られます。point.cは人間が読むことは想定していない上、displayなどの標準関数までインライン展開されているため極めて読みづらいですが、初期値として与えている定数111、222、333を手がかりとして追っていきます。すると、プログラム本体はリスト9のようにコンパイルされていることが分かりました（コメントは適宜補いました）。
リスト9 stalinが出力した中間コードpoint.c
int a657; /* X */int a658; /* Y */FILE *a1728;
/* THE-CURRENT-OUTPUT-PORT */struct headed_vector_type591 *a1730;
/* BUFFER */void f0(void){int a2078;/* OBJ */ int a2108;
/* NX */ int a2114; /* OBJ */ int t72; int t73; FILE *t74;
int t75; int t76; int t77; FILE *t78; int t79; int t80; FILE *t95;
struct headed_vector_type591 *t97; int t98; t95 = stdout;
/* 出力用バッファ */ t98 = 20; t97 = (struct headed_vector_type591 *)
GC_malloc_atomic(sizeof(structheaded_vector_type591)+((t98-1)*sizeof(int)));
t97->length = t98; a1728 = t95; a1730 = t97;
/* 初期化 (make-point 111 222)
*/ t79 = 111; t80 = 222; a657 = t79; a658 = t80;
/* ((the-point'set-x) 333) */ t75 = 333; a2108 = t75; a657 = a2108;
/* ((the-point'get-x)) */
t76 = a657; a2114 = t76; t77 = a2114; t78 = a1728;
/* stdout */ /* (display ...) */ f1438(t77, t78); /* ((the-point'get-y))
*/ t72 = a658; a2078 = t72; t73 = a2078; t74 = a1728;
/* stdout */ /* (display ...) */ f1438(t73, t74); return;} |
このうち、出力バッファはdisplay内部で用いるため、displayを使う限りはアロケートされるようです。注目すべきは、make-point関係のクロージャがすべて消去されていることです。pointのインスタンスは、何と単なるグローバル変数「a657」、「a658」として表現され、「get-x」、「set-x」などのメッセージの処理が、すべてインライン展開されています。
クロージャ（の実装） ≠ 関数 + 環境
このように、プログラムの字面でのクロージャは、必ずしも実装上での関数とは対応しません。むしろそれは、引数によってパラメータライズされた論理的なブロックと見るべきなのです。
クロージャを「C/C++的な関数に環境がくっついたもの」と考えていると、それとオブジェクトとが等価であるとはどうしても思えないかもしれません。しかし、クロージャをプログラムの意味、あるいは仕様の記述と見れば、両者は同じものを別の言葉で記述しているにすぎないということが分かります。「それが実際にマシン上でどのように実装されるか」という問題は、処理系の実装次第なのです。
型としてのオブジェクト
ここまで見てきたように、クロージャとは、「状態と処理を合わせたもの」にとどまらず、むしろパラメータライズされた処理のブロックを記述する汎用的な手段でした。一方、オブジェクトの方も単なる「状態＋処理」だけにとどまるものではありません。オブジェクト指向の特性とされる性質のうち、本稿で挙げたようなクロージャの使い方ではカバーできないものがあります。中でも重要なのが、型としての側面です。
静的型を持つクラス指向言語では、「クラス」はインスタンスのプロトタイプを指定するだけでなく、新たな複合型を定義するという性質を持ちます。「あるオブジェクトに対して、それが持つ状態と適用可能な操作の集合が明示的に宣言されている」ということです。
クロージャによる状態とメッセージの表現では、メッセージによって返されるクロージャの型がまちまちなため、静的な型解析がひどく厄介です。最適化やコンパイル時のエラー検出を追究していくと、すぐにStalinのようなプログラム全体の解析まで踏み込まざるを得なくなります。
クロージャをベースにしたアプローチを使っている場合、プログラマーはまず個々の操作に注目し、状態は、「必要なものが後から自然についてくる」といった感覚を持っているように思われます。
動的型付けのオブジェクト指向言語の場合、コンパイラによる型の解析という面では、オブジェクトからのアプローチによる利点を直接享受できません。それでも、その言語で考えているとき、プログラマーの頭の中には特定の「状態と操作の集合としての型」が存在するようです。
ハイブリッドの意味
プログラムというのは、それ全体が「状態と処理のひとかたまり」です。クロージャとオブジェクト指向はともに、その大きな塊を扱いやすい小さな塊へと分割してゆく手段です。どちらも最終的に得られるものは、小さな「状態＋処理」の塊であって、その意味では「クロージャ≡オブジェクト（mod構文）」であると言えます。
その一方で、そう言いきってしまうことに違和感を覚えるのは、分割していくアプローチに違いがあるためでしょう。幾つもの操作の中から共通した操作を見つけてくくり出していくクロージャベースのアプローチと、共通した操作が適用できる状態の集まりを先に探そうとするオブジェクト指向ベースのアプローチ、という傾向がありそうです。
どちらのアプローチをメインに据えるかに差はあれど、現代のプログラミング言語のほとんどは、両方のメカニズムを備えたハイブリッドなものになっています。プログラマーとしては、両者のアプローチの違いを頭において、問題に適したメカニズムを選択していくことになるでしょう。
言語設計者にとってのハイブリッド
ところで、言語設計者、あるいは処理系設計者として、この2つのメカニズムをどのように調和させるべきでしょうか。オブジェクト指向言語がクロージャのメカニズムから、あるいはクロージャ中心の言語がオブジェクト指向言語のメカニズムから採り入れられることはあるでしょうか。
クロージャベースの、特に動的型付け言語においては、操作を束ねるやり方として動的ディスパッチのみに頼るのではなく、「共通の操作の集合を宣言できるようなメカニズムを採り入れることでプログラマーの頭の中が整理しやすくなる」ということが考えられます。Haskellの型クラスのようなものがヒントになるかもしれません。
オブジェクト指向言語については、「メモリ上に連続して配置されている、状態のひとかたまり」と「状態と適用可能な操作の論理的な集合」との結びつきをもう少し緩めてはどうかと思います。ハードウェアアクセスなど低レベルなレイヤーを除いては、現代のプログラミングでオブジェクトを物理的にひとかたまりに配置しておく必要はあまりありません。この2つを切り離すことで、過去30年にわたり蓄積されてきた関数型言語のプログラム解析手法を、より自由に適用できるようになるのではないでしょうか。
より良いプログラミング言語を目指して
なお、本稿では「オブジェクト指向」「オブジェクト」という用語をあえて厳密に定義せず、それぞれ、
- 現在主流となっている、クラスベースあるいはインスタンスベースのオブジェクト指向言語処理系が採用しているメカニズム
- そのメカニズムにより実体化される「状態と処理を合わせたもの」
のように考えて筆を進めました。
前述したように、「オブジェクト指向」の定義は人により異なるためでもありますが、「言語に両方のメカニズムを採り入れることの意味について包括的に考えてみたかった」というのが主な動機です。切れ味の良い結論と言うより、オープンクエスチョンのようになってしまいましたが、これからのプログラミング言語を考えてゆく上でのヒントになれば幸いです。
このページで出てきた専門用語
コンパイラが手を抜いているか、のいずれかなので、気にしても仕方がない
（2）に関しては、コンパイル時間やデバッグの利便性からあえて最適化を行わないという選択をしている場合も多く、コンパイラが駄目だというわけではありません。ただ、実用的に使いこなしたければ「コンパイラの癖」のようなバッドノウハウを知る必要はあるでしょう。
リスト2のように書けます
この例では返されるリストの要素は与えたリストの逆順になります。集合として考えるなら順序は関係ないですが、順序を保存したければ、最後にリストをreverseすれば良いでしょう。
元のsum-of-numbersとmore-thanを再構成できます
sum-of-numbersに渡しているクロージャは、この場合単に関数「+」を同じ引数で呼び出しているだけなので、「(fold + 0 numbers)」と書いてしまっても構いません。
Gaucheの組み込関数disasmで逆アセンブルしてみましょう
本稿に上げたfoldを定義せずに「(disasm fold)」を評価すると、同名の組み込み関数foldの方の逆アセンブル結果が表示されることに注意してください。組み込み関数の方は可変長の引数を取れるため、その分コードが大きくなっています。それでもクロージャのアロケーションは行われないのです。
Jeffrey Mark SiskindによるStalin
Stalin: STAtic Language ImplementatioNの略、Dylanに対抗して名づけられたらしい。こちらに最新版0.11へのリンクがあります。
define-syntax構文
Scheme仕様で定められているマクロシステムの1つ。define-syntaxは、最新のScheme仕様であるR5RS（Revised5 Report on Algorithmic Language Scheme）で定められました。
参考文献
著者について  | | | ITmedia |
記事の評価
| 
