Download Parte 2 - Lenguajes de Programación

Lenguajes de Programación
Fundamentos de Racket - Parte II
Manuel Soto Romero
Universidad Nacional Autónoma de México
Facultad de Ciencias
10 de febrero de 2017
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
1 / 23
Diseño de funciones
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
2 / 23
Diseño de funciones
Cuando se tiene que implementar una función, se recomienda seguir
los siguientes pasos para su diseño:
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
2 / 23
Diseño de funciones
Cuando se tiene que implementar una función, se recomienda seguir
los siguientes pasos para su diseño:
1. Entender lo que la función tiene que hacer.
2. Escribir la descripción de la función.
3. Escribir su contrato, o sea su tipo (cuántos parámetros, de qué
tipo, qué retorna).
4. Escribir las pruebas unitarias asociadas a esta función sobre los
distintos posibles datos de entrada que pueda tener (casos
significativos).
5. Finalmente, implementar el cuerpo de la función.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
2 / 23
Descripción, contrato y pruebas
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
3 / 23
Descripción, contrato y pruebas
El contrato y la descripción se especifican en comentarios:
;; Función que calcula la potencia de una base x elevada
;; a un exponente b.
;; potencia: number number -> number
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
3 / 23
Descripción, contrato y pruebas
El contrato y la descripción se especifican en comentarios:
;; Función que calcula la potencia de una base x elevada
;; a un exponente b.
;; potencia: number number -> number
Escribir pruebas nos obliga a entender el comportamiento de la
función. Usaremos la primitiva test para definir pruebas unitarias:
(test (<nombre-funcion> <parámetros>+) <resultado-esperado>)
Ejemplos:
(test (potencia 2 0) 1)
(test (potencia 2 1) 2)
(test (potencia 2 3) 8)
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
3 / 23
Recursión
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
4 / 23
Recursión
Necesitamos pensar inductivamente, tal y como lo hacemos con los
números naturales.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
4 / 23
Recursión
Necesitamos pensar inductivamente, tal y como lo hacemos con los
números naturales.
I
Demostramos la propiedad para el caso base (el cero).
I
Asumiendo que se cumple para un número natural n,
demostramos que es cierto para un n + 1.
P (0)
P ( n ) ⇒ P ( n + 1)
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
4 / 23
Función potencia
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
5 / 23
Función potencia
Analizando la función potencia, tenemos:
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
5 / 23
Función potencia
Analizando la función potencia, tenemos:
x b = x x c−1 x c−2 ... x0
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
5 / 23
Función potencia
Analizando la función potencia, tenemos:
x b = x x c−1 x c−2 ... x0
Ejemplo:
23 = 2 22
1 0
2
2
Recordando que x0 = 1 por definición.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
5 / 23
Función potencia
Analizando la función potencia, tenemos:
x b = x x c−1 x c−2 ... x0
Ejemplo:
23 = 2 22
1 0
2
2
Recordando que x0 = 1 por definición.
Recursivamente:
x b = x x b −1
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
5 / 23
Función potencia en Racket
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
6 / 23
Función potencia en Racket
;; Función que calcula la potencia de una base x elevada
;; a un exponente b.
;; potencia: number number -> number
(define (potencia x b)
(if (zero? b)
1 ; caso base
(* b (potencia b (- x 1))))) ; paso recursivo
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
6 / 23
Función potencia en Racket
;; Función que calcula la potencia de una base x elevada
;; a un exponente b.
;; potencia: number number -> number
(define (potencia x b)
(if (zero? b)
1 ; caso base
(* b (potencia b (- x 1))))) ; paso recursivo
(potencia 2 3)
= (* 2 (potencia 2 2))
= (* 2 (* 2 (potencia 2 1)))
= (* 2 (* 2 (* 2 (potencia 2 0))))
= (* 2 (* 2 (* 2 1))))
= (* 2 (* 2 2))
= (* 2 4)
= 8
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
6 / 23
Pares
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
7 / 23
Pares
La estructura de datos más básica en Racket es el par, que pega dos
valores juntos.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
7 / 23
Pares
La estructura de datos más básica en Racket es el par, que pega dos
valores juntos.
> (cons 1 2)
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
7 / 23
Pares
La estructura de datos más básica en Racket es el par, que pega dos
valores juntos.
> (cons 1 2)
> (car (cons 1 2))
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
7 / 23
Pares
La estructura de datos más básica en Racket es el par, que pega dos
valores juntos.
> (cons 1 2)
> (car (cons 1 2))
> (cdr (cons 1 2))
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
7 / 23
Pares
La estructura de datos más básica en Racket es el par, que pega dos
valores juntos.
> (cons 1 2)
> (car (cons 1 2))
> (cdr (cons 1 2))
> ’(1 . 2)
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
7 / 23
Ejemplos
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
8 / 23
Ejemplos
I
Definir una función (suma u v) que regrese la suma de dos pares.
I
Definir una función (prod k u) que regrese el producto por
escalar de los pares u y k.
I
Definir una función (punto u v) que regrese el producto punto de
dos pares.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
8 / 23
Ejemplos
I
Definir una función (suma u v) que regrese la suma de dos pares.
I
Definir una función (prod k u) que regrese el producto por
escalar de los pares u y k.
I
Definir una función (punto u v) que regrese el producto punto de
dos pares.
(define (suma u v)
(cons (+ (car u) (car v)) (+ (cdr u) (cdr v))))
(define (prod k u)
(cons (* k (car u)) (* k (cdr u))))
(define (punto u v)
(+ (* (car u) (car v)) (* (cdr u) (cdr v))))
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
8 / 23
Listas
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
9 / 23
Listas
Muchas estructuras pueden ser construidas a partir de pares. Tal es el
caso de las listas.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
9 / 23
Listas
Muchas estructuras pueden ser construidas a partir de pares. Tal es el
caso de las listas.
I
La lista vacía es una lista y se representa por ’(), null o empty.
I
Si x es un elemento de un conjunto cualquiera y xs es una lista,
entonces (cons x xs) es una lista, x es la cabeza y xs es el
resto.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
9 / 23
Listas
Muchas estructuras pueden ser construidas a partir de pares. Tal es el
caso de las listas.
I
La lista vacía es una lista y se representa por ’(), null o empty.
I
Si x es un elemento de un conjunto cualquiera y xs es una lista,
entonces (cons x xs) es una lista, x es la cabeza y xs es el
resto.
> ’()
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
9 / 23
Listas
Muchas estructuras pueden ser construidas a partir de pares. Tal es el
caso de las listas.
I
La lista vacía es una lista y se representa por ’(), null o empty.
I
Si x es un elemento de un conjunto cualquiera y xs es una lista,
entonces (cons x xs) es una lista, x es la cabeza y xs es el
resto.
> ’()
> empty
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
9 / 23
Listas
Muchas estructuras pueden ser construidas a partir de pares. Tal es el
caso de las listas.
I
La lista vacía es una lista y se representa por ’(), null o empty.
I
Si x es un elemento de un conjunto cualquiera y xs es una lista,
entonces (cons x xs) es una lista, x es la cabeza y xs es el
resto.
> ’()
> empty
> (cons 1 (cons 2 (cons 3 empty)))
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
9 / 23
Formas de construir listas
Imagen tomada de ”Realm of Racket”
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
10 / 23
Ejemplos
>
>
>
>
>
>
>
>
>
>
>
>
(1 2 3)
’(1 2 3)
’(1 2 (+ 1 2))
(list 1 2 (+ 1 2))
(define l1 ’(1 2 3))
(define l2 ’(4 5 6))
(append l1 l2)
(car l1)
(cdr l1)
(car (cdr l1))
(cadr l1)
(caddr l1)
Manuel Soto Romero (UNAM)
>
>
>
>
>
>
>
>
>
>
>
(first l1)
(second l1)
(second (list 1 (+ 2 3) 3))
(second ’(1 (+ 2 3)))
(fourth l1)
(length l1)
(list-ref l1 0)
(reverse l1)
(findf even? ’(1 2 3 4 5 6))
(map add1 ’(1 2 3))
(filter even? ’(1 2 3))
Lenguajes de Programación
10 de febrero de 2017
11 / 23
Inducción estructural
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
12 / 23
Inducción estructural
Generaliza la inducción a estructuras más complejas que los números
naturales. Se tiene un caso base, pero en lugar de paso inductivo se
tiene un patrón recursivo.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
12 / 23
Inducción estructural
Generaliza la inducción a estructuras más complejas que los números
naturales. Se tiene un caso base, pero en lugar de paso inductivo se
tiene un patrón recursivo.
Para lograr la inducción sobre estructuras, suele usarse la técnica de
caza de patrones (pattern matching). En Racket usamos match.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
12 / 23
Inducción estructural
Generaliza la inducción a estructuras más complejas que los números
naturales. Se tiene un caso base, pero en lugar de paso inductivo se
tiene un patrón recursivo.
Para lograr la inducción sobre estructuras, suele usarse la técnica de
caza de patrones (pattern matching). En Racket usamos match.
(match <expresión>
[<patrón> <expresion>]+)
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
12 / 23
Ejemplos
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
13 / 23
Ejemplos
(match (and #t #f)
[#t ”bien”]
[#t ”mal”])
(match 1
[2 #t]
[3 #f])
(match 1
[2 #t]
[3 #f]
[else ”No hay caso para este número :(”])
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
13 / 23
Longitud de una lista
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
14 / 23
Longitud de una lista
;; Función que regresa la longitud de una lista.
;; longitud: list -> number
(define (longitud l)
(match l
[’() 0]
[(cons x xs) (+ 1 (longitud xs))]))
(test (longitud ’()) 0)
(test (longitud ’(1 2 3 4)) 4)
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
14 / 23
Contención
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
15 / 23
Contención
;; Predicado que determina si un elemento está contenido en
;; una lista.
;; contiene?: list -> boolean
(define (contiene? l e)
(match l
[’() #f]
[(cons x xs) (or (equal? x e) (contiene? xs e))]))
(test (contiene? ’() 5) #f)
(test (contiene? ’(1 2 3 4) 4) #t)
(test (contiene? ’(1 2 3 4) 5) #f)
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
15 / 23
Suma de elementos
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
16 / 23
Suma de elementos
;; Función que suma los elementos de la lista.
;; suma-elems: list -> number
(define (suma-elems l)
(match l
[’() 0]
[(cons x xs) (+ x (suma-elems xs))]))
(test (suma-elems ’()) 0)
(test (suma-elems ’(1 2 3 4)) 10)
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
16 / 23
Multiplica elementos
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
17 / 23
Multiplica elementos
;; Función que multiplica los elementos de la lista.
;; mult-elems: list -> number
(define (mult-elems l)
(match l
[’() 1]
[(cons x xs) (* x (mult-elems xs))]))
(test (mult-elems ’()) 1)
(test (mult-elems ’(1 2 3 4)) 24)
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
17 / 23
Funciones de plegado
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
18 / 23
Funciones de plegado
Las funciones de plegado foldr y foldl encapsulan los patrones de
recursión de la suma y el producto.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
18 / 23
Funciones de plegado
Las funciones de plegado foldr y foldl encapsulan los patrones de
recursión de la suma y el producto.
Definen funciones sobre listas recibiendo un operador y un valor final
como argumentos.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
18 / 23
Funciones de plegado
Las funciones de plegado foldr y foldl encapsulan los patrones de
recursión de la suma y el producto.
Definen funciones sobre listas recibiendo un operador y un valor final
como argumentos.
>
>
>
>
(foldr
(foldl
(foldr
(foldl
+
+
*
*
0
0
1
1
’(1
’(1
’(1
’(1
Manuel Soto Romero (UNAM)
2
2
2
2
3
3
3
3
4))
4))
4))
4))
Lenguajes de Programación
10 de febrero de 2017
18 / 23
foldr
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
19 / 23
foldr
(define (foldr f v l)
(match l
[’() v]
[(cons x xs) (f x (foldr f v xs))]))
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
19 / 23
foldr
(define (foldr f v l)
(match l
[’() v]
[(cons x xs) (f x (foldr f v xs))]))
Ejemplo:
(foldr
= (+ 1
= (+ 1
= (+ 1
= (+ 1
= (+ 1
= (+ 1
= (+ 1
= (+ 1
= 10
+ 0 ’(1 2 3 4))
(foldr + 0 ’(2 3 4)))
(+ 2 (foldr + 0 ’(3 4))))
(+ 2 (+ 3 (foldr + 0 ’(4)))))
(+ 2 (+ 3 (+ 4 (foldr + 0 ’())))))
(+ 2 (+ 3 (+ 4 0))))
(+ 2 (+ 3 4)))
(+ 2 7))
9)
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
19 / 23
foldl
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
20 / 23
foldl
(define (foldr f v l)
(match l
[’() v]
[(cons x xs) (foldl f (f x v) xs)]))
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
20 / 23
foldl
(define (foldr f v l)
(match l
[’() v]
[(cons x xs) (foldl f (f x v) xs)]))
Ejemplo:
(foldl + 0 ’(1 2 3 4))
= (foldl + (+ 1 0) ’(2 3 4))
= (foldl + (+ 2 (+ 1 0)) ’(3 4)
= (foldl + (+ 3 (+ 2 (+ 1 0))) ’(4))
= (foldl + (+ 4 (+ 3 (+ 2 (+ 1 0)))) ’())
= (+ 4 (+ 3 (+ 2 (+ 1 0))))
= (+ 4 (+ 3 (+ 2 1)))
= (+ 4 (+ 3 3))
= (+ 4 6)
= 10
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
20 / 23
Funciones anónimas
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
21 / 23
Funciones anónimas
Se pueden definir funciones anónimas usando la forma sintáctica
lambda.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
21 / 23
Funciones anónimas
Se pueden definir funciones anónimas usando la forma sintáctica
lambda.
Suelen usarse cuando usamos una función para un caso particular y
que no se necesiten más adelante.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
21 / 23
Funciones anónimas
Se pueden definir funciones anónimas usando la forma sintáctica
lambda.
Suelen usarse cuando usamos una función para un caso particular y
que no se necesiten más adelante.
> (lambda (x) (+ x 124))
> (map (λ (x) (+ x 124)) ’(1 2 3))
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
21 / 23
Funciones anónimas
Se pueden definir funciones anónimas usando la forma sintáctica
lambda.
Suelen usarse cuando usamos una función para un caso particular y
que no se necesiten más adelante.
> (lambda (x) (+ x 124))
> (map (λ (x) (+ x 124)) ’(1 2 3))
Azúcar sintáctica en funciones:
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
21 / 23
Funciones anónimas
Se pueden definir funciones anónimas usando la forma sintáctica
lambda.
Suelen usarse cuando usamos una función para un caso particular y
que no se necesiten más adelante.
> (lambda (x) (+ x 124))
> (map (λ (x) (+ x 124)) ’(1 2 3))
Azúcar sintáctica en funciones:
(define (foo x) x)
(define foo (λ (x) x))
(foo 10)
(let ([f (λ (x) x)]) (f 10))
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
21 / 23
letrec
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
22 / 23
letrec
Para funciones recursivas, se usa implícitamente letrec.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
22 / 23
letrec
Para funciones recursivas, se usa implícitamente letrec.
(letrec ([suma (lambda (l)
(if (empty? l) 0 (+ (car l) (suma (cdr l)))))])
(suma ’(1 2 3 4)))
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
22 / 23
Ejercicios
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
23 / 23
Ejercicios
Los ejercicios se encuentran en
http://lenguajesfc.com/laboratorio.html
Enviar al correo [email protected] un archivo
equipo_sesion2.rkt con asunto [LDP-Sesión 2] a más tardar a las
16:59:59.
Incluir el nombre de los integrantes en el cuerpo del correo.
Sólo pueden entregar aquellos alumnos que aparezcan en la lista
de asistencia de la sesión. No es válido apuntar a miembros del
equipo que no estén presentes.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
10 de febrero de 2017
23 / 23