私は数年前、clojureを学習していて挫折しました。
私が今まで一番使ってきたlispは、xyzzyというエディタに付属する common lispです。
私は、今までに何回か小さな lispインタープリタを作成した事があります。
私が作りたいlisp
- common lispの入門書に書いてあるぐらいの小さなlisp
- それにclojure風の便利機能を少し追加すること
- Java25で書くこと
コンセプト
clojureの学習に挫折した事がある中年のための、 common lispのサブセット。
既存の common lisp の知識に加えて少し覚えるだけで、clojure風のパワーを手に入れられること。
サブセットをどうやって決めるか？
色々 検索したのですが、私の好みに合いそうなものは見つかりませんでした。
uLispというマイコン用の lispが、一番私の好みに合っていました。
今はこの uLispのテストコードが通るインタープリタを作っています。
（まだ全部のテストは通りません）
コンパイラ
インタープリタ開発と並行して、コンパイラ作成も進めています。
Javaで書かれた多くのlispは直接JavaのJVM中間言語を生成します。
私が作っているのは、Javaのソース生成をするコンパイラです。
トランスパイラと言った方が正しい様です。
コンパイルの最初の目標
This is SBCL 2.4.5, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.
SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses. See the CREDITS and COPYING files in the
distribution for more information.
* (defun lam2 (x y) (lambda (z) (list x y z)))
LAM2
* (defvar zz (lam2 "x" "y"))
ZZ
* (funcall zz 3)
("x" "y" 3)
*
上のコードに示す、lam2がコンパイルできれば、クロージャのコンパイルが出来た事になります。
まずは、このコードのコンパイルを考えています。
コンパイラのフェーズ
[ジェミニの回答]
翻訳の基本的な流れは、字句解析、構文解析（構文木の生成）、意味解析、最適化、そしてコード生成の順に進みます。
私が作成しているトランスパイラは、構文木の生成の所に特徴があります。
今のところ最適化は全く行っていません。
[使い方のイメージ]
現在の目標は、関数単位のコンパイルなので、以下のような利用イメージです。
shlisp.compiler >> (defun lam2 (x y) (lambda (z) (list x y z)))
shlisp.compiler >> (make-java 'lam2)
今の所、関数単位のコンパイルの完成が優先です。ファイル単位のコンパイルは、だいぶ先になる予定です。
試作中トランスパイラの構文木
抽象構文木（AST：Abstract Syntax Tree）は、自作Lispに追加したclojure風の機能を使って表現しています。
上に示した 関数 lam のASTは以下のようになります。
{
:type :defun
:name lam2
:params [{
:name x
:location {
"special" false
"kind" "LOCAL"
"index" 2
"depth" 0}}
{
:name y
:location {
"special" false
"kind" "LOCAL"
"index" 3
"depth" 0}}]
:body [{
:type :block
:slot-idx 4
:name lam2
:body [{
:type :lambda
:local-count 1
:params [{
:name z
:location {
"special" false
"kind" "LOCAL"
"index" 0
"depth" 0}}]
:body [{
:type :lisp-one-call
:method "LIST"
:import "io.github.shlisp.runtime.StdFunctions"
:args ({
:type :resolved-var
:name x
:dynamic ()
:depth 1
:index 2
:kind CAPTURED}
{
:type :resolved-var
:name y
:dynamic ()
:depth 1
:index 3
:kind CAPTURED}
{
:type :resolved-var
:name z
:dynamic ()
:depth 0
:index 0
:kind LOCAL})}]}]}]
:local-count 5}
clojure風の中カッコ ( { ... } ) と、大カッコ ( [ ... ] )で、ASTが出来ているのが、見ていて楽しいです。
コンパイラの作成中、ジェミニに何度か質問しました。その時頂いたアドバイスとしては、「ASTを作る時になるべく多くの情報を収集しろ」というアドバイスでした。
上のASTを見ると、本当に余分な情報が沢山ついています。
しかし、以前書いていたソースから、この方式に書き直してから、コンパイラの見通しが良くなりました。
ASTの方に面倒な検索は全部やらせてしまいます。
後続の処理は、出来上がったASTから単純にJavaのソースを生成するだけです。
後続の処理が簡単になった事で、自分でも理解しやすいソースになりました。
最も特徴的なのは、(list x y z)の呼び出しの所です。
:method "LIST"
:import "io.github.shlisp.runtime.StdFunctions"
ここにもう、これだけ情報があるので、Javaのソースコード生成の時は、何をインポートしないといけないのか、自明です。
生成されたJavaソース
import io.github.shlisp.com9.RuntimeEnv;
import io.github.shlisp.except.BlockReturnException;
import io.github.shlisp.mvinterp.AbstractLispFunction;
import io.github.shlisp.mvinterp.LispValues;
import io.github.shlisp.objects.DynamicCell;
import io.github.shlisp.objects.Var;
import io.github.shlisp.runtime.VarUtil;
import static io.github.shlisp.runtime.StdFunctions.LIST; // (1)
public class lam2 extends AbstractLispFunction {
public lam2() {
}
public LispValues main(RuntimeEnv env) {
env.set(4, new Object());
try { // (2)
return LispValues.of(new __lambda_1001(env));
} catch (BlockReturnException e) {
if (e.matches(env.get(4))) return e.getValue();
throw e;
}
}
public static class __lambda_1001 extends AbstractLispFunction { // (3)
RuntimeEnv outerEnv;
public __lambda_1001(RuntimeEnv env) {
this.outerEnv = env;
}
@Override
public LispValues apply(Object[] args) {
RuntimeEnv env = new RuntimeEnv(1, outerEnv);
env.set(0, args[0]);
return newMethod(env);
}
public LispValues newMethod(RuntimeEnv env) {
// (4)
return LispValues.of(LIST.invoke(env.getCaptured(1, 2), env.getCaptured(1, 3), env.get(0)));
}
}
@Override
public LispValues apply(Object[] args) {
RuntimeEnv env = new RuntimeEnv(5); // (5)
env.set(2, args[0]);
env.set(3, args[1]);
return main(env);
}
}
(1) ASTに変換時に 集めてきた情報からインポート文を生成しています。
(2) Common Lispの仕様で、関数は暗黙のBLOCKを生成します。このBLOCKのために try- catchが必要になります。
なお、LispValuesというクラスは、多値を入れるためのクラスです。
(3) コンパイル目標(lam2という関数)の中にある、lambdaをJavaにトランスパイルしたクラスです。
(4) (list x y z)の所が、(4)のようトランスパイルされています。
(5) コンパイル目標(lam2という関数)の入り口の部分のコードです。
RuntimeEnvという実行時用の環境を作成しています。
環境について
私が作成しているlispは３種類の環境を持っています。
１．インタープリタ用の環境
これは、シンボルと値の対応表です。他には、ローカル関数定義などが入ります。
２．実行時用の環境（コンパイルされたJavaが動く時に使う環境）
環境の何番目のスロットから値を取り出せ、といった感じの環境です。
下にコードを示します。
３．コンパイラが使う環境
コンパイラが使う環境は、コンパイラが動いている時のみ存在します。
コンパイルが終わったら捨ててしまって良い環境です。
これは、シンボルと、スロット位置の対応関係を管理します。
実行時用の環境
public final class RuntimeEnv {
private final Object[] slots;
private final RuntimeEnv parent; // ★ 親（外側）の RuntimeEnv
// トップレベル用コンストラクタ（親なし）
public RuntimeEnv(int size) {
this(size, null);
}
// ★ Lambda（クロージャ）生成用コンストラクタ（親を指定）
public RuntimeEnv(int size, RuntimeEnv parent) {
this.slots = new Object[size];
this.parent = parent;
}
// --- 自分のフレーム（LOCAL）へのアクセス ---
public Object get(int index) {
return slots[index];
}
public void set(int index, Object value) {
slots[index] = value;
}
public RuntimeEnv getParent() {
return parent;
}
// --- クロージャ（CAPTURED）用：depth をたどって親環境にアクセス ---
/**
* depth 分だけ親をたどり、指定したインデックスのスロットから値を取得する
* @param depth 親をたどる階層数 (0なら自分、1なら直近の親)
* @param index CompileEnv が割り当てたスロット番号
* @return
*/
public Object getCaptured(int depth, int index) {
RuntimeEnv env = this;
for (int i = 0; i < depth; i++) {
env = env.parent;
if (env == null) {
throw new IllegalStateException("RuntimeEnv parent is null at depth: " + i);
}
}
return env.slots[index];
}
/**
* depth 分だけ親をたどり、指定したインデックスのスロットの値を更新する (setq / setf 用)
* @param depth
* @param index
* @param value
*/
public void setCaptured(int depth, int index, Object value) {
RuntimeEnv env = this;
for (int i = 0; i < depth; i++) {
env = env.parent;
if (env == null) {
throw new IllegalStateException("RuntimeEnv parent is null at depth: " + i);
}
}
env.slots[index] = value;
}
}
最後に
ここまで、お読み頂きありがとうございました。
コンパイラの方は、まだまだ、やる事が沢山ありますが、いつか適当なタイミングで、アルファー版か
ベータ版か、わかりませんが、デモ程度のものをリリースできたらと思っています。