View
183
Download
2
Category
Preview:
Citation preview
Mecanismos avançados para manipulação de tabelas em sistemas Prolog com suporte para tabulação
Flávio Manuel Fernandes CruzOrientador: Ricardo RochaInstituição: CRACS / FCUP
Prolog
SLD (Selective Linear Definite) é a estratégia de avaliação tradicional do Prolog
Apesar de ser muito usada tem algumas lacunas...
path(X, Y) :- path(X, Z), edge(Z, Y).path(X, Y) :- edge(X, Y).
edge(1, 2). edge(2, 3).
Tabulação
A tabulação é uma forma diferente de avaliar Prolog
Resolve as incapacidades da SLD quanto aos ciclos infinitos e computações redundantes
Consiste em guardar numa tabela as soluções intermédias de determinados objectivos para que possam ser reutilizadas quando surgirem chamadas repetidas
Tabulação
1. path(1, Z)
2. path(1, Z), edge(Z, Y) 3. edge(1, Y)
4. Y = 2 5. fail6. edge(2, Y)
7. Y = 3
9. edge(3, Y)
10. fail8. fail
Z = 2 Z = 3
11. complete
path(1, VAR0):
4. VAR0 = 2
7. VAR0 = 3
Call-Subsumption
A extensão do YAP para Tabulação (YapTab) só suporta chamadas variantes (Call-Variance)
O objectivo do trabalho é alterar o YapTab para também suportar Call-Subsumption
Call-Subsumption
Call-Variance só reaproveita soluções de um golo se este for variante de um já colocado na tabela. Exemplo: p(X, 1, Y) é variante de P(X, 1, Z)
No entanto podemos fazer ainda melhor, reaproveitando as soluções de golos mais gerais caso existam
Dizemos assim que um golo T1 subsume um golo T2 quando T1 é mais geral que T2: path(X, Y) subsume p(1, X)
Com este mecanismo podemos reutilizar resultados computados e diminuir a redundância nas tabelas do engine, poupando espaço e tempo
Perspectivas de solução
O mecanismo de tabulação do XSB Prolog já implementa Call-Subsumption
Existem dois artigos que descrevem soluções implementadas para o XSB
A ideia principal será usar as TST (time stamped tries) como base e tentar melhorar a partir daí
Plano de Trabalhos
Estudo dos modelos de execução de tabulação em sistemas Prolog com particular ênfase na implementação do sistema YapTab (feito)
Estudo dos algoritmos e estruturas de dados utilizados para suporte de Call-Subsumption e Common Global Trie (feito)
Plano de Trabalhos
Tentar reutilizar algoritmos e estruturas de dados do XSB Prolog e integrá-los na máquina do Yap (2,5 meses)
Melhorar os algoritmos e estruturas de dados do XSB. O objectivo será que ambos, XSB e YAP, façam proveito das novas melhorias (2 meses)
Plano de Trabalhos
Testes e validação (1 mes)
Escrita de 1 ou 2 artigos sobre o trabalho efectuado
Dissertação! (1 mes)
:- Fim.
Obrigado pela vossa atenção!Prasad Rao, C. R. Ramakrishnan, I. V. Ramakrishna. A Thread in Time Saves Tabling Time. 1996.
Ernie Johnson, C. R. Ramakrishnan, I.V. Ramakrishnan, Prasad Rao. A Space Efficient Engine for Subsumption-Based Tabled Evaluation of Logic Programs. 1999.
Ricardo Rocha, Fernando Silva, Vítor Santos Costa. The YapTab Tabling System. 2003.
http://github.com/flavioc/yap
http://flaviocruz.net
Call-Subsumption
path(X, Y) :- edge(X, Y).path(X, Y) :- edge(X,Z), path(Z, Y).
edge(1, 2). edge(2, 3). edge(3, 4).
1. path(X, Y)
2. edge(X, Y)
3. X = 1
Y = 2
4. X = 2
Y = 3
5. X = 3
Y = 46. fail
7. edge(X, Z), path(Z, Y)
8. path(2, Y) 11. path(3, Y) 14. path(4, Y)
9. Y = 3 12. Y = 4
15. fail
16. Y = 4
11. complete
path(VAR0, VAR1):
3. VAR0 = 1, VAR1 = 2
4. VAR0 = 2, VAR1 = 3
5. VAR0 = 3, VAR1 = 4
10. VAR0 = 1, VAR1 = 3
13. VAR0 = 2, VAR1 = 4
17. VAR0 = 1, VAR1 = 4
path(2, VAR0):
9. VAR0 = 3
16. VAR0 = 4
path(3, VAR0):
12. VAR0 = 4
Recommended