OCaml 컴파일러는 부울 연산자를 사용하여 재귀를 꼬리 재귀로 만듭니다.

Question

는의는 다음과 같은 기능 is_prime를 살펴 보자 : n mod i <> 0이 거짓입니다

let is_prime n = 
    let rec div_check i = i * i > n || (n mod i <> 0 && div_check (i+1)) 
    in 
    n >= 2 && div_check 2 

그렇다면,이 중지됩니다.

그러나 n mod i <> 0이 이면 인 경우 재귀 적으로 계속됩니다.

내 질문에 계속한다면 OCaml은 컴파일러를 최적화 했으므로 div_check(i+1) 즉 tail-recursive 만 반환하면됩니까? 또는 여전히 true && 부분을 보유하고 div_check이 반환 될 때까지 기다릴 것입니까?

PS는 기능 대답이 예 http://www.cs.cornell.edu/Courses/cs3110/2014sp/lectures/2/lec02.html

Answer 1

로부터 취해진 다.

이 입력을 감안할 때

let rec is_prime n = 
    let rec div_check i = 
    i * i > n || (i + i < n && div_check (i+1)) in 
    div_check n 

는 다음 어셈블리를 방출합니다 컴파일러 (나는 몇 가지 주석을 추가 한) : 나는 컴파일러 출력을 더 이해할 수 있도록, 당신의 예를 단순화했습니다

camlIs_prime__div_check_1010: 
.L102: 
    movq 16(%rbx), %rdi 
    movq %rax, %rsi 
    sarq $1, %rsi 
    movq %rax, %rdx 
    decq %rdx 
    imulq %rsi, %rdx   ; i * i 
    incq %rdx 
    cmpq %rdi, %rdx   ; if i * i <= n then return 
    jle .L101 
    movq $3, %rax 
    ret 
.L101: 
    movq 16(%rbx), %rdi 
    leaq -1(%rax, %rax), %rsi ; i + i 
    cmpq %rdi, %rsi   ; i + i ? n 
    jge .L100     ; if i + i >= n then return 
    addq $2, %rax    ; else i := i + 1 
    jmp .L102     ;  div_check i 
.L100: 
    movq $1, %rax 
    ret 

그러나 수 이것은 바닐라 OCaml의 단락 회로 운영자에게만 적용됩니다. let (&&) = (&&)과 같은 무해한 변경도 break입니다. jmp .L102은 call camlIs_prime__div_check_...으로 대체됩니다.

또한 통화가 단락 연산자 오른쪽에있는 경우에만 작동합니다. 왼쪽 표현식은 비 꼬리 재귀 적으로 marked입니다. 필자는 그것을 테스트했으며, 실제로 을 && 연산자의 왼쪽에 배치하면 비 꼬리 재귀 코드가 방출됩니다.

전화가 꼬리인지 아닌지 의심스러운 경우 언제든지 -annot 플래그를 컴파일러에 추가하고 *.annot 파일 (call (tail) 주석)을 볼 수 있습니다. Merlin에는 툴링 지원이 있지만, 제대로 사용하는 방법을 찾지 못했습니다. 최종 판사는 여전히 어셈블리 결과물입니다.