Tesis

T´ecnicas de diagn´ostico y depuraci´on declarativa
para lenguajes l´ogico-funcionales
Rafael Caballero Rold´an
Departamento de Sistemas Inform´aticos y Programaci´on
Universidad Complutense de Madrid

Memoria presentada para optar al t´ıtulo de:
Doctor en C.C. Matem´aticas
Director:
Mario Rodr´ıguez Artalejo
Tribunal de Lectura:
Presidente: Ricardo Pe˜na Mar´ı

U.C. Madrid

Secretario:

ManuelGarc´ıa Clavel

U.C. Madrid

Vocales:

Herbert R. Kuchen

U. M¨unster

Manuel Hermegildo Salinas U.P. Madrid
Mar´ıa Alpuente Frasnedo

Madrid, 2004

U.P. Valencia

ii

´Indice
´
Indice

III

Resumen
1. Introducci´
on
1.1. Motivaci´on . . . . . . . . . . . . .
1.1.1. Programaci´on Declarativa .
1.1.2. Herramientas de Desarrollo
1.1.3. Depuraci´on Declarativa . .
1.2. Objetivos . . . . . . . . . .. . . .
1.3. Estructura de la Tesis . . . . . . .

VIII

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

2. Panor´
amica de la Depuraci´
on Declarativa
2.1. Programaci´on L´ogica y Programaci´on L´ogica con Restricciones
2.1.1. Un poco dehistoria . . . . . . . . . . . . . . . . . . . .
2.1.2. Programaci´on l´ogica con restricciones . . . . . . . . . .
2.1.3. Preliminares . . . . . . . . . . . . . . . . . . . . . . . .
2.1.4. S´ıntomas y Errores . . . . . . . . . . . . . . . . . . . . .
2.1.5. C´alculos P OS y N EG . . . . . . . . . . . . . . . . . . .
2.1.6. Diagnosis mediante ´arboles de prueba . . . . . . . . . .
2.1.7. Aspectosrelacionados con la implementaci´
on . . . . . .
2.1.8. Sistemas . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.9. Diagnosis Abstracta . . . . . . . . . . . . . . . . . . . .
2.2. Un Esquema para la Depuraci´on Declarativa . . . . . . . . . .
´
2.2.1. Arboles
de C´omputo . . . . . . . . . . . . . . . . . . . .
2.2.2. Instancias del Esquema . . . . . . . . . . . . . . . . . .
2.3.Programaci´on Funcional . . . . . . . . . . . . . . . . . . . . . .
2.3.1. Depuraci´on Declarativa de
Lenguajes Funcionales Perezosos . . . . . . . . . . . . .
2.3.2. El EDT . . . . . . . . . . . . . . . . . . . . . . . . . . .

iii

.
.
.
.
.
.

1
1
2
2
3
4
5

.
.
.
.
.
.
.
.
.
.
.
.
.
.

7
7
7
8
9
10
13
19
23
26
26
27
27
28
29

. . . . . . .
. . . . . . .

30
31

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
..
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

2.3.3. Sistemas . . . . . . . . . . . . . . . . .
2.3.4. Otras Propuestas . . . . . . . . . . . .
2.4. Programaci´on L´ogico-Funcional . . . . . . . .
2.4.1. Depuraci´on Declarativa deLenguajes
L´ogico-Funcionales . . . . . . . . . .
2.4.2. Respuestas Incorrectas en PLF . . . .
2.4.3. Respuestas Perdidas en PLF . . . . .
2.4.4. Otras Propuestas . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .

34
36
38

.
.
.
.

38
39
41
44

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
..
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

Parte I: Marco Te´
orico para la Depuraci´
on de Respuestas Incorrectas en
PLF
´
3. Arboles
de Prueba Positivos para Programaci´
on L´
ogico-Funcional
46
3.1. Preliminares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
3.1.1. Tipos y Signaturas . . . . . . . . . . . . . . . . . . . . . . . . . . . .
473.1.2. Expresiones y Patrones . . . . . . . . . . . . . . . . . . . . . . . . .
48
3.1.3. Sustituciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
3.1.4. Expresiones Bien Tipadas . . . . . . . . . . . . . . . . . . . . . . . .
50
3.1.5. Programas Bien Tipados . . . . . . . . . . . . . . . . . . . . . . . . .
51
3.1.6. Un Programa Sencillo . . . . . . . . . . . . . . . . . ....