Czy Ruby przeprowadza optymalizację wywołań ogona?

Języki funkcjonalne prowadzą do wykorzystania rekurencji do rozwiązywania wielu problemów, dlatego wiele z nich wykonuje Tail Call Optimization (TCO). TCO powoduje, że wywołania funkcji z innej funkcji (lub samej siebie, w którym to przypadku ta funkcja jest również znana jako eliminacja rekurencji ogona, która jest podzbiorem TCO), jako ostatni krok tej funkcji, nie potrzebuje nowej ramki stosu, co zmniejsza obciążenie i zużycie pamięci.

Ruby najwyraźniej „zapożyczył” wiele koncepcji z języków funkcjonalnych (lambdy, funkcje takie jak mapa itp.), Co mnie zaciekawia: Czy Ruby przeprowadza optymalizację wywołań ogonowych?

Nie, Ruby nie oblicza całkowitego kosztu posiadania. Jednak tak nie jest wykonywać TCO.

Specyfikacja języka Ruby nie mówi nic o całkowitym koszcie posiadania. Nie mówi, że musisz to zrobić, ale też nie mówi, że nie możesz tego zrobić. Po prostu nie możesz polegać na tym .

Jest to w przeciwieństwie do schematu, gdzie Język Specyfikacja wymaga , że wszystkie implementacje muszą wykonać TCO. Ale jest to również w przeciwieństwie do Pythona, w którym Guido van Rossum wielokrotnie podkreślał (ostatni raz zaledwie kilka dni temu), że implementacje Pythona nie powinny przeprowadzać całkowitego kosztu posiadania.

Yukihiro Matsumoto sympatyzuje z TCO, po prostu nie chce narzucać wszystkiego wdrożeń do jego obsługi. Niestety oznacza to, że nie możesz polegać na całkowitym koszcie posiadania, a jeśli to zrobisz, Twój kod nie będzie już przenośny do innych implementacji Rubiego.

Tak więc niektóre implementacje Ruby zapewniają całkowity koszt posiadania, ale większość nie. Na przykład YARV obsługuje TCO, chociaż (na razie) trzeba jawnie odkomentować wiersz w kodzie źródłowym i przekompilować maszynę wirtualną, aby aktywować TCO - w przyszłych wersjach będzie domyślnie włączony, po wdrożeniu udowodni stabilny. Maszyna wirtualna Parrot natywnie obsługuje całkowity koszt posiadania, dlatego też Cardinal może z łatwością ją obsługiwać. CLR ma pewne wsparcie dla TCO, co oznacza, że ​​IronRuby i Ruby.NET prawdopodobnie mogłyby to zrobić. Rubinius prawdopodobnie też by to zrobił.

Ale JRuby i XRuby nie obsługują całkowitego kosztu posiadania i prawdopodobnie nie będą, chyba że sama JVM uzyska wsparcie dla całkowitego kosztu posiadania. Problem jest następujący: jeśli chcesz mieć szybką implementację oraz szybką i bezproblemową integrację z Javą, powinieneś być kompatybilny ze stosem z Javą i używać stosu JVM tak często, jak to możliwe. Możesz dość łatwo zaimplementować TCO z trampolinami lub jawnym stylem przekazywania kontynuacji, ale wtedy nie używasz już stosu JVM, co oznacza, że ​​za każdym razem, gdy chcesz wywołać Java lub wywołać z Javy do Rubiego, musisz wykonać jakiś rodzaj konwersja, która jest powolna. Tak więc XRuby i JRuby wybrali szybkość i integrację z Javą, a nie całkowity koszt posiadania i kontynuację (które zasadniczo mają ten sam problem).

Dotyczy to wszystkich implementacji Rubiego, które chcą ściśle zintegrować się z platformą hosta, która nie obsługuje natywnie TCO. Na przykład, myślę, że MacRuby będzie miał ten sam problem.

Aktualizacja: Oto ładne wyjaśnienie TCO w Rubim: http://nithinbekal.com/posts/ruby-tco/

Aktualizacja: możesz również sprawdzić klejnot tco_method : http://blog.tdg5.com/introducing-the-tco_method-gem/

W Ruby MRI (1,9, 2,0 i 2,1) można włączyć TCO za pomocą:

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

Pojawiła się propozycja domyślnego włączenia TCO w Ruby 2.0. Wyjaśnia również kilka problemów, które się z tym wiążą: Optymalizacja połączeń ogonowych: włączyć domyślnie ?.

Krótki fragment linku:

Ogólnie rzecz biorąc, optymalizacja rekurencji ogonowej obejmuje inną technikę optymalizacji - tłumaczenie „wywołanie” w celu „skoku”. Moim zdaniem trudno jest zastosować tę optymalizację, ponieważ rozpoznanie „rekurencji” jest trudne w świecie Rubiego.

Następny przykład. Wywołanie metody fact () w klauzuli „else” nie jest wywołaniem końcowym.

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

Jeśli chcesz użyć optymalizacji wywołań końcowych w metodzie fact (), musisz zmienić metodę fact () w następujący sposób (styl przekazywania kontynuacji).

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

Może mieć, ale nie gwarantuje, że:

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

TCO można również skompilować, dostosowując kilka zmiennych w vm_opts.h przed kompilacją: 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

Opiera się to na odpowiedziach Jörga i Ernesta. Zasadniczo zależy to od wdrożenia.

Nie mogłem dostać odpowiedzi Ernesta do pracy nad MRI, ale jest wykonalne. Znalazłem ten przykład, który działa dla MRI 1,9 do 2,1. Powinno to spowodować wydrukowanie bardzo dużej liczby. Jeśli nie ustawisz opcji TCO na true, powinieneś otrzymać błąd „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