Компиляторы семейства ML делают какую-либо сложную оптимизацию для хвостовых вызовов?

Question

Я (полагаю) следующее определение функции является хвостово-рекурсивным:

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

Тривиально, это эквивалентно следующему объявлению

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

Тем не менее, в этой версии последний шаг заключается в применении 'andalso', так что это не хвостовая рекурсия. Или может показаться, что, за исключением того, что (по крайней мере, стандарт) ML (из Нью-Джерси) использует оценку короткого замыкания, фактически также / не / последний шаг. Так будет ли у этой функции оптимизация хвостового вызова? Или есть другие интересные случаи, когда функция ML, которая явно не использует хвостовую рекурсию, на самом деле оптимизируется?

Answer 1

Если я переведу вашу вторую функцию на OCaml, я получу это:

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

Это компилируется как хвост-рекурсивная функция ocamlopt. Суть сгенерированного кода (x86_64) заключается в следующем:

        .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

Как вы можете видеть, в этом коде нет рекурсивных вызовов, только цикл.

(Но другие авторы правы в том, что OCaml не делает ничего особенного на пути сложного анализа. Этот конкретный результат кажется довольно простым.)

Answer 2

Обратите внимание, что

A andalso B

эквивалентно

if A then B else false

Определение языка SML даже определяет его таким образом. Следовательно, B находится в хвостовой позиции. Не нужно модной оптимизации.