La máquina SECD es una máquina virtual y una máquina abstracta muy influyente ( ver: § Contribución de Landin ) destinada a ser un objetivo para los compiladores de lenguajes de programación funcionales . Las letras significan S tack, E nvironment, C ontrol , D ump: los registros internos de la máquina. Los registros Stack, Control y Dump apuntan a (algunas realizaciones de) pilas , y Environment apunta a (alguna realización de) una matriz asociativa .
La máquina fue la primera en ser diseñada específicamente para evaluar expresiones de cálculo lambda . Fue descrita originalmente por Peter J. Landin en "The Mechanical Evaluation of Expressions" [1] en 1964. La descripción publicada por Landin era bastante abstracta y dejaba abiertas muchas opciones de implementación (como una semántica operativa ). Por lo tanto la máquina SECD se presenta a menudo en una forma más detallada, como Peter Henderson 's Lispkit Lisp compilador, que se ha distribuido desde 1980. Desde entonces se ha utilizado como el objetivo para varios otros compiladores experimentales.
En 1989, investigadores de la Universidad de Calgary trabajaron en una implementación de hardware de la máquina. [2]
La contribución de Landin
DA Turner (2012) [3] señala que The Revised Report on Algol 60 ( Naur 1963) especifica una llamada a procedimiento mediante una regla de copia que evita la captura de variables con un cambio sistemático de identificadores. Este método funciona en la implementación de Algol 60, pero en un lenguaje de programación funcional donde las funciones son ciudadanos de primera clase, una variable libre en una pila de llamadas podría desreferenciarse por error.
Turner señala que Landin resolvió esto con su máquina SECD, en la que una función está representada por un cierre en el montón. [3]
Descripción informal
Cuando comienza la evaluación de una expresión, la expresión se carga como el único elemento de control C
. El entorno E
, la pila S
y el volcado D
comienzan vacíos.
Durante la evaluación C
, se convierte a notación polaca inversa (RPN), siendo ap
(para aplicar ) el único operador. Por ejemplo, la expresión F (G X)
(un solo elemento de lista) se cambia a la lista X:G:ap:F:ap
.
La evaluación de los C
productos procede de forma similar a otras expresiones RPN. Si el primer elemento de la lista C
es un valor, se coloca en la pila S
. Más exactamente, si el elemento es un identificador, el valor empujado a la pila será el enlace para ese identificador en el entorno actual E
. Si el elemento es una abstracción, se construye un cierre para preservar los enlaces de sus variables libres (que están adentro E
), y es este cierre el que se empuja a la pila.
Si el elemento es ap
, se extraen dos valores de la pila y la aplicación se realiza (primero se aplica al segundo). Si el resultado de la aplicación es un valor, se inserta en la pila.
Sin embargo, si la aplicación es una abstracción de un valor, dará como resultado una expresión de cálculo lambda que puede ser en sí misma una aplicación (en lugar de un valor) y, por lo tanto, no se puede insertar en la pila. En este caso, el contenido actual de S
, E
y C
se empuja al volcado D
(que es una pila de estos triples), S
se reinicializa a vacío y C
se reinicia en el resultado de la aplicación con E
el entorno para las variables libres de esta expresión, aumentado con el enlace que resultó de la aplicación. Luego, la evaluación procede como se indicó anteriormente.
La evaluación completa se indica en C
blanco, en cuyo caso el resultado estará en la pila S
. A D
continuación, se muestra el último estado de evaluación guardado en , y el resultado de la evaluación completa se envía al contenido de la pila restaurado D
. La evaluación del estado restaurado continúa como se indicó anteriormente.
Si C
y D
están vacíos, la evaluación general se ha completado con el resultado en la pila S
.
Registros y memoria
La máquina SECD está basada en pilas . Las funciones toman sus argumentos de la pila. Los argumentos de las instrucciones incorporadas se codifican inmediatamente después de ellos en el flujo de instrucciones.
Como todas las estructuras de datos internas, la pila es una lista, con el S
registro que apunta a la lista de la cabeza o de comenzar. Debido a la estructura de la lista, no es necesario que la pila sea un bloque continuo de memoria, por lo que el espacio de la pila está disponible siempre que haya una sola celda de memoria libre. Incluso cuando se han utilizado todas las celdas, la recolección de elementos no utilizados puede generar memoria libre adicional. Obviamente, implementaciones específicas de la estructura SECD pueden implementar la pila como una estructura de pila canónica, mejorando así la eficiencia general de la máquina virtual, siempre que se establezca un límite estricto en la dimensión de la pila.
El C
registro apunta al principio del código o lista de instrucciones que se evaluará. Una vez que se ha ejecutado la instrucción, C
se apunta a la siguiente instrucción en la lista; es similar a un puntero de instrucción (o contador de programa ) en máquinas convencionales, excepto que las instrucciones subsiguientes siempre se especifican durante la ejecución y no están contenidas por defecto. en ubicaciones de memoria posteriores, como es el caso de las máquinas convencionales.
El entorno de la variable actual lo gestiona el E
registro, que apunta a una lista de listas. Cada lista individual representa un nivel de entorno: los parámetros de la función actual están en el encabezado de la lista, las variables que están libres en la función actual, pero limitadas por una función circundante, están en otros elementos de E
.
El volcado, en cuya cabecera D
apunta el registro, se utiliza como almacenamiento temporal para los valores de los otros registros, por ejemplo, durante las llamadas a funciones. Puede compararse con la pila de devolución de otras máquinas.
La organización de la memoria de la máquina SECD es similar al modelo utilizado por la mayoría de los intérpretes de lenguaje funcional : varias celdas de memoria, cada una de las cuales puede contener un átomo (un valor simple, por ejemplo 13 ), o representar un vacío o no lista vacía. En el último caso, la celda contiene dos punteros a otras celdas, una que representa el primer elemento y la otra que representa la lista, excepto el primer elemento. Los dos indicadores se denominan tradicionalmente coche y cdr, respectivamente, pero a menudo se utilizan los términos más modernos cabeza y cola . Los diferentes tipos de valores que puede contener una celda se distinguen por una etiqueta . A menudo, también se distinguen diferentes tipos de átomos (números enteros, cadenas, etc.).
Entonces, una lista que contenga los números 1 , 2 y 3 , generalmente escritos como (1 2 3)
, podría representarse de la siguiente manera:
Contenido de la etiqueta de dirección (valor para números enteros, coche y cdr para listas) 9 [entero | 2] 8 [entero | 3] 7 [lista | 8 | 0] 6 [lista | 9 | 7] ... 2 [lista | 1 | 6] 1 [entero | 1] 0 [nulo]
Las celdas de memoria 3 a 5 no pertenecen a nuestra lista, cuyas celdas se pueden distribuir aleatoriamente en la memoria. La celda 2 es el encabezado de la lista, apunta a la celda 1, que contiene el valor del primer elemento, y la lista que contiene solo 2 y 3 (comenzando en la celda 6). La celda 6 apunta a una celda que contiene 2 y a la celda 7, que representa la lista que contiene solo 3 . Lo hace apuntando a la celda 8 que contiene el valor 3 , y apuntando a una lista vacía ( nula ) como cdr. En la máquina SECD, la celda 0 siempre representa implícitamente la lista vacía, por lo que no se necesita un valor de etiqueta especial para señalar una lista vacía (todo lo que necesita eso puede simplemente apuntar a la celda 0).
El principio de que el cdr en una celda de lista debe apuntar a otra lista es solo una convención. Si tanto car como cdr apuntan a átomos, se producirá un par, generalmente escrito como(1 . 2)
Instrucciones
nil
empuja un puntero cero en la pilaldc
empuja un argumento constante a la pilald
empuja el valor de una variable a la pila. La variable está indicada por el argumento, un par. El coche de la pareja especifica el nivel, el cdr la posición. Entonces(1 . 3)
da el tercer parámetro de la función actual (nivel 1).sel
espera dos argumentos de lista y saca un valor de la pila. La primera lista se ejecuta si el valor emergente no era nulo, la segunda lista en caso contrario. Antes de que uno de estos punteros de lista se convierta en el nuevoC
, un puntero a la instrucción siguiente se guarda en el vertedero.join
saca una referencia de lista del volcado y lo convierte en el nuevo valor deC
. Esta instrucción ocurre al final de ambas alternativas de asel
.ldf
toma un argumento de lista que representa una función. Construye un cierre (un par que contiene la función y el entorno actual) y lo coloca en la pila.ap
muestra un cierre y una lista de valores de parámetros de la pila. El cierre se aplica a los parámetros instalando su entorno como el actual, empujando la lista de parámetros delante de eso, limpiando la pila y estableciendoC
el puntero de función del cierre. Los valores anteriores deS
,E
y el siguiente valor deC
se guardan en el volcado.ret
saca un valor de retorno de la pila, restauraS
,E
yC
del volcado, y empuja el valor de retorno a la pila actual.dum
empuja un "ficticio", una lista vacía, delante de la lista del entorno.rap
funciona como , solo que reemplaza una ocurrencia de un entorno ficticio con el actual, lo que hace posibles funciones recursivas
Existen varias instrucciones adicionales para funciones básicas como coche, cdr, construcción de listas, suma de enteros, E / S, etc. Todos toman los parámetros necesarios de la pila.
Ver también
Referencias
- ^ Landin, PJ (enero de 1964). "La Evaluación Mecánica de Expresiones" . Computación. J. 6 (4): 308–320. doi : 10.1093 / comjnl / 6.4.308 .
- ^ Seencuentra disponibleun documento sobre el diseño, SECD: DESIGN ISSUES .
- ^ a b D. A. Turner "Un poco de historia de los lenguajes de programación funcionales" en una conferencia invitada TFP12 , Universidad de St Andrews, 12 de junio de 2012. Consulte la sección sobre Algol 60
Otras lecturas
- Danvy, Olivier . Una deconstrucción racional de la máquina SECD de Landin . Informe de investigación BRICS RS-04-30, 2004. ISSN 0909-0878
- Field, Anthony J. Field y Peter G. Harrison. 1988 Programación funcional . Addison-Wesley. ISBN 0-201-19249-7
- Graham, Brian T. 1992 "El microprocesador SECD: un estudio de caso de verificación". Saltador. ISBN 0-7923-9245-0
- Henderson, Peter. 1980 Programación funcional: aplicación e implementación . Prentice Hall. ISBN 0-13-331579-7
- Kogge, Peter M. La arquitectura de las computadoras simbólicas . ISBN 0-07-035596-7
- Landin, PJ (marzo de 1966). "Los próximos 700 lenguajes de programación" (PDF) . Comm. ACM . 9 (3): 157-166. doi : 10.1145 / 365230.365257 .
enlaces externos
- Colección SECD