Eager contro Lazy Haskell. Elenchi infiniti possibili nelle lingue Eager?

Question

Apparentemente è possibile implementare Haskell in modo che valuti senza cambiare la semantica della lingua. Se questo è vero, come sono gestite le strutture dati infinite?

http://csg.csail.mit.edu/pubs/haskell.html

Pertanto, una grande quantità di tempo è trascorso creando e distruggendo parti sospese di calcolo (thunks). Troppo spesso, questi calcoli sono abbastanza semplici che sarebbe altrettanto semplice valutarli. Faxen e altri hanno utilizzato analisi statiche per esporre tali opportunità di entusiasmo. Noi invece proponiamo di usare l'entusiasmo ovunque, mentre utilizziamo meccanismi che ci permettono di recuperare se il nostro programma è troppo avido.

L'elemento chiave è "abbiamo meccanismi per recuperare se il nostro programma è troppo impaziente". Quali sono questi meccanismi? In che modo consentono per le strutture dati infinite e gli altri aspetti della valutazione pigra che sono stato indotto a credere che sono impossibili in un linguaggio volgare?

Answer 1

Non è proprio vero: è possibile valutare i termini Haskell con entusiasmo se si dimostra che non divergeranno.

Ad esempio, quando si vede f x, si potrebbe eseguire prima fino a 1000 passi di x (arresto se si raggiunge WHNF (testa debole forma normale) o un errore), e poi passarlo a f - la semantica viene conservata, ma se pensi che x debba essere valutato, allora puoi fare in modo che ciò accada in anticipo come un'ottimizzazione.

Se x = fix id, si arrenderà dopo 1.000 passaggi di non andare da nessuna parte. Se x = undefined, causerà un errore e si arrenderà (ripristinando il thunk originale e passandolo a f). E così via.

Se x = [1..], allora potrebbe finire riducendolo a 1 : 2 : 3 : ... : 999 : 1000 : [1001..], raggiungere il limite, e fermarsi, passando il risultato a f.

Fondamentalmente: Provando che un'espressione non può divergere, o delimitare la valutazione in modo che le cose terminino anche se lo fa. Nessuna modifica alla semantica e forse un grande miglioramento delle prestazioni.

Naturalmente, il rovescio della medaglia è che se x risulta essere un po 'di calcolo molto costoso che f utilizza solo la metà di, si spenderà 1.000 passi di riduzione perdite di tempo. E nel caso di [1..], si potrebbe finire con l'utilizzo di molta memoria per memorizzare un elenco; se f elabora l'elenco un elemento alla volta, buttando via la testa ogni volta, quindi sprecherai memoria. Ecco perché è complicato :)

La pagina originariamente collegata va più nel dettaglio delle tecniche specifiche utilizzate.