Implementación de Lenguajes Funcionales (ppt) (página 2)

Partes: 1, 2

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 <- 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.Tail, x>=l.Head])
}

Fun Sort(l:List)=>
{
if (l==[]) []
else {
Var menores=[];
for (e<-l.Tail)
if (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==[]) << { * = []; = &->Tail; } >>
else if (ApplyFunP(Conds.Head,`<-,2)) { // Generador
Var sl=symbol("ListaGenerador"), sv=Conds.Head.Arg(0);
Var srepetir=symbol("Repetir");
<< {
Var = ;
Label ;
if ( != []) {
Var = .Head;
;
= .Tail;
goto ;
}
} >>
}
else { // Condición
<< if () >>
}
}
<< {
Var = [], = &;
;

} >>
}

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
}