Müssen ML-Familien-Compiler raffinierte Optimierungen für Tail-Calls vornehmen?

I (glauben) die folgende Funktionsdefinition ist tail-rekursive:Müssen ML-Familien-Compiler raffinierte Optimierungen für Tail-Calls vornehmen?

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

Trivialerweise ist es gleichbedeutend mit der folgenden Erklärung

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

Doch in dieser Version ist der letzte Schritt ist die ‚andalso anzuwenden ', so ist es nicht tail-rekursiv. Oder es scheint so zu sein, außer dass (zumindest Standard) ML (von NJ) eine Kurzschlussauswertung verwendet, ist das und ist auch tatsächlich/nicht/der letzte Schritt. Hätte diese Funktion also Tail-Call-Optimierung? Oder gibt es noch andere interessante Fälle, in denen eine ML-Funktion, die offensichtlich keine Tail-Rekursion verwendet, tatsächlich optimiert wird?

Quelle

2014-07-17 Zach Halle

Ich kann Ihnen sagen, dass das letzte Mal, als ich die von OCaml generierte Assembly las, der Aufruf in 'fun x -> let r = gx in r' nicht als Tail-Call kompiliert wurde. –

Ich glaube nicht. Haskell antwortet ziemlich heftig auf den Compiler, um diese Art von Optimierung zu machen. Aber die Philosophie von OCaml besteht darin, diese Ebene der Optimierung dem Entwickler zu überlassen, und in der Regel kompiliert der Compiler das, was der Entwickler schreibt. –

Scheint mir, Ihre Funktion bekommt die falsche Antwort für die Liste '[3, 4, 2, 3, 4]' –

Wenn ich Ihre zweite Funktion zu OCaml übersetzen bekomme ich dies:

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

Dies als Schwanz-rekursive Funktion von ocamlopt kompiliert wird. Das Wesen des generierten Codes (x86_64) ist dies:

 .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

Wie Sie keine rekursiven Aufrufe gibt es in diesem Code sehen können, nur eine Schleife.

(Aber auch andere Plakate sind richtig, dass OCaml nicht alle in der Art und Weise der hoch entwickelten Analyse, dass viel macht. Dieses besondere Ergebnis scheint ziemlich einfach.)

Quelle

2014-07-17 16:02:31

Beachten Sie, dass

A andalso B

äquivalent zu

if A then B else false

Die SML-Sprachdefinition definiert es sogar so. Folglich ist B in der Endposition. Keine schicke Optimierung notwendig.

Quelle

2014-07-17 21:19:18

Müssen ML-Familien-Compiler raffinierte Optimierungen für Tail-Calls vornehmen?

Antwort

Verwandte Themen