PDF de programación - Programación Declarativa

Programación Declarativa

Pascual Julián Iranzo

Dep. de Informática. Univ. de Castilla-La Mancha.

Paseo de la Universidad, 4. 13071 Ciudad Real, España.

email: [email protected]

Primera versión:
Primera revisión:
Segunda revisión:

3-Septiembre-2000
2-Enero-2002
24-Octubre-2007

1

2

Capítulo 1

Introducción.

En este capítulo estudiaremos las características más nota-
bles de los lenguajes de programación convencionales y de
los lenguajes de programación declarativos.

Objetivos:

1. Entender qué son los lenguajes declarativos y qué apor-

tan de nuevo.

2. Establecer su ámbito de aplicación.

3

1.1. Computadores y Lenguajes de Programación Conven-

cionales.

Los lenguajes convencionales son una abstracción de alto
nivel del tipo de máquina para el que se han desarrollado.

Muchos de sus defectos e imperfecciones provienen de esta
estrecha relación con las máquinas que los sustentan.

1.1.1. Organización de los computadores.

Los computadores que siguen el modelo de organización de
von Neumann están constituidos por los siguientes componen-
tes internos:

1. Unidad central de proceso (UCP)

2. Memoria central (MC)

3. Procesadores de dispositivos periféricos

4. El bus del sistema.

4

UCPMCProcesadores E/SBus del sistema Computadores y Lenguajes de Prog. Convencionales.

La UCP está dividida en cuatro componentes funcionales,
que están unidos por buses internos y líneas de control:
• Los registros

• La unidad de control (UC): rige el comportamiento del
computador mediante la interpretación y secuenciamien-
to de las instrucciones que lee de la MC.

• La unidad aritmético lógica (UAL): realiza un número
muy limitado de operaciones (lógicas, como AND, OR,
y NOT; aritméticas como ADD; y desplazamientos).

• Un reloj

Existe una correspondencia entre los dos componentes prin-
cipales de la UCP, la UC y la UAL, y el tipo de informa-
ciones que almacena la MC, instrucciones y datos.
• La UC trata las instrucciones

• la ALU los datos.

5

Computadores y Lenguajes de Prog. Convencionales.

La MC puede considerarse como un conjunto de celdas
(llamadas palabras), cada una de ellas con la capacidad de
almacenar una información: dato o instrucción.
• La propiedad esencial de la memoria que nos interesa es
su capacidad de ser direccionada.

• Las celdas pueden considerarse numeradas y la UC cono-
ce cada celda por su número, llamado dirección.

6

UALCPRegistrosRPMicroprogramaLEC./ESC.Selec.PalabraMCDatos MC-UCPBus de SistemaUnidad Central de Proceso Computadores y Lenguajes de Prog. Convencionales.

El bus del sistema es un conjunto de conductores para-
lelos a través de los cuales transcurren una serie de señales
eléctricas que se intercambian entre los componentes del
sistema.
• Ventaja: la organización en torno a un bus único es la
menos costosa de las organizaciones.

• Desventaja: “cuello de botella de von Neumann”.

• Desventaja: gran parte del tráfico no es útil para el
cómputo (son direcciones de donde se encuentran las
instrucciones y los datos a procesar).

7

Computadores y Lenguajes de Prog. Convencionales.

El modelo de organización y funcionamiento de los compu-
tadores que acabamos de describir conduce a un modelo de
cómputo en el que:

1. Los procesadores ejecutan las intrucciones de un modo pu-

ramente secuencial (salvo rupturas de secuencia)
=⇒
los lenguajes convencionales son dificiles de paralelizar.

2. se realiza una completa separación entre el tipo de informa-
ciones que almacena la MC, dividiendolas en instrucciones
y datos
=⇒
repercusión sobre el diseño de los lenguajes convencionales.

3. se introduce el concepto de estado de la computación (de-
bido al uso de registros para realizar las operaciones de la
UCP y la visión de la MC como un conjunto de palabras).

8

1.1.2. Características de los lenguajes convencionales

Los lenguajes convencionales (o imperativos) están inspi-
rados en la arquitectura de von Neumann.

los distintos recursos expresivos proporcionados por tales
lenguajes pueden verse como abstracciones de los compo-
nentes de la máquina de von Neumann o de sus operaciones
elementales:
1. variables ⇐⇒ celdas de la MC / registros;

2. registro (o estructura) / arrray ⇐⇒ conjunto contiguo

de celdas de la MC;

3. instrucciones de control ⇐⇒ intrucciones de salto con-

dicional o incondicional del lenguaje máquina;

4. instrucción de asignación ⇐⇒ intrucciones LOAD+STORE

o MOVE del lenguaje máquina.

La instrucción de asignación resulta ser representativa del
cuello de botella de von Neumann y nos obliga a pensar en
términos de trasiego de información entre celdas de memo-
ria.

la instrucción de asignación separa la programación en dos
mundos: Expresiones / Instrucciones.

direcciones = expresión.

9

Computadores y Lenguajes de Prog. Convencionales.

Podemos distinguir dos aspectos fundamentales en las ta-
reas de programación:
• Aspectos lógicos: Esto es, ¿Qué debe computarse?).
Esta es la cuestión esencial.

• Aspectos de control:

◦ Organización de la secuencia de cómputos en pe-
queños pasos.

◦ Gestión de la memoria durante la computación.

Kowalski y otros son partidarios de la independencia de los
aspectos lógicos y de control.

Atendiendo a este criterio de independencia podemos elevar
algunas críticas sobre el uso de los lenguajes imperativos:

1. La presencia de instrucciones de control de flujo y las
operaciones de gestión de memoria obscurecen el conte-
nido lógico del programa.

2. La operación de asignación utiliza las variables de modo

matemáticamente impuro:

x = x+1.

Permite la introducción de efectos laterales.

3. Dejar las cuestiones de control al programador no parece

lo más indicado.

10

Computadores y Lenguajes de Prog. Convencionales.

Ejemplo 1 Concatenación de dos listas.

#include <stdio.h>
#include <stdlib.h>
typedef struct nodo
{

char dato;
struct nodo *enlace;
} LISTA;
void mostrar(LISTA *ptr);
void insertar(LISTA **ptr, char elemento);
LISTA *crear lista();
LISTA *concatenar(LISTA *ptr1, LISTA *ptr2);
void main()
{

LISTA *l1, *l2, *lis = NULL;
l1 = crear lista();
l2 = crear lista();
lis = concatenar(l1, l2);
printf("\n La nueva lista enlazada es: ");
mostrar(lis);

}
void mostrar(LISTA *ptr)
{

while(ptr != NULL)
{

printf(" %c",ptr->dato);
ptr = ptr->enlace;
}
printf("\n");

}
void insertar(LISTA **ptr, char elemento)
{

LISTA *p1, *p2;
p1 = *ptr;
if(p1 == NULL)

11

{

p1 = malloc(sizeof(LISTA));
if (p1 != NULL)
{

p1->dato = elemento;
p1->enlace = NULL;
*ptr = p1;

}

}
else
{

while(p1->enlace != NULL) p1 = p1->enlace;
p2 = malloc(sizeof(LISTA));
if(p2 != NULL)
{

p2->dato = elemento;
p2->enlace = NULL;
p1->enlace = p2;

}

}

}
LISTA *crear lista()
{

LISTA *lis = NULL;
char elemento;
printf("\n Introduzca elementos: ");
do{
elemento = getchar();
if(elemento != ’\n’) insertar(&lis, elemento);
} while(elemento != ’\n’);
return lis;
}LISTA *concatenar(LISTA *ptr1, LISTA *ptr2)
{ LISTA *p1;
p1 = ptr1;
while(p1->enlace != NULL) p1 = p1->enlace;
p1->enlace = ptr2;
return ptr1;

}

12

Computadores y Lenguajes de Prog. Convencionales.

Este programa ilustra y concreta algunas de las propiedades
de los lenguajes convencionales ya mencionadas junto a otras
nuevas:

1. Es una secuencia de instrucciones que son ordenes a la
máquina que operan sobre un estado no explícitamente
declarado (lenguajes imperativos).

2. Para entender el programa debemos ejecutarlo mentalmen-
te siguiendo el modelo de computación de von Neumann,
estudiando como cambian los contenidos de las variables y
otras estructuras en la MC.

3. Es necesario gestionar explícitamen la MC: llamada al sis-

tema malloc() y empleo de variables de tipo puntero.

4. El programa acusa una falta de generalidad debido a la
rigidez del lenguaje a la hora de definir nuevos tipos de
datos ( sólo concatena listas de caracteres).

5. La lógica y el control están mezclados, lo que dificulta la

verificación formal del programa.

13

Computadores y Lenguajes de Prog. Convencionales.

Hemos puesto de manifiesto los puntos débiles, sin embargo

reunen otras muchas ventajas:

1. eficiencia en la ejecución;

2. modularidad;

3. herramientas para la compilación separada;

4. herramientas para la depuración de errores;

5. son los lenguajes preferidos en amplias áreas de aplicación:

a) computación númerica,

b) gestión y tratamiento de la información,

c) programación de sistemas

14

1.2. Programación Declarativa.

La programación declarativa es un estilo de programación
en el que el programador especifica qué debe computarse
más bien que cómo deben realizarse los cómputos.

“programa = lógica + control” (Kowalski)
(“algoritmos + estructuras de datos = programas” (Wirth))

El componente lógico determina el significado del programa
mientras que el componente de control solamente afecta a
su eficiencia.

la tarea de programar consiste en centrar la atención en la
lógica dejando de lado el control, que se asume automático,
al sistema.

La característica fundamental de la programación declara-
tiva es el uso de la lógica como lenguaje de programación:
• Un programa es una teoría formal en una cierta lógica,
esto es, un conjunto de fórmulas lógicas que resultan ser
la especificación del problema que se pretende resolver,
y

• la computación se entiende como una forma de inferen-
cia o deducción en dicha lógica.

15

Programación Declarativa.

Los principales requisitos que debe cumplir la lógica em-
pleada son:

1. disponer de un lenguaje que sea suficientemente expre-

sivo;

2. disponer de una semántica operacional (un mecanismo

de cómputo que permita ejecutar los programas);

3. disponer de una semántica declarativa que permita dar
un significado a los programas de forma independiente
a su posible ejecución;

4. resultados de corrección y completitud.

Según la clase de lógica que empleemos como fundamento
del lenguaje declarativo obtenemos los diferen