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 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 de programas paso a paso ; son " abstractos " porque ignoran muchos aspectos de las máquinas ( hardware ) reales. [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 utilizarse por razones puramente teóricas, así como 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 de Mealy , los autómatas push-down y las máquinas de Turing . [4]
Las máquinas abstractas generalmente se clasifican 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 la forma en que los insumos se transforman en productos. [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 obtener 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 de la informática. [2] Estas máquinas realizan operaciones en una cinta (una cadena de símbolos) de cualquier longitud. Sus instrucciones prevén tanto la modificación de los símbolos como el cambio del 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 moverlo hacia la derecha", y esta máquina solo produciría una cadena de unos. [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 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 se puede implementar en software o firmware en niveles 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 que ofrece un lenguaje de programación . Esto implica que los algoritmos a ejecutar deben expresarse mediante 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 solo puede contar números enteros positivos (después de cargar 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 bucle de ejecución . [3] Por lo tanto, una máquina abstracta para un 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 nivel alto de un lenguaje de programación y el nivel bajo 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 operaciones de un determinado idioma fuente o conjunto de idiomas fuente. [9]
A finales de la década de 1950, la Association for Computing Machinery (ACM) y otras organizaciones aliadas desarrollaron muchas propuestas para el Lenguaje Universal Orientado a Computadora (UNCOL) , como la máquina de Conway . El concepto UNCOL es bueno, pero no se ha utilizado mucho 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 noventa. 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 la memoria suele estar implícita a cargo de un recolector de basura (función de recuperación de memoria integrada 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 secuencias de comandos 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 los primeros lenguajes de procesamiento de cadenas que utilizan una máquina abstracta para obtener independencia de la máquina. [3]
Las primeras máquinas abstractas para lenguajes funcionales , incluida 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. la llamada y precisamente una vez. Recientemente, la mayoría de las investigaciones se han centrado en la evaluación perezosa (o llamada 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 la función Los argumentos se evalúan sólo 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 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' universalmente cuantificadas, lo que significa comenzar el cálculo que intenta descubrir una prueba del objetivo. La Warren Abstract Machine 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 admitir el seguimiento hacia atrás (algoritmo de búsqueda). [19]
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 propias del idioma que interpreta. Sin embargo, dada la variedad de idiomas, es posible 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 lo 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 utilizadas por 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 del programa. Cuando se cumplen ciertas condiciones , es necesario cambiar la ejecución secuencial típica de un programa. [9] Por lo tanto, el intérprete emplea estructuras de datos (como las utilizadas para almacenar la dirección de la siguiente instrucción a ejecutar) que se modifican mediante operaciones distintas de las utilizadas para la manipulación de datos (por ejemplo, operaciones para actualizar la dirección de la siguiente instrucción). 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 tienen que ver con la tienda y el orden de recuperación de los operandos de la tienda. [9]
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 se pueden conservar indefinidamente o, en el caso de los lenguajes de programación, la memoria se puede asignar o desasignar 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 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, se puede introducir el nivel de máquina microprogramada abstracta. La máquina abstracta proporcionada 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 al proporcionar 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 proporcionada por el sistema operativo, sobre la cual se implementa un lenguaje de programación de alto nivel mediante una máquina intermediaria , como es 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 jerarquía. En este punto, se pueden introducir una o más aplicaciones que brinden servicios adicionales juntas. Se puede añadir, por ejemplo, un nivel de "máquina web" para implementar las funcionalidades necesarias para manejar las comunicaciones web ( protocolos de comunicación o presentación de código HTML ). Por encima de este se sitúa el nivel " Servicio Web ", 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 especifiquen el comportamiento de los llamados "procesos de negocio" basados en servicios web (un ejemplo es el Business Process Execution Language ). Por último, se puede encontrar una aplicación especializada al más alto nivel (por ejemplo, Comercio electrónico ) que tiene una funcionalidad muy específica y limitada. [9]
{{cite journal}}: Citar diario requiere |journal=( ayuda ){{cite journal}}: Citar diario requiere |journal=( ayuda )