Ruby esegue l’ottimizzazione delle chiamate tail?

I linguaggi funzionali portano all’uso della ricorsione per risolvere molti problemi, e quindi molti di essi eseguono l’ottimizzazione delle chiamate tail (TCO). 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.

Ovviamente Ruby ha “preso in prestito” una serie di concetti dai linguaggi funzionali (lambda, funzioni come la mappa e così via, ecc.), Il che mi rende curioso: Ruby esegue l’ottimizzazione delle chiamate tail?

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

La specifica del linguaggio Ruby non dice nulla sul TCO. Non dice che devi farlo, ma non dice nemmeno che non puoi farlo. Non puoi fare affidamento su di esso.

Questo è diverso da Scheme, dove la specifica della lingua richiede che tutte le implementazioni debbano eseguire il 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 è solidale con il TCO, non vuole forzare tutte le implementazioni a 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 triggersre il TCO – nelle versioni future sarà triggersta 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.

JRuby e XRuby però non supportano il TCO e probabilmente non lo faranno, a meno che la stessa JVM 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ù ansible. 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 piattaforms host che non supportano il TCO in modo nativo. Ad esempio, suppongo che MacRuby abbia lo stesso problema.

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

Aggiornamento: potresti anche controllare la gem tco_method : http://blog.tdg5.com/introducing-the-tco_method-gem/

In Ruby MRI (1.9, 2.0 e 2.1) è ansible triggersre il TCO con:

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

C’era una proposta per trasformare il TCO in default in Ruby 2.0. Spiega anche alcuni problemi che si presentano con: Ottimizzazione chiamata coda: abilita di default ?.

Breve estratto dal link:

In generale, l’ottimizzazione della coda-ricorsione include un’altra tecnica di ottimizzazione: la “chiamata” alla traduzione “salta”. A mio parere, è difficile applicare questa ottimizzazione perché riconoscere la “ricorsione” è difficile nel mondo di Ruby.

Prossimo esempio 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 tail-call sul metodo fact (), è necessario modificare il metodo fact () nel modo seguente (stile di passaggio continuo).

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

Può avere ma non è garantito a:

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

Il TCO può anche essere compilato modificando un paio di variabili in 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 

Questo si basa sulle risposte di Jörg 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 MRI 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 pe end