Defunzionalizzazione - Defunctionalization

Nei linguaggi di programmazione , la defunzionalizzazione è una trasformazione in fase di compilazione che elimina le funzioni di ordine superiore , sostituendole con una singola funzione di applicazione del primo ordine . La tecnica è stata descritta per la prima volta da John C. Reynolds nel suo articolo del 1972, "Interpreti definitivi per linguaggi di programmazione di ordine superiore". L'osservazione di Reynolds era che un dato programma contiene solo un numero finito di astrazioni di funzioni, in modo che ciascuna possa essere assegnata e sostituita da un identificatore univoco. Ogni applicazione di funzione all'interno del programma viene quindi sostituita da una chiamata alla funzione di applicazione con l'identificatore della funzione come primo argomento. L' unico compito della funzione apply è quello di inviare questo primo argomento e quindi eseguire le istruzioni indicate dall'identificatore della funzione sugli argomenti rimanenti.

Una complicazione a questa idea di base è che le astrazioni delle funzioni possono fare riferimento a variabili libere . In tali situazioni, la defunzionalizzazione deve essere preceduta dalla conversione di chiusura (lambda lifting) , in modo che qualsiasi variabile libera di un'astrazione di funzione venga passata come argomenti aggiuntivi da applicare . Inoltre, se le chiusure sono supportate come valori di prima classe , diventa necessario rappresentare queste associazioni acquisite creando strutture di dati.

Invece di avere un unico applicare funzione invio su tutti astrazioni funzione in un programma, vari tipi di analisi del flusso di controllo (comprese le distinzioni semplici basate su arity o firma tipo ) possono essere utilizzati per determinare quale funzione (s) possono essere richiamati in ogni applicazione funzione sito e si può invece fare riferimento a una funzione di richiesta specializzata . In alternativa, la lingua di destinazione può supportare chiamate indirette tramite puntatori a funzione , che possono essere più efficienti ed estensibili rispetto a un approccio basato sull'invio.

Oltre al suo uso come tecnica di compilazione per linguaggi funzionali di ordine superiore , la defunzionalizzazione è stata studiata (in particolare da Olivier Danvy e collaboratori) come un modo per trasformare meccanicamente gli interpreti in macchine astratte . La defunzionalizzazione è anche correlata alla tecnica della programmazione orientata agli oggetti di rappresentare funzioni tramite oggetti funzione (in alternativa alle chiusure).

Esempio

Questo è un esempio dato da Olivier Danvy , tradotto in Haskell:

Dato il tipo di dati Tree: 

data Tree a = Leaf a
            | Node (Tree a) (Tree a)

Defunzionalizzeremo il seguente programma: 

cons :: a -> [a] -> [a]
cons x xs = x : xs

o :: (b -> c) -> (a -> b) -> a -> c
o f g x = f (g x)

flatten :: Tree t -> [t]
flatten t = walk t []

walk :: Tree t -> [t] -> [t]
walk (Leaf x)     = cons x
walk (Node t1 t2) = o (walk t1) (walk t2)

Defunzionalizziamo sostituendo tutte le funzioni di ordine superiore (in questo caso oè l'unica funzione di ordine superiore) con un valore del Lamtipo di dato, e invece di chiamarle direttamente, introduciamo una applyfunzione che interpreta il tipo di dato: 

data Lam a = LamCons a
           | LamO (Lam a) (Lam a)

apply :: Lam a -> [a] -> [a]
apply (LamCons x)  xs = x : xs
apply (LamO f1 f2) xs = apply f1 (apply f2 xs)

cons_def :: a -> Lam a
cons_def x  = LamCons x

o_def :: Lam a -> Lam a -> Lam a
o_def f1 f2 = LamO f1 f2

flatten_def :: Tree t -> [t]
flatten_def t = apply (walk_def t) []

walk_def :: Tree t -> Lam t
walk_def (Leaf x)     = cons_def x
walk_def (Node t1 t2) = o_def (walk_def t1) (walk_def t2)

Guarda anche

Riferimenti

  • Reynolds, John (agosto 1972). "Interpreti definitivi per linguaggi di programmazione di ordine superiore". Atti del Convegno Annuale ACM . Boston, Massachusetts. pp. 717-740. doi : 10.1145/800194.805852 .
  • Danvy, Olivier ; Nielsen, Lasse R. (2001). "Defunzionalizzazione al lavoro" (PDF) . Atti del Convegno ACM SIGPLAN sui Principi e la Pratica della Programmazione Dichiarativa . pp. 162-174. doi : 10.1145/773184.773202 .(Versione più completa: Relazione tecnica BRICS-RS-01-23 )
  • Danvy, Olivier ; Millikin, Kevin R. (giugno 2009). "Rifunzionalizzazione al lavoro" . Scienza della programmazione informatica . 74 (8): 534-549. doi : 10.1016/j.scico.2007.10.007 .(Disponibile anche come Rapporto tecnico BRICS-RS-07-7 )

link esterno