PDF de programación - Tema 3: Programacion funcional (1/3)

1/25/2015

programacion­funcional

Tema 3: Programación funcional (1/3)

Hoy:

1.  El paradigma de programación funcional

Historia de la PF
Características fundamentales
El renacimiento de la PF

2.  Modelos de evaluación de expresiones en PF
3.  Scheme como lenguaje de PF

Funciones y formas especiales
Símbolos, quote, eval
Recursión

Objetivos

Conocer los hitos más importantes en la historia del paradigma funcional
Conocer las características más importantes del paradigma funcional
Saber diferenciar entre lenguajes y sentencias imperativas y lenguajes y sentencias
declarativas
Aplicar el modelo de computación de sustitución (en orden aplicativo y normal) para la
evaluación de expresiones
Diferenciar entre funciones y formas especiales en Scheme
Conocer y saber utilizar las formas especialies principales de Scheme
Conocer el tipo símbolo de Scheme y las funciones que trabajan con ellos
Conocer y saber utilizar la forma especial  eval  y la dualidad entre datos y programas
Comprender el uso de la recursión como forma de implementar la iteración en Scheme
y lenguajes funcionales
Comprender funciones recursivas sencillas que trabajen sobre estructuras compuestas
(listas y cadenas)

Bibliografía

SICP: Cap. 1.1.1–1.1.6, 2.3.1
PLP: Cap. 10
Concepts in Programming Languages Cap. 4.4

El paradigma de Programación Funcional

file:///C:/itl/PROG_LOGICA/programacion­funcional.htm

1/24

1/25/2015

programacion­funcional

Orígenes históricos

Cálculo lambda (Alonzo Church) en los años 30
Años 30 distintos matemáticos proponen modelos computacionales y demuestran su
equivalencia (Turing ­ Máquina de Turing, Kleen ­ Sustituciones algebráicas, …)
Modelo de cálculo lambda basado en la definición de funciones y la aplicación de estas
funciones a argumentos

Definición del paradigma funcional

En un sentido estricto, la programación funcional define un programa como una función
matemática que convierte unas entradas en unas salidas, sin ningún estado interno y
ningún efecto lateral.

La no existencia de estado interno (celdas de memoria en las que se guardan y se
modifican valores, por ejemplo) y la ausencia de efectos laterales es una característica de la
programación declarativa.

Otras características del paradigma funcional son las siguientes:

Recursión
Funciones como tipos de datos primitivos
Uso de listas

Historia del LISP

LISP es el primer lenguaje de programación de alto nivel basado en el paradigma
funcional
Creado en 1958 por John McCarthy
LISP es un lenguaje revolucionario e introduce nuevos conceptos de programación:
funciones como objetos primitivos, funciones de orden superior, polimorfismo, listas,
recursión, símbolos, homogeneidad de datos y programas, bucle “read­eval­print”
La herencia del LISP llega a lenguajes derivados de él (Scheme, Golden Common
LISP) y a nuevos lenguajes de paradigmas no estrictamente funcionales, como C#,
Python, Ruby, Objective­C o Scala

LISP no es un lenguaje estricto de programación funcional

En LISP (y Scheme) existen instrucciones que se salen del paradigma funcional puro y
permiten estado local y efectos laterales (programación imperativa)

LISP se diseñó con el objetivo de ser un lenguaje de alto nivel capaz de resolver
problemas prácticos de Inteligencia Artificial, no con la idea de ser un lenguaje formal
basado un único modelo de computación

file:///C:/itl/PROG_LOGICA/programacion­funcional.htm

2/24

1/25/2015

programacion­funcional

Con el paso de los años y el avance en los diseños de compiladores e intérpretes ha
sido posible diseñar lenguajes de programación que siguen más estrictamente las
características declarativas del paradigma funcional y que también son útiles y
prácticos para desarrollar programas en el mundo real, como Haskell, Miranda o ML

Programación declarativa

Hablamos de programación declarativa para referirnos a lenguajes de programación (o
sentencias de código) en los que se declaran los valores, objetivos o características
finales de los elementos del programa, pero no se especifican detalles de
implementación, ni de control de flujo, que se resuelven por la componente de run­time
del lenguaje.

Por ejemplo, un conjunto de reglas de Prolog son sentencias declarativas. O una
definición de una interfaz en Java.

Una característica fundamental del código declarativo es que no utiliza pasos de
ejecución, ni asignación destructiva. Define un conjunto de reglas y definiciones de
estilo matemático.

La programación declarativa no es exclusiva de los lenguajes funcionales. Existen
muchos lenguajes no funcionales que son declarativos (como el Prolog). De la misma
forma que existen lenguajes que tienen características funcionales y que no son
declarativos (como el LISP o Scheme).

En esta primera parte de la asignatura, en la que vamos a tratar el paradigma de
programación funcional, vamos a usar sólo las características declarativas de Scheme.

Programación declarativa vs. imperativa

Programación imperativa: pasos de ejecución y estado de variables:

int x = x + 1;
int y = y + 3;

Programación declarativa:

(define (cuadrado x)
       (* x x))

En programación declarativa no existe el estado local mutable. En programación
imperativa esto no es así. Por ejemplo, una de las características de la programación
orientada a objetos es guardar estado mutable en variables de instancia de clases.

file:///C:/itl/PROG_LOGICA/programacion­funcional.htm

3/24

1/25/2015

programacion­funcional

Por ejemplo, en Java:

public class Contador {
    int c;

    public Contador(int valorInicial) {
        c = valorInicial;
    }

    public int valor() {
        c++;
        return c;
    }
}

Contador cont = new Contador(10);
cont.valor(); // 11
cont.valor(); // 12
cont.valor(); // 13  

Cada llamada al método  valor()  modifica el estado del objeto  cont .

También se pueden definir funciones con estado local mutable en C:

int function contador () {
   static int c = 0;

   c++;
   return c;
}

contador() ;; 1
contador() ;; 2
contador() ;; 3

Transparencia referencial

El término transparencia referencial se utiliza en la teoría de la programación funcional
para indicar la siguiente propiedad que elimina los efectos laterales:

Dentro de un mismo ámbito en el que se han declarado unas variables x1, x2, …, xn
todas las ocurrencias de una misma expresión e que contiene a alguna de las
variables debe devolver el mismo valor

Por ejemplo, en el siguiente código (de un lenguaje cualquiera) se declaran dos

file:///C:/itl/PROG_LOGICA/programacion­funcional.htm

4/24

1/25/2015

programacion­funcional

variables con sus respectivos valores. La expresión  (x+y)  debe devolver siempre el
mismo valor si el código cumple la transparencia referencial.

begin
    integer x=3; integer y=4;
    5*(x+y)‐3
    ...   // ninguna declaración nueva de x o y // 
    4*(x+y)+1
end

Funciones devuelven siempre el mismo valor

Los lenguajes funcionales puros tienen la propiedad de transparencia referencial
Como consecuencia, en programación funcional, una función siempre devuelve el
mismo valor cuando se le llama con los mismos parámetros
Las funciones no modifican ningún estado, no acceden a ninguna variable ni objeto
global y modifican su valor

Diferencia entre declaración y modificación de variables

En programación funcional pura una vez declarada una variable no se puede modificar
su valor
En algunos lenguajes de programación (como Scala) este concepto se refuerza
definiendo la variable como inmutable (con la directiva  val ).
En programación imperativa es habitual modificar el valor de una variable en distintos
pasos de ejecución

Ejemplo:

1. int x = 1;
2. x = x+1;
3. int y = x+1;
4. y = x;

Líneas 1 y 3: sentencias declarativas
Líneas 2, 4: sentencias imperativas

Valores y referencias

En programación declarativa sólo existen valores, no hay referencias.

La distinción entre valores y referencias es fundamental, sin embargo, en la
programación imperativa.

file:///C:/itl/PROG_LOGICA/programacion­funcional.htm

5/24

1/25/2015

programacion­funcional

Diferencia entre valor y referencia

Cuando se realiza una asignación de un valor a una variable debemos considerar que
estamos dando un nombre a un objeto matemático que no puede ser modificado o que
estamos copiando el valor en la variable.

Por ejemplo, en Java, los tipos de datos primitivos son valores. Las asignaciones
valores de estos tipos a variables realizan copias de valores:

int a = 4;
int b = 2;
int c = b;
b = 3;

En la variable  a  se copia el valor 4 y en las variables  b  y  c  se copia el valor  2 . No
hay forma de modificar (mutar) esos valores. Podríamos cambiar las variables
guardando en ella otros valores, pero los valores propiamente dichos son inmutables.
En la última instrucción modificamos el valor de la variable  b , pero el valor de la
variable  c  sigue siendo 2.

Los tipos de datos cuyos valores son inmutables y sus asignaciones tienen una
semántica de copia reciben el nombre de tipos de valor (value types en inglés).

Los tipos de referencia son tipos de datos mutables en los que la asignación funciona
con semántica de referencia.

Por ejemplo, cualquier objeto en Java tiene una semántica de referencia. Cuando
asignamos un objeto a una variable, estamos guardando en la variable una referencia
al objeto.

Point2D p1 = new Point2D(3.0, 2.0);
Point2D p2 = p1;
p2.setCoordX(10.0);
p1.getCoordX(); // devuelve 10.0

La diferencia es fundamental, porque distintas variables pueden referenciar un mismo

file:///C:/itl/PROG_LOGICA/programacion­funcional.htm

6/24

1/25/2015

programacion­funcional

objeto y se pueden producir efectos laterales (side effects en inglés). El dato
guardado en una variable cambia después de una sentencia en la que no se ha usado
esa variable.

Asignación

En programación funcional no existe la asignación destructiva, en la que se modifica un
valor previamente asignado.

Sí que se pueden dar valor a variables o identificadores, entendiéndolo como una
definición de un valor consta