Ejemplo: Producto de matrices ***************************** Las matrices m se representan como una lista de las filas en donde cada fila es un lista con los elementos. En otras palabras m corresponde a: ( (m11 m12 ...) (m21 m22 ...) ...) en donde mij representa el elemento de m en la fila i y col. j. Por El objetivo implementar (prod m1 m2) como el producto de m1 y m2, suponiendo que ambas matrices están bien formadas. Ej.: (prod '((1 2) (3 4) (5 6)) '((3 5) (4 6))) => ((11 17) (25 39) (39 61)) previo: - calcular la matriz traspuesta (define (traspuesta m) (cond ((null? (car m)) '()) (else (cons (map car m) (traspuesta (map cdr m)))) )) - calcular el producto punto entre dos vectores (a1 a2 ...) (b1 b2 ...) con el mismo número de elementos: Sol. 1 (define (prod-punto v w) (apply + (map (lambda (x y) (* x y)) v w))) Sol. 2 (define (prod-punto v w) (cond ((null? v) 0) (else (+ (* (car v) (car w)) (prod-punto (cdr v) (cdr w)))) )) - calcular el producto de un vector por una matriz: Sol. 1 (define (prod-vect v m) (map (lambda (w) (prod-punto v w)) m)) Sol. 2 (define (prod-vect v m) (cond ((null? m) '()) (else (cons (prod-punto v (car m)) (prod-vect v (cdr m)))) )) - calcular el producto de matrices: Sol. 1 (define (prod a b) (prod-trasp a (traspuesta b))) (define (prod-trasp a b) (map (lambda (v) (prod-vect v b)) a) ) Sol. 2 (define (prod a b) (prod-trasp a (traspuesta b))) (define (prod-trasp a b) (cond ((null? a) '()) (else (cons (prod-vect (car a) b) (prod-trasp (cdr a) b))) )) Recursión por la cola ********************* Motivación: procedimiento para calcular el largo de la pila. (define (len l) (cond ((null? l) 0) (else (+ 1 (len (cdr l)))) )) Una típica preocupación usual de los programadores en Scheme es que este procedimiento puede alcanzar niveles de profundidad excesivos para la pila, haciendo que se desborde. Si esto es un problema, se puede modificar la implementación para lograr recursión por la cola: (define (len2 l) (tail-len l 0)) (define (tail-len l s) (cond ((null? l) s) (else (tail-len (cdr l) (+ s 1))) )) Se dice que (tail-len ...) es una llamada por la cola, i.e. el valor retornado por el llamador es directamente el valor retornado por el llamado (sin nunguna operación entre medio). En cambio la llamada de len en len no es por la cola porque es necesario procesar el valor sumándole 1, antes de retornarlo. Se requiere que todas las implementaciones de Scheme sean *recursivas por la cola propiamente*, lo que significa que cuando la recursión es por la cola el tamaño de la pila requerida es *fijo*. En realidad antes de hacer una llamada recursiva por la cola se desapila el registro de activación del procedimiento recursivo (como tail-len), lo que lo hace equivalente a la implementación de un while. Segundo ejemplo: inversión de una lista (rev) (define (rev l) (tail-rev l '())) (define (tail-rev l r) (cond ((null? l) r) (else (tail-rev (cdr l) (cons (car l) r))) )) Ciclos ****** Motivación: máximo común denominador mcd(15, 18)= 3 - Versión imperativa: mcd(x, y) { while (x!=y) if (x x y) (set! x (- x y)) (set! y (- y x))) (loop) )))) - Modificación de pares: (set-car! cons-exp val) evalúa las expresiones cons-exp y val. La primera expresión debe ser un par. Entonces asigna el campo car con el resultado de la segunda expresión. Además existe (set-cdr! cons-exp val) para modificar el cdr. Ejemplo: reverse mutable (define (reverse! l) (let ((curr l) (last '()) (next '()) ) (let loop () (if (not (pair? curr)) last (begin (set! next (cdr curr)) (set-cdr! curr last) (set! last curr) (set! curr next) (loop) ))))) Ejemplo: (define list '(a b c)) (define tail (cddr list)) list => (a b c) (reverse! list) => (c b a) list => (a) tail => (c b a) Identidad vs. Igualdad ********************** Los efectos laterales transforman los valores de scheme en objetos, i.e. tienen una dirección como los objetos de Java. - Test de identidad: eq? Permite determinar si dos objetos en Scheme son el mismo. - Test de igualdad: equal? Permite determinar si dos objetos tienen el mismo contenido. Ejemplos: (define list12 '(1 2)) ; list12 referencia una lista con 2 pares (define tail (cdr list12)) (define list2 (list 2)) ; construye un nuevo par! (eq? list2 (cdr list12)) => #f no, porque no se trata del mismo par (eq? tail (cdr list12)) => #t si, es el mismo par (equal? list2 (cdr list12)) => #t no son el mismo, pero tiene igual contenido - Los números también son objetos: (define pi 3.14) (define pi2 pi) (eq? pi pi2) => #t (eq? pi (+ 3. 0.14)) => #f en muchas implementaciones (eq? pi 3.14)) => #f en muchas implementaciones Vectores ******** - (define v (make-vector 10 "")) crea un vector con 10 elementos con "". - (vector-ref v 0) ... (vector-ref v 9) accede a los elementos del vector. - (vector-set! v i exp) asigna un valor al elemento con índice i. Ejemplo: sieve, determina los números primos entre 2 y n-1 (define (sieve n) (let ((primos (make-vector n #t))) ; al final primos[i]==#t <=> i es primo (let loopi ((i 2)) (if (< i n) (begin (if (vector-ref primos i) (let loopj ((j (+ i i))) ; i es primo (if (< j n) (begin (vector-set! primos j #f) (loopj (+ j i)) )))) ; i, 2i, 3i, ... no son primos (loopi (+ i 1)) ))) (let loopi ((i 2)) (if (< i n) (begin (if (vector-ref primos i) (begin (display i) (newline)) ) (loopi (+ i 1)) ))))) Ejercicios: 1) Escribir en Scheme un procedimiento recursivo por la cola que determine los números primos hasta n-1. Use un algoritmo distinto: (remainder x y) = 0 significa que x es divisible por y. 2) Escriba una versión del producto de matrices que use vectores de vectores para representar las matrices. Clausuras ********* La forma especial lambda permite crear procedimientos anónimos llamados clausuras (closures). Lambda puede acceder a cualquier variable visible en el contexto en donde se define. Ejemplo: (define (make-gen n) (lambda () (set! n (+ n 1)) n)) (define gen-a (make-gen 0)) gen-a => #[a procedure] (gen-a) => 1 (gen-a) => 2 (define gen-b (make-gen 10)) (gen-b) => 11 (gen-a) => 3 En scheme, el tiempo de vida de una variable es conceptualmente ilimitado. Esto significa que el parámetro n de make-gen no se destruye cuando éste retorna. La variable se aloja en el heap y es referenciada desde el objeto lambda, una clausura, que se crea dinámicamente, y que también se aloja en el heap. Cuando el recolector de basura detecta que la clausura no es accesible por la aplicación, entonces se recicla y por lo tanto la variable n tampoco es accesible y también se recicla. Una típica implementación de una clausura es mediante un objeto que referencia primero el código ejecutable y luego todas las variables que "captura", i.e. que son definidas afuera del lambda. Si Scheme colocara todas las variables en el heap, sería demasiado ineficiente (una variable en el heap cuesta 10 veces mas tiempo de CPU que una variable puesta en el stack). Por ello los compiladores analizan los programas y determinas qué variables son capturadas por los lambdas y cuales no. Las que son capturadas se alojan el heap, las que no, en el stack. quasiquote ********** La principal ventaja de no utilizar una sintaxis en Scheme, sino que representar los programas usando las listas de Scheme, es que se puede manipular trivialmente los programas. Central a esta propiedad está quasiquote, que permite escribir listas casi constantes, en donde sólo algunos de los elementos son calculados. Forma general: `list-exp en donde hay apariciones de ,exp o ,@exp - Ejemplo 1: supongamos que x es 1 e y es (+ a 1), entonces: `(let ((a ,x)) ,y) => (let ((a 1) (+ a 1)) en realidad la expresión es equivalente a: (list ´let (list (list 'a x)) y) (quasiquote (let ((a (unquote x))) (unquote y)) - Ejemplo 2: supongamos que l es (1 2 3), entonces: `(+ ,@l 4) => (+ 1 2 3 4) en realidad la expresión es equivalente a: (append '(+) l '(4)) (quasiquote (+ (unquote-splicing l) 4)) - unquote (,) se puede usar en cualquier parte dentro de una lista con quasiquote. Esto quiere decir que ,x aislado es un error. Sin embargo, ',a => (unquote a) - unquote-splicing (,@) se puede usar sólo en una lista, dentro de una expresión con quasiquote.