máquina abstracta -Abstract machine

Una máquina abstracta es un modelo teórico de las ciencias de la computación que permite un análisis detallado y preciso de cómo funciona un sistema informático . Es análogo a una función matemática en que recibe entradas y produce salidas basadas en reglas predefinidas. Las máquinas abstractas difieren de las máquinas literales en que se espera que funcionen correctamente e independientemente del hardware . Las máquinas abstractas son “ máquinas ” porque permiten la ejecución paso a paso de programas ; son " abstractos " porque ignoran muchos aspectos del hardware actual.) máquinas. Una máquina abstracta típica consta de una definición en términos de entrada, salida y el conjunto de operaciones permitidas utilizadas para convertir la primera en la segunda. Se pueden usar por razones puramente teóricas, así como también como modelos para sistemas informáticos del mundo real. En la teoría de la computación , las máquinas abstractas se utilizan a menudo en experimentos mentales relacionados con la computabilidad o para analizar la complejidad de los algoritmos . Este uso de máquinas abstractas está relacionado con el campo de la teoría de la complejidad computacional , como las máquinas de estados finitos, las máquinas de Mealy , los autómatas push-down y las máquinas de Turing .


Clasificación

Las máquinas abstractas generalmente se clasifican en dos tipos según la cantidad de operaciones que pueden realizar en un momento dado: máquinas abstractas deterministas y máquinas abstractas no deterministas . Una máquina abstracta determinista es un sistema en el que un estado o condición inicial particular siempre produce los mismos resultados. No hay aleatoriedad ni variación en la forma en que las entradas se transforman en salidas. Mientras tanto, una máquina abstracta no determinista puede proporcionar varias salidas para la misma entrada en diferentes ejecuciones. A diferencia de un algoritmo determinista, que da el mismo resultado para la misma entrada independientemente del número de iteraciones, un algoritmo no determinista toma varios caminos para llegar a diferentes salidas. Los algoritmos no deterministas son útiles para obtener respuestas aproximadas cuando es difícil o costoso derivar una solución precisa utilizando un enfoque determinista.

Una carrera de una máquina de Turing .

La máquina de Turing , por ejemplo, es una de las máquinas abstractas más fundamentales de la informática. Esta es una máquina que puede realizar operaciones en una cinta (una cadena de símbolos) de cualquier longitud. Incluye instrucciones tanto para modificar los símbolos como para cambiar el símbolo en el que se basa. El único comando en una computadora rudimentaria de Turing sería "convertir el símbolo en 1 y luego moverlo a la derecha", y esta máquina solo produciría una cadena de 1s. Esta máquina de Turing básica es determinista; sin embargo, también se pueden construir máquinas de Turing no deterministas que pueden ejecutar varias acciones con la misma entrada.

Implementación de una Máquina Abstracta

Toda implementación de una máquina abstracta en el caso de implementación física (en hardware ) utiliza algún tipo de dispositivo físico (mecánico, electrónico, etc) para ejecutar las instrucciones de un lenguaje de programación . Sin embargo, la máquina abstracta también se puede implementar en software o firmware en niveles intermedios entre la máquina abstracta y el dispositivo físico subyacente.

Implementación del lenguaje de programación

El término " máquina " se refiere a una máquina informática, que es una máquina física que ejecuta algoritmos que han sido suficientemente formalizados para que la máquina los "entienda". Una máquina abstracta es, intuitivamente, nada más que una abstracción de la idea de una computadora física. Para la ejecución real, los algoritmos deben formalizarse adecuadamente utilizando las construcciones que ofrece un lenguaje de programación . Esto implica que los algoritmos a ejecutar deben expresarse mediante instrucciones del lenguaje de programación. La sintaxis de un lenguaje de programación permite la construcción de programas utilizando un conjunto finito de construcciones conocidas como instrucciones. La mayoría de las máquinas abstractas comparten un almacén de programas y un estado , que a menudo incluye una pila y registros. En las computadoras digitales, la pila es simplemente una unidad de memoria con un registro de direcciones que solo puede contar números enteros positivos (después de que se carga un valor inicial). El registro de dirección de la pila se conoce como puntero de pila porque su valor siempre se refiere al elemento superior de la pila. El programa consta de una serie de instrucciones, con un puntero de pila que indica la siguiente instrucción a realizar. Cuando se completa la instrucción, se avanza un puntero de pila . Este mecanismo de control fundamental de una máquina abstracta también se conoce como su bucle de ejecución . Así, una máquina abstracta para lenguaje de programación es cualquier colección de estructuras de datos y algoritmos capaces de almacenar y ejecutar programas escritos en el lenguaje de programación. Cierra la brecha entre el alto nivel de un lenguaje de programación y el bajo nivel de una máquina real proporcionando un paso de lenguaje intermedio para la compilación . Las instrucciones de una máquina abstracta se adaptan a las operaciones únicas necesarias para implementar operaciones de un determinado idioma de origen o conjunto de idiomas de origen.

Lenguajes de programación imperativos

A fines de la década de 1950, la Asociación de Maquinaria de Computación (ACM) y otras organizaciones aliadas desarrollaron muchas propuestas para el lenguaje universal orientado a la computadora (UNCOL) , como la máquina de Conway . El concepto UNCOL es bueno, pero no ha sido muy utilizado debido al bajo rendimiento del código generado . En muchas áreas de la informática, su rendimiento seguirá siendo un problema a pesar del desarrollo de la máquina virtual de Java a fines de la década de 1990. Algol Object Code (1964), P4-machine (1976), UCSD P-machine (1977) y Forth (1970) son algunas máquinas abstractas exitosas de este tipo.

Lenguajes de programación orientados a objetos

Las máquinas abstractas para lenguajes de programación orientados a objetos a menudo se basan en pilas y tienen instrucciones de acceso especiales para métodos y campos de objetos . En estas máquinas, la gestión de la memoria a menudo la realiza implícitamente un recolector de basura (función de recuperación de memoria integrada en los lenguajes de programación). Smalltalk-80 (1980), Self (1989) y Java (1994) son ejemplos de esta implementación.

Lenguajes de procesamiento de cadenas

Un lenguaje de procesamiento de cadenas es un lenguaje informático que se enfoca en procesar cadenas en lugar de números. Ha habido lenguajes de procesamiento de cadenas en forma de shells de comandos , herramientas de programación , procesadores de macros y lenguajes de secuencias de comandos durante décadas. El uso de una máquina abstracta adecuada tiene dos beneficios: mayor velocidad de ejecución y mayor portabilidad. Snobol4 y ML/I son dos instancias notables de los primeros lenguajes de procesamiento de cadenas que usan una máquina abstracta para obtener independencia de la máquina.

Lenguajes de programación funcional

Representación pictórica de una máquina Krivine .

Las primeras máquinas abstractas para lenguajes funcionales , incluida la máquina SECD (1964) y la Máquina abstracta funcional de Cardelli (1983), definieron una evaluación estricta, también conocida como evaluación ansiosa o llamada por valor , en la que los argumentos de la función se evalúan antes de la llamada. y precisamente una vez. En los últimos años, la mayoría de las investigaciones se han centrado en la evaluación perezosa (o llamada por necesidad) , como la máquina G (1984), la máquina Krivine (1985) y la máquina de tres instrucciones (1986), en la que los argumentos de función se evalúan solo si es necesario y como máximo una vez. Una razón es que ahora se comprende bien la implementación efectiva de una evaluación estricta, por lo que ha disminuido la necesidad de una máquina abstracta.

Lenguajes de programación lógica

El cálculo de predicados (lógica de primer orden) es la base de los lenguajes de programación lógica . El lenguaje de programación lógica más conocido es Prolog . Las reglas en Prolog están escritas en un formato uniforme conocido como 'cláusulas de Horn' cuantificadas universalmente, lo que significa comenzar el cálculo que intenta descubrir una prueba del objetivo. Warren Abstract Machine WAM (1983), que se ha convertido en el estándar de facto en la compilación de programas Prolog, ha sido el foco de la mayoría de los estudios. Proporciona instrucciones de propósito especial, como instrucciones de unificación de datos e instrucciones de flujo de control para respaldar el rastreo (algoritmo de búsqueda).

Estructura de una Máquina Abstracta

Una máquina abstracta genérica está compuesta por una memoria y un intérprete . La memoria se utiliza para almacenar datos y programas, mientras que el intérprete es el componente que ejecuta las instrucciones incluidas en los programas.

La estructura de una máquina abstracta.

El intérprete debe realizar las operaciones propias del idioma que está interpretando. Sin embargo, dada la variedad de lenguajes, es concebible identificar categorías de operaciones y un " mecanismo de ejecución " compartido por todos los intérpretes. Las operaciones del intérprete y las estructuras de datos que las acompañan se dividen en las siguientes categorías:

  1. Operaciones para procesar datos primitivos :
  2. Operaciones y estructuras de datos para controlar la secuencia de ejecución de operaciones ;
  3. Operaciones y estructuras de datos para controlar las transferencias de datos ;
  4. Operaciones y estructuras de datos para la gestión de memoria .

Operaciones para procesar datos primitivos

Incluso una máquina abstracta funciona mediante la ejecución de algoritmos, por lo que debe contener operaciones para manipular tipos de datos primitivos , como cadenas y números enteros. Por ejemplo, los números enteros (enteros o reales) se consideran casi universalmente como datos básicos tanto para las máquinas físicas abstractas como para las máquinas abstractas utilizadas por muchos lenguajes de programación . La máquina realiza inmediatamente las diferentes operaciones aritméticas necesarias (suma, multiplicación, etc.).

Operaciones y estructuras de datos para el control de secuencias

Las operaciones y estructuras para el "control de secuencia" permiten controlar el flujo de ejecución de las instrucciones del programa. Cuando se cumplen ciertas condiciones , es necesario cambiar la ejecución secuencial típica de un programa. Por lo tanto, el intérprete emplea estructuras de datos (como las que se utilizan para almacenar la dirección de la siguiente instrucción a ejecutar) que son modificadas por operaciones distintas de las utilizadas para la manipulación de datos (por ejemplo, operaciones para actualizar la dirección de la siguiente instrucción a ejecutar). ).

Operaciones y estructuras de datos para controlar las transferencias de datos

Las operaciones de transferencia de datos se utilizan para controlar cómo se transportan los operandos y los datos desde la memoria al intérprete y viceversa. Estas operaciones se ocupan de la tienda y el orden de recuperación de los operandos de la tienda.

Operaciones y estructuras de datos para la gestión de memoria.

La gestión de la memoria se ocupa de las operaciones realizadas en la memoria para asignar datos y aplicaciones. En la máquina abstracta, los datos y los programas pueden almacenarse indefinidamente o, en el caso de los lenguajes de programación, la memoria puede asignarse o desasignarse mediante un mecanismo más complejo.

Jerarquías de Máquinas Abstractas

Una jerarquía de máquinas abstractas

A menudo se emplean jerarquías de máquinas abstractas, en las que cada máquina usa la funcionalidad del nivel inmediatamente inferior y agrega funcionalidad adicional propia para cumplir con el nivel inmediatamente superior. Se puede agregar una computadora de hardware , construida con dispositivos electrónicos físicos, en el nivel más básico. Por encima de este nivel, puede introducirse el nivel abstracto de máquina microprogramada . La máquina abstracta suministrada por el sistema operativo , que se implementa mediante un programa escrito en lenguaje de máquina , se encuentra inmediatamente encima (o directamente encima del hardware si el nivel de firmware no está allí). Por un lado, el sistema operativo amplía la capacidad de la máquina física proporcionando primitivas de nivel superior que no están disponibles en la máquina física (por ejemplo, primitivas que actúan sobre archivos). La máquina host está formada por la máquina abstracta dada por el sistema operativo, sobre la cual se implementa un lenguaje de programación de alto nivel utilizando una máquina intermediaria , como es la Máquina Virtual Java y su lenguaje bytecode. El nivel dado por la máquina abstracta para el lenguaje de alto nivel (por ejemplo, Java) no suele ser el nivel final de la jerarquía. En este punto, se pueden introducir una o más aplicaciones que entreguen servicios adicionales juntos. Se puede agregar un nivel de "máquina web", por ejemplo, para implementar las funcionalidades necesarias para manejar las comunicaciones web ( protocolos de comunicaciones o presentación de código HTML ). Por encima de este se ubica el nivel " Web Service ", que proporciona las funcionalidades necesarias para que los servicios web se comuniquen, tanto en términos de protocolos de interacción como de comportamiento de los procesos involucrados. En este nivel, se pueden desarrollar lenguajes completamente nuevos que especifican el comportamiento de los llamados "procesos comerciales" basados ​​en servicios web (un ejemplo es el lenguaje de ejecución de procesos comerciales ). Finalmente, se puede encontrar una aplicación especializada al más alto nivel (por ejemplo, E-commerce ) que tiene una funcionalidad muy específica y limitada.

Ver también

Referencias

  1. ^ Weisstein, Eric W. "Máquina abstracta" . mundomatemático.wolfram.com . Consultado el 16 de mayo de 2022 .
  2. ^ a b c d e f "¿Qué es una máquina abstracta?" . EasyTechJunkie . Consultado el 16 de mayo de 2022 .
  3. ^ a b c d e f g h i j Diehl, Stephan; Hartel, Pieter; Sestoft, Peter (mayo de 2000). "Máquinas abstractas para la implementación de lenguajes de programación" . Sistemas Informáticos de Futura Generación . 16 (7): 739–751. doi : 10.1016/S0167-739X(99)00088-6 .
  4. ^ "9.1.1: Descripción general de la máquina de estado finito" . Ingeniería de Textos Libres . 2021-04-29 . Consultado el 31 de mayo de 2022 .
  5. ^ "¿Qué es el sistema determinista? - Definición de Techopedia" . Techopedia.com . Consultado el 30 de mayo de 2022 .
  6. ^ Stearns, Richard E. (enero de 2003). "Tiempo determinista versus no determinista y problemas de límite inferior" . Revista de la ACM . 50 (1): 91–95. doi : 10.1145/602382.602409 . ISSN  0004-5411 . S2CID  2194820 .
  7. ^ Armoni, Michal; Gal-Ezer, Judith (diciembre de 2007). "No determinismo: un concepto abstracto en los estudios de informática" . Educación en Ciencias de la Computación . 17 (4): 243–262. Código Bib : 2007CSEd...17..243A . doi : 10.1080/08993400701442885 . ISSN  0899-3408 . S2CID  41928460 .
  8. ^ Gill, John (diciembre de 1977). "Complejidad Computacional de Máquinas de Turing Probabilísticas" . Revista SIAM de Computación . 6 (4): 675–695. doi : 10.1137/0206049 . ISSN  0097-5397 .
  9. ^ a b c d e f g h i j k l m n o Gabbrielli, Maurizio; Martini, Simone (2010), "Máquinas abstractas" , Lenguajes de programación: principios y paradigmas , Londres: Springer London, págs. 1–25, doi : 10.1007/978-1-84882-914-5_1 , ISBN 978-1-84882-913-8, consultado el 16 de mayo de 2022
  10. ^ Bair, rayo; Chien, Andrew; Cocine, Jeanine; Donofrio, Dave; Grider, Gary; Kuehn, Jeff; Moore, Shirley; Shalf, Juan; Vetter, Jeff (2018-02-01). "Evaluación de hardware: modelos abstractos de máquinas y arquitecturas de proxy para computación a exaescala" . doi : 10.2172/1733300 . OSTI  1733300 . {{cite journal}}:Citar diario requiere |journal=( ayuda )
  11. ^ "máquina abstracta de FOLDOC" . foldoc.org . Consultado el 07-08-2021 .
  12. ^ Vaya, J.; Melvin, SO; Patt, YN (1986). "La implementación de Prolog a través del microcódigo VAX 8600" . Actas del 19 º Taller Anual sobre Microprogramación - MICRO 19 . Nueva York, Nueva York, EE. UU.: ACM Press: 68–74. doi : 10.1145/19551.19538 . ISBN 081860736X. S2CID  3846072 .
  13. ^ "máquina abstracta" . Referencia de Oxford . Consultado el 16 de mayo de 2022 .
  14. García-Martín, Julio Manuel; Sutil-Martin, Miguel (15-08-1999). "Un patrón para diseñar máquinas abstractas" . doi : 10.13140/RG.2.1.3680.5203 . {{cite journal}}:Citar diario requiere |journal=( ayuda )
  15. ^ upscfever.com (2017-01-25). "Organización y Arquitectura de Computadores (Organización Stack) - UPSC FEVER" . upscfever.com . Consultado el 31 de mayo de 2022 .
  16. ^ a b Tyson, Mateo (2020-01-17). "¿Qué es la JVM? Introducción a la máquina virtual de Java" . InfoMundo . Consultado el 31 de mayo de 2022 .
  17. ^ "¿Qué es la programación orientada a objetos (POO)?" . Arquitectura de aplicaciones de búsqueda . Consultado el 31 de mayo de 2022 .
  18. ^ "Consideraciones de diseño para lenguajes de procesamiento de cadenas" , Un estudio en lenguajes de procesamiento de cadenas , Apuntes de conferencias en informática, Berlín, Heidelberg: Springer Berlin Heidelberg, vol. 205, págs. 17–37, 1985, doi : 10.1007/3-540-16041-8_2 , ISBN 978-3-540-16041-0, consultado el 31 de mayo de 2022
  19. ^ Hackett, Jennifer; Hutton, Graham (2019-07-26). "La llamada por necesidad es una llamada clarividente por valor" . Actas de la ACM sobre lenguajes de programación . 3 (ICFP): 1–23. doi : 10.1145/3341718 . ISSN  2475-1421 . S2CID  195782686 .
  20. ^ "Prólogo | Una introducción" . Geeks para Geeks . 2018-05-26 . Consultado el 31 de mayo de 2022 .
  21. ^ Accattoli, Beniamino; Barembaum, Pablo; Mazza, Damián (2014-11-26). "Máquinas abstractas de destilación" . Avisos ACM SIGPLAN . 49 (9): 363–376. doi : 10.1145/2692915.2628154 . ISSN  0362-1340 . S2CID  234775413 .
  22. ^ baeldung (2018-01-11). "Introducción a las primitivas de Java | Baeldung" . www.baeldung.com . Consultado el 31 de mayo de 2022 .
  23. ^ "Intérprete" , Patrones de diseño de arquitectura de software en Java , Publicaciones de Auerbach, 27 de abril de 2004, doi : 10.1201/9780203496213.ch34 , ISBN 978-0-8493-2142-9, consultado el 31 de mayo de 2022
  24. ^ "Hardware, software y firmware: ¿cuál es la diferencia?" . Alambre de vida . Consultado el 31 de mayo de 2022 .
  25. ^ Accattoli, Beniamino; Barras, Bruno (2017-10-09). "Ambientes y la complejidad de las máquinas abstractas" . Actas del 19º Simposio Internacional sobre Principios y Prácticas de la Programación Declarativa . Namur Bélgica: ACM: 4–16. doi : 10.1145/3131851.3131855 . ISBN 978-1-4503-5291-8. S2CID  11953081 .
  26. ^ "Servicios web" . referencia.wolfram.com . Consultado el 31 de mayo de 2022 .
  27. ^ DB Skillicorn (2005). Fundamentos de la Programación Paralela . Prensa de la Universidad de Cambridge. pags. 18. ISBN 978-0-521-01856-2.

Otras lecturas

  • Peter van Emde Boas, Machine Models and Simulations , págs. 3–66, que aparece en:
Jan van Leeuwen , ed. "Manual de informática teórica. Volumen A: Algoritmos y complejidad , The MIT PRESS/Elsevier, 1990. ISBN  0-444-88071-2 (volumen A). QA 76.H279 1990