Topic: PyTCO - Tail Call Optimization  (Letto 752 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline GlennHK

  • python sapiens sapiens
  • ******
  • Post: 1.655
  • Punti reputazione: 1
    • Mostra profilo
    • La Tana di GlennHK
PyTCO - Tail Call Optimization
« il: Agosto 06, 2014, 15:46 »
Ciao, oggi propongo un'idea che mi è venuta in mente ieri, ovvero l'implementazione di un decoratore che ottimizza l'esecuzione delle funzioni tail-recursive. (Per chi non lo sapesse o non se lo ricorda, una funzione è tail-recursive se è ricorsiva e tutte le chiamate ricorsive sono alla fine dei un path di esecuzione). Queste funzioni possono essere ottimizzate e trasformate in iterazioni, il metodo che mi è venuto in mente è il seguente:

  • Racchiudere tutto il body della funzione in un while True
  • Sostituire le chiamate con degli assegnamenti alle variabili con i nuovi valori
  • Appendere dopo gli assegnamenti un continue

I più attenti diranno: "ma se aggiungi un continue e c'è un ciclo annidato?". Ci ho pensato, ma delle chiamate ricorsive dentro un ciclo non sono tail-recursive.

Il decoratore che ho implementato effettua queste modifiche tramite ast e un modulo esterno chiamato astunparse. Per ora sono supportate solo chiamate ricorsive senza keyword arguments o star arguments, in futuro si potrebbero aggiungere. L'unica cosa che non mi piace è la parte in cui il codice viene eseguito, se qualcuno ha dei suggerimenti sono ben accetti!

Il link su GitHub del progetto è https://github.com/DavideCanton/pytco.

Offline GlennHK

  • python sapiens sapiens
  • ******
  • Post: 1.655
  • Punti reputazione: 1
    • Mostra profilo
    • La Tana di GlennHK
Re: PyTCO - Tail Call Optimization
« Risposta #1 il: Settembre 01, 2014, 13:58 »
up?

Offline riko

  • python deus
  • *
  • moderatore
  • Post: 7.453
  • Punti reputazione: 12
    • Mostra profilo
    • RiK0 Tech Temple
Re: PyTCO - Tail Call Optimization
« Risposta #2 il: Settembre 01, 2014, 15:41 »
up?

or down?

non ho avuto tempo di guardarci... e si, e' un bel progetto.

Diciamo che pero' lo trovo un interessante esercizio di stile e un ottimo modo per imparare cose sugli internals.
Ovviamente in produzione prenderei a calci qualcuno che lo usasse, perche' il modo "giusto" e' non usare ricorsione (specie se si ha idea che lo stack scoppi).

L'altro problema e' che e' una trasformazione *fuori* dalla semantica di Python.
« Ultima modifica: Settembre 01, 2014, 15:43 da riko »

Offline GlennHK

  • python sapiens sapiens
  • ******
  • Post: 1.655
  • Punti reputazione: 1
    • Mostra profilo
    • La Tana di GlennHK
Re: PyTCO - Tail Call Optimization
« Risposta #3 il: Settembre 01, 2014, 16:06 »
up?

or down?

non ho avuto tempo di guardarci... e si, e' un bel progetto.

Diciamo che pero' lo trovo un interessante esercizio di stile e un ottimo modo per imparare cose sugli internals.
Ovviamente in produzione prenderei a calci qualcuno che lo usasse, perche' il modo "giusto" e' non usare ricorsione (specie se si ha idea che lo stack scoppi).

L'altro problema e' che e' una trasformazione *fuori* dalla semantica di Python.

Up & Down :D

Si, sono d'accordo che è fuori dalla semantica di Python, però mi è sembrato interessante come problema non banale da risolvere. Vorrei più che altro qualche parere sulla qualità del codice, visto che sono alle prime armi in questo campo particolare