Có sử dụng rất nhiều đệ quy đuôi trong Erlang làm chậm nó xuống?

Question

Tôi đã đọc về Erlang thời gian gần đây và cách đệ quy đuôi được sử dụng rất nhiều, do khó khăn trong việc sử dụng vòng lặp lặp lại.

Không sử dụng quá trình đệ quy này làm chậm nó xuống, những gì có tất cả các cuộc gọi hàm và hiệu ứng mà chúng có trên ngăn xếp? Hay sự đệ quy đuôi phủ nhận hầu hết điều này?

Answer 1

Đợt đệ quy đuôi thường được thực hiện bằng cách sử dụng Tail calls. Điều này về cơ bản là một sự chuyển đổi của một cuộc gọi đệ quy thành một vòng lặp đơn giản.

C# Ví dụ:

uint FactorialAccum(uint n, uint accum) { 
    if(n < 2) return accum; 
    return FactorialAccum(n - 1, n * accum); 
}; 
uint Factorial(uint n) { 
    return FactorialAccum(n, 1); 
}; 

để

uint FactorialAccum(uint n, uint accum) { 
start: 
    if(n < 2) return accum; 
    accum *= n; 
    n -= 1; 
goto start; 
}; 
uint Factorial(uint n) { 
    return FactorialAccum(n, 1); 
}; 

hoặc thậm chí tốt hơn:

uint Factorial(uint n) { 
    uint accum = 1; 
start: 
    if(n < 2) return accum; 
    accum *= n; 
    n -= 1; 
goto start; 
}; 

---

C không # thực đuôi đệ quy, điều này là do giá trị trả về được sửa đổi , hầu hết các trình biên dịch sẽ không phá vỡ điều này wn vào một vòng lặp:

int Power(int number, uint power) { 
    if(power == 0) return 1; 
    if(power == 1) return number; 
    return number * Power(number, --power); 
} 

để

int Power(int number, uint power) { 
    int result = number; 
start: 
    if(power == 0) return 1; 
    if(power == 1) return number; 
    result *= number; 
    power--; 
goto start; 
} 

Answer 2

Điểm có ích là Erlang tối ưu hóa các cuộc gọi đuôi (không chỉ đệ quy). Tối ưu hóa các cuộc gọi đuôi khá đơn giản: nếu giá trị trả về được tính bằng một cuộc gọi đến một hàm khác, thì hàm khác này không chỉ đặt trên ngăn gọi hàm trên đầu của hàm gọi, mà thay vào đó khung ngăn xếp của hàm hiện tại là thay thế bằng một trong các chức năng được gọi. Điều này có nghĩa là các cuộc gọi đuôi không thêm vào kích thước ngăn xếp.

Vì vậy, không, sử dụng đệ quy đuôi không làm chậm Erlang xuống, cũng không gây ra nguy cơ tràn ngăn xếp.

Với tối ưu hóa cuộc gọi đuôi tại chỗ, bạn không chỉ có thể sử dụng đệ quy đuôi đơn giản, mà còn đệ quy đuôi một số chức năng (đuôi đuôi b, mà đuôi gọi c, đuôi gọi là ...) . Điều này đôi khi có thể là một mô hình tính toán tốt.

Answer 3

Nó không ảnh hưởng đến hiệu suất trong hầu hết các trường hợp. Những gì bạn đang tìm kiếm không chỉ là các cuộc gọi đuôi mà còn tối ưu hóa cuộc gọi đuôi (hoặc xóa cuộc gọi đuôi). Tail gọi tối ưu hóa là một trình biên dịch hoặc kỹ thuật thời gian chạy mà con số ra khi một cuộc gọi đến một chức năng là tương đương với 'popping stack' để có được trở lại chức năng thích hợp thay vì chỉ trở về. Nói chung, tối ưu hóa cuộc gọi đuôi chỉ có thể được thực hiện khi cuộc gọi đệ quy là hoạt động cuối cùng trong hàm, vì vậy bạn phải cẩn thận.

Answer 4

Tối ưu hóa tương tự tách các cuộc gọi hàm văn bản chương trình khỏi các cuộc gọi hàm thực hiện là 'nội tuyến'. Trong các cuộc gọi hàm ngôn ngữ hiện đại/chu đáo, có ít liên quan đến các cuộc gọi hàm mức máy.

Answer 5

Có sự cố liên quan đến đệ quy đuôi nhưng không liên quan đến hiệu suất - Tối ưu hóa đệ quy đuôi Erlang cũng liên quan đến việc loại bỏ dấu vết ngăn xếp để gỡ lỗi.

Ví dụ, xem Điểm 9.13 của Erlang FAQ:

Why doesn't the stack backtrace show the right functions for this code: 

     -module(erl). 
     -export([a/0]). 

     a() -> b(). 
     b() -> c(). 
     c() -> 3 = 4.   %% will cause badmatch 

The stack backtrace only shows function c(), rather than a(), b() and c(). 
This is because of last-call-optimisation; the compiler knows it does not need 
to generate a stack frame for a() or b() because the last thing it did was 
call another function, hence the stack frame does not appear in the stack 
backtrace. 

Đây có thể là một chút đau đớn khi bạn nhấn một vụ tai nạn (nhưng nó kinda đi với lãnh thổ của lập trình chức năng ...)