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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
El intérprete debe realizar 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]
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]
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]
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]
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]
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, sobre 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]