Efficienza della programmazione puramente funzionale

Qualcuno sa qual è il peggior rallentamento asintotico ansible che può accadere quando si programma puramente funzionalmente rispetto all’imperativo (cioè permettendo effetti collaterali)?

Chiarimento dal commento di itowlson : c’è qualche problema per il quale l’algoritmo non distruttivo più noto è asintoticamente peggiore dell’algoritmo distruttivo più noto e, in caso affermativo, di quanto?

Secondo Pippenger [1996] , quando si confronta un sistema Lisp che è puramente funzionale (e ha una semantica di valutazione rigorosa, non pigro) a uno che può mutare i dati, un algoritmo scritto per il Lisp impuro che viene eseguito in O ( n ) può essere tradotto ad un algoritmo nel puro Lisp che gira in tempo O ( n log n ) (basato sul lavoro di Ben-Amram e Galil [1992] sulla simulazione della memoria ad accesso casuale usando solo i puntatori). Pippenger stabilisce anche che esistono algoritmi per i quali è meglio che tu possa fare; ci sono problemi che sono O ( n ) nel sistema impuro che sono Ω ( n log n ) nel sistema puro.

Ci sono alcune avvertenze da fare su questo documento. Il più significativo è che non affronta i linguaggi funzionali pigri, come Haskell. Bird, Jones e De Moor [1997] dimostrano che il problema costruito da Pippenger può essere risolto in un linguaggio funzionale pigro nel tempo O ( n ), ma non stabiliscono (e per quanto ne so, nessuno lo ha) se o non un linguaggio funzionale pigro può risolvere tutti i problemi nello stesso tempo di esecuzione asintotico come un linguaggio con mutazione.

Il problema costruito da Pippenger richiede che Ω ( n log n ) sia specificamente costruito per ottenere questo risultato e non sia necessariamente rappresentativo di problemi pratici reali. Ci sono alcune restrizioni sul problema che sono un po ‘inaspettate, ma necessarie affinché la dimostrazione funzioni; in particolare, il problema richiede che i risultati siano calcolati on-line, senza essere in grado di accedere all’input futuro e che l’input sia costituito da una sequenza di atomi da un insieme illimitato di possibili atomi, piuttosto che da un set di dimensioni fisse. E la carta stabilisce solo i risultati (limite inferiore) per un algoritmo impuro di tempo lineare di esecuzione; per problemi che richiedono un tempo di esecuzione maggiore, è ansible che il fattore O aggiuntivo (log n ) visto nel problema lineare possa essere “assorbito” nel processo di operazioni aggiuntive necessarie per algoritmi con tempi di esecuzione maggiori. Questi chiarimenti e domande aperte sono esplorate brevemente da Ben-Amram [1996] .

In pratica, molti algoritmi possono essere implementati in un linguaggio funzionale puro con la stessa efficienza di un linguaggio con strutture dati mutabili. Per un buon riferimento alle tecniche da usare per implementare efficientemente strutture dati puramente funzionali, si veda “Purely Functional Data Structures” di Chris Okasaki [Okasaki 1998] (che è una versione ampliata della sua tesi [Okasaki 1996] ).

Chiunque abbia bisogno di implementare algoritmi su strutture dati puramente funzionali dovrebbe leggere Okasaki. Puoi sempre peggiorare un rallentamento di O (log n ) per operazione simulando la memoria mutabile con un albero binario bilanciato, ma in molti casi puoi fare decisamente meglio di così, e Okasaki descrive molte tecniche utili, dalle tecniche ammortizzate a quelle reali. quelli di tempo che fanno il lavoro ammortizzato in modo incrementale. Strutture di dati puramente funzionali possono essere un po ‘difficili da lavorare e analizzare, ma offrono molti vantaggi come la trasparenza referenziale che sono utili nell’ottimizzazione del compilatore, nell’elaborazione parallela e distribuita e nell’implementazione di funzioni come versioning, undo e rollback.

Si noti inoltre che tutto ciò discute solo i tempi di corsa asintotici. Molte tecniche per l’implementazione di strutture dati puramente funzionali forniscono una certa quantità di rallentamento costante dei fattori, a causa della contabilità aggiuntiva necessaria per il loro funzionamento e dei dettagli di implementazione della lingua in questione. I vantaggi delle strutture di dati puramente funzionali possono superare questi rallentamenti dei fattori costanti, quindi in genere è necessario fare dei compromessi in base al problema in questione.

Riferimenti

  • Ben-Amram, Amir e Galil, Zvi 1992. “Puntatori contro indirizzi” Journal of ACM, 39 (3), pp. 617-648, luglio 1992
  • Ben-Amram, Amir 1996. “Note sul confronto tra Pippenger di pura e impura Lisp” Manoscritto non pubblicato, DIKU, Università di Copenhagen, Danimarca
  • Bird, Richard, Jones, Geraint e De Moor, Oege 1997. “Più fretta, meno velocità: valutazione pigra contro entusiasta” Journal of Functional Programming 7, 5, pp. 541-547, settembre 1997
  • Okasaki, Chris 1996. Tesi di dottorato “Strutture puramente funzionali” , Carnegie Mellon University
  • Okasaki, Chris 1998. “Purely Functional Data Structures” Cambridge University Press, Cambridge, Regno Unito
  • Pippenger, Nicholas 1996. “Pure Versus Impure Lisp” Convegno ACM sui principi dei linguaggi di programmazione, pagine 104-109, gennaio 1996

Esistono infatti numerosi algoritmi e strutture dati per le quali non è nota alcuna soluzione puramente funzionale asintoticamente efficiente (quella implementabile nel calcolo lambda puro), anche con la pigrizia.

  • La summenzionata unione-trova
  • Tabelle hash
  • Array
  • Alcuni algoritmi grafici

Tuttavia, assumiamo che in linguaggi “imperativi” l’accesso alla memoria sia O (1) mentre in teoria non può essere così asintoticamente (cioè per dimensioni dei problemi illimitate) e l’accesso alla memoria all’interno di un enorme set di dati è sempre O (log n) , che può essere emulato in un linguaggio funzionale.

Inoltre, dobbiamo ricordare che in realtà tutti i linguaggi funzionali moderni forniscono dati mutabili, e Haskell lo fornisce senza sacrificare la purezza (la monade ST).

Questo articolo afferma che le note implementazioni puramente funzionali dell’algoritmo di ritrovamento dell’unione presentano tutte una peggiore complessità asintotica di quella che pubblicano, che ha un’interfaccia puramente funzionale ma utilizza internamente dati mutabili.

Il fatto che altre risposte affermino che non ci può mai essere alcuna differenza e che, ad esempio, l’unico “inconveniente” del codice puramente funzionale è che può essere parallelizzato ti dà un’idea della consapevolezza / obiettività della comunità di programmazione funzionale su questi argomenti .

MODIFICARE:

I commenti sottostanti sottolineano che una discussione parziale dei pro e contro della pura programmazione funzionale potrebbe non venire dalla “comunità di programmazione funzionale”. Buon punto Forse gli avvocati che vedo sono solo, per citare un commento, “analfabeti”.

Per esempio, penso che questo post di blog sia stato scritto da qualcuno che potrebbe essere considerato rappresentante della comunità di programmazione funzionale, e dato che è una lista di “punti per valutazione pigra”, sarebbe un buon posto per menzionare qualsiasi inconveniente che programmazione pigra e puramente funzionale. Un buon posto sarebbe stato al posto del seguente (tecnicamente vero, ma tendenzioso fino al punto di non essere divertente) licenziamento:

Se una funzione rigorosa ha complessità O (f (n)) in un linguaggio rigoroso, allora ha anche complessità O (f (n)) in un linguaggio pigro. Perché preoccuparsi? 🙂

Con un limite superiore fisso sull’utilizzo della memoria, non dovrebbero esserci differenze.

Schermata di prova: dato un limite superiore fisso sull’utilizzo della memoria, si dovrebbe essere in grado di scrivere una macchina virtuale che esegue un insieme di istruzioni imperativo con la stessa complessità asintotica come se si stesse effettivamente eseguendo su quella macchina. Questo perché è ansible gestire la memoria mutabile come una struttura di dati persistente, dando O (log (n)) in lettura e scrittura, ma con un limite superiore fisso sull’utilizzo della memoria, è ansible avere una quantità fissa di memoria, causando questi a decadimento a O (1). Quindi l’implementazione funzionale può essere la versione imperativa in esecuzione nell’implementazione funzionale della VM, e quindi entrambi dovrebbero avere la stessa complessità asintotica.

Suggerirei di leggere le performance di Haskell e di dare un’occhiata ai benchmark delle prestazioni di gioco per linguaggi funzionali rispetto a quelli procedurali / OO.

“Funzionale” è un insieme di caratteristiche diverse, ognuna delle quali è indipendentemente utile, e la sua trovata è più utile per guardarle individualmente.

Immutabilità

Ora che mi è familiare, ogni volta che riesco a farla franca restituendo un risultato immutabile, cerco sempre di farlo anche in un programma orientato agli oggetti. È più semplice ragionare sul programma se si dispone di dati di tipo valore.

Funziona come un primo tipo di class

Qualunque cosa tu voglia chiamarla, passando per delegati, azioni o funzioni, è un modo davvero pratico per risolvere un’intera class di problemi del mondo reale, come il “buco nel modello centrale”.

Essere in grado di comporre le funzioni (ad esempio, trasformare Action in solo Action è anche molto utile in alcuni scenari.

Dovremmo anche notare la syntax Lambda qui, perché si ottiene solo la syntax Lambda quando si promuovono le funzioni in tipi di prima class. La syntax Lambda può essere molto espressiva e concisa.

monadi

Questo è un costrutto sottile ma molto potente. È potente quanto la parola chiave yield utilizzata per creare classi IEnumerable in C #. Essenzialmente sta costruendo una macchina di stato per te sotto le coperte, ma la tua logica sembra lineare.

Valutazione e ricaduta pigra

Li ho messi insieme perché, mentre sono sempre concentrati come funzionalità di programmazione funzionale, si sono fatti strada così velocemente in linguaggi altrimenti imperativi che è difficile chiamarli più funzionali.

S-Espressioni

Immagino di non essere sicuro di dove metterlo, ma la possibilità di trattare il codice non compilato come un object (e controllarlo / modificarlo), come Lisp S-Expressions o LINQ Expressions, è, in qualche modo, lo strumento più potente della programmazione funzionale. La maggior parte delle nuove interfacce “fluenti” .NET e DSL utilizzano una combinazione di syntax lambda e LINQ Expressions per creare alcune API molto concise. Per non parlare di Linq2Sql / Linq2Nhibernate in cui il codice C # è “magicamente” eseguito come SQL anziché come codice C #.