Rustマクロで実装されたLisp

 (github.com/RyanWelly)
1 ポイント 投稿者 GN⁺ 2024-09-15 | まだコメントはありません。 | WhatsAppで共有

lisp-in-rs-macros

Rustの宣言的マクロで完全に動作する、シンプルなレキシカルスコープのLispインタプリタ。lisp! マクロはコードによって計算されたLisp値を展開し、文字列に変換する。たとえば lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) は文字列 "A" に展開され、すべての計算は rustc がマクロを展開するコンパイル時に行われる。

なぜ重要か

Rustのマクロで書かれたLispインタプリタという点が非常に興味深い。さらに、250行未満で書かれており簡潔。

例

let output = lisp!(CAR (LIST (QUOTE A) (QUOTE B) (QUOTE C)));
assert_eq!(output, "A");

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"を出力

もう1つの面白い例として quine がある:

lisp!((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s))) (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))));

このコードは自分自身を評価する。

再帰

このLispは現在、明示的な形式の再帰をサポートしていない。幸い、明示的な再帰は必須ではなく、ラムダだけで十分。2つのリストを連結するシンプルな関数は次のように書ける:

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)" となる。append 関数は本体内で append に言及していないが、再帰的に呼び出すことができる。

使用時の注意点

  • lisp! マクロは単一の式だけを評価する。複数の式を評価するには (PROGN expr1 expr2 expr3) を使う必要がある。
  • DISPLAY 形式は単一の式を評価したあとに println!("{}", stringify!(...)) 文を生成し、トークンの文字列表現を出力する。
  • 空リストは自己評価されないため、空リスト値を得るには NIL または (QUOTE ()) を使う必要がある。
  • ドットリストはサポートされておらず、cons は最後の引数がリストであることを前提とする。
  • define 形式はどこでも使え、空リストに評価されるが、再帰はサポートしない。
  • TRUE は関数ではない唯一の自己評価アトムである。

サポートされている形式

  • DEFINE
  • QUOTE
  • LAMBDA
  • LET
  • PROGN
  • CAR
  • CDR
  • CONS
  • LIST
  • EQ
  • ATOM
  • APPLY

メタ循環インタプリタ

以下は Lisp で書かれた Lisp インタプリタ:

lisp!(PROGN
  (DEFINE Y2
    (LAMBDA (h)
      ((LAMBDA (x) (h (LAMBDA (a b) ((x x) a b))))
        (LAMBDA (x) (h (LAMBDA (a b) ((x x) a b)))))))
  (DEFINE CADR (LAMBDA (X) (CAR (CDR X))))
  (DEFINE CAAR (LAMBDA (X) (CAR (CAR X))))
  (DEFINE CADAR (LAMBDA (X) (CAR (CDR (CAR X)))))
  (DEFINE CADDR (LAMBDA (X) (CAR (CDR (CDR X)))))
  (DEFINE CADDAR (LAMBDA (X) (CAR (CDR (CDR (CAR X))))))
  (DEFINE CAADAR (LAMBDA (X) (CAR (CAR (CDR (CAR X))))))
  (DEFINE ASSOC (Y2 (LAMBDA (ASSOC) (LAMBDA (X ENV)
    (IF (EQ (CAAR ENV) X) (CADAR ENV) (ASSOC X (CDR ENV))))))
  )
  (DEFINE eval (Y2 (LAMBDA (EVAL) (LAMBDA (E A)
    (COND
      ((ATOM E) (ASSOC E A))
      ((ATOM (CAR E))
        (COND
          ((EQ (CAR E) (QUOTE quote)) (CADR E))
          ((EQ (CAR E) (QUOTE atom)) (ATOM (EVAL (CADR E) A)))
          ((EQ (CAR E) (QUOTE car)) (CAR (EVAL (CADR E) A)))
          ((EQ (CAR E) (QUOTE cdr)) (CDR (EVAL (CADR E) A)))
          ((EQ (CAR E) (QUOTE equal)) (EQ (EVAL (CADR E) A) (EVAL (CADDR E) A)))
          ((EQ (CAR E) (QUOTE cons)) (CONS (EVAL (CADR E) A) (EVAL (CADDR E) A)))
          (TRUE (EVAL (CONS (ASSOC (CAR E) A) (CDR E)) A))
        ))
      ((EQ (CAAR E) (QUOTE lambda)) (EVAL (CADDAR E) (CONS (LIST (CAADAR E) (EVAL (CADR E) A)) A)))
    ))))
  )
  (eval (QUOTE (quote (A))) NIL)
  (eval (QUOTE ((lambda (X) X) (quote a))) NIL)
);

このコードは動作するが、インタプリタ内で ((lambda (X) X) (quote a)) を評価しようとすると 30 秒以上かかり、100万個以上のトークンを生成する。明示的な y combinator を使った再帰はここでは効率的ではない。これを解決するには、明示的な再帰プリミティブを追加する必要がある。メタ循環評価器の書き方についての優れた説明は Paul Graham の "Roots of Lisp" を参照。

技術的説明

EXPLANATION.md を参照。マクロは SECD マシンをシミュレートしており、これはラムダ計算式を評価するためのシンプルなスタックベースの抽象マシン。

優れた資料

  • Peter Henderson の "Functional Programming: Application and Implementation"
  • Mads Sig Ager らの "A functional correspondence between evaluators and abstract machines." (2003)
  • Simon Peyton Jones の "The Implementation of Functional Programming Languages"
  • Matt Might のブログ (https://matt.might.net) にある Lisp 関連のすべての記事

TODO

  • letrec の追加
  • 再帰的定義の追加

GN⁺の要約

  • Rustマクロで書かれたLispインタプリタは非常に興味深く、簡潔なコードで強力な機能を提供する。
  • 再帰を明示的にはサポートしていないが、ラムダを通じて再帰を実装できる。
  • メタ循環インタプリタは効率的ではないため、明示的な再帰プリミティブの追加が必要。
  • Paul Graham の "Roots of Lisp" はメタ循環評価器を理解するのに優れた資料。
  • 類似の機能を提供する別のプロジェクトとして、Scheme インタプリタや他の Lisp 方言が推奨される。

関連記事

まだコメントはありません。

まだコメントはありません。