Ruby esegue l'ottimizzazione chiamata coda?

Question

I linguaggi funzionali portano a ricorrere alla ricorsione per risolvere molti problemi, pertanto molti di essi eseguono il TCO (Tail Call Optimization). Il TCO provoca chiamate a una funzione da un'altra funzione (o se stessa, nel qual caso questa funzione è anche nota come eliminazione della ricorsione di coda, che è un sottoinsieme di TCO), come ultimo passaggio di tale funzione, per non richiedere un nuovo stack frame, che riduce il sovraccarico e l'utilizzo della memoria.

Ruby ha ovviamente "preso in prestito" una serie di concetti dai linguaggi funzionali (lambda, funzioni come la mappa e così via, ecc.), Il che mi incuriosisce: Ruby esegue l'ottimizzazione delle chiamate tail?

Answer 1

No, Ruby non esegue il TCO. Tuttavia, anche lo non esegue TCO.

La specifica del linguaggio Ruby non dice nulla sul TCO. Non dice che devi farlo, ma non ti dice neanche che lo non può farlo. Non puoi semplicemente contare su.

Questo è diverso schema, in cui la lingua specifica richiede che tutti Implementazioni deve eseguire TCO. Ma è anche diverso da Python, dove Guido van Rossum ha reso molto chiaro in diverse occasioni (l'ultima volta solo un paio di giorni fa) che le implementazioni Python non dovevano eseguire il TCO.

Yukihiro Matsumoto è in sintonia con il TCO, non vuole forzare lo tutte le implementazioni per supportarlo. Sfortunatamente, questo significa che non puoi fare affidamento sul TCO, o se lo fai, il tuo codice non sarà più portabile ad altre Implementazioni di Ruby.

Quindi, alcune implementazioni di Ruby eseguono il TCO, ma la maggior parte no. YARV, ad esempio, supporta il TCO, anche se (per il momento) devi annullare esplicitamente una riga nel codice sorgente e ricompilare la VM, per attivare il TCO - nelle versioni future sarà attivata per impostazione predefinita, dopo che l'implementazione si sarà dimostrata stabile. Parrot Virtual Machine supporta nativamente il TCO, quindi Cardinal potrebbe tranquillamente supportarlo. Il CLR ha qualche supporto per il TCO, il che significa che IronRuby e Ruby.NET potrebbero probabilmente farlo. Rubinio potrebbe probabilmente farlo anche lui.

Ma JRuby e XRuby non supportano il TCO e probabilmente non lo faranno, a meno che la JVM stessa non supporti il ​​TCO. Il problema è questo: se si desidera un'implementazione rapida e un'integrazione rapida e perfetta con Java, è necessario utilizzare lo stack compatibile con Java e utilizzare lo stack JVM il più possibile. Puoi facilmente implementare il TCO con trampolini o lo stile di passaggio continuo, ma non utilizzerai più lo stack JVM, il che significa che ogni volta che desideri chiamare in Java o chiamare da Java a Ruby, devi eseguire una sorta di conversione, che è lento. Quindi, XRuby e JRuby hanno scelto di andare con velocità e integrazione di Java su TCO e continuazioni (che fondamentalmente hanno lo stesso problema).

Questo vale per tutte le implementazioni di Ruby che desiderano integrarsi strettamente con alcune piattaforme host che non supportano il TCO in modo nativo. Ad esempio, suppongo che MacRuby abbia lo stesso problema.

Answer 2

Può avere, ma non è garantito per:

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

Answer 3

Aggiornamento: Ecco bella spiegazione di TCO in Ruby: http://nithinbekal.com/posts/ruby-tco/

Aggiornamento: Si potrebbe voler controllare anche la tco_method gemma: http://blog.tdg5.com/introducing-the-tco_method-gem/

In Ruby MRI (1.9, 2.0 e 2.1) è possibile attivare il TCO con:

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

C'è stata una proposta da attivare TCO attivato per impostazione predefinita in Ruby 2.0. Si spiega anche alcuni problemi che vengono con che: Tail call optimization: enable by default?.

estratto breve dal link:

In generale, l'ottimizzazione coda ricorsione include un'altra tecnica di ottimizzazione - "chiamata" a "saltare" traduzione. A mio parere, è difficile applicare questa ottimizzazione perché riconoscere la ricorsione " " è difficile nel mondo di Ruby.

Esempio successivo. Il richiamo del metodo fact() nella clausola "else" non è una "coda chiamata".

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

Se si desidera utilizzare l'ottimizzazione coda chiamata sul fatto metodo(), è necessario cambiare il metodo di fatto() come segue (proseguimento passando stile).

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

Answer 4

TCO può anche essere compilato in modificando un paio di variabili vm_opts.h prima della compilazione: 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 

Answer 5

Questo si basa su Jörg e di risposte di Ernest. Fondamentalmente dipende dall'implementazione.

Non ho potuto ottenere la risposta di Ernest per lavorare su MRI, ma è fattibile. Ho trovato this example che funziona con la risonanza magnetica da 1.9 a 2.1. Questo dovrebbe stampare un numero molto grande. Se non si imposta l'opzione TCO su true, si dovrebbe ottenere l'errore "stack troppo profondo".

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