Frege가 꼬리 호출 최적화를 수행합니까?

Question

꼬리표는 Frege에서 최적화됩니다. Java 나 Clojure와 Scala 같은 JVM 바이트 코드로 컴파일되는 언어에는 TCO가 없다는 것을 알고 있습니다. 프레지는?

Answer 1

Frege는 단순히 while 루프를 생성하여 테일 재귀 최적화를 수행합니다.

일반적인 꼬리 전화는 게으름을 통해 "비켜"취급됩니다. 컴파일러가 (간접적으로) 재귀적임을 나타내는 의심스러운 함수에 대한 꼬리 호출을 발견하면 지연된 결과 (썽크)가 반환됩니다. 따라서 그 기능을 호출하는 실제 부담은 발신자에게 있습니다. 이 방법으로, 깊이가 데이터에 의존하는 스택은 피할 수 있습니다.

정적 스택 깊이는 자바보다 함수 언어에서 더 깊다. 따라서, 일부 프로그램은 더 큰 스택 (즉, -Xss1m)을 제공해야합니다.

큰 썽크가 빌드되고 평가 될 때 스택 오버플로가 발생하는 병리 적 사례가 있습니다. 악명 높은 예제는 foldl 함수입니다 (하스켈에서와 같은 문제). 그러므로, Frege의 표준 왼쪽 접기는 접기입니다. 이것은 꼬리 재귀 적이며 누적기에 엄격하므로 스택 공간 (Haskells foldl '과 같은)에서 작동합니다.

다음 프로그램해야 2 ~ 3 초 후 하지 스택 오버 플로우하지만 인쇄 "거짓"이 같이 작동

module Test 
    -- inline (odd) 
    where 

even 0 = true 
even 1 = false 
even n = odd (pred n) 

odd n = even (pred n) 

main args = println (even 123_456_789) 

은 다음과 같습니다에 println 그렇게 평가하는 시도, 인쇄 값이 있어야합니다 (심지어 N). 그러나 그것이 얻는 모든 것은 썽크 (홀수 (pred n))입니다. 그러므로 그것은 다른 썽크를 얻는이 덩어리를 평가하려고합니다 (even (pred (pred n))). n-2가 이미 평가 된 다른 썽크 (odd (pred (n-2))를 반환하기 전에 인수가 0 또는 1인지 알아보기 위해 (pred (pred n)) 평가해야합니다.

인라인 지시어의 주석을 제거하면, 꼬리 재귀 버전 인 even을 얻게되고 결과는 10 번 얻게됩니다 (JVM 수준에서). println에서 실제로 수행됩니다. . 빠른

이 서투른 알고리즘은 데모입니다 말할 필요도없이 -. 여기

일반적으로 하나는 비트 연산과 짝수 다움을 확인 할

가 다른 버전, 즉 병적이며 overflo 스택 것 W :

even 0 = true 
even 1 = false 
even n = not . odd $ n 
odd = even . pred 

문제는 not 꼬리 호출하고 그것의 인수에 엄격한 것으로 여기 (즉, 무언가를 부정하려면 먼저 뭔가가 있어야합니다)를. 따라서 even n을 계산할 때 not은 odd n을 완전히 평가해야하며 차례로 even (pred n)을 완전히 평가해야하므로 2 * n 스택 프레임을 사용하게됩니다.

JVM이 언젠가 적절한 꼬리 전화를해야하더라도 유감스럽게도 변경되지 않습니다. 이유는 엄격한 함수의 인수에서 재귀입니다.

Answer 2

@Landei TCO는 Scala에서 완전히 지원되지 않습니다 ...이 항목을 시도해보십시오.

def foo() { def bar() { println("bar"); foo() }; println("foo"); bar() } 

참고로 평판이 나쁩니다. 원본 질문에 대한 답글에 답글을 달았습니다.