Uso de tipos únicos para implementar paralelismo seguro

19

He estado interesado en los tipos de singularidad como una alternativa a las mónadas en lenguajes funcionales puros durante algún tiempo; desafortunadamente, este es un área esotérica de investigación de CS y los recursos en línea sobre programación con tipos únicos son pocos y distantes entre sí.

Es obvio cómo se pueden usar los tipos de unicidad para implementar estructuras de datos con estado como referencias ("cuadros") y matrices, aunque se me escapa cómo podría implementar otras estructuras de datos con estado comunes con ellos.

¿Es posible implementar, por ejemplo, el bloqueo con tipos únicos? ¿Se pueden usar los tipos de unicidad para compartir datos mutables entre hilos? ¿Es posible usar tipos únicos para construir primitivas de sincronización (como mutexes), o es necesario pasar mensajes?

Ricky Stewart
fuente
¿Puedes hacer tu pregunta un poco más específica? ¿Qué, por ejemplo, ya sabe sobre el bloqueo con tipos únicos y dónde su conocimiento es insuficiente?
Robert Harvey
> ¿Qué, por ejemplo, ya sabe sobre el bloqueo con tipos únicos? No sé nada sobre el bloqueo con tipos únicos. Realmente no sé cómo funciona el paralelismo seguro con tipos únicos y me gustaría saber si existe son cualquier recurso sobre el tema.
Ricky Stewart
2
@RickyStewart: Probablemente ya conozca Clean ( wiki.clean.cs.ru.nl/Clean ). Solo quería agregar el enlace porque no lo mencionaste.
Giorgio
Creo que deberías buscar tipos lineales para el paralelismo. Los tipos de singularidad del IIRC se basan en tipos lineales. Frank Pfenning tiene algunas cosas interesantes sobre el tema
Daniel Gratzer

Respuestas:

2

¿Es posible implementar, por ejemplo, el bloqueo con tipos únicos?

Seguí el enlace que me proporcionó Robert Harvey e hice una lectura rápida. No puedo decir que entendí todo o que tengo un alto nivel de confianza de que realmente entendí lo que creo que entendí, pero me parece que el punto central de la unicidad externa y la inmutabilidad de referencia es no tener necesidad de bloquear.

Los enfoques modernos de subprocesamiento múltiple intentan evitar el bloqueo porque solo los programadores altamente experimentados pueden escribir código que usa bloqueo, e incluso su código es muy propenso a tener errores. Si agrega además el hecho de que el código de bloqueo es prácticamente inestable, debería ser obvio que es una forma muy indeseable de hacer las cosas, y cualquier solución que tenga como objetivo liberarnos del bloqueo es prometedora, por decir lo menos.

La forma en que hemos estado evitando el bloqueo es con el paso de mensajes, lo que requiere que los mensajes sean inmutables. Aproximadamente, (a primera vista), la inmutabilidad de referencia parece ser una técnica que puede ayudarnos a garantizar la inmutabilidad sin tener que construir tipos inmutables, y la singularidad externa parece ser una técnica que puede ayudarnos a relajar localmente el estricto requisito de inmutabilidad.

¿Se pueden usar los tipos de unicidad para compartir datos mutables entre hilos?

El documento no lo indicó claramente, pero por lo que entiendo, un grupo de objetos externo único es seguro para subprocesos porque de alguna manera (¿realmente, cómo? ) Se garantiza que solo exista una referencia externa en ese grupo de objetos, lo que significa que un hilo que recibe dicha referencia puede tratar los objetos a los que se hace referencia como mutables sin tener que preocuparse de que algún otro hilo también pueda mutarlos, porque ningún otro hilo puede tener otra referencia. Me gustaría saber cómo se puede implementar y hacer cumplir una construcción tan teórica.

¿Es posible usar tipos únicos para construir primitivas de sincronización (como mutexes), o es necesario pasar mensajes?

Nuevamente, por lo que entiendo, los tipos únicos externos y la inmutabilidad de referencia están destinados a hacer innecesarios los bloqueos, mutexes y similares. Pasar mensajes parece ser el camino a seguir, y eso es bueno.

Mike Nakis
fuente