Tare 1: Lenguajes de programación funcionales y lógicos.

1. Paradigma de programación funcional

La principal base teórica del paradigma funcional es el cálculo desarrollado en la
década de los 30 por Alonzo Church como modelo de computación con el mismo
poder computacional que una Máquina de Turing. El cálculo lambda proporciona una
notación muy simple (pero bastante críptica al mismo tiempo) de definición de
funciones matemáticas. Sólo son necesarias tres reglas sintácticas para definir las
expresiones del cálculo lambda:
expresión-lambda ::= variable | constante | abstracción | aplicación
abstracción ::= lambda variable.expresión-lambda
aplicación ::= (expresión-lambda)expresión-lambda
La abstracción sirve para construir nuevas funciones matemáticas en base a
expresiones previamente definidas. La aplicación, como su nombre indica, denota
la aplicación de una función.
Los lenguajes funcionales se basan en la declaración de funciones aritméticas, trata
de ser un lenguaje expresivo y matemáticamente elegante. Los programas escritos
en lenguajes funcionales están compuestos únicamente por la definición de
funciones, pero no se trata de subrutinas de un programa iterativo, sino más bien
como funciones puramente matemáticas. Son aquellos lenguajes donde las
variables no tienen estado, no hay cambios en éstas a lo largo del tiempo, son
inmutables y no pueden cambiarse los valores a lo largo de la ejecución. Además
los programas se estructuran componiendo expresiones que se evalúan como
funciones.

1.1. Caracteristicas de los lenguajes de programación funcionales

La potencia de los lenguajes de programación funcionales depende de varias
características que poseen; entre ellas: el manejo de funciones de alto orden, la
declaración de tipos algebraicos, la inferencia de tipos, el emparejamiento de
patrones y el manejo automático de la memoria dinámica. Estas características no
son exclusivas de los lenguajes funcionales; en el caso del emparejamiento de
patrones esta facilidad fue tomada de Prolog. El manejo automático de la memoria
dinámica, aunque tiene su origen en un lenguaje funcional, LISP, hoy en día lo
poseen lenguajes imperativos como JAVA; sin embargo todas estas características
han estado ligadas estrechamente al desarrollo de la programación funcional.
 Funciones de alto orden
Cualquier lenguaje funcional permite la definición de nuevas funciones como
forma de abstracción, y la evaluación de expresiones como forma de
 computación. El concepto "alto orden" se refiere a funciones que reciben
como argumento o retoman funciones, es decir, las funciones pueden
manipulase como datos; esta característica también es referida como
"funciones como objetos de primera clase."

 Tipos algebraicos
Los lenguajes funcionales con tipos como ML y Haskell dan la posibilidad de
declarar tipos adicionales a los tipos primitivos (int, char, float, etc.). Los tipos
declarados por el usuario se definen mediante constructores como la
enumeración:
let dirección = norte I sur I oriente I occidente;;
El producto cartesiano de tipos ya definidos o primitivos:
let racional = fraccion of int *int;;
Definiciones recursivas:
let lista = vacia I cons ofint *lista ;;
La recursividad es la que le da el nombre de algebraico al sistema de tipos y
le permite al programador definir y manejar estructuras bastante complejas,
sin necesidad de manipular apuntadores; esto elimina la gestión directa de
la memoria dinámica y, por tanto obvia, una gran fuente de errores. Además
es importante para expresar funciones que en otros lenguajes se expresan
con iteraciones. Muchas veces es más sencillo y natural utilizar una recursión
en la definición de una función.

 Emparejamiento de patrones
El emparejamiento de patrones, se refiere a la posibilidad que brindan
algunos lenguajes funcionales de definir funciones por casos; esto le da
mayor capacidad expresiva al lenguaje permitiendo escribir el código más
claro, sencillo y conciso.

 Inferencia de tipos
Tradicionalmente, los sistemas de tipos de los lenguajes de programación se
han dividido en dos: estrictos y no estrictos. En el primer caso, el
programador debe declarar el tipo de cada una de las variables y de los
argumentos de las funciones y procedimientos, y ceñirse de manera estricta
a estas declaraciones; en el segundo caso, el programador no debe ceñirse
necesariamente a las declaraciones' y eventualmente las puede obviar,
 como cuando a una función declarada en C que recibe un entero, se le envía
como argumento un número de punto flotante.
La experiencia ha demostrado que los sistemas de tipos estrictos son
preferibles a los no estrictos, pues favorecen la depuración sencilla del
código al eliminar en tiempo de compilación muchos errores potenciales; sin
embargo pueden resultar muy engorrosos para el programador por su falta
de flexibilidad.
Los sistemas de inferencia de tipos representan un punto intermedio entre
los dos esquemas mencionados anteriormente. Por un lado, conservan el
carácter estricto del sistema de tipos y por otro liberan al programador de
declaraciones explícitas de los tipos de los argumentos de las funciones y de
sus valores de retomo. Esto puede parecer contradictorio, pero la clave está
en que el compilador hace el trabajo de asignación de tipos por el
programador y, lo que es mejor, lo hace de la manera más general posible,
es decir, evidenciando la genericidad y el polimorfismo cuando éstos tienen
cabida dentro de una función.

1.2. Lisp como lenguaje de programación funcional

Lenguaje de programación popular especificado por John McCarthy y colaboradores
en el MIT en 1958. Su popularidad se basa especialmente en el empleo del lenguaje
de programación para el concepto de inteligencia artificial. Como su nombre lo dice,
List Processing, es un lenguaje que se basa casi exclusivamente en el uso de listas
y métodos recursivos complementarios a la solución de los problemas. Además de
esto, utiliza como un recurso común los paréntesis, con los cuales se definen todos
los métodos posibles. Lisp fue un lenguaje pionero en su tiempo, dando conceptos
sobre estructuras de datos como los árboles, el manejo de almacenamiento
automático, tipos dinámicos y el compilador autocontenido.
1.2.1. Principales Características
La característica principal de LISP es que todo programa consiste de una
función.
Algunas características:
 Objetos de datos
o Tipos de datos primitivos: átomos. Cada átomo tiene una lista de
propiedades asociada, accesible a través del puntero que almacena
el nombre del átomo. No se distinguen mayúsculas y minúsculas para
identificadores.
 o Tipos de datos estructurados: listas. Tienen asociado un puntero al
primer elemento (car) y otro al elemento siguiente (cdr). Una lista
vacía apunta a nil. Para la asignación se utiliza setq(x val).
o Representación y almacenamiento: Cada descriptor de un objeto de
datos proporciona tipo y atributos. En los datos estructurados (listas)
se tienen sólo punteros a primero y a siguiente.
 Control de secuencia
o El traductor LISP es una función read () que toma el fuente del fichero
y lo interpreta.
o La ejecución del programa consiste en la evaluación de las funciones
contenidas en el mismo.
o Expresiones:
 Condicional
 Operaciones sobre átomos (en preorden): +, -, *, /
 Operaciones sobre listas: cons, car, cdr, list, replace, null,
equal.
 Operaciones sobre propiedades: put, get.
 Enunciados: prog() para ejecución secuencial.
 Entrada y salida: open(), read(), print().
 Definición de funciones: defun, define.
 Gestión de subprogramas
o Tres clases de funciones:
 Función interpretada, en forma de estructura de listas.
Primitivas eval y apply.
 Función compilada, compiladas en un bloque de código
máquina que puede ser ejecutado por el intérprete del
hardware.
 Macro, se declara con define. Es simplemente una función
ordinaria en LISP. Puede ser interpretada y compilada.
 Gestión de almacenamiento
o La memoria se estructura en forma de montículo, que maneja
unidades de una palabra de tamaño fijo usando una lista de espacios
libres y un recolector de basura.
o Entorno de referencia:
 Local, es el que se da en las listas, como asociaciones de
átomos relacionados de una determinada manera.
  Global o común, se consigue mediante asociación de un
átomo con una propiedad del mismo que contiene un puntero
al datos referenciado. Se usa set y setq.
o Paso de parámetros:
 Transmisión por valor, consiste en evaluar las expresiones de
una lista de parámetros y transmitir los valores resultantes.
 Transmisión por nombre, transmitir las expresiones de la lista
de parámetros sin evaluar, y dejar que la función llamada los
evalue usando eval. En funciones macro la transmisión por
nombre es la norma. Para funciones lambda se puede
especificar la transmisión por nombre usando nlambda, en
lugar de lambda.

1.2.2. Funciones en Lisp

 Funciones normales, son las que se suelen incluir en las implementaciones
de LISP (ver manual en cada caso).
 Funciones de lista, para manipulación de listas:
o car L, devuelve el primer elemento de L.
o cdr L, devuelve la cola (lista - primero).
o cons x y, devuelve una lista formada por x e y.
o list x y z, devuelve la lista (x y z).
o quote x, no se evalúa x.
 Predicados
o atom x, devuelve True si x es un átomo.
o numberp x, devuelve True si x es un número.
o greaterp x y, devuelve True si x>y.
o lessp x y, devuelve True si x<y.
o null x, devuelve True si x es nulo.
o and x y, devuelve x and y.
o or x y, devuelve x or y.
o not x, devuelve not x.
o eq x y, devuelve True si x=y.
 Funciones aritméticas:
o +, -, *, y /.
o rem x y, devuelve el módulo x/y (remainder).
 Funciones de entrada y salida
o load nombrearchivo, lee el archivo a memoria.
 o print x, imprime el elemento x.
o open nombrearchivo, abre un archivo y devuelve un puntero al
mismo.
o read, lee del terminal un átomo.
o help, proporciona ayuda.
o trace, traza la función.
o bye, termina LISP.

2. Paradigma de programación lógica

Paradigma de programación basado en la lógica de primer orden. La Programación
Lógica estudia el uso de la lógica para el planteamiento de problemas y el control
sobre las reglas de inferencia para alcanzar la solución automática. La Programación
Lógica, junto con la funcional, forma parte de lo que se conoce como Programación
Declarativa, es decir la programación consiste en indicar como resolver un problema
mediante sentencias, en la Programación Lógica, se trabaja en una forma
descriptiva, estableciendo relaciones entre entidades, indicando no como, sino que
hacer, entonces se dice que la idea esencial de la Programación Lógica es

Programa = Lógica + Control

Se puede ver como una deducción controlada:

 Lógica (programador): hechos y reglas para representar conocimiento

 Control (interprete): deducción lógica para dar respuestas (soluciones)

2.1. Prolog como lenguaje de programación lógica

PROLOG es un lenguaje de programación declarativo. Los lenguajes declarativos
se diferencian de los lenguajes imperativos o procedurales en que están basados
en formalismos abstractos (PROLOG está basado en la lógica de predicados de
primer orden y LISP, otro lenguaje de programación declarativa, en lambda calculo),
y por tanto su semántica no depende de la máquina en la que se ejecutan. Las
sentencias en estos lenguajes se entienden sin necesidad de hacer referencia al
nivel máquina para explicar los efectos colaterales. Por tanto, un programa escrito
en un lenguaje declarativo puede usarse como una especificación o una descripción
formal de un problema. Otra ventaja de los programas escritos en lenguajes
declarativos es que se pueden desarrollar y comprobar poco a poco, y pueden ser
sintetizados o transformados sistemáticamente.
 PROLOG es un lenguaje de programación muy útil para resolver problemas que
implican objetos y relaciones entre objetos. Está basado en los siguientes
mecanismos básicos:
 Unificación
 Estructuras de datos basadas en árboles
 Backtracking automático
La sintaxis del lenguaje consiste en lo siguiente:
 Declarar hechos sobre objetos y sus relaciones
 Hacer preguntas sobre objetos y sus relaciones

 Definir reglas sobre objetos y sus relaciones

2.1.1. Los hechos PROLOG

Para explicar los fundamentos de PROLOG vamos a utilizar el típico ejemplo de las
relaciones familiares.
Para decir que Laura es uno de los dos progenitores de Damián, podríamos declarar el
siguiente hecho PROLOG:
progenitor(laura, damian).
“progenitor” es el nombre de la relación o nombre de predicado y “laura” y “damian” son
los argumentos. Los hechos acaban siempre con punto. Nosotros interpretaremos que
Laura, primer argumento de la relación, es la madre de Damián, segundo argumento de
la relación. Sin embargo, este orden es arbitrario y cada programador puede darle su
propio significado. Los nombres de las relaciones y los argumentos que se refieren a
objetos o personas concretas se escribirán con minúscula.

2.1.2. Las preguntas PROLOG

Sobre un conjunto de hechos se pueden realizar una serie de preguntas. Por ejemplo:
?- le_gusta_a(juan,maria).
PROLOG busca automáticamente en la base de datos si existe un hecho que se puede
unificar (es decir, tiene el mismo nombre de predicado, el mismo número de argumentos
o aridad y cada uno de los argumentos tiene el mismo nombre, uno a uno) con el hecho
que aparece en la pregunta. PROLOG contestará “SI” si encuentra ese hecho y “NO” si
no lo encuentra. La contestación “NO” no implica que el hecho sea falso (aunque sí lo
sea para nuestra base de datos), sino que no se puede probar (en general) que sea
verdadero con el conocimiento almacenado en la base de datos.

2.1.3. Las reglas PROLOG

Existe en PROLOG la posibilidad de definir la relación “abuelo(X,Y)” o la relación
“tio(X,Y)” como reglas, además de poderlo hacer como hechos o como conjunción de
objetivos.
abuelo(X,Y):- progenitor(X,Z), progenitor(Z,Y).
tio(X,Y):- progenitor(Z,Y), progenitor(V,Z), progenitor(V,X).
A la primera parte de la regla se le llama cabeza o conclusión, el símbolo ":-" es el
condicional (SI), y a la parte de la regla que está después de “:-“es el cuerpo o parte
condicional. El cuerpo puede ser una conjunción de objetivos separados por comas.
Para demostrar que la cabeza de la regla es cierta, se tendrá que demostrar que es
cierto el cuerpo de la regla.

Referencias
Escrig, M. T. (s.f.). El Lenguaje de Programación PROLOG.

Osorio, F. A. (s.f.). PROGRAMACION FUNCIONAL: CONCEPTOS y PERSPECTIVAS.

Pérez, K. M. (s.f.). Introducción al lenguaje de programación lógica Prolog .

Programación Funcional en LISP. (s.f.).