はじめに
Easy-ISLispのためのコンパイラを開発しています(FAST計画といいます）。平成29年8月リリースしました。仕様、問題点などを書き留めておこうと思います。
基本的アイディア
萩谷先生などのGCLを参考にしています。ISLispコードを等価なCコードに変換し、GCCによりオブジェクトファイルを生成します。これを動的にリンクすることによりISLisp処理系に読み込んでいます。関数の内部定義はGCCの拡張機能を利用しています。このためlabels、flet構文のスコープに制限があります。
コンパイル方法
起動時に-cオプションを使ってコンパイラを読み込んおくか、あるいはload関数でコンパイラを読み込みます。コンパイラのソースはcompiler.lspです。コンパイル済みのものはcompiler.oとなっています。
(compile-file filename) でコンパイルを開始します。filenameは文字列で与えます。compile-file関数はLispファイルを基にC言語によるファイルを生成します。さらにGCCを起動し、動的リンクオブジェクトを生成します。
セルフコンパイル
ver1.9以後、メモリ不足によりセルフコンパイルはできません。コンパイラをモジュール化したためその展開に多くのセルを必要とします。現在のコンパイラはLispコードで3500行ほどです。メモリ不足です。
コンパイル済みのファイルのload
通常のLispファイルと同様にload関数で読み込みます。識別子がo（オー）の場合には、load関数は動的リンクの処理をします。
小整数の即値化
インタプリタのEISLでは小整数も含めてすべてにつきセルオブジェクトを生成していました。このためにすぐにGCが起動し高速化は困難でした。コンパイラでは -999999999 ~ 999999999 までの整数は即値化をし、セル消費をしないようにしています。この結果、竹内関数やフィボナッチ数列の計算はかなり高速化することができました。ver1.9以後はインタプリタにおいても小整数を即値としました。この結果、コンパイラはシンプルになりました。
> (load "tarai.o")
T
> (time (tarai 12 6 0))
Elapsed Time(second)=0.068000
<undef>
> (time (fib 40))
Elapsed Time(second)=1.194000
<undef>
>
末尾再帰最適化
ISLisp規格では末尾再帰最適化は要請されていません。しかし、Schemeと同様に末尾再帰を繰り返しに置き換えるコードを生成しています。次の程度であればスタックも消費しませんし、速度もまずまず高速です。
(defun foo (n)
(if (= n 0)
t
(foo (- n 1))))
> (load "test.o")
T
> (foo 1000000000)
T
> (time (foo 1000000000))
Elapsed Time(second)=1.789000
<undef>
>
コンパイラのための拡張機能
コンパイラのために次の関数を独自拡張しました。
(subrp x) xが組み込み関数である場合にt、そうでなければnil
(macrop x) xがマクロである場合にt、そうでなければnil
(system str) str文字列をOSで実行する。GCC起動のため
(freedll) 直前に動的リンクしたファイルをリンク解除する。
(fixnump x) 小整数の場合にt、そうでなければnil
(longnump x) LONGNUMの場合にｔ、そうでなければnil
(bignump x) BIGNUMの場合にt、そうでなければnil
(readed-array-list x) #2a((1 2)(3 4))のような定数の配列をリスト((1 2)(3 4))に変換する。
(ignore-toplevel-check x) 引数としてtを渡すとdefclassなどのトップレベルチェックを外す、nilを渡すと元に戻してチェックをする。
(self-introduction) Linux系ならばlinuxシンボル、Windowsならwindowsシンボルを返す。
コンパイラがOSの種類によって動作を変えるため。
(get-method x) 名前ｘの包括関数のmethodをすべて取り出す。
(get-method-body x) method x の実体を取り出す。
(get-method-priority x) method x の優先順位を取り出します。
整数値であり次のようになっています。
AROUND 11
BEFORE 12
PRIORITY 13
AFTER 14
これらは包括関数のコンパイルに使います。包括関数はインタプリタでいったん、すべてのmethodを整理、保存した後においてその実体を取り出し、SUBRに変換します。
(format stream string)
string中にシングルクォートが２つ続いていた場合に独自の動作をします。連続したシングルクォートの間の文字列に対しては~%などの特殊文字制御を無視します。また、連続した２つのシングルクォートは１つのダブルクォートに変換されます。これはLispコードをCコードに変換し文字列ストリーム中にプールし、最後にファイルに出力する関係上、必要になったものです。
例
> (format (standard-output) "''hello~% world~A ''")
"hello~% world~A "NIL
>
スコープの制約
以下はM.Hiroiさんのページからの引用コードです。これはISLisp仕様を満たした正しいコードです。
(defun iota (n m)
(for ((m m (- m 1))
(a nil (cons m a)))
((< m n) a)))
FASTのfor構文では、これが意図通りに動作しません。変数部の(m m (- m 1)) で第1番目のmはforで使う変数であり、第2番目は引数として与えられたmです。for構文はこれを初期値としますが、そのスコープはforの外側を見ています。FASTはC言語に変換しており、Cのスコープはそのようになっていません。FASTでは次のように書いてください。
(defun iota (n m)
(for ((m1 m (- m1 1))
(a nil (cons m1 a)))
((< m1 n) a)))
注 2020年8月23日 コンパイラを改良し、forの前者の例も正常にコンパイルできるようにしました。
labels flet の制約
C言語では関数内に局所関数を定義することはできないこととなっています。GCCは拡張機能によりこれが可能となっています。静的スコープの動作を確保しつつ速度を稼ぐのにこの拡張機能を使いました。しかし、スコープがLispのものとは異なります。
lambdaの実装
lambdaは本来、無名関数なのですが、Cの関数にするために敢えて名前を付けています。compile-fileのファイル名＋自然数をその名前としています。静的スコープにするためには自由変数を保持しておく必要があります。これはGCLの方式をヒントにしました。保持しておかなければならない自由変数をリストにしてlambdaの関数名シンボルに紐つけてあります。lambda本体でアクセスするときにはnthで行っています。
lambdaの制約
lambda式のネストは3重までです。それ以上はエラーとなります。
以下はM.Hiroiさんのページからの引用コードです。これはISLisp仕様を満たした正しいコードです。
(defun id-search (start goal)
(labels ((dfs (limit path)
(if (= limit (length path))
(if (eq (car path) goal)
(print (reverse path)))
(for-each
(lambda (x)
(if (not (member x path))
(dfs limit (cons x path))))
(cdr (assoc (car path) adjacent))))))
(for ((limit 1 (+ limit 1)))
((= limit 7))
(format (standard-output) "----- ~D -----~%" limit)
(dfs limit (list start)))))
FASTコンパイラでは、これがコンパイルできません。lambdaはトップレベルにおいて名前をもったC関数として生成されます。lambdaの中で局所定義関数のdfsを呼び出しています。生成されたlambdaに相当するC関数からはCの局所定義関数として生成したdfsを参照することができません。
そこで、このような場合には下記のようにlabelsを使わないで書いてください。
(defun id-search (start goal)
(for ((limit 1 (+ limit 1)))
((= limit 7))
(format (standard-output) "----- ~D -----~%" limit)
(dfs limit (list start))))
(defun dfs (limit path)
(if (= limit (length path))
(if (eq (car path) goal)
(print (reverse path)))
(for-each
(lambda (x)
(if (not (member x path))
(dfs limit (cons x path))))
(cdr (assoc (car path) adjacent)))))
包括関数での制約
この制約はver2.0において解消しました。
以下はM.Hiroiさんのページからの引用コードです。これはISLisp仕様を満たした正しいコードです。
(defgeneric hash-func (k))
(defmethod hash-func ((s <string>))
(for ((i 0 (+ i 1))
(a 0))
((>= i (length s)) a)
(setq a (+ (* a 8) (convert (elt s i) <integer>)))))
method定義では引数名は包括関数を定義したときと異なる名前を付けても正しく動作する必要があります。インタプリタはその通りになっています。コンパイラの方は簡単にするために引数の名前を同じにしないといけないという制約があります。α変換をすればできるのだとは思うのですが、簡単に済ませることにしました。次のように記述する必要があります。
(defgeneric hash-func (k))
(defmethod hash-func ((k <string>))
(for ((i 0 (+ i 1))
(a 0))
((>= i (length k)) a)
(setq a (+ (* a 8) (convert (elt k i) <integer>))
C言語ソースとの混在
ISLispの関数記述中にC言語ソースを挿入できる機能を独自拡張しています。GCCの豊富なライブラリを簡便にISLispから使いたいためのものです。以下は単純なサンプルです。
(c-include "<stdio.h>")
(defun 1+ (n)
(c-lang "res=N+1"))
> (compile-file "test.lsp")
initialize
pass1
pass2
compiling 1+
finalize
invoke GCC
T
> (load "test.o")
T
> (1+ 3)
4
>
このようにCでの記述を混在できます。これを利用してラズパイのWiringPIを呼び出すとか、socketを呼び出す関数をLisp関数として記述することができます。CFFIに拠らないため、簡単にCとリンクできます。
用意してある関数は下記のものです。
(c-include x) #includeを挿入します。 例 (c-include "")
(c-define x y) #defineを挿入します。 例 (c-define "MAXINT" "999999999")
(c-lang x) c言語ソースを挿入します。 例 (c-lang "a = a+1;")
(c-option x) コンパイルオプションを追加します。 例(c-option "-lwinmm")
いずれの関数もインタプリタにおいては無視されます。
下記はWindowsのAPIを利用してMidi回線をオープンする関数の記述例です。
(c-include "<windows.h>")
(c-include "<mmsystem.h>")
(c-option "-lwinmm")
(c-define "MIDIMSG(status,channel,data1,data2)"
"( (DWORD)((status<<4) | channel | (data1<<8) | (data2<<16)) )")
(c-lang "HMIDIOUT hMidiOut;")
(defun midi-out-open ()
(c-lang "midiOutOpen(&hMidiOut, MIDI_MAPPER, 0, 0, CALLBACK_NULL);" )
t)
ソースコード、実行ファイル
ソースコードは拙作「ISLisp制作キット」の付録としてアップロードしてあります。不具合検出をしつつ、定期的にバージョンアップをしています。
https://www.amazon.co.jp/dp/B01IMUKOHS
無償配布の実行ファイルは下記にアップロードしてあります。コンパイラのソースとコンパイル済みのコンパイラも付属しています。
http://eisl.kan-be.com/library/easyislisp.html