루비는 테일 호출 최적화를 수행합니까?

StackOverflow https://stackoverflow.com/questions/824562

문제

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

루비는 분명히 기능 언어 (람다,지도 등과 같은 기능 등)의 여러 개념을 "빌린"것을 가지고 있습니다. 루비는 테일 콜 최적화를 수행합니까?

도움이 되었습니까?

해결책

아니요, 루비는 TCO를 수행하지 않습니다. 그러나 그것은 또한 그렇지 않습니다 ~ 아니다 TCO를 수행하십시오.

루비 언어 사양은 TCO에 대해 아무 말도하지 않습니다. 그것은 당신이 그것을해야한다고 말하지는 않지만, 또한 당신을 말하는 것은 아닙니다. 캔트 해. 당신은 그냥 할 수 없습니다 의존하다 그 위에.

이것은 언어 사양의 구성표와 다릅니다 필요합니다 저것 모두 구현 ~ 해야 하다 TCO를 수행하십시오. 그러나 Guido van Rossum이 Python 구현이 그 Python 구현이 여러 차례 (마지막으로 며칠 전)를 매우 명확하게 만든 Python과도 다릅니다. 해서는 안됩니다 TCO를 수행하십시오.

Yukihiro Matsumoto는 TCO에 동정적입니다. 모두 이를 지원하기위한 구현. 불행히도 이것은 TCO에 의존 할 수 없거나 그렇게하면 코드가 더 이상 다른 Ruby 구현에 휴대 할 수 없음을 의미합니다.

따라서 일부 루비 구현은 TCO를 수행하지만 대부분은 그렇지 않습니다. 예를 들어 YARV는 TCO를 지원하지만 (현재) 소스 코드의 줄을 명시 적으로 무너 뜨리고 VM을 다시 컴파일해야 TCO를 활성화해야합니다. 안정적인. 앵무새 가상 머신은 기본적으로 TCO를 지원하므로 추기경도이를 쉽게 지원할 수 있습니다. CLR은 TCO에 대한 지원을 받았으며, 이는 Ironruby와 Ruby.net이 아마도 그렇게 할 수 있음을 의미합니다. Rubinius도 아마 그것을 할 수있었습니다.

그러나 Jruby와 Xruby는 TCO를 지원하지 않으며 JVM 자체가 TCO를 지원하지 않는 한 아마도 그렇지 않을 것입니다. 문제는 이것입니다. 빠른 구현과 Java와의 빠르고 원활한 통합을 원한다면 Java와 스택과 호환되어 JVM의 스택을 최대한 많이 사용해야합니다. 트램폴린 또는 명백한 연속 통과 스타일로 TCO를 쉽게 구현할 수 있지만 더 이상 JVM 스택을 사용하지 않으므로 Java로 전화하거나 Java에서 Ruby로 전화를 걸고 싶을 때마다 어떤 종류의 공연을 수행해야합니다. 변환이 느립니다. 따라서 Xruby와 Jruby는 TCO 및 연속 (기본적으로 동일한 문제가 있음)에 대한 속도 및 Java 통합을 선택했습니다.

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

다른 팁

업데이트: 루비에서 TCO에 대한 좋은 설명은 다음과 같습니다. http://nithinbekal.com/posts/ruby-tco/

업데이트: 당신은 또한 확인을 원할 수도 있습니다 TCO_METHOD 보석: 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
}

루비 2.0에서 기본적으로 TCO를 켜는 제안이있었습니다. 또한 다음과 같은 몇 가지 문제를 설명합니다. 테일 콜 최적화 : 기본적으로 활성화?.

링크에서 짧은 발췌 :

일반적으로 꼬리 재고 최적화에는 또 다른 최적화 기술이 포함되어 있습니다 - "호출"to "Jump"번역이 포함됩니다. 제 생각에는 루비의 세계에서 "재귀"를 인식하는 것이 어렵 기 때문에이 최적화를 적용하기가 어렵습니다.

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

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

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에 대한 일에 대한 어니스트의 대답을 얻을 수 없었지만 가능합니다. 나는 찾았다 이 예 그것은 MRI 1.9에서 2.1에 효과적입니다. 이것은 매우 많은 숫자를 인쇄해야합니다. TCO 옵션을 true로 설정하지 않으면 "너무 깊은"오류를 가져와야합니다.

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
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top