Posts

April 25, 2011

Tailcall optimization in Ruby

Il commento di Alessandro al mio post precedente ha evidenziato che, con l’approccio descritto, non si potrebbe fare una cosa del tipo:

 proc { true }.while_true do
     puts "Stack overflow?"
 end

perché lo stack si riempirebbe dopo poco.

La soluzione a questo problema è l’implementazione della Tailcall Optimization (TCO). In parole povere si tratta, quando possibile, di rendere iterative le chiamate ricorsive. In teoria, dalla versione 1.9 di Ruby, è possibile abilitare la TCO, ma, o ho sbagliato qualcosa, oppure non funziona come dovrebbe, perché, anche abilitandola, lo stack va in overflow con la ricorsione.

Alla fine ho trovato questa discussione, da cui ho ricavato questo pezzo di codice, dove si sfrutta il meccanismo di catch/throw 1 e un po’ di metaprogrammazione:

 class Class
   def tailcall_optimize(meth)
     org = instance_method(meth)
     define_method(meth) do |*args,&block|
       if Thread.current[meth]
         throw(:recurse,args)
       else
         Thread.current[meth] = org.bind(self)
         result = catch(:done) do
           loop do
             args = catch(:recurse) do
               throw(:done,Thread.current[meth].call(*args,&block))
             end
           end
         end
         Thread.current[meth] = nil
         result
       end
     end
   end
 end

Il metodo tailcall_optimize altera il metodo passato, eliminando la ricorsione. Quindi, se si aggiunge:

 class Proc
     tailcall_optimize :while_true
 end

la ricorsione può continuare all’infinito.


  1. l’interprete Ruby, ad ogni chiamata a throw, cerca nello stack il blocco corrispondente (cioè che ha la stessa label del throw), svuota lo stack fino a quel punto e continua l’esecuzione da lì.