Programación Declarativa

3er Curso. Grado en Ingenierı́a Informática

Prueba de Programación Lógica V-A 18-11-2020

Apellidos: Nombre:
Grado: GII / GII-ONLINE / GII+GADE / GII+GIC / GII+GIS / GII+MAT

La duración de esta prueba es de 1 hora y 15 minutos.

No se permite el uso de ningún tipo de material ni dispositivo electrónico.

Entrada / Salida
¡
Además de los predicados aritméticos, el corte y la negación, se podrán utilizar los si-
M
guientes: length(?L,?N) (cierto si N es la longitud de la lista L), append(?L1,?L2,?L)
(cierto si L es la concatenación de las listas L1 y L2), reverse(?L1,?L2) (cierto si L2
es la inversa de la lista L1), member(?E,?L) (cierto si E pertenece a L), is_list(+L)
(cierto si L es una lista), sumlist(+L,?N) (cierto si L es una lista de números cu-
ya suma es N), map(+Obj,+L) (cierto si Obj se ejecuta con éxito sobre todos los ele-

-mentos de la lista L), map(+Obj,?L1,?L2) (cierto si Obj se ejecuta con éxito sobre
todas las parejas de elementos de las listas L1 y L2 situados en la misma posición), Salida
Entrada include/exclude(+Obj,+L1,?L2) (cierto si L2 incluye/excluye los elementos de la lis-
ta L1 sobre los que se ejecuta con éxito Obj), pliegai(+Obj,+L,+VI,-VF), cierto si
VF es el resultado de plegar mediante Obj la lista L desde la izquierda partiendo de
✓
VI), number/integer/var/nonvar(+N) (cierto si N es un número/entero/variable/nova-
riable), call(+Obj,+E1,..) (cierto si Obj, con parámetros extra E1,.., se ejecuta con
éxito) y los predicados de recolección bagof/setof/findall(?T, +Obj, ?L).

1. (1.5 puntos) Razone qué se obtendrı́a (un error, true, false, computación infinita,
respuesta(s) que serı́a(n) ...) al ejecutar en Prolog la siguiente consulta, solicitando
todas las posibles soluciones: R :[[1,214] /[2,4]/ [4]],
TIÍ
-

NR = [71614] ,
'

t
[
-
-
-
-

?- findall(NY, (append(T,Y,[1,2,a,4]), -

length(Y,LY),
,
,
,
,
A- = 7
LY >= 2, include(integer,Y,NY)), R),
map(sumlist, R, NR), filter .NL
Mi
member(A, NR), !. Variable que almacena
representa predicado tienen que la lista con la
a los elementos recolección de las soluciones
de
corte que elemento
los ,

que vamos
a almacenar cumplir
se almacenen
Solución:
que
en la lista para
El predicado findall construye la en R lalista resultado
lista de todos los NY que resultanR de fil-
en .my
trar (include) los números enteros de
LYtodos los posibles sufijos Y de [1,2,a,4]
T tamañoY [1,2 ait ] ✓ siguientes
>= 2 las [
[[11214]]
1. 2,4 ]combinaciones:
lo cualyexisten
,

con igual o superior a 2, para 4

[[11214 ] / [214]]
1a-1T [ ]
T=[], [ 112 ait]
Y=[1,2,a,4],
/ LY=4, NY=[1,2,4], T=[1], ✓ [ 2,4
Y=[2,a,4], ] LY=3, NY=[2,4]
>= , 4] ]
.

y T=[1,2], Y=[a,4],
] LY=2, NY=[4] 3(en elzresto de descomposiciones
4] [ [11214
de ] [2,4] [
,
[1,2,a,4]
/
Ziait [
ZAIT [el1]
.
[
sufijo Y tiene tamaño menor que 2).2Como2el3=2
✓
predicado findall solo se interesa
] Cait ]
=L X
3a.IT [1,2
.
por los NY,[resultará
t ] R=[[1, 2, 4], 1 [2, 4], 1 >[4]]. A continuación el predicado
] ×
tait CLR /a
map/3 aplica sumlist a cada una de las 05-2
listas de transformando cada lista
.

] [] 0 R,
at
Salt [112
.
/

NR A
Página 1 de 4
[ 716,4]
t.IT?--
 ( ÍL ?N)
length deuueluelalongituddelalistal-i.to
,
:

Tero
cierto si N es el número de elementos de la lista L
b Ar

]
? ( [ 1,213 ] , 3)
-

length .

True ✓
An &
.

)
? -

length ( [ 112,3 ] , N .

N =3 .

P b
3)
? -
length ( L , .
×

final :
predicado recolección de soluciones
de decir , es , devuelve
lista todos los elementos determinada condicion
qe cumplen
una con .

Los elementos se
pueden repetir yno tienen ningun orden .
include ( Integer , [ 1,2 , ait] ,
NY )

[ 1]
191T .

ánteger (1) →

112 ]
211T .

ánteger (2) → [

) [ 112 ]
311T .
ántegerca →

[ 11214 ]
ta-lt.in/-egerCt1 →

[ 2,4 ] / [ 4 ] ] NR )
mapcsumlist , [ [ 112,4 ] , ,

14T .
→
sumlist ( [ 112,4] ,
±> [ 7]

sumlistc [ 2,4] 6) → [ 7,6 ]

zalt .
,

sumlist ( [ t] 4) [ 71614]
3- It . , →
 member CA [ 7/6 4] )
member (7/[7,6/4])
, ,
?
pertenece
-
.

true .

se lt .
A- = 7

Elt .
A- = 6

Salt .
A- = 4
 Prueba de Programación Lógica V-A – 18-11-2020 (cont.)

en su suma, NR = [1+2+4=7, 2+4=6, 4], y por último el predicado member eli-

ge el primer elemento de esta última lista, dando A=7. Si se retrocede en busca
de más soluciones, las siguientes alternativas de member quedan podadas por el
corte final. Por todo lo anterior, la consulta dada darı́a como única respuesta la
del madrid ( )
siguiente:
hechos → _ sergio .

NR = [ 7 , 6 , → natural ( N )
R = [[1 , 2 , 4] , [2 , 4] , [ 4 ] ] ,
:-
reglas 4 ] , es _

)
A = 7.
Integer ( N ,

N >= ¢ .

2. (2 puntos) Considere el predicado ex(+L, +N, ?NL), cierto si L es una lista com-
puesta exclusivamente por términos no variables, N es un natural positivo y NL es
la lista resultante tras duplicar en L el elemento situado en la posición N, enten-
diendo que la cabeza de la lista está situada en la posición 1. El predicado no debe
producir ningún error en tiempo de ejecución y debe fallar si la operación no se
puede ejecutar porque la posición N es mayor que la longitud de L. Por ejemplo,
las consultas ?- ex(a,1,X), ?- ex([1],-1,X), ?- ex([],1,X), ?- ex([2],3,X),
?- ex([A],1,X) y ?- ex([1,2],a,X) darı́an false, ?- ex([1,2],1,[1,1,2]) de-
volverı́a true y ?- ex([1,a,5,3],3,X) darı́a X=[1,a,5,5,3] como única solución.
Proponga una implementación no recursiva para el predicado ex, basada en el uso
de algunos de los predicados mencionados al comienzo del enunciado.
88
EXCLININL ) maplnonvar / L )
ÁF
:
.
. .
-

maplnonvaril) ,

(
Solución:
natural positivo
Integer
ex (L , N, NL) :
N > ¢
(N) ,
] Nseaun
L1 L2
[ 1 / a 5/3]
,
m a p l i s t ( nonvar , L )-1°C
, ]
, L) ,
/

append ( 11112
i n t e g e r (N) ,[1. aislado [ 1 ] la / 5/3 ] [ E / El L2]
length
N >= ( L11 ,N ) ,
append
[1 , a.
533
, [
11a.SI#rC1,a ] [ 5,3 ]
( Pref , [C|R] , Lg.)[,1. 5] [3 ]
A a /

N1 i s N /1,[E] L1 ) )
appendl - ,
[ 1 / ais } ] C ,
]
[ 1ra] [ 5 ]
l e n g t h ( Pref , N1 ) , ) LZ
/ L1 ] / NL , L1 [11A 5,5/3]
append
→
, [ ,
EILZ
.
,
append ( Pref [ C,C|R] NL ) . + 5 1- [z ]
[1 ais] [1. a. 5]
]
/

[5 / [ 3]
[ 5,3] [dia, 515,3]
3. (2 puntos) Considere el predicado ex(+L, ?NL), cierto si L es una lista y NL es
la lista obtenida de L tras intercambiar el último número (empezando por la iz-
quierda) que aparece en L con el elemento situado justo a continuación suyo. Si
L no contuviese ningún número o su último número no tuviese siguiente, NL serı́a
igual a L. Por ejemplo, la consulta ?- ex(a,X) darı́a false y ?- ex([a,b],X),
?- ex([1,a,4],X), ?- ex([1,3,a],X) y ?- ex([a,1,3,c,a],X) darı́an, respecti-
vamente, X=[a,b], X=[1,a,4], X=[1,a,3] y ex([a,1,c,3,a],X) como única solu-
ción. Proponga una implementación recursiva para el predicado ex.

Página 2 de 4
 C- , )
map ,
-
-

? / a)
maplnonvar L ) / forall nonvar
-
.

true .

? -
nonvar (7) .

true .

? - nonuar (X) .

false .

? [ 1 , X , a] )
-

mapcnonvar ,
.

false
? C1 /XI a] , NL )
mapcnonvari
.

NL = [ true , false , tra ]

 Prueba de Programación Lógica V-A – 18-11-2020 (cont.)
e. ✗ ( + Li ? NL )
V1 CLIEX aux
a [3lb]
( [ CIR ] , NL ) : - CR X

C1 L , NL)
( Solución:
: - -

e. ✗ )
aux ( R , NNL ,
is listcl ), ex -

ex ( [ ] , [ ] ) .
-

]
LINL) NL = [ CINNL
[ C1 , C2(|R] , [ C2 , C1 |R ] ) :
.

ex ( aux
ex
.

CZ number (C1
aux ( [] , [
] ) ) , CB1
% C1 e s un número
ex .

[b]
-

l u d3
i n ca e ( number , [ C2 |R] CBZ
NL) :
, []) , % y e s e l ú l t i m o
1 CZIR ] ,
-

[3 ([
! .[
ex aux
-

nvmber ( C1) ,
,
[CZIR] , [ ] )
I include ( number
,
]) ,
,
ex ( [ C|R] , number
[C|NR]
,[
) CZIR
:
Fap ex (R, NR) .
NL = [ CZICDIR
] .

? ( [aiasib ] , ✗ ) .

predicado e. ✗

)
-
[b]
de
a 3
§ [ a/ b / 3]

:
[aissib ]
negación 4. Considere el siguiente código: [3ex.ae/n(Cai3ib] , ×

(not ) C1 : a
mist([], 0). CZ:3

mist([C|R], N) :- R Eaib/ 3]
( Ca 3lb] / X )
number(C),
[4 ex aux ,

ca.yni.p.biz#
!, -

mist(R, N). Cia

mist([_|R], N):-
R :[3lb]
☒ ex auxcczib] ,
Fbn }}'

mist(R, NR),
-

C1 :3
/
N is NR+1.
R :[]
(a) (0.5 puntos) Describa en lenguaje natural (con sus propias palabras) el cometido
del predicado anterior: “mist(L,N) es cierto si ...”
NL = [a / b) 3 ]

Solución:
mist(L,N) es cierto si N es el número de elementos de la lista L que NO son
números.

(b) (1.5 puntos) ¿Presenta el código anterior recursión de cola (recursión final)?
Justifique su respuesta y proponga una implementación alternativa, con o sin
recursión de cola dependiendo de su respuesta a la pregunta anterior.

Solución:
La implementación propuesta no tiene recursión de cola puesto que en la
tercera cláusula se realiza una suma después de la llamada recursiva. Una
implementación alternativa, incorporando un parámetro de acumulación pa-
ra conseguir recursión de cola, podrı́a ser la siguiente:
m i s t c (L , N) :
m i s t c (L , 0 , N ) .

m i s t c ( [ ] , Ac , Ac ) .
m i s t c ( [ C|R] , Ac , N) :
number (C) ,
!,

Página 3 de 4
 V12 C])
V3
e. ✗ ( + Li ? NL ) a [3lb]
ex ( [] , .

( [ CIR ] , CCINNL )
X
C} ex
] :-( R
aux
( L , NL)
:
C1
[ (2×[11/2]) :
- -

ex-auxlR.MN " ( [ CIICZIR ]

e. ✗
lista )
. -

¡s _
, ex ,

ex aux ( LINL)
( C1 ) ,
.

number
_

CZ [ ])
( [] ,
CB1
CZIR ])
[ ltnumber , [
ex aux .

]
-

3 [ b
a ) CBZ
] , [CZICLIR ]
: -
.

C.3 ex aux ( [C1 , CZIR

-

[CZIR] , [ ] ) map
nvmber ( C1) ,
I include ( number
,
CZIR] ) .
→④
,
number, [

( [a >' " ' × )

D
? ( [ CIR ], [ CINNL] ) :
.
'

predicado ex ex

1)
- -

de § [ "" b " }]

R:[ ¡¡
negación [3ex.ae/n(Cai3ib] , ✗
ex ( R , NNL ) .

(not ) C1 : a
CZ:3
3]
'
? -

par ([42,3/4]/11) .

[+ ex aux ( ca }, ,] ,
,

csizm.p.biz#
X)
-

C. a
? ( a/ ✗ =L
R :[sib]
FÍE} - ex .
;
☒ ex auxcczib] ,
,

11=4
/
falsa ;
-

C2 :b
R :C] false .

NL = [a / b) 3]
 Prueba de Programación Lógica V-A – 18-11-2020 (cont.)

m i s t c (R, Ac , N ) .
m i s t c ( [ |R] , Ac , N) :
NAc i s Ac + 1,
m i s t c (R, NAc , N ) .

5. (2.5 puntos) Dados el programa que se incluye en la otra cara de esta hoja y la
consulta

?- - q(X,Y), \+ m(X).

dibuje el Árbol de Resolución correspondiente, etiquetando cada arco con el uni-

ficador de máxima generalidad utilizado y marcando claramente las posibles ramas
podadas, ramas fallo, ramas infinitas o ramas éxito. En caso de haber soluciones, es-
tas solo se valorarán si se acompañan de los cálculos que permiten obtenerlas. Indique
además qué respuesta(s) ofrecerı́a Prolog ante la consulta dada, y en qué orden lo
harı́a.

q(X,Y) :- m(X), h(X,Y). | h(b,c).

q(X,Y) :- h(Y,X). | m(b).
q(a,b) :- !. |
q(a,c). |

Solución:
El árbol de Resolución asociado tiene, de izquierda a derecha, las siguientes ramas
(en el examen habı́a que dibujarlo): una rama fallo, una rama podada por un corte,
una rama fallo, una rama éxito con respuesta asociada X=c, Y=b, otra rama fallo,
una rama éxito con respuesta X=a, Y=b y una rama podada por un corte.
Además de dibujar el árbol, de acuerdo con el enunciado, era necesario:

Acompañar cada una de las soluciones de los cálculos que permiten obte-
nerlas (aplicando a cada una de las variables de la consulta los umg’s de la
rama éxito correspondiente, en orden, empezando por la raı́z).

Indicar qué respuestas ofrece Prolog ante la consulta dada y en qué orden
las da: dado que Prolog construye el árbol en profundidad por la izquierda,
ignorando tanto ramas fallo como ramas podadas, la primera respuesta serı́a
X=c, Y=b, la siguiente X=a, Y=b y acabarı́a con un false (indicando que
no hay más respuestas).

Página 4 de 4