Filosofía del paradigma¶

Es un paradigma de programación declarativa basado en el uso de funciones matemáticas, en contraste con la programación imperativa, que enfatiza los cambios de estado mediante la mutación de variables. La programación funcional tiene sus raíces en el cálculo lambda, un sistema formal desarrollado en los años 1930 para investigar la definición de función, la aplicación de las funciones y la recursión. Muchos lenguajes de programación funcionales pueden ser vistos como elaboraciones del cálculo lambda.

En la práctica, la diferencia entre una función matemática y la noción de una "función" utilizada en la programación imperativa, es que las funciones imperativas pueden tener efectos secundarios, como cambiar el valor de cálculos realizados previamente. Por esta razón carecen de transparencia referencial, es decir, la misma expresión sintáctica puede resultar en valores diferentes en varios momentos de la ejecución del programa. Con código funcional, en contraste, el valor generado por una función depende exclusivamente de los argumentos alimentados a la función. Al eliminar los efectos secundarios se puede entender y predecir el comportamiento de un programa mucho más fácilmente. Ésta es una de las principales motivaciones para utilizar la programación funcional.

Los lenguajes de programación funcional, especialmente los puramente funcionales, han sido enfatizados en el ambiente académico y no

tanto en el desarrollo comercial o industrial. Sin embargo, lenguajes de programación funcional como Scheme, Erlang, Rust, Objective Caml , Scala, F# y Haskell, han sido utilizados en aplicaciones comerciales e industriales por muchas organizaciones.

Cálculo Lambda¶

Es el más pequeño lenguaje universal de programación, consiste en en una regla de transformación simple (sustituir variables) y un esquema simple para definir funciones.

El cálculo lambda se puede decir que es equivalente a las máquinas Turing porque es capaz de evaluar y expresar cualquier función computable. Originalmente, Church había tratado de construir un sistema formal completo para modelar la Matemática; pero cuando éste se volvió susceptible a la paradoja de Russell, separó del sistema al cálculo lambda y lo usó para estudiar la computabilidad, culminando en la respuesta negativa al problema de la parada.

Considérese las siguientes dos funciones. Por un lado, la función identidad I(x) = x, que toma un único argumento, x, e inmediatamente devuelve x. Por otro lado, la función suma S(x,y) = x + y, que toma dos argumentos, x e y, y devuelve la suma de ambos: x + y, usando estas dos funciones como ejemplo podemos decir:

• Las funciones no necesitan ser explícitamente nombradas. Esto es, la función S(x,y) = x + y puede ser reescrita como una función anónima: x,y → x + y (que se lee: «el par de x e y se mapea a x + y»). Del mismo modo, I(x) = x puede ser reescrita de forma anónima como x → x, que se lee: «el argumento x se mapea a sí mismo».

• El nombre que se asigne a los argumentos de la función es generalmente irrelevante. Esto es, x → x e y → y expresan la misma función: la función identidad. Del mismo modo, x,y → x + y y u,v → u + v expresan la misma función: la función suma, por ejemplo, al tomar los números 2 y 3 como argumentos, se obtiene:

2 , 3 → x + y

2 + 3

5

Notación-λ¶

• Variable: <exp-λ> ::= <variable>
• Función: <exp-λ> ::= λ<variable> . <exp-λ>
• Aplicación de función: <exp-λ> ::= <exp-λ><exp-λ>

Por ejemplo, la función identidad antes vista como x → x se escribiría λx.x mediante la notación lambda, y la función suma currificada x → (y → x + y) sería λx.(λy.x+y).

Asociatividad¶

La asociatividad de funciones es por izquierda, esto se puede ver más claro mediante un ejemplo: Consideremos la expresión lambda (λx.x + 1) (λz.z) 3 , al escribir los paréntesis necesarios para mostrar el orden de las operaciones, la expresión quedaría de la siguiente forma:

( (λx.x + 1)(λz.z) ) 3 , la cual se operaría:

(λz.z + 1) 3

3 + 1

Características¶

Efectos secundarios¶

Están referidos a los estados en los que puede estar el código mientras se ejecuta, una de las características ya mencionadas de la programación funcional es que es de tipo declarativo, por lo que no existe la variación de estados, estos efectos secundarios pueden referirse a:

• Cambiar el valor de cálculos realizados previamente.
• Entrada - salida de datos estándar o por archivo.
• Modificar uno de los argumentos de la función.

Al no existir efectos secundarios, podemos decir con total certeza que dada una misma entrada, el programa siempre retornara la misma salida, no importa cuantas veces se ejecute.

Ejemplos¶

* Loops

Los loops generan "side effects" debido a que se está cambiando el valor de una variable para iterar y comparar, generando cambios de valor y por lo tanto cambiando la salida de una función o rutina.

for(int i=0; i<100; i++){}

* Variables aleatorias

Las variables generadas aleatoriamente generan side effects, ya que las funciones evaluadas con un número aleatorio no retornaran el mismo resultado ejecutadas dos veces.

int sumaAleatoria(int a){
    return (int)(Math.random()) + a;
}

Sí ejecutamos el código previo, al ejecutarlo dos veces no se garantiza que retorne el mismo resultado.

* Entrada de datos por consola en ejecución

Los argumentos de entrada de un programa en programación funcional se asignan sólo al principio de este (argumentos), en ejecución está prohibida la asignación de variables, ya que no garantizan que el código ejecutado dos veces sea exactamente igual.

public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    System.out.println(args[0] + sc.nextString());
}

Currificación¶

Toda función que requiere más de un argumento, como por ejemplo la función suma, puede ser reescrita como una función que acepta un único argumento, pero que devuelve una serie de funciones, las cuales a su vez aceptan un único argumento. Por ejemplo, x,y → x + y puede ser reescrita como x → (y → x + y), a esta transformación se conoce como currificación. Considérese la versión currificada de la función suma:

x → (y → x + y)

Si se toma al número 2 como argumento, se obtiene la función:

y → 2 + y

Y tomando luego al número 3 como argumento, se obtiene:

2 + 3 = 5

Recursión¶

En los lenguajes funcionales no existen los ciclos, así que muchas veces hay que reemplazarlos con funciones recursivas. A continuación un ejemplo de la misma función implementada con un ciclo for y con recursión (Ver en http://ideone.com/mCs1bh)

// Versión con for
int contar ( string a, string b ) {
    int r = 0;
    int n = min ( a.size(), b.size() );
    for ( int i = 0; i < n; ++i )
    	if ( a[i] == b[i] )
    		r++;
    return r;
}

// Versión recursiva
int contarRec ( string a, string b, int i ) {
    if ( i == a.size() || i == b.size() )
    	return 0;
    if ( a[i] == b[i] )
    	return 1 + contarRec(a,b,i+1);
    return contarRec(a,b,i+1);
}

Modularidad¶

Un problema complejo se puede descomponer en problemas más simples. Por ejemplo en programación funcional una serie de funciones realizadas secuencialmente podrían resolver la mayoría de problemas de programación.

* Modularidad para hallar la desviación estándar de una lista.

* Aplicación en Haskell:

main :: IO ()
main =  do
        let lista = [1..10]
        let sumatoria = sum lista
        let tam = length lista
        let media = sumatoria `div` tam
        let restas = map (media-) lista
        let cuadrados = map (^2) restas
        let sumCuadrados = sum cuadrados
        let valor = sumCuadrados `div` tam
        let r = sqrt . fromIntegral $ valor
        print(r)

Transparencia referencial¶

Se dice que una expresión es referencialmente transparente sí se puede reemplazar con su valor correspondiente sin cambiar el comportamiento del programa. Como resultado, la evaluación de una función referencialmente da el mismo valor para los mismos argumentos. Estas funciones se llaman funciones puras. Una expresión que no es referencialmente transparente se llama referencialmente opaca.

En las matemáticas todas las aplicaciones de una función son referencialmente transparentes por definición. Esto no pasa siempre en la programación, donde los términos procedimiento y método se utilizan para evitar connotaciones engañosas.

La importancia de la transparencia referencial es que permite al programador y al compilador razonar sobre el comportamiento del programa como un sistema de reescritura. Esto puede ayudar a probar la corrección, simplificar un algoritmo, ayudar a modificar el código sin romperlo, o optimizar el código mediante memoization, eliminación de subexpresión común, evaluación perezosa o paralelización.

Como la transparencia referencial requiere los mismos resultados para cualquier conjunto dado de entradas en cualquier punto en el tiempo, una expresión referencialmente transparente es por lo tanto determinista.

Ejemplo¶

* Se tiene la siguiente función:

int sumarUno(int x){
    return x + 1;
}

Es transparente, porque para cualquier valor de x no tendrá side effects.

* Pero con una función de tiempo como:

today();

No es transparente, porque para un día como hoy retornará 1 de Octubre de 2016, pero mañana no (llamando la función de la misma manera).

* En lenguajes que no tienen side effects como Haskell, podemos afirmar que,

f(x) = f(x)

para cada valor de x.

Polimorfismo paramétrico¶

Es una manera de hacer este tipo de lenguajes de programación mas expresivos, manteniendo su seguridad tipo estática. Usando polimorfismo paramétrico, una función o un tipo de dato puede ser escrito genéricamente para que pueda manejar valores idénticos sin depender de su tipo. Estas funciones y tipos de datos son llamadas funciones genéricas y tipos de dato genéricos respectivamente.

En programación funcional el polimorfismo parampetrico funciona de lasiguiente manera: * Evalúa la función dependiendo del tipo o del número de argumentos dados. * Permite que el tipo de una función dependa del tipo del parámetro

Ejemplos¶

La función "append" que une dos listas puede ser construida para que a esta no le importe el tipo de dato de sus elementos; puede juntar ya sea una lista de enteros, de reales, de strings, etc.
La función append puede ser escrita de la forma:

forall a. [a] x [a] -> a

Donde [a] denota el tipo de listas con elementos de tipo a. Podemos decir que el tipo de entrada de la función "append" está paramétrizado para todos los valores de a.

Ejemplo de polimorfismo en Haskell

data Shape = Circle Float Float Float | Rectangle Float Float Float Float

surface :: Shape -> Float
surface (Circle _ _ r) = pi * r ^2
surface (Rectangle x1 y1 x2 y2) = (abs $ x2 - x1) * (abs $ y2 - y1)

Funciones de primer orden y orden superior¶

Función de primer orden¶

Retorna un resultado o un valor de acuerdo a uno o más parámetros.

Función de orden superior¶

Retorna como resultado un valor o una función, tomando como parámetros valores o funciones. Por ejemplo, hallar la derivada de una función retorna como valor otra función.

Ejemplos¶

Funciones puras¶

Son funciones que no tienen efectos secundarios. Si una función pura se llama dos veces con la misma entrada, resultará en la misma salida. Ver los ejemplos en http://ideone.com/VLCx1o.

Ejemplos de funciones no puras (C++)¶

void add(int& val, int inc) {
  val += inc;
}

Modifica la variable val, lo cual es un efecto secundario.

int read() {
  int a;
  cin >> a;
  return a;
}

Puede dar salidas distintas en dos llamados con los mismos argumentos.

int f(int x) {
  int r = rand();
  return x + r%2;
}

Puede dar salidas distintas en dos llamados con los mismos argumentos.

Ejemplos de funciones puras (C++)¶

int max3(int a, int b, int c) {
  return max(a,max(b,c));
}

int sum(int n) {
  if ( n == 0 ) return 0;
  return n + sum(n-1);
}

double s(double x) {
  return sin(x);
}

Objetos inmutables¶

Todos los objetos son constantes, en un lenguaje funcional no es posible declarar un objeto, asignarle un valor, y después reemplazar el valor asignado. Por ejemplo, en Haskell, si se tiene una valor n, no se puede hacer let n = n-1, si se quiere guardar el valor n-1 se tendría que guardar en otro objeto, por ejemplo: let n2 = n-1. Ver ejemplo en http://ideone.com/eRRcDU.

Evaluación perezosa¶

• Algunos lenguajes funciones no evalúan expresiones que no son usadas. Esto puede reducir el tiempo de ejecución de algunas funciones en tiempo exponencial.

• Permite declarar infinitos valores, ya que siempre y cuando sólo se use un número finito solo estos se calcularán. Ver ejemplo en http://ideone.com/8sd0yF.

• Mediante la reducción por grafos, no se re-calculan expresiones o funciones ya evaluadas. Esto reduce el costo computacional.

Ventajas¶

1. Altos niveles de abstracción: El código muestra un mayor énfasis en el "¿qué se hace?" en lugar del "¿cómo se hace?".

2. Código declarativo y comprensible: Debido a los altos niveles de abstracción, los programas que aplican este paradigma suelen ser más cortos y fáciles de entender que sus versiones en programación imperativa.

3. La evaluación perezosa: Esta estrategia de evaluación permite realizar cálculos por demanda, evitando gasto computacional innecesario. El ejemplo más claro está en la utilización de listas infinitas.

4. Las características del paradigma, en especial la utilización de funciones puras, permiten realizar ciertas optimizaciones particulares.

5. Mayor probabilidad de aplicar expansión en línea: Esta es una optimización del compilador que sustituye los llamados a una función por la definición directa de dicha función, de tal forma que se ahorre tiempo y espacio durante la ejecución.

6. Optimizaciones a partir de la utilización de funciones puras: Las funciones puras nos garantizan la ausencia de efectos secundarios. Esto a su vez nos permite aplicar las siguientes mejoras:

   • Se pueden eliminar las funciones cuyo resultado no sea utilizado.
   • Una función retornará lo mismo siempre que se ejecute con los mismos parámetros, por lo cuál se puede evitar la repetición de cálculos mediante el uso de memoria caché.
   • El orden de ejecución de las funciones puede ser cambiado o incluso se puede llegar a aplicar paralelismo cuando no exista dependencia de datos entre dichas funciones.

Desventajas¶

1. Dificultad inicial para producir buen código: Esto debido a que un programador suele estar acostumbrado al pensamiento de la programación imperativa, tomando un poco de tiempo que la persona logre adaptarse y generar código útil.

2. Generación de grandes cantidades de short-lived garbage: Esto se debe principalmente a la caracteristica de inmutabilidad. Los garbage collectors tienden a optimizar este aspecto.

3. Menor eficiencia en el uso de CPU comparados con su contraparte imperativa: Debido principalmente a que muchas estructuras de variables mutables (como los arreglos) tienen una sencilla implementación en un paradigma imperativo, mientras que en la programación funcional no es fácil crear componentes homólogos inmutables con la misma eficiencia.

Lenguajes¶

A continuación se mencionarán y se dará una breve introducción con algunos ejemplos de lenguajes que implementan características del paradigma de programación funcional:

• Scala: Es un lenguaje de programación multi-paradigma diseñado para expresar patrones comunes de programación que integra características de lenguajes funcionales y orientados a objetos. La implementación actual corre en la máquina virtual de Java y es compatible con las aplicaciones Java existentes. En Scala las funciones son valores de primera clase, soportando funciones anónimas, orden superior, funciones anidadas y currificación. Scala viene integrado de fábrica con la técnica de pattern matching para modelar tipos algebraicos usados en muchos lenguajes funcionales. El siguiente código muestra una de las características de la programación funcional, el pasar funciones como argumentos de otras funciones.

Object Temporizador {
  def unaVezPorSegundo( repite : () >= unit ) {
    while (true) { repite(); Thread sleep 1000 }
  }
  def elTiempoVuela() {
    println("el tiempo pasa volando.....") 
  }
  def main(args : Array[String]) {
    unaVezPorSegundo( elTiempoVuela )
  }
}
`````````
Este código define la función unaVezPorSegundo, la cual ejecuta una función (en este caso elTiempoVuela) y espera un segundo para ejecutarla de nuevo una y otra vez.

* Scheme: Es un lenguaje funcional (si bien impuro pues sus estructuras de datos no son inmutables) y un dialecto de Lisp. Fue desarrollado por Guy L. Steele y Gerald Jay Sussman en la década de los setenta e introducido en el mundo académico a través de una serie de artículos conocidos como los Lambda Papers de Sussman y Steele. La filosofía de Scheme es minimalista. Su objetivo no es acumular un gran número de funcionalidades, sino evitar las debilidades y restricciones que hacen necesaria su adición. Así, Scheme proporciona el mínimo número posible de nociones primitivas, construyendo todo lo demás a partir de un reducido número de abstracciones. Las listas son la estructura de datos básica del lenguaje, que también ofrece arrays entre sus tipos predefinidos. Debido a su especificación minimalista, no hay sintaxis explícita para crear registros o estructuras, o para programación orientada a objetos, pero muchas implementaciones ofrecen dichas funcionalidades. El siguiente ejemplo muestra porque Scheme es un lenguaje funcional impuro, permitiendo realizar estructuras como for, las cuales incumplen la regla de que los objetos son inmutables.
`````````
( do ((i 0 (+ i 1)) )
   ((i = 5) )
   (display i))
`````````
Este código es un for desde 0 hasta 5, el cual imprime el valor del iterador en cada loop.
* Haskell: Es un lenguaje de programación estandarizado multi-propósito puramente funcional con semánticas no estrictas y fuerte tipificación estática. Su nombre se debe al lógico estadounidense Haskell Curry. En Haskell, "una función es un ciudadano de primera clase" del lenguaje de programación. Como lenguaje de programación funcional, el constructor de controles primario es la función. El lenguaje tiene sus orígenes en las observaciones de Haskell Curry y sus descendientes intelectuales. Las características más interesantes de Haskell incluyen el soporte para tipos de datos y funciones recursivas, listas, tuplas, guardas y calce de patrones.

## Ejemplos Fibonacci

Se hará un ejemplo de cómo imprimir los primeros diez números de Fibonacci en algunos lenguajes de programación funcional.

Python funcional¶

fibonacci = (lambda n, first=0, second=1:
    [] if n == 0 else
    [first] + fibonacci(n - 1, second, first + second))
print(fibonacci(10))

Haskell¶

fibonacci_aux = \n first second->
    if n == 0 then [] else
    [first] ++ fibonacci_aux (n - 1) second (first + second)
fibonacci = \n-> fibonacci_aux n 0 1
main = putStrLn (show (fibonacci 10))

Perl 6¶

subset NonNegativeInt of Int where * >= 0;

proto fib (|) is cached returns NonNegativeInt {*}
multi fib (0) { 0 }
multi fib (1) { 1 }
multi fib (NonNegativeInt $n) { fib($n - 1) + fib($n - 2) }

for ^10 -> $n { say fib($n) }

Erlang¶

-module(fib).
-export([fib/1]).

fib(1) -> 1; % If 1, then return 1, otherwise (note the semicolon ; meaning 'else')
fib(2) -> 1; % If 2, then return 1, otherwise
fib(N) -> fib(N - 2) + fib(N - 1).

Elixir¶

defmodule Fibonacci do
   def fib(0), do: 0
   def fib(1), do: 1
   def fib(n), do: fib(n-1) + fib(n-2)
end

Lisp¶

(defun fib (n &optional (a 0) (b 1))
  (if (= n 0)
      a
      (fib (- n 1) b (+ a b))))

Clojure¶

(defn fib
  [n]
  (loop [a 0 b 1 i n]
    (if (zero? i)
      a
      (recur b (+ a b) (dec i)))))

R¶

fib <- function(n) {
 if (n <= 2) 1
 else fib(n - 1) + fib(n - 2)
}

Aplicaciones:¶

La programación funcional es sobre todo popular en el ámbito académico, sin embargo a continuación se presentan algunas aplicaciones que se les ha dado a diferentes lenguajes funcionales.

• Scheme:

  • Desarrollo de aplicaciones para los primeros ordenadores de la firma Apple Macintosh.
  • Desarrollo de sistemas de simulación y de control de telescopio.
  • En el MIT se da uso a la programación funcional dentro de un curso de mecánica clásica avanzada. Este curso utiliza el libro llamado Structure and Interpretation of Classical Mechanics (SICM), en el cual se busca explicar fenómenos físicos usando programas para simularlos.

• Erlang: Este lenguaje se caracteriza por aplicar tanto programación funcional como concurrente. Fue diseñado para tener un enfoque hacia las aplicaciones distribuidas y tolerantes a fallos. Dentro de sus características principales encontramos la capacidad de proporcionar cambio en caliente de código. Estas propiedades lo han hecho útil dentro del campo de las telecomunicaciones, razón por la cual empresas como WhatsApp, Facebook y T-Mobile lo han usado dentro del desarrollo de algunos de sus proyectos.

• Haskell:

  • Desarrollo de sistemas aeroespaciales.
  • Programación web.
  • Diseño de hardware.

En el siguiente link se encuentra un gran listado de aplicaciones que se le ha dado a Haskell en la industria: https://wiki.haskell.org/Haskell_in_industry