Rustマクロで実装されたLisp

 (github.com/RyanWelly)
1 ポイント 投稿者 GN⁺ 2024-09-15 | 1件のコメント | WhatsAppで共有
  • lisp-in-rs-macrosは、Rustの宣言的マクロだけで動作するシンプルなレキシカルスコープのLispインタープリタであり、lisp!マクロがコードをコンパイル時に評価して、文字列化されたLisp値を生成する
  • lisp!(CAR (CONS (QUOTE A) (QUOTE (B))))はrustcのマクロ展開過程で計算され、文字列"A"へ展開される。実装全体は250行未満
  • 例ではCAR、LIST、QUOTE、PROGN、DEFINE、LAMBDA、DISPLAYを使用しており、quineの例はLispコードがそれ自身へ評価される形を示す
  • 明示的な再帰は現在サポートしていないが、self applicationによってリストのappendのような再帰的動作を書ける。ただしDEFINE自体は再帰定義を処理しない
  • メタサーキュラーインタープリタの例は動作するように見えるが、((lambda (X) X) (quote a))の評価に30秒以上かかり、100万個以上のトークンを生成してcargoがsigkillされるほど非効率

Rustマクロ内で実行されるLisp

  • lisp-in-rs-macrosは、Rustの宣言的マクロだけで書かれたレキシカルスコープのLispインタープリタ
  • lisp!マクロは渡されたLispコードを評価したあと、計算されたLisp値を文字列化する
  • たとえばlisp!(CAR (CONS (QUOTE A) (QUOTE (B))))は文字列"A"へ展開される
  • この計算はランタイムではなく、rustcがマクロを展開するコンパイル時に行われる
  • 実装は250行未満

基本的な使用例

  • CAR、LIST、QUOTEを組み合わせて、リストの最初の要素を取得できる
let output = lisp!(CAR (LIST (QUOTE A) (QUOTE B) (QUOTE C)));
assert_eq!(output, "A");
  • 複数の式を評価するにはPROGNを使う
    • PROGNはすべての式を評価し、最後の式の値を返す
  • DISPLAYは引数を先に評価したあと、println!("{}", stringify!(evaled_argument))の形へ展開し、トークンを文字列化して出力する
lisp!(PROGN
    (DEFINE message (LAMBDA () (QUOTE "hello there")))
    (DISPLAY (message))
    (DEFINE NOT (LAMBDA (X) (COND (X NIL) (TRUE TRUE))) )
    (DISPLAY (NOT NIL))
);
  • 上の例は"hello there"と"TRUE"を出力する

自分自身へ評価されるquine

  • quineの例は、Lispコードが自分自身へ評価される形を示す
lisp!
       ((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
       (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))));
  • このコードは次のようなstringify!呼び出しへ展開される
stringify!(((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
       (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s))))));

再帰とself application

  • このLispは現在、明示的な再帰をサポートしていない
  • 明示的な再帰がなくても、lambdaだけで再帰的な動作を作れる
  • 例のappend関数は本文中でappendという名前に直接言及せず、self引数を通じて自己適用による再帰呼び出しを行う
lisp!(PROGN
(DEFINE append
    (LAMBDA (self X Y)
        (COND
            ((EQ X NIL) Y)
            (TRUE (CONS (CAR X) (self self (CDR X) Y)))
        )))
(append append (QUOTE (A B)) (QUOTE (C D)))

)
  • このコードは結果として"(A B C D)"を生成する

利用上の制約

  • lisp!マクロは単一の式だけを評価する
    • 複数の式は(PROGN expr1 expr2 expr3)でまとめる必要がある
  • 空リストはself-evaluatingではない
    • 空リスト値はNILまたは(QUOTE ())で得られる
    • 空リストは唯一のfalsyなオブジェクト
  • dotted listはサポートしない
    • CONSは最後の引数がリストだと仮定する
  • DEFINEはどこでも使え、空リストへ評価されるが、再帰はサポートしない
  • TRUEは関数ではないatomのうち唯一self-evaluatingなもの

サポートするform

DEFINE
QUOTE
LAMBDA
LET
PROGN
CAR
CDR
CONS
LIST
EQ
ATOM
APPLY
  • DEFINEは本物のLisp風の再帰定義というより、Schemeの内部定義に近い形

Lispで書かれたLispインタープリタ

  • リポジトリには、このLisp上で書かれたメタサーキュラーインタープリタの例が含まれる
  • 例では2引数用のY2コンビネータ、CADR、CAAR、ASSOC、evalなどを定義する
  • インタープリタは動作するように見えるが、((lambda (X) X) (quote a))を評価しようとすると30秒以上かかる
  • この評価は100万個を超えるトークンを生成し、最終的にcargoがsigkillされるほど大きくなる
  • 明示的なYコンビネータを使った再帰は、ここでは特に非効率
  • これを直すには、明示的な再帰primitiveを追加する必要があると書かれている
  • メタサーキュラー評価器作成のwalkthroughとして、Paul Grahamの"Roots of Lisp"を薦めている

実装方式と参考資料

  • 技術的な説明はEXPLANATION.mdにある
  • マクロは本質的にSECD machineをシミュレートする
    • SECD machineはlambda calculus termを評価するシンプルなスタックベースの抽象機械

参考資料

  • Peter Henderson著 Functional Programming: Application and Implementation
  • Ager, Mads Sig, et al. "A functional correspondence between evaluators and abstract machines."
  • Simon Peyton Jones著 The Implementation of Functional Programming Languages
  • Matt MightのLisp関連ブログ記事: https://matt.might.net

TODO

  • letrecの追加
  • 再帰的なdefineの追加

関連記事

1件のコメント

 
GN⁺ 2024-09-15
Hacker Newsのコメント

  • Greenspunの第十法則がまた出てきた: https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule

    • これは主目的がLisp実装ではないコードベースについての話なので、ここにはあまりぴったり当てはまらない気がする
    • この法則の良い例は、C++がテンプレート言語の中で car/cdr を氷河のように遅い速度で再発見していることだ
      C++26になってようやく Args...[0] で型名パラメータパックの car を取得できるようになった
      なぜ空のパラメータパック用の nil と car/cdr 関数を導入して、今みたいな文法の混沌の代わりにパラメータパックを保存できるようにしないのか分からない
    • 「十分に複雑なCやFortranプログラムは、Common Lispの半分をその場しのぎで、非公式仕様として、バグだらけで遅く実装したものを含む」という一文をそのまま思い出す
    • 「十分に複雑な」が何を意味するのか分からないし、定義としていまひとつだ

  • 昔これに似たことをやったことがあるが、ハイフン入りシンボルを定義できない問題があった
    DEFINE MY-FN... みたいなのができなかった。Rustがハイフンでトークンを分割するからだ
    小さな違いではあるが、実際のLispコード片をそのまま貼り付けられず、全部アンダースコアに置き換えなければならなかった。この実装も同じなのか気になる

    • 今はすべてのアトムがRust識別子だと仮定している。実装が簡単になって $x:ident でマッチできるからで、なのでアトム内のハイフンはサポートしていない
      代わりに $x:ident $(- $y:ident)* みたいな形でマッチすればよさそうだ。いくつかのマクロ分岐の細部は変える必要があるだろうが、できそうではある
    • 問題なさそうだけど? DEFINE MYᜭFN... はちゃんと動く

  • マクロだけでなく、Rustベースでしっかりサポートされた Lisp実装 があるといいのに
    Rustの上に作った場合、メモリ安全性をどの程度維持できるのか、あるいは失うのか気になる。借用チェッカーを正気の方法で活用することは本当に可能なんだろうか?

    • SBCLのような一部のLispコンパイラでは、もっと広範な コンパイル時型検査 も可能だが、その情報はプログラマが与える必要があり、普通は日常的な漸進的開発というより最適化段階の一部に近い
      Lispは通常動的な性格で定義され、実行時型検査が大きな部分を占める。オブジェクト管理の仕方を事前にプログラマに意識させるようにすると、その種のシステムに期待される自由度や表現力と衝突する
      その代わりコンパイラ自体は比較的単純にできる。追加宣言のない一般的なコードは基本的に安全で、CLISPのようなバイトコードVMや、ハードウェア型検査を行うLispマシンでは、そのような宣言を無視しても常に安全であり得る
      SBCLはかなり速くコードをコンパイルするし、他の実装はもっと速いとも聞く。一方でRustコンパイラは、若いプログラマにスラッシングという概念を紹介する可能性のほうが高い
      この二つは、最初に見えるほどには両立しやすい世界ではないと思う。Lispは本質的に「The Right Thing」哲学の代表的な言語で、Cは「Worse is Better」の言語だ。Rustはそのどちらでもなく、両方の哲学の悪い特性を反映した新しい名前が必要なくらい、まったく別の何かに思える
      とはいえ元記事をけなしたいわけではなく、依然としてクールなハックだ
    • Steelは良さそう: https://github.com/mattwparas/steel
      他のLispもある(https://github.com/alilleybrinker/langs-in-rust)。ただ、あまり活発には保守されていないようだ

  • 作っていて楽しかったし、rust-analyser が数百万個のトークンを生成するマクロを処理できないことも学んだ

  • みんな「面白い」と歓声を上げるべき雰囲気だけど、こういうものを見るたびにRustで実装できてしまう事実が嫌になる
    Rustはもともと単純な言語ではなかったが、最初のころよりずっと扱いづらい形になった気がする

    • Rustが単純な言語ではないことには同意する
      ただ、これが可能だという事実をなぜ嫌がるのかはよく分からない。マクロシステムがほぼ無限に複雑なコードを生成できるのは確かだが、マクロでサンドボックス化されたLispを実装できることが、Rustが初期より管理しにくくなった強い例なのかは分からない
      一方で、Rustの型システムがC++テンプレートやHaskellの型システムのようにチューリング完全であることを踏まえると、そのやり方で実装したLispも見てみたくなる
    • その点には強く反対する。Rustチームは制約を取り除き、機能をより直交的にして、言語を使いやすくし続けている
      代表例は 非字句的ライフタイム、戻り値位置の impl Trait、非同期トレイトだ。1.0以前には特殊構文付きのGC参照も組み込まれていたが、そうした機能は削除もされている
    • 1.0以降の実質的な大きな変化は async だけだ。asyncなしで生きたいなら完全に選択可能で、言語の完全に任意な部分だ
      単純さを原則とする言語が欲しいなら、Rustはもともとそういう言語ではないし、他の選択肢はいくらでもある
    • こういうことが可能になるのに、実際にはごくわずかなものしか要らない。単純だと見なされるCマクロでもできそうだ
      確認してみたが、この賭けは私の勝ちだ: https://github.com/kchanqvq/CSP
    • マクロは常に非常に強力である一方で、同時に厄介なものでもあるのでは? マクロまわりを言語の複雑さには含めないだろう
      特にマクロを「書く」側について言えば、使っても使わなくてもいい追加機能に近いと見ている

  • うわ、これ macro_rules を使ってるのか

  • でもC++は、テンプレートがチューリング完全だから正気の言語じゃないって話じゃなかったっけ?

    • C++は少し知っただけでも正気の言語じゃない。少なくともRustマクロは文字どおりのテキスト置換ではないのだから、光に向けた一歩ではある
    • チューリング完全 とチューリング・タールピットは別物だ
      Rustマクロシステムがどちらなのかは分からない
    • C++テンプレートで開発するのは地獄だ。Rustには少なくとも macro_expand があるし、Rustのツール群がよくできているのは大きい

  • Carp も外せない。借用チェッカーを使うLispで、Lisp界の「Rust」のような存在だ
    1: https://github.com/carp-lang/Carp