PDF de programación - Técnicas Básicas de Programación Prolog

Técnicas Básicas de Programación Prolog

Ingeniería Informática

Ingeniería Técnica en Informática de Sistemas

Departamento de Lenguajes y

Ciencias de la Computación

Universidad de Málaga

Contenido

1. Programación recursiva
2. Recursión de cola y predicados iterativos
3. El paradigma generar/comprobar
4. Relaciones y bases de datos relacionales

Técnicas Básicas de Programación Prolog

2

Programación Recursiva

Recursión y Prolog

Prolog carece de mecanismos iterativos

Prolog emplea la recursión para:

representar información (estructuras recursivas)
procesar la información (relaciones recursivas)

Ejemplo: la aritmética de Peano

objetos  naturales
relaciones  operaciones y relaciones aritméticas

Cuidado: más adelante emplearemos aritmética extra-lógica!

Técnicas Básicas de Programación Prolog

4

Los naturales de Peano

Definición: el conjunto inductivo de los naturales N
1. 0 ∈ N
2. si X ∈ N, entonces θ(X) ∈ N

[base]
[recursivo]

θ representa a la función sucesor θθθθ: N  N

N = {0, θ(0), θ(θ(0)), θ(θ(θ(0))), … }

base

recursivo

Cuidado: θ(θ(θ(0))) ≠ 3, θ es un constructor
Los naturales son recursivos: θ(X) “contiene” a X

Técnicas Básicas de Programación Prolog

5

Representación en Prolog (I)

Necesitamos términos Prolog para representar naturales

Seguimos la definición inductiva de N :
1. 0 ∈ N
2. si X ∈ N, entonces θ(X) ∈ N

[base]
[recursivo]

Caso base  constante c
Caso recursivo  estructura functor s/1

Un natural bien formado es un término Prolog generado por la
gramática GN:

N ::= c

| s(N)

[base]
[recursivo]

Técnicas Básicas de Programación Prolog

6

Representación en Prolog (y II)

Decimal

Peano

0
1
2
3
…
n

0
θ(0)
θ(θ(0))
θ(θ(θ(0)))
…
θ(…(θ(0))…)

Prolog

c

s(c)

s(s(c))

s(s(s(c)))
…
s(…(s(c))…)

n veces

n veces

Ejercicio:
1. ¿qué representa el término s(s(s(X)))?

Técnicas Básicas de Programación Prolog

7

Pero Prolog no tiene tipos

Los siguientes términos no son naturales bien formados:

s(s(f(s(c)))) s(s(a)) s((s(0)))

s(2)

Pero Prolog los acepta porque no podemos restringir la
aplicación del functor s/1

Solución: introducir un predicado es_natural(X) que tenga
éxito cuando X sea un natural bien formado.

Técnicas Básicas de Programación Prolog

8

Definición extensional de es_natural/1

es_natural(c).

es_natural(s(c)).

es_natural(s(s(c))).

es_natural(s(s(s(c)))).

…

Técnicas Básicas de Programación Prolog

9

Definición intensional de es_natural/1

Seguimos la definición inductiva de N :
1. 0 ∈ N
2. si X ∈ N, entonces θ(X) ∈ N

[base]
[recursivo]

es_natural(c).
es_natural(s(X)) :- es_natural(X). [recursivo]

[base]

En general, para cada tipo a representar en Prolog daremos:
1. conjunto de valores (conjunto inductivo N)
2. representación sintáctica (gramática GN)
3. definición de dominio (predicado es_natural/1)

Técnicas Básicas de Programación Prolog

10

Definición de dominio o tipo

es_natural/1 es una definición de dominio o tipo

Se llama dominio a un conjunto de términos Prolog
Dado un dominio D, se llama definición de dominio o tipo a un
predicado de aridad 1 que tiene éxito si y sólo si su argumento
es un elemento del dominio D

términos Prolog

dominio D

La definición de dominio para D suele llamarse es_d/1

Técnicas Básicas de Programación Prolog

11

Comprobando naturales

:- es_natural(s(s(s(c)))).

Yes

:- es_natural(c).

Yes

:- es_natural(s(s(f(c)))).

No

:- es_natural(s(s(0)).

No

[en pizarra/SLD-Draw]

Técnicas Básicas de Programación Prolog

12

Generando naturales

:- es_natural(X).

X = c ;

X = s(c) ;

X = s(s(c)) ;

X = s(s(s(c))) ;

...

:- es_natural(s(s(Y))).

Y = c ;

Y = s(c) ;

...

[en pizarra/SLD-Draw]

Técnicas Básicas de Programación Prolog

13

Comprobando y generando naturales

El predicado es_natural/1 funciona de dos maneras distintas:

pertenencia a N: comprueba que el argumento sea un natural

bien formado (un elemento de N)

:- es_natural(s(s(c))).

generación de N : genera todos los elementos del conjunto

N, partiendo del caso base, c

:- es_natural(X).

¿De qué depende el comportamiento de es_natural/1?

Técnicas Básicas de Programación Prolog

14

Modo de un argumento

Un argumento o parámetro actual de un predicado p/n puede
estar en dos modos:

Modo +: (entrada) el argumento no contiene variables libres, o
las variables que contiene no resultan instanciadas en la
ejecución de p/n

:- es_natural(s(s(c))).

+

Modo -:
variables libres que resultan instanciadas al ejecutar p/n

(salida, entrada/salida) el argumento contiene

:- es_natural(s(s(X))).

-

Técnicas Básicas de Programación Prolog

15

Uso de un predicado

Combinación de los modos + y - de los parámetros actuales de la
invocación a un predicado

En general, un predicado de n argumentos, tendrá 2n usos
posibles:

:- es_natural(+).

:- padre(+,+).

:- es_natural(-).

:- padre(+,-).

:- padre(-,+).

:- padre(-,-).

No todos los usos serán útiles en la práctica (algunos no
funcionarán)

Técnicas Básicas de Programación Prolog

16

Comportamiento de un predicado

Forma operacional en que se comporta un predicado para un uso
concreto. Es una característica cuantitativa. Clasifica los usos
de un predicado según el número de respuestas generadas:

test

:- es_natural(s(s(c))).

único

:- padre(P,carlos).

acotado

:- padre(antonio,H).

generador

no acotado

:- es_natural(X)

anómalo

Técnicas Básicas de Programación Prolog

17

Significado de un predicado

Cómputo particular llevado a cabo por un predicado para cada
uso concreto. Es una característica cualitativa. Describe
formalmente las respuestas computadas obtenidas

Para un test: describe los términos para los cuales tiene éxito

es_natural(X), en uso +, tiene éxito si X = s(…s(c)…)

Para un generador: describe la secuencia de respuestas

es_natural(X), en uso -, genera X = c, s(c), s(s(c)),…

Técnicas Básicas de Programación Prolog

18

Tabla de comportamiento de un predicado

es_natural(X)
Uso
(+)

(-)

Comportamiento
test
generador no acotado genera X=c, s(c), s(s(c))..

Significado
comprueba que X ∈ N

Comportamiento

padre(A,B)
Uso
(+,+) test
(+,-) generador acotado
(-,+) generador único
(-,-) generador acotado

Significado
comprueba que A es padre de B
genera en B los hijos de A
genera en A el padre de B
genera parejas de padres e hijos

Técnicas Básicas de Programación Prolog

19

La directiva mode

Podemos declarar los usos posibles de un predicado:

:- mode es_natural(+).
:- mode es_natural(-).

:- mode padre(+,+).
:- mode padre(+,-).
:- mode padre(-,+).
:- mode padre(-,-).

El comodín ? (= +/-) permite abreviar las declaraciones:

:- mode es_natural(?). :- mode padre(?,?).

Prolog comprueba los modos en tiempo de ejecución: sólo se
pueden emplear los usos declarados.
SWI-Prolog no comprueba los modos, pero los emplea en la
documentación (+ = entrada, - = salida, ? = entrada/salida)

Técnicas Básicas de Programación Prolog

20

Ejercicios

1. ¿Cómo se comporta el predicado es_natural/1 si
intercambiamos el orden del hecho y la regla?

es_natural(s(X)) :- es_natural(X).

es_natural(c).

Reconstruye
semánticas declarativa y operacional.

la tabla de comportamiento y compara

las

2. Define los predicados par/1 e impar/1 utilizando recursión
directa y mutua. Construye sus tablas de comportamiento y
compáralas.

Técnicas Básicas de Programación Prolog

21

Operaciones como relaciones

Las operaciones aritméticas básicas se pueden representar por
relaciones ternarias:

Z= X+Y  suma(X,Y,Z)
Z= X-Y  resta(X,Y,Z)
Z= X*Y  producto(X,Y,Z)
Z= X/Y  cociente(X,Y,Z)

pasamos de un estilo funcional a un estilo relacional
desaparece la distinción entre entrada y salida

La recursión jugará un papel fundamental en la definición
intensional de las relaciones

Técnicas Básicas de Programación Prolog

22

La relación suma/3 (I)

suma(X,Y,Z) se satisface si y sólo si X, Y y Z son tres
naturales tales que Z= X+Y

Aplicamos recursión al primer argumento:

suma(c, ?, ?) :- …

suma(s(X), ?, ?) :- …

[base]

[recursivo]

Técnicas Básicas de Programación Prolog

23

La relación suma/3 (II)

suma(X,Y,Z) se satisface si y sólo si X, Y y Z son tres
naturales tales que Z= X+Y

El segundo argumento es un natural arbitrario (no aplicamos
recursión):

suma(c, Y, ?) :- …

suma(s(X), Y, ?) :- …

[base]

[recursivo]

Técnicas Básicas de Programación Prolog

24

La relación suma/3 (III)

suma(X,Y,Z) se satisface si y sólo si X, Y y Z son tres
naturales tales que Z= X+Y

El caso base es trivial (elemento neutro de la suma):

suma(c, Y, Y).

suma(s(X), Y, ?) :- …

[base]

[recursivo]

Técnicas Básicas de Programación Prolog

25

La relación suma/3 (IV)

suma(X,Y,Z) se satisface si y sólo si X, Y y Z son tres
naturales tales que Z= X+Y

El caso recursivo se llama a sí mismo:

suma(c, Y, Y).

[base]

suma(s(X), Y, ?) :- suma(?,?,?).

[recursivo]

Técnicas Básicas de Programación Prolog

26

La relación suma/3 (V)

suma(X,Y,Z) se satisface si y sólo si X, Y y Z son tres
naturales tales que Z= X+Y

En la llamada recursiva se reduce el problema:

suma(c, Y, Y).

[base]

suma(s(X), Y, ?) :- suma(X,Y,?).

[recursivo]

Reducimos (X+1) + Y a X + Y, un problema del mismo tipo
pero “más pequeño”

Técnicas Básicas de Programación Prolog

27

La relación suma/3 (VI)

suma(X,Y,Z) se satisface si y sólo si X, Y y Z son tres
naturales tales que Z= X+Y

En la llamada recursiva, suponemos que la solución es Z:

suma(c, Y, Y).

[base]

suma(s(X), Y, ?) :- suma(X,Y,Z).

[recursivo]

Inducción: lo suponemos para el caso n

Técnicas Básicas de Programación Prolog

28

La relación suma/3 (y VII)

suma(X,Y,Z) se satisface si y sólo si X, Y y Z son tres
naturales tales que Z= X+Y

Partiendo de la solución de X + Y, construimos la sol