Lisp được triển khai bằng macro Rust

 (github.com/RyanWelly)
1 điểm bởi GN⁺ 2024-09-15 | 1 bình luận | Chia sẻ qua WhatsApp
  • lisp-in-rs-macros là một trình thông dịch Lisp lexical scope đơn giản hoạt động chỉ bằng declarative macro của Rust, và macro lisp! đánh giá mã ở thời điểm biên dịch để tạo ra giá trị Lisp đã được chuyển thành chuỗi
  • lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) được tính toán trong quá trình mở rộng macro của rustc và được mở rộng thành chuỗi "A"; toàn bộ phần triển khai có dưới 250 dòng
  • Ví dụ sử dụng CAR, LIST, QUOTE, PROGN, DEFINE, LAMBDA, DISPLAY, và ví dụ quine cho thấy dạng mã Lisp tự đánh giá thành chính nó
  • Đệ quy tường minh hiện chưa được hỗ trợ, nhưng có thể viết hành vi đệ quy như append danh sách bằng self application; tuy nhiên bản thân DEFINE không xử lý định nghĩa đệ quy
  • Ví dụ trình thông dịch meta-circular có vẻ hoạt động, nhưng việc đánh giá ((lambda (X) X) (quote a)) mất hơn 30 giây và tạo ra hơn một triệu token, kém hiệu quả đến mức cargo bị sigkill

Lisp chạy bên trong macro Rust

  • lisp-in-rs-macros là một trình thông dịch Lisp lexical scope được viết hoàn toàn bằng declarative macro của Rust
  • Macro lisp! đánh giá mã Lisp được truyền vào rồi chuyển giá trị Lisp đã tính được thành chuỗi
  • Ví dụ, lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) sẽ được mở rộng thành chuỗi "A"
  • Việc tính toán này diễn ra không phải ở runtime mà tại thời điểm biên dịch khi rustc mở rộng macro
  • Phần triển khai có dưới 250 dòng

Ví dụ sử dụng cơ bản

  • Có thể kết hợp CAR, LIST, QUOTE để lấy phần tử đầu tiên của danh sách
let output = lisp!(CAR (LIST (QUOTE A) (QUOTE B) (QUOTE C)));
assert_eq!(output, "A");
  • Để đánh giá nhiều biểu thức, dùng PROGN
    • PROGN đánh giá mọi biểu thức và trả về giá trị của biểu thức cuối cùng
  • DISPLAY trước tiên đánh giá đối số, sau đó mở rộng thành dạng println!("{}", stringify!(evaled_argument)) để chuyển token thành chuỗi và in ra
lisp!(PROGN
    (DEFINE message (LAMBDA () (QUOTE "hello there")))
    (DISPLAY (message))
    (DEFINE NOT (LAMBDA (X) (COND (X NIL) (TRUE TRUE))) )
    (DISPLAY (NOT NIL))
);
  • Ví dụ trên sẽ in ra "hello there" và "TRUE"

Quine tự đánh giá thành chính nó

  • Ví dụ quine cho thấy mã Lisp tự đánh giá thành chính nó
lisp!
       ((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
       (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))));
  • Mã này được mở rộng thành lời gọi stringify! như sau
stringify!(((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
       (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s))))));

Đệ quy và self application

  • Lisp này hiện không hỗ trợ đệ quy tường minh
  • Ngay cả khi không có đệ quy tường minh, vẫn có thể tạo hành vi đệ quy chỉ bằng lambda
  • Hàm append trong ví dụ không nhắc trực tiếp đến tên append trong thân hàm, mà thực hiện lời gọi đệ quy thông qua đối số self bằng tự áp dụng
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)))

)
  • Mã này tạo ra kết quả "(A B C D)"

Các giới hạn khi sử dụng

  • Macro lisp! chỉ đánh giá một biểu thức duy nhất
    • Nhiều biểu thức phải được gói trong (PROGN expr1 expr2 expr3)
  • Danh sách rỗng không phải là self-evaluating
    • Có thể lấy giá trị danh sách rỗng bằng NIL hoặc (QUOTE ())
    • Danh sách rỗng là đối tượng falsy duy nhất
  • Không hỗ trợ dotted list
    • CONS giả định đối số cuối cùng là một danh sách
  • DEFINE có thể dùng ở bất cứ đâu và được đánh giá thành danh sách rỗng, nhưng không hỗ trợ đệ quy
  • TRUE là atom duy nhất tự đánh giá thành chính nó mà không phải là hàm

Các form được hỗ trợ

DEFINE
QUOTE
LAMBDA
LET
PROGN
CAR
CDR
CONS
LIST
EQ
ATOM
APPLY
  • DEFINE gần với internal definition của Scheme hơn là định nghĩa đệ quy Lisp thực thụ

Trình thông dịch Lisp được viết bằng Lisp

  • Kho chứa có kèm ví dụ trình thông dịch meta-circular được viết trên chính Lisp này
  • Ví dụ định nghĩa tổ hợp tử Y2 cho hai đối số, CADR, CAAR, ASSOC, eval, v.v.
  • Trình thông dịch có vẻ hoạt động, nhưng khi cố đánh giá ((lambda (X) X) (quote a)) thì mất hơn 30 giây
  • Việc đánh giá đó tạo ra hơn một triệu token, và cuối cùng phình to đến mức cargo bị sigkill
  • Đệ quy dùng tổ hợp tử Y tường minh ở đây đặc biệt kém hiệu quả
  • Tài liệu cho biết cần thêm primitive đệ quy tường minh để khắc phục
  • Với phần hướng dẫn viết bộ đánh giá meta-circular, tác giả khuyến nghị "Roots of Lisp" của Paul Graham

Cách triển khai và tài liệu tham khảo

  • Phần giải thích kỹ thuật nằm trong EXPLANATION.md
  • Về bản chất, macro mô phỏng một SECD machine
    • SECD machine là một máy trừu tượng đơn giản dựa trên stack để đánh giá các term của lambda calculus

Tài liệu tham khảo

  • 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
  • Bài viết blog về Lisp của Matt Might: https://matt.might.net

TODO

  • thêm letrec
  • thêm define đệ quy

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-09-15
Ý kiến trên Hacker News

  • Định luật thứ mười của Greenspun lại xuất hiện rồi: https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule

    • Câu này nói về các codebase mà mục đích chính không phải là triển khai Lisp, nên có vẻ không thật sự khớp ở đây
    • Một ví dụ hay cho định luật này là việc C++ tái khám phá car/cdr trong ngôn ngữ template với tốc độ chậm như băng hà
      Phải đến C++26 mới có thể lấy car của type-name parameter pack bằng Args...[0]
      Không hiểu sao họ không đưa vào nil cho parameter pack rỗng cùng các hàm car/cdr, rồi cho phép lưu parameter pack thay vì mớ cú pháp hỗn loạn như hiện nay
    • Tôi chợt nhớ đúng câu “Mọi chương trình C hoặc Fortran đủ phức tạp đều chứa một nửa Common Lisp được triển khai tạm bợ, không theo đặc tả chính thức, đầy lỗi và chậm”
    • Không rõ “đủ phức tạp” nghĩa là gì, và định nghĩa đó không hay lắm

  • Trước đây tôi từng làm một thứ tương tự, nhưng gặp vấn đề là không thể định nghĩa symbol có dấu gạch ngang
    Không thể viết kiểu DEFINE MY-FN..., vì Rust tách token ở dấu gạch ngang
    Khác biệt nhỏ thôi, nhưng không thể dán nguyên các đoạn mã Lisp thật vào mà phải đổi toàn bộ thành dấu gạch dưới. Không biết triển khai này có giống vậy không

    • Hiện tại mọi atom đều được giả định là định danh Rust. Vì như vậy dễ triển khai hơn, có thể khớp bằng $x:ident, nên không hỗ trợ dấu gạch ngang trong atom
      Thay vào đó có lẽ có thể khớp theo kiểu $x:ident $(- $y:ident)*. Một vài chi tiết ở các nhánh macro sẽ phải đổi, nhưng có vẻ khả thi
    • Có vẻ không vấn đề gì mà? DEFINE MYᜭFN... hoạt động tốt

  • Giá mà có một triển khai Lisp dựa trên Rust được hỗ trợ tốt, chứ không chỉ macro
    Tôi tò mò nếu xây trên Rust thì sẽ giữ được hay đánh mất bao nhiêu tính an toàn bộ nhớ. Liệu có thể tận dụng borrow checker theo cách hợp lý không?

    • Một số compiler Lisp như SBCL cũng có thể thực hiện kiểm tra kiểu tại thời điểm biên dịch rộng hơn, nhưng thông tin đó phải do lập trình viên cung cấp, và thường giống một phần của giai đoạn tối ưu hóa hơn là phát triển tiệm tiến hằng ngày
      Lisp thường được định nghĩa bởi tính động, và kiểm tra kiểu lúc chạy là một phần lớn. Nếu bắt lập trình viên phải bận tâm trước về cách quản lý đối tượng, điều đó sẽ xung đột với mức tự do và khả năng biểu đạt mà người ta kỳ vọng ở hệ thống như vậy
      Bù lại, bản thân compiler có thể tương đối đơn giản. Mã thông thường không có khai báo bổ sung mặc định là an toàn, và trong máy ảo bytecode như CLISP hoặc các Lisp machine có kiểm tra kiểu bằng phần cứng, có thể bỏ qua các khai báo đó mà vẫn luôn an toàn
      SBCL biên dịch mã khá nhanh, và tôi nghe nói các triển khai khác còn nhanh hơn. Ngược lại, compiler Rust có khả năng cao hơn trong việc giới thiệu khái niệm thrashing cho các lập trình viên trẻ
      Tôi cho rằng hai thế giới này, trái với ấn tượng ban đầu, khó tương thích với nhau. Lisp về bản chất là ngôn ngữ tiêu biểu cho triết lý “The Right Thing”, còn C là ngôn ngữ “Worse is Better”. Rust không thuộc cả hai, và có vẻ là một thứ hoàn toàn khác đến mức cần một cái tên mới phản ánh các đặc tính xấu của cả hai triết lý
      Nói vậy không phải để hạ thấp bài gốc; đây vẫn là một màn hack rất hay
    • Steel trông khá ổn: https://github.com/mattwparas/steel
      Cũng có các Lisp khác nữa (https://github.com/alilleybrinker/langs-in-rust). Chỉ là có vẻ chúng được bảo trì kém tích cực hơn

  • Làm cái này rất vui, và tôi cũng học được rằng rust-analyser không xử lý nổi macro tạo ra hàng triệu token

  • Có lẽ mọi người đều nên reo lên “thú vị thật”, nhưng mỗi lần thấy những thứ như thế này, tôi lại thấy ghét việc Rust có thể triển khai được chúng
    Rust vốn dĩ đã không phải là một ngôn ngữ đơn giản, nhưng có vẻ nó đã trở thành thứ khó kiểm soát hơn rất nhiều so với ban đầu

    • Tôi đồng ý rằng Rust không phải là ngôn ngữ đơn giản
      Nhưng tôi không hiểu lắm vì sao việc này khả thi lại khiến bạn ghét. Hệ thống macro có thể sinh ra mã phức tạp gần như vô hạn, nhưng việc triển khai một Lisp được sandbox bằng macro có phải là ví dụ mạnh cho thấy Rust đã khó quản lý hơn so với thời đầu hay không thì tôi không chắc
      Mặt khác, vì hệ thống kiểu của Rust là Turing-complete giống template C++ hay hệ thống kiểu Haskell, tôi cũng muốn xem một Lisp được triển khai theo cách đó
    • Tôi phản đối mạnh điểm đó. Nhóm Rust liên tục làm ngôn ngữ dễ dùng hơn bằng cách gỡ bỏ ràng buộc và khiến các tính năng trực giao hơn
      Ví dụ tiêu biểu là non-lexical lifetimes, impl Trait ở vị trí trả về, và async trait. Trước 1.0 còn có tham chiếu GC tích hợp với cú pháp đặc biệt, nhưng những tính năng như vậy đã bị loại bỏ
    • Thay đổi lớn thực chất duy nhất sau 1.0 là async. Nếu muốn sống không cần async thì hoàn toàn có thể chọn như vậy, và đó là một phần hoàn toàn tùy chọn của ngôn ngữ
      Nếu bạn muốn một ngôn ngữ lấy sự đơn giản làm nguyên tắc, thì Rust vốn chưa bao giờ là ngôn ngữ như thế, và có nhiều lựa chọn khác
    • Thật ra để làm được những thứ như thế này chỉ cần rất ít. Tôi nghĩ ngay cả macro C, vốn được xem là đơn giản, cũng có thể làm được
      Tôi đã kiểm tra rồi, và tôi thắng vụ cá cược này: https://github.com/kchanqvq/CSP
    • Chẳng phải macro lúc nào cũng vừa rất mạnh vừa rắc rối sao? Tôi sẽ không tính phần macro vào độ phức tạp của ngôn ngữ
      Đặc biệt là khi nói về phía “viết” macro; tôi xem nó gần như một tính năng bổ sung, có thể dùng hoặc không

  • Ồ, cái này dùng macro_rules cơ à

  • Nhưng chẳng phải người ta từng nói C++ không phải là ngôn ngữ bình thường vì template của nó là Turing-complete sao?

    • Chỉ cần biết một chút về C++ cũng thấy nó không phải ngôn ngữ bình thường rồi. Ít nhất macro của Rust không phải là thay thế văn bản theo nghĩa đen, đó là một bước tiến về phía ánh sáng
    • Turing-complete và Turing tarpit là hai chuyện khác nhau
      Hệ thống macro của Rust thuộc bên nào thì tôi không biết
    • Phát triển bằng template C++ là địa ngục. Rust ít nhất còn có macro_expand, và việc công cụ của Rust được làm tốt là điểm rất lớn

  • Không thể không nhắc đến Carp. Đó là một Lisp dùng borrow checking, kiểu như “Rust” của thế giới Lisp
    1: https://github.com/carp-lang/Carp