Lisp yang Diimplementasikan dengan Makro Rust

 (github.com/RyanWelly)
1 poin oleh GN⁺ 2024-09-15 | 1 komentar | Bagikan ke WhatsApp
  • lisp-in-rs-macros adalah interpreter Lisp sederhana dengan lexical scope yang berjalan hanya dengan makro deklaratif Rust, dan makro lisp! mengevaluasi kode saat waktu kompilasi untuk menghasilkan nilai Lisp yang telah diubah menjadi string
  • lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) dihitung selama proses ekspansi makro oleh rustc dan diperluas menjadi string "A", sementara seluruh implementasinya kurang dari 250 baris
  • Contohnya menggunakan CAR, LIST, QUOTE, PROGN, DEFINE, LAMBDA, DISPLAY, dan contoh quine menunjukkan bentuk saat kode Lisp mengevaluasi dirinya sendiri
  • Rekursi eksplisit saat ini belum didukung, tetapi perilaku rekursif seperti append list bisa ditulis dengan self application; namun DEFINE sendiri tidak menangani definisi rekursif
  • Contoh interpreter metasirkular tampak berjalan, tetapi evaluasi ((lambda (X) X) (quote a)) memakan waktu lebih dari 30 detik dan menghasilkan lebih dari sejuta token hingga cargo terkena sigkill karena sangat tidak efisien

Lisp yang Berjalan di Dalam Makro Rust

  • lisp-in-rs-macros adalah interpreter Lisp dengan lexical scope yang ditulis hanya dengan makro deklaratif Rust
  • Makro lisp! mengevaluasi kode Lisp yang diberikan, lalu mengubah nilai Lisp hasil perhitungan menjadi string
  • Sebagai contoh, lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) diperluas menjadi string "A"
  • Perhitungan ini tidak terjadi saat runtime, melainkan pada waktu kompilasi ketika rustc mengekspansi makro
  • Implementasinya kurang dari 250 baris

Contoh Penggunaan Dasar

  • Dengan menggabungkan CAR, LIST, dan QUOTE, kita bisa mengambil elemen pertama dari sebuah list
let output = lisp!(CAR (LIST (QUOTE A) (QUOTE B) (QUOTE C)));
assert_eq!(output, "A");
  • Untuk mengevaluasi beberapa ekspresi, gunakan PROGN
    • PROGN mengevaluasi semua ekspresi dan mengembalikan nilai dari ekspresi terakhir
  • DISPLAY terlebih dahulu mengevaluasi argumen, lalu diperluas ke bentuk println!("{}", stringify!(evaled_argument)) untuk mengubah token menjadi string dan mencetaknya
lisp!(PROGN
    (DEFINE message (LAMBDA () (QUOTE "hello there")))
    (DISPLAY (message))
    (DEFINE NOT (LAMBDA (X) (COND (X NIL) (TRUE TRUE))) )
    (DISPLAY (NOT NIL))
);
  • Contoh di atas mencetak "hello there" dan "TRUE"

Quine yang Mengevaluasi Dirinya Sendiri

  • Contoh quine menunjukkan bentuk ketika kode Lisp mengevaluasi dirinya sendiri
lisp!
       ((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
       (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))));
  • Kode ini diperluas menjadi pemanggilan stringify! berikut
stringify!(((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
       (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s))))));

Rekursi dan Self Application

  • Lisp ini saat ini belum mendukung rekursi eksplisit
  • Meski tanpa rekursi eksplisit, perilaku rekursif tetap bisa dibuat hanya dengan lambda
  • Fungsi append pada contoh melakukan pemanggilan rekursif melalui self application lewat argumen self, tanpa menyebut nama append secara langsung di dalam isi fungsi
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)))

)
  • Kode ini menghasilkan "(A B C D)"

Batasan Penggunaan

  • Makro lisp! hanya mengevaluasi satu ekspresi
    • Beberapa ekspresi harus dibungkus sebagai (PROGN expr1 expr2 expr3)
  • List kosong tidak bersifat self-evaluating
    • Nilai list kosong bisa diperoleh dengan NIL atau (QUOTE ())
    • List kosong adalah satu-satunya objek falsy
  • Dotted list tidak didukung
    • CONS mengasumsikan argumen terakhir adalah list
  • DEFINE bisa digunakan di mana saja dan akan dievaluasi menjadi list kosong, tetapi rekursi tidak didukung
  • TRUE adalah satu-satunya atom non-fungsi yang bersifat self-evaluating

Form yang Didukung

DEFINE
QUOTE
LAMBDA
LET
PROGN
CAR
CDR
CONS
LIST
EQ
ATOM
APPLY
  • DEFINE lebih mirip bentuk internal definition di Scheme daripada definisi rekursif ala Lisp yang sesungguhnya

Interpreter Lisp yang Ditulis dengan Lisp

  • Repositori ini menyertakan contoh interpreter metasirkular yang ditulis di atas Lisp ini
  • Contohnya mendefinisikan kombinator Y2 untuk dua argumen, CADR, CAAR, ASSOC, eval, dan lainnya
  • Interpreter tersebut tampaknya berjalan, tetapi ketika mencoba mengevaluasi ((lambda (X) X) (quote a)), prosesnya memakan waktu lebih dari 30 detik
  • Evaluasi tersebut menghasilkan lebih dari sejuta token, dan pada akhirnya cargo menjadi sangat besar hingga terkena sigkill
  • Rekursi yang memakai kombinator Y eksplisit sangat tidak efisien di sini
  • Tertulis bahwa untuk memperbaikinya perlu ditambahkan primitive rekursi eksplisit
  • Untuk walkthrough penulisan evaluator metasirkular, direkomendasikan "Roots of Lisp" karya Paul Graham

Cara Implementasi dan Referensi

  • Penjelasan teknis tersedia di EXPLANATION.md
  • Secara esensial, makro ini mensimulasikan SECD machine
    • SECD machine adalah mesin abstrak sederhana berbasis stack untuk mengevaluasi term lambda calculus

Referensi

  • 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
  • Tulisan blog Matt Might tentang Lisp: https://matt.might.net

TODO

  • Tambahkan letrec
  • Tambahkan define rekursif

Bacaan terkait

1 komentar

 
GN⁺ 2024-09-15
Komentar Hacker News

  • Hukum kesepuluh Greenspun muncul lagi: https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule

    • Hukum ini membahas codebase yang tujuan utamanya bukan implementasi Lisp, jadi sepertinya kurang tepat untuk kasus ini
    • Contoh bagus dari hukum ini adalah bagaimana C++ menemukan kembali car/cdr di dalam bahasa template-nya dengan kecepatan selambat gletser
      Baru di C++26 kita bisa mendapatkan car dari type-name parameter pack dengan Args...[0]
      Entah kenapa mereka tidak memperkenalkan nil untuk parameter pack kosong dan fungsi car/cdr, lalu membuat parameter pack bisa disimpan alih-alih kekacauan sintaks seperti sekarang
    • Langsung teringat kalimat: “Setiap program C atau Fortran yang cukup kompleks memuat implementasi setengah Common Lisp yang ad hoc, tidak dispesifikasikan secara informal, penuh bug, dan lambat”
    • Saya tidak tahu apa maksud “cukup kompleks”, dan definisinya kurang bagus

  • Dulu saya pernah mencoba hal serupa, tetapi ada masalah tidak bisa mendefinisikan simbol yang mengandung tanda hubung
    Yang seperti DEFINE MY-FN... tidak bisa, karena Rust memecah token pada tanda hubung
    Ini perbedaan kecil, tapi berarti potongan kode Lisp nyata tidak bisa langsung ditempel begitu saja dan semuanya harus diubah menjadi garis bawah. Saya penasaran apakah implementasi ini juga sama

    • Saat ini semua atom diasumsikan sebagai identifier Rust. Itu membuat implementasinya mudah karena bisa dicocokkan dengan $x:ident, jadi tanda hubung di dalam atom tidak didukung
      Sebagai gantinya, sepertinya bisa dicocokkan dengan pola seperti $x:ident $(- $y:ident)*. Beberapa detail cabang makro perlu diubah, tapi tampaknya memungkinkan
    • Sepertinya tidak masalah? DEFINE MYᜭFN... berjalan dengan baik

  • Akan menyenangkan kalau ada implementasi Lisp berbasis Rust yang didukung dengan baik, bukan hanya makro
    Saya penasaran seberapa banyak keamanan memori bisa dipertahankan atau hilang jika dibuat di atas Rust. Apakah mungkin memanfaatkan borrow checker dengan cara yang waras?

    • Beberapa compiler Lisp seperti SBCL juga memungkinkan pemeriksaan tipe saat kompilasi yang lebih luas, tetapi informasi itu harus diberikan oleh programmer dan biasanya lebih merupakan bagian dari tahap optimisasi daripada pengembangan inkremental sehari-hari
      Lisp biasanya didefinisikan oleh sifatnya yang dinamis, dan pemeriksaan tipe saat runtime adalah bagian besar darinya. Jika programmer harus memikirkan lebih dulu cara objek dikelola, itu bertabrakan dengan kebebasan dan daya ekspresi yang diharapkan dari sistem seperti itu
      Sebaliknya, compilernya sendiri bisa relatif sederhana. Kode biasa tanpa deklarasi tambahan pada dasarnya aman, dan pada VM bytecode seperti CLISP atau mesin Lisp dengan pemeriksaan tipe hardware, deklarasi semacam itu bisa diabaikan dan tetap selalu aman
      SBCL mengompilasi kode cukup cepat, dan saya juga pernah dengar implementasi lain bahkan lebih cepat. Sebaliknya, compiler Rust lebih mungkin memperkenalkan konsep thrashing kepada programmer muda
      Menurut saya keduanya, meski sekilas tidak terlihat begitu, berasal dari dunia yang sulit dipadukan. Lisp pada dasarnya adalah bahasa perwakilan filosofi “The Right Thing”, sementara C adalah bahasa “Worse is Better”. Rust bukan keduanya, dan tampak seperti sesuatu yang sama sekali berbeda sampai perlu nama baru yang mencerminkan sifat buruk dari kedua filosofi itu
      Bukan berarti saya ingin merendahkan tulisan aslinya; ini tetap hack yang keren
    • Steel terlihat cukup bagus: https://github.com/mattwparas/steel
      Ada Lisp lain juga (https://github.com/alilleybrinker/langs-in-rust). Hanya saja tampaknya pemeliharaannya kurang aktif

  • Membuatnya menyenangkan, dan saya juga belajar bahwa rust-analyser tidak bisa menangani makro yang menghasilkan jutaan token

  • Suasananya memang seperti semua orang harus bersorak “seru”, tetapi setiap kali melihat hal seperti ini, saya jadi tidak suka fakta bahwa ini mungkin dilakukan di Rust
    Rust sejak awal memang bukan bahasa sederhana, tetapi rasanya sekarang sudah menjadi jauh lebih sulit dikelola daripada dulu

    • Saya setuju Rust bukan bahasa yang sederhana
      Namun saya kurang paham mengapa fakta bahwa ini mungkin dilakukan menjadi sesuatu yang tidak disukai. Sistem makronya memang bisa menghasilkan kode yang kompleksitasnya nyaris tak terbatas, tetapi saya tidak yakin implementasi Lisp yang tersandbox di dalam makro adalah contoh kuat bahwa Rust menjadi lebih sulit dikelola dibanding masa awalnya
      Di sisi lain, karena sistem tipe Rust Turing-complete seperti template C++ atau sistem tipe Haskell, saya jadi ingin melihat Lisp yang diimplementasikan dengan cara itu juga
    • Saya sangat tidak setuju dengan bagian itu. Tim Rust terus membuat bahasa lebih mudah digunakan dengan menghapus batasan dan membuat fitur-fiturnya lebih ortogonal
      Contoh utamanya adalah non-lexical lifetimes, impl Trait pada posisi return, dan async trait. Sebelum 1.0 bahkan ada referensi GC bawaan dengan sintaks khusus, tetapi fitur seperti itu juga dihapus
    • Satu-satunya perubahan besar yang nyata sejak 1.0 adalah async. Jika ingin hidup tanpa async, itu sepenuhnya opsional, dan merupakan bagian bahasa yang benar-benar opsional
      Jika menginginkan bahasa yang menjadikan kesederhanaan sebagai prinsip, Rust memang sejak awal bukan bahasa seperti itu, dan ada banyak pilihan lain
    • Sebenarnya hanya perlu sangat sedikit hal agar ini bisa dilakukan. Sepertinya bahkan makro C yang dianggap sederhana pun bisa melakukannya
      Saya sudah mengeceknya, dan saya menang taruhan ini: https://github.com/kchanqvq/CSP
    • Bukankah makro memang selalu sangat kuat sekaligus rumit? Saya tidak akan memasukkan sisi makro ke dalam kompleksitas bahasa
      Terutama soal “menulis” makro; menurut saya itu lebih seperti fitur tambahan yang boleh dipakai atau tidak

  • Wow, ini memakai macro_rules

  • Tapi bukankah dulu katanya C++ bukan bahasa yang waras karena template-nya Turing-complete?

    • Bahkan dengan sedikit pengetahuan saja, C++ memang bukan bahasa yang waras. Setidaknya makro Rust bukan substitusi teks literal, jadi itu satu langkah menuju cahaya
    • Turing-complete dan Turing tarpit itu berbeda
      Saya tidak tahu sistem makro Rust termasuk yang mana
    • Mengembangkan dengan template C++ itu neraka. Di Rust setidaknya ada macro_expand, dan kualitas tooling Rust juga menjadi faktor besar

  • Carp juga tidak boleh dilupakan. Ini Lisp yang menggunakan borrow checking, semacam “Rust”-nya dunia Lisp
    1: https://github.com/carp-lang/Carp