1 Clasificación de los Lenguajes Funcionales
Según el método de evaluación Evaluación estricta (eaguer) Evaluación diferida (lazy, perezosa) Según la asignación Lenguajes funcionales puros o sin asignación Lenguajes funcionales con asignación Máquina abstracta para un lenguaje con evaluación eager (directa) FAM máquina basada en ámbitos Máquina abstracta para un un lenguaje con evaluación lazy (diferida) G-Machine máquina basada en grafos y combinadores.
2 Implementación de la Evaluación Estricta Un lenguaje funcional con evaluación estricta se parece mucho a un lenguaje imperativo por Las operaciones se realizan en el orden que indica el programador La evaluación estricta es compatible con la asignación Idea de implementación Modificar la máquina abstracta para lenguajes imperativos para que pueda ejecutar lenguajes funcionales con evaluación estricta. Problemas a resolver con las modificaciones Implementación óptima de la recursividad en cola. Funciones locales validas fuera de su entorno de definición Clausuras (código función+ámbito) Acceso a ámbitos de funciones inactivas
3 Recursividad en Cola: Importacia Problema de los lenguajes funcionales puros Un lenguaje funcional puro no tiene asignación. Por lo tanto, los cambios de estado solo se pueden realizar creando nuevas variables, o sea, realizando llamadas a funciones. Un programa que interaccione con el mundo real ha de cambiar su estado para representar el nuevo estado del mundo. Si para cada llamada a función se utiliza espacio de pila, el resultado es que el programa llenará la pila. Solución: Optimización de la recursividad en cola La interacción se implementa en un lenguaje imperativo con un bucle que procesa los eventos que vienen del mundo. En un lenguaje funcional se implementa con una función que procesa un evento y que al final se llama recursivamente para procesar en siguiente evento (recursividad en cola). Objetivo: Conseguir que la última llamada que realiza una función no consuma pila.
4 Recursividad en Cola: Problema Última llamada en un lenguaje imperativo void f(a,b) { int c,d,e; … g(c,d) }
b a PC f ED c d e d c Bloque de activación de f Parámetros de g Estado de la pila justo antes de llamar a g ( parametros de g en la pila) PC f d c Pila anterior Pila anterior Contenido de la pila que necesita la llamada a g. El bloque de activación de f se puede eliminar ya que lo último que se hace es llamar a g. Problema: después del bloque de activación de f se encuentran los parámetros de g
5 Recursividad en Cola: Solución Usar dos pilas Pila de contexto con los bloques de activación un pila de parámetros. De esta forma se evita que los parámetros impidan la eliminación del bloque de activación antes de la última llamada Los parámetros se han de copiar de la pila de argumentos al bloque de activación o ámbito de la función Pila de Contexto Pila de Argumentos EP CSP AP
6 Llamada a una Función (Ambito en la Pila) Código Llamada Calcular los argumentos y ponerlos en la pila de argumentos Llamar a la función
Código Función Guardar EP en la pila Copiar argumentos de la pila de argumentos a la pila de contexto Inicializar espacio de variables Cuerpo de la función Poner el valor de retorno en un registro Eliminar de la pila variables y argumentos Recuperar EP retornar
7 Ejemplo de Secuencia de Llamada Fun f(x,y)=>{ Var A; x+y; } Llamada f(10,20) Código llamada PushArg 10 PushArg 20 Call f Código función PushCon EP EP=SP PopArg VR PushCon VR PopArg VR PushCon VR PushCon NIL Cuerpo función SP=EP PopCon EP Ret
8 Aplicación de la Recursividad en Cola Función que realiza una llamada Fun f(x)={… g(10,20); } Código sin optimizar PushArg 10 PushArg 20 Call g SP=EP PopCon EP Ret Eliminar bloque de activación de f antes de llamar PushArg 10 PushArg 20 SP=EP PopCon EP Call g Ret Código optimizado PushArg 10 PushArg 20 SP=EP PopCon EP Jmp g
9 Definiciones Anidadas y Clausuras En los lenguajes funcionales son básicas las siguientes características Definición anidada de funciones Esta implica el uso de display Poder tratar cualquier función como un valor (apuntadores a funciones) Para que una función local a otra pueda referenciarse desde donde queramos hay que asociarle su ámbito de definición. Esta asociación la realizan las clausuras A través de una clausura es posible acceder a un ámbito de una función después de que esta haya acabado su ejecución Funciones lambda o anónimas Son necesarias para facilitar la escritura de llamadas a funciones de orden superior, pero no obligan a modificar la máquina abstracta una vez consideradas las características anteriores Son funciones definidas localmente Son funciones tratadas como un valor
10 Implementación de Clausuras Una clausura es Apuntador a la entrada del código de la función Ambito de la función donde se creo Display o valor de EP cuando se creo la clausura Fun f(x)={ Var y; Fun g(a,b)= { Var z; … } … g } PC EP x y Bloque de activación de f PC EP EP f a b z Bloque de activación de g Display EP EP Entrada g EP def Clausura Clausura de g
11 Ambitos en el Heap La función f retorna la clausura de g y al llamar a esta clausura se puede acceder a las variables de f. Por lo tanto, no se puede eliminar el ámbito de f al finalizar su ejecución Solución: Guardar el ámbito de f en el heap para que no se elimine al salir de f Los ámbitos en el heap existirán hasta que no se pueda acceder a ellos nulo x y EP PC EP Pila anterior Env SP Contenido de la pila al llamar a f con el ámbito en el heap Nodo con el ámbito de f en el heap
12 Llamada a una Función con el ámbito en el Heap Código Llamada Calcular los argumentos y ponerlos en la pila de argumentos Llamar a la función Código Función Guardar EP en la pila Crear nodo de ámbito en el heap e inicializarlo EP apunta al nodo de ámbito Copiar argumentos de la pila de argumentos al ámbito Cuerpo de la función Poner el valor de retorno en un registro Recuperar EP de la pila de contexto retornar
13 Ámbito en la Pila y en el Heap PC EP Display Argumentos Variables EP Env nulo Display Argumentos Variables EP PC EP Pila de contexto Heap Ambito en el Heap Ambito en la pila Pila de contexto CSP CSP
14 Llamada a una Clausura Código Llamada Calcular los argumentos y ponerlos en la pila de argumentos Clo=Clausura Llamar a la función Código Función Guardar EP en la pila de contexto Crear el Display a partir del EP de Clo Copiar argumentos de la pila de argumentos a la pila de contexto Inicializar espacio de variables en la pila de contexto Cuerpo de la función Poner el valor de retorno en un registro Recuperar EP de la pila de contexto retornar
15 Implementación de un Interprete de LISP Basado en Precompilación Organización de la memoria EP: apuntador al ámbito activo CSP: apuntador a la cabeza de la pila de contexto ASP: apuntador a la cabeza de la pila de argumentos PC: contador de programa Heap Pila de Contexto Pila de Argumentos EP CSP AP PC
16 Pila de Contexto y Pila de Argumentos En la pila de contexto se guarda PC de retorno Bloques de ámbito (bloques de activación de las funciones) En la pila de argumentos se guarda Los argumentos de las funciones El valor de retorno Los resultados intermedios de la evaluación de expresiones En el Heap se guarda Nodos de listas, símbolos, paquetes, etc. Código de las funciones (puede estar en un segmento de memoria aparte si no puede variar) Clausuras Bloques de ámbito accesibles desde fuera de la función que los ha creado
| Página siguiente |