Last update 1999/08/07
(C)平山直之
無断転載は禁止、リンクはフリー
誤字脱字の指摘は歓迎
前回どこまでやりましたっけ？ ああそうですか、構文木を内部に作るところまでですね。
その前に、前回のアーティクルでは作戦目標がいまいちあいまいだったようなので、もう少し技術的に踏み込んだ明確な作戦目標を示すことにします。
- 環境非依存のschemeインタプリタモジュールを作成する。
- 堅牢性・サイズ・保守の便宜のために、標準scheme以上の拡張は必要最小限しかしない。
- 外部とのインターフェイスには環境に適した動的モジュール機構を利用する。具体的には、Win32ではDLL機構を使う。
- 単体では完全なサーバとして働き、不必要なユーザーインターフェイスは（コンソールを含めて）持たない。また基本的には受動的にしか動作しない。
- オブジェクト指向機構をサポートする。
- オブジェクト永続化機構をサポートする。
といったところです。
これらの作戦目標は、「単体で自己主張をしない」「ほかのアプリケーションの道具として使える」ことを最終的な指針として立てられています。
もちろんこれは最終的な目標であり、本当にそのままだと開発・デバッグに不便なので、現在は対話型のコンソールをつけて開発しています（といっても単なる標準入出力ですが）。が、最終的にはコンソールもクライアントの一つとなるでしょう。
言語処理系の実装で、作業開始前に一番気になるのは、スタックの使い方です。
一般的に言って、機械言語は再帰的な構造をしています。そのため、パーサは再帰的な構文を読み取る必要があるし、エバリュエータは再帰的な構造を実行する必要があります。C言語で言えば、関数内で関数を呼び出すことができるということです。
さて、ここでスタックの観点から実装の対象として言語を見ると、機械言語は大きく2つの種類に分けることができます。
一方は実装言語のスタックをそのまま利用できる言語であり、もう一方は利用できない言語です。
たとえば、CommonLispは前者であり、schemeは後者です。
CommonLispの場合
これをもう少し詳しく説明しましょう。
CommonLispの大域制御構造には、throw/catch、block、tagbodyなどがありますが、これらはどれも「内から外への脱出」しかサポートしていません。ですから、C/C++でこれを実装するときもsetjmp/longjmpやthrow/catchで実装が可能です。また局所変数などを扱うにも、「局所環境」という関数を作り、入るときに局所変数スタックをプッシュして、出るときに局所変数スタックをポップするというアプローチで実装することが可能です。C++で言うなら、変数を束縛する場所でtryして、その関数の中からその環境に存在する式を評価するようにしておけば、その式の中で脱出されてもcatchで補足することが可能であるということです。もちろん局所脱出ですから、その後に例外を再射出することになります。
そういったわけで、CommonLispでは、基本的にlispの関数＝C++の関数と考えて実装することが可能です。その結果、組み込み関数を書くときも、単に字面がC++なだけで考え方はlispとまったく同じソースを書くことが可能になります。「インタプリタは遅い」と一般には思われていますが、上記のようなアプローチに多態性を加えると、実は処理上のロスのほとんどない「下手なプログラマが書いたネイティブコードと同じくらい高速」なインタプリタを作ることは不可能ではないのです。インタプリタが遅いのは一般にインタプリタに使われがちな言語仕様のせいが多分にあり、必ずしもインタプリタが遅いわけではないのです。
残念ながら、CommonLispの場合「ラムダリスト（関数の仮引数リストのこと）が不自然に複雑」などの制限があって実際にはそこまで高速にはできませんが、独自にインタプリタのための仕様を立てた場合の可能性としては明らかに存在します。
schemeの場合
一方、schemeでは、上記のような戦略は取れません。なぜなら、「継続」という概念があるからです。はっきりいってしまえば、Cのようなスタックベースの言語でインタプリタを作るよりも、ネイティブコンパイラを作るほうが楽なのではないかと思われるくらいです。
なぜそうなのかを理解してもらうには、まず「継続」について理解してもらう必要があるでしょう。
（とても面倒なので代わりに説明してくれているサイトがないかと探してみたのですが、どうもないようなので私が説明するしかないようです。書籍ならばちゃんとよいものがあるので本当は私ごときがわざわざこんなことをするのは時間のムダ以外の何者でもないのですが、webにないのでは仕方がありませんね。）
継続の説明＜書くのめんどくせえので省略＞
つまり、ifだのgotoだのtry/catchだのといった制御構造はすべて、継続の特殊形であり、逆に言うと継続はそれらの一般形であるということです。schemeは、それをファーストクラスオブジェクト（intなどのスカラ型と同じくらい楽ちんに使えるオブジェクトのことを総称してファーストクラスオブジェクトと言う。コンピュータ言語のテクニカルターム）としているため、そうした特殊形やループでさえ、マクロや関数などで実現できるというわけです。
そういうわけで、プログラム制御機構としてこの上なく強力（try/catchだのunwind-protectだのといった言った制御構造すべてを継続で表現できるくらい）なのですが、Cなどの構造化言語とソリがあわないため、インタプリタやCコンバータとしては残念ながら効率的な実装は困難なのです。
はっきりいってしまえば、継続のサポートを断念することも考えました。理由はこうです。
- 処理速度について言えば、スタックベースの実装と比べて下手すると一桁違っても不思議ではないと思わた。
- 現実問題として、スクリプト言語として必要なのは、throw/catchやunwind-protectなどの仕様局面について十分に考察されている「特殊形」であって、その一般形ではないのではないかと思われた。
- 内部で再帰が使えないため、内部で式の評価を行うような組み込み関数・特殊構文などの実装が困難なことが予想された。
しかし最終的には、なんとか気合で実装することを選びました。主な理由を以下に挙げます。
- 標準がある以上、それに従わないといろいろな面で損をすることが予想された。たとえば、GNUのGUILEでも継続はちゃんとサポートしている。
- 実装する能力がないと思われるのがシャクだった。
- schemeの言語仕様は大きくないし、組み込み関数の数もそう多くないので、気合で乗り切れるとみた。そもそも内部で再帰的に式を評価しない関数ならどちらでも関係ない。
- scheme上に乗せるシステム（たとえばオブジェクト指向システム）の開発に有用であると思われた。
- ゲームプログラミングのある種の局面（たとえばオブジェクトごとの思考ルーチンでそれぞれに継続を使う、など）に非常に有用なのではないかという漠然とした期待感があった。
- 元々の戦略上、ツールとして他のアプリケーションから「使われる」ことを予想している。となれば、クリティカルに速度が必要な場面では使う側でネイティブ実装すれば済む話ではないか。
- 今のマシンで処理時間を食われるのは主に画面処理などであり、このスクリプト処理サーバが担当すべき「データベース面」や「記号処理面」でのスピードは、どんなに時間がかかってもどうでもいいレベルでしかないと予想される。
- ヒープをスタック代わりに使うためスタックオーバーフローしないので、遠慮なく再帰を使えるのはlispとしては大きなメリット。
ということで、処理効率は犠牲にしましたが、胸を張って「schemeである」と言える実装にしました。
機会があれば、継続を省いてthrow/catchなどの「制御構造の特殊形」を加えた、インタプリタとしての高速性を念頭に置いた仕様のオブジェクト指向言語も作ろうと思います。
今回行ったschemeの「継続」の実装方法について述べます。
継続の説明＜書くのめんどくせえので省略＞
とりあえず仕様書にのっている機能について、以下を除いて実装が終わりました。
- 整数以外の数
- マクロ関係
- プロミス
- 文字、文字列
- ガベージコレクション
要するに、大体制御構造の実装が終わったところです。
残念ながら現在のバージョンでは、
- まだDLLとしてのインターフェイスなどが存在しない、
- すごい勢いでメモリリークする（後でGCを組み込むためで、わざと）
など実用に耐えない仕様になっていますので、これを優先的に処理したいと考えています。
また、実装上無駄な部分も多すぎる（たとえば型が分かってるのに仮想関数呼び出ししているとか、1回で済む仮想関数呼び出しを3回に分けてたりする）ので、近いうちにシェイプアップもすると思いますが、これはプロファイルを行いながらでないと非効率的なので、プライオリティとしては低くなっています。さっきから遅い遅いと書いてますが、このフェーズの努力次第ではかなり改善できると見ています。
ということで、次回は、上に書いたようなコンポーネントとしての不備な点を解消した後、このスクリプトサーバを使ったクライアントアプリケーション（多分対話式インターフェイスおよびオブジェクトブラウザ）の作成について、クライアントアプリケーションでのスクリプトサーバの使い方を説明しながらリポートしようと思います。
さすがにソースはかなりデカくなってしまったので、今回はアーカイブをのせておくにとどめます。
(C) 1998 Naoyuki Hirayama. All rights reserved.