capítulo v: programación l - inf.utfsm.clnoell/ili-253-p2/apunte05.pdf · • cálculo de...

Lenguajes de ProgramaciónDepartamento de Informática

Universidad Técnica Federico Santa María

1

Capítulo V:Programación Lógica



2

5.1 Breve Introducción al Cálculo de Predicados



V13

Definiciones Básicas

• Proposición: sentencia lógica que puede ser verdadera o falsa. – Se construye de objetos y relaciones.– Lógica formal provee métodos para verificar su validez

• Lógica Simbólica: permite expresar proposiciones, relaciones entre proposiciones y cómo inferir nuevas proposiciones que son verdaderas.

• Cálculo de Predicado: Forma particular de lógica simbólica usada en programación lógica.



V14

Objetos y Términos Compuestos

• Objetos se representan como un único término, que puede ser:– constante : representa un único objeto– variable : puede representar diferentes objetos

• Término compuesto: consiste de functor y una lista de parámetros– Un término con n parámetros se denomina ntupla.– El término padre(maria, jesús) es una 2tupla.



V15

Proposiciones

• Proposiciones pueden ser:– Atómicas: corresponde a un único término compuesto– Compuestas: dos o más proposiciones atómicas

conectadas por operadores lógicos.• Una proposiciones puede ser:

– Hecho: se define como una verdad (axioma)– Consulta: la verdad debe ser probada (teorema)



V16

Conectores Lógicos

NOMBRE SIMBOLO EJEMPLOnegación ¬ ¬aconjunción ∩ (∧) a ∧ bdisjunción ∪ (∨) a ∨ bequivalencia ≡ (⇔) a ≡ bimplicancia ⊃ (⇒)

⊂ (⇐)a ⊃ bb ⊂ a



V17

Cuantificadores

• Cuantificador Universal∀X.P : Para todo X, P es verdadero

• Cuantificador Existencial∃X.P : Existe un valor X tal que P es

verdaderoEJEMPLOS∀ ∀X.(mujer(X) ⊃ humano(X))∀ ∃X.(madre(maria, X) ∩ masculino(X))



V18

Forma de Cláusula

• Para automatizar se requiere reducir redundancia en la expresión de proposiciones.

• La forma de cláusula simplifica proposiciones, sin pérdida de generalidad.

• Una cláusula tiene la siguiente forma:B1 ∪ B2 ∪ … ∪ Bn ⊂ A1 ∩ A2 ∩ … ∩ Am

• Donde As y Bs son términos• Una cláusula significa: “Si todos los As son

verdaderos, entonces al menos un B es verdadero”



V19

Características de Cláusulas

• Una forma clausal no requiere de cuantificadores existenciales.

• Cuantificadores universales están implícitos en el uso de variables de proposiciones atómicas.

• No se requiere de otro conector que la conjunción y disjunción, apareciendo sólo en el orden definido por una cláusula (derecha e izquierda).

• Cualquier proposición de cálculo de predicado se puede transformar en una cláusula.



V110

Ejemplo de Cláusula

gusta(ana, fiesta) ⊂ gusta(joven, fiesta) ∩ joven(ana)

consecuencia antecedente

padre(luis, juan) ∪ padre(luis, maria) ⊂ padre(juan, pepe) ∩

madre(maria, pepe) ∩ abuelo(luis, pepe)



V111

Resolución

• Cálculo de Predicado provee método para expresar conjunto de proposiciones

• Aplicación interesante o útil es inferir de las proposiciones dadas nuevos hechos.

• Una aplicación es descubrir nuevos teoremas

• Resolución es proceso que permite inferir proposiciones de proposiciones dadas.



V112

Ejemplo de ResoluciónSi se tiene:

papa(juan, pato) ∪ mama(juan, pato) ⊂ padre(juan, pato) abuelo(juan, roro) ⊂ papa(juan, pato) ∩ papa(pato, roro)

Se puede resolver que:

abuelo(juan, roro) ∪ mama(juan, pato) ⊂ padre(juan, pato) ∩ papa(pato, roro)

¡Proceso de resolución consiste en conectar términos de la izquierda y de la derecha, y luego eliminar términos redundantes!



V113

Tautologías Importantes para Resolución

A ⊂ BC ⊂ D A ∪ C ⊂ B ∩ D

A ∪ B ⊂ C ∩ B A ⊂ C



V114

Proceso de Resolución

• La resolución es un proceso complejo• Presencia de variables requiere de un proceso de

calce (matching) que al reemplazar sus valores produce una verdad (éxito).

• Este proceso se denomina unificación.• Asignación temporal de valores a variables se

denomina instanciación.• Fallas (no éxito) en la instanciación requiere de

backtracking.



V115

Cláusulas de Horn

• Cláusulas de Horn simplifican el proceso de resolución, y permiten representar la mayoría de las proposiciones lógicas.

• Sólo permite dos tipos de formas:– Existe sólo una proposición atómica en la izquierda de

la cláusula (cláusula con cabeza)– El lado izquierdo está vacío (cláusula sin cabeza)

• Cláusulas con cabeza se usan para definir reglas, en cambio cláusulas sin cabezas sólo establecen ciertos hechos.



V116

Conclusiones

• Programación Lógica consiste básicamente en definir un conjunto de reglas y hechos (hipótesis).

• El sistema luego debe ser capaz de inferir si una determinada proposición (meta) es una verdad.

• Prolog está basado en el uso de cláusulas de Horn.



17

5.2 Introducción a Prolog



V118

Lenguaje Prolog

• Su nombre viene de Programación en Lógica, creado a comienzos de los ´70:

• Robert Kowalski (Edimburgo): lado teórico• Maarten van Emden (Edimburgo): demostración

práctica• Alain Colmerauer (Marsella): Implementación

• Popularidad se debe a David Warren (Edimburgo), que a mediados de los ´70 realizó implementación eficiente.



V119

Características de Prolog

• Basado en Lógica y programación declarativa • Produce estilo de programación orientado a metas• No se especifica cómo debe hacerse, sino qué

debe lograrse (alto nivel)• El programador se concentra más en el

conocimiento que en los algoritmos• ¿Qué es conocido? (hechos y relaciones )• ¿Qué preguntar? (cómo resolverlo)



V120

Aplicaciones de Prolog

• Pruebas Matemáticas– Demostración de teoremas

• Inteligencia Artificial– Sistemas Expertos

• Consultas a base de datos– Permite inferir relaciones no especificadas a

priori



V121

Hechos en Prolog: Ejemplo

padre(maria, pedro).padre(juan, pedro).padre(juan, carola).padre(pedro, ana).padre(pedro, paty).padre(paty, aldo).

ana

maria juan

pedro carola

paty

aldo



V122

Consultas en Prolog

? padre(pedro, ana).=> yes

? padre(ana, paty).=> no

? padre(X, carola).=> X = juan

? padre(pedro, X).=> X = ana ;=> X = paty ;=> no



V123

Consulta: Ejemplo 1

Preguntar por el abuelo de aldo:

∃X, Y : (X es padre de Y) ∩ (Y es padre de aldo)

que se expresa en Prolog como:

? padre(X, Y), padre(Y, aldo).=> X = pedro

Y = paty



V124

Consulta: Ejemplo 2Preguntar por los nietos de juan:

∃X, Y : (juan es padre de X) ∩ (X es padre de Y)


? padre(juan, X), padre(X, Y).=> X = pedro

Y = ana ;

=> X = pedroY = paty



V125

Consulta: Ejemplo 3Preguntar si ana y paty tienen un padre en común:

∃X : (X es padre de ana) ∩ (X es padre de patricio)


? padre(X, ana), padre(X, paty).=> X = pedro



V126

Otros HechosAgregar cláusulas sobre el sexo de las personas (relaciones unarias):

femenino(maria).masculino(juan).masculino(pedro).femenino(carola).femenino(ana).femenino(paty).masculino(aldo).



V127

Alternativa de definición de hechos

Podría haberse definido también con una relación binaria:

sexo(maria, femenino).sexo(juan, masculino).sexo(pedro, masculino).sexo(carola, femenino).sexo(ana, femenino).sexo(paty, femenino).sexo(aldo, masculino).

¡A continuación usaremos la forma unaria!



V128

Reglas en Prolog

• La relación:a ⊂ b

• se expresa en Prolog como:a : b.

• Una cláusula de este tipo se denomina regla, que tiene la siguiente estructura:

• la cabeza (parte izquierda de : ) es la conclusión • la proposición definida en el cuerpo (parte derecha de : )



V129

Resolución Simple

• La relación hijo de corresponde a:∀X, Y : (Y es hijo de X) ⊂ (X es padre de Y)

• que se expresa en Prolog como:hijo(X, Y) : padre(Y, X).

• Ejemplo: la meta siguiente es evaluada como:La meta: hijo(paty, pedro) se convierte en submeta padre(pedro, paty)Se busca este hecho: yes



V130

Ejemplo de Reglas

Se puede definir ahora varias nuevas reglas como:

papa(X, Y) : padre(X, Y), masculino(X).mama(X, Y) : padre(X, Y), femenino(X).abuelo(X, Y) : padre(X, Z), padre(Z, Y).hermana(X, Y) : padre(Z, X), padre(Z, Y), femenino(X).



V131

Ejemplo de Consulta?- hermana(ana, paty).

=> yes

?- hermana(X, paty).=> X = ana ;=> X = paty

oops ... paty es hermana de ella misma

¡Falta excluir este caso:

hermana(X, Y) : diferente(X, Y), padre(Z, X), padre(Z, Y), femenino(X).



V132

Observaciones• Programas Prolog se extienden simplemente agregando más cláusulas• Cláusulas son de tres tipos: hechos, reglas y consultas• Reglas declaran cosas que cuya verdad depende de otras condiciones• Por medio de consultas el usuario puede solicitar al programas que

establezca qué cosas son verdad• Una cláusula tiene una cabeza y un cuerpo. El cuerpo son metas

separadas por comas (conjunción)• Hechos son cláusulas que no tienen cuerpo• Preguntas sólo tienen cuerpo• Reglas tienen cabeza y cuerpo

• Una evaluación puede sustituir una variable X por otro objeto (se dice que X se instancia)

• Variables se cuantifican universalmente (∀)



V133

Reglas Recursivas

La relación antepasado se define sobre la base de una regla de descendencia directa y otra regla de descendencia indirecta:

∀X, Z : (X es un antepasado de Z), si {X es padre de Z } ∨

{ ∃Y: (X es padre de Y) ∧ (Y es antepasado de Z) }

Lo que en Prolog se expresa como :

antepasado(X, Z) : padre(X, Z). % descendiente directoantepasado(X, Z) : padre(X, Y), antepasado(Y, Z). % descendiente ind.



V134

Ejemplo de Consulta

% Consultar por los descendientes de maria

?- antepasado (maria, X)=> X = pedro ;=> X = ana ;=> X = paty ;=> X = aldo



V135

Resolución de Consultaantepasado(juan, paty)

NO

SI

padre(juan, paty)

Regla#1

padre(juan, X)antepasado(X, paty)

Regla#2

antepasado(pedro, paty)

Hecho:padre(juan, pedro)X=pedro

padre(pedro, paty)

Regla#1

ana

maria juan

pedro carola

paty

aldo



36

5.3 Tipos de Datos en Prolog



V137

Objetos de Datos en Prolog

• Objetos de datos simples• Objetos estructurados• Calce de operaciones fundamentales sobre

objetos



V138

Tipos de Objetos de Datos

Objetos de datos

Objetos simples Objetos estructurados

Constantes Variables

Atomos Números



V139

Reconocimiento de Tipos

• Se reconoce el tipo de un dato por su forma sintáctica; no se requiere de declaración de tipos

• Ejemplo:– Variables se definen comienzan con primera en

mayúsculas (e.g. X)– Atomos comienzan con una letra en minúscula

(e.g. pedro)



V140

Formación de Variables y Átomos

• Strings de los siguientes caracteres:– Letras mayúsculas A..Z– Letras minúsculas a..z– Dígitos 0..9– Caracteres especiales: + * / < > = : . & _ ~



V141

Atomos

• 1) Strings de letras, dígitos y underscore (_), comenzando con minúscula

pedro nil x_25 algo_especial• 2) Strings de caracteres especiales

<> ===> ...• 3) Strings con citación simple

´Juan´ ´San Francisco´



V142

Números

• Números enteros1 3213 0 323

• Reales3.14 0.0234 100.2

• Dado que Prolog es principalmente un lenguaje de computación simbólica, los números no son su fuerte (el entero es lo que más se usa)



V143

Variables

• Strings de letras, dígitos y underscore, comenzando con mayúscula o underscore.X Resultado _X1 _12

• Si una variable aparece una solo vez en una cláusula, se puede usar variables anónima _? padre(juan, _).

yes % no se imprime variabletiene_hijo(X) : padre(X, _).

• Ámbito de variable es una cláusula



V144

Objetos Estructurados

• Son objetos que tienen varias componentes• Estructuras son tratadas como un único

objeto• Se construyen usando un functor:

fecha(22, mayo, 2000)• Componentes pueden ser constantes,

variables o estructuras.Fecha(Dia, mayo, 2000)



V145

Ejemplo con Figuras Geométrica

2 4 6 8

2

4

6

P2 = (2,3)

P1 = (1,1)

(6,4)

(7,1)(4,2) TS

P1 = punto(1, 1)P2 = punto(2,3)S = seg(P1, P2)T = triangulo (punto(4,2),

punto(6,4), punto(7,1))



V146

Representación de Árbol de Estructuras

T = triangulo

punto punto

6 4 7 1

punto

4 2



47

5.4 Calce de Términos en Prolog



V148

Concepto de Calce• La operación más importante sobre

términos es el calce, que corresponde a la unificación en el cálculo de predicados.

• Dos términos calzan si:Son idénticosLas variables en ambos términos pueden ser

instanciados, sustituyendo variables, tal que los términos se hacen idénticos.



V149

Ejemplo de Calce

• Calzar: fecha(D, M, 2000) y fecha(D1, mayo, A1) , entonces:– D se instancia a D1– M se instancia a mayo– A1 se instancia a 2000

• Que como salida de Prolog se escribe:– D = D1– M= mayo– A1 = 2000



V150

Ejemplo de Calce

• Calzar: fecha(D, M, 2000) y fecha(D1, julio, 1956) , entonces:

• No es posible encontrar un calce (se dice que el proceso de calce ha fracasado).

• En caso contrario, se dice que el proceso ha sido exitoso.



V151

Ejemplo de Calce en Prolog? fecha(D, M, 2000) = fecha(D1, mayo, A1).

D = H86M = mayoD1 = H86A1 = 2000

? fecha(D, M, 2000) = fecha(D1, julio, 1956).no



V152

Grado de Ajuste del Calce

? fecha(D, M, 2000) = fecha(D1, mayo, A1).

Podría haber sido calzado como:D = 1D1 = 1M = mayoA1 = 2000

Pero esta forma es más restrictiva (menos general) que la anterior.

¡Prolog calza el resultado a su forma más general!



V153

Reglas de CalceDos términos S y T calzan, si:• Si S y T son constantes, entonces S y T calzan si ambos

son el mismo objeto.• Si S es una variable y T cualquier cosa, entonces calzan y

S se instancia como T. Viceversa, si T es variable, entonces T se instancia como S.

• Si S y T son estructuras, entonces calzan sólo si: S y T tienen el mismo functor, y Todas sus correspondientes componentes calzan. Instanciaciones resultantes es determinado por proceso de calce de

componentes.



V154

Ejemplo de Calce de Estructuras

triangulo

punto puntoA

1 1 2 3

triangulo

punto puntoX

4 Y 2 Z

? triangulo(punto(1, 1), A, punto(2, 3)) =triangulo(X, punto(4, Y), punto(2, Z)).

A = punto(4,H193)X = punto(1,1)Y = H193Z = 3



V155

Ejemplo de Calce con Estructuras? vertical(seg(punto(1,1), punto(1,2))).

yes

? vertical(seg(punto(1,1), punto(2,Y))).no

? horizontal(seg(punto(1,1), punto(2,Y))).Y = 1

? vertical(seg(punto(2,3), Y)).Y = punto(2,H561)

? vertical(S), horizontal(S).S = seg(punto(H576,H577),punto(H576,H577))



V156

Significado Declarativo versus Procedural

La cláusula:

P : Q, R.

Se interpreta declarativamente como:

p es verdadero si Q y R lo son.De Q y R se deriva P.

En cambio una interpretación procedural sería:

Para resolver P, primero se debe resolver Q y luego R.Para satisfacer a P, primero se debe satisfacer Q y luego R.



V157

Significado Declarativo

• Una meta G es verdadera (satisface o se deriva lógicamente de un programa), ssi:

Existe en el programa una cláusula C, tal que existe una cláusula I, instancia de C, tal que:

• La cabeza de I es idéntica a G, y• todas las metas en el cuerpo de I son verdaderas.



V158

Disjunción en Cláusulas

La cláusula:

P : Q; R.

Se puede interpretar como:

P : Q.P : R.

La cláusula:

P : Q, R;S, T, U.

Se puede interpretar como:

P : Q, R.P : S, T, U.



V159

Significado Procedural

• Especifica cómo responder a una pregunta• Para obtener la respuesta es necesario

satisfacer una lista de metas.• Las metas pueden ser satisfechas si a través

de la instanciación de sus variables se permite que del programa se deriven las metas.



V160

Visión Procedural

EjecuciónLista de metas

Indicador de éxito/fracaso

Instanciación de Variables

programa

Sólo si hay indicación de éxito



61

5.5 Listas y Operadores



V162

Listas en Prolog

• Una lista en Prolog se puede escribir como:[perro, gato, ratón, loro]

• Sin embargo esto es sólo un sabor sintáctico, pues Prolog lo traduce una forma de estructura.Si existe la estructura .(Cabeza, Cola), entonces:

.(perro, .(gato, .(ratón, .(loro, []))))equivale a la lista anterior (que es más legible)



V163

Representación de Listas

• Una lista define un árbol binario, similar a las listas propias de Scheme.

• Prolog permite una notación similar a los pares:– L = [a | Cola] , donde a es la cabeza (cualquier tipo)

y Cola es el resto de la lista (debe ser una lista) .– La lista vacía se expresa como [].

• Ejemplo:? L2 = [ a | [b | []]].

L2 = [a,b]



V164

Algunos Posibles Operadores sobre Listas

• Membresía del objeto X en la lista L:member(X, L)

• Concatenación de listas L1 y L2 en L3conc(L1, L2, L3)

• Agregar un elemento X en una lista Ladd(X, L, L1)

• Borrar un elemento X en una lista Ldel(X, L, L1)



V165

Definición de Operadores (1/2)

%definicion de membresia de X en una lista L: member(X, L).% ============================================

member(X, [X | Cola]).member(X, [Cabeza | Cola]) : member(X, Cola).

% concatenacion de listas L1 y L2 en lista L3: conc(L1, L2, L3).% ==============================================

% concat. con lista vacia es la misma listaconc([], L, L).

% caso de que primera lista no esté vacíaconc([X | L1], L2, [X | L3]) : conc(L1, L2, L3).



V166

Definición de Operadores (2/2)

% agregar un elemento en la cabeza% ==========================

add(X, L, [X | L]). % en realidad basta el operador |

% borrar un elemento de una lista% ======================

% elemento está en la cabezadel(X, [X | Cola], Cola).

% elemento no está en la cabezadel(X, [Y | Cola1], [Y | Cola2]) : del(X, Cola1, Cola2).



V167

Ejemplos de Operadores con Listas

? member(X, [a, b]).X = a ;X = b ;no

? conc([a], [b], L).L = [a,b] ;no

? add(a, X, Y).X = H918Y = [a | H918] ;no

? del(b, [a, b, c, b, d], L).L = [a,c,b,d] ;L = [a,b,c,d] ;no



V168

Sublistas

• Una sublista es una parte de una lista• El operador puede ser definido con la

siguiente regla:

• Ejemplo:? sublist([b, X], [a, b, c, d]).

X = c

sublist(S, L) : conc(L1, L2, L), conc(S, L3, L2).



V169

Permutación de una Lista

% Permutar la lista L% ==============

permutation([], []).

permutation(L, [X | P]) : del(X, L, L1), permutation(L1, P).



V170

Ejemplo de Permutación? permutation([gato, perro, raton], L).

L = [gato,perro,raton] ;

L = [gato,raton,perro] ;

L = [perro,gato,raton] ;

L = [perro,raton,gato] ;

L = [raton,gato,perro] ;

L = [raton,perro,gato] ;no



71

5.6 Operadores y Aritmética



V172

Notación de Operadores

• Las operaciones en Prolog se expresan normalmente como functores.

• Se permite también especificar operadores especiales con su relación de precedencia mediante directivas al traductor Prolog.

• Este mecanismo permite mejorar la lectura de programas (sabor sintáctico), similar a la sobrecarga de operadores en C++



V173

Ejemplo de Operadores

La expresión:

+(*(2, a), *(b, c))

podría escribirse como:

2*a + b*c

¡¡Que resulta más legible!!

Ejemplo en Prolog:

? X = +(*(2, 3), *(4, 5)).X = 2 * 3 + 4 * 5

? X is +(*(2, 3), *(4, 5)).X = 26 .

? X is 2*3 + 4*5.X = 26

Se ha supuesto que + tiene mayor precedencia que *



V174

Definición de Operadores

• Se permite definición de operadores prefijos, infijos y postfijos

• A cada operador se le puede definir el nivel de precedencia mediante un valor (e.g. entre 11200 en una implementación)

• Nombre del operador debe ser un átomo• Ejemplo: Operador binario infijo gusta

: op(600, xfx, gusta).



V175

Tipos de Operadores• Operador Infijo (tres tipos)

xfx xfy yfx• Operador Prefijo (dos tipos)

fx fy• Operador Postfijo (dos tipos)

xf yf• Donde la notación se interpreta como.

– f corresponde al nombre del operador– x e y representan los argumentos– x representa operando con precedencia estrictamente menor que el

operador– y representa operando cuya precedencia es menor o igual que el

operador



V176

Conjunto de Operadores Predefinidos

: op(1200, xfx, ´:´).: op(1200, fx, [:, ?] ).: op(1100, xfy, ´;´).: op(1000, xfy, ´,´).: op(700, xfx, [=, is, <, >, =<, >=, ==, =\=, \==, =:=] ).: op(500, yfx, [+, ] ).: op(500, fx, [+, , not] ).: op(400, yfx, [*, , div] ).: op(300, xfx, mod).



V177

Ejemplo:Operadores Matemáticos

? X = 3 + 5.X = 3 + 5 .yes

? X is 3 + 5.X = 8 .yes

? X is 5/3.X = 1.66666666666667 .yes

? X is 5 2 1.X = 2 .yes

? 1 + 2 = 2 + 1.no

? 1 + 2 =:= 2 +1.yes



V178

Ejemplo: Máximo Común Divisor

mcd(X, X, X).

mcd(X, Y, D) :X<Y,Y1 is YX,mcd(X, Y1, D).

mcd(X, Y, D) :Y<X,mcd(Y, X, D).



V179

Ejemplo: Máximo Común Divisor

? mcd(100, 10, X).

X = 10

? mcd(27, 36, X).

X = 9



V180

Ejemplo 1: Largo de una Lista

largo([], 0).

largo([ _ | Cola], N) :largo(Cola, N1),N is N1 + 1.

% Y ahora se consulta

? largo([a, b, [c, d], d, e], N).N = 5



V181

Ejemplo 2: Largo de una Lista

largo([], 0).

largo([ _ | Cola], N) :largo(Cola, N1),N = N1 + 1.

% Y ahora se consulta

? largo([a, b, [c, d], d, e], N).N = 0 + 1 + 1 + 1 + 1 + 1 ;



82

5.7 Ejemplos de Programas con Estructuras



83

Ejemplo de Programa

Recuperación de Información de Base de Datos



V184

Ejemplo de una Base de Datos% familias

familia( % padrepersona(juan, perez, fecha(7, mayo, 1950), trabajo(usm, 450000)),%madrepersona(maria, toledo, fecha(9, julio, 1956), cesante),% hijos[persona(tomas, perez, fecha(12, diciembre, 1976),

trabajo(aduana, 650000)), persona(ana, perez, fecha(23, enero, 1978),

trabajo(falabella, 550000)), persona(pedro, perez, fecha(16, octubre, 1985),

cesante)]).

% agregar todas las familias



V185

Consultas a la Base de Datos (1/3)%verifica si una persona es marido o mujer en la base de datos

marido(X) : familia(X, _, _).mujer(Y) : familia(_, Y, _).

%verifica si una persona es un hijo en la base de datosmiembro(X, [X | L]).miembro(X, [Y | L]) : miembro(X, L).

hijo(Z) : familia(_, _, Hijos),miembro(Z, Hijos).

%verifica si existe una persona en la base de datos

existe(P) : marido(P); mujer(P); hijo(P).



V186

Consultas a la Base de Datos (2/3)

% salario de una persona

salario(persona(_, _,_, trabajo(_, S)), S).salario(persona(_, _,_, cesante), 0).

% calcular el ingreso de lista de personas

ingresos_l([], 0).ingresos_l([Persona | Lista], Suma) :

salario(Persona, S), % salario del primeroingresos_l(Lista, Resto), % salarios del restoSuma is S + Resto.



V187

Consultas a la Base de Datos (3/3)% ahora se puede calcular ingreso familiar

ingresos(Pat, Mat, S) : familia(persona(_,Pat,_,_),persona(_,Mat,_,_),_),Papa = persona(_,Pat,_,_),Mama = persona(_,Mat,_,_),familia(Papa, Mama, Hijos),ingresosl([Papa, Mama | Hijos], S).

% y ahora se hace una consulta

? ingresos(X, Y, Z).X = perezY = toledoZ = 1650000 .



88

Ejemplo de Programa

Autómatas Finitos No Determinísticos



V189

Autómatas Finitos No Determinísticos

• Máquina abstracta que lee un string de símbolos de entrada• El string puede ser aceptado o rechazado• La máquina consiste de estados y transiciones entre estado

al leer un símbolo• Existen transiciones silenciosas que no corresponden a

ninguna entrada• Si se activa más de alguna transición, cualquiera de ellas

puede ocurrir• La máquina tiene un estado inicial y uno final



V190

Ejemplo de un Autómata Finito no Determinístico

s1 s2

s3s4

b

a

b

b

a



V191

Reglas en Prolog para el Autómata% Si esta en un estado final, entonces puede aceptar string nulo.

accepts(State, []) : final(State).

% En un estado se puede aceptar un string no nulo si el primer elemento% provoca una transición a un estado donde el resto del string alli también% puede ser aceptado.

accepts(State, [X | Resto]) : trans(State, X, State1),accepts(State1, Resto).

% Se acepta una transicion silenciosa, si también se acepta el mismo% string en el nuevo estado

accepts(State, String) : silent(State, State1),accepts(State1, String).



V192

Ejemplo en Prolog% ¿String de largo 3 que se acepta en s1?

? accepts(s1, [X1, X2, X3]).

X1 = aX2 = aX3 = b ;

X1 = bX2 = aX3 = b ;no



V193

Ejemplo en Prolog

% ¿String de largo 3 que se acepta en s1?

? String = [_, _, _], accepts(s1, String).

String = [a,a,b] ;

String = [b,a,b] ;no



94

Ejemplo de Programa

Problema de las Ocho Reinas



V195

Problema de las Ocho Reinas

1

2

3

4

5

6

7

8

1 2 3 4 5 6 7 8



V196

Solución #1 en Prologsolucion1([]).solucion1([X/Y | Otras]) : % primera reina en X/Y

solucion1(Otras),member(Y, [1,2,3,4,5,6,7,8]),noataque(X/Y, Otras). % Primera reina no ataca a otras

noataque(_, []).noataque(X/Y, [X1/Y1 | Otras]) :

Y =\= Y1, % diferentes filasY1 Y =\= X1 X, % diferentes diagonalesY1 Y =\= X X1,noataque(X/Y, Otras). % Primera reina no ataca a otras

plantilla([1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]).

solucion(S) : plantilla(S), solucion1(S).



V197

Consulta a la Solución #1

? solucion(S).

S = [1 / 4,2 / 2,3 / 7,4 / 3,5 / 6,6 / 8,7 / 5,8 / 1] ;

S = [1 / 5,2 / 2,3 / 4,4 / 7,5 / 3,6 / 8,7 / 6,8 / 1] ;

S = [1 / 3,2 / 5,3 / 2,4 / 8,5 / 6,6 / 4,7 / 7,8 / 1]



V198

Solución #2 en Prolog (1/2)

% Cada reina debe estar posicionada en una columna X diferente.% Por lo tanto la solucion es del tipo: [Y1, ... Y8].% Para evitar ataques horizontales, las reinas deben estar en diferentes filas,% por lo tanto la solucion es una permutacion de [1,2,3,4,5,6,7,8].

solucion(Reinas) : permutation([1,2,3,4,5,6,7,8], Reinas), seguro(Reinas).

% Un estado es seguro si no existe ataque de una reina a las otras

seguro([]).seguro([Reina | Otras]) : seguro(Otras),

no_ataque(Reina, Otras, 1).



V199

Solución #2 en Prolog (2/2)

% en una lista vacia no hay ataque

no_ataque(_, [], _).

% Existe ataque de una reina Y a otra Y1 ubicada a Xdist columnas si

no_ataque(Y, [Y1 | Ylist], Xdist) :Y1 Y =\= Xdist, % en diferente diagonal crecienteY Y1 =\= Xdist, % en diferente diagonal decrecienteDist is Xdist +1,no_ataque(Y, Ylist, Dist).



V1100

Consulta en Solución #2

? solucion(S).

S = [5,2,6,1,7,4,8,3] ;

...



101

5.8 Control de Backtracking



V1102

¿Porqué controlar Backtracking?

• Prolog realiza backtracking automático si falla la satisfacción de una cláusula

• Sin embargo, en algunos casos el backtracking automático es ineficiente

• El programador puede controlar o prevenir el backtracking usando cut.



V1103

Ejemplo de una Función

• Suponga las siguientes tres reglas para una función de doble escalón:

– Regla#1: Si (X<3) entonces Y=0– Regla#2: Si (3 ≤X) y (X<6), entonces Y=2– Regla#3: Si (6≤X), entonces Y =4

3 6

2

4



V1104

Función Expresada en Prologf(X, 0) : X<3. % regla #1

f(X, 2) : 3 =< X, X < 6. % regla #2

f(X, 4) : 6 =< X. % regla #3

% La consulta siguiente

? f(1, Y), 2<Y.

no



V1105

Evaluación de la Metaf(1, Y)2<Y

1<32<0

2<0

¡NO!

Regla#1Y=0

3≤11<62 < 2

Regla#2Y=2

¡NO!

Regla#3Y=4

¡NO!

6≤12<4

CUT



V1106

Función Expresada en Prolog usando CUT

f(X, 0) : X<3, !. % regla #1

f(X, 2) : 3 =< X, X < 6, !. % regla #2

f(X, 4) : 6 =< X. % regla #3

? f(1, Y), 2<Y.

no



V1107

Observaciones

• Ambas definiciones arrojan el mismo resultado.• Sin embargo, la segunda versión con CUT es más

eficiente dado que reconoce antes que la evaluación ha fallado.

• Se puede decir que el CUT ha modificado el significado procedural del programa (en este caso no ha sido modificado el significado declarativo).



V1108

Evaluación de la Meta

f(7, Y).

7<3

¡NO!

Regla#1Y=0

3≤77<6

Regla#2Y=2

¡NO!

Regla#3Y=4

Exito

6≤7

¡¡No se alcanza el CUT en ninguna evaluación!!

? f(7, Y).Y=4



V1109

Optimizando Evaluación de Función usando CUT

f(X, 0) : X<3, !. % regla #1

f(X, 2) : X < 6, !. % regla #2

f(X, 4) . % regla #3

? f(7, Y).

Y=4



V1110

Evaluación de la Meta

f(7, Y).

7<3

¡NO!

Regla#1Y=0

7<6

Regla#2Y=2

¡NO!

Regla#3Y=4

Exito

¡¡Se reducen el número de evaluaciones!!



V1111

Observación

• Esta optimización sólo funciona con CUT.• Si se sacaran los CUTs y se evalúa f(1, Y)

produciría varios resultados.• En este caso se dice que afecta el

significado declarativo.



V1112

Otro ejemplo con CUT% La función de membresía que se vió es:

member (X, [X | L]).member (X, [Y | L]) : member(X, L).

% se puede transformar en una versión con CUT que sólo% permite encontrar un solo miembro.

member (X, [X | L]) : !.member (X, [Y | L]) : member(X, L).



V1113

Negación como Falla

• A María le gustan los animales:gusta(maria, X) : animal(X).¡¡Pero no le gustan las serpientes!!

• Expresado en Prolog:

gusta(maria, X) : serpiente(X), !, fail;animal(X).



V1114

Ejemplos de NegaciónLa verificación si dos expresiones difieren:

diferente(X, Y) : X = Y, !, fail;true.

El procedimiento interno not de Prolog se comportacomo:

not(P) : P, !, fail; true.



V1115

Aplicación de la Negación

La función diferente ahora se puede escribir como:

diferente(X, Y) : not(X =Y).

Y la regla de Maria:

gusta(maria, X) : not(X = serpiente),animal(X).



V1116

Problema de las 8 Reinas Expresada con Negación

solucion1([]).

solucion1([X/Y | Otras]) : % primera reina en X/Ysolucion1(Otras),member(Y, [1,2,3,4,5,6,7,8]),not ataque(X/Y, Otras). % Primera reina no ataca a otras

ataque(X/Y, Otras) :member(X1/Y1, Otras),(Y = Y1; % en la misma filas, óY1 is Y + X1 X; % en la mismas diagonalesY1 is Y + X X1).

plantilla([1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]).

solucion(S) : plantilla(S), solucion1(S).



V1117

Uso de Cut y Negación

• Ventajas– Se puede aumentar la eficiencia– Se pueden expresar reglas que son mutuamente

exluyentes• Desventajas

– Se pierde correspondencia entre significado declarativo y procedural

– Cambio del orden de las cláusulas puede afectar significado declarativo



118

5.9 Entrada y Salida de Datos en Prolog



V1119

E/S en Prolog

• Hasta ahora sólo se ha visto entrada y salida en forma de preguntas y respuestas (instancias de variables)

• La E/S en Prolog es similar a Scheme:– Existen streams de entrada y salida– Sólo existe un stream activo de entrada y otro

de salida– Archivos son tratados como streams



V1120

Modelo de Comunicación

ProgramaProlog

Terminaldel Usuario

archivo1

archivo2

archivo3

archivo4Streams

deEntrada

Streamsde

Salida

user user



V1121

Abrir y Cerrar un Stream

• see(F). : abre el archivo F como stream actual de entrada.

• seen. : cierra el stream de entrada actual

• tell(F). : abre el archivo F como stream actual de salida.

• told. : cierra el stream de salida actual



V1122

Procesamiento de Archivos de Términos

• read(X) : lee desde el stream actual el término X

• write(X) : escribe en el stream actual el término X

• tab(N) : escribe N espacios en blancos en el stream actual

• nl : escribe nueva línea en el stream actual



V1123

Ejemplo de E/S (1/2)% Calcula el cubo de un número. Se termina con el átomo stop.

cubo : write('Ingrese un número: '),read(X),proceso(X).

proceso(stop) : !.

proceso(N) :C is N*N*N,write('El cubo de '), write(N), write(' es '), write(C), nl, nl,cubo.



V1124

Ejemplo de E/S (2/2)

? cubo.Ingrese un número: 3.El cubo de 3 es 27

Ingrese un número: 10.El cubo de 10 es 1000

Ingrese un número: 34.El cubo de 34 es 39304

Ingrese un número: stop.

yes



V1125

Ejemplo de Salida (1/2)% Escribe un elemento de una lista por línea% En caso que elemento sea lista, se imprime en la línea

writelist([]).writelist([X | L]) :

doline(X), nl, writelist(L).

doline([]).doline([X | L]) :

write(X), tab(1),doline(L).

doline(X) : write(X).



V1126

Ejemplo de Salida (2/2)

? writelist([a, b, [c, d, e], [f, g], e]).abc d e f g e

? writelist([[1, 2], [3, 4, 5, 6], [3, 4, 5]]).1 2 3 4 5 6 3 4 5



V1127

Ejemplo de Gráfico de Barra (1/2)barra([]).

barra([N | L]) :estrella(N), nl,barra(L).

estrella(N) :N =< 0.

estrella(N) :N > 0,write(*),N1 is N1,estrella(N1).



V1128

Ejemplo de Gráfico de Barra (2/2)

? barra([3, 5, 10, 7, 4]).*****************************



V1129

Esquema de Procesamiento de Archivos de Entrada

% ... see(F), leer_arch, see(user), ...

leer_arch : read(Term), % asumiendo que término no es variableprocesar(Term).

procesar(‘!EOF’) : !.

procesar(Term) :tratar(T),leer_arch.



V1130

Ejemplo de Procesamiento de Archivo (1/2)

mostrar_arch(N) :read(T),mostrar(T, N).

mostrar('!EOF', _) : !.

mostrar(T, N) :write(N), tab(2), write(T), nl,N1 is N+1,mostrar_arch(N1).



V1131

Ejemplo de Procesamiento de Archivo (2/2)

? see("parientes.pro"), mostrar_arch(1), see(user).1 padre(maria,pedro)2 padre(juan,pedro)3 padre(juan,carola)4 padre(pedro,ana)5 padre(pedro,paty)6 padre(paty,aldo)

yes



V1132

Ejemplo de Salida Formateadaescriba_familia(familia(H, M, H)) :

nl, write(padres), nl, nl,escriba_persona(H), nl,escriba_persona(M), nl, nl,escriba(hijos), nl, nl,escriba_lista_personas(H).

escriba_persona(persona(Nom, Ape, fecha(D, M, A), T)) :tab(4), write(Nom),tab(1), write(Ape),tab(1), write(', nacido el '),write(D), tab(1), write(' de '),write(M), write(' de '), write(A), write(', '),escriba_trabajo(T).



V1133

Ejemplo de Salida Formateadaescriba_lista_personas([]).

escriba_lista_personas([P | L]) :escriba_persona(P), nl,escriba_lista_personas(L).

escriba_trabajo(cesante) : write(cesante).

escriba_trabajo(trabajo(Emp, S)) :write('trabaja en '), write(Emp), write(', '),write('salario: '), write(S).



V1134

Procesamiento de Archivos de Caracteres

• put(C) : escribe un carácter en el stream actual, donde C es código ASCII

• get0(C) : lee un carácter del stream actual, donde C es código ASCII

• get(C) : lee un carácter no blanco del stream actual (se salta todos los

caracteres no imprimibles)



V1135

Lectura de Archivos de Programa

• consult(F).– Se leen todas las cláusulas de F y son usadas por Prolog

para responder consultas.– Se pueden leer múltiples archivos

• reconsult(F).– Similar a consult, pero permite sobrecargar cláusulas

antiguas que también se encuentran en F– consult agrega cláusula, reconsult permite redefinir.– No afecta a cláusulas que no están en F.

capítulo v: programación l - inf.utfsm.clnoell/ili-253-p2/apunte05.pdf · • cálculo de...

Documents