stringtranslate.com

Máquina abstracta

En informática , una máquina abstracta es un modelo teórico que permite un análisis detallado y preciso de cómo funciona un sistema informático. [1] Es similar a una función matemática en que recibe entradas y produce salidas basadas en reglas predefinidas. Las máquinas abstractas se diferencian de las máquinas literales en que se espera que funcionen correctamente e independientemente del hardware . [2] Las máquinas abstractas son " máquinas " porque permiten la ejecución paso a paso de programas ; son " abstractas " porque ignoran muchos aspectos de las máquinas reales ( de hardware ). [3] Una máquina abstracta típica consiste en 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 utilizar por razones puramente teóricas, así como modelos para sistemas informáticos del mundo real. [2] 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 . [3] Este uso de máquinas abstractas es fundamental para el campo de la teoría de la complejidad computacional , como las máquinas de estados finitos , las máquinas Mealy , los autómatas de empuje hacia abajo y las máquinas de Turing . [4]

Clasificación

Las máquinas abstractas se clasifican típicamente en dos tipos según la cantidad de operaciones que pueden ejecutar simultáneamente en un momento dado: máquinas abstractas deterministas y máquinas abstractas no deterministas . [2] 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 cómo se transforman las entradas en resultados. [5] Por el contrario, una máquina abstracta no determinista puede proporcionar varios resultados para la misma entrada en diferentes ejecuciones. [2] 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 resultados. [6] Los algoritmos no deterministas son útiles para obtener respuestas aproximadas cuando derivar una solución precisa utilizando un enfoque determinista es difícil o costoso. [7]

Una ejecución de una máquina de Turing

Las máquinas de Turing , por ejemplo, son algunas de las máquinas abstractas más fundamentales en la ciencia informática. [2] Estas máquinas realizan operaciones en una cinta (una cadena de símbolos) de cualquier longitud. Sus instrucciones permiten modificar los símbolos y cambiar el símbolo en el que se encuentra actualmente el puntero de la máquina. Por ejemplo, una máquina de Turing rudimentaria podría tener un solo comando, "convertir el símbolo en 1 y luego moverse a la derecha", y esta máquina solo produciría una cadena de 1. [8] Esta máquina de Turing básica es determinista; sin embargo, también se pueden construir máquinas de Turing no deterministas que puedan ejecutar varias acciones dada la misma entrada. [2]

Implementación

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

Implementación del lenguaje de programación

Una máquina abstracta es, intuitivamente, sólo una abstracción de la idea de una computadora física. [13] Para la ejecución real, los algoritmos deben formalizarse adecuadamente utilizando las construcciones ofrecidas por un lenguaje de programación . Esto implica que los algoritmos a ejecutar deben expresarse utilizando instrucciones del lenguaje de programación. [3] 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. [9] [14] En las computadoras digitales, la pila es simplemente una unidad de memoria con un registro de dirección que puede contar solo números enteros positivos (después de que se carga un valor inicial en ella). 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. [15] 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 . [3] Por lo tanto, una máquina abstracta para un lenguaje de programación es cualquier conjunto de estructuras de datos y algoritmos capaces de almacenar y ejecutar programas escritos en el lenguaje de programación. Salva la brecha entre el alto nivel de un lenguaje de programación y el bajo nivel de una máquina real al proporcionar 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 las operaciones de un determinado lenguaje fuente o conjunto de lenguajes fuente. [9]

Lenguas imperativas

A finales de los años 1950, la Association for Computing Machinery (ACM) y otras organizaciones aliadas desarrollaron muchas propuestas para el Lenguaje Universal Orientado a Computadoras (UNCOL) , como la máquina de Conway . El concepto UNCOL es bueno, pero no se ha utilizado ampliamente 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 Java a finales de los años 1990. Algol Object Code (1964), P4-machine (1976), UCSD P-machine (1977) y Forth (1970) son algunas máquinas abstractas exitosas de este tipo. [3]

Lenguajes orientados a objetos

Las máquinas abstractas para lenguajes de programación orientados a objetos suelen estar basadas en pilas y tienen instrucciones de acceso especiales para campos y métodos de objetos . En estas máquinas, la gestión de memoria suele estar implícitamente realizada por un recolector de basura (función de recuperación de memoria incorporada en los lenguajes de programación). [16] Smalltalk-80 (1980), Self (1989) y Java (1994) son ejemplos de esta implementación. [3]

Lenguajes de procesamiento de cadenas

Un lenguaje de procesamiento de cadenas es un lenguaje informático que se centra 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 scripts durante décadas. [17] El uso de una máquina abstracta adecuada tiene dos beneficios: mayor velocidad de ejecución y portabilidad mejorada. Snobol4 y ML/I son dos ejemplos notables de lenguajes de procesamiento de cadenas tempranos que utilizan una máquina abstracta para ganar independencia de la máquina. [3]

Lenguajes de programación funcional

Representación gráfica de una máquina de Krivine

Las primeras máquinas abstractas para lenguajes funcionales , entre ellas la máquina SECD (1964) y la máquina abstracta funcional de Cardelli (1983), definieron la evaluación estricta, también conocida como evaluación ansiosa o de llamada por valor , [3] en la que los argumentos de la función se evalúan antes de la llamada y precisamente una vez. Recientemente, la mayoría de las investigaciones se han centrado en la evaluación perezosa (o de llamada por necesidad) , [18] 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 la función se evalúan solo si es necesario y como máximo una vez. Una de las razones es que ahora se entiende bien la implementación efectiva de la evaluación estricta, por lo que la necesidad de una máquina abstracta ha disminuido. [3]

Lenguajes lógicos

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. La máquina abstracta de Warren (WAM) (1983), [3] 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 retroceso (algoritmo de búsqueda). [19]

Estructura

Una máquina abstracta genérica está formada 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. [9]

La estructura de una máquina abstracta

El intérprete debe llevar a cabo las operaciones propias del lenguaje que interpreta. 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: [9] [20]

  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 .

Procesamiento de datos primitivos

Una máquina abstracta debe contener operaciones para manipular tipos de datos primitivos, como cadenas y números enteros. [9] Por ejemplo, los números enteros se consideran casi universalmente un tipo de datos básico tanto para las máquinas abstractas físicas como para las máquinas abstractas que utilizan muchos lenguajes de programación . La máquina realiza las operaciones aritméticas necesarias, como la suma y la multiplicación, en un solo paso de tiempo. [21]

Control de secuencia

Las operaciones y estructuras de “control de secuencia” permiten controlar el flujo de ejecución de las instrucciones de un programa. Cuando se cumplen ciertas condiciones , es necesario cambiar la ejecución secuencial típica de un programa. [9] Por ello, 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 a las utilizadas para la manipulación de datos (por ejemplo, operaciones para actualizar la dirección de la siguiente instrucción a ejecutar). [22]

Control de 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 del almacenamiento y del orden de recuperación de los operandos desde el almacenamiento. [9]

Gestión de la memoria

La gestión de la memoria se ocupa de las operaciones que se realizan 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. [9]

Jerarquías

Una jerarquía de máquinas abstractas

A menudo se emplean jerarquías de máquinas abstractas, en las que cada máquina utiliza la funcionalidad del nivel inmediatamente inferior y añade funcionalidad adicional propia para cumplir con el nivel inmediatamente superior. Se puede añadir un ordenador de hardware , construido con dispositivos electrónicos físicos, en el nivel más básico. Por encima de este nivel, se puede introducir el nivel de máquina abstracta 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 por encima (o directamente por encima del hardware si no está el nivel de firmware ). 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 anfitriona está formada por la máquina abstracta dada por el sistema operativo, en la que se implementa un lenguaje de programación de alto nivel utilizando una máquina intermediaria , como la máquina virtual Java y su lenguaje de código de bytes. 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 prestan servicios adicionales en conjunto. Por ejemplo, se puede añadir un nivel de "máquina web" para implementar las funcionalidades necesarias para gestionar las comunicaciones web ( protocolos de comunicación o presentación de código HTML ). Por encima de éste se encuentra el nivel de " servicio web ", que proporciona las funcionalidades necesarias para que los servicios web se comuniquen, tanto en términos de protocolos de interacción como del comportamiento de los procesos implicados. En este nivel se pueden desarrollar lenguajes completamente nuevos que especifiquen el comportamiento de los denominados "procesos de negocio" basados ​​en servicios web (un ejemplo es el lenguaje de ejecución de procesos de negocio ). Finalmente, en el nivel más alto se puede encontrar una aplicación especializada (por ejemplo, comercio electrónico ) que tiene una funcionalidad muy específica y limitada. [9]

Véase también

Referencias

  1. ^ Weisstein, Eric W. "Abstract Machine". mathworld.wolfram.com . Consultado el 16 de mayo de 2022 .
  2. ^ abcdef "¿Qué es una máquina abstracta?". EasyTechJunkie . Consultado el 16 de mayo de 2022 .
  3. ^ abcdefghij Diehl, Stephan; Hartel, Pieter; Sestoft, Peter (mayo de 2000). "Máquinas abstractas para la implementación de lenguajes de programación". Future Generation Computer Systems . 16 (7): 739–751. doi :10.1016/S0167-739X(99)00088-6.
  4. ^ "9.1.1: Descripción general de la máquina de estados finitos". Ingeniería LibreTexts . 2021-04-29 . Consultado el 2022-05-31 .
  5. ^ "¿Qué es un sistema determinista? - Definición de Techopedia". Techopedia.com . 29 de agosto de 2019 . Consultado el 30 de mayo de 2022 .
  6. ^ Stearns, Richard E. (enero de 2003). "Problemas deterministas versus no deterministas de tiempo y 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. Bibcode :2007CSEd...17..243A. doi :10.1080/08993400701442885. ISSN  0899-3408. S2CID  41928460.
  8. ^ Gill, John (diciembre de 1977). "Complejidad computacional de las máquinas de Turing probabilísticas". Revista SIAM de informática . 6 (4): 675–695. doi :10.1137/0206049. ISSN  0097-5397.
  9. ^ abcdefghijklm 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, Ray; Chien, Andrew; Cook, Jeanine; Donofrio, Dave; Grider, Gary; Kuehn, Jeff; Moore, Shirley; Shalf, John; Vetter, Jeff (1 de febrero de 2018). Evaluación de hardware: modelos de máquinas abstractas y arquitecturas proxy para computación a exaescala (informe técnico). Oficina de Información Científica y Técnica del Departamento de Energía de los Estados Unidos. doi :10.2172/1733300. OSTI  1733300.
  11. ^ "Máquina abstracta de FOLDOC". foldoc.org . Consultado el 7 de agosto de 2021 .
  12. ^ Gee, J.; Melvin, SW; Patt, YN (1986). "La implementación de Prolog a través del microcódigo VAX 8600". Actas del 19.º taller anual sobre microprogramación . Nueva York, Nueva York, EE. UU.: ACM Press. págs. 68–74. doi :10.1145/19551.19538. ISBN . 081860736X. Número de identificación del sujeto  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 de agosto de 1999). "La máquina abstracta: un patrón para diseñar máquinas abstractas" (PDF) . Actas de Pattern Languages ​​of Programs '99 .
  15. ^ upscfever.com (25 de enero de 2017). «Organización y arquitectura de computadoras (organización de pilas) - UPSC FEVER». upscfever.com . Consultado el 31 de mayo de 2022 .
  16. ^ "¿Qué es la programación orientada a objetos (POO)?". SearchAppArchitecture . Consultado el 31 de mayo de 2022 .
  17. ^ "Consideraciones de diseño para lenguajes de procesamiento de cadenas", A Study in String Processing Languages , Lecture Notes in Computer Science, vol. 205, Berlín, Heidelberg: Springer Berlin Heidelberg, 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
  18. ^ Hackett, Jennifer; Hutton, Graham (26 de julio de 2019). "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.
  19. ^ "Prolog | Una introducción". GeeksforGeeks . 2018-05-26 . Consultado el 2022-05-31 .
  20. ^ Accattoli, Beniamino; Barenbaum, Pablo; Mazza, Damiano (26 de noviembre de 2014). "Destilando máquinas abstractas". Avisos SIGPLAN de la ACM . 49 (9): 363–376. doi :10.1145/2692915.2628154. ISSN  0362-1340. S2CID  234775413.
  21. ^ baeldung (11 de enero de 2018). "Introducción a las primitivas de Java | Baeldung". www.baeldung.com . Consultado el 31 de mayo de 2022 .
  22. ^ "Intérprete", Patrones de diseño de arquitectura de software en Java , Auerbach Publications, 27 de abril de 2004, doi : 10.1201/9780203496213.ch34, ISBN 978-0-8493-2142-9, consultado el 31 de mayo de 2022

Lectura adicional

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