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.