PDF de programación - La Programación Funcional: Un Poderoso Paradigma

Paradigmas de Programación

4. Paradigma Funcional

Departamento de Informática

Universidad de Valladolid

Curso 2010-11

Grado en Ingeniería Informática

Grado en Ingeniería Informática de Sistemas

11 Feb. 2011

César Vaca Rodríguez, Dpto. de Informática, UVa

1

CONCEPTOS

FUNDAMENTALES

9 Feb. 2011

César Vaca Rodríguez, Dpto.Informática, UVa

2

Paradigma Funcional (puro)

 No existe operación de asignación.

 Las “variables” almacenan definiciones o

referencias a expresiones.

 Basado en el concepto (matemático) de función.

 La operación fundamental es la aplicación de una
función a una serie de argumentos. La evaluación
se guia por el concepto de sustitución.

 Un programa consiste en una serie de definiciones

(de funciones, de tipos de datos..)

 Las estructuras de control básicas (y generalmente

únicas) son la composición y la recursión.

11 Feb. 2011

César Vaca Rodríguez, Dpto. de Informática, UVa

3

Objetivos:

 Referential Transparency : Las funciones no tienen

efectos laterales: Su resultado está determinado
únicamente por los valores de sus parámetros.

 No modifican sus parámetros

 No acceden ni modifican variables o estado globales

 Con ello se consigue una mayor grado de

modularidad en independencia.

 El análisis de la corrección de un programa es más

sencillo (y puede usar técnicas más potentes).

 Se puede implementar concurrencia de manera

más natural (incluso automatizar su aplicación)

11 Feb. 2011

César Vaca Rodríguez, Dpto. de Informática, UVa

4

Problemas:

 Interacción con el mundo exterior: Al realizar

acciones de I/O (entrada/salida) es inevitable el
producir efectos laterales.

 Eficiencia: Si no se pueden modificar datos es

necesario crear duplicados que incorporen la
modificación.

 Complejidad de programación: Si no existe un
estado externo, se debe enviar a cada función
todos los datos necesarios.

 Sistema de tipado: Es dificil imaginar cómo

incorporar un sistema de tipado estricto y/o O.O. a
un enfoque funcional.

11 Feb. 2011

César Vaca Rodríguez, Dpto. de Informática, UVa

5

Funciones

 En los lenguajes funcionales, las funciones son
entidades de primer orden (high-order), con un
estatus similar al de los valores:
 Pueden pasarse como parámetros a otras funciones

 Pueden ser devueltas por funciones

 Pueden combinarse (composición, aplicación parcial, ..)

con otras funciones para definir otras nuevas.

 Tienen un tipo de datos asociado.

 Funciones y valores en Haskell:

 Las funciones en Haskell están currificadas (una entrada,

una salida)

 Los valores se obtienen mediante constructores de datos,

que pueden verse como funciones sin entrada.

 ¡Todo es una función en Haskell!

11 Feb. 2011

César Vaca Rodríguez, Dpto. de Informática, UVa

6

El problema del mundo externo

 En un modelo funcional puro, las funciones no

pueden tener efectos laterales:
 La salida sólo puede depender de la entrada.

 No se pueden modificar entidades (sólo crear otras

nuevas y darlas como resultado)

 Una función sin parámetros debe devolver siempre el

mismo resultado (es igual a una constante).

 No tiene sentido una función sin resultado.

 Esto provoca problemas conceptuales:

 ¿Cómo definir un generador de números aleatorios?

 ¿Cómo definir una función que devuelva la fecha/hora?

 ¿Cómo definir una función que escriba en pantalla?

 ¿Cómo definir una función que lea un dato del usuario?

11 Feb. 2011

César Vaca Rodríguez, Dpto. de Informática, UVa

7

Posibles soluciones

 Abandonar la pureza: Permitir que exista un subconjunto

de funciones que tengan efectos laterales (Lisp, Scheme)

 Introducir el mundo exterior como entidad:
 random(generador) : { generador’ , valor aleatorio }

 getClockTime(mundo) : fecha/hora

 putStrLn(mundo , cadena) : mundo’

 getLine(mundo) : { mundo’ , cadena }

 Problemas de este enfoque: Mundos paralelos

mundo2 = putStrLn(mundo1,”Hola”)

mundo3 = putStrLn(mundo2,”Mundo”)

mundo4 = putStrLn(mundo2,”Pascual”)

11 Feb. 2011

César Vaca Rodríguez, Dpto. de Informática, UVa

8

Solución de Haskell: Mónadas

 Mónadas: Concepto de teoría de tipos (categorías).

Permite encapsular las acciones impuras de manera que
las funciones que las realicen sigan presentando una
interfaz pura (sin efectos laterales) al exterior.

 La mónada IO (IO α en Haskell) representa una

acción que, al ser evaluada, genera un efecto en
el mundo exterior.
 putStrLn :: String → IO () : Devuelve una acción, que
al ser evaluda genera el efecto de mostrar una cadena
por pantalla

 getLine :: IO String : Devuelve una acción (siempre la

misma): La acción de pedir una cadena de texto al
usuario. El valor introducido se encapsula dentro de la
mónada que representa la acción.

11 Feb. 2011

César Vaca Rodríguez, Dpto. de Informática, UVa

9

¿Problemas de Eficiencia?

 En los lenguajes funcionales los valores son

inmutables. Por ejemplo, al añadir un elemento a una lista, el
resultado es otra lista (con los mismos elementos más el nuevo)
distinta a la original (que no sufre cambios).

 Consecuencia de la transparencia referencial (no

existen efectos laterales ni modificaciones)

 Parece evidente que esto tiene serias conse-

cuencias respecto a la eficiencia (en este caso
referente al espacio). Si insertamos n elementos en una
lista, acabamos con n listas distintas ocupando un espacio total de
n2 / 2 elementos.

 No existen estructuras equivalentes a los arrays

(acceso directo en tiempo constante).

11 Feb. 2011

César Vaca Rodríguez, Dpto. de Informática, UVa

10

Si, pero no tan graves

 En general (y para problemas normales) los
lenguajes funcionales son menos eficientes.

 Pero no de una forma tan drástica:

 Las estructuras son enlazadas, y siempre se almacenan

referencias a valores, no los propios valores.

 Al ser inmutables, varias estructuras pueden compartir

referencias a elementos o trozos enteros de otras.

 Al no almacenar estado, si una estructura no va a ser

usada en cálculos subsiguientes, se puede reciclar (su
espacio se libera inmediatamente)

 Suelen existir mecanismos (aunque bastante sofisticados)

para simular el equivalente de los arrays (la mónada de
estado en Haskell)

11 Feb. 2011

César Vaca Rodríguez, Dpto. de Informática, UVa

11

Ejemplo: Inserción en lista

 Supongamos la función insertar al principio que recibe

un elemento y una lista y devuelve otra lista con el
elemento añadido al principio:

ins("d",["a","a","b"])

d

a

b

11 Feb. 2011

César Vaca Rodríguez, Dpto. de Informática, UVa

12

Ejemplo: Inserción en lista

 Supongamos la función insertar al principio que recibe

un elemento y una lista y devuelve otra lista con el
elemento añadido al principio:

ins("d",["a","a","b"])  ["d","a","a","b"]

d

a

b

11 Feb. 2011

César Vaca Rodríguez, Dpto. de Informática, UVa

13

ELEMENTOS

BÁSICOS DE HASKELL

9 Feb. 2011

César Vaca Rodríguez, Dpto.Informática, UVa

14

Lenguaje Haskell

 Síntesis diseñada por expertos de la familia ML de

lenguajes de programación (1990)

 Muy influyente (C#, Python, Scala, Ruby, ...)

 Es un lenguaje funcional puro.

 Tipado Algebraico con inferencia de tipos.

 Tipado estricto y seguro.

 Funciones currificadas.

 Concordancia de Patrones.

 Evaluación perezosa/diferida.

 Listas infinitas.

 I/O y estilo pseudo-imperativo mediante Mónadas.

11 Feb. 2011

César Vaca Rodríguez, Dpto. de Informática, UVa

15

Entorno Haskell

 www.haskell.org (GHCi, Hughs, ..)

 Se puede elegir entre modo interpretado y modo

compilado.

 El modo interpretado trabaja dentro de una

mónada I/O

 Contenido típico de un programa Haskell:

 Definiciones de tipos de datos

 Definiciones de funciones con su signatura de tipo

 Una función tiene el papel de punto inicial de ejecución (si

se requiere interactividad se usa mónadas I/O)

 Esa función se invoca desde el intérprete.

11 Feb. 2011

César Vaca Rodríguez, Dpto. de Informática, UVa

16

Estructura de un programa (I)

module Main where

main :: IO()
main = do

putStr "Introduzca valor = "
v <- readLn :: IO Integer
putStrLn (show (fact v))

-- Función factorial
fact :: Integer -> Integer
fact n = if n <= 1 then 1 else n * fact (n-1)

Función principal
(Síntaxis de mónada)

Definición de
funciones

-- Definición de nuevos tipos
data Pila a = PilaVac | MkPila a (Pila a)

Nuevos tipos de
datos

-- Declaración de instancias de clase
instance (Show a) => Show (Pila a) where

show PilaVac = ""
show MkPila x p = show x ++ "," ++ show p

-- Función insertar en pila
insPila :: Pila a -> a -> Pila a
insPila p x = MkPila x p

Instancia de clase

Definición de
funciones

11 Feb. 2011

César Vaca Rodríguez, Dpto. de Informática, UVa

17

Estructura de un programa (II)

module Main where

main :: IO()
main = do

putStr "Introduzca valor = "
v <- readLn :: IO Integer
putStrLn (show (fact v))

-- Función factorial
fact :: Integer -> Integer
fact n = if n <= 1 then 1 else n * fact (n-1)

-- Definición de nuevos tipos
data Pila a = PilaVac | MkPila a (Pila a)

-- Declaración de instancias de clase
instance (Show a) => Show (Pila a) where

show PilaVac
show MkPila x p = show x ++ "," ++ show p

= ""

-- Función insertar en pila
insPila :: Pila a -> a -> Pila a
insPila p x = MkPila x p

Declaración

de tipo

Definición
de función

Constructores de

valores

Restricciones

de tipos

Concordancia

de patrones

Genericidad

11 Feb. 2011

César Vaca Rodríguez, Dpto. de Informática, UVa

18

Valores, Tipos predefinidos

 Haskell tiene los tipos simples tradicionales:

 tipo Int  Números enteros
 tipo Integer  Enteros de tamaño arbitrario
 tipo Double  Números reales
 tipo Char  Caracteres (entre comillas simples: 'a', '/n')
 tipo Bool  Valores lógicos (literales True y False)

 Tipos compuestos:

 tipo [a]  Listas que contienen elementos de tipo a (todos

los elementos deben ser del mismo tipo). Ejemplos de lis