Ngôn ngữ Python homoiconic

 (aljamal.substack.com)
2 điểm bởi GN⁺ 2024-05-13 | 2 bình luận | Chia sẻ qua WhatsApp
  • Tính homoiconic của Lisp là đặc tính xử lý mã và dữ liệu dưới cùng một hình thức; khi chuyển bản kinh điển “Lisp in Lisp” sang Python, ý tưởng này hiện ra trong một cú pháp quen thuộc hơn
  • Ban đầu Lisp có cả M-expression là biểu diễn mã và S-expression là biểu diễn dữ liệu; “Lisp in Lisp” triển khai S-expression Lisp bằng M-expression
  • Phiên bản Python biểu diễn S-expression bằng list của Python, và chuyển M-expression thành lời gọi hàm cùng câu điều kiện để xây dựng trình thông dịch mà không cần parser riêng
  • Trình thông dịch đầu tiên được xây trên các primitive thao tác list như atom, eq, car, cdr, cons, append; để hỗ trợ lambda, có thêm assoc, pairlis và danh sách môi trường
  • eval nhận cả biểu thức và môi trường để xử lý ràng buộc biến, đồng thời dùng pairlis và assoc để liên kết tham số với giá trị theo kiểu dynamic scope

Sự hợp nhất giữa mã và dữ liệu mà Lisp đã cho thấy

  • Lisp để lại nhiều ý tưởng vẫn còn giá trị sau nhiều thập kỷ thông qua bài báo về Lisp của John McCarthy vào đầu thập niên 1960 và sổ tay Lisp 1.5
  • Trong đó, điểm cốt lõi là tính homoiconic
    • Trong các ngôn ngữ thông thường, mã được hiểu là chuỗi các phép toán tác động lên dữ liệu
    • Lisp xử lý mã và dữ liệu dưới cùng một hình thức, làm mờ ranh giới giữa toán tử và toán hạng
  • Alan Kay gọi đoạn mã “Lisp in Lisp” ở cuối trang 13 của sổ tay Lisp 1.5 là “Maxwell's Equations of Software”
    • Trích dẫn này hàm ý rằng vài dòng mã ấy là một sự khai sáng lớn, vì chúng chứa đựng cả thế giới lập trình

Cách chuyển “Lisp in Lisp” sang Python

  • Mục tiêu là viết lại đoạn mã “Lisp in Lisp” kinh điển bằng Python, đồng thời giữ tối đa tinh thần của mã gốc
  • Lisp có hai cách biểu diễn cú pháp
    • M-expression: biểu diễn mã, viết tắt của meta
    • S-expression: biểu diễn dữ liệu, viết tắt của symbolic
    • Hai biểu diễn này tương đương nhau về mặt ngữ nghĩa
  • Mã “Lisp in Lisp” hiện có được viết bằng M-expression để triển khai S-expression Lisp
  • Trong bản triển khai Python, S-expression của Lisp được biểu diễn bằng list của Python
    • Lisp là viết tắt của “List Processing”, và hoạt động xoay quanh một cấu trúc dữ liệu duy nhất là list
    • List của Python được dùng như một biểu diễn phù hợp để mô phỏng S-expression của Lisp
  • M-expression được dịch sang các cấu trúc mã như lời gọi hàm và câu điều kiện của Python
    • Nhờ ánh xạ này, có thể tạo trình thông dịch mà không cần xử lý chuỗi hay triển khai parser riêng

Trình thông dịch đầu tiên được tạo bằng các primitive thao tác list

  • Việc triển khai Lisp cần một số hàm cơ bản được cung cấp từ bên ngoài ngôn ngữ
  • Các primitive thao tác list được dùng trong bản triển khai Python như sau
    • atom(x): kiểm tra x có phải là list hay không
    • eq(x,y): kiểm tra x và y có giống nhau hay không
    • car(x): phần tử đầu tiên của list
    • cdr(x): phần còn lại của list
    • cons(x,y): gắn một atom vào list
    • append(x,y): nối hai list
  • Ngoại trừ một vài primitive đệ quy, có thể dùng Llama3-70b trên Groq để nhanh chóng tạo một trình thông dịch chạy được một tập con của mã “Lisp in Lisp”
  • Trong ví dụ, list của Python hoạt động như S-expression
  • Toàn bộ mã được cung cấp tại github gists

Mở rộng cho lambda và đệ quy

  • Bản triển khai đầu tiên còn thiếu một tính năng quan trọng là lambda
    • lambda là cách chính để định nghĩa và gọi hàm ẩn danh trong Lisp
    • Trong Lisp, nếu không có lambda thì không thể triển khai đệ quy
    • Không có đệ quy thì không đạt được Turing-completeness, tiêu chuẩn tối thiểu để tính được mọi thứ có thể tính toán
  • Để thêm lambda, assoc(x,y) và pairlis(x,y) được bổ sung
    • assoc(x,y) là tra cứu khóa/giá trị được triển khai bằng list, sử dụng association list
    • pairlis(x,y) ghép hai list lại với nhau giống zip(x,y) của Python
  • Lisp ban đầu phải xử lý cả thao tác quét tuyến tính đơn giản bằng đệ quy
    • Vì Lisp ban đầu không có vòng lặp
    • Trong bản dịch sang Python, assoc và pairlis có thể được biểu diễn gọn hơn bằng list comprehension
  • Khi xử lý COND, evcon của Lisp gốc được dịch thành vòng lặp; trong xử lý LAMBDA, cách tương tự cũng được áp dụng cho evlis

Danh sách môi trường và dynamic scope

  • Hàm eval của Lisp ban đầu nhận hai đối số
    • Đối số thứ nhất là S-expression cần đánh giá
    • Đối số thứ hai là danh sách môi trường gồm các cặp khóa/giá trị
  • Môi trường duy trì ràng buộc biến trong xử lý LAMBDA
    • Nếu hàm có biến x và dữ liệu được truyền vào, pairlis sẽ ghép symbol x với dữ liệu đó
    • Giá trị đã ghép được lưu hoặc thêm vào danh sách môi trường
    • Khi cần x, assoc sẽ tìm trong môi trường và thay ngược lại vào biểu thức
  • Cách ràng buộc này được gọi là dynamic scope
  • Bản triển khai cuối cùng là dạng chuyển “Lisp in Lisp” ban đầu sang Python, và ví dụ cuối bao gồm cả việc chạy lambda

Bài viết liên quan

2 bình luận

 
GN⁺ 2024-05-13
Ý kiến trên Hacker News

  • Nếu bạn quan tâm đến một Lisp dạng scripting phong cách Python, đơn giản và nhanh, đáng xem qua các ngôn ngữ kiểu Clojure như Hy và Janet

    1. Hy(https://hylang.org/): biên dịch thành bytecode Python, thường chậm hơn Python nhưng tương thích với mọi thư viện Python
    2. Janet(https://janet-lang.org/): một máy ảo nhúng cực nhẹ kiểu Lua, khoảng 1MB; trong các phép toán tương tự thì nhanh hơn Python khoảng 2 lần và tương tác với C rất dễ
    • Nếu nói về scripting phong cách Python nhanh, còn có https://github.com/ciel-lang/ciel, một Common Lisp “kèm pin”
      Được cung cấp dưới dạng binary khởi động nhanh, và cũng bao gồm các thư viện cho tác vụ hằng ngày
      Với hướng CL↔Python, cũng đáng tham khảo https://github.com/CodyReichert/awesome-cl?tab=readme-ov-fil...
    • Hy chậm hơn Python ư? Ít nhất là về thời gian chạy thì không nên như vậy
      Tôi là maintainer của Hy, và nếu thấy khác biệt hiệu năng có ý nghĩa thì đó là bug
      1. Basilisp(https://github.com/basilisp-lang/basilisp): “một phương ngữ Lisp tương thích kiểu Clojure-ish, nhắm tới Python 3.8+”
    • Nghe có thể như tùy hứng, nhưng Lisp luôn cho tôi cảm giác là một ngôn ngữ dễ gây tranh cãi vì bắt buộc phải có các dấu ngoặc bao quanh
      M-expression tránh được cái bẫy này, nên tôi tò mò liệu đã từng có ngôn ngữ thực tế nào không yêu cầu các dấu ngoặc như vậy mà vẫn giữ được homoiconicity và sự thanh nhã về mặt khái niệm của Lisp chưa
    • https://github.com/yaml/yamlscript
      Chính xác là thứ bạn đang nghĩ tới. Phần mô tả cũng rất thẳng thắn: “Program in YAML”
      Gần như không cần nói thêm gì nữa

  • Khoan đã, đây chẳng phải chỉ là Lisp được triển khai bằng Python sao?
    Có vẻ không phải là Python homoiconic như tiêu đề gợi ý; tôi đang bỏ lỡ điều gì à?

    • Theo định luật thứ mười của Greenspun thì đúng là vậy: https://en.m.wikipedia.org/wiki/Greenspun's_tenth_rule
    • Tôi cũng đã khá hào hứng vì tưởng đây là một Python homoiconic có thể khiến đồng nghiệp dùng Lisp mà không cần thuyết phục họ chấp nhận Lisp, nhưng không phải; nó chỉ là Lisp thôi
    • Trông có vẻ vậy. Tôi tò mò vì muốn thấy Python homoiconic này, nhưng cũng không chắc liệu nó có khả thi không
      Để làm vậy, cú pháp Python sẽ phải được cấu thành từ tuple, list, dict, và trình thông dịch sẽ phải đánh giá trực tiếp chúng
    • Khác biệt là gì?

  • Một ngôn ngữ hàm khác có thể triển khai gọn bằng Python là Binary Lambda Calculus
    Phần lớn mã xử lý mô hình nhập/xuất thuần của BLC; với việc tra cứu biến, nó dùng chỉ số de Bruijn để index vào mảng môi trường thay vì danh sách kết hợp
    Cùng trang đó còn có triển khai bằng 9 ngôn ngữ khác, và self-interpreter của BLC là gọn nhất với 232 bit (29 byte), bao gồm cả parser và tokenizer
    [1] https://rosettacode.org/wiki/Universal_Lambda_Machine#Python

  • Môn nền tảng lập trình của MIT bắt tất cả sinh viên viết trình thông dịch Lisp bằng Python
    Đó là dấu vết từ thời trước khi môn học này thực sự được dạy bằng Lisp
    https://py.mit.edu/spring24

    • Tương tự, môn tôi học ở đại học cũng yêu cầu triển khai một trình thông dịch Lisp cơ bản bằng Lisp

  • Tôi từng làm một thứ tương tự bằng list trong JS: https://github.com/andrelaszlo/js-lisp

  • Thật buồn cười mà cũng mỉa mai khi các ngôn ngữ hiện đại, sau hàng chục năm, lại tái khám phá những tính năng đáng kinh ngạc của Lisp
    Vài ngày trước, tôi đã bực mình vì một chương trình Python gọi API máy chủ tại nhà của tôi suốt 9 giờ rồi bị dừng. Đó là các lệnh gọi API tương tự nhau, gọi LLM với mẫu prompt đã định nghĩa sẵn và các ràng buộc ngữ pháp
    Trước khi chạy riêng các vòng lặp còn lại, tôi muốn lưu trạng thái chương trình rồi thoát, nhưng không tìm được cách sửa mã Python đang chạy hoặc xem các biến, nên cuối cùng mất toi 9 giờ làm việc
    Vài ngày sau tôi xem https://malisper.me/debugging-lisp-part-1-recompilation/, và rất ngạc nhiên khi biết Common Lisp đã tích hợp những tính năng như vậy vào ngôn ngữ từ hàng chục năm trước. Các tính năng khác như hệ thống macro mạnh nhất cũng tương tự

    • Việc các ngôn ngữ hiện đại sau hàng chục năm lại tái khám phá tính năng của Lisp không có gì đáng ngạc nhiên. Vì họ Lisp là những ngôn ngữ linh hoạt và giàu khả năng biểu đạt nhất
      Nhưng đó cũng chính là vấn đề. Khả năng biểu đạt quá mạnh
      Lisp luôn khiến tôi liên tưởng đến nghệ thuật thị giác đa chất liệu; tự do biểu đạt nghe có vẻ tốt, nhưng rốt cuộc tác phẩm thường kém hơn nghệ thuật đơn chất liệu truyền thống. Điều đó cho thấy ràng buộc của chất liệu cũng quan trọng không kém khả năng biểu đạt
    • Nếu muốn xem trạng thái ở một mức độ nào đó, có thể dùng Py-spy hoặc Pystack
      Hoặc cũng có https://github.com/malor/cpython-lldb
      Có thêm nhiều cách tại https://github.com/albertz/pydbattach/
    • Với một process chạy nhiều giờ, bạn nên lưu công việc xuống đĩa và sẵn sàng khởi động lại từ điểm đã bị ngắt
    • Không có exception nào được ném ra à?

  • Cách triển khai này là Python đồng hình ở chỗ nào?

  • Có Lisp nào có hệ thống kiểu giúp kiểm soát phần nào xu hướng Lisp trở nên khó đọc khi chương trình lớn dần không?
    Dù không phải hệ thống kiểu, tôi cũng tò mò liệu có yếu tố nào khác có thể kiềm chế đặc tính đó không
    Metaprogramming thật sự rất tuyệt, nhưng đôi khi nó đọc giống như thứ Haskell trừu tượng khó hiểu nhất từng thấy, mà thậm chí còn không có type signature làm kim chỉ nam
    Tôi xem hệ thống kiểu và linter là những công cụ tốt nhất để tự động thuần hóa mã, nhưng khó hình dung làm sao có thể kiềm chế xu hướng của các dự án Lisp mà không bó buộc chính lý do người ta chọn Lisp

    • Nếu nói Lisp có hệ thống kiểu thì tôi nghĩ đến Common Lisp
      SBCL, thứ gần như là chuẩn de facto, cũng có kiểm tra kiểu lúc compile khá tốt
      Ví dụ, nếu sau (declare (type String a b)) mà viết (+ a b), nó sẽ cảnh báo rằng kiểu suy ra của A là STRING trong khi lẽ ra phải là NUMBER
      Lý do lớn nhất khiến tôi chuyển từ Scheme sang CL là kiểm tra kiểu này, và sau đó tôi tiếp tục ở lại vì những tính năng nhỏ nhưng hay như restarts và continuable asserts
    • Hướng thân thiện và dễ tiếp cận có Typed Racket, còn hướng mạnh mẽ nhưng phức tạp có Shen
    • https://en.wikipedia.org/wiki/Dylan_(programming_language)

  • Nếu có Python hướng biểu thức thì nó sẽ tốt hơn Python hiện nay rất nhiều
    Bài này không đúng như điều tiêu đề ám chỉ, nhưng là phần giải thích tốt về Lisp

    • Python hướng biểu thức đơn giản sẽ không còn là Python nữa
      Dù vậy cũng không sao, nhưng “đặt biểu thức làm cú pháp hạng hai” là một lựa chọn khá căn bản và có chủ ý. Nó cũng là thiết kế nhằm gây khó cho các lập trình viên muốn viết kiểu “súp ngoặc”
      Vì vậy lambda: và := được cố tình làm thô vụng để hạn chế sử dụng, và cũng không thể viết hàm ẩn danh
      Python là ngôn ngữ nói rằng nếu muốn làm những việc thông minh, hãy làm bằng iterator chứ không phải bằng callable object

  • Tôi ước mọi thứ đều có kiểu phi cú pháp theo phong cách Lisp
    Với tôi như vậy tốt hơn, và may là trong CL rất dễ làm thế
 
kayws426 2024-05-13

Một phương ngữ Lisp được nhúng trong Python
https://hylang.org/