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
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
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
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
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
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
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