Ruby는 Tail Call 최적화를 수행합니까?

Ruby는 Tail Call 최적화를 수행합니까?

---

기능적 언어는 재귀를 사용하여 많은 문제를 해결하기 때문에 많은 문제가 TCO (Tail Call Optimization)를 수행합니다. TCO는 해당 함수의 마지막 단계 인 다른 함수 (또는 자체적으로이 기능을 TCO의 하위 집합 인 Tail Recursion Elimination라고도 함)에서 함수를 호출하여 새 스택 프레임이 필요하지 않게합니다. 오버 헤드와 메모리 사용량을 줄입니다.

Ruby는 분명히 기능적 언어 (람다,지도와 같은 함수 등)에서 여러 개념을 "차용"했습니다. 그래서 궁금합니다. Ruby가 테일 호출 최적화를 수행합니까?

---

아니요, Ruby는 TCO를 수행하지 않습니다. 그러나, 그것은 또한하지 않습니다 하지 총 소유 비용 (TCO)을 수행합니다.

Ruby 언어 사양에는 TCO에 대한 내용이 없습니다. 그것은 당신이 그것을해야한다고 말하는 것이 아니라 당신 이 그것을 할 수 없다는 것을 말하지도 않습니다 . 당신 은 그것에 의지 할 수 없습니다 .

언어 사양이 곳은 계획, 달리 요구 하는 것이 모든 구현이 있어야 총 소유 비용 (TCO)을 수행합니다. 그러나 Guido van Rossum이 Python 구현 이 TCO를 수행 해서는 안된다는 것을 여러 번 (마지막 며칠 전)에 매우 명확하게 한 Python 과도 다릅니다 .

Yukihiro Matsumoto는 TCO에 공감하며 모든 구현이이를 지원 하도록 강요하고 싶지는 않습니다 . 안타깝게도 이는 TCO에 의존 할 수 없다는 것을 의미합니다. 그렇지 않으면 코드를 더 이상 다른 Ruby 구현으로 이식 할 수 없습니다.

따라서 일부 Ruby 구현은 TCO를 수행하지만 대부분은 수행하지 않습니다. 예를 들어 YARV는 TCO를 지원하지만 (현재로서는) TCO를 활성화하기 위해 소스 코드의 한 줄을 명시 적으로 주석 해제하고 VM을 다시 컴파일해야합니다. 이후 버전에서는 구현이 입증 된 후 기본적으로 설정 될 것입니다. 안정된. Parrot Virtual Machine은 기본적으로 TCO를 지원하므로 Cardinal도이를 매우 쉽게 지원할 수 있습니다. CLR은 TCO를 일부 지원하므로 IronRuby와 Ruby.NET이이를 수행 할 수 있습니다. Rubinius도 그렇게 할 수 있습니다.

그러나 JRuby와 XRuby는 TCO를 지원하지 않으며 JVM 자체가 TCO를 지원하지 않는 한 지원하지 않을 것입니다. 문제는 이것입니다. 빠른 구현과 Java와의 빠르고 원활한 통합을 원한다면 Java와 스택 호환이 가능하고 JVM 스택을 가능한 많이 사용해야합니다. 트램폴린 또는 명시 적 연속 전달 스타일을 사용하여 TCO를 매우 쉽게 구현할 수 있지만 더 이상 JVM 스택을 사용하지 않습니다. 즉, Java를 호출하거나 Java에서 Ruby로 호출 할 때마다 다음 작업을 수행해야합니다. 느린 변환입니다. 따라서 XRuby와 JRuby는 TCO 및 연속성 (기본적으로 동일한 문제가 있음)보다 속도 및 Java 통합을 선택했습니다.

이는 기본적으로 TCO를 지원하지 않는 일부 호스트 플랫폼과 긴밀하게 통합하려는 Ruby의 모든 구현에 적용됩니다. 예를 들어, MacRuby도 같은 문제를 겪을 것 같습니다.

---

업데이트 : 다음은 Ruby의 TCO에 대한 멋진 설명입니다. http://nithinbekal.com/posts/ruby-tco/

업데이트 : tco_method gem을 확인하세요 : http://blog.tdg5.com/introducing-the-tco_method-gem/

Ruby MRI (1.9, 2.0 및 2.1)에서 다음을 사용하여 TCO를 켤 수 있습니다.

RubyVM::InstructionSequence.compile_option = {
  :tailcall_optimization => true,
  :trace_instruction => false
}

Ruby 2.0에서 기본적으로 TCO를 켜는 제안이있었습니다. 또한 그와 함께 제공되는 몇 가지 문제를 설명합니다. 테일 호출 최적화 : 기본적으로 활성화 하시겠습니까?.

링크에서 발췌 :

일반적으로 꼬리 재귀 최적화에는 "점프"변환에 대한 "호출"이라는 또 다른 최적화 기술이 포함됩니다. 제 생각에는 Ruby의 세계에서 "재귀"를 인식하는 것이 어렵 기 때문에이 최적화를 적용하기가 어렵습니다.

다음 예. "else"절의 fact () 메서드 호출은 "테일 호출"이 아닙니다.

def fact(n) 
  if n < 2
    1 
 else
   n * fact(n-1) 
 end 
end

fact () 메서드에서 tail-call 최적화를 사용하려면 다음과 같이 fact () 메서드를 변경해야합니다 (연속 전달 스타일).

def fact(n, r) 
  if n < 2 
    r
  else
    fact(n-1, n*r)
  end
end

---

다음을 가질 수 있지만 보장되지는 않습니다.

https://bugs.ruby-lang.org/issues/1256

---

컴파일하기 전에 vm_opts.h의 몇 가지 변수를 조정하여 TCO를 컴파일 할 수도 있습니다. https://github.com/ruby/ruby/blob/trunk/vm_opts.h#L21

// vm_opts.h
#define OPT_TRACE_INSTRUCTION        0    // default 1
#define OPT_TAILCALL_OPTIMIZATION    1    // default 0

---

이것은 Jörg와 Ernest의 답변을 기반으로합니다. 기본적으로 구현에 따라 다릅니다.

I couldn't get Ernest's answer to work on MRI, but it is doable. I found this example that works for MRI 1.9 to 2.1. This should print a very large number. If you don't set TCO option to true, you should get the "stack too deep" error.

source = <<-SOURCE
def fact n, acc = 1
  if n.zero?
    acc
  else
    fact n - 1, acc * n
  end
end

fact 10000
SOURCE

i_seq = RubyVM::InstructionSequence.new source, nil, nil, nil,
  tailcall_optimization: true, trace_instruction: false

#puts i_seq.disasm

begin
  value = i_seq.eval

  p value
rescue SystemStackError => e
  p e
end

참고URL : https://stackoverflow.com/questions/824562/does-ruby-perform-tail-call-optimization