Chuyển đổi một hàm để sử dụng đệ quy đuôi - một nghiên cứu chính thức

Question

Có ai đã viết một bài báo chính thức mô tả một phương thức để (tự động) chuyển đổi các hàm để đệ quy đuôi không? Tôi đang tìm kiếm một điều trị chính thức cấp đại học bao gồm các hạn chế (các loại chức năng có thể được chuyển đổi), các thủ tục chuyển đổi, và, nếu có thể, bằng chứng về tính chính xác? Ví dụ trong Haskell sẽ là tiền thưởng.

Answer 1

phương pháp (tự động) chuyển đổi các hàm thành đuôi đệ quy?

Vì vậy, có hai phần như sau:

• thừa nhận rằng một hàm đệ quy định có thể được chuyển đổi sang một hình thức đệ quy đuôi và làm cho rằng biến đổi
• đuôi thực hiện các cuộc gọi trong một cách hiệu quả, vì vậy chuyển đổi có giá trị trong khi.

Chuyển đổi đệ quy vào đuôi đệ quy

Nó xuất hiện phía trước tương đối thẳng để nhận ra đuôi định nghĩa đệ quy cú pháp. Sau khi tất cả, 'đuôi đệ quy' chỉ có nghĩa là cuộc gọi xuất hiện cú pháp trong đuôi của biểu thức.

Ví dụ: các chủ đề Đề án mô tả:

chỉ biên dịch các cuộc gọi tự thích hợp là nhảy không được suôn sẻ để đạt được đầy đủ đệ quy đuôi. Thay vào đó, chúng tôi phân chia cú pháp tất cả các vị trí phụ biểu thức trong ngôn ngữ nguồn thành hai lớp: đuôi (hoặc giảm) vị trí và vị trí dự án con. Trong biểu thức đơn giản (nếu predicate thay thế hậu quả), thì predicate là vị trí con của , trong khi cả hai kết quả và thay thế đều ở vị trí giảm. Khái niệm cú pháp này có thể dễ dàng được mở rộng đến các biểu thức con lồng nhau tùy ý.

• Compiling Higher-Order Languages into Fully Tail-Recursive Portable C

Chuyển đổi chức năng vào đuôi gọi

Phần khó khăn của câu hỏi của bạn là tối ưu hóa cho việc xác định và chuyển ứng cử viên tính toán đệ quy vào những đệ quy đuôi.

Một tham chiếu là trong GHC, sử dụng nội tuyến và một loạt các quy tắc đơn giản hóa để thu gọn các cuộc gọi đệ quy, cho đến khi cấu trúc đệ quy đuôi cơ bản của chúng vẫn còn.

• Secrets of the GHC inliner

Tail Loại bỏ

Một khi bạn có các chức năng của bạn trong một hình thức đuôi-đệ quy Call, bạn muốn có mà thực hiện effiicently. Nếu bạn có thể tạo ra một vòng lặp, đó là một khởi đầu tốt.Nếu máy mục tiêu của bạn không, thì tail call elimination "sẽ cần một vài thủ thuật. Để báo Odersky và Schinz, trích dẫn dưới đây,

kỹ thuật khác nhau đã được đưa ra trong những năm qua để loại bỏ chung (và không chỉ đệ quy) đuôi gọi, chủ yếu là cho các trình biên dịch nhắm mục tiêu C.

... đưa toàn bộ chương trình trong một chức năng lớn và để mô phỏng chức năng cuộc gọi bằng nhảy trực tiếp hoặc chuyển sang câu lệnh bên trong hàm này.

... một kỹ thuật phổ biến là sử dụng tấm bạt lò xo. là hàm bên ngoài lặp đi lặp lại gọi hàm bên trong. Mỗi lần hàm bên trong muốn đuôi gọi hàm khác, nó không gọi nó trực tiếp nhưng chỉ đơn giản là trả về danh tính của nó (ví dụ như đóng cửa) cho tấm bạt lò xo, sau đó tự gọi số . Tăng trưởng stack không giới hạn do đó tránh được, nhưng một số hiệu suất là chắc chắn bị mất, chủ yếu là bởi vì tất cả các cuộc gọi được thực hiện bởi tấm bạt lò xo là các cuộc gọi đến các chức năng không xác định tĩnh.

kỹ thuật khác là Henry Baker “Cheney trên MTA” Với kỹ thuật của anh, chương trình đầu tiên đã được chuyển đổi sang tiếp tục đi qua phong cách (CPS), do đó chuyển tất cả các cuộc gọi vào các cuộc gọi đuôi, và sau đó có thể biên soạn như thường lệ. Vào thời gian chạy, khi ngăn xếp sắp tràn, việc tiếp tục hiện tại được xây dựng và trả về (hoặc kéo dài) đến tấm bạt lò xo “đang chờ” ở cuối ngăn xếp cuộc gọi.

• Tail call elimination on the Java Virtual Machine, Michel Schinz Martin Odersky năm 2001

• Henry G. Baker, Jr. Nhược điểm không nên Nhược điểm đối số của nó, phần II: Cheney trên phiên bản, Tháng 1 năm 1994 Dự thảo MTA.

Answer 2

Thủy ngân chứa một vài tối ưu hóa để tự động làm mọi thứ có tính đệ quy đuôi. (Mercury là một ngôn ngữ lập trình logic thực thi, vì vậy nó nói về các biến vị ngữ hơn là các hàm, nhưng nhiều ý tưởng tương tự áp dụng cho các chương trình của Mercury như các hàm Haskell. Một khác biệt lớn hơn nhiều so với logic hơn là chức năng. nghiêm ngặt hơn là lười biếng)

"Giới thiệu tích lũy" tạo ra các phiên bản chuyên biệt của các biến vị ngữ có tham số tích lũy thêm để cho phép các hoạt động liên kết được di chuyển trước cuộc gọi đệ quy. Rõ ràng việc tối ưu hóa này không nhất thiết dẫn đến các biến vị ngữ đệ quy đuôi, nhưng thường dẫn đến một biểu mẫu có thể được tối ưu hóa theo tối ưu hóa thứ hai:

"Last call modulo constructors" về cơ bản cho phép gọi đệ quy chỉ bởi các hàm dựng được viết lại sao cho giá trị được xây dựng trước tiên có chứa một "lỗ" và sau đó gọi đệ quy trả về đầu ra của nó trực tiếp vào địa chỉ bộ nhớ của "lỗ" thay vì sử dụng quy ước trả về giá trị bình thường. Tôi tin rằng Haskell sẽ nhận được tối ưu hóa này miễn phí chỉ đơn giản là do sự lười biếng, tuy nhiên.

Cả hai tối ưu hóa này được mô tả trong bài báo Making Mercury programs tail recursive.