Các chương trình bằng các ngôn ngữ chức năng có nhiều khả năng có tràn ngăn xếp hơn không?

Question

Tôi bắt đầu học ocaml, và tôi thực sự đánh giá cao sức mạnh của đệ quy trong ngôn ngữ. Tuy nhiên, một điều mà tôi lo lắng là ngăn xếp tràn.

Nếu ocaml sử dụng ngăn xếp cho các cuộc gọi chức năng, cuối cùng nó sẽ không tràn ngăn xếp? Ví dụ: nếu tôi có chức năng sau:

let rec sum x = 
    if x > 1 then f(x - 1) + x 
    else x;; 

nó cuối cùng phải gây ra tràn ngăn xếp. Nếu tôi đã làm điều tương đương trong c + + (sử dụng đệ quy), tôi biết rằng nó sẽ tràn.

Vì vậy, câu hỏi của tôi là, có được xây dựng trong các biện pháp bảo vệ để ngăn chặn các ngôn ngữ chức năng tràn tràn ngăn xếp không? Nếu không, chúng không ít hữu ích như thế này, vì thuật toán tổng hợp ở trên, được viết theo kiểu thủ tục với vòng lặp for, có thể xử lý bất kỳ số nào (tràn số nguyên không liên quan)?

Answer 1

Tất cả (thực hiện phong nha ;-) ngôn ngữ chức năng tối ưu hóa đệ quy đuôi, nhưng đó không phải là những gì bạn đang làm ở đây, vì cuộc gọi đệ quy không phải là hoạt động LAST (nó cần phải được theo sau bởi việc bổ sung). Vì vậy, người ta sớm học cách sử dụng một hàm phụ trợ mà đuôi IS đệ quy (và lấy tổng số hiện tại được tích lũy làm đối số) để trình tối ưu hóa có thể thực hiện công việc của nó, tức là lưới cú pháp O'Caml có thể trong đó 'm gỉ:

let sum x = 
    aux(x)(0);; 

let rec aux x accum = 
    if x > 1 then aux(x - 1)(accum + x) 
    else (accum + x);; 

ở đây, tổng xảy ra như một cuộc tranh cãi với cuộc gọi đệ quy, tức là, trước khi đệ quy chính nó, và do đó đuôi tối ưu hóa có thể đá ở (vì đệ quy là điều cuối cùng mà cần phải xảy ra !).

Answer 2

Một số ngôn ngữ chức năng như Đề án chỉ định rằng tail recursionphải được tối ưu hóa để tương đương với lặp lại; do đó, một hàm đệ quy đuôi trong Đề án sẽ không bao giờ dẫn đến tràn ngăn xếp, bất kể nó lặp lại bao nhiêu lần (giả sử, tất nhiên, nó cũng không chấp nhận hoặc tham gia đệ quy lẫn nhau ở những nơi khác ngoài kết thúc).

Hầu hết các ngôn ngữ chức năng khác không yêu cầu đệ quy đuôi phải được triển khai hiệu quả; một số lựa chọn để làm như vậy, những người khác thì không, nhưng nó tương đối dễ thực hiện, vì vậy tôi hy vọng rằng hầu hết các triển khai sẽ làm như vậy.

Answer 3

Ngôn ngữ chức năng thường có ngăn xếp lớn hơn MUCH. Ví dụ, tôi đã viết một hàm đặc biệt để kiểm tra giới hạn ngăn xếp trong OCaml, và nó đã nhận được hơn 10.000 cuộc gọi trước khi nó bị chặn. Tuy nhiên, điểm của bạn là hợp lệ. Stack-overflows vẫn là thứ bạn cần phải chú ý trong các ngôn ngữ chức năng.

Một trong những chiến lược mà các ngôn ngữ chức năng sử dụng để giảm thiểu sự phụ thuộc vào đệ quy là việc sử dụng tail-call optimization. Nếu cuộc gọi đến đệ quy tiếp theo của hàm hiện tại là câu lệnh cuối cùng trong hàm, cuộc gọi hiện tại có thể bị hủy bỏ khỏi ngăn xếp và cuộc gọi mới được khởi tạo tại vị trí của nó. Các hướng dẫn lắp ráp được tạo ra về cơ bản sẽ giống như các lệnh cho các vòng lặp while trong phong cách bắt buộc.

Chức năng của bạn không thể tối ưu hóa cuộc gọi đuôi vì đệ quy không phải là bước cuối cùng. Nó cần phải trả về đầu tiên và sau đó nó có thể thêm x vào kết quả.Thông thường đây là dễ dàng để có được xung quanh, bạn chỉ cần tạo một hàm helper đi qua một ắc cùng với các thông số khác

let rec sum x = 
    let sum_aux accum x = 
    if x > 1 then sum_aux (accum + x) (x - 1) 
    else x 
    in sum_aux 0 x;; 

Answer 4

Đây là khó khăn - về nguyên tắc có, nhưng trình biên dịch và runtimes cho các ngôn ngữ chức năng chiếm tăng mức độ đệ quy trong các ngôn ngữ chức năng. Cơ bản nhất là hầu hết các ngôn ngữ chức năng yêu cầu một ngăn xếp lớn hơn nhiều so với các chương trình lặp thông thường sẽ sử dụng. Nhưng ngoài ra, một trình biên dịch ngôn ngữ chức năng còn có khả năng chuyển đổi mã đệ quy thành một không đệ quy do các ràng buộc chặt chẽ hơn nhiều của ngôn ngữ.

Answer 5

Nó chắc chắn dễ dàng cho người mới để viết các cuộc xâm nhập sâu thổi đòn. Mục tiêu Caml là không bình thường trong đó các thư viện List chức năng không xếp chồng lên nhau an toàn cho danh sách dài. Các ứng dụng như Unison thực sự đã thay thế thư viện chuẩn List của Caml bằng phiên bản xếp chồng an toàn. Hầu hết các triển khai khác thực hiện công việc tốt hơn với ngăn xếp. (Tuyên bố từ chối trách nhiệm: thông tin của tôi mô tả Mục tiêu Caml 3.08; phiên bản hiện tại, 3.11, có thể tốt hơn.)

Standard ML of New Jersey là bất thường ở chỗ nó không sử dụng ngăn xếp, vì vậy việc tiếp tục sâu sẽ tiếp tục cho đến khi bạn hết đống . Nó được mô tả trong cuốn sách tuyệt vời của Andrew Appel Compiling with Continuations.

Tôi không nghĩ có vấn đề nghiêm trọng ở đây; đó là một "điểm nhận thức" hơn, nếu bạn định viết nhiều mã đệ qui, bạn có nhiều khả năng làm bằng ngôn ngữ chức năng, bạn phải nhận thức được các cuộc gọi không đuôi và kích thước ngăn xếp như so với kích thước của dữ liệu bạn sẽ xử lý.