Lisp ที่สร้างด้วยแมโครของ Rust

(github.com/RyanWelly)

1 คะแนน โดย GN⁺ 2024-09-15 | ยังไม่มีความคิดเห็น | แชร์ทาง WhatsApp

`lisp-in-rs-macros`

อินเทอร์พรีเตอร์ Lisp แบบ lexical scope ที่เรียบง่ายแต่ใช้งานได้ครบถ้วน สร้างขึ้นทั้งหมดด้วย declarative macro ของ Rust แมโคร lisp! จะขยายค่า Lisp ที่คำนวณได้จากโค้ดและแปลงเป็นสตริง ตัวอย่างเช่น lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) จะถูกขยายเป็นสตริง "A" และการคำนวณทั้งหมดเกิดขึ้นในช่วงคอมไพล์เมื่อ rustc ทำการขยายแมโคร

ทำไมจึงสำคัญ

นี่คืออินเทอร์พรีเตอร์ Lisp ที่เขียนด้วยแมโครของ Rust ซึ่งน่าสนใจมาก อีกทั้งยังเขียนด้วยโค้ดไม่ถึง 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"

อีกตัวอย่างที่น่าสนุกคือ quine:

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

โค้ดนี้ประเมินค่าตัวมันเอง

การเรียกซ้ำ

Lisp ตัวนี้ยังไม่รองรับการเรียกซ้ำแบบ explicit ในตอนนี้ โชคดีที่เราไม่จำเป็นต้องมีการเรียกซ้ำแบบ explicit แค่มี lambda ก็พอ สามารถเขียนฟังก์ชันง่าย ๆ สำหรับเชื่อมสองลิสต์เข้าด้วยกันได้:

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 ในตัวฟังก์ชันเอง แต่ยังสามารถเรียกตัวเองแบบ recursive ได้

ข้อควรระวังเมื่อใช้งาน

แมโคร lisp! ประเมินได้เพียงนิพจน์เดียว หากต้องการประเมินหลายนิพจน์ ต้องใช้ (PROGN expr1 expr2 expr3)
รูปแบบ DISPLAY จะประเมินนิพจน์เดียว จากนั้นสร้างคำสั่ง println!("{}", stringify!(...)) เพื่อแสดงเวอร์ชันสตริงของโทเค็น
ลิสต์ว่างไม่ประเมินค่าเป็นตัวมันเอง หากต้องการค่าลิสต์ว่าง ให้ใช้ NIL หรือ (QUOTE ())
ไม่รองรับ dotted list และ cons จะสมมติว่าอาร์กิวเมนต์ตัวสุดท้ายเป็นลิสต์
รูปแบบ define ใช้ได้ทุกที่และจะประเมินเป็นลิสต์ว่าง แต่ไม่รองรับการเรียกซ้ำ
TRUE เป็นอะตอมเดียวที่ประเมินค่าเป็นตัวมันเองและไม่ใช่ฟังก์ชัน

รูปแบบที่รองรับ

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

อินเทอร์พรีเตอร์แบบ meta-circular

ต่อไปนี้คืออินเทอร์พรีเตอร์ 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 วินาทีและสร้างโทเค็นมากกว่าหนึ่งล้านรายการ การเรียกซ้ำด้วย y combinator แบบ explicit ไม่มีประสิทธิภาพในกรณีนี้ วิธีแก้คือต้องเพิ่ม primitive สำหรับการเรียกซ้ำแบบ explicit คำอธิบายที่ยอดเยี่ยมเกี่ยวกับการเขียน meta-circular evaluator ดูได้จาก "Roots of Lisp" ของ Paul Graham

คำอธิบายทางเทคนิค

ดู EXPLANATION.md แมโครนี้จำลองเครื่อง SECD ซึ่งเป็น abstract machine แบบใช้สแตกที่เรียบง่ายสำหรับประเมินนิพจน์ lambda calculus

แหล่งข้อมูลที่ยอดเยี่ยม

"Functional Programming: Application and Implementation" โดย Peter Henderson
"A functional correspondence between evaluators and abstract machines." โดย Mads Sig Ager และคณะ (2003)
"The Implementation of Functional Programming Languages" โดย Simon Peyton Jones
บทความทั้งหมดเกี่ยวกับ Lisp ในบล็อกของ Matt Might (https://matt.might.net)

TODO

เพิ่ม letrec
เพิ่มนิยามแบบเรียกซ้ำ

สรุปโดย GN⁺

อินเทอร์พรีเตอร์ Lisp ที่เขียนด้วยแมโคร Rust น่าสนใจมาก และมอบความสามารถที่ทรงพลังด้วยโค้ดที่กระชับ
แม้จะยังไม่รองรับการเรียกซ้ำแบบ explicit แต่สามารถทำการเรียกซ้ำผ่าน lambda ได้
อินเทอร์พรีเตอร์แบบ meta-circular ไม่มีประสิทธิภาพนัก จึงจำเป็นต้องเพิ่ม primitive สำหรับการเรียกซ้ำแบบ explicit
"Roots of Lisp" ของ Paul Graham เป็นแหล่งข้อมูลชั้นยอดสำหรับทำความเข้าใจ meta-circular evaluator
โปรเจ็กต์อื่นที่มีความสามารถคล้ายกันที่แนะนำได้คืออินเทอร์พรีเตอร์ Scheme หรือ Lisp สายพันธุ์อื่น ๆ