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 y algunos conceptos modernos de modularización y polimorfismo, como es el caso del lenguaje ML.

Programar en un lenguaje funcional significa construir funciones a partir de las ya existentes. Por lo tanto es importante conocer y comprender bien las funciones que conforman la base del lenguaje, así como las que ya fueron definidas previamente. De esta manera se pueden ir construyendo aplicaciones cada vez más complejas.

La desventaja de este modelo es que resulta bastante alejado del modelo de la máquina de von Neumann y, por lo tanto, la eficiencia de ejecución de los intérpretes de lenguajes funcionales no es comparable con la ejecución de los programas imperativos precompilados. Para remediar la deficiencia, se está buscando utilizar arquitecturas paralelas que mejoren el desempeño de los programas funcionales, sin que hasta la fecha estos intentos tengan un impacto real importante.

Los dos mecanismos básicos presentados anteriormente se corresponden con los conceptos de abstracción funcional y aplicación de función; si le agregamos un conjunto de identificadores para representar variables se obtiene lo mínimo necesario para tener un lenguaje de programación funcional. Lambda calculo tiene el mismo poder computacional que cualquier lenguaje imperativo tradicional.

Las ventajas de tener un lenguaje tan simple son:

• Permite definiciones simples.

• Facilita el estudio de aspectos computacionales.

• Su carácter formal facilita la demostración de propiedades.

Aplicaciones

• Compilación de lenguajes funcionales.

• Especificar semántica a lenguajes imperativos.

• Formalismo para definir otras teorías.

Programación funcional:

La crítica de John Backus a los "lenguajes convencionales de von Neumann" llamó la atención hacia la programación funcional (hacia 1978). El estilo de programación adoptado por Backus fue denominado FP (Functional Programming).

El componente básico de los lenguajes funcionales es la noción de función y su estructura de control esencial la aplicación de una función. Entre los lenguajes funcionales se encuentran ISWIM, ML, LISP y todos sus derivados, como Scheme. Las características fundamentales de los lenguajes funcionales de programación son, según [SET92]:

1. El valor de una expresión depende sólo de los valores de sus subexpresiones, si las tiene. La programación funcional pura es una programación sin asignaciones. En realidad, la mayoría de los lenguajes funcionales son impuros, ya que permiten asignaciones. Sin embargo, su estilo de programación es diferente al de los lenguajes de programación imperativa.

2. Almacenamiento implícito. El programador no debe preocuparse en manejar el almacenamiento de datos. Una consecuencia de esto es que la implementación del lenguaje debe realizar una "recolección de basura"

...