El modelo de actor y los cálculos de proceso comparten una historia y una coevolución interesantes .
Trabajo temprano
El modelo Actor, publicado por primera vez en 1973, [1] es un modelo matemático de cálculo concurrente . El modelo de actor trata a los "actores" como las primitivas universales de la computación digital concurrente: en respuesta a un mensaje que recibe, un actor puede tomar decisiones locales, crear más actores, enviar más mensajes y determinar cómo responder al siguiente mensaje recibido. .
A diferencia del enfoque anterior basado en la composición de procesos secuenciales, el modelo Actor se desarrolló como un modelo inherentemente concurrente. En el modelo de Actor, la secuencialidad era un caso especial que se derivaba del cálculo concurrente, como se explica en la teoría del modelo de Actor .
El trabajo inicial publicado de Robin Milner sobre concurrencia del mismo año [2] también fue notable porque posiciona la semántica matemática de los procesos de comunicación como un marco para comprender una variedad de agentes de interacción, incluida la interacción de la computadora con la memoria. El marco del modelado se basó en el modelo de dominios de Scott y, como tal, no se basó en procesos secuenciales. Su trabajo se diferencia del modelo Actor en las siguientes formas:
- Hay un número fijo de procesos en comparación con el modelo Actor que permite que el número de actores varíe dinámicamente.
- Las únicas cantidades que se pueden pasar en los mensajes son los números enteros y las cadenas, a diferencia del modelo Actor, que permite que las direcciones de los actores se pasen en los mensajes.
- Los procesos tienen una topología fija a diferencia del modelo Actor, que permite variar la topología.
- La comunicación es sincrónica a diferencia del modelo Actor en el que puede transcurrir un tiempo ilimitado entre el envío y la recepción de un mensaje.
- La semántica proporcionó un no determinismo limitado a diferencia del modelo Actor con un no determinismo ilimitado. Sin embargo, con el no determinismo limitado es imposible que un servidor garantice el servicio a sus clientes, es decir , un cliente podría morir de hambre .
Más tarde, Milner eliminó algunas de estas restricciones en su trabajo sobre el cálculo de Pi (ver sección Milner, et al. Más abajo).
La publicación por Tony Hoare en 1978 del original Communicating Sequential Processes fue diferente del modelo Actor que dice: [3]
- Este artículo sugiere que la entrada y la salida son primitivas básicas de la programación y que la composición paralela de los procesos secuenciales comunicantes es un método fundamental de estructuración de programas. Cuando se combinan con un desarrollo del comando cauteloso de Dijkstra, estos conceptos son sorprendentemente versátiles. Su uso se ilustra con soluciones de muestra de una variedad de ejercicios de programación familiares.
- ...
- Los programas expresados en el lenguaje propuesto están pensados para ser implementados tanto por una máquina convencional con un único almacén principal, como por una red fija de procesadores conectados por canales de entrada / salida (aunque son apropiadas optimizaciones muy diferentes en los diferentes casos). En consecuencia, es un lenguaje bastante estático: el texto de un programa determina un límite superior fijo en el número de procesos que operan al mismo tiempo; no hay recursividad ni facilidad para las variables valoradas por el proceso. También en otros aspectos, el lenguaje se ha reducido al mínimo necesario para la explicación de sus características más novedosas.
- ...
- Este artículo ha sugerido que la entrada, la salida y la concurrencia deben considerarse como primitivas de la programación, que son la base de muchos conceptos de programación familiares y menos familiares. Sin embargo, sería injustificado concluir que estas primitivas pueden reemplazar por completo a los otros conceptos en un lenguaje de programación. Cuando una construcción más elaborada (como un procedimiento o un monitor) es con frecuencia útil, tiene propiedades que se pueden demostrar de manera más simple y también se puede implementar de manera más eficiente que el caso general, hay una fuerte razón para incluir en un lenguaje de programación un notación especial para esa construcción. El hecho de que la construcción pueda definirse en términos de primitivas subyacentes más simples es una garantía útil de que su inclusión es lógicamente coherente con el resto del lenguaje.
La versión de 1978 de CSP difería del modelo Actor en los siguientes aspectos [Clinger 1981]:
- Las primitivas de concurrencia de CSP fueron entrada, salida, comandos protegidos y composición paralela, mientras que el modelo Actor se basa en mensajería unidireccional asincrónica.
- La unidad fundamental de ejecución fue un proceso secuencial en contraste con el modelo Actor en el que la ejecución fue fundamentalmente concurrente. La ejecución secuencial es problemática porque las computadoras multiprocesador son inherentemente concurrentes.
- Los procesos tenían una topología de comunicación fija, mientras que los Actores tenían una topología de comunicaciones que cambiaba dinámicamente. Tener una topología fija es problemático porque excluye la capacidad de ajustarse dinámicamente a las condiciones cambiantes.
- Los procesos se estructuraron jerárquicamente utilizando una composición paralela, mientras que los Actores permitieron la creación de una ejecución no jerárquica utilizando futuros [Baker y Hewitt 1977]. La composición paralela jerárquica es problemática porque excluye la capacidad de crear un proceso que sobreviva a su creador. Además, el paso de mensajes es el mecanismo fundamental para generar paralelismo en el modelo Actor; enviar más mensajes genera la posibilidad de más paralelismo.
- La comunicación fue sincrónica mientras que la comunicación del actor fue asincrónica. La comunicación sincrónica es problemática porque los procesos que interactúan pueden estar muy separados.
- La comunicación fue entre procesos, mientras que en el modelo Actor las comunicaciones son unidireccionales para los Actores. La comunicación síncrona entre procesos es problemática al requerir que un proceso espere en múltiples procesos.
- Las estructuras de datos consistían en números, cadenas y matrices, mientras que en el modelo Actor las estructuras de datos eran Actores. Restringir las estructuras de datos a números, cadenas y matrices es problemático porque prohíbe las estructuras de datos programables.
- Los mensajes contienen números y cadenas, mientras que en el modelo Actor, los mensajes pueden incluir las direcciones de los actores. No permitir direcciones en los mensajes es problemático porque excluye la flexibilidad en la comunicación porque no hay forma de proporcionar a otro proceso la capacidad de comunicarse con un proceso ya conocido.
- El modelo de CSP deliberadamente había limitado el no determinismo [Francez, Hoare, Lehmann y de Roever 1979] mientras que el modelo Actor tenía un no determinismo ilimitado . Dijkstra [1976] había convencido a Hoare de que no se podía implementar un lenguaje de programación con un no determinismo ilimitado. En consecuencia, no fue posible garantizar que los servidores implementados con CSP brinden servicio a múltiples clientes.
Cálculos de proceso y modelo de actor
Milner y col.
En su conferencia de Turing, [4] Milner comentó lo siguiente:
- Ahora, el cálculo lambda puro se construye con solo dos tipos de cosas: términos y variables . ¿Podemos lograr la misma economía para un cálculo de procesos? Carl Hewitt, con su modelo Actors, respondió a este desafío hace mucho tiempo; declaró que un valor, un operador sobre valores y un proceso deberían ser todos el mismo tipo de cosa: un Actor . Este objetivo me impresionó, porque implica la homogeneidad y la integridad de la expresión ... Pero pasó mucho antes de que pudiera ver cómo alcanzar el objetivo en términos de cálculo algebraico ... Entonces, en el espíritu de Hewitt, nuestro primer paso es exigir que todas las cosas denotadas por términos o accesibles por nombres - valores, registros, operadores, procesos, objetos - sean todas de la misma clase de cosas; todos deberían ser procesos. A partir de entonces, consideramos el acceso por nombre como la materia prima de la computación ...
En 2003, Ken Kahn recordó en un mensaje sobre el cálculo Pi :
- El cálculo de Pi se basa en la comunicación sincrónica (apretón de manos). Hace unos 25 años fui a cenar con Carl Hewitt y Robin Milner (de CCS y la fama del cálculo de pi) y estaban discutiendo sobre las primitivas de comunicación sincrónica o asincrónica. Carl usó la metáfora de la oficina de correos mientras que Robin usó el teléfono. Ambos admitieron rápidamente que uno puede implementar uno en el otro.
Hoare y col.
Tony Hoare , Stephen Brookes y AW Roscoe desarrollaron y perfeccionaron la teoría de la CSP en su forma moderna. [5] El enfoque adoptado para desarrollar la versión teórica de CSP fue fuertemente influenciado por el trabajo de Robin Milner sobre el Cálculo de Sistemas de Comunicación (CCS), y viceversa. A lo largo de los años, ha habido muchos intercambios de ideas fructíferos entre los investigadores que trabajan tanto en CSP como en CCS.
Hewitt y col.
Will Clinger [1981] desarrolló el primer modelo de actor denotacional para el cálculo concurrente que encarnaba el no determinismo ilimitado . Bill Kornfeld y Carl Hewitt [1981] demostraron que el modelo Actor podía abarcar la concurrencia a gran escala. Agha desarrolló Actors como modelo fundamental para la computación concurrente. Su trabajo sobre la representación de la abstracción y composición del actor, y sobre el desarrollo de una semántica operativa para actores basada en árboles de comunicaciones asincrónicas, fue explícitamente influenciado por el trabajo de Milner sobre el cálculo de sistemas de comunicación (CCS). [6] así como el trabajo de Clinger.
Mayor coevolución
El cálculo π , parcialmente inspirado por el modelo Actor descrito por Milner anteriormente, introdujo la topología dinámica en los cálculos de procesos al permitir la creación dinámica de procesos y que los nombres se pasaran entre diferentes procesos. Sin embargo, el objetivo de Milner y Hoare de lograr un cálculo algebraico condujo a una divergencia crítica del modelo Actor: la comunicación en los cálculos de proceso no es directa como en el modelo de Actor, sino indirectamente a través de canales (ver Modelo de actor y cálculos de proceso ). En contraste, un trabajo reciente sobre el modelo Actor [Hewitt 2006, 2007a] ha enfatizado los modelos denotacionales y el Teorema de Representación .
No obstante, existen interesantes coevoluciones entre el modelo de actor y los cálculos de procesos. Montanari y Talcott [7] discutieron si el modelo de actor y el cálculo π eran compatibles entre sí. Sangiorgi y Walker [ cita requerida ] mostraron cómo el trabajo de Actor en el tratamiento de las estructuras de control como patrones de transmisión de mensajes [8] podría modelarse utilizando el cálculo π.
Aunque se han desarrollado leyes algebraicas para el modelo Actor, no capturan la propiedad crucial de la entrega garantizada de mensajes enviados a serializadores. Por ejemplo, vea lo siguiente:
Ver también
Referencias
- ^ Carl Hewitt, Peter Bishop y Richard Steiger. Un formalismo universal de actor modular para la inteligencia artificial IJCAI 1973.
- ^ Robin Milner. Procesos: un modelo matemático de agentes informáticos en el coloquio de lógica 1973.
- ^ COCHE Hoare . Comunicación de procesos secuenciales CACM. Agosto de 1978.
- ^ Robin Milner : Elementos de interacción: conferencia del premio Turing , Comunicaciones de la ACM, vol. 36, no. 1, págs. 78-89, enero de 1993. ( DOI ).
- ^ SD Brookes, CAR Hoare y W. Roscoe. Una teoría de la comunicación de procesos secuenciales JACM 1984.
- ^ Gul Agha (1986). "Actores: un modelo de computación concurrente en sistemas distribuidos". Tesis doctoral. Prensa del MIT. hdl : 1721,1 / 6952 . Cite journal requiere
|journal=
( ayuda ) - ^ Ugo Montanari y Carolyn Talcott. ¿Pueden los actores y los agentes pi vivir juntos? Notas electrónicas en informática teórica. 1998.
- ^ Carl Hewitt. Visualización de las estructuras de control como patrones de transmisión de mensajes Journal of Artificial Intelligence. Junio de 1977.
- ^ Mauro Gaspari; Gianluigi Zavattaro (mayo de 1997). "Un álgebra de actores". Informe técnico UBLCS-97-4. Universidad de Bolonia. Cite journal requiere
|journal=
( ayuda ) - ^ M. Gaspari; G. Zavattaro (1999). "Un álgebra de actores". Métodos formales para sistemas abiertos basados en objetos. Cite journal requiere
|journal=
( ayuda ) - ^ Gul Agha ; Prasanna Thati (2004). "Una teoría algebraica de actores y su aplicación a un lenguaje simple basado en objetos" (PDF) . De OO a FM (Dahl Festschrift) LNCS 2635. Archivado desde el original (PDF) el 20 de abril de 2004 . Consultado el 15 de enero de 2008 . Cite journal requiere
|journal=
( ayuda )
Otras lecturas
- Edsger Dijkstra. Una disciplina de programación Prentice Hall . 1976.
- Carl Hewitt y col. Acta de la conferencia de inducción y metaevaluación de actores del simposio de ACM sobre principios de lenguajes de programación, enero de 1974.
- Carl Hewitt y col. Semántica conductual de la estructura de control no recursiva Procedimientos de Colloque sur la Programmation, abril de 1974.
- Irene Greif y Carl Hewitt. Semántica de actor de PLANNER-73 Conferencia Record del Simposio ACM sobre principios de lenguajes de programación. Enero de 1975.
- Irene Greif. Semántica de la comunicación de procesos paralelos Tesis doctoral EECS del MIT. Agosto de 1975.
- Carl Hewitt y Henry Baker Actores y Actas de Funcionalidad Continua de la Conferencia de Trabajo de IFIP sobre Descripción Formal de Conceptos de Programación. 1-5 de agosto de 1977.
- Carl Hewitt y Henry Baker Leyes para la comunicación de procesos paralelos IFIP-77, agosto de 1977.
- Henry Baker y Carl Hewitt The Incremental Garbage Collection of Processes Proceedings of the Symposium on Artificial Intelligence Programming Languages. Avisos SIGPLAN 12, agosto de 1977.
- Aki Yonezawa Especificaciones y técnicas de verificación para programas paralelos basadas en la semántica de aprobación de mensajes MIT EECS Tesis doctoral. Diciembre de 1977.
- Henry Baker . Actor Sistemas de Computación en Tiempo Real MIT EECS Tesis Doctoral. Enero de 1978.
- George Milne y Robin Milner . Procesos concurrentes y su sintaxis JACM. Abril de 1979.
- Nissim Francez , CAR Hoare , Daniel Lehmann y Willem de Roever. Semántica del no determinismo, concurrencia y comunicación Journal of Computer and System Sciences. Diciembre de 1979.
- Nancy Lynch y Michael Fischer. Sobre describir el comportamiento de sistemas distribuidos en Semántica de Computación Concurrente. Springer-Verlag. 1979.
- Will Clinger. Fundamentos de la semántica del actor MIT Matemáticas Tesis doctoral. Junio de 1981.
- JA Bergstra y JW Klop. Álgebra de procesos para información y control de comunicación síncrona . 1984.
- Eike Best . Comportamiento concurrente: secuencias, procesos y axiomas Lecture Notes in Computer Science Vol.197 1984.
- Luca Cardelli. Un modelo de implementación del seminario de comunicación de encuentro sobre concurrencia. Apuntes de conferencias en Ciencias de la Computación 197. Springer-Verlag. 1985
- Robin Milner, Joachim Parrow y David Walker. Cálculo de procesos móviles Departamento de Ciencias de la Computación de Edimburgo. Informes ECS-LFCS-89-85 y ECS-LFCS-89-86. Junio de 1989. Revisado en septiembre de 1990 y octubre de 1990, respectivamente.
- Robin Milner. The Polyadic pi-Calculus: A Tutorial de la Universidad de Edimburgo. Informe LFCS ECS-LFCS-91-180. 1991.
- Kohei Honda y Mario Tokoro. Un cálculo de objetos para la comunicación asincrónica ECOOP 91.
- Benjamin Pierce, Didier Rémy y David Turner. Lenguaje de programación mecanografiado de orden superior basado en el taller pi-calculus sobre teoría de tipos y su aplicación a sistemas informáticos. Universidad de Kyoto. Julio de 1993.
- Cédric Fournet y Georges Gonthier . La máquina abstracta química reflexiva y el cálculo combinado POPL 1996.
- Cédric Fournet, Georges Gonthier, Jean-Jacques Lévy, Luc Maranget y Didier Rémy. Un cálculo de agentes móviles CONCUR 1996.
- Gérard Boudol. El pi-cálculo en estilo directo POPL 1997
- Tatsurou Sekiguchi y Akinori Yonezawa . Un cálculo con Code Mobility FMOODS 1997.
- Luca Cardelli y Andrew D. Gordon . Ambientes móviles Fundamentos de la ciencia del software y las estructuras computacionales, Maurice Nivat (Ed.), Lecture Notes in Computer Science, Vol. 1378, Springer, 1998.
- Robin Milner. Sistemas móviles y de comunicación: Pi-Calculus Cambridge University Press. 1999.
- JCM Baeten. Una breve historia del álgebra de procesos Informática teórica. 2005. (enlace válido a partir de 2015_26_5_0004)
- JCM Baeten, T. Basten y MA Reniers. Álgebra de los procesos de comunicación Cambridge University Press. 2005.
- He Jifeng y CAR Hoare. Vinculación de las teorías de la concurrencia Instituto Internacional de Tecnología de Software de la Universidad de las Naciones Unidas Informe UNU-IIST No. 328. Julio de 2005.
- Luca Aceto y Andrew D. Gordon (editores). Cálculos de procesos algebraicos: los primeros veinticinco años y más allá del álgebra de procesos. Bertinoro, Forl`ı, Italia, 1 al 5 de agosto de 2005.
- Carl Hewitt. ¿Qué es el compromiso? COIN @ AAMAS Físico, Organizacional y Social . 27 de abril de 2006b.
- Carl Hewitt (2007a) ¿Qué es el compromiso? Físico, Organizacional y Social (Revisado) Pablo Noriega .et al. editores. LNAI 4386. Springer-Verlag. 2007.
- Carl Hewitt (2007b) La computación organizacional a gran escala requiere paraconsistencia no estratificada y reflexión COIN @ AAMAS'07.