सत्यापित करें कि एक ओकैमल फ़ंक्शन पूंछ-रिकर्सिव

Question

मैं कैसे बता सकता हूं कि ओकैमल किसी विशेष कार्य को पूंछ-पुनरावर्ती के रूप में पहचानता है या नहीं? विशेष रूप से, मैं पता लगाना चाहते हैं OCaml संकलक पहचानता है, तो नीचे दिए गए जेफरी का जवाब देने के लिए Short-circuited operators and tail recursion

---

धन्यवाद, मैं साधारण समारोह के साथ इस कोशिश की

let rec check_all l = 
    match l with 
    | [] -> true 
    | hd :: tl -> 
     hd && check_all tl 

और वास्तव में, यह करने के लिए अनुकूलन करता है:

camlTest__check_all_1008: 
     .cfi_startproc 
.L102: 
     cmpl $1, %eax 
     je  .L100 
     movl (%eax), %ebx 
     cmpl $1, %ebx 
     je  .L101 
     movl 4(%eax), %eax 
     jmp  .L102 
     .align 16 
.L101: 
     movl $1, %eax 
     ret 

Answer 1

ओकैमल 4.03 से शुरू हो रहा है, और Changes फ़ाइल में टाइपो के बावजूद, आप फ़ंक्शन एप्लिकेशन में @tailcall का उपयोग कर सकते हैं और संकलक चेतावनी देगा अगर यह मामला नहीं है।

(f [@tailcall]) x y ने चेतावनी दी है कि अगर f x y एक पूंछ-कॉल नहीं है

उदाहरण:

$ cat tailrec.ml 
let rec f a x = if x <= 1 then a else (f [@tailcall]) (a * x) (x - 1) 

let rec g x = if x <= 1 then 1 else x * (g [@tailcall]) (x - 1) 

$ ocaml tailrec.ml 

File "tailrec.ml", line 3, characters 40-63: 
Warning 51: expected tailcall 

Answer 2

कई अन्य लोग ओकैमल आंतरिक के बारे में बुद्धिमान हैं, लेकिन सरल कार्यों के लिए जेनरेटेड असेंबली कोड में पूंछ रिकर्सन देखना बहुत आसान है camlopt:

$ cat tailrec.ml 
let rec f a x = if x <= 1 then a else f (a * x) (x - 1) 

let rec g x = if x <= 1 then 1 else x * g (x - 1) 
$ ocamlopt -c -S tailrec.ml 

आप अतिरिक्त उत्पादन का एक बहुत आप f के लिए यह देखने ध्यान नहीं देते हैं:

_camlTailrec__f_1008: 
     .cfi_startproc 
.L101: 
     cmpq $3, %rbx 
     jg  .L100 
     ret 
     .align 2 
.L100: 
     movq %rbx, %rdi 
     addq $-2, %rdi 
     sarq $1, %rbx 
     decq %rax 
     imulq %rbx, %rax 
     incq %rax 
     movq %rdi, %rbx 
     jmp  .L101 
     .cfi_endproc 

संकलक एक पाश में पुनरावर्ती कॉल बदल गया है (अर्थात, समारोह पूंछ पुनरावर्ती है)।

यहाँ आप g के लिए क्या मिलता है:

 .cfi_startproc 
     subq $8, %rsp 
     .cfi_adjust_cfa_offset 8 
.L103: 
     cmpq $3, %rax 
     jg  .L102 
     movq $3, %rax 
     addq $8, %rsp 
     .cfi_adjust_cfa_offset -8 
     ret 
     .cfi_adjust_cfa_offset 8 
     .align 2 
.L102: 
     movq %rax, 0(%rsp) 
     addq $-2, %rax 
     call _camlTailrec__g_1011 
.L104: 
     movq %rax, %rbx 
     sarq $1, %rbx 
     movq 0(%rsp), %rax 
     decq %rax 
     imulq %rbx, %rax 
     incq %rax 
     addq $8, %rsp 
     .cfi_adjust_cfa_offset -8 
     ret 
     .cfi_adjust_cfa_offset 8 
     .cfi_endproc 

प्रत्यावर्तन एक वास्तविक पुनरावर्ती कॉल (पूंछ नहीं पुनरावर्ती) द्वारा नियंत्रित किया जाता।

जैसा कि मैंने कहा है, अगर आप ओकैम इंटरमीडिएट फॉर्मों को बेहतर तरीके से समझते हैं तो इसे समझने के बेहतर तरीके हो सकते हैं।

Answer 3

मुझे आश्चर्य है, क्यों कोई सम्मानित -annot विकल्प के बारे में बताया कि सभी कॉल के लिए एनोटेशन डंप हो जाएगा । हालांकि असेंबली का उपयोग करना सबसे निश्चित तरीका है, असेंबली पढ़ने में हर कोई अच्छा नहीं है। लेकिन एनोट के साथ यह इतना आसान है कि आप इसे स्वचालित भी कर सकते हैं। ,

ocamlc -annot test.ml && if grep -A1 call test.annot | grep stack; then echo "non tailrecursive"; exit 1; fi 

ocaml -annot test.ml एक फ़ाइल संकलन एक test.annot फ़ाइल पैदा करेगा कि: उदाहरण के लिए, यह देखते हुए कि अपने कोड test.ml फ़ाइल में है, हम स्वचालित रूप से जांच कर सकते हैं कि सभी कॉल्स के बाद एक-लाइनर के साथ एक पूंछ स्थिति में हैं प्रत्येक अभिव्यक्ति के लिए एक टिप्पणी होगी। grep -A1 call test.annot सभी कॉल एनोटेशन निकालेगा, और उनकी सामग्री को देखेंगे। grep stack कम से कम एक स्टैक कॉल होने पर सत्य वापस आ जाएगा।

वास्तव में यहां तक ​​कि एक emacs पूरक भी है, जिसे आप the ocaml भंडार में पा सकते हैं, जो इस जानकारी को annot फ़ाइल से निकाल देगा। उदाहरण के लिए, caml-types-show-call फ़ंक्शन है, जो बिंदु पर निर्दिष्ट फ़ंक्शन का एक प्रकार का कॉल दिखाएगा।हालांकि, इस समारोह वर्तमान में एक बग है (जैसे कि यह अब समर्थित नहीं है यह लग रहा है), यह तय करने के लिए आप इसे करने के लिए निम्न पैच लागू करने की आवश्यकता:

--- a/emacs/caml-types.el 
+++ b/emacs/caml-types.el 
@@ -221,7 +221,7 @@ See `caml-types-location-re' for annotation file format." 
       (right (caml-types-get-pos target-buf (elt node 1))) 
       (kind (cdr (assoc "call" (elt node 2))))) 
      (move-overlay caml-types-expr-ovl left right target-buf) 
-   (caml-types-feedback kind))))) 
+   (caml-types-feedback "call: %s" kind))))) 
    (if (and (= arg 4) 
       (not (window-live-p (get-buffer-window caml-types-buffer)))) 
     (display-buffer caml-types-buffer))