Mutazione interna di strutture dati persistenti

Sarei molto restio a chiamare una struttura di dati "immutabile" a meno che, una volta esposta al mondo esterno, a meno che tutte le modifiche apportate al suo stato interno continuino sempre a lasciare l'oggetto nello stesso stato osservabile e a meno che lo stato dell'oggetto non sia valido con qualsiasi combinazione arbitraria di tali modifiche che si verificano o non si verificano.

Un esempio di un oggetto "immutabile" ragionevolmente buono che obbedisce a questo principio è il tipo string di Java. Include un campo di codice hash che inizialmente è zero, ma che viene utilizzato per memoizzare il risultato dell'interrogazione del codice hash. Lo stato di un string con un campo di codice hash zero è semanticamente uguale a quello di una stringa in cui è compilato il campo del codice hash. Se due thread tentano simultaneamente di interrogare il codice hash, è possibile che entrambi possano terminare eseguendo il calcolo e memorizzando il risultato, ma non importa perché nessuno dei due negozi influenzerà lo stato osservabile dell'oggetto. Se un terzo thread arriva e interroga il codice hash, potrebbe o non potrebbe vedere i negozi dai primi due, ma il codice hash restituito sarà lo stesso indipendentemente.

(A proposito, il mio cavillo con il metodo di hashing delle stringhe di Java è che è possibile che la funzione di hash restituisca zero per una stringa non nullo. Avrei pensato che fosse meglio avere il test della funzione hash per zero e sostituire qualcosa Ad esempio, se il passo hashing è tale che l'aggiunta di un singolo carattere a una stringa il cui hash è zero genererà sempre un hash diverso da zero, sarà sufficiente restituire l'hash della stringa meno l'ultimo carattere. hash una lunga stringa migliaia di volte può essere molto peggio del tempo normale.)

Le grandi cose da cui fare attenzione sono (1) sequenze di operazioni che cambiano lo stato di un oggetto e poi lo cambiano, o (2) la sostituzione di oggetti che sembrano avere lo stesso stato, ma non lo fanno. Ironia della sorte, la risoluzione di Microsoft di ciò che considera un bug nel suo metodo predefinito Struct.Equals rende più difficile la # 2 da proteggere. Se uno ha un numero di oggetti immutabili che contengono riferimenti a quelli che sembrano essere identici oggetti immutabili, la sostituzione di tutti quei riferimenti con riferimenti a uno di quegli oggetti immutabili dovrebbe essere sicura. Sfortunatamente, Equals esegue l'override per i tipi di sistema Decimal , Double e Float a volte riporta true anche quando si confrontano valori leggermente diversi. Un tempo era che il wrapping di uno di quei tipi in una struct e chiamando Equals su quella struct avrebbe verificato l'equivalenza vera, ma Microsoft ha cambiato le cose in modo che una struttura riportasse Equals se i suoi membri lo fanno, anche se questi membri non hanno - valori equivalenti dei tipi sopra menzionati.

Un strong argomento contro lo stato interno mutabile è che richiede la sincronizzazione. Se più thread accedono alla struttura, è necessario sincronizzarsi sulle operazioni che aggiornano lo stato.

Ti suggerisco di leggere il famoso libro di Okasaki Strutture dati puramente funzionali (PDF ). Ne vale la pena. In particolare, risolve la questione su come usare la pigrizia per rendere le strutture dati permanenti e immutabili (intendo perfettamente immutabili, nessuno stato modificabile interno eccetto la valutazione pigra e la memoizzazione dei valori valutati - proprio quello che fa Haskell).

Non solo descrive le strutture con costi ammortizzati efficienti, ma descrive anche strutture che hanno efficienti costi nel caso peggiore. L'idea è di forzare una piccola parte di calcoli non valutati ad ogni operazione.

Per dare un esempio su come può funzionare, nella Sezione 4.2 descrive le code in tempo reale. In Haskell, sembrerebbe

module RTQueue(RTQueue(), empty, add, headQ, tailQ) where

-- Invariant: |schedule| = |front| - |rear|
data RTQueue a = RTQueue { front :: [a], rear :: [a], schedule :: [a] }

empty = RTQueue [] [] []

-- Smart constructor that preserves the invariant.
-- We get |f| - |r| + 1 = |s| and fix it so that
-- the invariant |f| - |r| = |s| holds.
-- Either we force another element of 's' or
-- if 's' is empty we perform a rotation.
queue :: [a] -> [a] -> [a] -> RTQueue a
queue f r (_:s')  = RTQueue f r s'
queue f r []      = let f' = rotate f r []
                    in RTQueue f' [] f'
  where
    -- rotate f r a = f ++ reverse r ++ a
    -- and always |r| = |f| + 1
    rotate :: [a] -> [a] -> [a] -> [a]
    rotate []     [y]    a  = y : a
    rotate (x:f') (y:r') a  = x : rotate f' r' (y : a)

add :: RTQueue a -> a -> RTQueue a
add (RTQueue f r s) x = queue f (x : r) s

headQ :: RTQueue a -> a
headQ (RTQueue (x:_) _ _) = x

tailQ :: RTQueue a -> RTQueue a
tailQ (RTQueue (_:f) r s) = queue f r s

La coda è divisa in due parti: front da cui prendiamo gli elementi e rear che è invertito e a cui anteponiamo gli elementi. Di volta in volta ruotiamo la coda - invertiamo rear e aggiungiamo front . Il terzo valore schedule detiene front dopo ogni rotazione, ma durante ogni add (o tailQ ) uno dei suoi elementi è forzato (questo viene fatto semplicemente dalla corrispondenza del modello su di esso in queue ). Il risultato è che la lista front viene gradualmente valutata ed è pronta quando necessario da headQ o successiva rotate . Questa coda ha peggiore complessità O (1) per le sue operazioni.

Esiste una struttura dati funzionale (non nota all'epoca in cui Okasaki scrisse il suo libro) che permette di rappresentare sequenze finite con tempo di accesso costante ammortizzato ad entrambe le estremità e tempi di accesso logaritmico ammortizzati ovunque, compreso il tempo di unione logaritmica. Vedi Data.Sequence .

la maggior parte degli usi per immutabili cose copy-on-write come quella è per la sicurezza dei thread, quindi puoi usare una primitiva di CaS per gli aggiornamenti e non avere bisogno di un blocco

con la struttura sottostante che è mutabile questo non è più sicuro per i thread

anche per un esempio che invalida l'immutabilità sarebbe: (usando la sintassi del template di D) assumendo che questo sia sotto il cofano con un campo di puntatore e lunghezza

ImmutableArr!int a ={1,2,3,4}
ImmutableArr!int b = a.insert(2,9)

se b viene espanso sul posto allora a conterrà {1,2,9,3} dopo l'inserto