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 }
| Página siguiente |