PDF de programación - Principios de Programación Lógica

Principios de Programación Lógica

Ingeniería Informática

Departamento de Lenguajes y

Ciencias de la Computación

Universidad de Málaga

Contenido

1) Objetos, Relaciones y Objetivos
2) Datos: Objetos y Términos
3) Procedimientos: Hechos y Reglas
4) Programa Principal: Objetivos
5) Semántica Operacional de Prolog
6) Prolog = Programación Lógica

Principios de Programación Lógica

2

Objetos, Relaciones y Objetivos

Programas lógicos y cómputos

Programa lógico (o relacional): conjunto de relaciones entre
objetos

Cómputo: deducción controlada y constructiva de que un objetivo
OOOO es consecuencia lógica de las relaciones definidas en un
programa lógico PPPP

P P P P OOOO

Principios de Programación Lógica

4

Objetos, relaciones y objetivos

Objetos:

se corresponden con los datos
se representan mediante términos

Relaciones:

se corresponden con los procedimientos
se definen mediante hechos y reglas

Objetivos:

se corresponden con el programa principal
se definen mediante consultas

Principios de Programación Lógica

5

¿Cómo se escribe un programa lógico?

Para escribir un programa lógico debemos identificar:

qué objetos intervienen en el problema,
cuáles son las relaciones entre éstos, y
qué objetivos queremos alcanzar

Una vez identificados los elementos anteriores debemos:

representar los objetos mediante términos
definir las relaciones mediante hechos y reglas
definir los objetivos mediante consultas

Ilustraremos la metodología anterior mediante un ejemplo
Problema: escribir un programa lógico que defina relaciones de
parentesco y deduzca qué personas están emparentadas

Principios de Programación Lógica

6

La familia a considerar

Antonio

María

Elena

Carlos

Eva

David

Fernando

Silvia

Emilio

Principios de Programación Lógica

Identificando objetos y relaciones

objetos

relaciones

Antonio

María

Elena

Carlos

Eva

David

Fernando

Silvia

Emilio

Principios de Programación Lógica

7

8

Representando objetos mediante términos

Objetos:

son las personas que forman la familia

representados por términos (sus nombres en minúscula)

Ejemplos:

Antonio  antonio
María  maría

Principios de Programación Lógica

9

Definiendo relaciones mediante hechos

Relaciones:

son las relaciones de paternidad y maternidad

definidas mediante hechos (relaciones incondicionales)

Ejemplos:

Antonio es padre de Carlos  padre(antonio,carlos).
María es madre de Carlos  madre(maría,carlos).

Principios de Programación Lógica

10

La familia completa definida en Prolog

padre(antonio,carlos).

padre(antonio,eva).

padre(carlos,fernando).

padre(carlos,silvia).

padre(david,emilio).

madre(maría,carlos).

madre(maría,eva).

madre(elena,fernando).

madre(elena,silvia).

madre(eva,emilio).

Principios de Programación Lógica

11

Deduciendo objetivos

Objetivos:

son preguntas sobre el parentesco

definidas mediante consultas

Ejemplos:

¿es David padre de Emilio?  :- padre(david,emilio).
¿quiénes son los hijos de Eva?  :- madre(eva,X).
¿quién es el padre de Silvia?  :- padre(P,silvia).

Principios de Programación Lógica

12

Identificando relaciones implícitas

abuelo

Antonio

María

Elena

Carlos

Eva

David

Fernando

Silvia

hermanos

Emilio

primos

Principios de Programación Lógica

13

Una mala idea...

Definimos las relaciones extra mediante hechos:

hermanos(carlos,eva).

hermanos(fernando,silvia).

Inconvenientes:

tamaño excesivo
propenso a errores
mantenimiento (nacimientos, etc.)
adaptabilidad a otras situaciones (familias)

Sería preferible definir esta relación de forma genérica,
identificando las condiciones bajo las cuales dos personas “A” y
“B” son hermanos

Principios de Programación Lógica

14

Definiendo relaciones mediante reglas

¿Cómo podemos definir la relación “hermanos”?

“A y B son hermanos si comparten los padres”

Definiremos la relación condicional anterior mediante la regla:

hermanos(A,B) :-

padre(P,A),

madre(M,A),

padre(P,B),

madre(M,B),

A \== B.

Principios de Programación Lógica

Ejercicios

Define las siguientes relaciones de parentesco:

1. abuelo(A,B) – A es abuelo de B
2. tio(A,B) – A es tío de B
3. primos(A,B) – A y B son primos
4. procrearon(A,B) – A y B tienen algún hijo en común

Principios de Programación Lógica

15

16

Reglas para identificar objetos y relaciones

Objetos: nombres propios y comunes, en singular o plural

Relaciones: verbos y formas verbales

A veces es posible más de una formalización, y la diferencia entre
objeto y relación no está clara...

Una relación determina un conjunto de objetos: aquéllos que la
satisfacen. Por tanto, una relación puede emplearse para
referirnos a estos objetos.

Ejemplo: “Los hijos de Antonio”  padre(antonio,H)

Principios de Programación Lógica

17

Datos: Objetos y Términos

Datos: objetos y términos

Los objetos (datos) se representan mediante términos:

constante

átomo

número

entero

real

término

variable

estructura

Los términos son adecuados para el procesamiento simbólico

Principios de Programación Lógica

19

Átomos

Uso: representan objetos concretos mediante un nombre; es
decir, denominan a un objeto en particular

Sintaxis:

secuencias de letras, dígitos y _ comenzando por minúscula
ejemplos: antonio, x, lista_vacía, nil, x25

secuencias de caracteres entre apóstrofos
ejemplos: ‘antonio garcía’, ‘Antonio’

secuencias de símbolos especiales
ejemplos: +, -, =, ===, ::=, :=, <->, :^:

Principios de Programación Lógica

20

Números

Uso: representan números enteros y reales

Sintaxis:

enteros: 2, 34, -56

reales: -0.0092, 4.5e-5

Se aplican las restricciones típicas de rango (enteros y reales) y
precisión (reales)

Principios de Programación Lógica

21

Variables

Uso: representan objetos por determinar. Las variables son
semejantes a incógnitas: no se les puede asignar valores a
voluntad.

Sintaxis:

Secuencia de letras, dígitos y _ comenzando por mayúscula o _

Ejemplos:

X1
Padre
_X
Num_Telef
ListaClientes

Principios de Programación Lógica

22

Estructuras (I)

Uso: representan objetos compuestos que pueden ser concretos
(no contienen variables) o por determinar (contienen variables)

Sintaxis:

sin espacios

átomo(término1,...,términon)

nombre

aridad

Al par nombre/aridad se le denomina functor de la estructura
Ejemplos:

fecha(17,agosto,2004) % fecha/3

cita(miguel,fecha(Día,enero,2006)) % cita/2

Principios de Programación Lógica

23

Estructuras (II)

Los functores no se declaran.

Puede emplearse el mismo nombre con diferentes aridades: se
trata de functores distintos

Ejemplo:

fecha(17,agosto,2004)

% fecha/3

fecha(14,abril)

% fecha/2

Principios de Programación Lógica

24

Sintaxis (simplificada) de los términos

término ::= átomo

| número

| variable

| estructura

estructura ::= átomo(argumentos)

argumentos ::= término

| término , argumentos

Más adelante extenderemos esta sintaxis con operadores y
listas

Principios de Programación Lógica

25

Prolog comprueba la sintaxis de los términos...

Prolog detecta y señala los siguientes errores sintácticos

2pi

fecha(12,,2001)

fecha()

cita(fernando,fecha(2,diciembre,2001)

lista (a,b,c)

F(X,Y)

Principios de Programación Lógica

26

Pero la intención es lo que cuenta...

La intención es representar las fechas por términos de la forma:

fecha(día,mes,año)

donde día ∈∈∈∈ {1,...,31}

mes ∈∈∈∈ {enero,...,diciembre}
año ∈∈∈∈ {2000,...}

Pero Prolog no puede detectar usos inadecuados:

fecha(enro,2,2001)

La sintaxis es correcta, pero el orden de los argumentos no es el
esperado y enro no es un mes válido
Prolog no conoce las intenciones del programador: no hay
declaraciones de tipo

Principios de Programación Lógica

27

Representación física vs. sintáctica

punteros

arrays
...

registros

objeto a

representar

términos

constantes

functores

...

programador imperativo

programador lógico

Principios de Programación Lógica

28

¿Cómo se representa un objeto en Prolog?

El programador lógico debe decidir una sintaxis adecuada para
cada tipo de dato:

Constantes:

qué nombre o número resulta apropiado

Variables:

se emplean para objetos por determinar (plantillas)

Estructuras:
functor
orden y sintaxis de los argumentos, recursión.

Sin embargo, no hay forma de comunicar a Prolog esta intención:
no hay declaraciones de tipo

Principios de Programación Lógica

29

Ejemplo: representación de pilas (I)

Para representar el TAD pila, el programador debe elegir una
sintaxis adecuada

Sintaxis:

tad_pila ::= pila_vacía

| pila(cima,tad_pila)

cima::= término

Pero no es posible comunicar a Prolog esta sintaxis...

Principios de Programación Lógica

30

Ejemplo: representación de pilas (II)

Ejemplos de pilas bien formadas:

pila(a,pila(b,pila(c,pila_vacía)))

pila(a,pila(fecha(2,enero,2001),pila_vacía))

pila(pila_vacía,pila_vacía)

Ejemplos de términos Prolog que no son pilas bien formadas:

pila(pila_vacía)

pila(a,pila(b))

Principios de Programación Lógica

Ejemplo: representación de pilas (III)

Las estructuras que contienen variables son plantillas:

Ejemplos:
pilas con 2 elementos y a en la cima

pila(a,pila(X,pila_vacía))

pilas de 3 elementos cualesquiera

pila(X,pila(Y,pila(Z,pila_vacía)))

pilas de al menos un elemento

pila(X,Y)

pilas que tienen una b como segundo elemento

pila(X,pila(b,Y))

Las dos últimas plantillas suponen que Y es una pila
Principios de Programación Lógica

31

32

Ejemplo: circuitos digitales (I)

x
y

z

Objetos:

variables de entrada (a,b,c,...,x,y,z)
puertas lógicas (or, and, nand, not)

Principios de Programación Lógica

33

Ejemplo: circuitos digitales (II)

Representación:

entradas -> átomos
puertas -> estructuras or/2,and/2,nand/2,not/1

Sintaxis:

circuito::= entrada

| or(circuito, circuito)

| and(circuito, circuito)

| nand(circuito, circuito)

| not(circuito)

entrada ::= átomo

Principios de