Trabalho Prático: Tabulação em Linguagens Lógicas
Objectivo
Permitir que os alunos adquiram uma maior sensibilidade e conhecimento
prático do funcionamento da técnica de tabulação aplicada à linguagem
de programação lógica Prolog.
Descrição
A tabulação é uma das mais bem sucedidas técnicas de implementação que
resolve a incapacidade dos sistemas tradicionais de Prolog em lidarem
com computações redundantes e ciclos infinitos. A ideia básica da
tabulação é guardar as soluções das computações intermédias de modo a
que estas possam ser re-utilizadas quando aparecem chamadas repetidas a
subgolos tabelados. As estratégias de tabulação dividem-se em duas
categorias principais: a tabulação com espera e a
tabulação linear. Para assegurar que todas as soluções são
correctamente encontradas, a tabulação com espera utiliza um mecanismo
de suspensão no qual preserva o estado das sub-computações
correspondentes a subgolos tabelados. A tabulação linear usa a simples
execução em árvore onde os subgolos tabelados são re-executados
sucessivamente até a computação atingir o seu ponto-fixo.
A forma mais eficiente de implementar tabulação num sistema Prolog é
estender a máquina abstracta de execução. Uma forma mais simples mas
menos eficiente de implementar tabulação é conseguida por re-escrita
dos programas originais onde se incluem primitivas externas de suporte
à execução com tabulação. Essas primitivas podem depois ser
implementadas em Prolog e/ou utilizando o interface a outras
linguagens disponível nos sistemas Prolog.
Neste trabalho pretende-se que utilize a aproximação baseada na
re-escrita de programas com primitivas externas para implementar o
suporte à execução com tabulação no sistema Yap Prolog.
Implementação
A aproximação baseada na re-escrita de programas com primitivas
externas para implementar tabulação pode dividir-se em duas
componentes: a componente que implementa a re-escrita dos programas
originais e a componente que implementa o suporte às primitivas
externas incluidas pela componente de re-escrita. Na realização deste
trabalho implemente apenas a componente de suporte às primitivas
externas e considere que os programas já se encontram re-escritos tal
como pretendido. A estratégia a implementar será a estratégia de
tabulação linear. A correcção do desenho do algoritmo de suporte à
execução com tabulação linear será mais valorizada do que a sua
eficiência em termos do eventual número de re-computações necessárias
para atingir o ponto-fixo.
A representação da tabela deverá ser conseguida por utilização de uma
estrutura de dados baseada em tries. Para isso utilize o módulo
tries do sistema Yap Prolog através da directiva:
:- use_module(library(tries)).
Exemplos da utilização do módulo das tries e exemplos de programs de
teste podem ser obtidos aqui.
O Que Entregar?
Um ficheiro .tar que inclua:
- Os ficheiros Prolog (pode ser só um) com a implementação das
primitivas externas.
- Os ficheiros Prolog com o código dos programas de teste
re-escritos segundo o algoritmo utilizado (um por programa).
- Um ficheiro .pdf com um pequeno relatório do trabalho (estrutura
livre) onde se descreve de forma sucinta e clara:
- A ideia do algoritmo de re-escrita e sua aplicação aos
programas de teste.
- A ideia do algoritmo de suporte à execução com tabulação
(incluir a descrição das primitivas utilizadas e seu
encadeamento, principais estruturas de dados, funções
auxiliares relevantes, ...).
- As dificuldades encontradas na implementação (se alguma).
- Os tempos de execução e o número de golos tabelados e soluções
encontradas para os programas de teste.
O código deve compilar e executar nas máquinas dos laboratórios das
aulas práticas. Uma boa estruturação e legibilidade do código será
valorizada.
Prazos
O trabalho deve ser entregue por email até às 12 horas do dia 24 de
Maio de 2013, sendo a sua apresentação feita posteriormente em horário
a definir.