martes, 1 de julio de 2008

Lenguajes Funcionales

Existen cuatro grandes paradigmas entre los lenguajes de programación:
  • Lenguajes Imperativos: Pascal, C, Fortran.
  • Lenguajes Orientados a Objetos: Smalltalk, Java (no puro), Python, Ruby.
  • Lenguajes Lógicos: Prolog.
  • Lenguajes Funcionales: FP, APL, Lisp.
Los lenguajes funcionales suelen usarse mucho para Inteligencia Artificial. Para alguien que está acostumbrado a programar en lenguajes imperativos u orientado a objetos, la curva de aprendizaje es un poco más grande; cuesta un poco entender el paradigma. Lo más chocante es que en general no existe la asignación de variables, se trabaja en forma recursiva, con memoria dinámica, y, en algunos lenguajes, cualquier programa se puede escribir en una sola línea (por ejemplo en APL), lo que dificulta un poco su lectura.

http://en.wikipedia.org/wiki/Functional_programming

Cálculo Lambda

Cálculo Lambda es una base teórica matemática para definir lenguajes funcionales. Data de la década de 1930 y fue creado por Alonzo Church y Stephen Cole Kleene, tres décadas antes de que existieran las computadoras.

http://en.wikipedia.org/wiki/Lambda_calculus

FP (Functional Programming)

Este lenguaje nace como un lenguaje teórico del paper de John Backus de 1977 titulado: "Can Programming be Liberated from the von Neumann Style?".

Hay algunos intérpretes libres circulando por Internet, aunque no existe ninguna implementación comercial. Las que hay son versiones hechas por universitarios.

FP maneja básicamente dos tipos de datos:
  • Átomos: pueden ser números, strings, valores lógicos (True y False) o el elemento vacío. Ejemplos: a, b, 1, 2 0.
  • Secuencias: son como arrays o listas y se escriben con corchetes angulares. Ejemplos: <a b c> <d e> <<d e> <a b>> < > (La secuencia vacía es equivalente al elemento vacío y es átomo y secuencia a la vez).
El lenguaje está compuesto por los tipos de datos y las funciones, que pueden ser:
  • Primitivas
  • Formas Funcionales
  • Definidas por el Usuario
Las funciones no tienen argumentos. Son monádicas. Lo único que reciben como entrada es el ambiente.

FP es un lenguaje muy compacto y poderoso, a pesar de no contar con implementación comercial. Hay tres distintas formas de trabajar con FP:

de modo Recursivo:


de modo Funcional:


de modo Iterativo:


El código que mostré para cada modo es el de la función factorial. Comparando las tres funciones, vemos que la del modo funcional es la más compacta y elegante. Esto sucede así, ya que es el modo que mejor soporta el lenguaje; el más cercano al paradigma. El tercer modo, el iterativo, es el más similar a un lenguaje imperativo.

http://en.wikipedia.org/wiki/FP_programming_language

APL (A Programming Language)

Creado en 1957 por Kenneth E. Iverson. Fue hecho para resolver problemas matemáticos. Entre otras aplicaciones, se usó para describir el hardware de la IBM 360, para el sistema Deep Blue de IBM que venció a Kasparov al ajedréz y para generar los efectos de la célebre película Tron de Walt Disney.

Existen varias implementaciones comerciales y libres de APL. Algunas de ellas son:

Free APL
APL 2000
APL 2C

(Particularmente, sólo he probado la Trial Version del APL 2C para Windows y la verdad que me pareció muy cómoda y user friendly, ya que uno puede seleccionar los caracteres extraños haciendo click con el mouse en un tecladito que se dibuja debajo de la ventana. En cambio, en los otros intérpretes uno tiene que memorizar una combinación de teclas para nada amigable.)

APL es el lenguaje más compacto que alguna vez vi. Todo, absolutamente todo, puede escribirse en una sola línea. No se usa declaración de identificadores, ya que nada está declarado estáticamente. Las asociaciones son dinámicas, por ende cualquier variable se puede asociar con cualquier tipo de dato.

Los tipos de datos pueden ser:

Simples: números, booleanos, strings.
Estructurados: arreglos multidimensionales homogéneos.

Todo el lenguaje está compuesto por los tipos de datos y un conjunto de operadores, que pueden ser monádicos o diádicos.

Escribir un programa que calcule el factorial en este lenguaje es trivial, ya que tenemos el operador ! que ya hace eso.

APL es excelente para trabajar con matrices porque cuenta con operadores de trasposición, inversión y de espejamiento de matrices.

El siguiente código de ejemplo devuelve todos los números primos comprendidos entre 1 y N:


Un tema curioso es que la ejecución del código se hace de derecha a izquierda y el orden de ejecución de los operadores es en ese orden también.

http://en.wikipedia.org/wiki/APL_programming_language

LISP (List Processing)

Es el lenguaje más popular del paradigma funcional.

Fue creado por John McCarthy en 1958.

En general, los intérpretes de Lisp están escritos en C y existen varias implementaciones. Algunas de ellas son:

XLISP
XLISP-PLUS
CLISP
CUSP (un plugin para Eclipse)

(He probado el XLISP-PLUS, el CLISP, el TLC-LISP -que no menciono en la lista porque no encuentro una página de donde bajarlo- y el plugin para Eclipse. A pesar de que tiene bastantes bugs, el que más me simpatizó es el plugin para Eclipse de IBM. Unos amigos que tienen Windows me dijeron que no lo pudieron instalar. Yo tengo Ubuntu Hardy Heron y no tuve problemas. Si uno quiere algo más liviano y menos bugeado, CLISP y XLISP o XLISP-PLUS son las mejores opciones.)

Los tipos de datos (objetos) que forman el lenguaje son:

Átomos: 2, 3.2, a, CASA, +, &, T, nil
Listas: ((a b) c d) (a b) ((a b) (c d)) ()

Los valores lógicos son T (true) y nil (vacío, que equivale a false). Además, () equivale a nil. Al igual que en FP, la lista vacía es átomo y lista a la vez.

Todo en Lisp es una lista o un átomo. Aunque parezca extraño, también una llamada a función. Por ejemplo:

(+ 3 2)

Como FP, Lisp cuenta con funciones nativas (una larga lista: selectoras, constructoras, reconocedoras de objetos, aritméticas, booleanas, relacionales, condicionales, funcionales -similares a las formas funcionales de FP-, etc), funciones definidas por el programador (con nombre o anónimas) y además abundan vastas bibliotecas de terceros que complementan muy bien al lenguaje.

Lisp es el más poderoso de todos. Es muy cómodo para programar secuencias de tareas parametrizadas. Por eso suele usarse para la programación de robots o para la creación de algún intérprete (muchos de los intérpretes universitarios de FP que andan dando vueltas están hechos en LISP).

Lo más extraño que tiene este lenguaje es que todo, absolutamente todo, se ejecuta, a menos que se especifique lo contrario con la función QUOTE.

Por ejemplo, si uno escribe:

(car (1 2 3))

CAR es un selector que recibe una lista por parámetro y devuelve la cabeza. Si se hubiera escrito esta línea, así como está, se hubiera devuelto un error, ya que el intérprete no podría encontrar la función "1" (a menos que la función "1" haya sido definida con anterioridad).

En cambio, si escribimos:

(car (quote (1 2 3)))

O simplemente:

(car '(1 2 3))

El intérprete devuelve 1, como debería ser.

La función factorial escrita en Lisp (con el dialecto Common Lisp) sería:

(defun FACT (N)
(if (eq N 0) 1 (* N (FACT (- N 1))))
)

Lisp es altamente recursivo.

http://en.wikipedia.org/wiki/Lisp_programming_language

Conclusiones

Los lenguajes funcionales no son populares salvo en ambientes universitarios. Se suelen usar mucho para investigación y, en general, resultan herramientas muy poderosas para cálculos matemáticos, definiciones y demostraciones.

Algunos lenguajes del mundo de la orientación a objetos se están dando cuenta de su poder y, de a poco, están incluyendo bibliotecas para trabajar de forma funcional. Uno de los casos más conocidos es el del monstruo Java, cuya comunidad se debate si los closures (objetos funcionales del mundo del paradigma funcional) deben formar parte de la especificación estándar del JDK de Java 7.