Uso dei tipi di unicità per implementare il parallelismo sicuro

18

Da qualche tempo mi sono interessato ai tipi di unicità come alternativa alle monadi in puro linguaggio funzionale; sfortunatamente, questa è una specie di area esoterica della ricerca di CS e le risorse online sulla programmazione con tipi di unicità sono poche e lontane tra loro.

È ovvio come i tipi di unicità possano essere usati per implementare strutture di dati stateful come i riferimenti ("scatole") e gli array, anche se mi sfugge il modo in cui potresti implementare con loro altre strutture di dati stateful comuni.

È possibile implementare, ad esempio, il blocco con tipi unici? È possibile utilizzare i tipi di unicità per condividere dati mutabili tra thread? È possibile utilizzare tipi univoci per creare primitive di sincronizzazione (come i mutex) o il passaggio di messaggi è necessario?

    
posta Ricky Stewart 07.05.2014 - 00:14
fonte

1 risposta

1

Is it possible to implement, for example, locking with unique types?

Ho seguito il link che Robert Harvey ha fornito e ho fatto una rapida lettura. Non posso dire di aver capito tutto o di avere un alto livello di sicurezza che io veramente ho capito cosa io penso ho capito, ma mi sembra che il punto l'unicità esterna e l'immutabilità di riferimento è quella di non aver bisogno di bloccare.

I moderni approcci al multithreading tentano di evitare il blocco perché solo i programmatori di grande esperienza possono scrivere codice che utilizza il blocco, e anche il loro codice è altamente incline ad avere bug. Se si aggiunge il fatto che il codice di blocco è praticamente non verificabile, dovrebbe essere ovvio che si tratta di un modo altamente indesiderabile di fare le cose, e qualsiasi soluzione che ci aiuti a liberarci dal blocco è a dir poco promettente.

Il modo in cui evitiamo di bloccare è il passaggio dei messaggi, che richiede che i messaggi siano immutabili. Approssimativamente, (a prima vista) l'immutabilità di riferimento sembra essere una tecnica che può aiutarci a garantire l'immutabilità senza dover effettivamente costruire tipi immutabili, e l'unicità esterna sembra essere una tecnica che può aiutarci a rilassare il rigoroso requisito di immutabilità a livello locale. p>

Can uniqueness types be used to share mutable data across threads?

Il documento non lo indicava chiaramente, ma da quello che ho capito, un cluster di oggetti esternamente unico è thread-safe perché in qualche modo (davvero, come? ) è garantito che esiste solo uno all'esterno riferimento in quel cluster di oggetti, il che significa che un thread che riceve tale riferimento può trattare gli oggetti di riferimento come mutabili senza doversi preoccupare che qualche altro thread possa anche mutarli, poiché nessun altro thread può possedere un altro riferimento. Sarei curioso di sapere in che modo un tale costrutto teorico può essere implementato e applicato.

Is it possible to use unique types to build synchronization primitives (like mutexes), or is message passing necessary?

Ancora una volta, da quello che ho capito, i tipi unici esternamente e l'immutabilità dei riferimenti hanno lo scopo di rendere non necessari i blocchi, i mutex e simili. Il passaggio dei messaggi sembra essere la strada da percorrere, e va bene.

    
risposta data 09.02.2015 - 22:06
fonte