Programacion funcional con recursividad

José Helo Guzmán, Cartago: Editorial Tecnológica de Costa Rica, 2000

ISBN 9977-66-113-8 PROGRAMACION FUNCIONAL CON RECURSIVIDAD

Introducción

El objetivo del paradigma funcional es conseguir lenguajes expresivos y matemáticamente elegantes, en los que no sea necesario bajar al nivel de la máquina para describir el proceso llevado a cabo por el programa, y evitando el concepto de estado del cómputo. La secuencia de computaciones llevadas a cabo por el programa se regiría única y exclusivamente por la reescritura de definiciones más amplias a otras cada vez más concretas y definidas, usando lo que se denominan definiciones dirigidas.

Todo esto con el objetivo de familiarizar a los estudiantes con un lenguaje elegante en el cual se pueda manejar más fácilmente y así los programas sean menos extensos y complejos.

Otro de los objetivos primordiales de dicho paradigma es buscar satisfacer las necesidades del usuario con respecto a operaciones matemáticas y convertirse en un lenguaje más expresivo.

Paradigma Funcional

Historia

Sus orígenes provienen del Cálculo Lambda (o λ-cαlculo), una teoría matemática elaborada por Alonso Church como apoyo a sus estudios sobre Computabilidad. Un lenguaje funcional es, a grandes rasgos, un azúcar sintáctico del Cálculo Lambda.

Cálculo Lambda

Los orígenes teóricos del modelo funcional se remontan a la década del 30, mas precisamente al año 1934, cuando Alonso Church introdujo un modelo matemático de computación llamado lambda calculo.

A pesar de que en esta época las computadoras aun no existían el lambda cálculo se puede considerar como el primer lenguaje funcional de la historia y sus fundamentos fueron la base de toda la teoría de la programación funcional y de los lenguajes funcionales desarrollados posteriormente. Se puede decir que los lenguajes funcionales modernos son versiones de lambda cálculo con numerosas ayudas sintácticas.

Aunque cuando aparece el cálculo lambda, aún no existían las computadoras, resulta ser una herramienta simple que se adelanta a su época, que abarca dos operaciones:

a. Definir alguna(s) función(es) de un solo argumento y con un cuerpo específico, denotado por la siguiente terminología:

b. lx.B, en donde:

i. x: Define el parámetro o argumento formal.

ii.

iii. B: Representa el cuerpo de la función.

iv. Es decir f(x) = B.

a. REDUCCION:

Consiste en aplicar alguna de las funciones creadas, sobre un argumento real (A); resultado de sustituir las ocurrencias del argumento formal (x), que aparezcan en el cuerpo (B) de la función, con el argumento (A),

es decir: (lx.B)

Ejemplo:

(lx.(x+5))3, indica que en la expresión x + 5, debemos sustituir el valor de x por 3.

Cuando ya no es posible reducir una función, se dice que ésta se encuentra en su estado normal, o sea hemos encontrado el valor de la función, que dependerá únicamente de los argumentos y siempre tendrá la consistencia de regresar el mismo valor para los mismos argumentos.

Lo anterior es la transferencia referencial y al no contar con variables globales, permiten al sistema la ejecución de procesos en forma paralela para incrementar su eficiencia.

Sobre estos simples conceptos está basada la programación funcional, aunque existen otros, usados para identificarla y aumentan su potencial en el desarrollo de aplicaciones.

Características

Los programas escritos en un lenguaje funcional están constituidos únicamente por definiciones de funciones, entendiendo éstas no como subprogramas clásicos de un lenguaje imperativo, sino como funciones puramente matemáticas, en las que se verifican ciertas propiedades como la transparencia referencial (el significado de una expresión depende únicamente del significado de sus subexpresiones), y por tanto, la carencia total de efectos laterales.

Otras características propias de estos lenguajes son la no existencia de asignaciones de variables y la falta de construcciones estructuradas como la secuencia o la iteración (lo que obliga en la práctica a que todas las repeticiones de instrucciones se lleven a cabo por medio de funciones recursivas).

Existen dos grandes categorías de lenguajes funcionales: los funcionales puros y los híbridos. La diferencia entre ambos estriba en que los lenguajes funcionales híbridos son menos dogmáticos que los puros, al admitir conceptos tomados de los lenguajes procedimentales, como las secuencias de instrucciones o la asignación de variables.

En contraste, los lenguajes funcionales puros tienen una mayor potencia expresiva, conservando a la vez su transparencia referencial, algo que no se cumple siempre con un lenguaje funcional híbrido.

Entre los lenguajes funcionales puros, cabe destacar a Haskell y Miranda. Los lenguajes funcionales híbridos más conocidos son Lisp, Scheme, Ocaml y Standard ML (estos dos últimos, descendientes del lenguaje ML).

La programación funcional, es un modelo basado en la evaluación de funciones matemáticas, entendidas como mecanismos para aplicar ciertas operaciones sobre algunos valores o argumentos, para obtener un resultado o valor de la función para tales argumentos.

Sin embargo, tanto argumentos como resultado de una función, pueden ser otra función, o incluso la misma, tal como una forma de recursividad, que constituye una poderosa herramienta de la programación funcional

Lenguajes Funcionales

Los matemáticos desde hace un buen tiempo están resolviendo problemas usando el concepto de función. Una función convierte ciertos datos en resultados. Si supiéramos cómo evaluar una función, usando la computadora, podríamos resolver automáticamente muchos problemas.

Así pensaron algunos matemáticos, que no le tenían miedo a la máquina, e inventaron los lenguajes de programación funcionales. Además, aprovecharon la posibilidad que tienen las funciones para manipular datos simbólicos, y no solamente numéricos, y la propiedad de las funciones que les permite componer, creando de esta manera, la oportunidad para resolver problemas complejos a partir de las soluciones a otros más sencillos.

También se incluyó la posibilidad de definir funciones recursivamente.

Un lenguaje funcional ofrece conceptos que son muy entendibles y relativamente fáciles de manejar para todos los que no se durmieron en las clases de matemáticas. El lenguaje funcional más antiguo, y seguramente el más popular hasta la fecha, es LISP, diseñado por McCarthy [1] en la segunda mitad de los años 50. Su área de aplicación es principalmente la Inteligencia Artificial. En la década de los 80 hubo una nueva ola de interés por los lenguajes funcionales, añadiendo la tipificación

...