解体JAKLD初日

ken

JAKLDは京大の湯浅先生が携帯電話のJVMで動作させることを狙ってお作りになったSchemeもどきのLispです。先日、開催されたばかりの情報処理学会プログラミング研究会でほぼ二年ぶりにお会いしたときに、JAKLDの名前の由来をお訊ねしたのですが、そのご返事に唖然としてしまいました。ちょっと考えてみて下さい。

今年の新四年生向けの春セミナーの一環で、このJAKLDを読み解くことを取り上げました。今回はその第一回です。JAKLDはすべてJavaで記述されていて、14個のJavaファイル、計3,720行で構成されたとてもコンパクトな処理系です。

274 Char.java
79 Contin.java
84 Env.java
629 Eval.java
28 Function.java
785 IO.java
79 Lambda.java
467 List.java
32 Misc.java
744 Num.java
28 Pair.java
237 Subr.java
254 Symbol.java

このうち、Char, Num, Symbol はそれぞれ文字と文字列、数値、シンボルに対応した基本的なデータ型に対応するクラスです。Lambda は一級関数、Contin は継続を実装しています。Envは名前とそれが束縛する値の対応関係を表す評価環境を、Subrは組込み関数名とその実装との対応表を実装しているようです。Schemeインタプリタの構文解析を含む入出力部がIOで、読み込んだ式を評価するのがEvalという感じです。

今日は初日ということで、基本データ型を実装するChar.javaとNum.javaを学びました。プログラムにコメントを入れるような感じで解説するのは大変なので面白いと思ったところだけ、掻い摘んで紹介します。

文字の表現には、Java の文字を用いているので少なくとも内部的には Unicode で表現されています。まだ読んでいない構文解析器次第なのですが、もし日本語に対応していなかったとしても、比較的簡単に対応できるでしょう。

文字の表現では、char データではなく Character オブジェクトを採用しています。これは記憶容量についてはやや損をするように思えるかもしれませんけれども、実行時の型を表すタグをクラスで代用していると考えれば、さほど大きな損ではないのかもしれません。

文字型に限らず、JAKLD の内部表現においては、Scheme のそれぞれのデータ型を Java の対応するクラスのオブジェクトを用いて表現しています。そして、型検査を型キャストや instanceof 演算子に任せることで、実行時システムの実装の大幅な簡略化に成功しています。

例を挙げると以下は、与えられた引数が英文アルファベットか否かを判定する組込み手続きの実装例にあたります。

95 static { Subr.def(“Char”, “alphabetic”, “char-alphabetic?”, 1); }
96 public static Boolean alphabetic(char c) {
97 return Character.isLetter(c) ? T : F;
98 }

Scheme のプログラムは静的に型検査を行いません。ですので、Scheme の実行時システムを実装する上では、以下のような （文法的には妥当な）Scheme の実行において char-alphabetic? 関数に本来この関数が想定しない関数が渡されることを考慮しなくてはなりません。

(char-alphabetic? (lambda () 1))

ところが、上のプログラムでは一見するとこの点を検査しているようには見えません。秘密は alphabetic メソッドのコードの 96 行目で引数の型が char として与えられている点にあります。Scheme の関数の引数には潜在的には任意のデータが与えられます。ですので、引数の型は Object だと考えるのが自然です。それに対して、敢えて char を宣言する場合、このメソッドが処理できるのは、実引数として char データが与えられた場合は、あるいは char に適合するクラスが与えられた場合のみです。この char に適合するクラスとは自動的な unboxing 処理によって char になり得る型すなわち Character クラスのインスタンスということになります。

先程のように関数を渡した場合、実引数は Lambda クラスのオブジェクトとなり、makeString メソッドは signature が適合しないために実行時例外が発生します。((研究室のみなさまへ、本日のセミナーのなかで私はキャストがどうのこうのという説明をしましたが、あれは間違いであることにきづきました。ここに書いた説明が正しいと思います。))

次にやはりよく似た例を見てみましょう。make-string は与えられた長さの文字列を返す関数です。引数に長さのみを与えれば、返される文字列は空白が埋められています。長さだけでなく、文字を引数に与えた場合には、その文字で埋められた文字列を返します。

この関数を実装する makeString メソッドの場合、さきほどとは異なり第二引数の型は Character です。

145 static { Subr.def(“Char”, “makeString”, “make-string”, 1, 1); }
146 public static String makeString(int length, Character fill) {
147 if (length == 0)
148 return “”;
149 else {
150 char c = (fill == null ? ‘ ‘ : fill.charValue());
151 char[] v = new char[length];
152 for (int i = 0; i < length; i++)
153 v[i] = c;
154 return new String(v);
155 }
156 }

この関数の第二引数については以下の三つの場合が想定されます。

+ 第二引数が与えられない
+ 第二引数に文字が与えられる
+ 第二引数に文字以外のデータが与えられる

第一の場合 fill は null となります。第二の場合 fill には Character 型のオブジェクトが与えられます。いずれも、Character 型で宣言した fill に適合します。第三の場合、すなわち第一引数が整数型で、第二引数が文字列以外の型の場合、makeString の signature は適合しません。このため、与えられた引数を処理するためのメソッドは存在しないことになり実行時エラーとなります。

ちなみに第一と第二の違いを吸収しているのは、150行目です。

ここで、仮引数 fill の型をその前の例と同様に char と宣言してしまうと、JVM の自動的な unboxing 処理が null を char にキャストするときに NullPointer 例外を発生すると思います。

以上のテクニックは JAKLD の実行時ライブラリの実装の至るところに見ることができます。「JAKLD はどこで実行時の型検査をしているのだろう」という疑問を持ったら、キャストとinstanceof演算子を探してみて下さい。

ここまで書いてから、[[湯浅先生の論文:http://www.yuasa.kuis.kyoto-u.ac.jp/~yuasa/jakld/pro.pdf%5D%5Dがあったことを思い出して読んでみたら、同じようなことが6-7ページにかけて書いてありました。Java が発生させた例外をSchemeのプログラマに分りやすい形で与えることに苦労なさったようです。実際に例外処理を行っているのは Subr クラスのなかのようです。ここは少し難所かもしれません。

さて、文字を表すのに基本型ではなく Character クラスのインスタンスを用いることの妥当性について、実行時システムの実装面から見てきたのですが、それでもやはり記憶領域は気になります。どうなっているのでしょう。

実は、JAKLD の内部では、ASCII文字は静的に確保されていて、実行時にそれに相当するオブジェクトは作成しません。以下がそれに相当するコードです。

23 private final static Character[] chtab = new Character[128];
24
25 static {
26 for (int i = 0; i < 128; i++)
27 chtab[i] = new Character((char) i);
28 }

このコードに続いて、Scheme の文字データを生成するための makeChar 関数があるのですが、そこでは文字コードが128未満の場合には、静的に作られた文字表 (chtab) を参照して該当する文字オブジェクトへの参照を返します。このため、個々の ASCII 文字については参照に相当するデータ量しか消費しません。JVM は 32bit アーキテクチャですから 4バイトだけが消費されることになります。2バイトの Unicode に比べて大きいと思うかもしれませんが、Scheme のデータを実装するためには普通であれば2バイトの Unicode のデータに加えて、データの型を表すタグが少なくとも1バイト必要になります。また、32ビットアーキテクチャで普通に32ビットアラインメントでデータを保存した場合32ビット以内のデータ量の大小は、普通は問題にはならないでしょう。

なお文字コードが128以上の文字データは、個別にオブジェクトが生成されます。JAKLD のユーザは Unicode を使うときはメモリーリークに気をつけましょう。