Scala가 꼬리 재귀 최적화를 지원합니까?

Question

Scala가 꼬리 재귀 최적화를 지원합니까?

Answer 1

Scala는 다른 포스터가 말했듯이 컴파일 타임에 꼬리 재귀 최적화를 수행합니다. 즉, 테일 재귀 함수를 실행할 때 스택 트레이스에서 볼 수 있듯이 테일 재귀 함수는 컴파일러에 의해 루프로 변환됩니다 (메소드 호출이 점프로 변환됨).

다음 스 니펫을 사용해보십시오.

def boom(n: Int): Nothing = if(n<=0) throw new Exception else boom(n-1)
boom(10)

스택 추적을 검사하십시오. 함수 붐에 대한 하나의 호출 만 표시되므로 컴파일 된 바이트 코드는 재귀가 아닙니다.

주위에 떠 다니는 제안이 있습니다 JVM 레벨에서 꼬리 호출을 구현하십시오 - JVM이 코드의 시간 최적화를 컴파일하는 대신 런타임 최적화를 수행 할 수 있기 때문에 내 의견으로는 큰 일이 될 것입니다. 기본적으로 a tailcall invoke 정상적인 방법과 똑같이 행동합니다 invoke 그러나 안전 할 때 발신자의 스택이 떨어질 것입니다. 사용된.

그것의 현재 상태는입니다 프로토 80%. 나는 그것이 Java 7을 위해 제 시간에 이루어질 것이라고 생각하지 않는다 (invokedynamic 우선 순위가 높고 구현이 거의 완료되었지만 Java 8에서 구현 된 것을 볼 수 있습니다.

Answer 2

Scala 2.8에서 사용할 수 있습니다 @tailrec 컴파일러가 예상되는 특정 방법을 표시하려면 다음을 최적화합니다.

import scala.annotation.tailrec

@tailrec def factorialAcc(acc: Int, n: Int): Int = {
  if (n <= 1) acc
  else factorialAcc(n * acc, n - 1)
}

메소드를 최적화 할 수 없으면 컴파일 타임 오류가 발생합니다.

Answer 3

Scala 2.7.x는 최종 방법 및 로컬 기능의 자체 추론 (기능 자체)을위한 꼬리 통화 최적화를 지원합니다.

Scala 2.8에는 트램폴린에 대한 라이브러리 지원도 제공 될 수 있으며, 이는 상호 재귀 기능을 최적화하는 기술입니다.

스칼라 재귀 상태에 대한 많은 정보가 Rich Dougherty의 블로그.

Answer 4

기능이 자립적인 매우 간단한 경우에만.

꼬리 재귀 능력의 증거.

그러나 Scala 2.8이 꼬리 수익률 인식을 향상시키는 것처럼 보입니다.