#はじめに
2016年に制作を開始したEasy-ISLisp（以下「EISL」という)はその年にインタプリタが完成し、2017年上期においてはそのコンパイラの制作をしていました。7月ごろに完成、公開しています。このコンパイラのことについて書き記したいと思います。
#FAST計画
コンパイラのアイディアはScheme世界の重鎮、Clinger先生からのMLでの助言が基になっています。これをもとに当時、制作中だったScheme処理系にコンパイラの制作を始めました。しかし、近年、どんどん仕様複雑化、巨大化するSchemeに嫌気がさしました。そんな折、五味先生の本が発端となってISLispに鞍替えすることにしました。Scheme用のコンパイラのアイディアを基に、このコンパクトなLispに最高に高速なコンパイラを装備したいと思いました。FAST計画と名付けてプロジェクトを開始しました。
#実行例
コンパイラはC言語へのトランスレート方式です。Cソースを生成し、GCCにより動的コンパイルし、REPLより動的リンクをする方式をとっています。以下はその実行例です。
C:\MinGW\mingw32\bin\eisl>eisl -c compiler.o
eisl -c compiler.o
Easy-ISLisp Ver0.84
> (compile-file "tarai.lsp")
initialize
pass1
pass2
compiling TARAI
compiling FIB
compiling GFIB
compiling TAK
compiling LISTN
compiling TAKL
compiling CTAK
compiling CTAK-AUX
finalize
invoke GCC
T
> (load "tarai.o")
T
> (tarai 12 6 0)
12
>
#マイクロベンチマーク
有名処理系であるSBCLと比較してみます。
EISL
> (time (tarai 12 6 0))
Elapsed Time(second)=0.084257
<undef>
> (time (fib 40))
Elapsed Time(second)=1.334401
<undef>
>
SBCL
* (time (tarai 12 6 0))
Evaluation took:
0.084 seconds of real time
0.078125 seconds of total run time (0.078125 user, 0.000000 system)
92.86% CPU
265,954,567 processor cycles
0 bytes consed
12
* (time (fib 40))
Evaluation took:
1.507 seconds of real time
1.500000 seconds of total run time (1.500000 user, 0.000000 system)
99.54% CPU
4,808,655,812 processor cycles
0 bytes consed
102334155
*
小整数の計算ですと、まずまずの結果を出しています。後述しますが、浮動小数点数やリスト構造ですとSBCLの方が優れています。
#小整数の即値化
EISLはインタプリタにおいては小整数は素朴にセルを生成していました。これはセルを多量に消費し、計算も遅くなります。コンパイラでは小整数を即値化しています。
セルの番地を表す整数のうち小整数（-999999999～999999999）は正数の場合には最上位より2番目のbitに1を立てることにより小整数とすることにしました。セル番地は正数ですから小整数の負数はそのままで即値としました。
また、コンパイラとは直接関係ありませんが、EISLでは小整数とBIGNUMの間にLONGNUMを置いています。Cのlong int型を使っています。こうした工夫により18桁程度の素因数分解は数秒以内に計算を終えることができています。
> (prime-factors 12983719287123123123123231)
(110208079664461 43661 11681 11 7 3)
> (time (prime-factors 12983719287123123123123231))
Elapsed Time(second)=0.270218
<undef>
>
#末尾再帰最適化
ISLispでは末尾再帰最適化は仕様としては要求されていません。しかし、SBCLなど多くの有名処理系が末尾再帰最適化をサポートしています。EISLにおいても末尾再帰最適化をサポートしています。次のような末尾再帰の関数はループに変換しています。従って10億回程度であれば数秒で実行します。
(defun foo (n)
(if (= n 0)
t
(foo (- n 1))))
> (foo 1000000000)
T
> (time (foo 1000000000))
Elapsed Time(second)=2.395850
<undef>
>
因みに以下はSBCLでの実行例です。このようなコードではEISLの方が良い結果をだしています。
* (time (foo 1000000000))
Evaluation took:
14.920 seconds of real time
14.859375 seconds of total run time (14.828125 user, 0.031250 system)
[ Run times consist of 0.126 seconds GC time, and 14.734 seconds non-GC time. ]
99.59% CPU
47,624,394,804 processor cycles
11,115,106,256 bytes consed
T
*
#型推論
現状のEISLコンパイラは不完全です。小整数の計算ではまずまずの結果を出すのですが、浮動小数点数を使う計算になりますと途端に遅くなります。浮動小数点数ではセルオブジェクトを生成し、計算もインタプリタ内にある計算ルーチンを呼び出すからです。浮動小数点数についてもCのオブジェクトとして生成し、Cの演算ルーチンを直接呼び出すことができれば高速化できるはずです。
ISLispはオブジェクト指向が仕様として組み込まれています。ILOSといいます。＜number＞ ＜integer> というようなクラスがあらかじ用意されていて、クラスチェックのためと思われるtheという構文が用意されています。これをコンパイラに応用することにしました。例えば竹内関数はその計算範囲は実際的には小整数であることがわかっています。しかし、コンパイラはLONGNUM BIGNUMの可能性を否定できないことからこの範囲をカバーしたコードを生成しています。小整数に型を限定してしまえばもっと効率の良いコードを生成できるはずです。
(defun tarai (x y z)
(the <fixnum> x)(the <fixnum> y)(the <fixnum> z)
(if (<= x y)
y
(tarai (tarai (- x 1) y z)
(tarai (- y 1) z x)
(tarai (- z 1) x y))))
浮動小数点数を使ったフィボナッチ数は次のように型を指定します。
(defun fib (n)
(the <float> n)
(if (< n 2.0)
1.0
(fib (- n 1.0))))
さらにSML言語にあるような型推論を考え始めました。(- n 1.0) という演算から変数ｎは浮動小数点数であることが推定されます。型指定をすることなく自動的に型推論し適切なCコードを生成すれば性能は飛躍的に向上するはずです。
こうしたアイディアをもとに実装を始めたのものの途中経過を書き記したものが次の記事です。
「ISLispにおける型推論器の制作」
https://qiita.com/sym_num/items/ba3608abebf5c12385c5
まだ、不完全です。型推論はPrologの推論過程と同じ手法を使っています。
現状のEISLはキカイダー・ジローのようです。不完全な良心回路を抱えています。良心回路を完全化したキカイダーはめちゃくちゃ強いのです。いずれ型推論の実装を完成させ、EISLを完全にしたいと思っています。
#C言語ラッパー
EISLのコンパイラはC言語ラッパーを有しています。Lispコード中に容易にCコードを埋め込むことができます。次はラズパイ用のWiringPiをCラッパーで記述した例です。
(c-include "<wiringPi.h>")
(c-include "<wiringPiSPI.h>")
(c-option "-lwiringPi")
(defun wiringpi-setup-gpio ()
(c-lang "Fmakeint(wiringPiSetupGpio());"))
(defun wiringpi-spi-setup-ch-speed (x y)
(if (not (integerp x)) (error "wiringgpi-spi-setup-ch-spped: not integer" x))
(if (not (integerp y)) (error "wiringgpi-spi-setup-ch-spped: not integer" y))
(c-lang "Fmakeint(wiringPiSPISetup( (INT_MASK & X), (INT_MASK & Y)));"))
(defun pwm-set-mode (x)
(cond ((eq x 'pwm-mode-ms)
(c-lang "pwmSetMode(PWM_MODE_MS);"))
((eq x 'pwm-mode-bal)
(c-lang "pwmSetMode(PWM_MODE_BAL);"))
(t (error "pwm-set-mode: not integer" x)))
t)
通常、Lispからラズパイのハードを利用しようとすると、FFIを使ってCで書かれたものを呼び出すほかなかったと思います。上記のようにEISLコンパイラでは簡単にC言語を埋め込むことができます。ラズパイ遊びにEISLが使えるのではないかと思います。あるいはWindowsのAPIを直接にLispから呼び出すこともできますから、内蔵MIDIから音を出したり、Window描画APIを呼び出すことも可能です。
#終わりに
私は20代の頃に竹内郁雄先生のLisp本を読んでLispを習得しました。先生は「Lispのココロは自由である」とおっしゃっていたように思います。言語仕様やライブラリにがんじがらめにされてするプログラミングは少なくとも私は楽しくありません。Lispから自由にハードにアクセスできたり、WEB資源にアクセスできたら楽しいだろうと思いました。ライブラリが準備されるのを待つのではなく、自分で作ってしまえばいい、そしてEISLはそのための手段を用意しておきたいと思っています。Lispによるハッキングは楽しいのですから。
EISLの実装はここに置いてあります。非商用利用は無償です。
http://eisl.kan-be.com/library/easyislisp.html
EISLコンパイラの詳細については下記を参照してください。
https://qiita.com/sym_num/items/793adfe118514668e5b0