Máquina abstracta

En informática, una máquina abstracta es un modelo teórico que permite un análisis detallado y preciso del funcionamiento de un sistema informático. Es similar 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 los programas; son "abstractos" porque ignoran muchos aspectos de las máquinas reales (hardware). 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 es fundamental en el campo de la teoría de la complejidad computacional, como las máquinas de estados finitos, las máquinas 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. Por el contrario, 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.

Las máquinas de Turing, por ejemplo, son algunas de las máquinas abstractas más fundamentales en informática. Estas máquinas realizan operaciones en una cinta (una cadena de símbolos) de cualquier longitud. Sus instrucciones prevén 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 un solo comando, '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

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, la 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.

• Ejecución en hardware: La aplicación directa de la máquina abstracta en hardware es una cuestión de utilizar dispositivos físicos como memoria, circuitos aritméticos y lógicos, autobuses, etc., para implementar una máquina física cuyo lenguaje de la máquina coincide con el lenguaje de programación. Una vez construido, sería prácticamente difícil cambiar tal máquina. Una CPU puede ser considerada como una realización de hardware concreto de una máquina abstracta, especialmente el diseño del procesador.

• Simulación usando software: Implementar una máquina abstracta con software implica la escritura de programas en un lenguaje diferente para implementar las estructuras de datos y algoritmos necesarios por la máquina abstracta. Esto proporciona la mayor flexibilidad ya que los programas que implementan construcciones de máquinas abstractas pueden cambiarse fácilmente. Una máquina abstracta implementada como simulación de software, o para la cual existe un intérprete, se llama máquina virtual.

• Emulación mediante firmware: La implementación de firmware se sitúa entre hardware y aplicación de software. Se compone de simulaciones de microcódigo de estructuras de datos y algoritmos para máquinas abstractas. Microcode permite a un programador de computadora escribir instrucciones de máquina sin necesidad de fabricar circuitos eléctricos.

Implementación del lenguaje de programación

Una máquina abstracta es, intuitivamente, solo 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 ciclo 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.

Idiomas 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 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 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 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 funcionales

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 la función los argumentos 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 lógicos

El cálculo de predicados (lógica de primer orden) es la base de los lenguajes de programación lógicos. 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

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.

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" compartida 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 el procesamiento de 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. Por ejemplo, los números enteros se consideran casi universalmente un tipo de datos básico 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 las operaciones aritméticas necesarias, como la suma y la multiplicación, en un solo paso de tiempo.

Control de secuencia

Operaciones y estructuras para "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).).

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 de la tienda y el orden de recuperación de los operandos de la tienda.

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

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. Una "máquina web" level, por ejemplo, se puede agregar para implementar las funcionalidades necesarias para manejar las comunicaciones Web (protocolos de comunicaciones o presentación de código HTML). El "servicio web" El nivel se ubica 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 de comportamiento de los procesos involucrados. En este nivel, lenguajes completamente nuevos que especifican el comportamiento de los llamados "procesos comerciales" Se pueden desarrollar servicios basados en Web (un ejemplo es el Business Process Execution Language). 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.