An Implementation of the Extended Andorra Model
Ricardo Lopes
Departamento de Ciência de Computadores & LIACC
Faculdade de Ciências, Universidade do Porto
Rua do Campo Alegre, 823 4150 Porto, Portugal
Dezembro de 2001
Resumo
O Prolog é uma linguagem de programação lógica de alto-nível que tem
sido muito investigada tendo em vista conseguir-se obter um elevado
desempenho na execução das aplicações. O progresso em \emph{coroutining},
programação por restrições e tabelação permitiram reduções
substanciais no espaço de procura da função de procura do Prolog,
e são a base para a construção de aplicações mais ambiciosas. O uso
de paralelismo, por outro lado, permite que as aplicações lógicas
explorem de forma transparente as vantagens das arquitecturas
paralelas, de forma a melhorar ainda mais esse desempenho.
Obter o máximo desempenho nas aplicações foi desde sempre um dos
maiores objectivos da investigação na programação lógica. Este
objectivo só poderá ser conseguido através de novos modelos de
computação que sejam capazes de executar eficientemente os programas
lógicos através da redução do espaço de procura e através da extracção
do paralelismo existente nesses mesmos programas. Estes objectivos
motivaram o desenvolvimento do Extended Andorra Model
(EAM), um novo modelo que permite que os predicados sem restrições não
determinísticas possam ser executados primeiro.
Neste trabalho apresentamos um sistema criado com base na EAM original
de David H. D. Warren com controle implícito que designamos por Basic
design for Extended Andorra Model (ou BEAM). Apresenta-se uma
descrição completa do modelo, das regras de execução e do controle de
execução.
São referidos os principais algoritmos de execução do sistema bem como
todas as estruturas de dados associadas que permitem uma execução
eficiente das aplicações. São também discutidas algumas extensões ao
modelo EAM que permitem um melhor controle da execução e que servem
para evitar computações infinitas. Incluímos igualmente um estudo
detalhado sobre o desempenho e comportamento da gestão de memória do
sistema. Por fim, apresenta-se um novo modelo de execução paralelo
que poderá ser implementado sobre a BEAM.
