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

 (github.com/RyanWelly)
1 คะแนน โดย GN⁺ 2024-09-15 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • lisp-in-rs-macros เป็นอินเทอร์พรีเตอร์ Lisp แบบ lexical scope อย่างง่ายที่ทำงานด้วย declarative macros ของ Rust ล้วน ๆ และแมโคร lisp! จะประเมินโค้ดในเวลา compile time แล้วสร้างค่า Lisp ที่ถูกแปลงเป็นสตริง
  • lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) ถูกคำนวณระหว่างกระบวนการ macro expansion ของ rustc และขยายเป็นสตริง "A" โดยทั้ง implementation มีขนาด น้อยกว่า 250 บรรทัด
  • ตัวอย่างใช้ CAR, LIST, QUOTE, PROGN, DEFINE, LAMBDA, DISPLAY และตัวอย่าง quine แสดงรูปแบบที่โค้ด Lisp ถูกประเมินเป็นตัวมันเอง
  • ปัจจุบันยังไม่รองรับ recursion แบบระบุชัดเจน แต่สามารถเขียนพฤติกรรมแบบ recursive เช่น list append ได้ด้วย self application; อย่างไรก็ตาม DEFINE เองไม่รองรับการนิยามแบบ recursive
  • ตัวอย่าง metacircular interpreter ดูเหมือนจะทำงานได้ แต่การประเมิน ((lambda (X) X) (quote a)) ใช้เวลามากกว่า 30 วินาทีและสร้าง token มากกว่าหนึ่งล้านรายการ จนไม่มีประสิทธิภาพถึงขั้นที่ cargo ถูก sigkill

Lisp ที่รันอยู่ภายในแมโคร Rust

  • lisp-in-rs-macros เป็นอินเทอร์พรีเตอร์ Lisp แบบ lexical scope ที่เขียนด้วย declarative macros ของ Rust ล้วน ๆ
  • แมโคร lisp! จะประเมินโค้ด Lisp ที่ส่งเข้าไป แล้วแปลงค่า Lisp ที่คำนวณได้เป็นสตริง
  • เช่น lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) จะขยายเป็นสตริง "A"
  • การคำนวณนี้เกิดขึ้นใน เวลา compile time ที่ rustc ขยายแมโคร ไม่ใช่ runtime
  • implementation มีขนาดน้อยกว่า 250 บรรทัด

ตัวอย่างการใช้งานพื้นฐาน

  • สามารถนำ CAR, LIST, QUOTE มาผสมกันเพื่อดึงสมาชิกตัวแรกของ list ได้
let output = lisp!(CAR (LIST (QUOTE A) (QUOTE B) (QUOTE C)));
assert_eq!(output, "A");
  • หากต้องการประเมินหลาย expression ให้ใช้ PROGN
    • PROGN จะประเมิน expression ทั้งหมดและคืนค่าของ expression สุดท้าย
  • DISPLAY จะประเมิน argument ก่อน แล้วขยายเป็นรูปแบบ println!("{}", stringify!(evaled_argument)) เพื่อแปลง token เป็นสตริงแล้วพิมพ์ออกมา
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 ที่ประเมินเป็นตัวเอง

  • ตัวอย่าง quine แสดงรูปแบบที่โค้ด Lisp ถูก ประเมินเป็นตัวมันเอง
lisp!
       ((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
       (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))));
  • โค้ดนี้จะขยายเป็นการเรียก stringify! ดังนี้
stringify!(((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
       (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s))))));

Recursion และ self application

  • Lisp นี้ปัจจุบันยังไม่รองรับ recursion แบบระบุชัดเจน
  • แม้ไม่มี recursion แบบระบุชัดเจน ก็สามารถสร้างพฤติกรรม recursive ได้ด้วย lambda เท่านั้น
  • ฟังก์ชัน append ในตัวอย่างไม่ได้กล่าวถึงชื่อ append โดยตรงใน body แต่ใช้ argument self เพื่อเรียกซ้ำผ่านการนำตัวเองไป apply
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)"

ข้อจำกัดในการใช้งาน

  • แมโคร lisp! ประเมินได้เพียง expression เดียว
    • หากมีหลาย expression ต้องห่อด้วย (PROGN expr1 expr2 expr3)
  • list ว่างไม่ใช่ self-evaluating
    • สามารถได้ค่า list ว่างด้วย NIL หรือ (QUOTE ())
    • list ว่างเป็นอ็อบเจ็กต์ falsy เพียงชนิดเดียว
  • ไม่รองรับ dotted list
    • CONS สมมติว่า argument สุดท้ายเป็น list
  • DEFINE ใช้ได้ทุกที่และประเมินเป็น list ว่าง แต่ไม่รองรับ recursion
  • TRUE เป็น atom เพียงตัวเดียวที่ไม่ใช่ฟังก์ชันและเป็น self-evaluating

form ที่รองรับ

DEFINE
QUOTE
LAMBDA
LET
PROGN
CAR
CDR
CONS
LIST
EQ
ATOM
APPLY
  • DEFINE มีลักษณะใกล้เคียงกับ internal definition ของ Scheme มากกว่าจะเป็นการนิยาม recursive แบบ Lisp จริง ๆ

อินเทอร์พรีเตอร์ Lisp ที่เขียนด้วย Lisp

  • repository มีตัวอย่าง metacircular interpreter ที่เขียนขึ้นบน Lisp นี้
  • ตัวอย่างนิยาม Y2 combinator สำหรับ argument สองตัว, CADR, CAAR, ASSOC, eval และอื่น ๆ
  • อินเทอร์พรีเตอร์ดูเหมือนจะทำงานได้ แต่เมื่อพยายามประเมิน ((lambda (X) X) (quote a)) จะใช้เวลามากกว่า 30 วินาที
  • การประเมินดังกล่าวสร้าง token มากกว่าหนึ่งล้านรายการ และสุดท้ายมีขนาดใหญ่จน cargo ถูก sigkill
  • recursion ที่ใช้ Y combinator แบบระบุชัดเจนในที่นี้ ไม่มีประสิทธิภาพ เป็นพิเศษ
  • มีการระบุว่าควรเพิ่ม recursive primitive แบบระบุชัดเจนเพื่อแก้ปัญหานี้
  • สำหรับ walkthrough การเขียน metacircular evaluator แนะนำ "Roots of Lisp" ของ Paul Graham

วิธี implementation และเอกสารอ้างอิง

  • คำอธิบายเชิงเทคนิคอยู่ใน EXPLANATION.md
  • โดยพื้นฐานแล้วแมโครจำลอง SECD machine
    • SECD machine เป็น abstract machine แบบ stack-based อย่างง่ายสำหรับประเมิน lambda calculus term

เอกสารอ้างอิง

  • 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
  • บล็อกโพสต์เกี่ยวกับ Lisp ของ Matt Might: https://matt.might.net

TODO

  • เพิ่ม letrec
  • เพิ่ม define แบบ recursive

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-09-15
ความคิดเห็นบน Hacker News

  • กฎข้อที่สิบของ Greenspun มาอีกแล้ว: https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule

    • แต่นี่พูดถึงโค้ดเบสที่ไม่ได้มีเป้าหมายหลักเพื่อทำ Lisp implementation เลย เลยดูไม่ค่อยตรงนักในกรณีนี้
    • ตัวอย่างที่ดีของกฎนี้คือ C++ ค่อย ๆ ค้นพบ car/cdr ขึ้นมาใหม่ภายในภาษาเท็มเพลตของตัวเองอย่างเชื่องช้าราวธารน้ำแข็ง
      กว่าจะถึง C++26 ก็เพิ่งจะสามารถใช้ Args...[0] เพื่อเอา car ของ type-name parameter pack ได้
      ไม่เข้าใจว่าทำไมถึงไม่เพิ่ม nil กับฟังก์ชัน car/cdr สำหรับ parameter pack ว่าง และเปิดให้เก็บ parameter pack ได้ แทนไวยากรณ์ยุ่งเหยิงแบบทุกวันนี้
    • ทำให้นึกถึงประโยคที่ว่า “โปรแกรม C หรือ Fortran ที่ซับซ้อนมากพอ จะมีการ implement Common Lisp ครึ่งหนึ่งแบบชั่วคราว ไม่มีสเปกทางการ เต็มไปด้วยบั๊ก และช้า”
    • ไม่รู้ว่า “ซับซ้อนมากพอ” หมายถึงอะไร นิยามไม่ค่อยดีเท่าไร

  • เคยลองทำอะไรคล้าย ๆ กันมาก่อน แล้วเจอปัญหาว่า นิยามสัญลักษณ์ที่มีขีดกลาง ไม่ได้
    อะไรอย่าง DEFINE MY-FN... ใช้ไม่ได้ เพราะ Rust จะแยกโทเคนตรงขีดกลาง
    เป็นความต่างเล็กน้อยก็จริง แต่แปลว่าคัดลอกโค้ด Lisp จริงมาแปะตรง ๆ ไม่ได้ ต้องเปลี่ยนเป็นขีดล่างหมด สงสัยว่า implementation นี้ก็เป็นเหมือนกันไหม

    • ตอนนี้สมมติให้ทุก atom เป็น Rust identifier ไปก่อน เพราะจะทำให้ implement ง่ายและจับคู่ได้ด้วย $x:ident เลยยังไม่รองรับขีดกลางใน atom
      แต่ก็น่าจะจับคู่แบบ $x:ident $(- $y:ident)* ได้แทน อาจต้องแก้รายละเอียดของบางแขนงในแมโคร แต่ดูแล้วน่าจะทำได้
    • ไม่น่ามีปัญหานะ? DEFINE MYᜭFN... ใช้งานได้ดี

  • อยากให้มี Lisp implementation ที่รองรับได้ดีบน Rust แบบจริงจัง ไม่ใช่แค่แมโคร
    ถ้าสร้างบน Rust จะรักษาหรือเสียเรื่อง memory safety ไปได้แค่ไหนนะ จะใช้ borrow checker แบบไม่ประหลาดได้จริงหรือเปล่า?

    • Lisp compiler บางตัวอย่าง SBCL ทำ การตรวจชนิดตอนคอมไพล์ ที่กว้างขวางกว่านั้นได้ด้วย แต่ข้อมูลนั้นต้องให้โปรแกรมเมอร์ใส่เอง และโดยมากก็ใกล้เคียงกับขั้นตอน optimization มากกว่าการพัฒนาแบบค่อยเป็นค่อยไปในชีวิตประจำวัน
      โดยทั่วไป Lisp นิยามตัวเองด้วยความเป็นภาษาพลวัต และการตรวจชนิดตอนรันไทม์ก็เป็นส่วนใหญ่ของมัน ถ้าบังคับให้โปรแกรมเมอร์ต้องกังวลเรื่องวิธีจัดการอ็อบเจ็กต์ล่วงหน้า มันก็จะขัดกับอิสระและพลังการแสดงออกที่คาดหวังจากระบบแบบนั้น
      ในทางกลับกัน ตัวคอมไพเลอร์เองอาจเรียบง่ายขึ้นได้ โค้ดทั่วไปที่ไม่มี declaration เพิ่มเติมจะปลอดภัยเป็นพื้นฐานอยู่แล้ว และในกรณีของ bytecode VM อย่าง CLISP หรือ Lisp machine ที่มีการตรวจชนิดระดับฮาร์ดแวร์ declaration พวกนั้นอาจถูกเมินได้โดยที่ยังปลอดภัยเสมอ
      SBCL คอมไพล์โค้ดได้ค่อนข้างเร็ว และก็เคยได้ยินมาว่า implementation อื่นเร็วกว่าอีก ส่วนคอมไพเลอร์ Rust น่าจะมีแนวโน้มแนะนำแนวคิดเรื่อง thrashing ให้โปรแกรมเมอร์รุ่นใหม่มากกว่า
      สำหรับผม ทั้งสองโลกนี้เข้ากันยากกว่าที่เห็นตอนแรกมาก Lisp เป็นภาษาตัวแทนของปรัชญา “The Right Thing” โดยแก่นแท้ ส่วน C เป็นภาษาแบบ “Worse is Better” และ Rust ก็ไม่ใช่ทั้งสองแบบ แต่เหมือนเป็นอะไรอีกอย่างที่ต่างออกไปมากเสียจนควรมีชื่อใหม่ไว้เรียกลักษณะด้านแย่ของทั้งสองปรัชญาที่มันสะท้อนออกมา
      ไม่ได้จะกดงานต้นฉบับนะ ยังไงนี่ก็เป็นแฮ็กที่เจ๋งอยู่ดี
    • Steel ดูใช้ได้เลย: https://github.com/mattwparas/steel
      ยังมี Lisp อื่น ๆ อีกด้วย(https://github.com/alilleybrinker/langs-in-rust) แต่ดูเหมือนจะไม่ค่อยมีการดูแลต่อเนื่องเท่าไร

  • ทำไปก็สนุกดี และยังได้รู้ด้วยว่า rust-analyser รับมือกับแมโครที่สร้างโทเคนนับล้านตัวไม่ไหว

  • เหมือนทุกคนควรจะต้องร้องว่า “สนุกดี” แต่ทุกครั้งที่เห็นอะไรแบบนี้ก็ยิ่งไม่ชอบที่ Rust เปิดทางให้ทำได้
    Rust เดิมทีก็ไม่ใช่ภาษาที่เรียบง่ายอยู่แล้ว แต่ตอนนี้ดูเหมือนจะยิ่งกลายเป็นอะไรที่รับมือยากกว่าตอนแรกมาก

    • เห็นด้วยว่า Rust ไม่ใช่ภาษาที่เรียบง่าย
      แต่ก็ไม่ค่อยเข้าใจว่าทำไมถึงไม่ชอบที่มันทำแบบนี้ได้ ระบบแมโครสร้างโค้ดที่ซับซ้อนได้แทบไม่จำกัดก็จริง แต่การทำ Lisp แบบแซนด์บ็อกซ์ด้วยแมโครจะเป็นตัวอย่างที่หนักแน่นขนาดนั้นหรือว่ามันทำให้ Rust จัดการยากกว่ายุคแรก ๆ
      อีกด้านหนึ่ง พอรู้ว่าระบบชนิดของ Rust เป็น ทัวริงสมบูรณ์ เหมือนเท็มเพลต C++ หรือระบบชนิดของ Haskell ก็เลยอยากเห็น Lisp ที่ implement ด้วยวิธีนั้นเหมือนกัน
    • ไม่เห็นด้วยอย่างแรงในจุดนั้น ทีม Rust เอาข้อจำกัดออกและทำให้ฟีเจอร์ต่าง ๆ เป็นออร์โธกอนัลมากขึ้นเรื่อย ๆ เพื่อให้ภาษาใช้ง่ายขึ้นต่อเนื่อง
      ตัวอย่างเด่นคือ non-lexical lifetimes, impl Trait ในตำแหน่งคืนค่า, และ async trait ส่วนก่อน 1.0 ยังเคยมี GC reference แบบ built-in พร้อมไวยากรณ์เฉพาะด้วย ซึ่งฟีเจอร์แบบนั้นก็ถูกถอดออกไปแล้ว
    • การเปลี่ยนแปลงใหญ่ที่มีผลจริงหลัง 1.0 มีแค่ async เท่านั้น ถ้าไม่อยากใช้ async ก็เลือกไม่ใช้ได้ทั้งหมด และมันเป็นส่วนที่เลือกใช้ได้ของภาษา
      ถ้าคุณต้องการภาษาที่ยึดความเรียบง่ายเป็นหลัก Rust ก็ไม่เคยเป็นภาษานั้นแต่แรกอยู่แล้ว และก็มีตัวเลือกอื่นอีกมาก
    • จริง ๆ แล้วของที่ต้องมีเพื่อให้ทำสิ่งนี้ได้มีน้อยมาก น่าจะทำได้แม้แต่ด้วย C macro ที่คนมองว่าเรียบง่าย
      ลองเช็กแล้ว และผมชนะเดิมพันนี้: https://github.com/kchanqvq/CSP
    • แมโครก็ทรงพลังมากและก็ชวนปวดหัวมากมาแต่ไหนแต่ไรไม่ใช่หรือ? ผมคงไม่เอาฝั่งแมโครไปรวมกับความซับซ้อนของภาษาหรอก
      โดยเฉพาะฝั่งการ “เขียน” แมโคร เพราะมันใกล้เคียงกับความสามารถเสริมที่คุณจะใช้หรือไม่ใช้ก็ได้มากกว่า

  • ว้าว อันนี้ใช้ macro_rules แฮะ

  • แต่ C++ ไม่ใช่ว่าเคยถูกมองว่าไม่ใช่ภาษาที่ปกติเพราะเท็มเพลตของมันเป็นทัวริงสมบูรณ์หรอกหรือ?

    • แค่รู้ C++ นิดหน่อยก็พอจะรู้แล้วว่ามันไม่ใช่ภาษาปกติ อย่างน้อยแมโครของ Rust ก็ไม่ใช่การแทนที่ข้อความแบบตรงตัว จึงถือว่าเป็นก้าวหนึ่งสู่แสงสว่าง
    • ทัวริงสมบูรณ์ กับทัวริงทาร์พิทไม่เหมือนกัน
      ผมไม่รู้ว่าระบบแมโครของ Rust อยู่ฝั่งไหน
    • การพัฒนาด้วยเท็มเพลต C++ คือขุมนรก อย่างน้อย Rust ก็มี macro_expand และเครื่องมือของ Rust ก็ทำมาดีมาก ซึ่งสำคัญมาก

  • Carp ก็ต้องนับด้วย เป็น Lisp ที่ใช้ borrow checker และเป็นเหมือน “Rust” แห่งโลก Lisp
    1: https://github.com/carp-lang/Carp