Antonio Damigo

La Programación Declarativa.

por 22 de febrero de 2013, 906 visitas
La Programación Declarativa. Aunque en nuestro país la informática comenzó a popularizarse en la década de los ochenta, con la aparición del ordenador personal (pc), la programación de computadoras es mucho más antigua. El lenguaje maquina, basado en el sistema binario y el álgebra booleana, es el natural de las computadoras. La razón reside en que el soporte físico de las mismas lo constituye el paso de una corriente eléctrica a través de un circuito microprogramable, dando lugar a dos niveles de voltaje: encendido(1) y apagado(0). La consecuencia lógica de estas dos situaciones es la aplicación de un lenguaje que tenga como sistema de numeración ambas cifras. (0 y 1). La trascendencia fue tal que en nuestro sistema educativo le dimos una gran importancia a la “teoría de conjuntos”, allá por los años setenta. Pero la programación en este lenguaje es pesada, laboriosa y tediosa por lo que pronto se construyeron otros lenguajes en los que las instrucciones al computador se hacían con palabras más significativas, los lenguajes de más alto nivel: Ensamblador, Cobol, Fortram, Perl, Basic, Pascal, C, Smalltalk , Lisp y otros. No obstante, al final, mediante un interprete o mediante un proceso llamado compilación, se traducen esas palabras de más alto nivel al lenguaje que verdaderamente entiende la máquina. La clasificación de todos estos lenguajes que tratan la programación de computadoras puede hacerse desde varios puntos de vistas: bajo y alto nivel, de propósito general o especialistas, interpretados o compilados, etc. Pero hay uno que nos interesa especialmente para introducirnos en el tema: la filosofía de cómo abordar un sistema de programación. Desde está óptica podemos clasificar a los lenguajes en dos grandes bloques: Imperativos y Declarativos. Los lenguajes imperativos son aquellos que dicen al computador qué tiene que ser computado, cómo tiene que hacerlo y en el orden que deben ejecutarse las sentencias. Los lenguajes declarativos son los que indican qué debe computarse, que resultados queremos obtener, pero no necesariamente se le indica al computador cómo hacerlo y es prerrogativa del computador elegir el orden de las sentencias.
La Programación Declarativa

1) Paradigmas de la programación: imperativo y declarativo.

Hasta la aparición de los lenguajes declarativos los lenguajes se engloban conjuntamente en el paradigma llamado imperativo. El nombre se debe al hecho de que los programas consisten en secuencias de mandatos, instrucciones u órdenes que han de ser ejecutados por el computador en el orden indicado por el programador.

Dichos lenguajes pueden verse como un “recubrimiento” de alto nivel de las instrucciones presentes en el hardware.

A diferencia de esta visión, en los paradigmas declarativos el programador expresa las propiedades que han de ser satisfechas por el cómputo, pero no el orden exacto en que han de realizarse las acciones dentro del ordenador. Los compiladores de estos lenguajes tienen gran libertad para decidir dicho orden. Un mismo programa puede ser ejecutado siguiendo diferentes secuencias de acciones elementales sin que por ello se vea afectado su resultado final.

Dentro de los paradigmas declarativos distinguimos:


- La programación lógica.
- La programación funcional.

Los paradigmas de la programación han evolucionado a lo largo de la historia de la misma.  Los lenguajes de programación pueden ser clasificados con respecto a diversos criterios. Pero existe un criterio para clasificarlos, que veremos a continuación, que los divide en dos grandes grupos: lenguajes imperativos y lenguajes declarativos.  Dando lugar cada uno de ellos a un tipo de programación distinta tanto en su enfoque filosófico como estructural.

Empecemos viendo qué es programación declarativa y cuáles son sus ejemplares.

Un lenguaje declarativo es tal que sus frases describen relaciones entre los datos, ocultando los algoritmos dentro de la semántica del lenguaje. Esto es difícil de entender e intentaremos aclarar los términos.

Informalmente, la Programación Declarativa (PD) establece qué debe ser computado, pero no necesariamente cómo computarlo. En el ámbito de la programación, el término declarativa se suele introducir en contraposición al término imperativa (o procedimental). En ésta última, las estructuras de control del lenguaje de programación permiten seguir perfectamente las acciones que debe realizar un programa. La ausencia de este tipo de estructuras de control es lo que caracteriza a los lenguajes declarativos. De esta forma, la PD facilita la labor del programador, permitiéndole concentrarse en dar una formulación del problema, liberándolo del control del algoritmo: cómo la máquina, a partir de tal formulación, encontrará las soluciones del problema. Puede decirse que en la aproximación imperativa la construcción de un programa consiste en estudiar las secuencias de instrucciones que debo dar al computador para buscar la solución, mientras que la aproximación declarativa viene caracterizada por una actitud muy diferente: ¿cómo expresar la descripción del problema para que el computador pueda buscar las soluciones?.

El primero de los estilos describe las acciones a realizar, mientras que el segundo describe el conocimiento acerca del problema. Así  en PD un algoritmo aparece descompuesto a través de la famosa ecuación de [Kowalski, 1979]:



Algoritmo = Lógica + Control



que indica que la componente (¿esencial?) de un algoritmo es la componente lógica o especificación de un problema en términos de cierta lógica. Tal ecuación ha sido considerada la caja de Pandora [Schreye y Denecker, 1999] de la PD, ya que permite aislar la especificación del problema, de la estrategia de búsqueda de la solución. Hasta el punto es así que muchos autores han intentado generalizar la ecuación de múltiples formas con objeto de interpretar otros estilos de la PD.

Los dos principales paradigmas de la PD son la Programación Lógica (PL) y la Programación Funcional (PF).  Históricamente el término declarativo ha sido acuñado para cubrir la PF y la PL, reconociendo que tienen muchos aspectos en común. Sin embargo, la comunidad científica que usa ambos estilos han reconocido trabajar de forma separada, con conferencias independientes (p.e., International Logic Programming Conference), y publicaciones también independientes (p.e., Journal of Functional Programming, Cambridge University Press, o Journal of Logic Programming). Afortunadamente, durante los últimos años se han consolidado varias conferencias sobre ambos paradigmas.

Entre los ejemplares de la PD aparecen otros paradigmas además de las citados: Programación con Restricciones [Lassez, 1987; Maher, 1999], Programación Ecuacional [O’Donnell,1985], Programación Inductiva [Lavrac y Dzeroski, 1997], Programación Algebraica [Bird y de Moor, 1997], o incluso mezcla de distintos paradigmas: Programación Concurrente con Restricciones [Saraswat, 1993], Programación Lógica/Concurrente con Restricciones [Ueda, 1999], y Programación Lógico/Funcional (PLF) [Hanus, 1997; López-Fraguas y Sanchez-Hernandez, 1999].

Aún lo dicho anteriormente, los principales paradigmas de la PD son la PL  y la PF. Por esta razón, muchos autores han intentado localizar los aspectos que permiten unificarlas. Ello aclararía si realmente ambos estilos son ejemplares de una misma filosofía o punto de vista de la computación.

Quizás una primera visión interesante de partida sea: fórmulas como programas. Desde esta perspectiva, un programa tiene dos lecturas. La primera es ver la fórmula como un programa desde el punto de vista operacional, con un modelo de reducción simple y conciso. La segunda es ver un programa como una fórmula de una lógica a la que exigiremos también una semántica declarativa simple. El término declarativa indica que se utiliza un dominio matemático conocido en el cual interpretar los objetos sintácticos.

La posible ventaja de esta visión viene dada cuando la interpretación semántica es sencilla, y de esta forma los programas son fáciles de manejar, transformar y verificar.

Así, si leemos el programa como una fórmula podemos razonar sobre su corrección centrando nuestra atención en un análisis lógico de la fórmula, a través de un formalismo que permita probar que el programa satisface la especificación. Obviamente, tanto la especificación como el programa son fórmulas. C.A.R. Hoare escribía:

. . . una especificación es un predicado que describe todas las observaciones de un sistema complejo

. . . un programa es un predicado expresado utilizando un subconjunto de conectivas, codificadas con un lenguaje de programación. [Hoare y Jones, 1989]



Otros autores establecen paralelismos entre ambas concepciones:

. . . si sustituimos conectivas por cláusulas de Horn, la especificación es un programa lógico y no es necesaria una codificación. [Ringwood, 1988]



Normalmente en un programa intervienen varias fórmulas. Así, podemos formalizar algo más la concepción anterior en la forma siguiente. La idea de la PD es que:

   un programa es una teoría descrita en alguna lógica L y
   un cómputo es una deducción a partir de la teoría.

¿Qué lógica L es apropiada? Los principales requisitos de la lógica L es que debe tener: (1) un modelo teórico (semántica declarativa), (2) un mecanismo de deducción o cómputo (semántica procedural u operacional), y (3) un teorema de corrección (los cómputos o respuestas calculadas deben ser correctos). Ejemplos de tales teorías son la lógica de primer orden (Prolog), ciertas lógicas polimórficas de primer orden (Gödel), o el ?C simple tipificado (?Prolog, Escher). . Ejemplos de mecanismos de cómputo asociados pueden ser la resolución o la reescritura.

Dependiendo del lenguaje, se requieren otras propiedades, como la compleción, la confluencia, o la terminación. De esta forma, la división entre PF y PL puede ser vista desde un punto de vista histórico o sociológico, pero no técnico.


2) Principios de la Programación Declarativa

El proceso en la tarea de la programación comienza formalizando el problema en la lógica para después escribir la componente lógica o programa. En PL tal componente es una teoría consistente en un conjunto de axiomas descrito como fórmulas de primer orden o cláusulas de Horn. En PF  la componente lógica del programa puede ser una colección de ecuaciones para un ïC tipificado. Una vez escrita la componente lógica, puede ser necesario que el programador añada una componente de control explícita. En este sentido, podemos distinguir entre PD  en sentido débil, donde los programas son teorías pero el programador puede suministrar información (control) con objeto de obtener un programa eficiente. En la PD en sentido fuerte todo el mecanismo de control es implícito y el programador solo proporciona una teoría o programa.

El punto de vista descrito permite confirmar que los estilos funcional y lógico son ejemplares de una misma filosofía. Otra segunda visión puede consistir en unificar los paradigmas PL y PF, por ejemplo vía métodos algebraicos proporcionados por la Programación ecuacional [O’Donnell, 1977]. Esta aproximación considera el uso de ecuaciones para definir funciones y su evaluación mediante reducción por reescritura [Klop, 1992], buscando en un espacio de estados una forma irreducible, que en el caso de la PF viene dada por la ausencia de expresiones reducibles (redexes), y en el caso de la PL es la derivación de la cláusula vacía. Por tanto, al eliminar las conectivas lógicas y todo símbolo de predicado distinto de la igualdad, se obtiene un subconjunto restringido de la lógica de primer orden: la lógica ecuacional. La programación ecuacional incide en mayor medida en el contenido lógico de las computaciones y establece una conexión clara con otros estilos declarativos, como el lógico/funcional [Moreno Navarro y Rodríguez Artalejo, 1988; Hanus, 1994].

Una tercera visión muy prometedora es la proporcionada por la Semántica contextual. La confluencia, propiedad esencial del lambda cálculo, se puede extender a otros sistemas de reescritura. Sin embargo, en muchos casos puede interesar que se pierda tal propiedad. Tales sistemas han sido modelados por [Abramsky, 1990] en el marco de la semántica contextual, que proporciona información de los términos (programas con o sin variables libres) a través de una relación de preorden contextual (un contexto es un término con un hueco) que permite definir una noción de equivalencia de programas. En tal modelo la confluencia no es importante, siendo ésta reemplazada por el concepto de transformación correcta. Tal modelo permite capturar el indeterminismo y la evaluación perezosa [Schmidt-Schaußy Huber, 2000], y la evaluación de un término puede realizarse en presencia de variables libres.

A pesar de la profusión de la PD en el currículum, normalmente su exposición está basada en ejemplos aislados y sin principios comunes. [Sabry, 1999] argumenta que el fundamento principal de la PD es la abstracción: el uso de abstracciones que compatibiliza con el dominio del problema. En algunos casos, las abstracciones son esencialmente TADs (Tipos Abstractos de Datos) (p.e., el TAD de las ecuaciones lineales en Mathematica [Wolfram, 1999]). En otros casos las abstracciones son herramientas encapsuladas en una librería. En casos más complejos, las abstracciones son proporcionadas por un lenguaje orientado al dominio (domain–specific language). [Sabry, 1999] defiende que la clave del éxito de la enseñanza de la PD es la enseñanza de las abstracciones en programación en todos los niveles imaginables.

La historia de las abstracciones es tan amplia como la historia de los lenguajes de programación. En su forma final, la PD proporciona soluciones a los problemas usando únicamente el enunciado del problema como programa. Históricamente este nivel de abstracción ha sido asociado con lenguajes de programación especializados, pero es usado hoy en día de forma rutinaria por estudiantes y profesores en una variedad de situaciones, lenguajes y cursos.

3) Lambda cálculo

A mediados de los años 60, Peter Landin observó que un lenguaje de programación complejo podía ser formulado a través de un reducido núcleo y un conjunto de expresiones derivadas que posteriormente serían traducidas a dicho núcleo. El núcleo al que Peter Landin se refería era el lambda-cálculo, un sistema formal inventado en los años 30 por Church en el que todos los cálculos se reducen a dos operaciones básicas, la de?nición defunciones y su aplicación. Hoy en día, el lambda cálculo se puede considerar como el más pequeño lenguaje universal de programación y se utiliza habitualmente en el diseño e implementación de los lenguajes de programación y en el estudio de los sistemas de tipos.

Exiten otros sistemas alternativos al lambda-cálculo que pueden ser utilizados para el mismo objetivo. El pi-cálculo se utiliza para de?nir la semántica de lenguajes concurrentes basados en paso de mensajes. El object-cálculo se utiliza a su vez para de?nir las características básicas de los lenguajes orientados a objetos.

El lambda-cálculo básico es extremadamente limitado, pero puede ser enriquecido de diferentes formas. Por ejemplo, introduciendo una sintaxis concreta para ciertas características comunes como los números, las tuplas o los registros. También es posible introducir otros conceptos más avanzados como las referencias o las excepciones.

Conceptos básicos

La de?nición de funciones es una de las características básicas de cualquier lenguaje de programación. En lugar de escribir la misma fórmula una y otra vez, de?nimos una función o procedimiento realiza el cálculo de forma genérica en función (o no) de un conjunto de parámetros. Por ejemplo, un programador sustituiría la expresión:

(5 * 4 * 3 * 2 * 1) + (7 * 6 * 5 * 4 * 3 * 2 * 1) -(3 * 2 * 1)

por factorial(5) + factorial(7) -factorial(3) una vez de?nida la función:

factorial(n) = if n = 0 then 1 else n * factorial(n-1)

En el lambda-cálculo, la expresión ‘‘?n. ...’’ equivale “la función que, para cada n devuelve ...”. Utilizando esta notación, podemos reescribir la función factorial como:

factorial = ?n. if n = 0 then 1 else n * factorial(n-1)

En el lambda-cálculo puro TODO son funciones, los parámetros de las funciones son funciones, el resultado de las funciones también. La sintaxis es muy sencilla, pues sólo existen tres tipos de términos: las variables, las abstracciones de una variable en un término y la aplicación de un término a otro término.

t::=
x
?x.t
tt

Una mayor información acerca de este cálculo se escapa de lo que se pretende en esta página (una mera divulgación de la programación declarativa), ello lo podrá encontrar en este enlace Especificaciones sobre el Lambda-cálculo o también este otro Introducción al Lambda-cálculo

4) La Programación Lógica

Introducción

   Un programa lógico consta de un conjunto de fórmulas lógicas que expresan propiedades satisfechas por un cierto problema.
   En el caso más habitual, estas fórmulas pertenecen a un subconjunto de la lógica de predicados de primer orden conocido como cláusulas de Horn. Una cláusula de Horn es una implicación lógica de la forma:

   A?B1?. . . ? Bn
   donde A y los Bi son predicados atómicos posiblemente con variables
   Una misma variable X puede aparecer en varios de los predicados atómicos. Se entiende entonces que la implicación es cierta cualesquiera que sean los valores asignados a la variable X y al resto de las variables que aparezcan en la fórmula.

Un programa lógico de relaciones familiares


1) descendiente(X,Y) :- hijo(X,Y).
2) descendiente(X,Y) :- hijo(Z,Y), descendiente(X,Z).
3) hermano(X,Y) :- hijo(X,Z), hijo(Y,Z), X /= Y.
4) sobrino(X,Y) :- hermano(Y,Z), descendiente(X,Z).
5) hijo(miguel,pedro).
6) hijo(sonia,pedro).
7) hijo(sonia,juana).
8) hijo(laura,juana).
9) hijo(luis, sonia).
10) hijo(antonio,sonia).
11) hijo(olga,luis).
12) hijo(diana,antonio).

Características de la Programación Lógica.



El predicado hijo(X,Y) expresa la relación “X es hijo de Y”. El mismo criterio se aplica a las relaciones descendiente, hermano y sobrino.

La ejecución de un programa lógico consiste en plantearle “preguntas” u objetivos, para averiguar si se deducen del programa.

Varias respuestas ante una misma pregunta (no determinismo):

hermano(sonia,X)? -> X = miguel; X = laura

Ejecución reversible:

descendiente(X,pedro)? versus descendiente(diana,Y)?

Ejecución mediante pasos de resolución, que pueden entenderse como pasos de deducción lógica dirigida por objetivos.

Abstracción en gran parte de la secuencia de ejecución, aunque algún control es necesario para no caer en búsquedas infinitas.

A diferencia del paradigma imperativo, se puede verificar la corrección de cada cláusula independientemente de las otras.

5) Programación con Restricciones

La programación de restricciones es una tecnología software utilizada para la descripción y posterior resolución efectiva de grandes y complejos problemas, particularmente combinatorios, de muchas áreas de la vida real. Muchos de estos problemas pueden modelarse como problemas de satisfacción de restricciones (CSPs)y resolverse usando técnicas de programación de restricciones(ecuaciones). Esto incluye problemas de areas tales como inteligencia artificial, investigación operativa, bases de datos, sistemas expertos, etc. Algunos ejemplos son scheduling, planificacion, razonamiento temporal, diseño en la ingeniera, problemas de empaquetamiento, criptografía, diagnosis, toma de decisiones, etc.

Durante los últimos años, la programacion de restricciones ha generado una gran expectación entre expertos de muchas áreas debido a su potencial para la resolución de grandes problemas reales. Por ello, no es de sorprender, que la ACM (Association for Computer Machinery) ha identicado a la programación de restricciones como una de las direcciones estratégicas en la investigación informática. Sin embargo, al mismo tiempo, se considera la programación de restricciones como una de las tecnologías menos conocida y comprendida.

Resilución del CSP

La resolución de un problema de satisfacción de restricciones (CSP) consta de dos fases diferentes:

   Modelar el problema como un problema de satisfacción de restricciones. La modelización expresa el problema mediante una sintaxis de CSPs, es decir, mediante un conjunto de variables, dominios y restricciones del CSP.
   Procesar el problema de satisfacción de restricciones resultante. Una vez formulado el problema como un CSP, hay dos maneras de procesar las restricciones:
       Técnicas de consistencia. Se trata de técnicas para la resolución de CSPs basadas en la eliminación de valores inconsistentes de los dominios de las variables.
       Algoritmos de búsqueda. Estos algoritmos se basan en la exploración sistemática del espacio de soluciones hasta encontrar una solución o probar que no existe tal solución.

Las técnicas de consistencia o inferenciales permiten deducir información del problema, (niveles de consistencia, valores posibles de variables, dominios mínimos, etc.), aunqueen general se combinan con las técnicas de b&úacute;squeda, ya que reducen el espacio de soluciones y los algoritmos de b&úacute;squeda exploran dicho espacio resultante.

Modelización del CSP


Generalmente la declaración de un problema se suele expresar de muchas maneras diferentes, e incluso en lenguaje natural. Una parte muy importante para la resolución de problemas de la vida real es el modelado del problema en términos de CSPs, es decir, variables, dominios y restricciones. A continuación consideraremos un ejemplo en el cual veremos distintas modelizaciones de un mismo problema y las ventajas de una modelización adecuada para resolverlo.

Consideremos el conocido problema criptografíco 'send+more=money' . El problema puede ser declarado como: asignar a cada letra {s, e, n, d, m, o,r, y} un dígito diferente del conjunto {0,...,9} de forma que se satisfaga
send+more=money.

La manera más facil de modelar este problema es asignando una variable a cada una de las letras, todas ellas con un dominio {0,...,9} y con las restricciones de que todas las variables toman valores distintos y con la correspondiente restricción para que se satisfaga 'send+more=money'.

De esta forma las restricciones (no binarias) son:

• 103(s+m)+102(e+o)+10(n+r)+d+e = 104m + 103o + 102n + 10e + y;
• restriccion de todas diferentes (s; e; n; d, m; o; r; y);

Para el algoritmo más general como es Backtracking (BT), este modelo no es muy eficiente porque con BT, todas las variables necesitan ser instanciadas antes de comprobar estas dos restricciones. De esta manera no se puede podar el espacio de búsqueda para agilizar la búsqueda de soluciones. Además, la primera restricción es una igualdad en la que forman parte todas las variables del problema (restricción global) por lo que dificulta el proceso de consistencia.

Veamos a continuación un modelo más eficiente para resolver el problema. Este modelo utiliza los bit de acarreo para descomponer la ecuación anterior en una colección de pequeñas restricciones.

Tal y como está planteado el problema, M debe de tomar el valor 1 y por lo tanto S solamente puede tomar valores de {1, . . . , 9}. Además de las variables del modelo anterior, el nuevo modelo incluye tres variables adicionales, c1; c2; c3 que llamaremos 'portadoras'. Los dominios de las variables e, n, d, o, r e y son {0, . . . , 9}, el dominio de s es {1, . . . , 9}, el dominio de m es {1}, y los dominios de las variables portadores c1; c2; c3 son {0, 1}. Con la ayuda de las variables portadores, la restricción de la ecuación anterior puede descomponerse en varias restricciones más pequeñas:

• e + d = y + 10c1;
• c1 + n + r = e + 10c2;
• c2 + e + o = n + 10c3;
• c3 + s + m = 10m + o.
• restricción de todas diferentes (s; e; n; d, m; o; r; y);

La ventaja de este modelo es que estas restricciones más pequeñas pueden comprobarse antes en la búsqueda de backtracking, y as podarse muchas inconsistencias.

En las dos formulaciones anteriores, la restricción de todas diferentes puede reemplazarse por un conjunto de pequeñas restricciones, es decir e ? s; :::; r ? y, obteniendo as un modelo alternativo.

Como hemos visto en las formulaciones anteriores, dependiendo de la transformación que se haga del problema planteado en lenguaje natural a la modelización en forma de CSP, el problema se
resolvera con más o menos eficiencia.

Un problema con restricciones contiene los siguientes elementos:

Un conjunto de variables-incógnita X1, . . . , Xn.

Un conjunto de dominios D1, . . . ,Dn en los que, respectivamente, toman valores dichas variables.

Un conjunto de restricciones Ci (Xj1 , . . . , Xjni), 1 = i = m. Cada restricción representa una relación entre los valores admisibles de las variables involucradas, es decir, para todo i, Ci  ?  Dj1 x . . . x Djni.

Las restricciones pueden ser sobre números reales (programación lineal), sobre números enteros (programación lineal entera), o sobre dominios finitos (resolutores especializados).


Ejemplo de restricciones sobre dominios finitos: Colocar n reinas en un tablero de ajedrez n x n sin que se den jaque.
Variables X1, . . . , Xn que representan las columnas ocupadas por las n reinas.
Los dominios son los intervalos Di = {1, . . . ,  n}.
Las restricciones son las siguientes:
- distintas (X1, . . . , Xn), que expresa que las columnas de las n reinas reinas han de ser diferentes.
- Xi - Xj | ? |i - j| para todo par (i , j), i ? j, de reinas, que expresa que las diagonales ocupadas por dos reinas cualesquiera han de ser distintas.

6) La Programación Funcional

La abstracción sobre la arquitectura de John von Neuman ha influido en la evolución de los lenguajes, desde los ensambladores hasta los orientados a objetos. Una filosofía distinta a la empleada por estos lenguajes es la empleada en la programación funcional, donde no aparece (o no debería aparecer) el concepto de variable mutable que es reemplazado por el concepto de función matemática como entidad de primera clase: son pasadas como argumentos a otras funciones, o devueltas como resultado, aparecen en estructuras de datos, etc. Así, programar en un estilo funcional consiste básicamente en definir funciones a partir de otras más sencillas, componiéndolas. La semántica de una función se puede identificar con el conjunto de valores que computa a partir de ciertas entradas, y el valor de una función no depende del momento en que se evalúa. El concepto de variable es el de la matemática: una variable denota un mismo valor; las variables pueden utilizarse para denotar, tanto los argumentos de las funciones como otras funciones, y las funciones pueden definirse a partir de estas variables.

El uso de funciones para crear programas, junto con operaciones básicas (composición, recursión y condicional) es la esencia de la programación funcional; pero a ello hay que añadir una propiedad fundamental: la transparencia referencial, es decir, el valor de una función depende únicamente de los valores de sus argumentos, las variables no pueden representar valores diferentes, y una vez que a una variable se le asigna un valor, éste no puede cambiar. Los lenguajes funcionales con tal propiedad se llaman aplicativos puros aunque algunos autores incluyen tal propiedad en el término “lenguaje funcional”; esta es una diferencia fundamental con los llamados lenguajes imperativos ya que la ausencia de variables mutables prohíbe los efectos laterales y el cómputo de una función puede realizarse por reescritura o reducción: sustitución de llamadas a funciones (según su definición) por los argumentos. Estamos hablando lógicamente de un lenguaje funcional puro; por razones de eficiencia algunos lenguajes (p.e. LisP) incluyen ciertas características imperativas, como las variables mutables.

La noción de igualdad es otra característica fundamental. Dos expresiones se consideran iguales si se pueden transformar una en otra por reescritura. Para garantizar cómputos deterministas es necesario añadir la propiedad de confluencia, y ésta queda asegurada en aquellas clases de sistemas de reescritura que resultan ser ortogonales [Klop, 1992], en los cuales, la ortogonalidad puede verificarse fácilmente mediante condiciones sintácticas. Los sistemas de reescritura también se utilizan para modelar otras características en programación funcional.

La transparencia referencial garantiza que esta igualdad sea sustitutiva, de forma que las expresiones pueden ser manipuladas como entidades matemáticas, utilizando leyes algebraicas conocidas. Esto dota al programador de un marco conceptual simple y suficientemente expresivo que le permite verificar y transformar programas en forma algebraica. Así, los lenguajes funcionales basados en un ?–cálculo extendido junto con la correspondiente semántica operacional proporciona un concepto de igualdad junto con un comportamiento que puede ser utilizado para definir técnicas de transformación de programas en forma correcta.

Resumiendo las características de la Programación Funcional actual

   Ausencia de estado mutable:  Ejecutar=Simplificar una expresión
   No hay control de secuencia, salvo la implícita en las dependencias de datos
   El recorrido recursivo de las estructuras de datos se encapsula en funciones de orden superior. Con ello se dispone de un amplio catá logo de bloques genéricos reutilizables.
   Numerosas funciones de orden superior predefinidas, especialmente para listas. El programador puede añadir nuevas funciones de orden superior.
   Sofisticado sistema polimórfico de tipos, con sobrecarga definida por el programador. No es imprescindible declarar los tipos. Algoritmo de inferencia automática.
   Gestión implícita de la memoria basada en un recolector de basura.
   Sintaxis muy concisa, lo que elimina líneas de código.
   Programar se parece más a componer piezas que a crear código nuevo.

Aportaciones de la Programación Funcional.


a) El orden superior


- Consideremos la definición de la función que suma los elementos de una lista:

suma [ ] = 0

suma (x : xs) = x + suma xs

- El patrón que sigue es común a otras funciones que se aplican a listas: operar la cabeza de la lista, con el resultado de aplicar recursivamente la función definida al resto de la lista. Si la lista es vacía, devolver una constante.

- Las únicas partes de la definición que son específicas del cálculo de la suma son las que están recuadradas.

- El orden superior permite separar de modo eficaz los dos aspectos presentes en la definición:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
suma = foldr (+) 0
producto = foldr (*) 1
length = foldr g 0  where g x n = 1 + n
busca y = foldr g False where g x e = y == x || e

b) El sistema polimórfico de tipos


- Los sistemas de tipos comenzaron siendo un factor de seguridad de los lenguajes.

- Los sistemas polimórficos (R. Milner, 1978) añaden otra dimensión, la generalidad: si un código admite muchos tipos distintos, se puede usar con seguridad en muchos contextos distintos. Cuanto más general sea un tipo, tanto más reutilizable será el componente que lo posea.

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

- La segunda aportación es el algoritmo de inferencia automática: si una definición es tipable, al algoritmo calcula el tipo más general posible para ella. Si no es tipable, el algoritmo da error.

- Esta característica es, de momento, exclusiva del paradigma funcional.

c) La evaluación perezosa


- La evaluación perezosa es otra “cola de pegar” que permite ensamblar juntas piezas de un programa funcional que de otro modo serían disjuntas: separa la generación de los datos, de su consumo, permitiendo que una función distinta se ocupe de cada uno de ellos:

(!!) :: [a] -> Int -> a
(x:xs) !! 0 = x
ç(x:xs) !! i = xs !! (i-1)
scanl :: (b -> a -> b) -> b -> [a] -> [b]
scanl f z [] = [z]
scanl f z (x:xs) = z : scanl f (f z x) xs
cuadrado :: Num a => a -> a
cuadrado n = (scanl (+) 0 [1,3..]) !! n

- Programas que no terminan bajo evaluación impaciente, lo hacen bajo evaluación perezosa.

- Permite definir y utilizar estructuras de datos infinitas.

- Permite definir funciones no estrictas, es decir, funciones que pueden dar un resultado definido aunque algunos de sus parámetros estén indefinidos.

Principales lenguajes declarativos

Haskell (Programación funcional)
ML (Programación funcional
Lips (Programación funcional)
Prolog(Programación Lógica)
F-Prolog(Programación Lógica Difusa)
Curry (Programación Lógico-Funcional)
Y otros como HOPE, SML, SASL, KRC, Miranda, etc.



Por Antonio Damigo

Bibliografía

Rafael del Vado Vírseda (Departamento de Sistemas Informáticos y Computación – U.C.Madrid)
Carlos Alberto Romero Díaz (Departamento de Sistemas Informáticos y Computación – U.C.Madrid)
Ricardo Peña Marí (Sistemas Informáticos y Computación-U.C.Madrid)
Blas Carlos Ruiz Jiménez (Departamento de Lenguajes y Ciencias de la Computación – U.Malaga)
Federico Barber (Departamento de Sistemas Informáticos y Computación – U.P.Valencia)
Miguel A. Salido (Departamento de Ciencias de la Computación e Inteligencia Artificial– U.Alicante)


Añadir comentario