LIFE: integração de predicados,
funções e classes
Jacques Robin
Reginaldo Valadares
DI-UFPE
A molécula lpy
Classes e herança de tipo
FOOL
Log In
LIFE
Funções e
avaliação lazy
Le Fun
Relações e
resolução lógica
LOGIN: características

Prolog com:
• representação de informação parcial e hierarquia de tipos
• termos de 1a ordem substituídos por termos 

Exemplo: append em Login x em Prolog
• Prolog:
append([ ],L,L) :- listp(L).
append([H|T], L, [H|R]) :- listp(T), listp(L), listp (R),
append(T,L,R).
listp([]).
listp(H|T] :- listp(T).
• Login:
list:= {[ ]; [ _|list]}.
append([ ],L:list,L).
append([H|T:list], L:list, [H|R:list]) :- append(T,L,R).
LOGIN: exemplo
coisaboa
nota
notaboa
notaruim
a
b
c
d
notaboa <| coisaboa.
notaboa := {a;b}.
notaruim := {c;d;e}.
gosta(X:person,X).
f
gosta(peter,mary).
gosta(pessoa,coisaboa).
tem(peter,c).
tem(paul,f).
pessoa
tem(mary,a).
feliz(X:pessoa) :- gosta(X,Y),tem(X,Y).
estudante
peter
paul
feliz(X:pessoa) :- gosta(X,Y),tem(Y,coisaboa).
mary
?- feliz(X).
X=mary; X=mary; X=peter; no
?-
LEFUN: integração
relacional (lógica) funcional


Linguagem de programação funcional e relacional
Extensão da parte funcional:
• variáveis lógicas e predicados como argumentos de funções
• integra unificação e busca built-in no paradigma funcional

Extensão da parte lógica (relacional):
• expressões aplicativas como argumentos de predicados
• integra computação determinística no paradigma lógico
• adequação aquisicional para conhecimento inerentemente
procedimental
• igualdade semântica
LEFUN: unificação

Unificação de termo lógico p com expressão funcional f:
• dispara avaliação de f no contexto local de instanciação das
variáveis lógica
• como is de Prolog mas bi-direcional e generalizado a expressões
simbólicas

Dificuldade:
• o que fazer quando f contém variáveis ainda não instanciadas?

Solução:
• suspender a unificação necessitando a avaliação de f
• até depois das unificações instanciados as variáveis lógicas de f

Unificação:
• cria equação funcional residual
• passada pela esquerda da premissa que disparou a unificação de p
com f
LEFUN: exemplo de Unificação
q(X,Y,Z) :- p(X,Y,Z,Z), pick (X, Y).


p(X,Y,X+Y,X*Y).
p(X,Y,X+Y,(X*Y) - 14).

1o sub-objetivo p(A,B,C,C).
Tente 1a cláusula p(X,Y,X+Y,X*Y);
Envolve unificar A + B = A * B.
•
Aqui Prolog falharia,


pick(3,5).
pick(2,2).
pick(4,6).


?- q(A,B,C).
?- O que acontece se forcar
backtracking?



unificação puramente sintática
apesar do próximo passo pick(A,B)
poder prover instâncias para essas
variáveis que verificam a equação
Equação A+B = A * B acresentada
como nova premissa de q(A,B,C)
1o sub-objetivo pick(A,B)
1a instanciação de pick(A,B) não
verifica a equação residual:
3+5 != 3*5 dispara backtracking
2a instanciação A = B = 2 verifica
equação residual
LeFun devolve: A = B = 2, C = 4.
LEFUN: expressões de ordem superior
sq(X) -> X * X.
twice(F,X) -> F(F(X)).
valid_op(twice).
p(1).
pick(lambda(X,X)).
q(V) :- G = F(X),
V = G(1),
valid_op(F),
pick(X),
p(sq(V)).

O primeiro goal literal G = F(X)
cria uma S-residuation com o
conjunto de RV {F,X}
• A variável de ordem superior F
não apresenta problema pois
não há tentativa de resolvê-la



?- q(Ans).

O próximo passo gera uma nova
S-residuation ao obter Ans =
F(X)(1).
F é instanciada para a função
twice, mudando a S-residuation
para Ans = twice(X)(1).
pick(X) transforma X na função
identidade, liberando a Sresiduation e instancializando
Ans para 1
sq(1) = 1 é verificado, sucesso.
FOOL: caraterísticas


Linguagem funcional orientada a padrão;
Termos construtores de primeira ordem substituídos por
termos psi
• FOOL é para Haskell assim como LOGIN é para Prolog
• FOOL mais expressão devido a inversão de funções, estruturas
de dados parciais e variáveis lógicas

psi term subsumption ordering x first-order matching
ordering em termos construtores
• aridade fixa
• herança

Ordem parcial definida pelo usuário permite que sejam
escritas funções altamente genéricas (encapsulamento)
FOOL: Exemplos
list := {[ ]; [ _| list]}.
append([ ],L: list) -> L.
append([H|T: list],L: list) -> [ H|append
(T,L)].
map ([ ], _ ) -> [ ].
map ([ H|T], F) -> [ F(H)|map(T,F)].
? X = map ([1,2,3],+1)
X = [2,3,4]
age(person(birthDate => date(year => Y)),
ThisYear:int)
-> ThisYear - Y.
válida para qualquer sub-tipo de pessoa:
student, employee, work-study, staff,
prof, s1, s2, w1, w2, e1, e2, f1, f2, f3 s1
person
employee
student
staff
faculty
workstudy
s2 w1 w2 e1 e2 f1 f2 f3
LIFE = LOGIN + LEFUN + FOOL

A terrível novela: requisitos
1. A soap opera is a TV show whose characters
include a husband, a wife and a mailman such
that:
2. the wife and the mailman blackmail each other
3. everybody is either alcoholic, drug addict or
gay
4. Dick is gay, Jane is alcoholic and Harry is a
drug addict
5. the wife is always an alcoholic and the longlost sister of her husband
6. the husband is always called Dick and the
lover of the mailman
7. the long-lost sister of any gay is called either
Jane or Cleopatra
8. Harry is the lover of every gay
9. Jane blackmails every drug addicted lover of
Dick
10. soap operas are invariably terrible!
0. Which is a terrible TV show and what are its
characters?

A terrível novela em LIFE
cast := {[];[person|cast]}.
soapOpera :=
tvShow(chars => [H,W,M],
%1
husband => H:dick,
%1 & 6a.
wife => W:alcoholic,
%1 & %5a
mailman => M)
%1
| blackmail(W,M),
%2
lovers(M.H),
% 6b
longLostSister(W,H). % 5b
person := {alcoholic; drugAddict; gay}. % 3
dick <| gay.
%4a
jane <| alcoholic.
%4b
harry <| drugAddict. %4c
longLostSister(gay) -> {jane;cleopatra}. %7
lovers(harry,gay).
%8
blackmail(jane,X:drugAddict) :- lovers(X, dick).
terrible(soapOpera).
?- terrible(T:tvShow(chars => cast)).
LIFE x Prolog

LIFE supera os maiores problemas de Prolog:
•
•
•
•
•
•
•
•
•
Funções, incluindo aritmética correta (IS inútil)
Orientação a objetos (fraca)
Tipos e herança múltipla
Manipulação correta de estruturas cíclicas
Variáveis globais
Atribuição destrutiva limpa (assert e retract inútil)
Estruturas de dados persistentes
Registros nos moldes de C
Estruturas de dados expandidas: arrays e hash
LIFE x Prolog

Programas em Prolog facilmente estendidos para LIFE
• Termos LIFE não têm aridade, mas indefinido número de
argumentos



aridade não pode ser usada para distinguir predicados, como é feito
em Prolog
programador deve usar nomes diferentes para predicados diferentes
unificação pode ser alcançada mesmo entre psi-termos com raízes
diferentes (glb não vazio)
• Exemplo: pred (A, B, C) :- write(A), write(B), write(C).
Prolog
?- pred (1,2,3).
123
 ?- pred (A, B, C).
_26_60_94
 ?- pred (A, B, C, D).
WARNING: ‘pred/4’ undefined
?- pred (A, B).
WARNING: ‘pred/2’ undefined
x
LIFE: exemplo
> ?- pred (1,2,3)?
123
 > ?- pred (A, B, C)?
A=@, B=@, C=@--1>
>
--1> .
> ?- pred (A, B, C, D)?
A=@, B=@, C=@, D=@
 --1> .
> ?- pred (A, B)?
A=@, B=@.
 --1> .
> ?- pred?
***Yes
.
LIFE x orientação a objetos


LIFE não distingue entre classe e objetos
LIFE não permite fechar os atributos autorizados para
uma classe nas declarações hierárquicas
• unificação assume informação sempre parcial


em Java a definição class pessoa (string nome; string end; int id)
limita em três os atributos de pessoa
uma declaração do tipo pessoa (Silva, 345) é verificada em LIFE
• em LIFE possível apenas através de meta-programação e
restrições com predicados ou funções |
Predicados em LIFE




Predicados são definidos e executados em LIFE da
mesma forma que em Prolog
Termos  substituem termos de Herbrand.
Programas em Prolog podem rodar inalterados em LIFE
se cada predicado usado com apenas uma aridade.
Toda regras LIFE da forma:
• c(..., ci, ...) :- p (..., pj, ...)... , q(..., qk, ...).
• onde c, p e q não são sorts mais predicados.
• predicado não tem especialização nem generalização.

LIFE não permite:
• s(..., ci, ...) :- u(..., pj, ...)... , v(..., qk, ...).
• onde s, u e v são sorts da hierarquia de tipos
Definindo Predicados em LIFE
exemplo


Definição de Predicados consiste em uma ou várias
cláusulas definitas.
Cláusulas são guardadas na assertion base na mesma
ordem de entrada

Uma cláusula de definição tem a forma: Head :- Body

Head é um atomic goal e Body uma seqüência não vazia de
atomic goals


Atomic goal é um psi-termo onde a raiz é definida como
um predicado no programa
A cláusula Head :- succeed é chamada de fato.
Funções em LIFE
exemplo





Função é uma rotina que é chamada por matching e que
retonra um valor
Computações funcionais são determinadas: chamadas de
funções só são disparadas uma vez e nunca mais pode ser
voltada por backtracking
Função pode ser chamada antes que os valores dos seus
argumentos sejam conhecidos (a função é suspensa)
A suspensão é chamada de resididuation or residual
equation
A função executa assim que seus argumentos são
conhecidos
Funções em LIFE (2)





A função também pode ser chamada com argumentos a
menos (currying)
Rotina independente de ordem é aquela cujo resultado
depende apenas dos argumentos e não da ordem na qual
são ligados, relativo a quando a rotina é chamada
Programadores não precisam se preocupar em saber quais
são as dependências de dados
Generate-and-test substituído pelo test-and-generate
Uma função residual age como um daemon: verifica
continuamente se seus argumentos estão
sufucuentemente instanciados
Definindo Funções em LIFE





A definição de uma função consiste de uma ou mais
regras funcionais
A ordem em que guardadas na assertion base é a mesma
usada durante a execução
Uma regra funcional tem a forma: Head -> Expr. (Head
evaluates to Expr)
Head é um psi-termo cuja nome da root-sort é o mesmo
da função sendo definido
Expr é um psi-termo.
Download

life2