TEMA
IMPLEMENTACION DE LENGUAJES
FUNCIONALES.
Lecciónes
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)
}
Estado de la pila
justo antes de
llamar a g
( parametros de g
en la pila)
Pila
anterior
b
a
PC f
ED
c
d
e
d
c
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
Bloque de
activación de f
Parámetros de g
Pila
anterior
d
c
PC f
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
EP
CSP
AP
Pila de
Argumentos
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
}
Display
Bloque de
activación de f
Clausura de g
PC
EP
x
y
EP
Entrada g
EP def
Clausura
Bloque de
activación de g
PC
EP
EP f
a
b
z
EP
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
Env
Pila
anterior
PC
EP
SP
Contenido de la pila
al llamar a f con el ámbito
en el heap
EP
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
Ambito en la pila
Pila de contexto
PC
EP
EP
Display
Argumentos
Variables
CSP
Ambito en el Heap
Heap
nulo
Pila de contexto
PC
EP
EP
Display
CSP
Argumentos
Variables
Env
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
Pila de
Contexto
EP
CSP
AP
Pila de
Argumentos
Heap
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)
Poner
Arg.
Sacar
Arg
Crear
ámbito
Ejecutar
cuerpo
Salir
PC de ret PC de ret PC de ret PC de ret
EP
EP
EP
X
X=10
X=10
Y
Y=20
Y=20
20
10
20
10
(10 20)
(10 20)
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)
Poner
Arg.
Sacar
Arg
Crear
ámbito
PC de ret PC de ret
EP
EP
X=10
X=10
Y=20
Y=20
PC de ret PC de ret
EP(ED)
Disp:EP f
a
20
10
20
10
Ejecutar
cuerpo
PC de ret
EP
X=10
Y=20
PC de ret
EP(ED)
Disp:EP f
a=20
10
Salir
PC de ret PC de ret
EP
EP
X=10
X=10
Y=20
Y=20
PC de ret
EP(ED)
Disp:EP f
a=20
30
10
30
10
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:
clausura de g
ámbito de F
X=10
Y=20
Código
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.
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))
(#<Closure: #ffd8b044> #<Closure: #ffd8b020>)
(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
{ x | x  [1 .. 100 ], x mod 5  0}
2
– 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 <- lista o intervalo
– Guarda: condición
• Ejemplo: [x**2 | x<-1..100, x%5==0]
23
Generadores y Guardas
[expresión | generadores y guardas]
• Generadores variable <- lista o intervalo
– Declara la variable
– La variable se instanciará con todos los
elementos de la lista
• Guardas condición
– Si la condición se cumple se evaluará la
expresión y se guardará en la lista
resultante
• Ejemplos
var l=[1,2,3,9,1]
var l2=[6,4,2,19]
[(x,y) | x<-l; y<-l2, x>y]
Resultado:
[(3,2),(9,6),(9,4),(9,2)]
24
Quick Sort con Listas por Comprensión
Fun Sort(l:List)=>
{
if (l==[]) []
else
Sort([x | x<-l.Tail, x<l.Head)]) ++
[l.Head] ++
Sort([x | x<-l.Tail, x>=l.Head])
}
Fun Sort(l:List)=>
{
if (l==[]) []
else {
Var menores=[];
for (e<-l.Tail)
if (e<l.Head) menores=e::menores;
Var mayores=[];
for (e<-l.Tail)
if (e>=l.Head) mayores=e::mayores;
Sort(menores)++[l.head]++Sort(mayores)
}
}
25
Qsort Funcional e Imperativo
• Quicksort in Haskell
qsort []
= []
qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
where
elts_lt_x
= [y | y <- xs, y < x]
elts_greq_x = [y | y <- xs, y >= x]
• Quicksort in C
void qsort( int a[], int lo, int hi )
{
int h, l, p, t;
if (lo < hi) {
l = lo;
h = hi;
p = a[hi];
do {
while ((l < h) && (a[l] <= p))
l = l+1;
while ((h > l) && (a[h] >= p))
h = h-1;
if (l < h) {
t = a[l];
a[l] = a[h];
a[h] = t;
}
} while (l < h);
t = a[l];
a[l] = a[hi];
a[hi] = t;
qsort( a, lo, l-1 );
qsort( a, l+1, hi );
}
}
26
Listas por Comprensión en LISP (I)
(defmacro listcomp (Exp &rest Conds)
(let ((SymList (gensym "LIST")) (SymP (gensym "P")))
`(let* ((,SymLIST (cons nil nil)) (,SymP ,SymLIST))
,(ListComp2 Exp Conds SymP)
(cdr ,SymLIST)
)
)
)
(defun ListComp2 (E Q L)
(cond
((null Q)
`(progn (setf (cdr ,L) (cons ,E nil)) (setq ,L (cdr ,L)))
)
((and (consp (car Q)) (eq (caar Q) 'in))
`(dolist (,(cadar Q) ,(caddar Q))
,(ListComp2 E (cdr Q) L)
)
)
(T `(when ,(car Q) ,(ListComp2 E (cdr Q) L)))
)
)
27
Listas por Comprensión en LISP (II)
• Ejemplo
(setq l ‘(1 10 5 2 9))
(ListComp (* x x) (in x l) (> x 3))
– Resultado: (100 25 81)
– Código generado:
(LET* ((LIST5 (CONS NIL NIL)) (P6 LIST5))
(DOLIST (X L)
(WHEN (> X 3) (PROGN
(SETF (CDR P6) (CONS (* X X) NIL))
(SETQ P6 (CDR P6)))))
(CDR LIST5))
– Código “optimizado”:
(LET* ((LIST5 (CONS NIL NIL)) (P6 LIST5))
(DOLIST (X L)
(WHEN (> X 3)
(SETF (CDR P6) (CONS (* X X) NIL))
(SETQ P6 (CDR P6))))
(CDR LIST5))
28
Listas por Comprensión en CoSeL
Fun ListComp(Exp,Conds)=>
{
Var SList=symbol("Lista"), SP=symbol("Posicion");
Fun ListComp2(Conds)=>
{
if (Conds==[]) << { *<SymP> = [<Exp>]; <SP> = &<SP>->Tail; } >>
else if (ApplyFunP(Conds.Head,`\<-,2)) { // Generador
Var sl=symbol("ListaGenerador"), sv=Conds.Head.Arg(0);
Var srepetir=symbol("Repetir");
<< {
Var <sl> = <Conds.Head.Arg(1)>;
Label <sRepetir>;
if (<sl> != []) {
Var <sv> = <sl>.Head;
<ListComp2(Conds.Tail)>;
<sl> = <sl>.Tail;
goto <sRepetir>;
}
} >>
}
else { // Condición
<< if (<Conds.Head>) <ListComp2(Conds.Tail)> >>
}
}
<< {
Var <SList> = [], <SP> = &<SList>;
<ListComp2(Conds)>;
<SList>
} >>
}
29
Ejemplo
ListComp(`x,[`(x<-li),`(x>10)])
{
Var Lista=[];
Var Posicion=&Lista;
{
Var ListaGenerador=li;
Label Repetir;
if (ListaGenerador!=[]) {
Var x=ListaGenerador.Head;
if (x>10) {
&Posicion=[x];
Posicion=&Posicion->Tail;
}
ListaGenerador=ListaGenerador.Tail;
GoTo Repetir
}
}
Lista
}
30
Pattern Maching
31
Descargar

Funcionales