Lisp yang Diimplementasikan dengan Makro Rust

lisp-in-rs-macros

Sebuah interpreter Lisp sederhana dengan lexical scope yang sepenuhnya berfungsi, dibangun menggunakan makro deklaratif Rust. Makro lisp! memperluas nilai Lisp yang dihitung oleh kode dan mengubahnya menjadi string. Sebagai contoh, lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) diperluas menjadi string "A", dan seluruh komputasi terjadi pada waktu kompilasi saat rustc memperluas makro.

Mengapa ini penting

Ini adalah interpreter Lisp yang ditulis dengan makro Rust, yang sangat menarik. Selain itu, implementasinya ringkas karena ditulis dalam kurang dari 250 baris.

Contoh

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))
); // mencetak "hello there" dan "TRUE"

Contoh menarik lainnya adalah quine:

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

Kode ini mengevaluasi dirinya sendiri.

Rekursi

Lisp ini saat ini tidak mendukung bentuk rekursi eksplisit. Untungnya, rekursi eksplisit tidak diperlukan, cukup dengan lambda. Kita bisa menulis fungsi sederhana untuk menggabungkan dua list:

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

Hasilnya adalah "(A B C D)". Fungsi append tidak menyebut append di dalam tubuhnya, tetapi tetap bisa dipanggil secara rekursif.

Hal yang perlu diperhatikan saat penggunaan

• Makro lisp! hanya mengevaluasi satu ekspresi. Untuk mengevaluasi beberapa ekspresi, gunakan (PROGN expr1 expr2 expr3).
• Bentuk DISPLAY mengevaluasi satu ekspresi lalu menghasilkan pernyataan println!("{}", stringify!(...)) untuk mencetak versi string dari token.
• List kosong tidak mengevaluasi dirinya sendiri; untuk mendapatkan nilai list kosong, gunakan NIL atau (QUOTE ()).
• Dotted list tidak didukung, dan cons mengasumsikan argumen terakhir adalah list.
• Bentuk define dapat digunakan di mana saja dan akan dievaluasi menjadi list kosong, tetapi tidak mendukung rekursi.
• TRUE adalah satu-satunya atom yang mengevaluasi dirinya sendiri dan bukan fungsi.

Bentuk yang didukung

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

Interpreter metasirkular

Berikut adalah interpreter Lisp yang ditulis dalam 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)
);

Kode ini memang berfungsi, tetapi saat mencoba mengevaluasi ((lambda (X) X) (quote a)) di dalam interpreter, prosesnya memakan waktu lebih dari 30 detik dan menghasilkan lebih dari satu juta token. Rekursi dengan y combinator eksplisit tidak efisien di sini. Untuk mengatasinya, perlu ditambahkan primitive rekursi eksplisit. Untuk penjelasan yang sangat baik tentang cara menulis evaluator metasirkular, lihat "Roots of Lisp" karya Paul Graham.

Penjelasan teknis

Lihat EXPLANATION.md. Makro ini mensimulasikan mesin SECD, yaitu mesin abstrak sederhana berbasis stack untuk mengevaluasi ekspresi lambda calculus.

Referensi yang sangat bagus

• Peter Henderson, "Functional Programming: Application and Implementation"
• Mads Sig Ager dkk., "A functional correspondence between evaluators and abstract machines." (2003)
• Simon Peyton Jones, "The Implementation of Functional Programming Languages"
• Semua tulisan tentang Lisp di blog Matt Might (https://matt.might.net)

TODO

• menambahkan letrec
• menambahkan definisi rekursif

Ringkasan GN⁺

• Interpreter Lisp yang ditulis dengan makro Rust sangat menarik dan menawarkan kemampuan kuat dengan kode yang ringkas.
• Meski tidak mendukung rekursi secara eksplisit, rekursi bisa diimplementasikan melalui lambda.
• Interpreter metasirkular tidak efisien, sehingga perlu menambahkan primitive rekursi eksplisit.
• "Roots of Lisp" karya Paul Graham adalah referensi yang sangat baik untuk memahami evaluator metasirkular.
• Proyek lain dengan fungsi serupa yang direkomendasikan adalah interpreter Scheme atau varian Lisp lainnya.