Hispanopedia Wiki
Articulo de referencia

Historia del modelo Actor

En informática , el modelo Actor , publicado por primera vez en 1973, es un modelo matemático de computación concurrente . Ordenación de eventos frente al estado global Un desaf...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , el modelo Actor , publicado por primera vez en 1973, es un modelo matemático de computación concurrente .

Ordenación de eventos frente al estado global

Un desafío fundamental al definir el modelo Actor es que no contemplaba estados globales, por lo que un paso computacional no podía definirse como el paso de un estado global al siguiente, como se había hecho en todos los modelos de computación anteriores.

En 1963, en el campo de la Inteligencia Artificial , John McCarthy introdujo las variables de situación en la lógica, concretamente en el Cálculo Situacional. En McCarthy y Hayes (1969), una situación se define como «el estado completo del universo en un instante dado». En este sentido, las situaciones de McCarthy no son adecuadas para su uso en el modelo de Actor, ya que este carece de estados globales.

A partir de la definición de Actor, se observa que tienen lugar numerosos eventos: decisiones locales, creación de Actores, envío y recepción de mensajes, y designación de cómo responder al siguiente mensaje recibido. En el modelo de Actor se han axiomatizado órdenes parciales de dichos eventos y se ha explorado su relación con la física (véase la teoría del modelo de Actor ).

Relación con la física

Según Hewitt (2006), el modelo Actor se basa en la física, a diferencia de 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 maneras, especialmente la física cuántica y la física relativista . Una cuestión es qué se puede observar sobre los sistemas Actor. La pregunta no tiene una respuesta obvia, ya que plantea desafíos tanto teóricos como observacionales similares a los que surgieron 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 (véase Indeterminación en la computación concurrente ). Intentar hacerlo afecta los resultados e incluso puede trasladar la indeterminación a otros ámbitos. Por ejemplo , véase Metaestabilidad en electrónica . En lugar de observar el interior de los procesos de arbitraje de las computaciones Actor, esperamos los resultados.

Modelos anteriores al modelo Actor

El modelo Actor se basa en modelos de computación anteriores.

Cálculo lambda

El cálculo lambda de Alonzo Church puede considerarse el primer lenguaje de programación de paso de mensajes (véase Hewitt, Bishop y Steiger, 1973; Abelson y Sussman, 1985 ). Por ejemplo, la expresión lambda que se muestra a continuación implementa una estructura de datos de árbol cuando se le proporcionan parámetros para leftSubTree y rightSubTree . Cuando a dicho árbol se le proporciona el parámetro "getLeft" , devuelve leftSubTree , y de igual manera, cuando se le proporciona el mensaje "getRight", devuelve rightSubTree .

λ(subárbol izquierdo, subárbol derecho) λ(mensaje) si (mensaje == "getLeft") entonces leftSubTree sino si (mensaje == "getRight") entonces rightSubTree

Sin embargo, la semántica del cálculo lambda se expresaba mediante la sustitución de variables, en la que los valores de los parámetros se insertaban en el cuerpo de la expresión lambda invocada. Este modelo de sustitución no es adecuado para la concurrencia, ya que no permite compartir recursos modificables. Inspirado en el cálculo lambda, el intérprete del lenguaje de programación Lisp utilizó una estructura de datos denominada entorno, de modo que no era necesario sustituir los valores de los parámetros en el cuerpo de la expresión lambda invocada. Esto permitía compartir los efectos de la actualización de estructuras de datos compartidas, pero no garantizaba la concurrencia.

Simula

Simula 67 fue pionero en el uso del paso de mensajes para la computación, motivado por las aplicaciones de simulación de eventos discretos. Estas aplicaciones se habían vuelto extensas y no modulares en los lenguajes de simulación anteriores. En cada paso de tiempo, un programa central extenso debía recorrer y actualizar el estado de cada objeto de simulación, el cual cambiaba según el estado de los objetos con los que interactuaba en ese paso. Kristen Nygaard y Ole-Johan Dahl desarrollaron la idea (descrita por primera vez en un taller de la IFIP en 1967) de contar con métodos en cada objeto que actualizaran su propio estado local en función de los 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 informal

Alan Kay se vio influenciado por el paso de mensajes en la invocación dirigida por patrones de Planner al desarrollar Smalltalk -71. Hewitt estaba intrigado por 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 habló sobre algunas de sus ideas para Smalltalk-72, basándose en el trabajo de Seymour Papert con Logo y el modelo de computación de "persona pequeña" utilizado para enseñar a programar a los niños. Sin embargo, el paso de mensajes de Smalltalk-72 era bastante complejo. El intérprete veía el código en este lenguaje simplemente como una secuencia de tokens. Como lo describió más tarde Dan Ingalls :

El primer token encontrado en un programa se consultaba en el contexto dinámico para determinar el receptor del mensaje subsiguiente. La búsqueda del nombre comenzaba con el diccionario de clases de la activación actual. Si no se encontraba allí, se pasaba al emisor de dicha activación y así sucesivamente a lo largo de la cadena de emisores. Cuando finalmente se encontraba una vinculación para el token, su valor se convertía en el receptor de un nuevo mensaje, y el intérprete activaba el código de la clase de ese objeto.

Por lo tanto, el modelo de paso de mensajes en Smalltalk-72 estaba estrechamente ligado a un modelo de máquina y una sintaxis de lenguaje de programación específicos que no se prestaban a la concurrencia. Además, aunque el sistema se basaba en sí mismo, las construcciones del lenguaje no estaban definidas formalmente como objetos que respondieran a mensajes Eval (véase la discusión a continuación). Esto llevó a algunos a creer que un nuevo modelo matemático de computación 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 de usar los métodos virtuales de Simula en la estructura de paso 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 dichas primitivas en objetos, pero se abstuvieron principalmente por razones de eficiencia. Java, en un principio, utilizó la solución de tener versiones tanto primitivas como de objetos para enteros, números de coma flotante, etc. El lenguaje de programación C# (y versiones posteriores de Java, a partir de Java 1.5) adoptaron el uso de boxing y unboxing , una variante de la cual 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, informática personal, la interfaz del navegador de clases y muchas otras áreas. Para más detalles, véase The Early History of Smalltalk de Kay . [ 1 ] Mientras tanto, los esfuerzos del MIT en el campo de los actores se mantuvieron enfocados en el desarrollo de la ciencia y la ingeniería de la concurrencia de alto nivel. (Véase el artículo de Jean-Pierre Briot para conocer ideas que se desarrollaron posteriormente 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 utilizaban ampliamente para modelar la computación no determinista. Sin embargo, se reconocía que tenían una limitación importante: modelaban el flujo de control, pero no el flujo de datos. En consecuencia, no eran fácilmente componibles, lo que limitaba su modularidad. Hewitt señaló otra dificultad de las redes de Petri: la acción simultánea. Es decir , el paso atómico de la computación en las redes de Petri es una transición en la que los tokens desaparecen simultáneamente de las entradas de una transición y aparecen en las salidas. La base física del uso de una primitiva con este tipo de simultaneidad le parecía cuestionable. A pesar de estas dificultades aparentes, las redes de Petri siguen siendo un enfoque popular para modelar la concurrencia y continúan siendo objeto de investigación activa.

Hilos, bloqueos y búferes (canales)

Antes del modelo de Actores, la concurrencia se definía en términos de bajo nivel de máquina, como hilos , bloqueos y búferes ( canales ). Si bien es cierto que las implementaciones del modelo de Actores suelen utilizar estas capacidades de hardware, no hay razón para que el modelo no pueda implementarse directamente en hardware sin exponer hilos ni bloqueos. Además, no existe una relación necesaria entre el número de Actores, hilos y bloqueos que puedan participar en un cálculo. Las implementaciones del modelo de Actores pueden utilizar hilos y bloqueos de cualquier forma compatible con las reglas de los Actores.

Abstraer los detalles de implementación

Un reto importante a la hora de definir el modelo de Actor fue abstraer los detalles de implementación.

Por ejemplo, consideremos la siguiente pregunta: "¿Cada Actor tiene una cola donde se almacenan sus comunicaciones hasta que las recibe para procesarlas?". Carl Hewitt argumentó en contra de incluir dichas colas como parte integral del modelo de Actor. Una consideración era que estas colas podrían modelarse como Actores que reciben mensajes para encolar y desencolar las comunicaciones. Otra consideración era que algunos Actores no usarían dichas colas en su implementación real. Por ejemplo, un Actor podría tener una red de árbitros . Por supuesto, existe una abstracción matemática que es la secuencia de comunicaciones recibidas por un Actor. Pero esta secuencia solo surge a medida que el Actor opera. De hecho, el orden de esta secuencia puede ser indeterminado (véase Indeterminación en la computación concurrente ).

Otro ejemplo de abstracción de los detalles de 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 cómo su script de programa procesa los mensajes eval . (De esta manera, los Actores se definirían de forma análoga a Lisp , que se "definía" mediante un procedimiento intérprete metacircular llamado eval escrito en Lisp). Hewitt argumentó en contra de hacer de la interpretación una parte integral del modelo Actor. Una consideración era que, para procesar los mensajes eval , el script de programa de un Actor tendría a su vez otro script de programa (¡que a su vez tendría...!). Otra consideración era que algunos Actores no usarían la interpretación en su interpretación real. Por ejemplo, un Actor podría implementarse en hardware. Por supuesto, no hay nada malo en la interpretación en sí misma . Además, implementar intérpretes usando mensajes eval es más modular y extensible que el enfoque monolítico de intérprete de Lisp.

Modelo operativo

Sin embargo, el desarrollo del modelo avanzó de forma constante. En 1975, Irene Greif publicó el primer modelo operativo en su tesis doctoral.

Esquema

Gerald Sussman y Guy Steele se interesaron entonces por los Actores y publicaron un artículo sobre su intérprete de Scheme en el que concluyeron: «Descubrimos que los "actores" y las expresiones lambda eran idénticos en su implementación». Según Hewitt, el cálculo lambda es capaz de expresar ciertos tipos de paralelismo, pero, en general, no la concurrencia expresada en el modelo de Actores. Por otro lado, el modelo de Actores es capaz de expresar todo el paralelismo del cálculo lambda.

Leyes para actores

Dos años después de que Greif publicara su modelo operativo, Carl Hewitt y Henry Baker publicaron Las leyes para actores.

Prueba de continuidad de funciones computables

Utilizando las leyes del modelo Actor, Hewitt y Baker demostraron que cualquier Actor que se comporta como una función es continuo en el sentido definido por Dana Scott (véase 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 proporciona una solución eficiente para encapsular recursos compartidos para el control de concurrencia .

Caracterización matemática mediante la teoría de dominios

Finalmente, ocho años después de la primera publicación de Actor, Will Clinger (basándose 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 incorporaba el no determinismo no acotado utilizando la teoría de dominios en su disertación en 1981 (véase 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. Véase Historia de la semántica denotacional .

Véase también

Referencias

  1. ↑ Kay, Alan (marzo de 1993). "La historia temprana del Smalltalk" (PDF) . ACM SIGPLAN Notices . 28 (3): 69–75 . doi : 10.1145/155360.155364 . Archivado del original (PDF) el 5 de febrero de 2012.

Bibliografía

  • Hewitt, Carl; Bishop, Peter; Steiger, Richard (1973). "Un formalismo de actor modular universal para la inteligencia artificial" . IJCAI'73: Actas de la 3.ª Conferencia Internacional Conjunta sobre Inteligencia Artificial . págs. 235–245 . 
  • McCarthy, John (1963). "Situaciones, acciones y leyes causales". Informe técnico (2). Laboratorio de Inteligencia Artificial de la Universidad de Stanford.
  • McCarthy, John; Hayes, Patrick (1969). "Algunos problemas filosóficos desde el punto de vista de la inteligencia artificial". Machine Intelligence (4). Edinburgh University Press : 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; Bishop, Peter; Greif, Irene; Smith, Brian; Matson, Todd; Steiger, Richard (enero de 1974). "Inducción de actores y metaevaluación". Actas del 1er Simposio anual ACM SIGACT-SIGPLAN sobre Principios de Lenguajes de Programación – POPL '73 . págs. 153–168 . CiteSeerX 10.1.1.104.295 . doi : 10.1145/512927.512942 . S2CID 33611569 .   
  • Hewitt, Carl (abril de 1974). "Semántica conductual de estructuras de control no recursivas" . Simposio de programación, Actas Colloque sur la Programmation . Saltador. págs. 385 a 407. ISBN  9783540068594.
  • Greif, Irene; Hewitt, Carl (enero de 1975). "Semántica de actores de PLANNER-73". Actas del 2.º Simposio ACM SIGACT-SIGPLAN sobre Principios de Lenguajes de Programación – POPL '75 . págs. 67–77 . doi : 10.1145/512976.512984 . S2CID 18178340 .  
  • Hewitt, Carl (septiembre de 1975). "Cómo usar lo que sabes". Actas de la 4.ª Conferencia Internacional Conjunta sobre Inteligencia Artificial . 1 : 189–198 .
  • Greif, Irene (1975). Semántica de la comunicación de profesiones paralelas (Ph.D.). MIT EECS .
  • Baker, Henry; Hewitt, Carl (agosto de 1977). "La recolección incremental de basura de procesos" . Actas del simposio de 1977 sobre inteligencia artificial y lenguajes de programación . pp. 55–59 . doi : 10.1145/800228.806932 . hdl : 1721.1/41969 . S2CID 1557419 .  
  • Hewitt, Carl; Baker, Henry (agosto de 1977). "Leyes para la comunicación de procesos paralelos". Federación Internacional para el Procesamiento de la Información . hdl : 1721.1/41962 .
  • Yonezawa, Aki (1977). Técnicas de especificación y verificación para programas paralelos basadas en semántica de paso de mensajes (Ph.D.). MIT EECS .
  • Bishop, Peter (1977). Sistemas informáticos modularmente extensibles con un espacio de direcciones muy grande (Ph.D.). MIT EECS .
  • Hewitt, Carl (junio de 1977). "Visualizando las estructuras de control como patrones de paso de mensajes". Journal of Artificial Intelligence . 8 (3): 323– 364. doi : 10.1016/0004-3702(77)90033-9 . hdl : 1721.1/6272 .
  • Baker, Henry (1978). Sistemas de actores 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". IEEE Transactions on Software Engineering : 10–23 . doi : 10.1109/TSE.1979.234149 . hdl : 1721.1/5756 . S2CID 15272353 . 
  • 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) . IEEE Transactions on Systems, Man, and Cybernetics . 11 : 24–33 . doi : 10.1109/TSMC.1981.4308575 . hdl : 1721.1/5693 . S2CID 1322857 . 
  • Lieberman, Henry (mayo de 1981). "Pensar en muchas cosas a la vez sin confundirse: paralelismo en el acto 1". MIT AI Memo (626). hdl : 1721.1/6351 .
  • Lieberman, Henry (junio de 1981). "Un avance del acto 1". MIT AI Memo (625). hdl : 1721.1/6350 .
  • Barber, Gerry (1981). Razonamiento sobre el cambio en sistemas de oficina basados ​​en el conocimiento (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 de actores (Ph.D.). Matemáticas del MIT .
  • Theriault, Daniel (abril de 1982). "Una introducción al lenguaje del Acto 1". MIT AI Memo (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". Communications of the ACM . 26 (6): 419. CiteSeerX 10.1.1.123.5055 . doi : 10.1145/358141.358147 . S2CID 14161480 .  
  • Theriault, Daniel (junio de 1983). "Problemas en el diseño e implementación del Acto 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 apiario" (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 las descripciones y las acciones en los sistemas abiertos". Actas de la Conferencia Nacional sobre Inteligencia Artificial . hdl : 1721.1/5649 .
  • Jammer, M. (1985). "El problema EPR en su desarrollo histórico". En P. Lahti, P. Mittelstaedt (eds.). Simposio sobre los fundamentos de la física moderna: 50 años del experimento mental Einstein-Podolsky-Rosen . Singapur: World Scientific. pp. 129–149 . 
  • Fine, A. (1986). El juego inestable: el realismo de Einstein y la teoría cuántica . Chicago: University of Chicago Press. ISBN 978-0226249476.
  • Hewitt, Carl; Lieberman, Henry (noviembre de 1983). "Problemas de diseño en la arquitectura paralela para la inteligencia artificial". MIT AI Memo (750). hdl : 1721.1/5653 .
  • Fuchs, Christopher (2002). «La mecánica cuántica como información cuántica (y algo más)». En A. Khrenikov (ed.). Teoría cuántica: reconstrucción de los fundamentos . Växjo: Editorial de la Universidad de Växjo.
  • Hewitt, Carl (27 de abril de 2006). "¿Qué es el compromiso? Físico, organizacional y social" (PDF) . COIN@AAMAS .