Ogni linguaggio funzionale può essere pigro?

Question

In un linguaggio funzionale, le funzioni sono cittadini di prima classe e quindi chiamando il numero non è l'unica cosa che posso fare. Posso anche conservarli via.

Ora, quando ho una lingua, che è rigorosa per impostazione predefinita, non sono ancora costretto a valutare una chiamata di funzione. Ho la possibilità di memorizzare la funzione e i suoi parametri, ad es. in una tupla per una valutazione successiva.

Così, invece di

x = f a b c 

faccio qualcosa di simile

x = (f,a,b,c) 

E più tardi, posso valutare questa cosa con qualcosa di simile

eval (f,a,b,c) = f a b c 

Beh, v'è probabilmente più a perché voglio valutare ogni chiamata di funzione non valutata solo una volta, ma a me sembra che possa anche questo essere risolto con una struttura dati che è un po 'più elaborata di una semplice tupla.

Anche l'inverso sembra essere il caso, perché ad es. in Haskell, che è pigro per impostazione predefinita, posso applicare la valutazione con seq o BangPatterns.

Quindi è corretto dire, che ogni linguaggio funzionale ha il potenziale di essere pigro, ma la maggior parte di loro sono semplicemente non pigri di default e quindi richiede sforzo di programmazione aggiuntiva per chiamare una funzione pigramente, mentre Haskell è pigro per impostazione predefinita e richiede uno sforzo di programmazione aggiuntivo per chiamare una funzione in modo rigoroso?

In questo caso, cosa è più difficile per il programmatore: la scrittura di chiamate a funzione pigra in un linguaggio rigoroso o la scrittura di chiamate a funzioni rigorose in un linguaggio pigro?

Come nota a margine: era Simon P. Jone serio quando ha detto: "la prossima versione di haskell sarà rigorosa". Ho pensato inizialmente che fosse uno scherzo. Ma ora penso che strict per impostazione predefinita non sia poi così male finché si può essere pigri se necessario.

Answer 1

La risposta è un sì qualificato. La tua intuizione che la pigrizia possa essere implementata in un linguaggio rigoroso in cui le funzioni sono oggetti di prima classe è corretta. Ma entrare nei dettagli rivela una serie di sottigliezze.

Prendiamo un linguaggio funzionale (con cui intendo un linguaggio in cui le funzioni possono essere costruite e manipolate come oggetti di prima classe, come nel calcolo lambda), dove l'applicazione della funzione è rigorosa (cioè la funzione¹ e il suo argomento (s) sono completamente valutati prima dell'applicazione della funzione). Userò la sintassi di Standard ML, poiché si tratta di un linguaggio funzionale rigoroso e storicamente importante. Un'applicazione rigorosa FA (dove F e A sono due espressioni) può essere ritardato di codifica come

Thunk (F, A)

Questo oggetto contiene una funzione e un argomento è chiamato thunk. Siamo in grado di definire un tipo di thunk:

datatype ('a, 'b) thunk = Thunk of ('a -> 'b) * 'a; 

e una funzione per valutare un thunk:

fun evaluate (Thunk (f, x)) = f x; 

Nizza e facile finora. Ma non abbiamo, in effetti, implementato una valutazione pigra! Ciò che abbiamo implementato è la valutazione dell'ordine normale, nota anche come call-by-name. La differenza è che se il valore del thunk viene utilizzato più di una volta, viene calcolato ogni volta. La valutazione lenta (nota anche come call-by-need) richiede la valutazione dell'espressione al massimo una volta.

In un linguaggio puro e rigoroso, la valutazione lenta è infatti impossibile da implementare. Il motivo è che la valutazione di un thunk modifica lo stato del sistema: passa da non valutato a valutato. L'implementazione della valutazione lenta richiede un modo per modificare lo stato del sistema.

C'è una sottigliezza qui: se la semantica della lingua è definita puramente in termini di stato di terminazione delle espressioni e il valore delle espressioni di terminazione, quindi, in un linguaggio puro, call-by-need e call-by- il nome è indistinguibile. Call-by-value (vale a dire valutazione rigorosa) è distinguibile perché meno espressioni terminano - call-by-need e call-by-name nascondono qualsiasi non-terminazione che si verifica in un thunk che non viene mai valutato. L'equivalenza di call-by-need e call-by-name consente di considerare la valutazione lazy come un'ottimizzazione della valutazione di ordine normale (che ha delle buone proprietà teoriche). Ma in molti programmi, l'utilizzo di call-by-name anziché call-by-value farebbe saltare in aria il tempo di esecuzione calcolando il valore delle stesse espressioni più e più volte.

In una lingua con stato mutabile, la valutazione lazy può essere espressa memorizzando il valore nel thunk quando viene calcolato.

datatype ('a, 'b) lazy_state = Lazy of ('a -> 'b) * 'a | Value of 'a; 
type ('a, 'b) lazy_state = ('a, 'b) lazy_state ref; 
let lazy (f, x) = ref (Lazy (f, x)); 
fun force r = 
    case !r of Value y => y 
      | Lazy (f, x) => let val y = f x in r := Value y; y end; 

Questo codice non è molto complicato, quindi, anche in dialetti ML che forniscono valutazione pigra come una funzione di libreria (eventualmente con zucchero sintattico), non viene utilizzato tutto ciò che spesso in pratica - spesso, il punto in quale valore sarà necessario è una posizione nota nei programmi, e i programmatori usano semplicemente una funzione e passano il suo argomento in quella posizione.

Mentre questo sta entrando in territorio soggettivo, direi che è molto più facile implementare una valutazione pigra come questa, piuttosto che implementare una valutazione rigorosa in un linguaggio come Haskell. Costringere la rigorosa valutazione in Haskell è praticamente impossibile (eccetto che avvolgere tutto in una monade di stato e scrivere essenzialmente codice ML nella sintassi Haskell). Ovviamente, una valutazione rigorosa non modifica i valori calcolati dal programma, ma può avere un impatto significativo sulle prestazioni (e, in particolare, a volte è molto apprezzata perché rende le prestazioni molto più prevedibili - prevedendo le prestazioni di un Il programma Haskell può essere molto difficile).

Questo meccanismo di valutazione e archiviazione è effettivamente il nucleo di ciò che un compilatore Haskell fa sotto il cofano. Haskell è puro², quindi non puoi implemente farlo nel linguaggio stesso! Tuttavia, sembra che il compilatore lo faccia sotto il cofano, perché questo particolare uso di effetti collaterali non infrange la purezza del linguaggio, quindi non invalida alcuna trasformazione del programma. Il motivo per cui il valore di un thunk è memorizzato è che trasforma la valutazione call-by-name in call-by-need, e come abbiamo visto sopra, questo non modifica i valori delle espressioni di terminazione, né cambia le espressioni che terminano.

Questo approccio può essere in qualche modo problematico in un linguaggio che combina una valutazione locale puramente funzionale con un ambiente multithread e un passaggio di messaggi tra i thread. (Questo è in particolare il modello di Erlang.) Se un thread inizia a valutare un thunk, e un altro thread ha bisogno del suo valore solo allora, che cosa succederà? Se non vengono prese precauzioni, entrambi i thread calcoleranno il valore e lo memorizzeranno. In un linguaggio puro, questo è innocuo nel senso che entrambi i thread calcoleranno lo stesso valore comunque³. Tuttavia questo può danneggiare le prestazioni. Per garantire che un thunk venga valutato solo una volta, il calcolo del valore deve essere racchiuso in un lock; questo aiuta con lunghi calcoli eseguiti molte volte ma fa male i calcoli che vengono eseguiti solo una volta, poiché prendere e rilasciare un blocco richiede del tempo.

¹ _{La funzione, non il corpo della funzione, ovviamente.}
² _{O meglio, il frammento di Haskell che non usa una monade effetto collaterale è puro.} ³ _{È necessario che la transizione tra un thunk ritardato e un valore calcolato sia atomico: i thread concorrenti devono essere in grado di leggere un valore lazy e ottenere un valore valido o un valore calcolato valido, non una combinazione di i due non è un oggetto valido. A livello di processore, la transizione da thunk ritardato a valore calcolato è solitamente un'assegnazione di puntatore, che per la maggior parte delle architetture è atomica, per fortuna.}

Answer 2

Quello che proponi funzionerà. I dettagli per farlo in Scheme possono essere found in SICP. Si potrebbe immaginare una versione rigorosa di Haskell in cui esiste una funzione "pigra" che fa il contrario di ciò che "seq" fa in Haskell. Tuttavia, l'aggiunta di questo a un linguaggio simile a Haskell richiederebbe la compilazione magica perché altrimenti il ​​thunk viene forzato prima di essere passato a "pigro".

Tuttavia, se la tua lingua ha effetti incontrollati, questo può diventare peloso, perché un effetto si verifica ogni volta che viene valutata la sua funzione di chiusura, e capire quando capita quando ciò accadrà in un lazy pigro è difficile. Ecco perché Haskell ha la monade IO.

Answer 3

valutazione pigro, al livello basso, viene implementato da un concetto chiamato thunk, che comprende due cose:

1. Una chiusura che calcola il valore del calcolo differito
2. A di- una volta cella di memoria mutevole per la memorizzazione del risultato.

La prima parte, la chiusura, può essere modellata in un modo ancora più semplice della tupla con la funzione e i suoi argomenti. Puoi semplicemente usare una funzione che accetta l'unità o nessun argomento (a seconda di come funziona la tua lingua), e nel suo corpo si applica la funzione agli argomenti. Per calcolare il risultato, basta invocare la funzione.

Paul Johnson cita Scheme, che è un linguaggio perfetto per dimostrarlo. Come una macro Scheme (pseudocodice, non testata):

(define-syntax delay 
    (syntax-rules() 
    ((delay expr ...) 
    ;; `(delay expr)` evaluates to a lambda that closes over 
    ;; two variables—one to store the result, one to record 
    ;; whether the thunk has been forced. 
    (let ((value #f) 
      (done? #f)) 
     (lambda() 
     (unless done? 
      (set! value (begin expr ...)) 
      (set! done? #t)) 
     value))))) 

(define (force thunk) 
    ;; Thunks are procedures, so to force them you just invoke them. 
    (thunk)) 

Ma per ottenere questo ritorno al titolo della domanda: questo significa che ogni lingua funzionale può essere pigro? La risposta è no. I linguaggi desiderosi possono implementare il thunking e utilizzarlo per fornire la valutazione ritardata opt-in negli spot selezionati dall'utente, ma questo non è lo stesso che avere una valutazione pigmentata pervasiva come le implementazioni di Haskell.