Conversione di una funzione per ricorrere alla ricorsione in coda: uno studio formale

Question

Qualcuno ha scritto un documento formale che descrive un metodo per convertire (automaticamente) le funzioni in coda ricorsiva? Sto cercando un trattamento formale di livello universitario che includa le limitazioni (tipi di funzioni che possono essere convertite), le procedure per la conversione e, se possibile, le prove di correttezza? Esempi in Haskell sarebbero un bonus.

Answer 1

un metodo per convertire (automaticamente) le funzioni in coda ricorsiva?

Quindi ci sono due parti di questo:

• riconoscendo che una determinata funzione ricorsiva può essere convertito in una forma ricorsiva coda e rendendo tale trasformazione
• coda di esecuzione chiamate in modo efficiente, così la trasformazione vale la pena.

Trasformare ricorsione in coda ricorsione

Risulta avanti relativamente semplice riconoscere coda definizioni ricorsive sintatticamente. Dopo tutto, 'coda ricorsiva' significa solo che la chiamata appare sintatticamente nella coda dell'espressione.

E.g. la gente Schema descrivono:

semplicemente la compilazione di appositi auto-chiamate come i salti non è suficient a raggiungere la piena coda ricorsione. Invece, dividiamo sintatticamente tutte le posizioni di sub-espressione nella lingua di partenza in due classi: tail (o riduzione) posizione e posizione di sottoproblema. Nell'espressione semplice (se alternativa predicate alternativa), la predicate è una posizione di sottoproblema , mentre entrambe le derivate e alternative sono nelle posizioni di riduzione . Questa nozione sintattica può essere facilmente estesa alle sottoespressioni arbitrariamente nidificate .

• Compiling Higher-Order Languages into Fully Tail-Recursive Portable C

funzioni Trasformare in coda le chiamate

La parte difficile della tua domanda è ottimizzazioni per l'identificazione e la trasformazione candidati calcoli ricorsivi in ​​quelli ricorsivi di coda.

Un riferimento è in GHC, che utilizza l'inlining e un'ampia gamma di regole di semplificazione per comprimere le chiamate ricorsive, fino a quando la struttura ricorsiva della coda sottostante rimane.

• Secrets of the GHC inliner

coda Eliminazione

Una volta che avete le vostre funzioni in una forma ricorsiva in coda di chiamata, ti piacerebbe avere quella attuata effiicently. Se riesci a generare un ciclo, è un buon inizio.Se la macchina di destinazione non lo fa, allora il tail call elimination "avrà bisogno di un paio di trucchi. Per citare Odersky e Schinz, citato qui di seguito,

Varie tecniche sono state proposte nel corso degli anni per eliminare generale (e non solo ricorsiva) coda chiede, soprattutto per compilatori destinati C.

... mettere l'intero programma in una grande funzionalità e di simulare funzione telefoniche usando salti diretti o istruzioni switch all'interno di questa funzione.

... a la tecnica popolare è usare un trampolino elastico è una funzione esterna che chiama ripetutamente una funzione interna. Ogni volta che la funzione interna desidera chiamare un'altra funzione, non la chiama direttamente ma semplicemente restituisce la propria identità (ad esempio come chiusura) al trampolino, che quindi fa la stessa chiamata . La crescita illimitata dello stack è quindi evitata, ma alcune prestazioni sono inevitabilmente perse, , soprattutto perché tutte le chiamate effettuate dal trampolino sono chiamate allo a funzioni staticamente sconosciute.

Un'altra tecnica è Henry Baker “Cheney sul MTA” Con la sua tecnica, il programma deve prima essere convertito in continuazione passando stile (CPS), quindi ruotando tutte le chiamate in chiamate di coda, e può quindi essere compilato come di solito. In fase di esecuzione, quando lo stack sta per traboccare, la continuazione corrente dello viene creata e restituita (o longjmped) al trampolino "in attesa" nella parte inferiore dello stack di chiamate.

• Tail call elimination on the Java Virtual Machine, Michel Schinz Martin Odersky 2001

• Henry G. Baker, Jr. CONS non dovrebbe CONS suoi argomenti, parte II: Cheney sul progetto di MTA versione, gennaio 1994.

Answer 2

Mercury contiene un paio di ottimizzazioni per rendere automaticamente ricorsive le cose. (Mercury è un linguaggio di programmazione della logica di purezza dell'applicazione, quindi parla di predicati piuttosto che di funzioni, ma molte delle stesse idee si applicano ai programmi Mercury come a quelli di Haskell. Una differenza molto più grande di logica piuttosto che funzionale è che è rigoroso piuttosto che pigro)

"Introduzione accumulatore" genera versioni specializzate di predicati con un parametro di accumulatore aggiuntivo per consentire lo spostamento delle operazioni associative prima della chiamata ricorsiva. Apparentemente questa ottimizzazione non porta necessariamente a dei predicati ricorsivi, ma spesso si traduce in una forma che può essere ottimizzata dalla seconda ottimizzazione:

"Costruttori modulo ultima chiamata" consente essenzialmente una chiamata ricorsiva che viene seguita solo dalle applicazioni del costruttore che devono essere riscritte in modo tale che il valore sia costruito per primo contenente un "buco" e quindi la chiamata ricorsiva restituisce il suo output direttamente nell'indirizzo di memoria del "buco" anziché utilizzare la normale convenzione di ritorno del valore di ritorno. Credo che Haskell otterrebbe gratuitamente questa ottimizzazione semplicemente a causa della pigrizia.

Entrambe queste ottimizzazioni sono descritte nel documento Making Mercury programs tail recursive.