Lisp được hiện thực bằng macro Rust

 (github.com/RyanWelly)
1 điểm bởi GN⁺ 2024-09-15 | Chưa có bình luận nào. | Chia sẻ qua WhatsApp

lisp-in-rs-macros

Một trình thông dịch Lisp đơn giản với lexical scope hoạt động hoàn chỉnh, được viết hoàn toàn bằng macro khai báo của Rust. Macro lisp! mở rộng thành một giá trị Lisp được tính toán bởi mã và chuyển nó thành chuỗi. Ví dụ, lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) sẽ mở rộng thành chuỗi "A", và toàn bộ phép tính diễn ra ở thời điểm biên dịch khi rustc mở rộng macro.

Vì sao điều này quan trọng

Đây là một trình thông dịch Lisp được viết bằng macro của Rust, rất thú vị. Ngoài ra, nó được viết trong chưa đến 250 dòng nên rất cô đọng.

Ví dụ

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))
); // in ra "hello there" và "TRUE"

Một ví dụ thú vị khác là quine:

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

Đoạn mã này tự đánh giá chính nó.

Đệ quy

Lisp này hiện không hỗ trợ dạng đệ quy tường minh. May mắn là không cần đệ quy tường minh, chỉ cần lambda là đủ. Có thể viết một hàm đơn giản để nối hai danh sách:

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

Kết quả là "(A B C D)". Hàm append không nhắc đến append trong phần thân, nhưng vẫn có thể tự gọi một cách đệ quy.

Lưu ý khi sử dụng

  • Macro lisp! chỉ đánh giá một biểu thức duy nhất. Nếu muốn đánh giá nhiều biểu thức, cần dùng (PROGN expr1 expr2 expr3).
  • Dạng DISPLAY tạo ra một câu lệnh println!("{}", stringify!(...)) sau khi đánh giá một biểu thức duy nhất để in ra phiên bản chuỗi của token.
  • Danh sách rỗng không tự đánh giá; để lấy giá trị danh sách rỗng, cần dùng NIL hoặc (QUOTE ()).
  • Danh sách chấm không được hỗ trợ, và cons giả định đối số cuối cùng là một danh sách.
  • Dạng define có thể dùng ở bất kỳ đâu và được đánh giá thành danh sách rỗng, nhưng không hỗ trợ đệ quy.
  • TRUE là nguyên tử tự đánh giá duy nhất, không phải là một hàm.

Các dạng được hỗ trợ

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

Trình thông dịch meta-circular

Sau đây là một trình thông dịch Lisp được viết bằng chính 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)
);

Đoạn mã này hoạt động, nhưng nếu thử đánh giá ((lambda (X) X) (quote a)) trong trình thông dịch, nó sẽ mất hơn 30 giây và tạo ra hơn một triệu token. Đệ quy dùng y combinator tường minh không hiệu quả trong trường hợp này. Để giải quyết, cần bổ sung primitive đệ quy tường minh. Để có phần giải thích rất hay về cách viết một meta-circular evaluator, hãy xem "Roots of Lisp" của Paul Graham.

Giải thích kỹ thuật

Xem EXPLANATION.md. Macro mô phỏng máy SECD, một abstract machine đơn giản dựa trên stack để đánh giá biểu thức lambda calculus.

Tài liệu hay

  • "Functional Programming: Application and Implementation" của Peter Henderson
  • "A functional correspondence between evaluators and abstract machines." (2003) của Mads Sig Ager và cộng sự
  • "The Implementation of Functional Programming Languages" của Simon Peyton Jones
  • Mọi bài viết về Lisp trên blog của Matt Might (https://matt.might.net)

TODO

  • thêm letrec
  • thêm định nghĩa đệ quy

Tóm tắt của GN⁺

  • Trình thông dịch Lisp được viết bằng macro Rust rất thú vị và cung cấp tính năng mạnh mẽ với mã nguồn cô đọng.
  • Dù không hỗ trợ đệ quy tường minh, vẫn có thể hiện thực đệ quy thông qua lambda.
  • Trình thông dịch meta-circular không hiệu quả, nên cần thêm primitive đệ quy tường minh.
  • "Roots of Lisp" của Paul Graham là tài liệu rất tốt để hiểu về meta-circular evaluator.
  • Các dự án khác có chức năng tương tự có thể là trình thông dịch Scheme hoặc các biến thể Lisp khác.

Bài viết liên quan

Chưa có bình luận nào.

Chưa có bình luận nào.