Rust makrolarıyla uygulanmış Lisp

lisp-in-rs-macros

Rust'ın bildirime dayalı makrolarıyla tamamen çalışan, basit bir leksik kapsamlı Lisp yorumlayıcısı. lisp! makrosu, kod tarafından hesaplanan Lisp değerlerini genişletir ve bunları dizgeye dönüştürür. Örneğin, lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) ifadesi "A" dizgesine genişler ve tüm hesaplama, rustc makroları genişletirken derleme zamanında gerçekleşir.

Neden önemli

Rust makrolarıyla yazılmış bir Lisp yorumlayıcısı olması onu oldukça ilginç kılıyor. Ayrıca 250 satırdan kısa olması da onu son derece özlü yapıyor.

Örnek

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" ve "TRUE" çıktısını verir

Bir başka eğlenceli örnek de quine:

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

Bu kod kendisini değerlendirir.

Özyineleme

Bu Lisp şu anda açık bir özyineleme biçimini desteklemiyor. Neyse ki açık özyineleme gerekli değil; yalnızca lambda yeterli. İki listeyi birleştiren basit bir fonksiyon şöyle yazılabilir:

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)))
);

Bunun sonucu "(A B C D)" olur. append fonksiyonu gövdesinde append adını anmasa da kendisini özyinelemeli olarak çağırabilir.

Kullanırken dikkat edilmesi gerekenler

• lisp! makrosu yalnızca tek bir ifadeyi değerlendirir. Birden fazla ifadeyi değerlendirmek için (PROGN expr1 expr2 expr3) kullanılmalıdır.
• DISPLAY biçimi, tek bir ifadeyi değerlendirdikten sonra println!("{}", stringify!(...)) ifadesi üreterek token'ların dizgesel sürümünü yazdırır.
• Boş liste kendisini değerlendirmez; boş liste değerini elde etmek için NIL veya (QUOTE ()) kullanılmalıdır.
• Noktalı listeler desteklenmez ve cons, son argümanın bir liste olduğunu varsayar.
• define biçimi her yerde kullanılabilir ve boş listeye değerlendirilir, ancak özyinelemeyi desteklemez.
• TRUE, fonksiyon olmayan tek kendini değerlendiren atomdur.

Desteklenen biçimler

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

Meta-döngüsel yorumlayıcı

Aşağıda Lisp ile yazılmış bir Lisp yorumlayıcısı yer alıyor:

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)
);

Bu kod çalışıyor, ancak yorumlayıcı içinde ((lambda (X) X) (quote a)) ifadesini değerlendirmeye çalıştığınızda 30 saniyeden uzun sürüyor ve bir milyondan fazla token üretiyor. Açık y combinator kullanan özyineleme burada verimli değil. Bunu çözmek için açık bir özyineleme ilkelinin eklenmesi gerekiyor. Meta-döngüsel değerlendiricinin nasıl yazılacağına dair harika bir açıklama için Paul Graham'ın "Roots of Lisp" yazısına bakabilirsiniz.

Teknik açıklama

EXPLANATION.md dosyasına bakın. Makro, lambda ifadelerini değerlendirmek için kullanılan basit bir yığın tabanlı soyut makine olan SECD makinesini simüle eder.

Harika kaynaklar

• Peter Henderson, "Functional Programming: Application and Implementation"
• Mads Sig Ager ve diğerleri, "A functional correspondence between evaluators and abstract machines." (2003)
• Simon Peyton Jones, "The Implementation of Functional Programming Languages"
• Matt Might'ın blogunda (https://matt.might.net) Lisp hakkındaki tüm yazılar

TODO

• letrec ekle
• özyinelemeli tanımlar ekle

GN⁺ özeti

• Rust makrolarıyla yazılmış bu Lisp yorumlayıcısı, özlü bir kod tabanıyla güçlü yetenekler sunduğu için oldukça ilgi çekici.
• Açık özyinelemeyi desteklemese de lambda üzerinden özyineleme kurulabiliyor.
• Meta-döngüsel yorumlayıcı verimli değil; bu yüzden açık bir özyineleme ilkelinin eklenmesi gerekiyor.
• Paul Graham'ın "Roots of Lisp" yazısı, meta-döngüsel değerlendiriciyi anlamak için çok iyi bir kaynak.
• Benzer işler yapan başka projeler arasında Scheme yorumlayıcıları veya diğer Lisp türevleri önerilebilir.