Ruby esegue l'ottimizzazione delle chiamate di coda?

Question

I linguaggi funzionali portano all'uso della ricorsione per risolvere molti problemi, e quindi molti di loro eseguono l'ottimizzazione delle chiamate di coda (TCO). Il TCO fa sì che le chiamate a una funzione da un'altra funzione (o se stessa, nel qual caso questa funzione è anche nota come eliminazione della ricorsione della coda, che è un sottoinsieme di TCO), come ultimo passaggio di quella funzione, non necessitano di un nuovo frame di stack, che riduce il sovraccarico e l'utilizzo della memoria.

Ovviamente Ruby ha "preso in prestito" un certo numero di concetti da linguaggi funzionali (lambda, funzioni come map e così via, ecc.), il che mi incuriosisce: Ruby esegue l'ottimizzazione delle chiamate in coda?

Answer 1

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

La specifica della lingua di Ruby non dice nulla sul TCO. Non dice che devi farlo, ma non dice anche che non puoi farlo. Non puoi affidarti su di esso.

Questo è diverso dallo Schema, in cui la specifica della lingua richiede che tutte le implementazioni devono eseguire il TCO. Ma è anche diverso da Python, in cui Guido van Rossum ha chiarito in più occasioni (l'ultima volta solo un paio di giorni fa) che le implementazioni Python non dovrebbero eseguire il TCO.

Yukihiro Matsumoto è solidale con TCO, semplicemente non vuole forzare tutto le implementazioni per supportarlo. Sfortunatamente, questo significa che non puoi fare affidamento sul TCO o, in caso contrario, il tuo codice non sarà più portabile su 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) è necessario decommentare esplicitamente una riga nel codice sorgente e ricompilare la VM, per attivare il TCO & nbsp; - nelle versioni future sarà attivata per impostazione predefinita, dopo l'implementazione risulta stabile. Parrot Virtual Machine supporta il TCO in modo nativo, quindi anche Cardinal potrebbe facilmente supportarlo. Il CLR ha un supporto per TCO, il che significa che IronRuby e Ruby.NET potrebbero probabilmente farlo. Anche Rubinio potrebbe probabilmente farlo.

Ma JRuby e XRuby non supportano il TCO, e probabilmente non lo faranno, a meno che la JVM stessa non ottenga supporto per il TCO. Il problema è questo: se si desidera avere un'implementazione rapida e un'integrazione rapida e senza soluzione di continuità con Java, è necessario essere compatibili con lo stack con Java e utilizzare lo stack di JVM il più possibile. Puoi facilmente implementare il TCO con trampolini o esplicito stile di passaggio di continuazione, ma poi non stai più usando lo stack JVM, il che significa che ogni volta che vuoi chiamare in Java o chiamare da Java in Ruby, devi eseguire un qualche tipo di conversione, che è lenta. Quindi, XRuby e JRuby hanno scelto di andare con velocità e integrazione Java su TCO e continuazioni (che sostanzialmente 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, immagino che MacRuby avrà lo stesso problema.

Answer 2

Aggiornamento: ecco una bella spiegazione del TCO in Ruby: http: // nithinbekal.com/posts/ruby-tco/

Aggiornamento: potresti anche dare un'occhiata alla tco_method gem: 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'era una proposta per attivare il TCO per impostazione predefinita in Ruby 2.0. Spiega anche alcuni problemi che ne derivano: Ottimizzazione delle chiamate di coda: abilitare per impostazione predefinita?.

Breve estratto dal link:

  

Generalmente, l'ottimizzazione della ricorsione della coda include un'altra tecnica di ottimizzazione - "call" per "saltare" traduzione. Secondo me,   è difficile applicare questa ottimizzazione perché riconoscendo   & Quot; ricorsione " è difficile nel mondo di Ruby.

     

Esempio successivo. invocazione del metodo fact () in " else " la clausola non è una "coda"   chiamare ".

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

  

Se si desidera utilizzare l'ottimizzazione di coda chiamata sul metodo fact (), è necessario   per cambiare il metodo fact () come segue (stile di passaggio di continuazione).

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

Answer 3

Può avere ma non è garantito:

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

Answer 4

Il TCO può anche essere compilato modificando un paio di variabili in vm_opts.h prima di compilare: 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 sulle risposte di J & # 246; rg's ed Ernest. Fondamentalmente dipende dall'implementazione.

Non sono riuscito a ottenere la risposta di Ernest per lavorare sulla risonanza magnetica, ma è fattibile. Ho trovato questo esempio che funziona per la risonanza magnetica da 1.9 a 2.1. Questo dovrebbe stampare un numero molto grande. Se non imposti l'opzione TCO su true, dovresti ottenere lo "stack troppo profondo" di errore.

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