La máquina SECD es una máquina virtual y abstracta muy influyente ( ver: § Contribución de Landin ) pensada como objetivo para los compiladores de lenguajes de programación funcional . Las letras representan Stack , Environment , Control, Dump (pila, entorno , control y volcado ), 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 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 operacional ).
Lispkit Lisp fue un compilador influyente basado en la máquina SECD, [2] y la máquina SECD se ha utilizado como objetivo para otros sistemas como Lisp/370. [3] En 1989, investigadores de la Universidad de Calgary trabajaron en una implementación de hardware de la máquina. [4]
DA Turner (2012) [5] señala que el lenguaje de programación ALGOL 60 no podía devolver funciones de otras funciones (lo que hacía que las funciones ya no fueran de primera clase). Una función anidada dentro de otra función podría hacer referencia a una variable que se encuentra en la pila de la función externa. Si la función anidada se devolviera desde la función externa, entonces estaría haciendo referencia a una variable en un marco de pila que ya no está presente. Turner señala que la máquina SECD de Landin resuelve este problema (permitiendo así que las funciones devuelvan funciones), ya que el valor de una función ahora se representa con un cierre en el montón que puede almacenar el entorno de las variables que debería utilizar independientemente de lo que suceda en la pila. [5]
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 Sy el volcado Dcomienzan vacíos.
Durante la evaluación, Cse convierte a notación polaca inversa (RPN) con ap(para aplicar ) como único operador. Por ejemplo, la expresión F (G X)(un único elemento de lista) se cambia a lista X:G:ap:F:ap.
La evaluación de Cprocede de manera similar a otras expresiones RPN. Si el primer elemento en Ces un valor, se coloca en la pila S. Más exactamente, si el elemento es un identificador, el valor colocado en 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 en E), y es este cierre el que se coloca en la pila.
Si el elemento es ap, se extraen dos valores de la pila y se realiza la aplicación (el primero se aplica al segundo). Si el resultado de la aplicación es un valor, se coloca en la pila.
Sin embargo, si la aplicación es de una abstracción a 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 colocar en la pila. En este caso, el contenido actual de S, E, y Cse coloca en el volcado D(que es una pila de estos triples), Sse reinicializa a vacío y Cse reinicializa al resultado de la aplicación con que Econtiene el entorno para las variables libres de esta expresión, aumentada con el enlace que resultó de la aplicación. Luego, la evaluación continúa como se indicó anteriormente.
La evaluación completada se indica al Cestar vacía, en cuyo caso el resultado estará en la pila . Luego se extrae Sel último estado de evaluación guardado en y el resultado de la evaluación completada se coloca en la pila cuyo contenido se restauró desde . Luego, la evaluación del estado restaurado continúa como se indicó anteriormente.DD
Si Cy Destán ambos vacíos, la evaluación general se ha completado con el resultado en la pila S.
La máquina SECD está basada en pila . Las funciones toman sus argumentos de la pila. Los argumentos de las instrucciones integradas se codifican inmediatamente después de ellas en el flujo de instrucciones.
Al igual que todas las estructuras de datos internas, la pila es una lista, con el Sregistro apuntando al comienzo o al principio de la lista. Debido a la estructura de lista, la pila no necesita ser 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 hayan utilizado todas las celdas, la recolección de basura puede generar memoria libre adicional. Obviamente, las 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 Cregistro apunta al principio del código o la lista de instrucciones que se evaluará. Una vez que se ha ejecutado la instrucción, el Capunta a la siguiente instrucción de la lista; es similar a un puntero de instrucción (o contador de programa ) en las máquinas convencionales, excepto que las instrucciones posteriores siempre se especifican durante la ejecución y no están contenidas por defecto en las ubicaciones de memoria posteriores, como es el caso de las máquinas convencionales.
La variable actual environment es administrada por el Eregistro, 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 la cabecera 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 dump, a cuya cabecera Dapunta el registro, se utiliza como almacenamiento temporal de los valores de los demás registros, por ejemplo durante las llamadas a funciones. Se puede comparar con la pila de retorno 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 lenguajes funcionales : un número de celdas de memoria, cada una de las cuales puede contener un átomo (un valor simple, por ejemplo 13 ), o representar una lista vacía o no vacía. En el último caso, la celda contiene dos punteros a otras celdas, uno que representa el primer elemento, el otro que representa la lista excepto el primer elemento. Los dos punteros se denominan tradicionalmente car y cdr respectivamente, pero a menudo se utilizan en su lugar los términos más modernos head y tail . 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 (enteros, cadenas, etc.).
Entonces, una lista que contiene los números 1 , 2 y 3 , usualmente escrita como (1 2 3), podría representarse de la siguiente manera:
Contenido de la etiqueta de dirección (valor para números enteros, car 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 [ cero ]
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 la cabeza de la lista, apunta a la celda 1, que contiene el valor del primer elemento, y a 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 ( nil ) 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 lo necesite 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, eso producirá un par, que generalmente se escribe como(1 . 2)
nilEmpuja un puntero nulo a la pilaldcinserta un argumento constante en la pilaldColoca el valor de una variable en la pila. La variable se indica mediante el argumento, un par. El car del par especifica el nivel, el cdr la posición. Por lo tanto, (1 . 3)proporciona el tercer parámetro de la función actual (nivel 1).selespera dos argumentos de lista y extrae un valor de la pila. La primera lista se ejecuta si el valor extraído no es nulo, la segunda lista en caso contrario. Antes de que uno de estos punteros de lista se convierta en new , se guarda en el volcado Cun puntero a la siguiente instrucción .
joinextrae una referencia de lista del volcado y convierte este en el nuevo valor de C. Esta instrucción se produce al final de ambas alternativas de un sel.ldfToma 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.apextrae 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, colocando la lista de parámetros delante de este, limpiando la pila y estableciendo Cel puntero de función del cierre. Los valores anteriores de S, Ey el siguiente valor de Cse guardan en el volcado.retextrae un valor de retorno de la pila, restaura S, Ey Cdel volcado, y empuja el valor de retorno a la pila actual.dumcoloca un "ficticio", una lista vacía, delante de la lista de entorno.rapFunciona como , solo que reemplaza una ocurrencia de un entorno ficticio con el actual, lo que hace posibles las funciones recursivas.Existe una serie de instrucciones adicionales para funciones básicas como car, cdr, construcción de listas, suma de números enteros, E/S, etc. Todas ellas toman los parámetros necesarios de la pila.
{{cite journal}}: Requiere citar revista |journal=( ayuda )