Sembra che valutazione pigra di espressioni possa far perdere il controllo del programmatore sull'ordine in cui viene eseguito il codice. Ho difficoltà a capire perché questo sia accettabile o desiderato da un programmatore.
Come può essere usato questo paradigma per costruire un software prevedibile che funzioni come previsto, quando non abbiamo alcuna garanzia su quando e dove verrà valutata un'espressione?
Molte risposte stanno entrando in cose come elenchi infiniti e guadagni in termini di prestazioni da parti non calcolate del calcolo, ma questo manca della motivazione più grande per la pigrizia: modularità .
L'argomentazione classica è esposta nel tanto citato articolo "Perché funzionale Questioni di programmazione "(collegamento PDF) di John Hughes. L'esempio chiave di quel documento (Sezione 5) sta giocando a Tic-Tac-Toe usando l'algoritmo di ricerca alfa-beta. Il punto chiave è (pagina 9):
[Lazy evaluation] makes it practical to modularize a program as a generator that constructs a large number of possible answers, and a selector that chooses the appropriate one.
Il programma Tic-Tac-Toe può essere scritto come una funzione che genera l'intero albero di gioco a partire da una determinata posizione, e una funzione separata che la consuma. A runtime ciò non genera intrinsecamente l'intero albero di gioco, ma solo le sottoparti di cui il consumatore ha effettivamente bisogno. Possiamo cambiare l'ordine e la combinazione in cui le alternative sono prodotte cambiando il consumatore; non c'è bisogno di cambiare il generatore.
In un linguaggio appassionato, non puoi scriverlo in questo modo perché probabilmente impiegheresti troppo tempo e memoria per generare l'albero. Quindi finisci entrambi:
How can this paradigm be used to build predictable software that works as intended, when we have no guarantee when and where an expression will be evaluated?
Quando un'espressione è priva di effetti collaterali, l'ordine in cui vengono valutate le espressioni non influisce sul loro valore, quindi il comportamento del programma non è influenzato dall'ordine. Quindi il comportamento è perfettamente prevedibile.
Ora gli effetti collaterali sono una cosa diversa. Se gli effetti collaterali potrebbero verificarsi in qualsiasi ordine, il comportamento del programma sarebbe effettivamente imprevedibile. Ma questo non è in realtà il caso. Linguaggi pigri come Haskell rendono un punto di riferimento trasparente, cioè assicurandosi che l'ordine in cui vengono valutate le espressioni non influenzerà mai il loro risultato. In Haskell questo si ottiene forzando tutte le operazioni con effetti collaterali visibili all'utente all'interno della monade IO. Questo assicura che tutti gli effetti collaterali si verifichino esattamente nell'ordine che ti aspetti.
Se hai familiarità con i database, un modo molto frequente per elaborare i dati è:
select * from foobar
Non si controlla come viene generato il risultato e in quale modo (indici? scansioni complete della tabella?), o quando (dovrebbero essere generati tutti i dati contemporaneamente o in modo incrementale quando richiesto?). Tutto ciò che sai è: se ci sono più dati, lo otterrai quando lo chiedi.
La valutazione pigra è abbastanza vicina alla stessa cosa. Supponi di avere una lista infinita definita come. la sequenza di Fibonacci - se hai bisogno di cinque numeri, ottieni cinque numeri calcolati; se hai bisogno di 1000 ottieni 1000. Il trucco è che il runtime sa cosa fornire dove e quando. È molto, molto utile.
(I programmatori Java possono emulare questo comportamento con Iterators - altre lingue possono avere qualcosa di simile)
Considera chiedere al tuo database un elenco dei primi 2000 utenti i cui nomi iniziano con "Ab" e hanno più di 20 anni. Inoltre devono essere maschi.
Ecco un piccolo diagramma.
You Program Processor
------------------------------------------------------------------------------
Get the first 2000 users ---------->---------- OK!
--------------------- So I'll go get those records...
WAIT! Also, they have to ---------->---------- Gotcha!
start with "Ab"
--------------------- NOW I'll get them...
WAIT! Make sure they're ---------->---------- Good idea Boss!
over 20!
--------------------- Let's go then...
And one more thing! Make ---------->---------- Anything else? Ugh!
sure they're male!
No that is all. :( ---------->---------- FINE! Getting records!
--------------------- Here you go.
Thanks Postgres, you're ---------->---------- ...
my only friend.
Come puoi vedere da questa terribile interazione, il "database" non sta facendo nulla finché non è pronto a gestire tutte le condizioni. È il risultato di caricare pigro ad ogni passo e applicare ogni volta nuove condizioni.
Al contrario di ottenere i primi 2000 utenti, restituendoli, filtrandoli per "Ab", restituendoli, filtrandoli per oltre 20, restituendoli, filtrandoli per il maschio e infine restituendoli.
Caricamento lento in poche parole.
Lazy evaluation of expressions will cause the designer of a given piece of code lose control over the sequence their code is executed.
Il progettista non dovrebbe preoccuparsi dell'ordine in cui vengono valutate le espressioni purché il risultato sia lo stesso. Ritardando la valutazione, potrebbe essere possibile evitare di valutare alcune espressioni del tutto, il che consente di risparmiare tempo.
Puoi vedere la stessa idea al lavoro a un livello inferiore: molti microprocessori sono in grado di eseguire le istruzioni fuori servizio, il che consente loro di usare le loro varie unità di esecuzione in modo più efficiente. La chiave è che guardano le dipendenze tra le istruzioni ed evitano di riordinare dove cambierebbe il risultato.
Ci sono diversi argomenti per la valutazione lazy che penso siano convincenti
Modularità con una valutazione lenta puoi rompere il codice in parti. Ad esempio, supponiamo di avere il problema di "trovare i primi dieci reciproci di elementi in una lista in modo tale che i reciproci siano inferiori a 1." In qualcosa come Haskell puoi scrivere
take 10 . filter (<1) . map (1/)
ma questo è solo errato in un linguaggio rigoroso, dal momento che se lo assegni a [2,3,4,5,6,7,8,9,10,11,12,0] dovrai dividerlo per zero. Vedi la risposta di Sacundim sul perché questo è fantastico in pratica
Altre cose funzionano Strictly (pun intended) più programmi terminano con una valutazione non rigorosa rispetto a una valutazione rigorosa. Se il tuo programma termina con una strategia di valutazione "avida", terminerà con uno "pigro", ma l'oposite non è vera. Ottieni cose come strutture di dati infiniti (che sono davvero solo abbastanza interessanti) come esempi specifici di questo fenomeno. Più programmi funzionano in lingue pigre.
Ottimalità la valutazione Call-by-need è asintoticamente ottimale rispetto al tempo. Sebbene i principali linguaggi "pigri" (che essenzialmente sono Haskell e Haskell) non promettano la necessità di chiamare, è possibile prevedere più o meno un modello di costo ottimale. Gli analizzatori di rigidità (e la valutazione speculativa) mantengono il sovraccarico in pratica. Lo spazio è una questione più complicata.
Forces Purity utilizzando la valutazione lazy rende il trattamento degli effetti collaterali in modo indisciplinato un dolore totale, perché, come dici tu, il programmatore perde il controllo. Questa è una buona cosa. La trasparenza referenziale rende la programmazione, il rifrattore e il ragionamento sui programmi molto più semplici. I linguaggi rigorosi inevitabilmente si riducono alla pressione di avere pezzi impuri - qualcosa che Haskell e Clean hanno resistito magnificamente. Questo non vuol dire che gli effetti collaterali siano sempre cattivi, ma controllarli è così utile che questa ragione da sola è sufficiente per usare le lingue pigre.
Supponiamo che tu abbia molti calcoli costosi offerti, ma non sai quali saranno effettivamente necessari o in quale ordine. Potresti aggiungere un complicato protocollo mother-may-i forzare il consumatore a capire cosa è disponibile e fare calcoli che non sono ancora stati eseguiti. O potresti semplicemente fornire un'interfaccia che agisce come se fossero i calcoli tutto fatto.
Supponiamo inoltre di avere un risultato infinito. L'insieme di tutti i numeri primi, per esempio. È ovvio che non è possibile calcolare l'insieme in anticipo, quindi qualsiasi operazione nel dominio dei primi deve essere pigra.
con una valutazione lenta non si perde il controllo sull'esecuzione del codice, è comunque assolutamente deterministico. È difficile abituarsi, però.
La valutazione pigra è utile perché è un modo di ridurre il termine lambda che termina in alcuni casi, dove la valutazione impaziente fallirà, ma non viceversa. Ciò comprende 1) quando devi collegare al risultato del calcolo prima di eseguire effettivamente il calcolo, ad esempio, quando costruisci la struttura del grafico ciclico, ma vuoi farlo in uno stile funzionale 2) quando definisci una struttura di dati infinita, ma utilizza questo feed di struttura per utilizzare solo parte della struttura dati.
Leggi altre domande sui tag functional-programming haskell