PDF de programación - ECLiPSe - Constraint Logic Programming

ECLECLiiPSPSee
CLP CLP -- Constraint

Constraint Logic

Logic Programming
Programming

ECLECLiiPSPSee

Herramienta open
Herramienta open--source
útil para modelar problemas de satisfacción de restricciones:
útil para modelar problemas de satisfacción de restricciones:

de CLP [Constraint

Constraint Logic

source de CLP [

Logic Programming
Programming]]

http://www.eclipse--clp.org
http://www.eclipse
clp.org

Computer--Industry

European Computer

Historia
Historia
1991
1991 –– European
1999
1999 –– ParcParc Technologies (spin
2001
2001 –– Biblioteca
2004
2004 –– Adquisición de

Industry Research

Research Centre (ECRC),

Centre (ECRC), Munich
Munich
College, Londres)
, Londres)

Technologies (spin--off del Imperial

off del Imperial College

Biblioteca icic (propagación de restricciones)
(propagación de restricciones)
Adquisición de ParcParc Technologies por parte de Cisco

Technologies por parte de Cisco Systems
Systems

11

ECLECLiiPSPSee

 PROLOG
PROLOG
Elementos del lenguaje
 Elementos del lenguaje
 Búsqueda en PROLOG: Backtracking
Búsqueda en PROLOG: Backtracking
 Satisfacción de restricciones en PROLOG
Satisfacción de restricciones en PROLOG

 ECLECLiiPSPSee
 ECLECLiiPSPSee

Satisfacción de restricciones en ECLECLiiPSPSee
 Satisfacción de restricciones en
Elementos del lenguaje: arrays
 Elementos del lenguaje:
La biblioteca suspend
 La biblioteca
suspend
Las bibliotecas sdsd & & icic
 Las bibliotecas
 Estrategias de búsqueda
Estrategias de búsqueda

arrays e e iteradores
iteradores..

22

PROLOG Satisfacción de restricciones
PROLOG
Satisfacción de restricciones

Los problemas de satisfacción de restricciones pueden
Los problemas de satisfacción de restricciones pueden
representarse mediante programas lógicos:
representarse mediante programas lógicos:

Problema

PSR

• Desigualdad triangular: La
• Desigualdad triangular: La
suma de las longitudes de
cualesquiera 2 lados no es
menor que la del tercero.

x

y

z

• Variables: X,Y,Z
• Variables: X,Y,Z
• Dominios: [0,inf)
• Restricciones

• X+Y>=Z
• X+Z>=Y
• Y+Z>= X

33

PROLOG Satisfacción de restricciones
PROLOG
Satisfacción de restricciones

Los problemas de satisfacción de restricciones pueden
Los problemas de satisfacción de restricciones pueden
representarse mediante programas lógicos:
representarse mediante programas lógicos:

PSR

Programa Lógico

• Variables: X,Y,Z
• Variables: X,Y,Z
• Dominios: [0,inf)
• Restricciones

• X+Y>=Z
• X+Z>=Y
• Y+Z>= X

• triangular(X,Y,Z)
• triangular(X,Y,Z)

:-

X>0 AND Y>0 AND Z>0
AND
X+Y>=Z AND X+Z>=Y AND Y+Z>=X

44

PROLOG Satisfacción de restricciones
PROLOG
Satisfacción de restricciones

Un programa lógico puede interpretarse como una base
Un programa lógico puede interpretarse como una base
de conocimiento (hechos y reglas) sobre la que se
de conocimiento (hechos y reglas) sobre la que se
realizan consultas
realizan consultas

Programa Lógico

El programa lógico termina con
El programa lógico termina con
El programa lógico termina con
El programa lógico termina con
Una respuesta “Sí”/”No”
 Una respuesta “Sí”/”No”
en función de si se puede
en función de si se puede
deducir la consulta de la
deducir la consulta de la
base de conocimiento.
base de conocimiento.
 Una sustitución de variables
Una sustitución de variables
que la hace cierta.
que la hace cierta.

• triangular(X,Y,Z):-

X>0 AND Y>0 AND Z>0 AND X+Y>=Z
AND X+Z>=Y AND Y+Z>=X
AND X+Z>=Y AND Y+Z>=X

Consulta

• triangular(3,4,5)?

Respuesta: Sí

• triangular(8,1,2)?

Respuesta: No

• triangular(3,4,Z)?

Respuesta: Z = [1..7]

55

PROLOG
PROLOG

Ejemplo
Ejemplo

REGLAS
REGLAS

HECHOS
HECHOS

ancestro(X,Y) :-- padre(X,Y).
ancestro(X,Y) :
padre(X,Y).
ancestro(X,Y) :-- padre(Z,Y), ancestro(X,Z).
ancestro(X,Y) :
padre(Z,Y), ancestro(X,Z).

homer).).
padre(abe,
padre(abe, homer
padre(abe, herbert
padre(abe,
herbert).).
padre(
homer, , bartbart).).
padre(homer
padre(
padre(margemarge, , bartbart).).

66

PROLOG
PROLOG

Consulta
Consulta

ancestro(
ancestro(X,bart

X,bart). ).

ancestro(X,Y) :-- padre(X,Y).
ancestro(X,Y) :
padre(X,Y).

ancestro(X,bart)

padre(X,Y)

Y=bart

padre(Z,X),
ancestro(Y,Z)

X=bart

padre(X,bart)

X=homer

padre(X,bart)

X=marge

Padre(Z,bart),
ancestro(Y,Z)

Z=homer

Padre(marge,bart),
ancestro(Y,marge)

ancestro(X,Y) :
ancestro(X,Y) :-- padre(Z,Y), ancestro(X,Z).
padre(Z,Y), ancestro(X,Z).
padre(abe,
homer).).
padre(abe, homer
padre(abe, herbert
padre(abe,
herbert).).
padre(
homer, , bartbart).).
padre(homer
padre(
padre(margemarge, , bartbart).).

Success
X=homer

Success
X=marge

Padre(Z,bart)

Z=homer

Success

Padre(abe,homer)

Y=abe

Success
X=abe

Ancestro(Y,Z)

Z=homer

Padre(Y,marge)

Padre(Y,marge),

ancestro(Z,Y)

Padre(abe,homer),

ancestro(Z,abe)

Fail

Fail

Padre(abe,homer)

Success

Ancestro(Z,abe)

Fail

77

PROLOG -- Aritmética
PROLOG
Aritmética

Operadores predefinidos para aritmética básica:
Operadores predefinidos para aritmética básica:
+, +, --,*,

,*, divdiv, , modmod, ^,

, ^, -- (unario),

(unario), absabs

Si no se especifica lo contrario, los operadores son como cualquier
 Si no se especifica lo contrario, los operadores son como cualquier
otra relación (predicado)
otra relación (predicado)

X = 1+2.
X = 1+2.
Respuesta: X=1+2 % X unificado al término +(1,2)
Respuesta: X=1+2 % X unificado al término +(1,2)
Respuesta: X=1+2 % X unificado al término +(1,2)
Respuesta: X=1+2 % X unificado al término +(1,2)

 El operador “

El operador “isis” fuerza la evaluación de expresiones aritméticas:
” fuerza la evaluación de expresiones aritméticas:
A A isis B B evalúa B a un número y unifica el resultado con A.
evalúa B a un número y unifica el resultado con A.

X X isis 1+2.
1+2.
Respuesta: X = 3
Respuesta: X = 3

 Los operadores de comparación fuerzan también la evaluación
Los operadores de comparación fuerzan también la evaluación

145 * 34 > 100.
145 * 34 > 100.
Respuesta: Yes.
Respuesta: Yes.

88

PROLOG -- Comparación
PROLOG
Comparación

Operadores
Operadores

= vs. =:=
= vs. =:=

X > Y

X < Y

X >= Y

X =< Y

X es mayor que Y

X es menor que Y

X es mayor o igual que Y

X es menor o igual que Y

X =:= Y

Los valores de X e Y son iguales

X =\= Y

Los valores de X e Y no son iguales

unificación de X e Y
de X e Y
puede queque la la instanciación

instanciación de de

 X=Y
X=Y
causa
causa la la unificación
(y (y puede
variables)
variables)
 X =:= Y
X =:= Y
 X =:= Y
X =:= Y
causa
causa unauna evaluación
X e Y (
X e Y (peropero no no puede
instanciación de variables)
instanciación
de variables)

evaluación aritmética
lugar a a

puede dardar lugar

aritmética de de

1 + 2 =:= 2 + 1.

> Yes

1 + 2 = 2 + 1.

> No

1 + A = B + 2.

> A = 2
> B = 1

1+A =:= B+2.

> Error (variables no instanciadas)

X is Y + 1

> Error (variable no instanciada)

Y=0, X is Y + 1.

> X = 1

X = 0, X is X + 1

> No.
No se puede unificar X con X + 1.

X = 0, X1 is X + 1.

> Yes. X = 0, X1 = 1.

99

PROLOG -- Listas
PROLOG
Listas

[a, [1,2,3],tomtom, 1995, fecha(1,mayo,1995)]
[a, [1,2,3],
, 1995, fecha(1,mayo,1995)]

 Lista vacía: []
Lista vacía: []
Lista = [Cabeza | Cola]
 Lista = [Cabeza | Cola]
 Cabeza: primer elemento de la lista.
 Cabeza: primer elemento de la lista.
Cabeza: primer elemento de la lista.
Cabeza: primer elemento de la lista.
 Cola: Una lista formada por el resto de la lista.
Cola: Una lista formada por el resto de la lista.

[X|Y] = [a,b,c
[X|Y] = [
a,b,c]]
> X=a, Y=[
> X=a, Y=[b,cb,c]]

Representan a la misma lista:
Representan a la misma lista:

[[a,b,c
a,b,c] = [a| [

] = [a| [b,cb,c]] = [a, b |[c]] = [

]] = [a, b |[c]] = [a,b,c

a,b,c | []]
| []]

1010

PROLOG -- Listas
PROLOG
Listas

Ejemplos
Ejemplos

 Miembro de una lista
Miembro de una lista
member(X, [
X|Tail]).]).
member(X, [X|Tail
member(X, [Head | Tail]) :
member(X, [Head | Tail]) :-- member(
member(X, [Head | Tail]) :
member(X, [Head | Tail]) :-- member(

member(X,Tail
member(X,Tail

X,Tail).).
X,Tail).).

 Concatenación de listas
Concatenación de listas
append([],L,L).
append([],L,L).
append([X|L1], L2, [
append([X|L1], L2, [X|Result

X|Result]) :]) :-- append(L1,L2,Result).
append(L1,L2,Result).

1111

PROLOG -- Listas
PROLOG
Listas

Ejemplos de uso
Ejemplos de uso

a,b,c] ).] ).

a,b,c], [1,2,3], L).
], [1,2,3], L).

append( [
append( [a,b,c
> L = [a,b,c,1,2,3]
> L = [a,b,c,1,2,3]
append( L1, L2, [a,b,c
append( L1, L2, [
> L1 = [], L2 = [
> L1 = [], L2 = [a,b,c
> L1 = [], L2 = [
> L1 = [], L2 = [a,b,c
a,b,c];];
a,b,c];];
> L1 = [a], L2 = [
> L1 = [a], L2 = [b,cb,c];];
> L1 = [a,ba,b], L2 = [c];
> L1 = [
], L2 = [c];
> L1 = [
> L1 = [a,b,c
a,b,c], L2 = [];
], L2 = [];
> no> no
append( Before, [4|After], [1,2,3,4,5,6,7]).
append( Before, [4|After], [1,2,3,4,5,6,7]).
> Before = [1,2,3], After = [5,6,7]
> Before = [1,2,3], After = [5,6,7]
append(_, [
append(_, [PredPred, 4,
> > PredPred = 3, = 3, SuccSucc = 5= 5

, 4, SuccSucc |_], [1,2,3,4,5,6,7]).
|_], [1,2,3,4,5,6,7]).

PROLOG Ejemplos
PROLOG
Ejemplos

Selección de valores dentro de un rango definido:
Selección de valores dentro de un rango definido:

select_val(4,6,Val)

Min=<Max,
Val is Min

(Val = 4)

Min < Max,

Min1 is Min(4) +1,
Min1 is Min(4) +1,
select_val(5,6,Val)

Min=<Max,
Val is Min

(Val=5)

Min < Max,

Min1 is Min(5) +1,
select_val(6,6,Val)

select_val((Min,Max,Val

% % select_val
% variable Val en el rango [
% variable Val en el rango [Min,Max

Min,Max,Val) selecciona un valor para la
) selecciona un valor para la
Min,Max], ambos incluidos
], ambos incluidos

select_val
select_val((Min,Max,Val
select_val
select_val((Min,Max,Val

Min,Max,Val) :) :-- Min =< Max, Val
Min,Max,Val) :) :--
Min < Max, Min1
Min < Max, Min1 isis Min + 1,
Min + 1,
select_val(Min1,Max,Val).
select_val
(Min1,Max,Val).

Min =< Max, Val isis Min.Min.

1212

Min=<Max,
Val is Min
Val is Min

(Val = 6)

Min < Max,

FALLO!

1313

PROLOG Satisfacción de restricciones
PROLOG
Satisfacción de restriccione