ML系列编译器是否对尾部调用进行了任何复杂的优化？

扎克·霍尔

我（相信）以下函数定义是尾递归的：

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”，因此它不是尾递归的。或看起来如此，除了（由于NJ的）ML（至少是标准）使用短路评估外，andand实际上是/ not /的最后一步。那么此功能是否可以进行尾部调用优化？还是在其他有趣的情况下，实际上不明显使用尾递归的ML函数得到了优化？

杰弗里·斯科菲尔德

如果我将您的第二个功能转换为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在复杂分析方面所做的工作并不多。这种特殊结果似乎非常简单。）

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。