valutazione della strategia

Question

Come dovrebbe una ragione circa la valutazione della funzione negli esempi riportati di seguito in Haskell:

let f x = ... 
    x = ... 
in map (g (f x)) xs 

In GHC, a volte (f x) viene valutata solo una volta, e, a volte, una volta per ogni elemento in xs, a seconda di cosa esattamente f e g sono. Questo può essere importante quando f x è un calcolo costoso. Ha appena inciampato in un principiante Haskell che stavo aiutando e non sapevo cosa dirgli a parte il fatto che spetta al compilatore. C'è una storia migliore?

Aggiornamento

Nell'esempio seguente (f x) saranno valutati 4 volte:

let f x = trace "!" $ zip x x 
    x = "abc" 
in map (\i -> lookup i (f x)) "abcd" 

Answer 1

Con estensioni del linguaggio, siamo in grado di creare situazioni in cui f xmust essere valutato più volte:

{-# LANGUAGE GADTs, Rank2Types #-} 
module MultiEvG where 

data BI where 
    B :: (Bounded b, Integral b) => b -> BI 

foo :: [BI] -> [Integer] 
foo xs = let f :: (Integral c, Bounded c) => c -> c 
      f x = maxBound - x 
      g :: (forall a. (Integral a, Bounded a) => a) -> BI -> Integer 
      g m (B y) = toInteger (m + y) 
      x :: (Integral i) => i 
      x = 3 
     in map (g (f x)) xs 

Il punto cruciale è quello di avere f x polimorfico anche come argomento di g, e dobbiamo creare una situazione in cui il i tipi ai quali è necessario non possono essere previsti (la mia prima coltellata utilizzava uno Either a b invece di BI, ma quando si ottimizzava, ciò comportava, naturalmente, solo due valutazioni di f x al massimo).

Un'espressione polimorfa deve essere valutata almeno una volta per ogni tipo in cui viene utilizzata. Questa è una delle ragioni per la restrizione del monomorfismo. Tuttavia, quando l'intervallo di tipi a cui può essere necessario è limitato, è possibile memorizzare i valori per ciascun tipo e, in alcune circostanze, GHC lo fa (necessita di ottimizzazione, e mi aspetto che il numero di tipi coinvolti non sia troppo grande). Qui lo confrontiamo con quello che è fondamentalmente un elenco non omogeneo, quindi in ogni invocazione di g (f x), può essere necessario in un tipo arbitrario che soddisfi i vincoli, quindi il calcolo non può essere revocato all'esterno dello map (tecnicamente, il compilatore potrebbe ancora creare una cache dei valori ad ogni tipo usato, quindi sarebbe valutato solo una volta per tipo, ma GHC non lo fa, con ogni probabilità non ne varrebbe la pena).

• Le espressioni monomorfologiche devono essere valutate solo una volta, possono essere condivise. Se sono all'altezza dell'implementazione; per purezza, non cambia la semantica del programma. Se l'espressione è legata a un nome, in pratica puoi fare affidamento sul fatto che sia condivisa, dal momento che è facile e ovviamente ciò che il programmatore vuole. Se non è legato a un nome, è una questione di ottimizzazione. Con il generatore bytecode o senza ottimizzazioni, l'espressione sarà spesso valutata ripetutamente, ma con l'ottimizzazione ripetuta la valutazione indicherebbe un errore del compilatore.
• Le espressioni polimorfiche devono essere valutate almeno una volta per ogni tipo in cui vengono utilizzate, ma con ottimizzazioni, quando GHC può vedere che può essere utilizzato più volte allo stesso tipo, sarà (di solito) ancora condiviso per quello digita durante un calcolo più grande.

Bottom line: compilare sempre con ottimizzazioni, aiutare il compilatore associando le espressioni che si desidera condividere con un nome e assegnare firme di tipo monomorfico laddove possibile.

Answer 2

Questo è veramente dipende ottimizzazioni del GHC, come siete stati in grado di dire.

La cosa migliore da fare è studiare il GHC core che si ottiene dopo aver ottimizzato il programma. Vorrei esaminare il nucleo generato ed esaminare se f x aveva la propria istruzione let al di fuori dello map oppure no.

Se si vuole essere sicuri , allora si dovrebbe fattore f x fuori nella propria variabile assegnata in un let, ma non c'è davvero un modo garantito per capirlo diversa lettura attraverso Nucleo.

Tutto ciò detto, ad eccezione di cose come trace che utilizzano unsafePerformIO, questo non cambierà mai la semantica del programma: come si comporta effettivamente.

Answer 3

I tuoi esempi sono davvero molto diversi.

Nel primo esempio, l'argomento da mappare è g (f x) e viene passato una volta a map molto probabilmente come funzione parzialmente applicata. Se g (f x) si applica a un argomento entro map, valuta il suo primo argomento, quindi questo verrà eseguito solo una volta e quindi il thunk (f x) verrà aggiornato con il risultato.

Quindi, nel primo esempio, f x verrà valutato al massimo 1 volta.

Il secondo esempio richiede un'analisi più approfondita prima che il compilatore possa arrivare alla conclusione che (f x) è sempre costante nell'espressione lambda. Forse non lo ottimizzerà affatto, perché potrebbe essere a conoscenza del fatto che la traccia non è del tutto kosher. Quindi, questo può valutare 4 volte quando si traccia, e 4 volte o 1 volta quando non si traccia.

Answer 4

In modalità GHC senza ottimizzazioni, il corpo di una funzione viene valutato ogni volta che viene chiamata la funzione. (Una "chiamata" indica che la funzione viene applicata agli argomenti e il risultato viene valutato). Nell'esempio seguente, f x si trova all'interno di una funzione, quindi verrà eseguito ogni volta che viene chiamata la funzione. (GHC può ottimizzare questa espressione come discusso nella Domanda [1].)

let f x = trace "!" $ zip x x 
    x = "abc" 
in map (\i -> lookup i (f x)) "abcd" 

Tuttavia, se si passa f x dalla funzione, viene eseguito solo una volta.

let f x = trace "!" $ zip x x 
    x = "abc" 
in map ((\f_x i -> lookup i f_x) (f x)) "abcd" 

Questo può essere riscritta più essere letti come

let f x = trace "!" $ zip x x 
    x = "abc" 
    g f_x i = lookup i f_x 
in map (g (f x)) "abcd" 

La regola generale è che, ogni volta che una funzione viene applicata ad un argomento, viene creata una nuova "copia" del corpo funzione. L'applicazione di funzione è l'unica cosa che può causare un'espressione da rieseguire. Tuttavia, tieni presente che alcune funzioni e chiamate di funzione non assomigliano alle funzioni sintatticamente.

[1] http://www.haskell.org/haskellwiki/GHC/FAQ#Subexpression_Elimination