Download Parte 1 - Lenguajes de Programación

Lenguajes de Programación
Tipos de datos abstractos - Parte I
Manuel Soto Romero
Universidad Nacional Autónoma de México
Facultad de Ciencias
17 de febrero de 2017
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
1 / 10
Gramáticas
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
2 / 10
Gramáticas
Una gramática, es en pocas palabras, una forma de describir las
reglas de escritura de las expresiones que pertenecen a un lenguaje.
S → 0S | 0A
A → 1A | 1
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
2 / 10
Gramáticas
Una gramática, es en pocas palabras, una forma de describir las
reglas de escritura de las expresiones que pertenecen a un lenguaje.
S → 0S | 0A
A → 1A | 1
I
Cada renglón de la gramática es llamado producción .
I
Cada producción indica cómo sustituir los símbolos no terminales
(S y A) para llegar a una expresión compuesta únicamente por
símbolos no terminales (0 y 1).
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
2 / 10
Forma extendida de Backus Naur
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
3 / 10
Forma extendida de Backus Naur
Para representar las especificaciones o reglas sintácticas de un
lenguaje de programación, es común usar la Forma Extendida de
Backus Naur (EBNF).
<S> :=
|
<A> :=
|
0<S>
0<A>
1<A>
1
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
3 / 10
Forma extendida de Backus Naur
Para representar las especificaciones o reglas sintácticas de un
lenguaje de programación, es común usar la Forma Extendida de
Backus Naur (EBNF).
<S> :=
|
<A> :=
|
0<S>
0<A>
1<A>
1
I
Usamos el símbolo := en lugar de →.
I
Los símbolos terminales van entre diamantes <>.
I
Los símbolos de barra | simplemente separan las posibles
sustituciones.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
3 / 10
Gramáticas en Racket
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
4 / 10
Gramáticas en Racket
El dialecto plai cuenta con mecanismos especiales para definir
gramáticas.
(define-type Nombre
[constructor (p Tipo?)*]+)
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
4 / 10
Gramáticas en Racket
El dialecto plai cuenta con mecanismos especiales para definir
gramáticas.
(define-type Nombre
[constructor (p Tipo?)*]+)
Al definir una gramática en Racket, realmente estamos creando un
TDA.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
4 / 10
Gramáticas en Racket
El dialecto plai cuenta con mecanismos especiales para definir
gramáticas.
(define-type Nombre
[constructor (p Tipo?)*]+)
Al definir una gramática en Racket, realmente estamos creando un
TDA.
Podemos escribir expresiones de
estos TDA en el intérprete.
(define-type Nat
[cero]
[sucesor (n Nat?)])
> (cero)
cero
> (sucesor (sucesor (cero)))
(sucesor (sucesor (cero)))
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
4 / 10
¿Qué otra cosa podemos hacer con define-type?
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
5 / 10
¿Qué otra cosa podemos hacer con define-type?
Al definir un nuevo TDA con define-type, el lenguaje nos regala por
defecto varias cosas:
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
5 / 10
¿Qué otra cosa podemos hacer con define-type?
Al definir un nuevo TDA con define-type, el lenguaje nos regala por
defecto varias cosas:
1. Un predicado para verificar que una expresión es de ese tipo.
2. Un predicado por cada constructor definido.
3. Para cada parámetro de un constructor, nos regala una función
que obtiene el valor de dicho parámetro.
4. Por cada parámetro de un constructor, nos regala una función
para modificar el valor de dicho parámetro.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
5 / 10
El TDA Nat
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
6 / 10
El TDA Nat
(define-type Nat
[cero]
[sucesor (n Nat?)])
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
6 / 10
El TDA Nat
(define-type Nat
[cero]
[sucesor (n Nat?)])
Racket nos regala:
I Nat?
I cero?
I sucesor?
I sucesor-n
I set-sucesor-n!
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
6 / 10
El TDA Nat
(define-type Nat
[cero]
[sucesor (n Nat?)])
> (Nat? (sucesor (cero)))
Racket nos regala:
I Nat?
I cero?
I sucesor?
I sucesor-n
I set-sucesor-n!
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
6 / 10
El TDA Nat
(define-type Nat
[cero]
[sucesor (n Nat?)])
> (Nat? (sucesor (cero)))
#t
Racket nos regala:
I Nat?
I cero?
I sucesor?
I sucesor-n
I set-sucesor-n!
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
6 / 10
El TDA Nat
(define-type Nat
[cero]
[sucesor (n Nat?)])
> (Nat? (sucesor (cero)))
#t
> (cero? (cero))
Racket nos regala:
I Nat?
I cero?
I sucesor?
I sucesor-n
I set-sucesor-n!
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
6 / 10
El TDA Nat
(define-type Nat
[cero]
[sucesor (n Nat?)])
> (Nat? (sucesor (cero)))
#t
> (cero? (cero))
#t
Racket nos regala:
I Nat?
I cero?
I sucesor?
I sucesor-n
I set-sucesor-n!
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
6 / 10
El TDA Nat
(define-type Nat
[cero]
[sucesor (n Nat?)])
Racket nos regala:
> (Nat? (sucesor (cero)))
#t
> (cero? (cero))
#t
> (sucesor? (sucesor (cero)))
I Nat?
I cero?
I sucesor?
I sucesor-n
I set-sucesor-n!
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
6 / 10
El TDA Nat
(define-type Nat
[cero]
[sucesor (n Nat?)])
Racket nos regala:
> (Nat? (sucesor (cero)))
#t
> (cero? (cero))
#t
> (sucesor? (sucesor (cero)))
#t
I Nat?
I cero?
I sucesor?
I sucesor-n
I set-sucesor-n!
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
6 / 10
El TDA Nat
(define-type Nat
[cero]
[sucesor (n Nat?)])
Racket nos regala:
I Nat?
I cero?
> (Nat? (sucesor (cero)))
#t
> (cero? (cero))
#t
> (sucesor? (sucesor (cero)))
#t
> (define uno (sucesor (cero)))
> uno
I sucesor?
I sucesor-n
I set-sucesor-n!
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
6 / 10
El TDA Nat
(define-type Nat
[cero]
[sucesor (n Nat?)])
Racket nos regala:
I Nat?
I cero?
I sucesor?
> (Nat? (sucesor (cero)))
#t
> (cero? (cero))
#t
> (sucesor? (sucesor (cero)))
#t
> (define uno (sucesor (cero)))
> uno
(sucesor (cero))
I sucesor-n
I set-sucesor-n!
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
6 / 10
El TDA Nat
(define-type Nat
[cero]
[sucesor (n Nat?)])
Racket nos regala:
I Nat?
I cero?
I sucesor?
I sucesor-n
> (Nat? (sucesor (cero)))
#t
> (cero? (cero))
#t
> (sucesor? (sucesor (cero)))
#t
> (define uno (sucesor (cero)))
> uno
(sucesor (cero))
> (sucesor-n uno)
I set-sucesor-n!
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
6 / 10
El TDA Nat
(define-type Nat
[cero]
[sucesor (n Nat?)])
Racket nos regala:
I Nat?
I cero?
I sucesor?
I sucesor-n
> (Nat? (sucesor (cero)))
#t
> (cero? (cero))
#t
> (sucesor? (sucesor (cero)))
#t
> (define uno (sucesor (cero)))
> uno
(sucesor (cero))
> (sucesor-n uno)
(cero)
I set-sucesor-n!
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
6 / 10
El TDA Nat
(define-type Nat
[cero]
[sucesor (n Nat?)])
Racket nos regala:
I Nat?
I cero?
I sucesor?
I sucesor-n
I set-sucesor-n!
Manuel Soto Romero (UNAM)
> (Nat? (sucesor (cero)))
#t
> (cero? (cero))
#t
> (sucesor? (sucesor (cero)))
#t
> (define uno (sucesor (cero)))
> uno
(sucesor (cero))
> (sucesor-n uno)
(cero)
> (set-sucesor-n! uno (sucesor
(cero)))
Lenguajes de Programación
17 de febrero de 2017
6 / 10
El TDA Nat
(define-type Nat
[cero]
[sucesor (n Nat?)])
Racket nos regala:
I Nat?
I cero?
I sucesor?
I sucesor-n
I set-sucesor-n!
Manuel Soto Romero (UNAM)
> (Nat? (sucesor (cero)))
#t
> (cero? (cero))
#t
> (sucesor? (sucesor (cero)))
#t
> (define uno (sucesor (cero)))
> uno
(sucesor (cero))
> (sucesor-n uno)
(cero)
> (set-sucesor-n! uno (sucesor
(cero)))
> uno
Lenguajes de Programación
17 de febrero de 2017
6 / 10
El TDA Nat
(define-type Nat
[cero]
[sucesor (n Nat?)])
Racket nos regala:
I Nat?
I cero?
I sucesor?
I sucesor-n
I set-sucesor-n!
Manuel Soto Romero (UNAM)
> (Nat? (sucesor (cero)))
#t
> (cero? (cero))
#t
> (sucesor? (sucesor (cero)))
#t
> (define uno (sucesor (cero)))
> uno
(sucesor (cero))
> (sucesor-n uno)
(cero)
> (set-sucesor-n! uno (sucesor
(cero)))
> uno
(sucesor (sucesor (cero)))
Lenguajes de Programación
17 de febrero de 2017
6 / 10
Caza de patrones y TDA
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
7 / 10
Caza de patrones y TDA
Tenemos dos formas de procesar TDA mediante la técnica de caza de
patrones:
I
I
Mediante la primitiva match.
Mediante la primitiva type-case.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
7 / 10
Caza de patrones y TDA
Tenemos dos formas de procesar TDA mediante la técnica de caza de
patrones:
I
I
Mediante la primitiva match.
Mediante la primitiva type-case.
(match <expresion>
[<patron> <expresión>]+
[else <expresión>]*)
(type-case <Tipo> <expresión>
[<constructor> (<parámetro>*) <expresión>]+
[else <expresión>]*)
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
7 / 10
Caza de patrones y TDA
Tenemos dos formas de procesar TDA mediante la técnica de caza de
patrones:
I
I
Mediante la primitiva match.
Mediante la primitiva type-case.
(match <expresion>
[<patron> <expresión>]+
[else <expresión>]*)
(type-case <Tipo> <expresión>
[<constructor> (<parámetro>*) <expresión>]+
[else <expresión>]*)
Nota: El caso else de type-case sólo se puede usar cuando no se
cazan todos los patrones para un TDA.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
7 / 10
Suma de naturales
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
8 / 10
Suma de naturales
I
Definir una función suma1 que dados dos números naturales
regrese su suma, usar match para implementar esta función.
I
Definir una función suma2 que dados dos números naturales
regrese su suma, usar type-case para implementar esta función.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
8 / 10
Suma de naturales
I
Definir una función suma1 que dados dos números naturales
regrese su suma, usar match para implementar esta función.
I
Definir una función suma2 que dados dos números naturales
regrese su suma, usar type-case para implementar esta función.
(define (suma1 n1 n2)
(match nat1
[(cero) nat2]
[(sucesor n) (sucesor (suma n n2)]))
(define (suma2 n1 n2)
(type-case Nat n1
[cero () nat1]
[sucesor (n) (sucesor (suma n n2))]))
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
8 / 10
Multiplicación de naturales
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
9 / 10
Multiplicación de naturales
I
Definir una función producto1 que dados dos números naturales
regrese su producto, usar match para implementar esta función.
I
Definir una función producto2 que dados dos números naturales
regrese su producto, usar type-case para implementar esta
función.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
9 / 10
Multiplicación de naturales
I
Definir una función producto1 que dados dos números naturales
regrese su producto, usar match para implementar esta función.
I
Definir una función producto2 que dados dos números naturales
regrese su producto, usar type-case para implementar esta
función.
(define (producto1 n1 n2)
(match nat1
[(cero) (cero)]
[(sucesor m) (suma1 n2 (producto1 m n2)]))
(define (producto2 n1 n2)
(type-case Nat n1
[cero () (cero)]
[sucesor (m) (suma2 n2 (producto2 m n2))]))
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
9 / 10
Ejercicios
Manuel Soto Romero (UNAM)
Lenguajes de Programación
17 de febrero de 2017
10 / 10
Ejercicios
Los ejercicios se encuentran en
http://lenguajesfc.com/laboratorio.html
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
17 de febrero de 2017
10 / 10