Download Programación Funcional
Document related concepts
no text concepts found
Transcript
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