Rust makrolarıyla yazılmış Lisp

 (github.com/RyanWelly)
1 puan yazan GN⁺ 2024-09-15 | 1 yorum | WhatsApp'ta paylaş
  • lisp-in-rs-macros, yalnızca Rust'ın deklaratif makroları ile çalışan basit bir leksik kapsamlı Lisp yorumlayıcısıdır ve lisp! makrosu kodu derleme zamanında değerlendirerek stringleştirilmiş bir Lisp değeri üretir
  • lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))), rustc'nin makro genişletme sürecinde hesaplanır ve "A" dizgesine genişler; tüm uygulama 250 satırdan azdır
  • Örnekler CAR, LIST, QUOTE, PROGN, DEFINE, LAMBDA, DISPLAY kullanır; quine örneği ise Lisp kodunun kendisine değerlendiği bir yapıyı gösterir
  • Açık özyineleme şu anda desteklenmiyor, ancak self application ile liste birleştirme gibi özyinelemeli davranışlar yazılabiliyor; buna karşın DEFINE kendi başına özyinelemeli tanımları işlemiyor
  • Meta-circular yorumlayıcı örneği çalışıyor gibi görünüyor, ancak ((lambda (X) X) (quote a)) değerlendirmesi 30 saniyeden uzun sürüyor ve bir milyondan fazla token üreterek cargo'nun sigkill almasına yol açacak kadar verimsiz kalıyor

Rust makrolarının içinde çalışan Lisp

  • lisp-in-rs-macros, yalnızca Rust'ın deklaratif makroları ile yazılmış, leksik kapsamlı bir Lisp yorumlayıcısıdır
  • lisp! makrosu, kendisine verilen Lisp kodunu değerlendirir ve ardından hesaplanan Lisp değerini stringleştirir
  • Örneğin lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))), "A" dizgesine genişler
  • Bu hesaplama çalışma zamanında değil, rustc'nin makroları genişlettiği derleme zamanında gerçekleşir
  • Uygulama 250 satırdan azdır

Temel kullanım örneği

  • CAR, LIST, QUOTE birleştirilerek bir listenin ilk öğesi alınabilir
let output = lisp!(CAR (LIST (QUOTE A) (QUOTE B) (QUOTE C)));
assert_eq!(output, "A");
  • Birden fazla ifadeyi değerlendirmek için PROGN kullanılır
    • PROGN, tüm ifadeleri değerlendirir ve son ifadenin değerini döndürür
  • DISPLAY, önce argümanını değerlendirir, ardından println!("{}", stringify!(evaled_argument)) biçiminde genişleyerek token'ları stringleştirip yazdırır
lisp!(PROGN
    (DEFINE message (LAMBDA () (QUOTE "hello there")))
    (DISPLAY (message))
    (DEFINE NOT (LAMBDA (X) (COND (X NIL) (TRUE TRUE))) )
    (DISPLAY (NOT NIL))
);
  • Yukarıdaki örnek "hello there" ve "TRUE" çıktısını üretir

Kendisine değerlendirilen quine

  • Quine örneği, Lisp kodunun kendisine değerlendiği bir yapıyı gösterir
lisp!
       ((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
       (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))));
  • Bu kod, aşağıdaki stringify! çağrısına genişler
stringify!(((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
       (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s))))));

Özyineleme ve self application

  • Bu Lisp şu anda açık özyinelemeyi desteklemiyor
  • Açık özyineleme olmadan da yalnızca lambda ile özyinelemeli davranış üretilebiliyor
  • Örnekteki append fonksiyonu, gövdesinde doğrudan append adını anmadan, self argümanı üzerinden kendini uygulayarak özyinelemeli çağrı yapıyor
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)))

)
  • Bu kod "(A B C D)" sonucunu üretir

Kullanım kısıtları

  • lisp! makrosu yalnızca tek bir ifadeyi değerlendirir
    • Birden fazla ifade (PROGN expr1 expr2 expr3) ile gruplanmalıdır
  • Boş liste self-evaluating değildir
    • Boş liste değeri NIL veya (QUOTE ()) ile elde edilebilir
    • Boş liste, tek falsy nesnedir
  • Dotted list desteklenmez
    • CONS, son argümanın bir liste olduğunu varsayar
  • DEFINE her yerde kullanılabilir ve boş listeye değerlendirilir, ancak özyineleme desteklemez
  • TRUE, fonksiyon olmayan atomlar arasında self-evaluating olan tek atomdur

Desteklenen formlar

DEFINE
QUOTE
LAMBDA
LET
PROGN
CAR
CDR
CONS
LIST
EQ
ATOM
APPLY
  • DEFINE, gerçek Lisp tarzı özyinelemeli tanımdan ziyade Scheme'deki iç tanımlara daha yakındır

Lisp ile yazılmış Lisp yorumlayıcısı

  • Depoda, bu Lisp üzerinde yazılmış bir meta-circular yorumlayıcı örneği bulunuyor
  • Örnek; iki argümanlı Y2 kombinatörü, CADR, CAAR, ASSOC, eval gibi tanımlar içeriyor
  • Yorumlayıcı çalışıyor gibi görünse de, ((lambda (X) X) (quote a)) ifadesini değerlendirmeye çalıştığında 30 saniyeden uzun sürüyor
  • Bu değerlendirme bir milyondan fazla token üretiyor ve sonunda cargo, sigkill alacak kadar büyüyor
  • Açık Y kombinatoryle yapılan özyineleme burada özellikle verimsiz
  • Bunu düzeltmek için açık bir özyineleme primitive'i eklenmesi gerektiği belirtiliyor
  • Meta-circular değerlendirici yazımına dair walkthrough olarak Paul Graham'ın "Roots of Lisp" yazısı öneriliyor

Uygulama biçimi ve referanslar

  • Teknik açıklama EXPLANATION.md içinde yer alıyor
  • Makrolar özünde bir SECD machine simüle ediyor
    • SECD machine, lambda calculus terimlerini değerlendiren basit, yığın tabanlı bir soyut makinedir

Referanslar

  • Functional Programming: Application and Implementation by Peter Henderson
  • Ager, Mads Sig, et al. "A functional correspondence between evaluators and abstract machines."
  • The Implementation of Functional Programming Languages by Simon Peyton Jones
  • Matt Might'ın Lisp ile ilgili blog yazıları: https://matt.might.net

TODO

  • letrec ekleme
  • özyinelemeli define ekleme

İlgili okumalar

1 yorum

 
GN⁺ 2024-09-15
Hacker News yorumları

  • Greenspun'un onuncu kuralı yine karşımıza çıkmış: https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule

    • Bu daha çok asıl amacı Lisp uygulaması olmayan kod tabanlarıyla ilgili bir söz, o yüzden buraya tam oturmuyor gibi görünüyor
    • Bunun iyi bir örneği, C++'ın şablon dili içinde car/cdr'yi buzul kadar yavaş bir hızla yeniden keşfetmesi
      Ancak C++26 ile Args...[0] kullanarak tür isimli parametre paketinin car'ını alabiliyoruz
      Neden boş parametre paketleri için nil ve car/cdr işlevleri ekleyip, şu anki sözdizimi keşmekeşi yerine parametre paketlerini saklanabilir hale getirmediklerini bilmiyorum
    • Aklıma tam şu cümle geliyor: “Yeterince karmaşık her C ya da Fortran programı, geçici çözümlerle, gayriresmî olarak belirtilmiş, hatalı ve yavaş bir Common Lisp'in yarısını içerir”
    • “Yeterince karmaşık” ifadesinin ne anlama geldiğini bilmiyorum, tanımı pek iyi değil

  • Eskiden benzer bir şey denemiştim ama içinde tire olan semboller tanımlanamıyordu
    DEFINE MY-FN... gibi bir şey çalışmıyordu, çünkü Rust tirede token'ları bölüyor
    Küçük bir fark gibi ama gerçek Lisp kod parçalarını doğrudan yapıştırmak mümkün olmuyor, hepsini alt çizgiye çevirmek gerekiyor. Bunun da aynı durumda olup olmadığını merak ediyorum

    • Şu anda tüm atomların Rust tanımlayıcısı olduğu varsayılıyor. Uygulaması daha kolay olduğu için $x:ident ile eşleştiriliyor ve bu yüzden atom içindeki tireler desteklenmiyor
      Ama bunun yerine $x:ident $(- $y:ident)* gibi bir şeyle eşleştirmek mümkün olabilir. Bazı makro dalı ayrıntılarını değiştirmek gerekir ama yapılabilir görünüyor
    • Sorun yok gibi? DEFINE MYᜭFN... gayet çalışıyor

  • Sadece makro değil, Rust tabanlı iyi desteklenen bir Lisp uygulaması olsa güzel olurdu
    Rust üzerinde yapılırsa bellek güvenliğinin ne kadarının korunacağı ya da kaybedileceği merak konusu. Ödünç alma denetleyicisini aklı başında bir şekilde kullanmak gerçekten mümkün olur mu?

    • SBCL gibi bazı Lisp derleyicileri daha kapsamlı derleme zamanı tür denetimi de yapabiliyor, ama bu bilgi programcı tarafından sağlanmalı ve genelde günlük artımlı geliştirmeden çok optimizasyon aşamasının bir parçası gibi duruyor
      Lisp genelde dinamik doğasıyla tanımlanır ve çalışma zamanı tür denetimi büyük yer tutar. Programcıyı nesne yönetim biçimiyle önceden ilgilenmeye zorlamak, böyle sistemlerde beklenen özgürlük ve ifade gücüyle çelişir
      Öte yandan derleyicinin kendisi nispeten daha basit olabilir. Ek bildirim olmadan yazılmış sıradan kod temelde güvenlidir ve CLISP gibi bir bytecode sanal makinesinde ya da donanım tür denetimi yapan Lisp makinelerinde bu tür bildirimler yok sayılsa bile her zaman güvenli olabilir
      SBCL kodu oldukça hızlı derliyor, başka uygulamaların daha da hızlı olduğu da söyleniyor. Buna karşılık Rust derleyicisi genç programcılara thrashing kavramını tanıtma ihtimali daha yüksek
      Bana kalırsa bunlar, ilk bakışta öyle görünmese de, birbirleriyle pek uyuşmayan dünyalar. Lisp özünde “The Right Thing” felsefesinin amiral gemisi dilidir, C ise “Worse is Better” dilidir. Rust ise ikisi de değil; her iki felsefenin de kötü yanlarını yansıtan, bambaşka bir şey için yeni bir isim gerektirecek kadar farklı görünüyor
      Bu arada bunu özgün yazıyı küçümsemek için söylemiyorum, yine de harika bir hack
    • Steel fena görünmüyor: https://github.com/mattwparas/steel
      Başka Lisp'ler de var (https://github.com/alilleybrinker/langs-in-rust). Yalnız daha az aktif biçimde bakımı yapılıyor gibiler

  • Bunu yaparken eğlendim ve ayrıca rust-analyser'ın milyonlarca token üreten makroları işleyemediğini de öğrendim

  • Herkesin “eğlenceli” diye tezahürat yapması bekleniyor ama ben böyle şeyler gördükçe Rust'ta bunun mümkün olmasından hoşlanmıyorum
    Rust zaten baştan beri basit bir dil değildi ama şimdi ilk hâline göre çok daha zor taşınır bir şeye dönüşmüş gibi geliyor

    • Rust'ın basit bir dil olmadığına katılıyorum
      Ama bunun mümkün olmasından neden hoşlanmadığını pek anlamıyorum. Makro sistemi neredeyse sınırsız karmaşıklıkta kod üretebilir, ama makrolarla sandbox'lanmış bir Lisp uygulamak, Rust'ın ilk günlerine göre yönetmesinin daha zor hâle geldiğine dair güçlü bir örnek mi, emin değilim
      Öte yandan Rust'ın tür sisteminin C++ şablonları ya da Haskell tür sistemi gibi Turing-complete olması nedeniyle, o şekilde yazılmış bir Lisp'i de görmek isterdim
    • Buna kesinlikle katılmıyorum. Rust ekibi kısıtları kaldırıp özellikleri daha ortogonal hâle getirerek dili kullanmayı sürekli kolaylaştırıyor
      Bunun öne çıkan örnekleri non-lexical lifetimes, return-position impl Trait ve async trait. 1.0 öncesinde özel sözdizimine sahip GC referansları da yerleşik olarak vardı ama böyle özellikler kaldırıldı
    • 1.0'dan sonraki gerçek anlamda büyük değişiklik aslında sadece async oldu. Async olmadan yaşamak istiyorsan bu tamamen senin seçimin ve dilin bütünüyle isteğe bağlı bir parçası
      Eğer ilke olarak sadeliği benimseyen bir dil istiyorsan, Rust zaten hiçbir zaman öyle bir dil değildi; başka pek çok seçenek var
    • Bunun mümkün olması için aslında çok az şey gerekiyor. Basit kabul edilen C makrolarıyla bile yapılabilir gibi görünüyor
      Kontrol ettim ve bu bahsi ben kazandım: https://github.com/kchanqvq/CSP
    • Makrolar zaten her zaman hem çok güçlü hem de aynı anda sorunlu şeyler değil mi? Makro tarafını dilin karmaşıklığına katmazdım
      Özellikle makro “yazma” kısmından söz ediyorum; bence kullanılması da kullanılmaması da mümkün olan ek bir özellik gibi

  • Vay canına, bu macro_rules kullanıyor

  • Ama C++'ın şablonları Turing-complete diye aklı başında bir dil olmadığını söylemiyor muyduk?

    • C++, biraz bildiğin anda bile aklı başında bir dil değil. En azından Rust makroları harfi harfine metin değiştirme yapmıyor; bu da aydınlığa doğru bir adım
    • Turing-complete olmakla Turing tarpiti olmak aynı şey değil
      Rust makro sisteminin hangisine girdiğini bilmiyorum
    • C++ şablonlarıyla geliştirme yapmak cehennem gibi. Rust'ta en azından macro_expand var ve Rust araçlarının iyi yapılmış olması büyük fark yaratıyor

  • Carp da anılmalı. Ödünç alma denetimi kullanan bir Lisp ve Lisp dünyasının “Rust”ı gibi
    1: https://github.com/carp-lang/Carp