Frege có thực hiện tối ưu hóa cuộc gọi đuôi không?

Question

Các cuộc gọi đuôi được tối ưu hóa trong Frege. Tôi biết rằng có TCO không phải trong Java cũng không phải trong các ngôn ngữ biên dịch sang bytecode JVM như Clojure và Scala. Còn Frege thì sao?

Answer 1

Frege thực hiện Tối ưu hóa đệ quy đuôi bằng cách tạo ra các vòng lặp đơn giản.

Cuộc gọi đuôi chung được xử lý "bằng cách" thông qua sự lười biếng. Nếu trình biên dịch nhìn thấy một cuộc gọi đuôi đến một chức năng nghi ngờ được biết đến là (gián tiếp) đệ quy, một kết quả lười biếng (một mảnh) được trả về. Do đó, gánh nặng thực sự của việc gọi hàm đó nằm với người gọi. Bằng cách này, ngăn xếp có chiều sâu phụ thuộc vào dữ liệu được tránh.

Điều đó đang được nói, độ sâu ngăn xếp tĩnh là do bản chất sâu hơn trong ngôn ngữ chức năng hơn trong Java. Do đó, một số chương trình sẽ cần phải có một ngăn xếp lớn hơn (tức là với -Xss1m).

Có trường hợp bệnh lý, nơi khối lớn được xây dựng và khi chúng được đánh giá, tràn ngăn xếp sẽ xảy ra. Một ví dụ khét tiếng là hàm foldl (cùng một vấn đề như trong Haskell). Do đó, nếp gấp tiêu chuẩn trong Frege là gấp, mà là đệ quy đuôi và nghiêm ngặt trong ắc quy và do đó làm việc trong không gian ngăn xếp liên tục (như Haskells foldl ').

Các chương trình sau đây nên không stack overflow nhưng print "false" sau 2 hoặc 3s:

module Test 
    -- inline (odd) 
    where 

even 0 = true 
even 1 = false 
even n = odd (pred n) 

odd n = even (pred n) 

main args = println (even 123_456_789) 

này hoạt động như sau: println phải có giá trị để in, vì vậy cố gắng để đánh giá (ngay cả n). Nhưng tất cả nó được là một mảnh để (lẻ (pred n)). Do đó nó cố gắng để đánh giá thunk này, mà được một thunk để (thậm chí (pred (pred n))). thậm chí phải đánh giá (pred (pred n)) để xem đối số là 0 hay 1, trước khi trả về một đoạn khác (lẻ (pred (n-2)) trong đó n-2 đã được đánh giá. ở cấp độ JVM) được thực hiện từ bên trong println.Không có lúc nào thực sự gọi lẻ, hoặc ngược lại.

Nếu một chỉ thị không trực tiếp, một phiên bản có đuôi đệ quy, và kết quả thu được mười lần . nhanh

Không cần phải nói, thuật toán vụng về này chỉ dành cho trình diễn -. Thông thường người ta sẽ kiểm tra thậm chí-Ness với một thao tác chút

Dưới đây là một phiên bản khác, đó là bệnh lý và sẽ stack overflo w:

even 0 = true 
even 1 = false 
even n = not . odd $ n 
odd = even . pred 

Vấn đề là ở đây mà not là tiếng gọi đuôi và nó là nghiêm ngặt trong đối số của nó (ví dụ, để phủ nhận điều gì đó, trước tiên bạn phải có một cái gì đó). Do đó, khi tính toán even n, thì not phải đánh giá đầy đủ odd n, do đó, phải đánh giá đầy đủ even (pred n) và do đó, nó sẽ có khung 2 ngăn xếp * n.

Thật không may, điều này sẽ không thay đổi, ngay cả khi JVM có cuộc gọi đuôi thích hợp một ngày. Lý do là đệ quy trong đối số của một chức năng nghiêm ngặt.

Answer 2

@Landei TCO không được hỗ trợ đầy đủ trong Scala ... hãy thử cái này.

def foo() { def bar() { println("bar"); foo() }; println("foo"); bar() } 

Lưu ý, tôi không có đủ danh tiếng để nhận xét trực tiếp. Tìm nhận xét Tôi đang trả lời trong phần bình luận của câu hỏi gốc.