Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Prolog

Cátedra Paradigmas de Programación
by

Horacio Omar Martín

on 21 May 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Prolog

Proposiciones --> hechos
Juan es un programador. --> programador (juan).
Pedro es el primer ministro. --> primer_ministro (pedro).
Google emplea a juan. --> emplea (google, juan).


Sintaxis:
predicado (argumento, argumento, ....).
minúsculas
argumentos separados por comas
las cláusulas terminan en punto
guión bajo para separar predicados compuestos

PROLOG

PRO
gramación
LOG
ica
Paradigma declarativo
Creado por Alain Colmerauer en 1970
Áreas de aplicación: Sistemas Expertos (Inteligencia artificial)
Combinado con otros paradigmas (Visual Prolog)
Embebido en lenguajes algorítmicos (C, Java)
Visual Prolog: Sección predicates
predicates --> definición de predicados y argumentos (tipos, de entrada, de salida, determinísticos o no determinísticos)

PREDICATES
lagarto(symbol)
serpiente(symbol)
mamifero(symbol)
marsupial(symbol)
pez(symbol)
devoran(symbol,symbol) - nondeterm (i,o), nondeterm (o,i), nondeterm (o,o),
nondeterm (i,i)
carnivoro(symbol) - nondeterm (i), nondeterm (o)
Visual Prolog: Sección goal
goal --> consultas a la base de conocimientos

GOAL
marsupial(Y).
/* carnivoro(X). */
/* devoran(cobras,X), mamifero(X);*/
/* devoran(_,Presas).*/
Visual Prolog: Sección clauses
clauses --> hechos y reglas

CLAUSES
lagarto(iguanas).
serpiente(cobras).
mamifero(ratas).
marsupial(canguros).
pez(tiburones).
devoran(cobras,sapos).
devoran(cobras,ratas).
devoran(cobras,iguanas).
carnivoro(X):-devoran(X,_).
Reglas
Todo programador es un profesional informático.
programador (X) :- profesional_informático (X).

Si X y Y están casados entonces X es esposa de Y.
esposa (X, Y) :- casados (X, Y).
esposo (X, Y) :- casados (Y, X).

Si X es un varón y adulto entonces X es hombre.
hombre (X) :- varon (X), adulto (X).

La madre o el padre de una persona son progenitores.
progenitor (X, Y) :- madre (X,Y); padre (X,Y).

Sintaxis:
Variables en mayúsculas
La variable a ambos lados de la regla (puede haber variables auxiliares en el cuerpo de la regla)
La coma significa
Y lógico
El punto y coma significa
O lógico
El símbolo de inferencia :- se lee
SI
(difiere de la implicación) 5
Consultas
¿Juan es un programador?
Consulta: programador (juan).
Rta: si o no

¿quienes son programadores?
Consulta: programador (X).
Rta: X = juan,
etc.

Sintaxis:
similar a los hechos y reglas.
Variable en blanco
Se utiliza cuando es necesario reconocer la existencia de un argumento, pero no se desea instanciarlo por un valor constante.

Una persona es esposa si está casada con alguien.
esposa (X):- casados (X, _).
esposo (X):- casados (_, X).

Aritmética
PREDICATES
asignacion()
suma(real,real,real)
area(real,real,real)
absoluto(real,real)- nondeterm (i,o)
paridad(integer,symbol)- nondeterm (i,o)

CLAUSES
asignacion:-Resultado=3+2, write (Resultado), nl, Resultado=3-2, write(Resultado).
suma(X,Y,Z):- Z = X+Y.
area(Base, Altura, Area):-X=Base*Altura, Area=X/2.
absoluto(X,Y):-X>0, Y=X; X<=0, Y=X*-1.
paridad(X,P):-Z=X mod 2, Z=0,P=par;Z=X mod 2, Z<>0,P=impar.

El signo = es asignación la primera vez que aparece en una cláusula, luego es operador de comparación.
GOAL
asignacion().
/* suma(4,3,Total);
area(3,4,A).
absoluto(-3,Y).
paridad(32,Paridad).
*/
Sección domains: Tipo estructura o functores
DOMAINS
nombre=persona(symbol, symbol)
cumple = fecha(symbol, integer, integer)
tel = symbol

PREDICATES
agenda nondeterm (persona(o,o),o,fecha(o,o,o))

CLAUSES
agenda(persona(juan, perez), "422208", fecha(agosto, 3, 1955)).
agenda(persona(pedro, rodriguez), "433906", fecha(mayo, 12, 1962)).

GOAL
agenda(persona(Nombre,Apellido), Tel,fecha(Mes,Dia,Anio)).
Entradas y Salidas
Predicados predefinidos: write - readln - nl
PREDICATES
ingrese_clave() - nondeterm()
verificar(symbol)- nondeterm (i)

CLAUSES
ingrese_clave:-readln(X), verificar(X).
verificar(horacio):-write("OK"), nl.
verificar(_):-write("ERROR"), nl.

GOAL
ingrese_clave.

Modos de Predicados
Tipos de dominios standars

char
real
integer
shot, ushort
long, uloing
integer, unsigned
byte, sbyte
word, dword
string
symbol
Negación
PREDICATES
hombre(symbol) - nondeterm (i), nondeterm (o)
persona(symbol)- nondeterm (i), nondeterm (o)

CLAUSES
persona(maria).
persona(matias).
persona(jose).
mujer(maria).
hombre(X):-persona(X),
not
(mujer(X)).


GOAL
hombre(X).
Condicional: Si A entonces B
A --> B
Inferencia: B si A
B :- A
Búsqueda en la Base de Conocimiento I
La búsqueda se realiza recorriendo de arriba hacia abajo la Base de Conocimiento (BC).
Si
la consulta no tiene variables
se "alcanza una
meta
" (goal) cuando la consulta coincide o "
empata
" con un hecho. En tal caso devuelve la respuesta: YES y continúa buscando más coincidencias. Si no encuentra coincidencias devuelve: NO. Ejemplo:
CLAUSES
empleado (ortiz).
empleado (zavala).
cadete (ramos).
gerente (jimenez).
gerente (mejia).
supervisa (X, Y) :-gerente (X), empleado (Y).
supervisa (X, Y) :-empleado (X), cadete (Y).
supervisa (X, Y) :-gerente (X), cadete (Y).


Recursividad (o Recurrencia)
Es la habilidad de definir un predicado en términos de sí mismo.

Ejemplo:
"Los
antepasados
de alguien son los
antepasados
de su padre".
Definir en la sección CLAUSES una serie de hechos que describan tu árbol genealógico (hasta cierto nivel) de la forma:
padre (
padre, hijo/a
).
Y las reglas:
antepasados(X,Y):-padre(X,Y). // 1º arg. X son los antepasados
antepasados(X,Y):-padre(Z,Y), antepasados(X,Z).
Luego consulta desde las sección GOAL quienes son tus antepasados.
Si l
a consulta tiene variables
se alcanza la meta cuando:

los predicados de un hecho y de una consulta coinciden
y el número de argumentos (NOAR) de ambos es igual. Entonces se asignan los valores constantes de los argumentos del hecho a las variables de la consulta. Luego continúa buscando más empates. Para el ejemplo anterior:

CLAUSES
empleado (ortiz).
empleado (zavala).
cadete (ramos).
gerente (jimenez).
gerente (mejia).
supervisa (X, Y) :-gerente (X), empleado (Y).
supervisa (X, Y) :-empleado (X), cadete (Y).
supervisa (X, Y) :-gerente (X), cadete (Y).

Búsqueda en la Base de Conocimiento II
Búsqueda en la Base de Conocimiento III
Si el predicado de la consulta coincide con el predicado de una regla con algún argumento constante
:
Se asignan las constantes de la consulta a la variables del encabezado de la regla que ocupan la misma posición entre los argumentos. Ejemplo:
CLAUSES
empleado (ortiz).
empleado (zavala).
cadete (ramos).
gerente (jimenez).
gerente (mejia).
supervisa (X, Y) :-empleado (X), cadete (Y).
supervisa (X, Y) :-gerente (X), empleado (Y).
supervisa (X, Y) :-gerente (X), cadete (Y).
GOAL
empleado (zavala). --> YES
empleado (perez). --> NO
GOAL
empleado (X).
Respuestas:
X = ortiz
X = zavala
GOAL
supervisa (ortiz, Y). --> ¿a quiénes supervisa Ortiz?

Al encontrar la primera regla se asigna X = ortiz pero
ahora debe confirmar la regla ...
Búsqueda en la Base de Conocimiento III
Luego se recorre el cuerpo de la regla de izquierda a derecha: por cada predicado que contenga el cuerpo de la regla se inicia una nueva búsqueda desde el principio de la BC.
Si el primero de estos predicados coincide con la consulta se dice que se alcanzó una
submeta
y se procede como en I o II. Luego se continúa con el siguiente predicado del
cuerpo
de la regla.
Si un predicado del cuerpo de la regla no puede ser empatado, se abandona la búsqueda en esa regla y se prosigue buscando con la siguiente en la BC.
CLAUSES
empleado (ortiz).
empleado (zavala).
cadete (ramos).
gerente (jimenez).
gerente (mejia).
supervisa (X, Y) :-empleado (X), cadete (Y).
supervisa (X, Y) :-gerente (X), empleado (Y).
supervisa (X, Y) :-gerente (X), cadete (Y).
Luego, recorriendo la regla de izquierda a derecha se encuentra: empleado(X) instanciado como
empelado (ortiz). Se busca desde el principio de la BC
y se encuentra en el primer hecho. Por lo tanto, se vuelve a la regla y se procede con el siguiente predicado: cadete (Y). Encuentra que empata con el tercer hecho y por lo tanto asigna Y = ramos
Ahora se vuelve a buscar más coincidencias de cadete (Y) a partir del hecho siguiente, pero no las hay, así que falla y finaliza.
El corte !
El operador de corte ! tiene el efecto de restringir el funcionamiento del mecanismo de búsqueda
impidiendo la regresión
o backtracking.

CLAUSES
progenitor (juan).
progenitor (alfredo).
progenitora (juana).
varon (juan).
varon (alfredo).
mujer (juana).
padre (X):-progenitor (X), varon (X),
!.
-->
Búsqueda en la Base de Conocimiento IV
Si el
predicado de la consulta coincide con el predicado de una regla sin argumentos constantes:

CLAUSES
empleado (ortiz).
empleado (zavala).
cadete (ramos).
gerente (jimenez).
gerente (mejia).
supervisa (X, Y) :-empleado (X), cadete (Y).
supervisa (X, Y) :-gerente (X), empleado (Y).
supervisa (X, Y) :-gerente (X), cadete (Y).
GOAL
supervisa (X, Y) --> ¿quien supervisa a quien?
El empate con la 1ª regla no puede instanciar variables pero comienza a recorrer el cuerpo de la regla. Inicia entonces una nueva búsqueda: empleado (X). Procediendo como en II encuentra X = ortiz. Avanzando hacia la izquierda de la regla debe buscar ahora: cadete (Y). Procediendo como en II encuentra Y = ramos.
Ha completado la regla y entrega la solución:
X = ortiz Y = ramos
Pero hay más soluciones por lo que debe buscarlas...
-->
Búsqueda en la Base de Conocimiento IV
Si el
predicado de la consulta coincide con el predicado de una regla sin argumentos constantes:

CLAUSES
empleado (ortiz).
empleado (zavala).
cadete (ramos).
gerente (jimenez).
gerente (mejia).
supervisa (X, Y) :-empleado (X), cadete (Y).
supervisa (X, Y) :-gerente (X), empleado (Y).
supervisa (X, Y) :-gerente (X), cadete (Y).
GOAL
supervisa (X, Y) --> ¿quien supervisa a quien?
El empate con la 1ª regla no puede instanciar variables pero comienza a recorrer el cuerpo de la regla. Inicia entonces una nueva búsqueda: empleado (X). Procediendo como en II encuentra X = ortiz. Avanzando hacia la izquierda de la regla debe buscar ahora: cadete (Y). Procediendo como en II encuentra Y = ramos.
Ha completado la regla y entrega la solución:
X = ortiz Y = ramos
Pero hay más soluciones por lo que debe buscarlas...
X permanece instanciada a ortiz por lo que busca más soluciones con la submeta cadete (Y). Como no la encuentra, ahora regresará buscando otro empate para la cláusula empleado (X) empezando por la cláusula que está por debajo de empleado (ortiz). El proceso de intentar empatar de nuevo una cláusula si falla la que está inmediatamente a su derecha se llama
REGRESIÓN o BACKTRACKING
. Al encontrar empleado (zavala) asigna ahora X = zabala y repite el proceso indicado en IV.
Analice: ¿cual será la respuesta de la consulta?
GOAL
padre (X).
Fail
Fail es un predicado predefinido cuyo efecto es
forzar la falla
de la búsqueda en el lugar en que se introduzca.

PREDICATES
hijo(symbol,symbol)- nondeterm (o,o)

CLAUSES
hijo(matias, horacio).
hijo(franco, lorenzo).
hijo(gabriel, santiago).

Sección domains: Tipo predicados
DOMAINS
operacion = determ INTEGER (INTEGER, INTEGER) - (i,i)

PREDICATES
suma: operacion
multiplicacion: operacion
calcular(operacion, integer, integer,integer)

CLAUSES
multiplicacion(Op1, Op2, Res):-Res=Op1*Op2.
suma(Op1, Op2, Res):-Res=Op1+Op2.
calcular(Operacion, Op1, Op2, Res):-Res=Operacion(Op1, Op2).

GOAL
calcular(multiplicacion, 3, 4, R).
/* calcular(suma, 2, 3, R). */
Analice el ejemplo con y sin fail.
GOAL
hijo(X,Y),write(Y, " es padre de ",X, "\n"),fail.
¿Cuáles serán las respuestas
para éstas consultas?
Observe que ocurre con la primera consulta. Analice las demás.
Un uso de la sección domais que otorga "polimorfismo" al predicado calcular.
3
4
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Recursividad matemática

Ejemplo: El factorial de un número entero positivo se define en matemáticas como:
Si N = 0 entonces Factorial = 1
Si N > 0 entonces Factorial = N * Factorial (N-1)

Adaptándolo a la sintaxis de Prolog resulta:
factorial(0,1).
factorial (N, X):- N > 0, M = N - 1, factorial (M, Y), X = M*Y.


27
Paradigmas de Programación
Programación Lógica

Compruebe estas reglas en VisualProlog e investigue cómo se genera la solución en forma recurrente. ¿Que rol importante para la recurrencia cumple la primera regla?
Extienda la BC integrando hechos y reglas para considerar también a los antepasados por línea materna.
Cuando haya más de un predicado con el mismo identificador, deben ubicarse en forma consecutiva en la BC.
Full transcript