Download Bases de la Programación Funcional

UNIDAD IV
Programación Funcional
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
?
é
u
q
r
o
P
2
Introducción
Porque aprender programación funcional?
- Recursión
- Abstracción funcional
- Funciones de primer orden
Estos conceptos se han incorporado en la mayoría de los
lenguajes de programación y deben formar parte del conjunto
de técnicas que todo programador profesional.
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Introducción
Un lenguaje de programación funcional
tienen una gran flexibilidad, es conciso en su
notación y su semántica es sencilla.
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Introducción
Posee varias ventajas respecto a la
programación imperativa, y se utiliza en
prototipado,
inteligencia
artificial,
sistemas de comprobación matemática
y programación lógica.
Los programas se definen como
funciones, y al tratar a las mismas como
datos limita los efectos colaterales y el
uso de administración de memoria.
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
El inconveniente principal es la ineficiencia de la ejecución
de los lenguajes funcionales ya que debido a su naturaleza
dinámica el código es interpretado mas que compilado,
resultando esto una perdida sustancial de velocidad.
En los últimos años la aparición
de nuevas tecnologías ayudo a
atenuar esta situación.Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Pueden los lenguajes funcionales competir con los lenguajes
imperativos u OO?
- Nunca fueron lenguajes de “primer importancia”
- Programadores aprenden sobre lenguajes imperativos
- Los lenguajes OO se construyen sobre conceptos imperativos
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Introducción
Veremos:
- Concepto matemático de función
- Bases de la Programación Funcional
- Características
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Concepto matemático de función
Una función establece una asociación entre valores de
entrada y valores de salida.
Ejemplo:
Función doble: 2 → 4
5 → 10
Función capital: Argentina → Bs. As
España → Madrid
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Concepto matemático de función
Una Función es una regla de correspondencia en la que a
un elemento del conjunto Dominio le corresponde un único
elemento del conjunto Imagen.
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Concepto matemático de función
Función doble
Dominio: Enteros
Imagen: Enteros
Función capital
Dominio: Paises
Imagen: Ciudades
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Concepto matemático de función
Aplicación de una función: es la particularización de la
regla de correspondencia en la que a un valor del Dominio le
corresponde un valor concreto de la Imagen.
Esto se representa con la notación: f(x)=y
f: nombre de la función
x: argumento
y: resultado
doble(5) = 10
capital(Argentina) = Bs.As.
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Concepto matemático de función
Existen funciones conocidas y con notación universal que
comunmente son representadas por un operador.
Ejemplo: Suma, Resta, etc. (Notación empírica)
Composición de funciones: el argumento de una
función puede provenir del resultado de otra función o de la
misma.
Ejemplo:
doble(doble(5)) = 20
doble(mayor(3,5))= 10
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Concepto matemático de función
Definición de Funciones:
Comprensión: ecuación cuya parte izquierda la componen los
argumentos (entrada) y la parte derecha la representa la expresión
algebraica de las operaciones que componen la función.
Ejemplo: funcion doble x = 2 * x
Extensión: conjunto de pares ordenados donde el primer elemento
es un valor del conjunto dominio y el segundo del conjunto imagen
Ejemplo: función capital
Argentina = Bs.As.
España = Madrid
...
Italia
Roma
Lic. Jesús Germán Andrés
PAUTSCH - =
FCEQyN
- UNaM
Introducción
- Concepto matemático de función
- Bases de la Programación Funcional
- Características
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Bases de la Programación Funcional
También llamada Declarativa con el paradigma lógico de
programación.
Busca describir los problemas como funciones matemáticas
puras sin efectos “laterales”.
Detalla lo que hay que calcular y no detallan como.(contrario a
los programas imperativos)
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Bases de la Programación Funcional
Como ya mencionamos se asimila al uso de una hoja de
cálculo o una calculadora. El usuario ingresa una expresión y el
sistema la evalúa mediante un proceso de reducción.
Se caracteriza por poseer Transparencia Referencial: el
resultado devuelto por una función sólo depende de los
argumentos que se le pasan a la llamada.
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Bases de la Programación Funcional
PROGRAM ConEfectoLateral;
VAR estado: boolean;
FUNCTION Efectos (n: integer): integer;
BEGIN
IF (estado) THEN
Efectos:= n
ELSE
Efectos:= 2*n+1;
estado:= NOT estado;
END;
BEGIN
estado = TRUE;
WriteLn(Efectos(1), ' ', Efectos(1));
WriteLn(Efectos(2), ' ', Efectos(2));
END;
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Bases de la Programación Funcional
PROGRAM ConEfectoLateral;
VAR estado: boolean;
FUNCTION Efectos (n: integer): integer;
BEGIN
IF (estado) THEN
Efectos:= n
ELSE
Efectos:= 2*n+1;
estado:= NOT estado;
END;
BEGIN
estado = TRUE;
WriteLn(Efectos(1), ' ', Efectos(1));
WriteLn(Efectos(2), ' ', Efectos(2));
END;
Llamada a la funcion con los mismos
argumentos
produce resultados distintos.
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Bases de la Programación Funcional
x=x+1
x = <expresion>
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Bases de la Programación Funcional
En los programas funcionales tampoco hay que manejar
punteros de memoria, y por lo tanto, no existe la necesidad
de instrucciones de asignación:
- el programador no gestiona la memoria
- no existe concepto de puntero de memoria
- x = <expresión>
Esto último no es una asignación. x es, por definición,
igual a <expresión>. x siempre podrá sustituirse por su
definición en cualquier lugar, ya que no habrá efectos
laterales.
- Resulta obvio que en un mismo programa no puede
aparecer otra definición de x
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Bases de la Programación Funcional
Estructuras de control en los programas funcionales:
1) composición funcional
2) construccion condicional
3) recursividad
A travez de esta ultima se modelan los bucles, ya que no
hay manera de incrementar o decrementar el valor de una
variable.
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Introducción
Veremos:
- Concepto matemático de función
- Bases de la Programación Funcional
- Características
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Características
- Funciones de orden superior
- Tipado fuerte y estático
- Inferencia de tipos
- Polimorfismo
- Orden de evaluación normal y perezosa
- Tipos de datos definidos por el usuario
- Ajuste de patrones
- Listas por comprensión
Estas ultimas 3 las veremos mas adelante con hashkell
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Características
Funciones de orden superior:
Aquí las funciones son tratadas como valores de primera
clase. Por lo que pueden ser almacenadas en estructuras de
datos, pasadas como parámetros y devueltas como
resultado. Esto proporsiona un alto nivel de abtracción.
Ejemplo: doble(mayor(7,3))=14
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Características
Tipado estático:
Los errores se detectan en tiempo de compilación
Fuertemente tipado: Ejemplo Hashkell "/" no tolera divisores
de tipo integer
No hay obligación de declarar el tipo de datos de las
expresiones, el compilador infiere el tipo.
Si se declara el tipo el compilador lo verifica
Ejemplo:
saludo(x) = IF x THEN "adios" ELSE "hola"
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Características
Polimorfismo:
Aumenta la reusabilidad. El tipo de una función depende
de un parámetro.
Ejemplo funcion longuitud.
No hay necesidad de conocer los tipos de la lista sino solo
“recorrer” y devolver la cantidad de elementos.
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Características
Orden de evaluación:
Aplicativo: se reducen las expresiones mas internas antes
que las externas (de izquierda a derecha). Programación
tradicional(imperativa).
Normal: se reducen las expresiones mas externas antes que
las internas (de izquierda a derecha). Programación
funcional.
Perezosa: las expresiones solo se evaluan en el momentos
que se las necesita.
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Características
Que sucede en este código?
Ejemplo:
g(x:integer): integer
begin
/////"bucle sin fin"
while true do x:=x;
end;
****Programa Principal****
BEGIN
Write (f(4,g(5));
END
f(x,y:integer): integer
begin
f:=x+3;
end;
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM
Características
Ejemplo:
g(x:integer): integer
begin
/////"bucle sin fin"
while true do x:=x;
end;
****Programa Principal****
BEGIN
Write (f(4,g(5));
END
f(x,y:integer): integer
begin
f:=x+3;
end;
Evaluación tradicional provoca un bucle sin fin.
Con evaluación perezosa el resultado es 7 dato que la
funcion solo se sustituye por su definición
Lic. Jesús Germán Andrés PAUTSCH - FCEQyN
- UNaM