¿Cómo se implementa el Alcance léxico?

Question

Hace un par de años comencé a escribir un intérprete para un pequeño lenguaje específico de dominio que incluía funciones definidas por el programador.

Al principio implementé el ámbito variable usando una simple pila de tablas de símbolos. Pero ahora quiero pasar al alcance léxico apropiado (con la opción de cierres). ¿Alguien puede explicarme o señalarme una buena explicación de la estructura de datos y el algoritmo detrás del alcance léxico?

Answer 1

No hay una sola forma correcta de hacerlo. Lo importante es establecer claramente la semántica que está buscando proporcionar, y luego las estructuras de datos y los algoritmos seguirán.

Answer 2

Para llegar alcance y cierres léxica correcta en un intérprete, todo lo que tiene que hacer es seguir estas reglas:

• En su intérprete, las variables siempre se buscan en una tabla de entorno aprobada en la persona que llama/mantenido como una variable, no alguna pila env global. Es decir, eval(expression, env) => value.
• Cuando el código interpretado llama a una función, el entorno es NOT pasado a esa función. apply(function, arguments) => value.
• Cuando se invoca una función interpretada, el entorno en el que se evalúa su cuerpo es el entorno en el que se realizó la definición de la función y no tiene nada que ver con la persona que llama. Entonces, si tiene una función local, entonces es un cierre, es decir, una estructura de datos que contiene los campos {function definition, env-at-definition-time}.

Para ampliar ese último bit en Python-ish sintaxis:

x = 1 
return lambda y: x + y 

es ejecutado como si fuera

x = 1 
return makeClosure(<AST for "lambda y: x + y">, {"x": x}) 

en el que el segundo argumento dict puede ser justo la corriente de env en lugar de una estructura de datos construida en ese momento. (Por otro lado, conservar todo el env en lugar de solo las variables cerradas puede causar fugas de memoria.)

Answer 3

Lea The implementation of Lua 5.0 por ejemplo.

Answer 4

Hay muchas formas diferentes de implementar el alcance léxico. Éstos son algunos de mis favoritos:

• Si usted no necesita el rendimiento súper rápido, utilizar una estructura de datos puramente funcional para implementar sus tablas de símbolos, y representa a una función anidada por un par que contiene un puntero a la código y un puntero a la tabla de símbolos.

• Si necesita velocidades de código nativo, mi técnica favorita se describe en Making a Fast Curry por Simon Marlow y Simon Peyton Jones.

• Si necesita velocidades de código nativo, pero las funciones al curry no son tan importantes, considere closure-passing style.

Answer 5

BS implementado esto en el primer compilador de C++ simplemente con una tabla de símbolos por alcance, y una regla de encadenamiento que siguió alcances hacia el exterior hasta que se encuentre una definición.Cómo funciona esto depende exactamente de su semántica precisa. Asegúrate de clavarlos primero.

Knuth en El arte de la programación de computadoras, Vol. 1, proporciona un algoritmo para una tabla de símbolos de Cobol según la cual el alcance se realiza a través de enlaces.