Descargar

Implementación de lenguajes funcionales

Enviado por Pablo Turmero


    edu.red

    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.

    edu.red

    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

    edu.red

    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.

    edu.red

    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

    edu.red

    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

    edu.red

    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

    edu.red

    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

    edu.red

    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

    edu.red

    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

    edu.red

    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

    edu.red

    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

    edu.red

    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

    edu.red

    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

    edu.red

    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

    edu.red

    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

    edu.red

    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

    edu.red

    17 Llamada a una Función LISP Código de llamada Poner los argumentos en la pila de argumentos Nargs=Número de argumentos Call funcion Código de la función Verificar del número de argumentos (NArgs) Guardar EP en la pila de contexto Crear el ámbito (EP apunta hacia el) Copiar el Display de la clausura de la función Leer los argumentos y ponerlos en el ámbito Ejecutar el cuerpo de la función (deja el valor de retorno en la pila de argumentos Eliminar el ámbito Recuperar EP de la pila de contexto retornar

    edu.red

    18 Llamada a Función Simple Función: (defun f (x y) (list x y)) Llamada: (f 10 20) 10 PC de ret 20 EP PC de ret X Y 10 20 EP PC de ret X=10 Y=20 EP PC de ret X=10 Y=20 (10 20) (10 20) Poner Arg. Crear ámbito Sacar Arg Ejecutar cuerpo Salir

    edu.red

    19 Llamada a Función con Display Función: (defun f (x y) (labels ((g (a) (+ a x))) (list x (g y)))) Llamada: (f 10 20) EP PC de ret X=10 Y=20 Poner Arg. Crear ámbito Sacar Arg Ejecutar cuerpo Salir 10 20 PC de ret EP PC de ret X=10 Y=20 10 20 PC de ret EP(ED) Disp:EP f a EP PC de ret X=10 Y=20 10 PC de ret EP(ED) Disp:EP f a=20 EP PC de ret X=10 Y=20 10 30 PC de ret EP(ED) Disp:EP f a=20 EP PC de ret X=10 Y=20 10 30

    edu.red

    20 Clausuras Una clausura es un código de una función junto con el apuntador al ámbito en que se ha de ejecutar la función. Ejemplo: clausura de g:

    Donde ha de estar el ámbito de f: Si solo se llama a g desde dentro de f, el ámbito de f puede estar en la pila Si es posible llamar a g desde fuera de f, el ámbito de f ha de estar en el HEAP. Código de G X=10 Y=20 ámbito de F clausura de g

    edu.red

    21 Ejempo de Clausuras en el HEAP Función que retorna dos funciones ligadas por una variable local (defun varEscondida (n) (list (lambda (x) (+ x n)) (lambda (x) (setq n x)) ) )

    (setq a (varEscondida 10)) (# #)

    (funcall (first a) 5) 15

    (funcall (second a) 30) 30

    (funcall (first a) 5) 35

    edu.red

    22 Listas Por Comprensión La notación de conjuntos por comprensión es Compacta Fácil de entender Muy expresiva Por ejemplo Expresa el conjunto de los cuadrados de los números pertenecientes al intervalo [1,100] divisibles por 5. Por lo anterior se ha implementado en los lenguajes de programación funcionales Hope, Miranda, Haskell, etc., pero se cambia el conjunto por lista. Notación: [expresión | generadores y guardas] Generador: variable