Làm thế nào để định nghĩa vĩ mô đệ quy được đánh giá

Question

này định nghĩa đệ quy của một vĩ mô hiện những gì nó cần (tổng các số nguyên từ 1 đến n):

(defmacro sum-int-seq (n) 
    `(cond 
    ((equal 0 ,n) 0) 
    (t (+ ,n (sum-int-seq (- ,n 1)))))) 

Ví dụ (sum-int-seq 5) cho 15.

Nhưng tại sao nó công việc? Khi macro được mở rộng, tôi nhận được thông tin này:

(macroexpand '(sum-int-seq 5)) 
(IF (EQUAL 0 5) 0 (+ 5 (SUM-INT-SEQ (- 5 1)))) 

Nhưng vì tổng hợp-macro là macro nên việc đánh giá macro sẽ trở thành vòng lặp vô hạn. Liệu trình biên dịch tạo ra một hàm đệ quy thay thế? Nếu định nghĩa này tạo ra một hàm đệ quy thì có cách nào để định nghĩa các macro một cách đệ quy không?

(Đây là một ví dụ ngớ ngẩn vì lợi ích ngắn gọn, hàm sẽ tất nhiên làm việc tốt hơn cho việc này)

Answer 1

Ví dụ của bạn không hoạt động.

Nó có thể hoạt động trong thông dịch viên. Nhưng với trình biên dịch, bạn sẽ thấy một vòng lặp vô tận trong quá trình biên dịch.

CL-USER 23 > (defun test (foo) 
       (sum-int-seq 5)) 
TEST 

Hãy sử dụng LispWorks thông dịch viên:

CL-USER 24 > (test :foo) 
15 

Hãy thử biên dịch các chức năng:

CL-USER 25 > (compile 'test) 

Stack overflow (stack size 15997). 
    1 (continue) Extend stack by 50%. 
    2 Extend stack by 300%. 
    3 (abort) Return to level 0. 
    4 Return to top loop level 0. 

Type :b for backtrace or :c <option number> to proceed. 
Type :bug-form "<subject>" for a bug report template or :? for other options. 

Vì vậy, bây giờ câu hỏi tiếp theo: tại sao nó làm việc trong các thông dịch viên, nhưng trình biên dịch không thể biên dịch nó?

OK, tôi sẽ giải thích.

Hãy nhìn vào thông dịch viên trước.

• nó thấy (sum-int-seq 5).
• macro này sẽ mở rộng nó thành (COND ((EQUAL 0 5) 0) (T (+ 5 (SUM-INT-SEQ (- 5 1))))).
• rồi đánh giá biểu mẫu ở trên. Nó xác định rằng nó cần phải tính toán (+ 5 (SUM-INT-SEQ (- 5 1))). Cho rằng nó cần phải macroexpand (SUM-INT-SEQ (- 5 1)).
• cuối cùng nó sẽ mở rộng thành một cái gì đó như (cond ((EQUAL 0 (- (- (- (- (- 5 1) 1) 1) 1) 1)) 0) .... Mà sau đó sẽ trở về 0 và tính toán có thể sử dụng kết quả này và thêm các điều khoản khác vào nó.

Trình thông dịch nhận mã, đánh giá những gì có thể và macro mở rộng nếu cần. Mã được tạo sau đó được đánh giá hoặc macroexpanded. Và cứ thế.

Bây giờ, hãy xem trình biên dịch.

• nó thấy (sum-int-seq 5) và macro mở rộng nó thành (COND ((EQUAL 0 5) 0) (T (+ 5 (SUM-INT-SEQ (- 5 1))))).
• giờ việc mở rộng macro sẽ được thực hiện trên các biểu mẫu con, cuối cùng.
• trình biên dịch sẽ macroexpand (SUM-INT-SEQ (- 5 1)). lưu ý rằng mã không bao giờ được đánh giá, chỉ được mở rộng.
• trình biên dịch sẽ macroexpand (SUM-INT-SEQ (- (- 5 1) 1)) v.v. cuối cùng bạn sẽ thấy tràn ngăn xếp.

Trình biên dịch sẽ chuyển tiếp (đệ quy biên dịch/mở rộng) mã. Nó có thể không thực thi mã (trừ khi nó tối ưu hóa hoặc macro thực sự đánh giá nó một cách rõ ràng).

Đối với macro đệ quy, bạn cần phải thực sự đếm ngược. Nếu bạn đánh giá bên trong macro, thì một cái gì đó như (sum-int-seq 5) có thể được thực hiện. Nhưng đối với (defun foo (n) (sum-int-seq n)) điều này là vô vọng, vì trình biên dịch không biết giá trị của n là gì.

Answer 2

Mở rộng một macro tạo ra mã Lisp mà sau đó được đánh giá. Việc gọi một hàm sẽ chuyển hướng luồng thực thi thành một bản sao của mã lisp đã tồn tại từ trước, sau đó nó chạy. Ngoài ra, cả hai đều khá giống nhau, và đệ quy hoạt động theo cùng một cách. Cụ thể, việc mở rộng macro dừng lại vì lý do tương tự mà chức năng đệ quy bằng văn bản đúng dừng lại: bởi vì có điều kiện chấm dứt, và phép chuyển đổi giữa một cuộc gọi và lần tiếp theo được viết để thực sự đạt được điều kiện này. Nếu nó không đạt được, việc mở rộng macro sẽ nhập vào một vòng lặp, giống như một hàm đệ quy không đúng.

Answer 3

Để trả lời của Kilan tôi muốn thêm, macroexpand không phải tạo ra một bản mở rộng đầy đủ của tất cả các macro trong biểu mẫu của bạn, cho đến khi không còn macro nữa. rằng nó đánh giá các hình thức toàn bộ cho đến khi nó không phải là một vĩ mô (trong trường hợp của bạn nó dừng lại tại if). Và trong quá trình biên dịch, tất cả các macro được mở rộng, như thể macroexpand được áp dụng cho từng phần tử của cây nguồn, không chỉ với gốc của nó.

Answer 4

Một điều khác cần thêm: trong ví dụ của bạn, sự xuất hiện của sum-int-seq bên trong macro nằm bên trong biểu thức được trích dẫn, vì vậy nó không được mở rộng khi macro được đánh giá. Nó chỉ là dữ liệu cho đến khi macro được gọi. Và vì nó được lồng trong một cond, tại thời gian chạy, macro bên trong chỉ được gọi khi điều kiện là đúng, giống như trong một hàm bình thường.

Answer 5

Dưới đây là một thực hiện mà không làm việc:

(defmacro sum-int-seq (n) 
    (cond 
    ((equal 0 n) `0) 
    (t `(+ ,n (sum-int-seq ,(- n 1)))))) 

Có thể viết một macro đệ quy, nhưng (như đã đề cập), việc mở rộng phải có khả năng để đạt trường hợp cơ sở tại thời gian biên dịch. Vì vậy, các giá trị của tất cả các đối số được truyền cho macro phải được biết tại thời gian biên dịch.

(sum-int-seq 5) 

trình, nhưng

(sum-int-seq n) 

Liệu không.