Download Programación Funcional

Programación Funcional
Alberto Pardo
Marcos Viera
Instituto de Computación, Facultad de Ingenierı́a
Universidad de la República, Uruguay
Alberto Pardo, Marcos Viera
Programación Funcional
Objetivo del curso
Este es un curso introductorio de programación funcional (PF)
Veremos conceptos y técnicas de programación relativas a
este paradigma
Nos vamos a focalizar en un abordaje especı́fico a PF que
corresponde a lenguajes fuertemente tipados y con
evaluación perezosa (lazy evaluation)
Programaremos en el lenguaje Haskell
Alberto Pardo, Marcos Viera
Programación Funcional
Material del curso
Las transparencias de cada tema ası́ como los prácticos van a
estar disponibles en la plataforma EVA.
Bibliografı́a Nos basaremos en el siguiente libro:
Haskell: The craft of functional programming
Simon Thompson
Third Edition
Pearson Education Limited
2011
A lo largo del curso se va a ir indicando que partes del libro se
van tratando.
Alberto Pardo, Marcos Viera
Programación Funcional
Modalidad del curso
Este es un curso presencial por lo que se recomienda ir a clase.
En caso de no poder, el material se va a ir dejando en la
plataforma EVA.
Se recomienda seguir los temas a través de la lectura de las
transparencias y el libro.
Alberto Pardo, Marcos Viera
Programación Funcional
Evaluación
Una tarea de programación en las últimas semanas del curso.
Puede ser realizada en grupos de hasta 2 estudiantes.
Una prueba al final del curso. Se incluye todo lo visto en las
clases y prácticos.
Alberto Pardo, Marcos Viera
Programación Funcional
Haskell
Haskell (http://www.haskell.org) es un lenguaje
puramente funcional con evaluación perezosa, fuertemente
tipado, de tipado estático e inferencia de tipos.
Fue definido en 1990 por un comité internacional con el fin de
establecer un estandar.
Debe su nombre al del lógico Haskell B. Curry.
Usaremos el compilador GHC (Glasgow Haskell Compiler) y su
intérprete GHCi (https://www.haskell.org/ghc)
Recomendamos instalarse Haskell Platform
(https://www.haskell.org/platform) que trae GHC
junto a una serie de paquetes.
Alberto Pardo, Marcos Viera
Programación Funcional
Caracterı́sticas de la Programación Funcional
PF es un paradigma de programación de la misma forma que
lo son la programación imperativa, la programación orientada
a objetos, o la programación lógica.
Los lenguajes funcionales poseen poderosos mecanismos de
abstracción y modularización, como por ejemplo:
polimorfismo paramétrico, funciones de alto orden, etc.
Gracias al alto nivel de abstracción y a una sintaxis minimal
(como sucede en Haskell), los programas funcionales suelen
ser mas concisos que en otros lenguajes.
Alberto Pardo, Marcos Viera
Programación Funcional
Definición de funciones
Un programa en PF consiste de una lista de definiciones (de
funciones) que se expresan en una notación semejante a la
usada en matemática.
Las definiciones son escritas como ecuaciones, eventualmente
acompañadas de una descripción de su tipo.
Ejemplo:
square :: Integer → Integer
square x = x ∗ x
min
:: (Integer , Integer ) → Integer
min (x, y ) = if x 6 y then x else y
Alberto Pardo, Marcos Viera
Programación Funcional
Evaluación de expresiones
Computar un resultado se hace a través de la evaluación de
expresiones, que pueden contener llamadas a
las funciones definidas en el programa, o
funciones definidas en el ambiente (por ej., Haskell Prelude)
En la evaluación las definiciones de funciones actúan como
reglas de reducción que permiten simplificar las expresiones.
Por ejemplo, evaluemos
square (3 + 4)
Alberto Pardo, Marcos Viera
Programación Funcional
Evaluación de expresiones (2)
Una forma de evaluarla:
square (3 + 4)
= {def +}
square 7
= {def square }
7∗7
= {def ∗}
49
Alberto Pardo, Marcos Viera
Programación Funcional
Evaluación de expresiones (3)
Otra forma:
square (3 + 4)
= {def square }
(3 + 4) ∗ (3 + 4)
= {def +}
7 ∗ (3 + 4)
= {def +}
7∗7
= {def ∗}
49
La expresión 49 se dice que está en forma normal o canónica
debido a que no puede ser mas reducida.
Alberto Pardo, Marcos Viera
Programación Funcional
Ausencia de efectos colaterales
Propiedad: Para toda expresión e, cualquiera dos secuencias de
reducción diferentes de e que terminen lo van a hacer en el mismo
valor v .
Esta es una propiedad muy relevante que caracteriza a la PF y
la diferencia de otros paradigmas. Se debe en parte a la
ausencia de efectos colaterales, en particular, a la inexistencia
de una sentencia de asignación.
Dicha propiedad no es válida en la mayorı́a de los lenguajes
imperativos, en los que el método de cómputo se basa en
cambiar los valores almacenados en memoria. El orden de
ejecución de las sentencias es entonces crucial.
Por ejemplo, en un lenguaje imperativo la expresión
n + (n := 1) va a retornar distintos valores dependiendo de si se
evalúa primero el sumando de la izquierda o el de la derecha.
Alberto Pardo, Marcos Viera
Programación Funcional
Ausencia de efectos colaterales (2)
La ausencia de efectos colaterales hace que en PF las
variables se comporten como en la matemática: cada nombre
está asociado/ligado a un único valor.
En PF las variables denotan valores a diferencia de lo que
ocurre en los lenguajes imperativos en que las variables
denotan direcciones de memoria cuyo contenido puede ser
modificado.
Al igual que en la matemática, el valor retornado por una
función sólo depende de los valores dados como entrada. No
hay variables globales que puedan modificar el
comportamiento de una función.
La ausencia de efectos facilita el razonamiento sobre los
programas funcionales, por ejemplo, para probar formalmente
propiedades de los mismos.
Alberto Pardo, Marcos Viera
Programación Funcional
Diseño composicional
En PF es muy común construir nuevas funciones a partir de
funciones mas sencillas previamente definidas.
Ejemplo:
quad :: Integer → Integer
quad x = double (double x)
double
:: Integer → Integer
double x = 2 ∗ x
El patrón de aplicar una función y luego aplicar otra al
resultado es muy usual en PF y amerita la definición de un
operador especı́fico, llamado de composición de funciones:
(f . g ) x = f (g x)
De esta manera podemos escribir quad como:
quad = double . double
Que tipo tiene el operador de composición de funciones?
Alberto Pardo, Marcos Viera
Programación Funcional
Diseño composicional (2)
El patrón de definición de quad da para jugar un poco mas.
Podemos abstraer la situación de que double está compuesta
consigo misma e introducir una nueva definición:
twice f = f . f
Por lo tanto,
quad = twice double
Cual es el tipo de twice?
Alberto Pardo, Marcos Viera
Programación Funcional
Próxima clase
Tipos Básicos.
Leer Capı́tulos 1 al 3 del libro.
Alberto Pardo, Marcos Viera
Programación Funcional