Upload
robo-prometheus
View
251
Download
1
Embed Size (px)
Citation preview
7/24/2019 Introduo a Prolog
1/52
Introduo a Prolog
Aula terico-prtica
7/24/2019 Introduo a Prolog
2/52
O que Prolog?
Linguagem mais divulgada do paradigma de Programaoem Lgica
Baseado em clusulas de Horn
P1 P2 P3 ... Pn Q
Operacionalizao simples, prtica e eficiente da metfora daprogramao em lgica
Metfora da programao em lgica
Programar = Declarar axiomas e regras
Teoria Lgica x Prolog
Axiomas: Fatos prolog
Regras: Regras prolog
Teoremas: Deduzidos a partir dos fatos e regras
7/24/2019 Introduo a Prolog
3/52
Exemplo - Fatos
parent(pam, bob).
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).parent(pat, jim).
female(pam).
female(ann).
female(pat).
female(liz).
male(bob).
male(tom).
male(jim).
pam tom
bob
jim
ann pat
liz
7/24/2019 Introduo a Prolog
4/52
Exemplo Perguntas base de
fatos
Bob filho de Jim?
- parent(jim, bob).
false
Bob filho de quem?
- parent(X, bob).X = pam ;
X = tom ;
Encontre X e Y tal que X progenitor de Y.
parent(X, Y).X = pam
Y = bob ;
...
pam tom
bob
jim
ann pat
liz
7/24/2019 Introduo a Prolog
5/52
Exemplo Regras
Quem o pai de bob?
- parent(X, bob),male(X).
X = tom
Definindo uma regra para paifather(X, Y) :- parent(X,
Y), male(X).
Isto a sintaxe em prolog para
x, y parent(x, y) male(x)
father(x, y)Agora podemos perguntar
- father(X, bob).
X = tom
pam tom
bob
jim
ann pat
liz
7/24/2019 Introduo a Prolog
6/52
Exerccio 1
Defina as regras: (arquivo family.P)
mother(X,Y)
sister(X, Y)
grandparent(X, Y)
Defina a regra:
aunt(X, Y)
Dica: voc pode usar a regra sister(X, Y) definida anteriormente
7/24/2019 Introduo a Prolog
7/52
Exemplo Regras recursivas
Quais so os ancestrais de jim?
Podemos expressar a relao
ancestor(X, Y) por uma regra
recursiva
ancestor(X, Y) :-father(X, Y).
ancestor(X, Y) :-
father(X, Z),
ancestor(Z, Y).
Faa as perguntas Quem so os ancestrais de Jim?
Bob ancestral de quem? E Jim?
pam tom
bob
jim
ann pat
liz
7/24/2019 Introduo a Prolog
8/52
Sintaxe de Prolog
fato -> fa. (abreviao para Formula Atmica)
regra -> fa0 :- fa1, ... , faN.
consulta -> fa1, ... , faN.
fa -> pred(termo1, ... , termoN) | preop termo1 termo2| termo1 inop termo2 | termo1 termo2 postop
termo -> constante | varivel | fa
constante -> tomos | nmeros
pred -> tomo
7/24/2019 Introduo a Prolog
9/52
Sintaxe de Prolog (2)
varivel ex:C, Chico, Francisco_carvalho, Chico1, _fatc,_
tomo ex:c, fatc, =>, francisco_carvalho, chico1, chico ia
nmero ex:23
termos, fatos, regras e consultassemvariveis:
instanciados(ground) ex.: person(bob,40,cs).
termos, fatos e regras comvariveis:
universais
ex.:father(adao,X).
father(X, Y) :- parent(X, Y), male(X). consultas comvariveis:
existenciais
ex.:- father(F,P).
7/24/2019 Introduo a Prolog
10/52
Intepretao de um programa
Prolog
P :- Q, R.
Interpretaes declarativas
P verdadeiro se Q e R forem verdadeiros.
Q e R implica P.
Interpretaes procedurais
Para resolver o problema P:
Primeiro resolva o subproblema Q
Depois resolva o subproblema R
Para satisfazer P:
Primeiro satisfaa Q
E ento satisfaa R
7/24/2019 Introduo a Prolog
11/52
Interpretador Prolog: Controle e Busca
(funcionamento procedural)
Aplica regra de resoluo:
com estratgia linear(sempre tenta unificar ltimo fatoa provar
com a concluso de uma clusula do programa),
na ordem escritadas clusulas no programa,
com encadeamentode regras regressivo (backward-chaining),
busca emprofundidadee
da esquerda para direitadas premissas das clusulas,
e com backtrackingsistemticoe linearquando a unificao
falha, e sem occur-checkna unificao.
7/24/2019 Introduo a Prolog
12/52
Prolog e aritmtica
Operadores aritmticos
+adio
- subtrao
* multiplicao
/ diviso
**potenciao
//diviso inteira
mod mdulo (resto da diviso
inteira)
O atribuidor is VarivelisExpr. Aritmtica
Exemplos
- X = 1 + 2
X = 1 + 2
- X is 1 + 2
X = 3
- X is 5/2, Y is 5//2,Z is 5 mod 2.
X = 2.5
Y = 2
Z = 1
7/24/2019 Introduo a Prolog
13/52
Prolog e aritmtica (2)
Operadores de comparao
>maior que
= maior ou igual
=< menor ou igual =:= teste de igualdade
aritmtica
=\= teste de diferena
aritmtica
Exemplos
- 1 + 2 =:= 2 + 1.
yes
- 1 + 2 = 2 + 1.
no
- 1 + A = B + 2.
A = 2
B = 1
7/24/2019 Introduo a Prolog
14/52
Exemplo Aritmtico - Fatorial
factorial(0, 1).
factorial(N, Fn) :-
N > 0,
M is N - 1,
factorial(M, Fm),
Fn is N * Fm.
(arquivo fac.P)
- factorial(10, X).
X = 362880
- factorial(10, 362880).
yes
- factorial(10, 10000).
no
7/24/2019 Introduo a Prolog
15/52
Exerccio 2
Defina uma regra fib(X, Y) que calcula o nmero de fibonacci
de X, atribuindo-o a Y.
A sequncia de Fibonacci definida matematicamente como
fib(1) = 1
fib(2) = 1
fib(n) = fib(n1) + fib(n2)
Use seu programa para calcular o fib(5).
O que acontece quando voc calcula o fib(30)?
7/24/2019 Introduo a Prolog
16/52
Adicionando e removendo
clusulas dinamicamente
Um programa prolog pode ser visto como um banco de dados
Relaes
Explcitas: fatos
Implcitas: regras
Predicados built-inpermitem a atualizao do programa em
tempo de execuo
Adicionar uma nova clusula
assert, asserta, assertz
Remover uma clusula retract
No XSB mdulos com predicados dinmicos devem ser
carregados com o comando load_dyn/1
7/24/2019 Introduo a Prolog
17/52
Usando assert para tornar o
programa fib eficiente
fib(1, 1).
fib(2, 1).
fib(N, Fn) :-
N > 2,
M is N - 1,
fib(M, Fm),
O is N - 2,
fib(O, Fo),
Fn is Fm + Fo,asserta(fib(N, Fn)).
Agora os resultados parciais
so armazenados, no
precisando serem
recalculados.
Teste fib(40, X).
7/24/2019 Introduo a Prolog
18/52
Ferramentas de Debug
trace/0 : ativa o modo de rastreamento.
O sistema interage com o usurio cada vez que um predicado :
ativado inicialmente (call)
retorna com sucesso (exit)
vai fazer backtracking (redo)
falhou completamente (fail)
Podem ser observados predicados especficos com o comando
spy(predicado/aridade).
Diferentes aes escolhidas na interao com o debugador:
Creep (step), Leap (continuar at prximo spy), Skip (desabilita trace
at o final desta execuo), Abort (aborta a execuo atual).
notrace/0, nospy/1.
7/24/2019 Introduo a Prolog
19/52
Mais um Exemplo
Vamos definir a funo
Se X < 3 ento Y = 0
Se 3 X e X < 6 ento Y = 2
Se 6 X ento Y = 4
(arquivo funct.P)
f(X, 0) :- X < 3.
f(X, 2) :- 3 =< X, X < 6.
f(X, 4) :- 6 =< X.
3 6 X
Y
2
4
7/24/2019 Introduo a Prolog
20/52
Execuo do exemplo
Como prolog se comporta quandofazemos uma consulta?
Vamos acompanhar a execuode uma consulta ativando omecanismo de trace do xsb.
- trace. Agora faamos a consulta: f(1,
Y), 2 < Y.
f(X, 0) :- X < 3.
f(X, 2) :- 3 =< X, X < 6.
f(X, 4) :- 6 =< X.
(0) Call: f(1,_h454) ? c
(1) Call: 1 < 3 ? c
(1) Exit: 1 < 3 ? c
(0) Exit: f(1,0) ? c
(2) Call: 2 < 0 ? c
(2) Fail: 2 < 0 ? c
(0) Redo: f(1,0) ? c
(1) Redo: 1 < 3 ? c
(1) Fail: 1 < 3 ? c
(3) Call: 3 =< 1 ? c
(3) Fail: 3 =< 1 ? c
(4) Call: 6 =< 1 ? c
(4) Fail: 6 =< 1 ? c
(0) Fail: f(1,_h454) ? c
7/24/2019 Introduo a Prolog
21/52
f(X, 0) :- X < 3.
f(X, 2) :- 3 =< X, X < 6.
f(X, 4) :- 6 =< X.
Diagrama da execuo do
exemplo
f(1, Y)
2 < Y
1 < 3
2 < 0
3 1
1 < 62 < 2
6 1
2 < 4
2 < 0 no
no noCUT
Regra 1
Y = 0Regra 2
Y = 2
Regra 3
Y = 4
Regras mutuamente
exclusivas
7/24/2019 Introduo a Prolog
22/52
Evitar backtracking intil: ! (o cut)
op built-indepruning, logicamente sempre verificado
com efeito colateral de impedir backtracking: na sua esquerda na clusula que ocorre
em outras clusulas com a mesma concluso
ex:A :- B, C, D.
C :- M, N, !, P, Q.
C :- R.
impedebacktracking P -> N
permitebacktracking N -> M, Q -> P,
D -> (R xor Q), (P xor R) -> B R tentado:
unicamente se M ou N falha
nunca se P ou Q falha
7/24/2019 Introduo a Prolog
23/52
Cut: exemplo
Otimizando o exemplo anterior:
f(X, 0) :- X < 3, !.
f(X, 2) :- 3 =< X, X < 6, !.
f(X, 4) :- 6 =< X.
Nesse caso os cuts alteram apenas o comportamento
procedural do programa.
Se removermos os cuts o programa continuar produzindo os
mesmos resultados.
Green cuts
7/24/2019 Introduo a Prolog
24/52
Cut: exemplo (2)
Podemos otimizar ainda mais
o programa, pensando-o da
seguinte forma:
if (X < 3) then Y = 0
else if (X < 6) then Y = 2else Y = 4
Eliminamos assim 2
comparaes desnecessrias.
Verso anterior:
f(X, 0) :- X < 3, !.
f(X, 2) :- 3 =< X,
X < 6, !.
f(X, 4) :- 6 =< X. Reescrevemos para:
f(X, 0) :- X < 3, !.
f(X, 2) :- X < 6, !.
f(X, 4).
7/24/2019 Introduo a Prolog
25/52
Cut: exemplo(3)
O que acontece agora se os cuts forem removidos?
f(X, 0) :- X < 3.
f(X, 2) :- X < 6.
f(X, 4).
f(1, Y).
Y = 0;
Y = 2;
Y = 4;
Neste caso os cuts afetam a semntica do programa
Red cuts
7/24/2019 Introduo a Prolog
26/52
Hiptese do mundo fechado
Ao contrrio da Lgica de 1a ordem, Prolog nopermite nem
fatos, nem concluses de regras negativos:
~animal_lover(geber).
~kill(X,Y) :- animal_lover(X), animal(Y).
Princpio de economia:
declarar e deduzir apenas o que verdadeiro,
supor que tudo que no mencionado nem dedutvel falso
(hiptese do mundo fechado)
Operador de negao por falha Podemos usar o ! para implementar um operador de negao
por falha, tal que:
not p(X) verificado sse p(X) falha
7/24/2019 Introduo a Prolog
27/52
Negao por falha
Uma maneira de definir a negao por falha:not(P) :- P, !, fail
;
true.
fail o objetivo que sempre falha, enquanto que true sempretem sucesso.
not j pr-definido (built-in) no interpretador prolog, comoum operador pr-fixo.- not true.
no- not fail.
yes
7/24/2019 Introduo a Prolog
28/52
Voltando ao exemplo da famlia...
Definimos a relao sister(X, Y) como:
sister(X, Y) :- female(X), parent(Z, X), parent(Z, Y).
Vimos que isso tambm deduz que uma mulher irm dela
mesma: logicamente correto pela definio acima.
Podemos usar a negao por falha para alcanar o resultado
desejado.
sister(X, Y) :- female(X), parent(Z, X), parent(Z, Y), not(X = Y).
7/24/2019 Introduo a Prolog
29/52
Exemplo da famlia
- sister(X, pat).
X = ann;
no
Conforme o comportamento
esperado.
Experimento:
Modifique a relao sister(X,
Y) para
sister(X, Y) :- not(X = Y),
female(X), parent(Z, X),parent(Z, Y).
Agora consulte:
- sister(X, pat).
pam tom
bob
jim
ann pat
liz
7/24/2019 Introduo a Prolog
30/52
O que aconteceu?
Afinal de contas de acordo com a lgica:
a b c d e equivalente ad a b c e
Negao por falha no tem a mesma semntica da negao
da lgica.
Vamos acompanhar o trace da consulta:
- trace.
- sister(X, pat).
(0) Call: sister(_h446,pat) ? c
(1) Call: not _h446 = pat ? c
(1) Fail: not _h446 = pat ? c
(0) Fail: sister(_h446,pat) ? c
7/24/2019 Introduo a Prolog
31/52
O que aconteceu? (2)
Problema com objetivos no instanciados
Quantificao de variveis diferente na negao por falha
not(X = pat) no interpretado como existe X tal que
not(X = pat)
A quantificao na negao por falha universal
Para todo X: not(X = pat)?
O que claramente falso, pois X (no instanciado) unifica-se
perfeitamente com pat
Concluso: cuidado ao usar cuts e negao por falha.
7/24/2019 Introduo a Prolog
32/52
Prolog: listas
[e ]: incio e fim de lista
,separao entre elementos
|: separao entre 1 elemento (cabea) e resto da lista (calda)
acar sinttico para predicado .(Head,Tail)
ex.: [a,[b,c],d] acar sinttico para .(a,.(.(b,.(c,[])),.(d,[])))-[a,b,X,p(Y,C)] = [Head|Tail]
Head = a, Tail = [b,X,p(Y,C)]
- [[p(X),[a]],q([b,c])] = [[H|T1]|T2]
H = p(X), T1 = [[a]], T2 = [q([b,c])]
- member(X,[X|_]).- member(X,[Y|Z]) :- member(X,Z).
- member(b,[a,b,c])-> yes.
- member(X,[a,b,c])-> X = a ; X = b ; X = c ; no.
7/24/2019 Introduo a Prolog
33/52
Exemplo: Append
append(L1, L2, L3): L1 e L2 so duas listas e L3 a sua
concatenao.
Append de uma lista vazia com uma segunda lista a prpria
segunda lista:
append([], L, L).
Append de uma lista [X|L1] com a lista L2 uma lista [X|L3],
onde L3 a concatenao da cauda da primeira (L1) com L2.
append([X|L1], L2, [X|L3]) :-
append(L1, L2, L3).
7/24/2019 Introduo a Prolog
34/52
Exemplo: Append (2)
Exemplos do uso do append
Qual o resultado da concatenao das listas [a, b] e [c, d]?
- append([a,b], [c,d], X).
X = [a, b, c, d]
Que listas concatenadas resultam na lista [a, b, c, d]?
- append(X, Y, [a, b, c, d]).
X = []
Y = [a,b,c,d];
X = [a]
Y = [b,c,d];
7/24/2019 Introduo a Prolog
35/52
Exerccios 3
Usando o append, escreva uma regra para apagar os trs
ltimos elementos de uma lista L, produzindo uma lista L1
(arquivo append.P)
Defina a relao last(Item, List) de forma que Item o ltimo
elemento de List de duas formas diferentes:
usando append
sem usar append
7/24/2019 Introduo a Prolog
36/52
Prolog x prog. imperativa
Interativo:
compilao transparente integrada na interpretao
rodar programa = consultar um BD
Gerenciamento automtico da memria
Mecanismo nico de manipulao de dados -- unificaode
termos lgicos -- implementando:
atribuio de valor
passagem de parmetros
alocao de estruturas
leitura e escrita em campos de estruturas
7/24/2019 Introduo a Prolog
37/52
Prolog x prog. imperativa (2)
Estrutura de dados nica: termo Prolog
variveis lgicas sem tipo esttico (tipos dinmicos)
Controle implcito built-in na estratgia de resoluo, ex: Em
programao imperativa
procedure c(E)
const e0:tipoE0;
var E:tipoE, S0:tipoS0, l1:tipo-I1, S1:tipoS1;
do if E = e0 then do S0 := call p0(e0); return S0; end;
else do I1 := call p1(E); S1 := call p2(E,l1); return S1; end;
end;
Em Prolog
c(e0,S0) :- p0(e0,S0).
c(E,S1) :- p1(E,I1), p2(E,I1,S1).
7/24/2019 Introduo a Prolog
38/52
Prolog x prog. funcional
Matematicamente, predicado = relao:
no-determinismo:
respostas mltiplas (disponveis por backtracking),
unificao e busca built-in,
livra o programador da implementao do controle;
bi-direcionalidade:
cada argumento pode ser entrada ou sada, dependendo do
contexto de chamada,
nica definio para usos diferentes: verificador, instanciador,resolvedor de restries, enumerador.
integrao imediata com BD relacional
7/24/2019 Introduo a Prolog
39/52
Prolog x prog. funcional (2)
Append em Haskell:
append [] L = L
append H:T L = H : append T L
?- append([a,b],[c,d])
[a,b,c,d]
Append em Prolog:
append([],L,L).
append([H|T1],L,[H|T2]) :- append(T1,L,T2).
?- append([a,b],[c,d],R).R = [a,b,c,d].
Append relacional codifica vrias funes
7/24/2019 Introduo a Prolog
40/52
Vrios usos do mesmo predicado
verificador:
?- append([a,b],[c],[a,b,c]). -> yes.
?- append([a,b],[c],[a]). -> no.
instanciador:
?- append([a,b],[c],R). -> R = [a,b,c].
?- append(H,[c],[a,b,c]).-> H = [a,b].
resolvedor de restries:
?- append(X,Y,[a,b,c]). -> X = [], Y = [a,b,c]
; -> X = [a], Y = [b,c] ...
enumerador:
?- append(X,Y,Z). -> X = [], Y =[], Z = []
; -> X = [_], Y = [], Z = [_] ...
7/24/2019 Introduo a Prolog
41/52
Prolog x programao OO
Funcionalidades built-in:
+ unificao e busca
- tipos, herana e encapsulamento
Ontologicamente: Entidade Atmica (EA): em OO, valor de tipo built-in
em Prolog, tomo (argumento ou predicado)
Entidade Composta (EC): em OO, objeto
em Prolog, fato
Relao simples entre EC e EA: em OO, atributo de tipo built-in
em Prolog, posio em um predicado
Relao simples entre ECs: em OO, atributo de tipo objeto
em Prolog, predicado
Relao complexa entre entidades: em OO, mtodo
em Prolog, conjunto de regras
7/24/2019 Introduo a Prolog
42/52
Prolog x programao OO:
exemplo
Em OO:
pt[subclass_of planobj;
attrs[X inst_of int, Y inst_of int];
mets[right(Pt inst_of pt) {return self.X >= Pt.X}]]
pt1[inst_of pt; attrs[X = 0, Y = 0]]pt2[inst_of pt; attrs[X = 1, Y =1]]
?- pt1.right(pt2) -> no.
Em Prolog:
pt(0,0).
pt(1,1).
planobj(pt(_,_)).
right(pt(X1,_),pt(X2,_)) :- X1 >= X2.
?- right(pt(0,0),pt(1,1)). -> no.
7/24/2019 Introduo a Prolog
43/52
Programao em Lgica: Disciplina
Eletiva de Graduao e Ps
Prolog aprofundado
Programao por resoluo de restries a base lgica
(Constra int Log ic Programm ing)
extenso de Prolog com resolues de inequaes e equaes
restries quantitativas (N, Z, R, C)ou qualitativas (tipos, ontologias)
Escalonamento, raciocnio espacial, otimizao,
automao industrial, CAD/CAM, msica computacional
Programao em lgica funcional
Programao em lgica orientada a objetos
Programao multiparadigma a base lgica:
lgica + restries + funcional + OO
todo a IA e mais !
P L i Di i li
7/24/2019 Introduo a Prolog
44/52
Programao em Lgica: Disciplina
Eletiva de Graduao e Ps
Programao em lgica para engenharia de software
especificao formal prototipagem rpida
acelerao do modelo de desenvolvimento em espiral
Programao em lgica probabilista e bayesiana
raciocnio com incerteza
Programao em lgica indutiva
aprendizagem de mquina, agentes adaptativos,
minerao de dados, descoberta de conhecimento em BD,
programao automtica, bio-informtica
Programao em lgica multiagentes
sistemas inteligentes distribudos
comercio eletrnico
jogos, competio de futebol de robs
P L i Di i li
7/24/2019 Introduo a Prolog
45/52
Programao em Lgica: Disciplina
Eletiva de Graduao e Ps
Bancos de dados dedutivos:
descoberta de conhecimento em BD, sistemas especialistas de
grande porte, servidores de conhecimento ontolgico
Bancos de dados dedutivos orientada a objetos
Bancos de dados dedutivos temporais Bancos de dados de restries:
GIS, BD espaciais, BD espao-temporais,
integrao de dados e interoperabilidade
Bancos de dados de restries orientada a objetos toda a IA de grande escala e mais !
Bancos de dados probabilistas:
BD de sensores, data warehousing, integrao de dados com fontes
no confiveis ou mutuamente inconsistentes,
Programao em Lgica: Disciplina
7/24/2019 Introduo a Prolog
46/52
Programao em Lgica: Disciplina
Eletiva de Graduao e Ps
Gramticas lgicas:
Parser e gerador de linguagem built-in em Prolog
Basta desenvolver gramtica (i.e.,como com lex e yacc)
Minerao da web, extrao de informao na Internet, compilao
traduo automtica, gerao automtica de resumos, chatterbots
APIs Prolog/Javae Prolog/XML
sistemas de informao inteligentes distribudos e heterogneosa infra-
estrutura web
integrao de dados, interoperabilidade entre sistemas, mediadores, data
warehousing
comercio eletrnico
agentes inteligentes de recuperao, classificao, extrao e notificao
de informao na web, na Internet, em Intranet
inteligncia na computao pervasiva
toda a IA embutida e mais !
Programao em Lgica:
7/24/2019 Introduo a Prolog
47/52
Programao em Lgica:
Disciplina Eletiva de Graduao e
Ps-Graduao Aplicao fio condutor para ilustrao dos conceitos
By the year 2050, develop a team of ful ly auton omous hum anoidrobots that can win against the human world soccer champion team.http://www.robocup.org
Programao em Lgica: Disciplina
7/24/2019 Introduo a Prolog
48/52
Programao em Lgica: Disciplina
Eletiva de Graduao e Ps
7/24/2019 Introduo a Prolog
49/52
Introduo a Prolog
FIM
7/24/2019 Introduo a Prolog
50/52
Exerccio 1 - Respostas
mother(X, Y) :- parent(X, Y), female(X).
sister(X, Y) :- female(X), parent(Z, X), parent(Z, Y).
grandparent(X, Y) :- parent(X, Z), parent(Z, Y).
aunt(X, Y) :- sister(X, Z), parent(Z, Y).
Quais so as respostas devolvidas para sister(X, pat). ?
Por que isso ocorre?
Como isso pode ser evitado?
Cenas dos prximos slides...
7/24/2019 Introduo a Prolog
51/52
Exerccio 2 - Resposta
fib(1, 1).
fib(2, 1).
fib(N, Fn) :-
N > 2,
M is N - 1,
fib(M, Fm),
O is N - 2,
fib(O, Fo),
Fn is Fm + Fo.
O programa tem
comportamento exponencial,
para cada passo calculamos
toda a seqncia de fibonacci.
Os mesmos valores socalculados vrias vezes...
Veja implementaes mais
eficientes neste link.
http://cubbi.com/fibonacci/prolog.htmlhttp://cubbi.com/fibonacci/prolog.html7/24/2019 Introduo a Prolog
52/52
Exerccios 3 - Resposta
del3(L, L1) :- append(L1, [_, _, _], L).
last(Item, List) :- append(_, [Item], List).
last2(Item, [Item]).
last2(Item, [_|XL]) :- last2(Item, XL).