Open

RustでLisp

31

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

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

図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>を使い分けるみたいなことはあまりしたくない……

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>>>>
}

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

https://qiita.com/kmtoki/items/cc5bb1204fcba166fd6f

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))
ログインするとコメントできます