En informática , el modelo Actor , publicado por primera vez en 1973, es un modelo matemático de cálculo concurrente .
Orden de eventos versus estado global
Un desafío fundamental en la definición del modelo Actor es que no preveía estados globales de modo que un paso computacional no pudiera definirse como pasar de un estado global al siguiente estado global como se había hecho en todos los modelos de cálculo anteriores.
En 1963 en el campo de la Inteligencia Artificial , John McCarthy introdujo variables de situación en lógica en el Cálculo Situacional. En McCarthy y Hayes 1969, una situación se define como "el estado completo del universo en un instante de tiempo". En este sentido, las situaciones de McCarthy no son adecuadas para su uso en el modelo Actor ya que no tiene estados globales.
A partir de la definición de Actor, se puede ver que ocurren numerosos eventos: decisiones locales, creación de Actores, envío de mensajes, recepción de mensajes y designación de cómo responder al siguiente mensaje recibido. Los ordenamientos parciales de tales eventos se han axiomatizado en el modelo Actor y se ha explorado su relación con la física (ver Teoría del modelo Actor ).
Relación con la física
Según Hewitt (2006), el modelo Actor se basa en la física en contraste con otros modelos de computación que se basaban en la lógica matemática, la teoría de conjuntos, el álgebra, etc. La física influyó en el modelo Actor de muchas formas, especialmente la física cuántica y la física relativista. . Un problema es lo que se puede observar sobre los sistemas Actor. La pregunta no tiene una respuesta obvia porque plantea desafíos tanto teóricos como de observación similares a los que habían surgido al construir los fundamentos de la física cuántica. En términos concretos para los sistemas Actor, normalmente no podemos observar los detalles por los cuales se determina el orden de llegada de los mensajes para un Actor (ver Indeterminación en cálculo concurrente ). Intentar hacerlo afecta los resultados e incluso puede llevar la indeterminación a otra parte. por ejemplo , ver metaestabilidad en electrónica . En lugar de observar el interior de los procesos de arbitraje de los cálculos de Actor, esperamos los resultados.
Modelos anteriores al modelo Actor
El modelo Actor se basa en modelos de cálculo anteriores.
Cálculo lambda
El cálculo lambda de Alonzo Church puede verse como el primer lenguaje de programación que pasa mensajes (ver Hewitt, Bishop y Steiger 1973; Abelson y Sussman 1985 ). Por ejemplo, la expresión lambda a continuación implementa una estructura de datos de árbol cuando se suministra con parámetros para un leftSubTree y rightSubTree . Cuando un árbol de este tipo recibe un mensaje de parámetro "getLeft" , devuelve leftSubTree e igualmente cuando se le da el mensaje "getRight" vuelve rightSubTree .
λ (subárbol izquierdo, subárbol derecho) λ (mensaje) if (message == "getLeft") then leftSubTree else if (message == "getRight") then rightSubTree
Sin embargo, la semántica del cálculo lambda se expresó mediante la sustitución de variables en la que los valores de los parámetros se sustituyeron en el cuerpo de una expresión lambda invocada. El modelo de sustitución no es adecuado para la concurrencia porque no permite la capacidad de compartir recursos cambiantes. Inspirado por el cálculo lambda, el intérprete del lenguaje de programación Lisp hizo uso de una estructura de datos llamada entorno para que los valores de los parámetros no tuvieran que ser sustituidos en el cuerpo de una expresión lambda invocada. Esto permitió compartir los efectos de actualizar las estructuras de datos compartidas, pero no proporcionó concurrencia.
Simula
Simula 67 fue pionera en el uso del paso de mensajes para la computación, motivado por aplicaciones de simulación de eventos discretos. Estas aplicaciones se habían vuelto grandes y no modulares en los lenguajes de simulación anteriores. En cada paso de tiempo, un gran programa central tendría que revisar y actualizar el estado de cada objeto de simulación que cambia según el estado de los objetos de simulación con los que interactúa en ese paso. Kristen Nygaard y Ole-Johan Dahl desarrollaron la idea (descrita por primera vez en un taller de IFIP en 1967) de tener métodos en cada objeto que actualizarían su propio estado local basado en mensajes de otros objetos. Además, introdujeron una estructura de clases para objetos con herencia . Sus innovaciones mejoraron considerablemente la modularidad de los programas.
Sin embargo, Simula utilizó una estructura de control de corrutinas en lugar de una verdadera concurrencia.
Charla
Alan Kay se vio influenciado por el paso de mensajes en la invocación dirigida por patrones de Planner al desarrollar Smalltalk -71. A Hewitt le intrigaba Smalltalk-71, pero le desanimaba la complejidad de la comunicación que incluía invocaciones con muchos campos, como global , remitente , receptor , estilo de respuesta , estado , respuesta , selector de operador , etc.
En 1972, Kay visitó el MIT y discutió algunas de sus ideas para Smalltalk-72 basándose en el trabajo de Logo de Seymour Papert y el modelo de computación de "personita" utilizado para enseñar a los niños a programar. Sin embargo, el mensaje de Smalltalk-72 fue bastante complejo. El intérprete vio el código en el idioma como simplemente un flujo de tokens. Como Dan Ingalls lo describió más tarde:
- El primer (token) encontrado (en un programa) se buscó en el contexto dinámico para determinar el receptor del mensaje siguiente. La búsqueda de nombres comenzó con el diccionario de clases de la activación actual. Al fallar allí, se trasladó al remitente de esa activación y así sucesivamente en la cadena de remitentes. Cuando finalmente se encontró un enlace para el token, su valor se convirtió en el receptor de un nuevo mensaje y el intérprete activó el código para la clase de ese objeto.
Por lo tanto, el modelo de paso de mensajes en Smalltalk-72 estaba estrechamente vinculado a un modelo de máquina particular y a una sintaxis de lenguaje de programación que no se prestaba a la concurrencia. Además, aunque el sistema se arrancó por sí mismo, las construcciones del lenguaje no se definieron formalmente como objetos que responden a los mensajes Eval (consulte la discusión a continuación). Esto llevó a algunos a creer que un nuevo modelo matemático de cálculo concurrente basado en el paso de mensajes debería ser más simple que Smalltalk-72.
Las versiones posteriores del lenguaje Smalltalk siguieron en gran medida el camino del uso de los métodos virtuales de Simula en la estructura de transmisión de mensajes de los programas. Sin embargo, Smalltalk-72 convirtió primitivas como enteros, números de coma flotante, etc. en objetos . Los autores de Simula habían considerado convertir tales primitivos en objetos, pero se abstuvieron en gran medida por razones de eficiencia. Java al principio usó el expediente de tener versiones primitivas y de objetos de enteros, números de punto flotante, etc. El lenguaje de programación C # (y versiones posteriores de Java, comenzando con Java 1.5) adoptó la solución menos elegante de usar boxing y unboxing , un variante de la que se había utilizado anteriormente en algunas implementaciones de Lisp .
El sistema Smalltalk llegó a ser muy influyente, innovando en pantallas de mapa de bits, computación personal, la interfaz del navegador de clases y muchas otras formas. Para obtener más información, consulte The Early History of Smalltalk de Kay . [1] Mientras tanto, los esfuerzos de Actor en el MIT se mantuvieron enfocados en desarrollar la ciencia y la ingeniería de la concurrencia de alto nivel. (Consulte el artículo de Jean-Pierre Briot para conocer las ideas que se desarrollaron más adelante sobre cómo incorporar algunos tipos de concurrencia de actores en versiones posteriores de Smalltalk).
Redes de Petri
Antes del desarrollo del modelo Actor, las redes de Petri se usaban ampliamente para modelar la computación no determinista. Sin embargo, se reconoció ampliamente que tenían una limitación importante: modelaron el flujo de control pero no el flujo de datos. En consecuencia, no se podían componer fácilmente, lo que limitaba su modularidad. Hewitt señaló otra dificultad con las redes de Petri: la acción simultánea. Es decir , el paso atómico de cálculo en redes de Petri es una transición en la que los tokens desaparecen simultáneamente de los lugares de entrada de una transición y aparecen en los lugares de salida. La base física de utilizar un primitivo con este tipo de simultaneidad le parecía cuestionable. A pesar de estas aparentes dificultades, las redes de Petri continúan siendo un enfoque popular para modelar la concurrencia y siguen siendo objeto de una investigación activa.
Hilos, bloqueos y búferes (canales)
Antes del modelo Actor, la concurrencia se definía en términos de máquina de bajo nivel de subprocesos , bloqueos y búferes ( canales ). Es cierto que las implementaciones del modelo Actor suelen hacer uso de estas capacidades de hardware. Sin embargo, no hay ninguna razón por la que el modelo no se pueda implementar directamente en el hardware sin exponer los subprocesos y bloqueos del hardware. Además, no existe una relación necesaria entre el número de actores, subprocesos y bloqueos que pueden estar involucrados en un cálculo. Las implementaciones del modelo Actor son libres de hacer uso de hilos y bloqueos de cualquier forma que sea compatible con las leyes de los Actores.
Resumen de los detalles de implementación
Un desafío importante en la definición del modelo Actor fue abstraer los detalles de implementación.
Por ejemplo, considere la siguiente pregunta: "¿Cada actor tiene una cola en la que se almacenan sus comunicaciones hasta que el actor las recibe para procesarlas?" Carl Hewitt argumentó en contra de incluir tales colas como parte integral del modelo Actor. Una consideración fue que tales colas podrían modelarse como Actores que recibieron mensajes para poner en cola y quitar la cola de las comunicaciones. Otra consideración fue que algunos Actores no usarían tales colas en su implementación real. Por ejemplo, un actor podría tener una red de árbitros en su lugar. Por supuesto, existe una abstracción matemática que es la secuencia de comunicaciones que ha recibido un Actor. Pero esta secuencia surgió solo cuando el Actor operaba. De hecho, el orden de esta secuencia puede ser indeterminado (ver Indeterminación en cálculo concurrente ).
Otro ejemplo de abstracción de los detalles de la implementación fue la cuestión de la interpretación : "¿Debería la interpretación ser una parte integral del modelo Actor?" La idea de la interpretación es que un actor se definiría por la forma en que se procesó el guión eval mensajes. (De esta manera, los actores se definirían de una manera análoga a Lisp que fue "definido" por un procedimiento de interpretación meta-circular llamado eval escrito en Lisp.) Hewitt argumentó en contra de hacer que la interpretación sea parte integral del modelo Actor. Una consideración fue que para procesar la eval , el script de programa de un Actor tendría en sí mismo un script de programa (que a su vez tendría ...). Otra consideración fue que algunos actores no usarían la interpretación en su interpretación real. Por ejemplo, un actor podría implementarse en hardware en su lugar. Por supuesto, no hay nada de malo en la interpretación per se . También implementando intérpretes usando Los mensajes de evaluación son más modulares y extensibles que el enfoque de intérprete monolítico de Lisp.
Modelo operacional
Sin embargo, el progreso en el desarrollo del modelo fue constante. En 1975, Irene Greif publicó el primer modelo operativo en su disertación.
Esquema
Luego, Gerald Sussman y Guy Steele se interesaron por Actors y publicaron un artículo sobre su intérprete de Scheme en el que concluían que "descubrimos que los 'actores' y las expresiones lambda eran idénticas en su implementación". Según Hewitt, el cálculo lambda es capaz de expresar algunos tipos de paralelismo pero, en general, no la concurrencia expresada en el modelo Actor. Por otro lado, el modelo Actor es capaz de expresar todo el paralelismo en el cálculo lambda.
Leyes para actores
Dos años después de que Greif publicara su modelo operativo, Carl Hewitt y Henry Baker publicaron Leyes para actores.
Prueba de continuidad de funciones computables
Usando las leyes del modelo Actor, Hewitt y Baker demostraron que cualquier Actor que se comporte como una función es continuo en el sentido definido por Dana Scott (ver semántica denotacional ).
Especificaciones y pruebas
Aki Yonezawa publicó sus técnicas de especificación y verificación para Actores. Russ Atkinson y Carl Hewitt publicaron un artículo sobre técnicas de especificación y prueba para serializadores que brindan una solución eficiente para encapsular recursos compartidos para el control de concurrencia .
Caracterización matemática utilizando la teoría de dominios
Finalmente, ocho años después de la primera publicación de Actor, Will Clinger (basado en el trabajo de Irene Greif 1975, Gordon Plotkin 1976, Michael Smyth 1978, Henry Baker 1978, Francez, Hoare , Lehmann y de Roever 1979, y Milne y Milnor 1979) publicó el primer modelo denotacional matemático satisfactorio que incorpora el no determinismo ilimitado utilizando la teoría del dominio en su disertación en 1981 (ver el modelo de Clinger ). Posteriormente, Hewitt [2006] aumentó los diagramas con tiempos de llegada para construir un modelo denotacional técnicamente más simple y más fácil de entender. Consulte Historia de la semántica denotacional .
Ver también
- Modelo de actor e historia de cálculo de procesos
- Historia de la semántica denotacional
- Actor modelo historia media
- Modelo de actor historia posterior
Referencias
- ^ Kay, Alan (marzo de 1993). "La historia temprana de Smalltalk" (PDF) . Avisos ACM SIGPLAN . 28 (3): 69–75. doi : 10.1145 / 155360.155364 . Archivado desde el original (PDF) el 5 de febrero de 2012.
- Carl Hewitt; Peter Bishop; Richard Steiger (1973). "Un formalismo universal de actor modular para la inteligencia artificial" . IJCAI: 235–245. Cite journal requiere
|journal=
( ayuda ) - McCarthy, John (1963). "Situaciones, acciones y leyes causales". Memo de informe técnico . Laboratorio de Inteligencia Artificial de la Universidad de Stanford (2).
- McCarthy, John; Hayes, Patrick (1969). "Algunos problemas filosóficos desde el punto de vista de la inteligencia artificial". Inteligencia de máquina . Prensa de la Universidad de Edunburgh (4): 463–502. CiteSeerX 10.1.1.85.5082 .
- Heisenberg, Werner (1971). Física y más allá: encuentros y conversaciones . Traducido por AJ Pomerans. Nueva York: Harper & Row. págs. 63–64. ISBN 978-0061316227.
- Hewitt, Carl; Obispo, Peter; Greif, Irene; Smith, Brian; Matson, Todd; Steiger, Richard (enero de 1974). "Inducción y metaevaluación del actor". Acta de la conferencia del simposio de ACM sobre principios de lenguajes de programación : 153–168. CiteSeerX 10.1.1.104.295 . doi : 10.1145 / 512927.512942 .
- Hewitt, Carl (abril de 1974). "Semántica conductual de la estructura de control no recursiva" . Actas de Colloque Sur la Programmation : 385–407. ISBN 9783540068594.
- Greif, Irene; Hewitt, Carl (enero de 1975). "Semántica del actor de PLANNER-73". Acta de la conferencia del simposio de ACM sobre principios de lenguajes de programación : 67–77. doi : 10.1145 / 512976.512984 .
- Hewitt, Carl (septiembre de 1975). "Cómo utilizar lo que sabe". Actas de la IV Conferencia Conjunta Internacional sobre Inteligencia Artificial . 1 : 189-198.
- Greif, Irene (1975). Semántica de la comunicación de profesas paralelas (Ph.D.). MIT EECS .
- Baker, Henry; Hewitt, Carl (agosto de 1977). "La recolección de basura incremental de procesos" . Actas del Simposio sobre lenguajes de programación de inteligencia artificial .[ enlace muerto permanente ]
- Hewitt, Carl; Baker, Henry (agosto de 1977). "Leyes para la comunicación de procesos paralelos". Federación Internacional de Procesamiento de la Información . hdl : 1721,1 / 41962 .
- Yonezawa, Aki (1977). Técnicas de especificación y verificación para programas paralelos basados en la semántica de paso de mensajes (Ph.D.). MIT EECS .
- Obispo, Peter (1977). Espacio de direcciones muy grande Sistemas informáticos extensibles modularmente (Ph.D.). MIT EECS .
- Hewitt, Carl (junio de 1977). "Visualización de estructuras de control como patrones de transmisión de mensajes". Revista de Inteligencia Artificial . hdl : 1721,1 / 6272 .
- Baker, Henry (1978). Actor Sistemas para Computación en Tiempo Real (Ph.D.). MIT EECS .
- Hewitt, Carl; Atkinson, Russ (enero de 1979). "Técnicas de especificación y prueba para serializadores". Revista IEEE sobre ingeniería de software : 10–23. doi : 10.1109 / TSE.1979.234149 . hdl : 1721,1 / 5756 .
- Kahn, Ken (1979). Una teoría computacional de la animación (Ph.D.). MIT EECS .
- Hewitt, Carl; Attardi, Beppe; Lieberman, Henry (octubre de 1979). "Delegación en el paso de mensajes". Actas de la Primera Conferencia Internacional sobre Sistemas Distribuidos . Huntsville, Alabama.
- Atkinson, Russ (1980). Verificación automática de serializadores (Ph.D.). MIT .
- Kornfeld, Bill; Hewitt, Carl (enero de 1981). "La metáfora de la comunidad científica" (PDF) . Transacciones IEEE sobre sistemas, hombre y cibernética . 11 : 24–33. doi : 10.1109 / TSMC.1981.4308575 . hdl : 1721,1 / 5693 .
- Lieberman, Henry (mayo de 1981). "Pensar en muchas cosas a la vez sin confundirse: paralelismo en el acto 1". Nota de IA del MIT (626). hdl : 1721,1 / 6351 .
- Lieberman, Henry (junio de 1981). "Una vista previa del acto 1". Nota de IA del MIT (625). hdl : 1721,1 / 6350 .
- Barbero, Gerry (1981). Razonamiento sobre el cambio en los sistemas de oficina informados (Ph.D.). MIT EECS .
- Kornfeld, Bill (1981). Paralelismo en la resolución de problemas (Ph.D.). MIT EECS .
- Clinger, Will (1981). Fundamentos de la semántica del actor (Ph.D.). Matemáticas del MIT .
- Theriault, Daniel (abril de 1982). "Una cartilla para el lenguaje Act-1". Nota de IA del MIT (672). hdl : 1721,1 / 5675 .
- Lieberman, Henry; Hewitt, Carl (junio de 1983). "Un recolector de basura en tiempo real basado en la vida útil de los objetos". Comunicaciones de la ACM . 26 (6): 419. CiteSeerX 10.1.1.123.5055 . doi : 10.1145 / 358141.358147 .
- Theriault, Daniel (junio de 1983). "Problemas en el diseño e implementación de la Ley 2". Informe técnico de IA del MIT (728). hdl : 1721,1 / 6940 .
- Lieberman, Henry (agosto de 1983). "Un simulador orientado a objetos para el colmenar" (PDF) . Conferencia de la Asociación Americana de Inteligencia Artificial . Washington DC
- Hewitt, Carl; de Jong, Peter (agosto de 1983). "Análisis de los roles de descripciones y acciones en sistemas abiertos". Actas de la Conferencia Nacional de Inteligencia Artificial . hdl : 1721,1 / 5649 .
- Jammer, M. (1985). "El problema de la EPR en su desarrollo histórico". En P. Lahti, P. Mittelstaedt (ed.). Simposio sobre los fundamentos de la física moderna: 50 años del experimento Einstein-Podolsky-Rosen Gedanken . Singapur: World Scientific. págs. 129-149.
- Bien, A. (1986). El juego inestable: el realismo de Einstein y la teoría cuántica . Chicago: Prensa de la Universidad de Chicago. ISBN 978-0226249476.
- Hewitt, Carl; Lieberman, Henry (noviembre de 1983). "Problemas de diseño en arquitectura paralela para inteligencia artificial". Nota de IA del MIT (750). hdl : 1721,1 / 5653 .
- Fuchs, Christopher (2002). "Mecánica cuántica como información cuántica (y solo un poco más)". En A. Khrenikov (ed.). Teoría cuántica: reconstrucción de cimientos . Växjo: Växjo University Press.
- Hewitt, Carl (27 de abril de 2006). "¿Qué es el compromiso? Físico, organizacional y social" (PDF) . COIN @ AAMAS .