Jaki jest właściwy sposób na wdrożenie bardzo głębokiej rekursji w języku Ruby w sposób * czysty *?

Question

Ruby ma oczywiście rekurencję, podobnie jak każdy inny język programowania wysokiego poziomu. Działa to dobrze, tak długo, jak głębokość rekurencji nie jest zbyt wysoka, ale jeśli tak, to złapiesz przepełnienie stosu:

#!/usr/bin/ruby2.0 
def rec_naive(i) 
    return 1 if i==1 
    rec_naive(i-1) + i 
end 

puts rec_naive(10000) #(Stack size: ~9360) 
#==> test.rb:3: stack level too deep (SystemStackError) 

Najbardziej oczywiste rozwiązanie, które przychodzi do głowy to po prostu zwiększyć rozmiar stosu. Niestety, odpowiedzi na ten temat znalazłem, zmieniając stan systemu operacyjnego w taki czy inny sposób - majstrując przy użyciu kodu źródłowego tłumacza Ruby, ulimit, kompilując flagi i tym podobne - co jest czystym Rubinem i, oczywiście, nie zawsze jest możliwe, szczególnie w bezpiecznym środowisku. Tak, mniej oczywistych rozwiązań przybywających do umysłu są przepisać funkcję przestępstwa w non-rekurencyjne sposób lub reimplement stos numerem:

# Recursion-free way 
def rec_norecurse(i) 
    acc = 0 
    (1..i).each do |n| 
     acc += n 
    end 
    return acc 
end 
puts rec_norecurse(100) 

# Reimplementing the call stack 
StackFrame = Struct.new(:state, :args) 
def rec_customstack(stack) 
    lastresult = nil 
    until stack.empty? 
     frame = stack.last 
     state, args = frame.state, frame.args 
     i = args[0] 

     case state 
      when :entrance_point 
       if i==1 
        #-- return 1 #-- 
        lastresult = 1 
        stack.pop 
        #--------------- 
       else 
        #-- rec(i-1) #-- 
        stack.last.state = :returned_from_recursion 
        stack << StackFrame.new(:entrance_point, [i-1]) 
        #--------------- 
       end 
      when :returned_from_recursion 
       #-- return rec_result+i #-- 
       lastresult = lastresult + i 
       stack.pop 
       #-------------------------- 
     end 
    end 
    return lastresult 
end 
customstack = [StackFrame.new(:entrance_point, [100])] 
puts rec_customstack(customstack) 

jednak przepisanie nawet niezbyt złożonych funkcji w ten sposób może być żmudne zadanie , a wynikowy kod wydaje się być zbyt zagracony i zasłonięty w porównaniu do oryginału. Chciałem zaimplementować jakieś metaprogramowanie i napisać coś w rodzaju "opakowania", które mogłoby sprawić, że funkcja zawijana zachowa się właściwie z głęboką rekurencją, a jednocześnie będzie wystarczająco czysta, nawet jeśli nie będzie wyglądała dokładnie tak, jak nieopakowana. Zaimplementowałem rozwiązanie z Fibers, które początkowo wydawało się wystarczająco dobre, ale wtedy napotkałem pewne niespodziewane trudności (szczegóły: see the related question).

Poszukuję prawa i czystych - z najmniejszą ilością zakłóceń i zaciemnień, jak to tylko możliwe - sposób realizacji bardzo głębokich wywołań rekurencyjnych bez zbytniego obciążania wydajności.

Answer 1

Wymyśliłem to rozwiązanie. Wciąż jest daleki od doskonałości, ale wydaje się być wystarczająco dobry pod nieobecność lepszych pomysłów. Zasadniczo dzieli funkcję punktu rekurencyjnego wywołania i odkłada żadnych obliczeń, które muszą być wykonane po blokami:

def rcall(*args, &block) 
    cs = [nil] #Call Stack 
    rec = false 
    rcaller = proc do |*pargs, &pblock| 
     # Enqueue and return control to rcall 
     rec = true # We *are* doing rcall 
     cs << pblock 
     pargs 
    end 
    result = args 
    until cs.empty? 
     rec = false 

     result = block.call(rcaller, *result) 
     while (!rec) && (!cs.empty?) 
      # we got result! Return it to past preproc call and work it :3 
      lastblock = cs.pop 
      result = lastblock.call(*result) if !lastblock.nil? 
     end 
    end 
    return result 
end 

Zastosowanie:

puts (rcall 100 do |rcaller, i| 
    if i==1 
     1 
    else 
     rcaller.(i-1) {|i2| 
      i2+i 
     } 
    end 
end) 
# ==> 5050 

To jest nawet wolniejszy niż reimplementacja stosu wywołań , ale wygląda o wiele czystsze. A jeśli nie są wymagane obliczenia po rcall, wygląda nawet lepiej, podobny do tego z prostego ogona-Call -

puts (rcall(100, []) do |rcaller, i, acc| 
    if i==1 
     [1, *acc] 
    else 
     rcaller.(i-1, [i, *acc]) 
    end 
end).join', ' 
#==> 1, 2, 3..., 99, 100 

Answer 2

Inną opcją jest użycie tail-call optimization aby umożliwić kompilator produkować iteracyjny kod zamiast metod pchających oraz argumenty na stosie:

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

RubyVM::InstructionSequence.new(<<-EOF).eval 
    def sum_down(n, acc=1) 
    return acc if n == 1 
    return sum_down(n-1, n+acc) 
    end 
EOF 

puts sum_down(100) # => 5050 
puts sum_down(100000) # => 5000050000 

metoda ta jest odporna na przepełnienie stosu i powinno być szybkie, jak równoważne metody iteracyjnej.

Aby uzyskać meta-programistyczne rozwiązanie optymalizujące funkcję rekurencji ogona, patrz Tail Call Optimization in Ruby. Kluczem do wyciągnięcia tej sztuczki jest uzyskanie źródła metody za pomocą method_source.