Czy Ruby przeprowadza optymalizację wywołań ogona?

92

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?

Charlie Flowers
źródło

Odpowiedzi:

128

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.

Jörg W Mittag
źródło
2
Mogę się mylić (proszę mnie oświecić, jeśli tak), ale wątpię, czy całkowity koszt posiadania ma jakikolwiek sens w prawdziwych językach OO, ponieważ wywołanie ogonowe musi być w stanie ponownie wykorzystać ramkę stosu wywołań. Ponieważ z późnym wiązaniem nie wiadomo w czasie kompilacji, która metoda zostanie wywołana przez wysłanie wiadomości, wydaje się to trudne do zapewnienia (być może z JIT typu sprzężenie zwrotne typu lub przez wymuszenie na wszystkich implementujących wiadomości użycia ramek stosu tej samej wielkości lub ograniczając całkowity koszt posiadania do samodzielnego wysłania tej samej wiadomości…).
Damien Pollet
2
To świetna odpowiedź. Tych informacji nie można łatwo znaleźć za pośrednictwem Google. Ciekawe, że Yarv to obsługuje.
Charlie Flowers
15
Damien, okazuje się, że całkowity koszt posiadania jest faktycznie wymagany w przypadku prawdziwych języków OO: patrz projectfortress.sun.com/Projects/Community/blog/… . Nie przejmuj się zbytnio ramami stosu: jest całkowicie możliwe, aby zaprojektować ramy stosu rozsądnie, aby dobrze współpracowały z TCO.
Tony Garnock-Jones
2
tonyg uratował post, do którego odwołuje się GLS przed wymarciem, kopiując
Frank
Robię zadanie domowe , które wymaga mnie rozbierać zestaw zagnieżdżonych tablic arbitralnej głębokości. Oczywistym sposobem jest rekurencja, a podobne przypadki użycia online (które mogę znaleźć) wykorzystują rekurencję. Mój konkretny problem jest bardzo mało prawdopodobny, nawet bez TCO, ale niepokoi mnie fakt, że nie mogę napisać całkowicie ogólnego rozwiązania bez przejścia na iterację.
Izaak Rabinowicz
42

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
Ernest
źródło
12

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

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

Steve Jessop
źródło
W tej chwili łącze jest nieaktywne.
karatedog
@karatedog: dzięki, zaktualizowane. Chociaż szczerze mówiąc, odniesienie jest prawdopodobnie nieaktualne, ponieważ błąd ma teraz 5 lat i od tego czasu zaczęto zajmować się tym samym tematem.
Steve Jessop,
Tak :-) Właśnie przeczytałem o temacie i zobaczyłem, że w Ruby 2.0 można to włączyć z kodu źródłowego (koniec z modyfikacją źródła C i rekompilacją).
karatedog
4

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
Christophera Kuttruffa
źródło
2

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
kelwin
źródło