Trabalho I: 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 poderá ser uma estratégia de tabulação com espera ou de tabulação linear (consulte a secção Trabalho Relacionado para obter mais detalhes sobre diferentes formas de implementar tabulação). A correcção do desenho do algoritmo de suporte à execução com tabulação 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)).

Alguns exemplos da utilização deste módulo podem ser obtidos aqui.

Programas de Teste

Trabalho Relacionado

O Que Entregar?

Um ficheiro .tar que inclua:

Os ficheiros Prolog com a implementação das primitivas externas (pode ser só um).
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 via web até às 12 horas do dia 31 de Março de 2008, sendo a sua apresentação feita posteriormente em horário a definir.