Cosa condivisione riferiscono alla realizzazione di un linguaggio di programmazione funzionale

Question

Condivisione significa che i dati temporanei vengono memorizzati se sta per essere utilizzato più volte. Cioè, una funzione valuta i suoi argomenti solo una volta. Un esempio potrebbe essere:

let x = sin x in x * x 

Quali altre caratteristiche contribuiscono a condivisione E come interagiscono con la necessità di programmi concreti per eseguire IO?

Answer 1

Il più chiaro esempio di condivisione nella programmazione funzionale viene da Clean, che si basa sul grafico riscrittura.Lì, un calcolo si riferisce a un DAG, in modo da poter vedere l'espressione (sin x) * (sin x) come

(*) 
/ \ 
sin x sin x 

sistemi di riscrittura di grafi hanno un concetto esplicito di condivisione, in modo da poter esprimere che il calcolo come

(*) 
/\ 
    \/
    sin x 

puntando il nodo di moltiplicazione allo stesso nodo, condividendo così il calcolo di sin x. I sistemi di riscrittura a termine non hanno una nozione così esplicita di condivisione, ma l'ottimizzazione è ancora rilevante. In GHC, a volte è possibile esprimere la condivisione con variabili locali, ad es. riscrittura

f x = (sin x) * (sin x) 

in

f x = sinx * sinx 
    where sinx = sin x 

Ma poiché i due sono semanticamente equivalenti, il compilatore è libero di attuare sia allo stesso modo, con o senza condivisione. Secondo la mia comprensione, il GHC generalmente preserverà la condivisione introdotta con variabili locali e talvolta la introdurrà (aggiungendo la condivisione al primo), ma senza alcuna espressione formale di condivisione nei sistemi di riscrittura a termine, il comportamento dipende dall'implementazione (vedi commento e risposta del tel).

Condivisione di tocchi I/O perché i valori di effetti collaterali non possono essere condivisi. Se consideriamo un linguaggio impura, v'è una differenza tra

(string-append (read-line) 
       (read-line)) 

e

(let ((s (read-line))) 
    (string-append s s)) 

Il primo esegue l'azione IO due volte, chiedendo due linee da parte degli utenti e li aggiungendo; il secondo "condivide" l'azione IO, eseguendola una volta e aggiungendola a se stessa. In generale, la condivisione di un calcolo puro riduce il tempo di esecuzione senza modificare il risultato del programma, mentre la condivisione di un valore di effetto collaterale (che può cambiare nel tempo o interagire con l'utente) modifica il risultato. Affinché il compilatore possa condividere automaticamente i calcoli, deve sapere che sono puri e che quindi la riduzione del numero di valutazioni non ha importanza. Pulito lo fa con i tipi di unicità; un'azione IO ha l'attributo type UNQ, che dice al compilatore che non deve essere condiviso. Haskell fa lo stesso in modo diverso con la monade IO.

Answer 2

La condivisione riguarda un tipo di uguaglianza: l'uguaglianza del puntatore. Nella terra di valore di Haskell (interpretazione semantica) non esiste una cosa come la condivisione. I valori possono essere uguali solo se hanno istanze di Eq e quindi "equality" è definita come la relazione binaria (==).

Sharing sfugge così l'interpretazione semantica facendo riferimento a questa uguaglianza puntatore sottostante, che esiste in virtù di attuazione, invece di semantica. Questo è un effetto collaterale utile a volte, però. Sfortunatamente, dal momento che Haskell è definito dalla sua interpretazione semantica, l'uso della condivisione è un comportamento indefinito. È legato a una particolare implementazione. Alcune librerie usano la condivisione e quindi hanno un comportamento legato a GHC.

C'è un meccanismo di condivisione incorporato, però. Questo è esposto dall'interfaccia StableName. Generiamo gli oggetti StableName a utilizzando makeStableName :: a -> IO (StableName a) e abbiamo un -questo StableName introduce un qualche tipo di uguaglianza per qualsiasi tipo.

StableName l'uguaglianza è quasi uguaglianza puntatore. Per citare la documentazione Haddock

Se sn1 :: StableName e sn2 :: StableName e sn1 == sn2 poi sn1 e sn2 sono stati creati da chiamate al makeStableName sullo stesso oggetto.

Si noti che questo è solo un se dichiarazione, non un se e solo se. Il fatto che due cose possano essere "pointer equivalent" ma abbia ancora nomi stabili diversi a volte è (a) forzato dalla flessibilità che Haskell lascia al GC e (b) una scappatoia che permette a StableName di esistere in qualsiasi implementazione Haskell anche se c'è nessuna cosa come "uguaglianza puntatore" nell'implementazione qualunque.

Questi valori StableName non hanno ancora alcun significato semantico, ma poiché sono stati introdotti nella monade IO che è "OK". Invece, si potrebbe dire che implementano un sottoinsieme (ironicamente) instabile della più piccola (più specifica) relazione di uguaglianza possibile su qualsiasi tipo.

Answer 3

L'esempio non è un esempio di condivisione: semplicemente moltiplica un valore con se stesso (quindi allontana il valore originale).

La condivisione è il caso in cui parte di una struttura di dati si verifica due volte in una struttura dati più grande o in strutture di dati diverse. Ad esempio:

p = (1, 2) 
pp = (p, p) -- p is shared between the first and second component of pp 

xs = [1, 2, 3] 
ys = 0::1::xs 
zs = 5::xs -- ys and zs share the same tail 

In memoria, tale condivisione si tradurrà in una struttura DAG.