Máquina abstracta

En ciencias de la computación , 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 el sentido de 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 ( 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. Pueden usarse 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 sobre 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 con las máquinas de estados finitos , las máquinas de Mealy , los autómatas de pila y las máquinas de Turing . ^{[ 4 ]}

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 las mismas salidas. No hay aleatoriedad ni variación en cómo las entradas se transforman en salidas. ^{[ 5 ]} Por el contrario, una máquina abstracta no determinista puede proporcionar varias salidas 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 salidas. ^{[ 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 ]}

Las máquinas de Turing , por ejemplo, son algunas de las máquinas abstractas más fundamentales en la informática. ^{[ 2 ]} Estas máquinas realizan operaciones sobre una cinta (una cadena de símbolos) de cualquier longitud. Sus instrucciones permiten tanto modificar los símbolos como 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 una sola instrucción: "convertir el símbolo en 1 y luego moverse a la derecha", y esta máquina solo produciría una cadena de 1s. ^{[ 8 ]} 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. ^{[ 2 ]}

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 en hardware : La implementación directa de una máquina abstracta en hardware consiste en utilizar dispositivos físicos como memoria , circuitos aritméticos y lógicos , buses, etc., para implementar una máquina física cuyo lenguaje de máquina coincide con el lenguaje de programación . Una vez construida, sería prácticamente imposible modificar dicha máquina. ^{[ 9 ]} Una CPU puede considerarse como una realización concreta en hardware de una máquina abstracta, en particular el diseño del procesador . ^{[ 10 ]}
• Simulación mediante software : Implementar una máquina abstracta con software implica escribir programas en un lenguaje diferente para implementar las estructuras de datos y los algoritmos que necesita la máquina abstracta. Esto proporciona la mayor flexibilidad, ya que los programas que implementan las construcciones de la máquina abstracta se pueden modificar fácilmente. ^{[ 9 ]} Una máquina abstracta implementada como una simulación de software, o para la cual existe un intérprete , se denomina máquina virtual . ^{[ 11 ]}
• Emulación mediante firmware : La implementación del firmware se sitúa entre la implementación del hardware y la del software. Consiste en simulaciones de microcódigo de estructuras de datos y algoritmos para máquinas abstractas. ^{[ 9 ]} El microcódigo permite a un programador escribir instrucciones de máquina sin necesidad de fabricar circuitos eléctricos . ^{[ 12 ]}

Una máquina abstracta es, intuitivamente, solo una abstracción de la idea de una computadora física. ^{[ 13 ]} Para su ejecución real, los algoritmos deben formalizarse adecuadamente utilizando las construcciones que ofrece un lenguaje de programación . Esto implica que los algoritmos que se van 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 direcciones que puede contar solo enteros positivos (después de que se carga un valor inicial en él). El registro de direcciones para la pila se conoce como puntero de pila porque su valor siempre se refiere al elemento superior de la pila. ^{[ 15 ]} El programa consiste en una serie de instrucciones, con un puntero de pila que indica la siguiente instrucción que se va a ejecutar. 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 ]} Así, 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 dicho lenguaje. Establece un puente 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 específicas necesarias para implementar las operaciones de un determinado lenguaje fuente o conjunto de lenguajes fuente. ^{[ 9 ]}

Lenguajes de programación funcionales

Las primeras máquinas abstractas para lenguajes funcionales , incluyendo 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 por valor , ^{[ 3 ]} en la que los argumentos de la función se evalúan antes de la llamada y exactamente una vez. Recientemente, la mayor parte de la investigación se ha centrado en la evaluación perezosa (o por necesidad) , ^{[ 18 ]} como la máquina G (1984), la máquina Krivine (1985) y la Máquina de Tres Instrucciones (1986), en las que los argumentos de la función se evalúan solo si es necesario y como máximo una vez. Una razón es que la implementación efectiva de la evaluación estricta ahora se comprende bien, por lo que la necesidad de una máquina abstracta ha disminuido. ^{[ 3 ]}

Una máquina abstracta genérica se compone de 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 ]}

El intérprete debe realizar las operaciones que son propias del idioma que está interpretando. Sin embargo, dada la variedad de idiomas, 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 el procesamiento de datos primitivos :
2. Operaciones y estructuras de datos para controlar la secuencia de ejecución de las operaciones ;
3. Operaciones y estructuras de datos para el control de transferencias de datos ;
4. Operaciones y estructuras de datos para la gestión de memoria .

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 funcionalidades propias para satisfacer las del nivel inmediatamente superior. En el nivel más básico se puede añadir un ordenador físico , construido con dispositivos electrónicos. Por encima de este nivel, se puede introducir el nivel de máquina microprogramada abstracta. La máquina abstracta proporcionada por el sistema operativo , implementada mediante un programa escrito en lenguaje máquina , se sitúa inmediatamente por encima (o directamente por encima del hardware si no existe el nivel de firmware ). Por un lado, el sistema operativo amplía las capacidades 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 operan sobre archivos). La máquina anfitriona está formada por la máquina abstracta proporcionada por el sistema operativo, sobre la cual se implementa un lenguaje de programación de alto nivel utilizando una máquina intermedia , como la máquina virtual Java y su lenguaje de código de bytes. El nivel proporcionado 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 ofrecen servicios adicionales de forma conjunta. 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 ). El nivel de " servicio web " se sitúa por encima de este y 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 especifican el comportamiento de los denominados "procesos de negocio" basados ​​en servicios web (un ejemplo es el Business Process Execution Language ). Finalmente, en el nivel más alto se puede encontrar una aplicación especializada (por ejemplo, el comercio electrónico ) que posee una funcionalidad muy específica y limitada. ^{[ 9 ]}

• Interpretación abstracta : enfoque para el análisis estático de programas. 
• Paralelismo síncrono masivo : modelo para el diseño de algoritmos paralelos 
• Tiempo discreto : marcos para modelar variables que evolucionan con el tiempo. Páginas que muestran breves descripciones de los destinos de redireccionamiento. 
• Taxonomía de Flynn : Clasificación de arquitecturas informáticas 
• Modelos formales de computación : capacidad para resolver un problema mediante un procedimiento eficaz. 
• Modelo de computación : modelo matemático que describe cómo se calcula la salida de una función a partir de una entrada. 
• Máquina de acceso aleatorio paralela : computadora abstracta para el diseño de algoritmos paralelos. Páginas que muestran breves descripciones de los destinos de redirección , el modelo estándar de facto. 
• Máquina SECD : máquina abstracta utilizada como objetivo para compiladores. 
• Espacio de estados : conjunto de todos los valores posibles de un sistema. Páginas que muestran descripciones breves de los destinos de redirección. 

• Peter van Emde Boas, Modelos y simulaciones de máquinas, págs.  3-66, publicado 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

• Stephan Diehl, Pieter Hartel y Peter Sestoft, Máquinas abstractas para la implementación de lenguajes de programación Archivado el 1 de mayo de 2013 en Wayback Machine , Future Generation Computer Systems, Vol. 16(7), Elsevier, 2000.
• Werner Kluge (2006). Máquinas de computación abstractas: una perspectiva del cálculo lambda . Springer. ISBN 978-3-540-27359-2.