RustでLisp

Lispというのは可変なデータ構造を持つ言語なので、(set-car! x x)とした瞬間に循環参照が発生し参照カウントは永遠に0にならずGC不可避、可変性を廃しても(letrec (f ...) (g ...))としたら相互参照が登場してしまうわけで参照カウントが永遠に0にならず…… といった具合でRustに入門するための題材としては難しいのではということにパーサ書いたあとで気づいたけど不変データ構造でローカルな相互再帰なくてもS式使ってればLispだよね(妥協)という意識レベルの低い新年と相成った。

でもletrecはRC<T>だけでいける気がしてきた

ウムー https://doc.rust-lang.org/book/ch15-06-reference-cycles.html#preventing-reference-cycles-turning-an-rct-into-a-weakt

Cc<T>: A reference counted type with cycle collection for Rust.

図

図2

fn apply_rec(ref, args) {
  let rec_lambda = ref.env.lookup(ref.key);
  apply_lambda(args, ref.env, rec_lambda.body)
}

的な。
f内でgが参照されるときは、ref(key="g", env=env)を新しく生成する?

impl Env for RecEnv {
  fn lookup(name: &str) {
    if self.rec_lambdas.has_key(name) {
      Ref::new(self, name)
    } else {
      self.parent.lookup(name)
    }
  }
}

的な……

ローカル変数への代入を許すとこうなる……

当然そうなるの図

RC<T>には弱参照を作る機能があるが、上記の問題をそれで解決できるだろうか?
実行時に循環参照を検出して、動的にRC<T>とWeak<T>を使い分けるみたいなことはあまりしたくない……

Rc can detect and deallocate cycles of Rcs through the use of Adoptable. Cycle detection is a zero-cost abstraction.
https://artichoke.github.io/cactusref/cactusref/

nightlyのオプション使えばrcの循環参照検出できそう https://github.com/japaric/rust-san

RUSTFLAGS="-Z sanitizer=leak" cargo +nightly run

図です

ア゛〜〜〜ッ

let-recで定義した変数を再代入しようとすると困るな、循環参照から逃れられないので禁止しましょう。
特定の条件(外部環境を参照していない/参照している環境が束縛対象の変数と同じ所属)を満たせば理論上いける気はするが……

enum Value {
  // ...
  Cons(Rc<Value>, Rc<Value>)
}

この場合はcar/cdrを得るのに

fn car(self: &Value) -> Option<&Value> {
  match self { Value::Cons(car, _) => Some(car) }

という操作が可能だが、可変にするために

struct Value {
  // ...
  Cons(Rc<RefCell<Value>>, Rc<RefCell<Value>>)
}

とするとそうはいかない。RefCellの中身への参照のライフタイムはValueのライフタイムと別に管理する必要があるため。

返り値を&Value から Ref<Value>にすればいいけど、もうcloneでもいいような気がしますね

enum Value {
    Bool(bool),
    Int(i32),
    Sym(Rc<str>),
    Nil,
    Ref(Rc<RefValue>)
}
enum RefValue {
    // ...
    Cons(RefCell<Value>, RefCell<Value>)
}

となった(car/cdrは素直にclone)。

冷静に考えたら、これくらいで充分という気がしますね

struct LocalEnv {
  values: Vec<Rc<RefCell<Vec<Value>>>>
}

letrec実装の都合上、いちばんナイーブなやつ(parent: Option<Rc<LocalEnv>>を持つ)がいちばん扱いやすいのでそのようにした。環境のネストがそこまで深くなることはないし、これでも大差なかろう(小賢しい工夫をした実装は面倒なのでパフォーマンスの比較が困難ですが……)

Lisp処理系高速化バトル会場があった。

https://github.com/kmtoki/secd-rs のmasterで (fib 30) が実測5.2sec、こちらの実装は2.8secなので一応勝ってる(言語仕様が違うのであまり比較に意味はないかもだが……)

(^^;

gosh> (time (fib 30))
;(time (fib 30))
; real   0.086
; user   0.090
; sys    0.000
832040

(^^;;;;

Chez Scheme Version 9.5.4
Copyright 1984-2020 Cisco Systems, Inc.

> (define (fib n) (if (= n 0) 0 (if (= n 1) 1 (+ (fib (- n 1)) (fib (- n 2))))))
> (time (fib 30))
(time (fib 30))
    no collections
    0.011206316s elapsed cpu time
    0.011336000s elapsed real time
    0 bytes allocated
832040

関数呼び出し時は

fn eval(ast, global_env, local_env) -> Result { .. }

fn eval_app(f, args, global_env) -> Result {
  let new_env = f.env.extend(args);
  eval(f.body, global_env, new_env)
}

というのが正攻法だが、関数呼び出しのたびに環境をコピーするのが嫌ですよね。というわけで

fn eval(ast, global_env, local_env, arg_env) -> Result { .. }

fn eval_app(f, args, global_env) -> Result {
  eval(f.body, global_env, f.env, args)
}

と、明示的に「現在の引数」を持ち回るようにした。lambdaが出現しなければ新しい環境を作る必要は無い。
変数を参照する場所によってアクセス方法を変えなければいけないので、AST構築時に名前解決して、GetLocal, GetArg, GetGlobalに振り分けている。

効果の程は不明……

という小賢しいことをやってたらletrecの環境作るときargsのことを忘れててわかりにくいバグが発生した

現在の処理系はソース -[parse]-> S式 -[built_ast]-> AST -[eval]-> 出力 というアーキテクチャになっているんですが、AST構築時にエラーが起きた段階で終了すると、テストをセルフホスティングするときに困る。

(assert-error
  (lambda () undefined-var)
  '(VariableNotFound undefined-var))

みたいなことをしたいが、assert-errorの評価前にエラーになってしまうとエラーがテストできないんですね。
というわけで、ASTにエラーを返す命令Error(EvalError)を用意して、コンパイル時のエラーをASTに埋め込む必要がある。テスト時にしか役立たない機能なので、評価器のオプションとしてeager errorモードを持たせるべきかもしれない。

モジュールシステム。

(module m1
  (define x 123)
  (module m2
    ; ここで m1:xは見えるべきか?
    ; lambdaからの類推では見えそうだが、しかし見えることによるメリットはないのでは?
    ; たとえばScalaにおいてネストしたobjectでは外側が見える、しかしパッケージだと外は見えない
    ; 両方名前空間を階層化する目的で使っているのになぜそれでいいのか、シンタクスの違い?
    ; defから外のobjectが見えた方が嬉しいということはあるが、
    ; ネストしたobjectから外が見えて嬉しいことはなかった気がする……
))


(import-from some-module x)
x ; some-module:x が参照される

(module m1
  ; importはここでも有効
  x ; some-module:x
  ; defineはパス指定をサポートしない。現在のモジュールを操作対象とする
  (define x 123)
  ; 名前の探索順は、現在のモジュール > import
  x ; :m1:x
)

(module m1
  (define foo ...))

; どこか別の場所
(import-from another-module foo)
(module m1
  ; 名前の探索順から、m1:fooが呼ばれる
  (foo))

非直感的だなあ……

(import-from another-module bar)
(module m1
  (define bar ...)
  ; しかし、ここではimportよりモジュール定義を優先してm1:barが呼ばれてほしい感じがする
  (bar)
)

(import-from another-module buz)
(module m1
  (define buz ...))
; ...しばらく後
(module m1
  ; これはどうなってほしいか
  (buz))

Gaucheの場合: https://practical-scheme.net/gauche/man/gauche-refj/moziyuru.html

グローバル変数の束縛の解決は次の手順で行われます。まずカレントモジュールが探されます。次に、importしているモジュールが importされた逆の順番に並べられ、それぞれについてそのモジュールおよびそのモジュールの先祖(継承されているモジュール)が順に探されます。 importは遷移的ではありません；importされたモジュールがimportしているモジュール… というふうに再帰的に辿ることはしません。最後に、カレントモジュールの先祖が順に探されます。

モジュール自身を値として扱えると、REPLからメンバの一覧を見ることができたりして便利かもしれない。循環参照の問題は発生しないし、とりあえず入れてみるか。
動的にメンバを追加するのは、名前解決時の問題が発生するためなしで。

(module m1
  (define name 'm1))

m1 ;=> #<module:m1>
(module-members m1) ;=> (name)
(module-get-member m1 'name) ;=> m1
(module-set-member m1 'name 'm1???)

モジュールを値として扱えるようにした場合、こういうケースどうしよう……

(module m1)
(define m1 123)

gaucheだとm1は変数を指し、モジュールへのアクセスは(find-module name)経由でやるようになってるのでそうしよう

トップレベルでの名前評価が、モジュール名と変数名で挙動に一貫性がないという微妙なことになっており、どうにかしたい。

x ; :global:x
(module m1 ) ; module :m1
(m1:x) ; :m1:x

(module global ; module :global
  (module m1) ; module :global:m1
)

でもトップレベルでxと書いたらトップレベルに対応するモジュールのxを参照したいし、(module m1)と書いたらモジュール:m1になってほしいですねえ。……それではm1:xの場合は?

Rubyの場合はObject include Kernelで、トップレベルの名前解決はObjectの内部と同等、defはKernelのインスタンスメソッドとなり、moduleはObjectの子になるという挙動に見える。

btw, 複数のファイルを評価することを考えると、単一のトップレベルが存在して特定のモジュールに属しているという仕様が微妙なので、ファイル単位のトップレベルに対応する匿名モジュールがあるとよさそうである。

こういうのは決めの問題なのでてきとうに決めてしまいましょう。

; foo.lisp

; トップレベルで定義された名前は、そのファイルに対応するモジュール(以下、トップレベルモジュール)のメンバになる
; :<123>:x
(define x 1)

; トップレベルで参照される単純名は、
; 1. トップレベルモジュール
; 2. import
; の順に探索される
x ; :<123>:x

; 絶対名はそのままの意味で解決すればよし
:foo:bar

; トップレベルで参照される相対名は、
; 先頭のモジュール名を以下の順で探索し、解決結果を起点に残りのパスを解決する。
; 1. ルート
; 1. import
std:list ; :std:list

; トップレベルで定義されたモジュールは、ルート直下のモジュールになる
(module m1 ; module :m1
  ; モジュール内で定義された名前は、そのモジュールのメンバになる
  (define x 2) ; :m1:x
  ; モジュール内で定義されたモジュールは、親モジュールのメンバになる
  (module m2
    ; モジュール内で参照される単純名は、
    ; 1. そのモジュール
    ; 2. import
    ; 3. 親モジュール
    ; 4. 親の親モジュール...
    ; 5. トップレベルモジュール
    ; の順に探索される
    x ; :m1:x

    ; モジュール内で参照される相対名は、先頭のモジュール名を以下の順で探索し、
    ; 解決結果を起点に残りのパスを解決する
    ; 1. そのモジュール
    ; 2. import
  )

  ; モジュールが絶対名で指定されていたらそれに従う
  (module :foo:bar)
)

; bar.lisp

; foo.lispのトップレベルとは別のモジュールが使われる
x ; not found

define/defmacroはトップレベル以外では禁止しているが、マクロからの使い勝手を考えてトップレベルbeginの内部もトップレベル扱いとしている。すなわち、(if foo? (define x 123) ())のような式は違法だが、(begin (define x 123) x)は合法。

複数のトップレベル式 $e_1, e_2, \cdots, e_n$ を評価する際は、

大域環境 $G_0$ を元に静的環境 $S_0$ を構築
$S_0$ の元で $e_1$ をコンパイル
$G_0$ の元で $e_1$ を評価し、更新された大域環境 $G_1$ を得る
……
$G_{n-1}$ を元に $S_{n-1}$ を構築
$S_{n-1}$ の元で $e_n$ をコンパイル
$G_{n-1}$ の元で $e_1$ を評価し、 $G_n$ を得る

とすればよい。

ところが、式が $({\rm begin}\ e_1 \cdots e_n)$ の形式の場合、

大域環境 $G_0$ を元に静的環境 $S_0$ を構築
$S_0$ の元で $e_1$ をコンパイルし、更新された静的環境 $S_1$ を得る
……
$S_{n-1}$ の元で $e_n$ をコンパイルし、 $S_n$ を得る
$G_0$ の元で $e_1$ を評価し、 $G_1$ を得る
……
$G_{n-1}$ の元で $e_n$ を評価し、 $G_n$ を得る

という手順を踏むことになる。
本質的に同じ処理であるにも関わらず、コンパイルのタイミングにより実装を使い分ける必要があり、二種類の評価において一貫性を保つのが困難である、というか実際バグった。

選択肢としては、

頑張って正しい処理を書く(早期にエラー発見できるメリットはある)
$e1$ の評価終了まで $e2$ の評価を遅延させる

後者の場合、トップレベルbeginのコンパイル結果としてTopAst::Begin(Vec<Value>) を返し、eval時には内部の要素ごとにコンパイル+実行を繰り返せばよい。あまりかっこよくはない……

設計変えて名前環境を分離できれば前者でもどうにかなりそう。な気がする。

(begin
  (define (f x) ...)
  (defmacro (g x) (f x))
  (g 123))

みたいなのを考えると先行の式が評価されるまで後続式をコンパイルできないのは自明！！！！！

enum TopAst {
  // ...
  Begin(Box<TopAst>, rest: Vec<Value>)
}

fn eval(...) {
  TopAst::Begin(e, rest) => {
    eval(e)?;
    let mut ret = Value::Nil;
    for next in rest {
      ret = eval(compile(next)?)?;
    }
    ret
}

RefCellよりarena使った方が安全性が高まるので良いという話があり、検討しています

enum Value {
  Cons(ValueRef, ValueRef),
}

struct ValueRef(&Arena, usize);
impl Drop for ValueRef {
  fn drop(self) {
    self.0.dec_ref(usize);
  }
}
impl Clone for ValueRef {
  fn clone(&self) -> ValueRef {
    self.0.inc_ref(self.1);
    ValueRef(self.0, self.1)
  }
}

struct Arena { values: Vec<(usize, Value)>, free: Vec<usize> };

みたいな?

ValueRefが&Arena持つの無駄なので、何かトリックを考えたいところですが……