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

Program / 글쓴이

기능적 언어는 재귀를 사용하여 많은 문제를 해결하기 때문에 많은 문제가 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의 답변을 기반으로합니다. 기본적으로 구현에 따라 다릅니다.

MRI 작업에 대한 Ernest의 답변을 얻지 못했지만 가능합니다. MRI 1.9 ~ 2.1에서 작동하는 이 예제 를 찾았습니다 . 이것은 매우 많은 수를 인쇄해야합니다. TCO 옵션을 true로 설정하지 않으면 “stack too deep”오류가 발생합니다.

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

답변