PDF de programación - Tema 5: Introducción a la programación funcional

Programación Declarativa

Curso 2004-2005
Departamento de Electrónica, Sistemas Informáticos y Automática
Universidad de Huelva

Tema 5: Introducción a la
programación funcional.

Programación Declarativa

Tema 5: Introducción a la programación funcional.

Qué es la programación Funcional (I)
•La programación funcional apareció como un
paradigma independiente a principio de los
sesenta.

•Su creación es debida a las necesidades de los
investigadores en el campo de la inteligencia
artificial y en sus campos secundarios del cálculo
simbólico, pruebas de teoremas, sistemas basados
en reglas y procesamiento del lenguaje natural.

•Estas necesidades no estaban cubiertas por los

lenguajes imperativos de la época.

Departamento de Electrónica, Sistemas Informáticos y Automática
Universidad de Huelva

Pág. 2

Curso 2004-2005

Programación Declarativa

Tema 5: Introducción a la programación funcional.

Qué es la programación Funcional (II)

• La característica principal de la programación funcional es
que los cálculos se ven como una función matemática que
hacen corresponder entradas y salidas.

• No hay noción de posición de memoria y por tanto,

necesidad de una instrucción de asignación.

• Los bucles se modelan a través de la recursividad ya que
no hay manera de incrementar o disminuir el valor de una
variable.

• Como aspecto práctico casi todos los lenguajes funcionales

soportan el concepto de variable, asignación y bucle.

• Estos elementos no forman parte del modelo funcional

“puro”.

Departamento de Electrónica, Sistemas Informáticos y Automática
Universidad de Huelva

Pág. 3

Curso 2004-2005

Programación Declarativa

Tema 5: Introducción a la programación funcional.

Qué es la programación Funcional (III)
Cualquiera que haya programado una hojade cálculo conocela

experienciade la programación funcional.

• En una hojade cálculo, se especifica cada celdaen terminosde los

valoresde otras celdas. El objetivo es que debeser calculadoy no en
como debe calcularse.

Por ejemplo:
• No especificamos el orden en el que las celdas serán calculadas,en

cambio obtenemos el orden que garantiza que la hoja de cálculo puede
calcular las celdas respetando las dependencias.

• No indicamos a la hoja de cálculo como manejar la memoria, en
cambio esperamos que nos presente un plano de celdas, aparentemente
infinito, pero que solo utiliza la memoria de las celdas que están
actualmente en uso.

• Lo más importante, especificamos el valor de una celda por una

expresión (cuyas partes pueden ser evaluadas en cualquier orden), en
vez de una secuencia de comandos que calculan los valores.

Departamento de Electrónica, Sistemas Informáticos y Automática
Universidad de Huelva

http://www.haskell.org/aboutHaskell.html

Pág. 4

Curso 2004-2005

Programación Declarativa

Tema 5: Introducción a la programación funcional.

¿Por qué Haskell?

•Haskell es un lenguaje funcional puro
•Haskell no es un lenguaje muy rápido, pero
se prioriza el tiempo del programador sobre
el tiempo de computación.

Departamento de Electrónica, Sistemas Informáticos y Automática
Universidad de Huelva

Pág. 5

Curso 2004-2005

Programación Declarativa

Tema 5: Introducción a la programación funcional.

Introducción a Haskell

• Haskell es un lenguaje de programación con tipos

polimórficos, con evaluación perezoso (lazy), y
puramente funcional, muy diferente a otros lenguajes
imperativos.

• El lenguaje toma el nombre de Haskell BrooksCurry

(1900-1982 Millis, Massachusetts, USA), cuyos trabajos
en lógica matemática sirvieron como base a los lenguajes
funcionales.

• Haskell está basado en el cálculo lambda, de aquí el

símbolo λ (lambda) que aparece en el logo.
http://www.lfcia.org/openprojects/camllets/doc/html/node11.html
http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Curry.html

Departamento de Electrónica, Sistemas Informáticos y Automática
Universidad de Huelva

Pág. 6

Curso 2004-2005

Programación Declarativa

Tema 5: Introducción a la programación funcional.

Haskell BrooksCurry

Experto en lógica simbólica, trabajó

en el primer ordenador
electrónico llamado ENIAC
(Electronic Numerical Integrator
and Computer) durante Segunda
Guerra Mundial. Trabajóen los
50 en los fundamentosde la
lógica combinatoriay los aplicó
en MitreCorporation Curry
Chip en 1986 un innovador
elementohardware basadoen los
conceptosde combinatoriade
Curry.

http://www.research.psu.edu/history/history3.shtml

Departamento de Electrónica, Sistemas Informáticos y Automática
Universidad de Huelva

Pág. 7

Curso 2004-2005

Programación Declarativa

Tema 5: Introducción a la programación funcional.

Función matemática

En Matemáticas, una función f entre dos conjuntos A y B,
llamados conjuntos inicial y final, es una correspondencia que a
cada elemento de un subconjunto de A, llamado “Dominio de f”, le
hace corresponder uno y sólo uno de un subconjunto B llamado
“Imagen de f”.

f: A B
f(x) ....

Ejemplo:
sucesor: Z Z
sucesor(x) x + 1
Departamento de Electrónica, Sistemas Informáticos y Automática
Universidad de Huelva

pi: R
pi 3.141592

Las constantes son
funciones que no tienen
parámetros y devuelven
siempre lo mismo

Pág. 8

Curso 2004-2005

Programación Declarativa

Tema 5: Introducción a la programación funcional.

Sesiones y declaraciones

Desde el punto de vista de la programación funcional, el
ordenador actúa como una calculadora, o evaluador, que calcula
el resultado de las expresiones que introducimos
•El programador dispone de un conjunto de valores, funciones y
operadores predefinidos, cuyo significado lo conoce ya el
evaluador

Prelude> 1 + 3
4 :: Integer
Escribiremos “:set+t” para que Haskell muestre el tipo de dato

Departamento de Electrónica, Sistemas Informáticos y Automática
Universidad de Huelva

Pág. 9

Curso 2004-2005

Programación Declarativa

Tema 5: Introducción a la programación funcional.

Sesiones y declaraciones (II)

Las líneas anteriores representan “una sesión” o un
diálogo con el evaluador.
Le pedimos a Haskell que calculase el valor de la
expresión “1 + 3” y éste respondió “4 :: Integer”
También podemos definir funciones con una sintaxis
muy cercana a la matemática, de ahí la facilidad a la
hora de escribir programas, ya que serán meras
implementaciones de las funciones matemáticas.

Departamento de Electrónica, Sistemas Informáticos y Automática
Universidad de Huelva

Pág. 10

Curso 2004-2005

Programación Declarativa

Tema 5: Introducción a la programación funcional.

Tipos de datos

En Haskell se puede trabajar con diferentes tipos de datos. Cada
valor tiene un tipo y hay tipos que están predefinidos, como los
enteros, los reales, etc...
Prelude> cos(-2*pi)
1.0 ::Double

Existen otros tipos de datos más complejos

Prelude> [1..5]
[1,2,3,4,5] :: [Integer]
Prelude>sum[1..5]
15 :: Integer

Departamento de Electrónica, Sistemas Informáticos y Automática
Universidad de Huelva

Pág. 11

Curso 2004-2005

Programación Declarativa

Tema 5: Introducción a la programación funcional.

Currificación

Las funciones con más de un argumento se pueden interpretar
como funciones que toman un único argumento y devuelven como
resultado otra función con un argumento menos.
Este mecanismo que permite representar funciones de varios
argumentos mediante funciones de un argumento se denomina
“CURRIFICACIÓN” (debido a Haskell B. Curry)
La mayoría de los lenguajes funcionales están basados en el

λ-cálculo

Departamento de Electrónica, Sistemas Informáticos y Automática
Universidad de Huelva

Pág. 12

Curso 2004-2005

Programación Declarativa

Tema 5: Introducción a la programación funcional.

λ-Cálculo
Fue concebido originalmente por el lógico-matemático Alonzo
Church en los años 30 como parte de una teoría general para
modelar funciones y lógica de orden superior.
Haskell es un lenguaje descrito como un λ-Cálculo extendido

Definición: Dado un conjunto(infinito numerable) de variables V
y un conjunto C de constantes, el conjunto Λ de los términos del
λC queda definido por la sintaxis

Λ ::= V | C | (λV.Λ) | (Λ Λ)

Donde λx.M representa la función xM
Departamento de Electrónica, Sistemas Informáticos y Automática
Universidad de Huelva

Pág. 13

Curso 2004-2005

Programación Declarativa

Para la función

f: A B
x 2x + 1

Tema 5: Introducción a la programación funcional.

Podemos escribirla como una λ-expresión de la forma

λx.2x+1

Ejemplo:

f(x,y) = (x + y)*2
λx λy (x + y) * 2

Se expresaría en λCalculo como
λx. λy. * (+ x y) 2

Departamento de Electrónica, Sistemas Informáticos y Automática
Universidad de Huelva

Pág. 14

Curso 2004-2005

Programación Declarativa

Tema 5: Introducción a la programación funcional.

Particularidades:

•El ámbito de x en la expresión λx.E se extiende a la derecha
tanto como sea posible, hasta el primer paréntesis no cerrado o
hasta el final de la expresión.
• λx1x2...xn.M ≡ λx1.(λx2.(... (λxn.M)...))

Esto es muy importante, ya que nos permite descomponer

cualquier función multi-variable como composición de
funciones de una única variable
•La aplicación es asociativa por la izquierda
M N1 N2....Nn ≡ (...((M N1) N2)... Nn))

Departamento de Electrónica, Sistemas Informáticos y Automática
Universidad de Huelva

Pág. 15

Curso 2004-2005

Programación Declarativa

Tema 5: Introducción a la programación funcional.

Declaración de una función ejemplo

Vamos a definir nuestra primera función en Haskell, que calcule

El sucesor de un numero entero

sucesor :: Integer Integer
sucesor x = x + 1

“sucesor” es el nombre de la función
•La primera línea es una declaración de tipos e indica que sucesor
es una función de enteros en enteros
•La segunda línea es una ecuación, y proporciona la forma de
cálculo del valor de esa función.

Departamento de Electrónica, Sistemas Informáticos y Automática
Universidad de