Java による半分の Arc の改訂実装

2010.10.1, 2011.10.20 (鈴)

1. 概要

Semi-Arc 10.0 を改訂し,プログラム上のいくつかの誤りを修正するとともに,より忠実な Arc 言語の実装とした。

右図は MacBook Pro, Core Duo 2GHz, DDR2 2GB, Mac OS X "Leopard" 10.5.8 上の Java 1.5.0_24 で,改訂版である Semi-Arc 10.1 を動作させた例である。 Windows でも Cygwin を使えば,このとおりに操作できる。

Semi-Arc 10.1 は,Paul Graham らによるオリジナルの Arc 実装の初期化スクリプトである arc.arc をそのまま自身の初期化ファイルとしている (Copyright.txt)。 右図の例で (nqueens 6) の実行時間を計測している time は,arc.arc が定義するマクロの一つである。 Semi-Arc 10.1 はより完全に近い Arc の実装であり,Semi-Arc 10.0 で使っていた簡易版初期化スクリプト Prelude.txt にかえて,本物の初期化スクリプトを使うことができる。

言語本体に対する主要な変更は,有理数のサポートである。 必要に応じて java.math.BigInteger を分子と分母に使うことにより, 任意長の有理数を扱うことができる。 有理数は Rational.java が実現している。これは任意長の整数演算のための下請けとして BuiltinMath.java の整数関数を使う。

日本語文字を扱うことができること, フリーシンボルの捕捉を自動的に回避すること等の特長は,Semi-Arc 10.0 からそのまま引き継いでいる。

Java による組込み Lisp 関数を新しく定義する方法は,L2 Lisp 9.2 と基本的に変わらない。 ただし, Callable.java のコンストラクタ引数仕様が変更されている点と, Lisp 内で文字列が (変更不可能な) java.lang.String ではなく (変更可能な) char[] によって表現されていることに注意されたい。 簡単のため,Lisp スクリプト内から動的に組込み関数をロードする手段として 2引数の java-load ではなく1引数の java-def を用意した。その引数は Callable の派生クラスの名前の文字列である。

右図の例では,組込み関数 printf を実現する Java クラス PrintfExample をソースからコンパイルし, arc の対話セッション内で (java-def "PrintfExample") によってロードし,let 式の中で,日本語文字を含む文字列および整数を引数として printf を呼び出している。


一年ぶりの改訂である Semi-Arc 10.2 では主に有理数での無限大の取り扱いについてのバグを修正した。 Arc 言語としてサポートするデータ型や関数の種類は 10.1 版と同じである。

有理数演算の例を示します。
arc> (/ 640 480)
4/3
arc> (* 4/3 3)
4
arc>
有理数を実現する Rational クラスを java.lang.Number の派生クラスとして定義しましたが,Semi-Arc で直接使わないメソッドは未実装のままにしています。 必要な下請けメソッドとともに編成し直し,いくつかのユーティリティを補完し, 汎用の有理数クラスとして完成させることは読者への課題とします。 MIT/X11 ライセンスですから,その成果は (読者が自由なソフトウェアの信奉者であっても,なくても :-) 自由度高く使えます。

2. Arc との相違点

Arc 言語として Semi-Arc 10.1 に欠けているのは次の点である。

Arc 言語と比べて Semi-Arc が異なった仕様を実現しているのは次の点である。 これらはむしろ長所といってよいが,Arc との互換性のために注意が必要である。 フリーシンボルの補足回避については 前回第3節 も参照されたい。

2.1 Semi-Arc 10.2 の変更点

Semi-Arc 10.2 では Semi-Arc 10.1 に対し,主に有理数演算のバグを修正した。

  1. 下記のルールが有理数に対する + 関数と expt 関数でも成り立つようにした。
    • 浮動小数点演算で結果が Infinity になるような場合は 1/0 を結果とする。
    • 浮動小数点演算で結果が -Infinity になるような場合は -1/0 を結果とする。
    • 浮動小数点演算で結果が NaN になるような場合は実行時例外を送出する。
    Rational.java の Rational#add(Rational) と BuiltinMath.java の BuiltinMath.expt(Number, Number) を参照されたい。前者のコードでは無限大を特別扱いしておらず,自然に上記の結果が得られている点に注意されたい。
    arc> (+ (/ 12.0 0) (/ 34.0 0))
    Infinity
    arc> (+ (/ 12 0) (/ 34 0))
    1/0 
    
  2. Lisp 式の読み取りでは,0/0 のような不正な有理数リテラルを構文誤りとして扱うようにした。
    LispReader.java の LispReader.tryToParseAsNumber(String) を参照されたい。
    arc> (+ 0/0 9)
    *** SyntaxError: not a number: 0/0 -- 1: (+ 0/0 9)
    

また,これとは別に,意味論上の矛盾を避けるため, 規定の入れ子深さを超えても静的マクロ展開が終わらないときは, 動的展開に持ち越すのではなく評価時例外とするようにした。 これに付随して,規定値を設定する公開メソッド LL.setMaxMacroExps(int) 等を用意した。 また,この変更を受けて公開メソッドIInterp#expandMacros(Object, int) の仕様も変更した。 LL.javaIInterp.java および IInterp の実装である Interp.java を参照されたい。

Semi-Arc 10.2 は Java 5, Java 6, Java 7 で動作する。

3. Java による他の Arc 処理系

前回 Semi-Arc 10.0 の作成後,Java による Arc 処理系がすでに少なくとも二つ公開されていることを知った。

試行時現在の Jarc はインタープリタでの末尾再帰の最適化をしておらず,スタックあふれのため 9queens.ar をそのまま実行することはできない。 下記は

(time (prn (nqueens 5)))

を評価するように 9queens.ar を改めて, Dell Optiplex GX280, Pentium4 3.2GHz, 1GB RAM の Windows XP Professional SP3 上の Cygwin bash でそれぞれ実行した例である。 Jarc は 2010 年 9 月 17 日の jarc19 を, Rainbow は 2010 年 9 月 16 日時点の版をそれぞれ使った。 この結果による限り,Semi-Arc は高速な処理系の部類に入る。

01:~/tmp$ java -jar semi_arc.jar 5queens.ar
((4 2 5 3 1) (3 5 2 4 1) (5 3 1 4 2) (4 1 3 5 2) (5 2 4 1 3) (1 4 2 5 3) (2 5 3
1 4) (1 3 5 2 4) (3 1 4 2 5) (2 4 1 3 5))
time: 16 msec.
01:~/tmp$ java -jar jarc.jar 5queens.ar
((4 2 5 3 1) (3 5 2 4 1) (5 3 1 4 2) (4 1 3 5 2) (5 2 4 1 3) (1 4 2 5 3) (2 5 3
1 4) (1 3 5 2 4) (3 1 4 2 5) (2 4 1 3 5))
time: 110 msec.
01:~/tmp$ cd rainbow/src/arc/
01:~/tmp/rainbow/src/arc$ java -jar rainbow.jar -f ../../../5queens.ar -q
*** redefining no
*** redefining map1
*** redefining pr
*** redefining list
((4 2 5 3 1) (3 5 2 4 1) (5 3 1 4 2) (4 1 3 5 2) (5 2 4 1 3) (1 4 2 5 3) (2 5 3
1 4) (1 3 5 2 4) (3 1 4 2 5) (2 4 1 3 5))
time: 15 msec.
01:~/tmp/rainbow/src/arc$ java -version
java version "1.6.0_21"
Java(TM) SE Runtime Environment (build 1.6.0_21-b06)
Java HotSpot(TM) Client VM (build 17.0-b16, mixed mode)
01:~/tmp/rainbow/src/arc$

4. 謝辞

本処理系は,2010 年現在の Arc の言語仕様について下記サイトを参照し,細部について Arc3 の実装等を確認して作りました。

初期化スクリプト arc.archttp://arclanguage.org で配布されている Arc3 に含まれる同名のファイルのそのままのコピーです。 Arc3 の著作権表示を下記に示します。

This software is copyright (c) Paul Graham and Robert Morris.  Permission
to use it is granted under the Perl Foundation's Artistic License 2.0.


総目次へ


Copyright (c) 2010, 2011 OKI Software Co., Ltd.