Trình biên dịch gia đình ML có thực hiện bất kỳ tối ưu hóa tinh vi nào cho các cuộc gọi đuôi không?

Question

I (tin) định nghĩa hàm sau là đuôi-đệ quy:

fun is_sorted [] = true 
    | is_sorted [x] = true 
    | is_sorted (x::(y::xs)) = 
    if x > y 
     then false 
     else is_sorted (y::xs) 

trivially, nó tương đương với việc kê khai sau

fun is_sorted [] = true 
    | is_sorted [x] = true 
    | is_sorted (x::(y::xs)) = 
    (x <= y) andalso (is_sorted (y::xs)) 

Tuy nhiên, trong phiên bản này là bước cuối cùng là để áp dụng các 'AndAlso ', do đó, nó không phải đệ quy đuôi. Hoặc nó sẽ có vẻ như vậy, ngoại trừ rằng (ít nhất là tiêu chuẩn) ML (của NJ) sử dụng đánh giá ngắn mạch, andalso là trong thực tế/không/bước cuối cùng. Vậy chức năng này có tối ưu hóa cuộc gọi đuôi không? Hoặc có bất kỳ trường hợp thú vị nào khác mà một hàm ML không rõ ràng sử dụng đệ quy đuôi trong thực tế được tối ưu hóa không?

Answer 1

Nếu tôi dịch chức năng thứ hai của bạn để OCaml tôi có được điều này:

let rec is_sorted : int list -> bool = function 
| [] -> true 
| [_] -> true 
| x :: y :: xs -> x < y && is_sorted xs 

này được biên soạn như một hàm đuôi-đệ quy bằng ocamlopt. Bản chất của mã được tạo (x86_64) là:

 .globl  _camlAndalso__is_sorted_1008 
_camlAndalso__is_sorted_1008: 
     .cfi_startproc 
.L103: 
     cmpq  $1, %rax 
     je .L100 
     movq  8(%rax), %rbx 
     cmpq  $1, %rbx 
     je .L101 
     movq  (%rbx), %rdi 
     movq  (%rax), %rax 
     cmpq  %rdi, %rax 
     jge .L102 
     movq  8(%rbx), %rax 
     jmp .L103 
     .align  2 
.L102: 
     movq  $1, %rax 
     ret 
     .align  2 
.L101: 
     movq  $3, %rax 
     ret 
     .align  2 
.L100: 
     movq  $3, %rax 
     ret 
     .cfi_endproc 

Như bạn có thể thấy không có lời gọi đệ quy nào trong mã này, chỉ cần lặp lại.

(Nhưng áp phích khác là đúng rằng OCaml không làm tất cả những gì nhiều trong cách phân tích tinh vi. Kết quả cụ thể này có vẻ khá đơn giản.)

Answer 2

Lưu ý rằng

A andalso B 

tương đương với

if A then B else false 

Định nghĩa ngôn ngữ SML thậm chí xác định theo cách đó. Do đó, B là ở vị trí đuôi. Không cần tối ưu hóa ưa thích.