IMPLEMENTAÇÃO DE UM SISTEMA DE
PROGRAMAÇÃO EM LÓGICA
CONTEXTUAL
Artur Miguel Dias
UNL-DI 26/90
Setembro de 1990
Esta tese foi submetida ao Departamento de Engenharia Electrotécnica e de
Computadores do INSTITUTO SUPERIOR TÉCNICO para satisfação parcial dos
requisitos
do
programa
de
mestrado
em
Engenharia
Computadores.
Departamento de Informática
Universidade Nova de Lisboa
2825 Monte da Caparica
Portugal
Electrotécnica
e
de
IMPLEMENTAÇÃO DE UM SISTEMA DE
PROGRAMAÇÃO EM LÓGICA
CONTEXTUAL
Artur Miguel de Andrade Vieira Dias
licenciado em Engenharia Informática
pela
FACULDADE DE CIÊNCIAS E TECNOLOGIA
UNIVERSIDADE NOVA DE LISBOA
Tese submetida para satisfação parcial dos requisitos do
programa de mestrado
em
Engenharia Electrotécnica e de Computadores
(Computadores)
INSTITUTO SUPERIOR TÉCNICO
Departamento de Engenharia Electrotécnica e de Computadores
LISBOA
Setembro de 1990
Tese realizada sob a supervisão de
Professor Doutor Luís Fernando Lopes Monteiro
Professor Associado do Departamento de Informática
FACULDADE DE CIÊNCIAS E TECNOLOGIA
UNIVERSIDADE NOVA DE LISBOA
e de
Professor Doutor Pedro Manuel Barbosa Veiga
Professor Associado do Departamento Engenharia Electrotécnica e de Computadores
INSTITUTO SUPERIOR TÉCNICO
UNIVERSIDADE TÉCNICA DE LISBOA
2
Resumo
Programação em lógica contextual, ou CxLP, é um novo esquema de programação
que enriquece o paradigma da programação em lógica com mecanismos de
estruturação dos programas em units e de controlo do processo de derivação com base
no agrupamento de units em entidades dinâmicas chamadas contextos. Neste
trabalho descrevemos a implementação de um sistema de programação em lógica
contextual, compatível com o Prolog, portável, e muito eficiente e flexível. No seu
coração encontra-se uma máquina abstracta altamente optimizada, chamada CxM,
desenvolvida a partir da WAM de D.Warren, cuja velocidade atinge os 60 Klips numa
VAXstation 3540 com o programa de teste naïve-reverse. Algum conforto
e
flexibilidade de utilização foram conseguidos como resultado do desenvolvimento de
um compilador incremental rápido e da utilização de mecanismos de ligação
incrementais e reversíveis. Do ponto de vista funcional, o sistema tem todas as
propriedades de um interpretador.
Palavras chave:
Programação em lógica, programação em lógica contextual,
compilação incremental, ligação, implementação, contexto.
Abstract
Contextual logic programming (CxLP), is a new programming scheme that extends
the logic programming paradigm with mechanisms to structure programs into units
and to control the derivation process by grouping units in dynamic entities named
contexts.
In
this
work
a
Prolog
compatible,
portable,
fast
and
flexible
implementation of a contextual logic programming system is described. In its heart
there is an highly optimized abstract machine, named CxM, developed as an
extension of D. Warren’s WAM, that attains 60 Klips on a VAXstation 3540 using the
standard naïve-reverse benchmark. Some convenience and flexibility was achieved
as the result of the development of a fast incremental compiler and the use of
incremental and reversible binding mechanisms. Functionally, our system enjoys all
the properties of an interactive interpreter .
Keywords:
Logic programming, contextual logic programming, incremental
compilation, binding, implementation, context.
3
Índice
Sumário .....................................................................................................................
2
Índice .........................................................................................................................
3
1. Introdução ............................................................................................................
7
1.1. Apresentação .............................................................................................
7
1.2. Organização ...............................................................................................
8
1.3. Agradecimentos .........................................................................................
9
1.4. Orientação.................................................................................................. 10
2. Programação em Lógica .......................................................................................
2.1. Origens e características da programação em lógica ................................
2.2. Um pouco da história das implementações de Prolog ..............................
2.3. A WAM .......................................................................................................
2.3.1. Representação dos termos ..............................................................
2.3.2. Áreas de dados .................................................................................
2.3.3. Estruturas de dados de controlo .....................................................
2.3.4. Registos da WAM .............................................................................
2.3.5. Classificação das variáveis ............................................................
2.3.6. Optimização da última chamada (LCO) e trimming .......................
2.3.7. Indexação ........................................................................................
2.3.8. Instruções ........................................................................................
11
11
13
15
16
16
17
17
18
18
19
19
3. Programação em Lógica Contextual ....................................................................
3.1. Introdução .................................................................................................
3.2. Sintaxe .......................................................................................................
3.3. Units ..........................................................................................................
3.4. Designador de Unit ....................................................................................
3.5. Contexto .....................................................................................................
22
22
23
23
24
24
Índice
3.6.
3.7.
3.8.
3.9.
4
Nomes dependentes do contexto ................................................................
Contexto histórico .....................................................................................
Regras de inferência ..................................................................................
Exemplos ...................................................................................................
25
25
25
28
- Máquina abstracta para CxLP ..................................................................
Introdução .................................................................................................
Representação dos termos .........................................................................
Organização da memória ..........................................................................
4.3.1. Área de código .................................................................................
4.3.2. Stacks (heap + stack local) ..............................................................
4.3.3. Trail ................................................................................................
Ligações em CxLP .......................................................................................
4.4.1. Ligação dos nomes definidos localmente .......................................
4.4.2. Ligação dos nomes dependentes do contexto ..................................
4.4.2.1. Cache .................................................................................
4.4.2.2. Estrutura da cache ............................................................
4.4.3. Ligação dos nomes em fórmulas de extensão .................................
4.4.4. Ligação dos nomes importados ......................................................
Parâmetros das units ................................................................................
Implementação dos contextos ...................................................................
4.6.1. Representação dos contextos ..........................................................
4.6.2. Registos para suporte dos contextos ...............................................
4.6.3. Instruções para controlo dos contextos .........................................
4.6.4. Fórmulas de libertação de contexto e a unit [] ................................
Implementação do contexto histórico ......................................................
4.7.1. Representação do contexto histórico e registos associados ...........
4.7.2. Instruções para controlo do contexto histórico .............................
As outras estruturas de dados do stack local ............................................
4.8.1. Registos de activação ......................................................................
4.8.2. Pontos de escolha ............................................................................
A C-WAM ....................................................................................................
30
30
31
32
32
32
33
33
33
34
34
35
35
37
37
38
38
39
41
42
43
43
44
45
45
46
46
5. Mecanismos de ligação incremental da CxM ......................................................
5.1. Introdução .................................................................................................
5.2. O sistema de suporte de CxLP .....................................................................
5.3. Manutenção das ligações na CxM .............................................................
5.3.1. Descritores de nome de predicado ..................................................
5.3.2. Estabelecimento das ligações .........................................................
5.3.2.1. MakeIndex ........................................................................
5.3.2.2. MakeImportBinding ........................................................
5.3.2.3. MakeCtxExtBinding .........................................................
5.3.2.4. MakeCtxDepBinding ........................................................
5.3.3. Invalidação das ligações .................................................................
5.3.3.1. Efeitos da alteração do conjunto de cláusulas de uma unit ......
5.3.3.2. Efeitos da alteração de importação ..................................
5.3.3.3. Efeitos da mudança de visibilidade .................................
5.3.3.4. Efeitos da eliminação de um nome de predicado .............
5.3.4. As ligações dos nomes dependentes do contexto revisitadas .........
5.3.4.1. Adição de cláusulas ..........................................................
47
47
48
50
50
51
52
52
52
52
53
54
55
55
56
56
56
4. CxM
4.1.
4.2.
4.3.
4.4.
4.5.
4.6.
4.7.
4.8.
4.9.
Índice
5
5.3.4.2. Mudança do estado de visibilidade de um nome ..............
5.3.4.3. Eficiência ..........................................................................
57
58
6. Técnicas de implementação da CxM ...................................................................
6.1. Introdução .................................................................................................
6.2. Lips! ............................................................................................................
6.3. Técnica de interpretação ...........................................................................
6.3.1. Código threaded ..............................................................................
6.3.2. Método clássico ...............................................................................
6.3.3. Comparação ....................................................................................
6.3.4. Eliminação do ciclo de interpretação ............................................
6.3.5. Código expandido ............................................................................
6.4. Tags ............................................................................................................
6.5. Rotina de unificação ..................................................................................
6.6. Especialização das instruções ...................................................................
6.7. Utilização de registos da máquina hospedeira .........................................
6.8. Indexação ...................................................................................................
6.9. Penalizações provocadas pelos novos mecanismos .................................
59
59
59
60
60
61
61
62
62
63
66
67
68
69
69
7. Compilação ..........................................................................................................
7.1. Introdução .................................................................................................
7.2. Características gerais do compilador .......................................................
7.3. Funcionamento geral e código gerado .......................................................
7.4. A tabela de variáveis .................................................................................
7.5. Algoritmo de atribuição de registos ..........................................................
7.6. Golos que mudam de contexto ...................................................................
7.6.1. Passagem de parâmetros para units ...............................................
7.6.2. Tratamento de referências a parâmetros de units .........................
7.7. Indexação ...................................................................................................
7.7.1. Índice ...............................................................................................
7.7.2. Índice rápido ...................................................................................
7.7.3. Índice compacto ..............................................................................
7.7.4. Índice super-rápido .........................................................................
7.7.5. Na WAM ...........................................................................................
7.8. Compilador optimizador ..........................................................................
7.9. Outras linguagens ......................................................................................
71
71
72
72
75
76
79
79
80
81
81
82
83
84
85
85
86
8. Outras Componentes do Sistema .........................................................................
8.1. Predicados de sistema ...............................................................................
8.1.1. Predicados deterministas escritos em C ........................................
8.1.2. Predicados de sistema não deterministas escritos em C ...............
8.1.3. Predicados de sistema escritos em CxLP ........................................
8.2. Analisador sintáctico ...............................................................................
8.3. Tratamento de erros ..................................................................................
8.4. Colector de lixo do heap .............................................................................
8.5. Colector de lixo da área de código ..............................................................
8.6. Monitor de Comandos ...............................................................................
87
87
88
88
90
90
91
91
93
93
9. Conclusão .............................................................................................................
94
Índice
6
Apêndices ...................................................................................................................
96
A. Predicados de sistema ..........................................................................................
A.1. Introdução .................................................................................................
A.2. Sucesso e falhanço .....................................................................................
A.3. Controlo .....................................................................................................
A.4. Manipulação de golos ................................................................................
A.5. Gestão das units e do seu conteúdo ............................................................
A.6. Contextos ...................................................................................................
A.7. Classificação de termos .............................................................................
A.8. Manipulação de estruturas ........................................................................
A.9. Igualdade ....................................................................................................
A.10. Avaliação de expressões aritméticas e comparação de números .............
A.11. Gestão de ficheiros .....................................................................................
A.12. Entradas e Saídas ......................................................................................
A.13. Diversos .....................................................................................................
97
97
97
97
98
99
102
103
103
103
104
104
104
106
B. Operações Básicas e Instruções da CxM ...............................................................
B.1. Introdução .................................................................................................
B.2. Pseudo-código ............................................................................................
B.3. Operações básicas da CxM .........................................................................
B.4. Instruções procedimentais e de controlo ..................................................
B.5. Instruções Put ............................................................................................
B.6. Instruções Get ............................................................................................
B.7. Instruções Unify ........................................................................................
B.8. Instruções Build .........................................................................................
B.9. Instruções de indexação ............................................................................
B.10. Instruções para fórmulas de extensão ......................................................
B.11. Instruções de importação ..........................................................................
B.12. Instruções para nomes dependentes do contexto ......................................
B.13. Instruções de gestão do contexto histórico ...............................................
109
109
109
110
114
117
118
119
122
123
125
127
129
130
C. Exemplos de código gerado .................................................................................. 132
Bibliografia ............................................................................................................... 135
7
1
Introdução
1.1. Apresentação
A programação em lógica contextual - ou abreviadamente CxLP - representa um
novo e prometedor esquema de programação, que enriquece de forma significa e útil o
paradigma da programação em lógica. As novidades incluem um suporte para a
estruturação dos programas em diferentes units, e o fornecimento de mecanismos
para combinação dinâmica de units em contextos, que permitem uma forma de
controlo abstracto sobre as derivações dos programas. Este esquema responde a
diversas necessidades sentidas em Inteligência Artificial, sendo por isso de admitir
que ele possa contribuir para o incremento do uso da lógica como formalismo para o
desenvolvimento de aplicações naquela área.
A demonstração da viabilidade de implementar eficientemente uma linguagem
baseada neste paradigma, a um nível próximo dos melhores compiladores de Prolog,
seria com certeza um factor ampliador do interesse por ela. Um dos principais
objectivos do presente trabalho é, precisamente, o de mostrar como isto pode ser feito
numa máquina sequencial convencional, por aplicação de algumas das técnicas que
correspondem ao presente estado da arte da implementação do Prolog. Para isso foi
definida uma máquina abstracta - chamada CxM - que foi concebida como uma
extensão da, muito justamente aclamada, WAM de David Warren. Foram ainda
adaptadas algumas ideias da máquina abstracta C-WAM descrita em [Lamma 89].
Mas o trabalho ficaria incompleto se não incluisse, igualmente, a definição de um
sistema de suporte para CxLP, que fosse encarregado das tarefas de gestão dos dados,
1. Introdução
8
compilação e ligação, e suportando a um ambiente de trabalho mínimo. As duas ideias
chave, que presidiram ao desenvolvimento deste sistema, foram a velocidade de
resposta e flexibilidade na utilização. O aspecto da velocidade foi tratado, não só ao
nível da máquina abstracta (a qual foi alvo de todas as optimizações que foi possível
inventar), mas também ao nível do desempenho do compilador, no qual procurámos
encontrar o melhor compromisso entre rapidez de compilação e qualidade do código
gerado. Quanto à flexibilidade de utilização, foram tratadas entre outras questões, as
que são colocadas em CxLP pelo carácter modular dos programas. Fomos um pouco
além dos mecanismos clássicos da compilação separada e ligação, recorrendo a
técnicas
de
compilação
e
ligação
incrementais,
que
proporcionaram
uma
flexibilidade geral de utilização idêntica à de um interpretador.
1.2. Organização
O próximo capítulo, o segundo deste trabalho, tem um carácter introdutório. Nele é
efectuada uma apresentação sumária das origens e de algumas características
fundamentais
da
programação
em
lógica,
assim
como
da
história
das
implementações da linguagem Prolog. Na sua parte final, é feita uma descrição dos
principais conceitos e nomenclatura envolvidos na máquina abstracta WAM.
No terceiro capítulo descrevemos de forma razoavelmente precisa um sistema
prático para programação em lógica contextual, designado como linguagem CxLP.
Fazemos uma breve descrição das principais noções básicas nele envolvidas, além da
sua definição de um ponto de vista operacional. No final são apresentados alguns
exemplos de utilização da linguagem. Parte deste capítulo constitui uma adaptação de
[Monteiro 89c].
No quarto capítulo são apresentadas e justificadas as principais características da
máquina abstracta CxM com relevo para: forma de representação e gestão dos
contextos, política de estabelecimento de ligações entre nomes e definições de
predicados, e mecanismos para suporte de units parameterizadas.
A forma de conciliação da flexibilidade de um interpretador com a utilização de
técnicas de compilação, é o tema do quinto capítulo. A solução reside nas
características incrementais do sistema que assentam fortemente nos mecanismos de
ligação usados.
No sexto capítulo são abordadas as técnicas de implementação da máquina
abstracta que estão na origem da sua apreciável velocidade. O nosso protótipo de
CxLP, numa forma (quase) portável, corre a aproximadamente 60 Klips numa
VAXstation 3540, o que representa cerca de 2/3 da velocidade do Quintus-Prolog v2.4,
e quase o dobro da velocidade do SB-Prolog e do SICStus-Prolog.
A compilação de programas CxLP constitui o tema do sétimo capítulo. São
referidas as características gerais do compilador, faz-se a descrição de alguns
1. Introdução
9
algoritmos importantes, e discutem-se alguns problemas que surgem na geração de
código específico para controlo dos contextos. São ainda abordadas com algum
detalhe as diversas formas de indexação usadas na CxM.
No capítulo oitavo ocupamo-nos, de forma abreviada, dos seguintes tópicos:
técnicas usadas na implementação dos predicados de sistema, analisador sintáctico
(parser), mecanismo de recuperação de erros de sistema, colectores de lixo e monitor
de comandos.
Na conclusão tecemos breves comentários sobre o estado actual do projecto e o
trabalho a desenvolver a curto prazo.
Antes da bibliografia encontram-se ainda três apêndices onde apresentamos
sucessivamente: a descrição funcional dos predicados de sistema que definimos
(apêndice A), a descrição algorítmica das instruções da CxM com indicação das
condições de geração pelo compilador (apêndice B) e alguns exemplo de código gerado
(apêndice C).
1.3. Agradecimentos
Agradecimentos são devidos a diversas pessoas, a maior parte das quais colegas da
Universidade Nova de Lisboa, pela ajuda prestada no âmbito deste trabalho.
Ao meu orientador Luís Monteiro, e ao meu co-orientador Pedro Veiga, pelo apoio
recebido.
Mais uma vez ao Luís Monteiro, e ao António Porto, pela criação do paradigma da
Programação em Lógica Contextual, o qual constituiu um óptimo pretexto para a
realização deste trabalho.
Ao José Alegria, por inúmeras úteis sugestões e discussões. Reparo agora que a
opção pela realização deste trabalho, bem assim como muitas das suas ideias mais
essenciais (como por exemplo a preocupação com o ambiente de programação),
resultaram muito da sua influência e incentivo ao longo dos últimos anos de trabalho
conjunto.
Ao Paulo Rosado, pelas discussões mantidas sobre a WAM, que muito me ajudaram
a atingir o seu entendimento completo.
Ao Salvador Abreu, pela preciosa ajuda prestada no apuramento, em termos de
velocidade de execução, da versão do sistema CxLP, que corre nos Vax.
À Margarida Mamede, pelo atendimento de inúmeras dúvidas de amplo espectro,
desde a Programação em Lógica até às regras gramaticais da Língua Portuguesa.
Ao Vasco Pedro, pelo esclarecimento de dúvidas relacionadas com a CxLP e com o
pré-processador que ele realizou para uma versão desta linguagem.
1. Introdução
10
Ao Gabriel David, por me ter mostrado a grande utilidade prática de um mecanismo
do tipo do contexto histórico em CxLP, o qual estava ausente dos planos iniciais .
Ao Carlos Ponte e ao António Páscoa por úteis discussões relacionadas com a
implementação da CxM, que contribuíram principalmente para o estabelecimento do
formato final das tags dos termos da linguagem CxLP.
Ao meu pai, Artur Vieira Dias, pela leitura e correcção a nível gramatical de uma
versão deste trabalho.
1.4. Orientação
Esta tese foi orientada por Luís Monteiro, Professor Associado da Universidade
Nova de Lisboa, e co-orientada por Pedro Veiga, Professor Associado da Universidade
Técnica de Lisboa. Foi realizada entre os meses de Novembro de 1989 e de Julho de
1990.
11
2
Programação em lógica
2.1. Origens e características da programação em lógica
A programação em lógica surgiu na sequência de importantes desenvolvimentos na
área da demonstração automática de teoremas, com destaque para a descoberta do
princípio da resolução em 1965 por Robison [Robison 65]. Este princípio consiste num
processo sistemático e eficiente, que permite efectuar demonstrações orientadas por
objectivos em lógica de predicados de primeira ordem e que usa, na representação das
proposições lógicas, a chamada forma clausal.
A ideia de olhar para conjuntos de proposições lógicas como programas e de
considerar o processo de raciocínio, o qual envolve longas sequências de inferências
focalizadas para um objectivo, como computação, deve-se a Green [Green 68].
Em 1972, Alain Colmeraurer, com a ajuda de P. Roussel, desenvolveu na
Universidade de Marselha um sistema de raciocínio destinado ao processamento de
linguagem natural, no qual mostrou que se fosse considerada uma parte restrita da
lógica
proposicional,
o
princípio
da
resolução
podia
ser
implementado
eficientemente, de forma análoga à da invocação de procedimentos nas linguagens
imperativas [Colmeraurer 72]. Este sistema, escrito em Algol W, foi chamado de
Prolog, nascendo assim esta linguagem.
Uma implementação mais prática do Prolog seria desenvolvida no ano seguinte
por dois discípulos de Colmeraurer: Battani e Meloni [Battani 73]. Foi usada na
implementação a linguagem Fortran, a única suficientemente portável da época,
tendo-se registado uma considerável difusão do sistema. A influência deste Prolog,
2. Programação em Lógica
12
dito de Marselha, persiste ainda nos dias de hoje, atendendo a que algumas das suas
características mais importantes são ainda aceites na prática, estando presentes na
maior parte das implementações actuais da linguagem. Os aspectos a que nos
referimos são os seguintes: estratégia de controlo, utilização dos predicados de
sistema cut/0, univ/2, assert/1 e retract/1, possibilidade de definição de operadores
pelo utilizador, e suporte para gramáticas de cláusulas definidas ([Colmeraurer 75]).
Em 1974, Kowalsky e van Emden identificaram a natureza da restrição usada por
Colmeraurer no Prolog, e formularam com rigor uma interpretação procedimental
para o domínio da lógica das cláusulas de Horn, baseada na estratégia de controlo
SLD-resolução [Kowalski 74]. A estratégia usada na linguagem Prolog - pesquisa
depth-first com retrocesso, no espaço de estados - representa apenas um caso
particular deste tipo de resolução: outra alternativa, que neste caso tem a
desvantagem de ser mais exigente em termos de recursos computacionais, é a
correspondente a uma pesquisa breadth-first, tal como se faz na linguagem LogLisp
[Robison 80].
É também a van Emden e Kowalsky que devemos outro estudo fundamental da
semântica da programação em lógica [van
Emden
76].
Neste
trabalho
eles
desenvolveram três tipos distintos de semânticas - operacional, declarativa (ou
não -operacional) e denotacional - e provaram a sua equivalência.
Desde as suas origens, que acabámos de descrever, até aos dias de hoje, muito
trabalho tem sido desenvolvido na área da programação em lógica, registando-se
grande evolução. Do ponto vista da sua aplicação prática, o paradigma tem tido
também bastante sucesso e ganho numerosos aderentes, o que não será de surpreender
se pensarmos nas suas múltiplas vantagens como ferramenta de programação:
expressividade, clareza, versatilidade, facilidade de manutenção, vasto domínio de
aplicação, etc.
O aspecto crucial deste tipo de programação, de onde derivam todas as vantagens
atrás referidas, reside no seu forte carácter declarativo, herdado da utilização da
lógica como formalismo para a escrita de programas. É aliás este o motivo que
justifica o facto das linguagens lógicas serem muitas vezes classificadas como sendo
de muito alto nível. Com efeito, é frequente que uma boa implementação de um
programa em lógica seja também uma sua boa especificação.
Este aspecto declarativo é realçado pela circunstância de o conteúdo descritivo dos
programas em lógica ser absolutamente independente dos mecanismos de execução
usados, ao contrário do que se passa com as linguagens imperativas. Inclusivamente,
o comportamento das suas variáveis é controlado pelo processo de alto nível do
emparelhamento de padrões da unificação, não necessitando de ser analisado por
referência a um estado da computação.
2. Programação em Lógica
13
Apesar do que ficou dito, durante o desenvolvimento de programas Prolog não é
possível evitar ter de considerar o controlo da sua execução, se quisermos que sejam
eficientes e que existam garantias de terminação. Idealmente, seria excelente que o
sistema de suporte da linguagem tivesse a possibilidade de deduzir a partir da
componente declarativa de um programa uma estratégia de controlo adequada;
contudo parece difícil que esta esta ideia possa alguma vez deixar de fazer parte do
domínio da ficção científica.
2.2. Um pouco da história das implementações de Prolog
Antes que a lógica pudesse ser considerada como um formalismo prático,
suficientemente competitivo para o desenvolvimento de programas, foi necessária
uma grande evolução na tecnologia de implementação.
Pelos padrões actuais, o interpretador de Prolog de Marselha não era muito
eficiente, quer em termos de utilização de memória, quer em termos de velocidade de
execução. Por exemplo, os registos de activação criados na invocação dos predicados
só eram desempilhados na ocorrência de retrocesso e, no que respeita à velocidade,
segundo Warren [Warren 74] ela não excedia os 200 lips num IBM 360-67. Foi nesta
implementação que pela primeira vez foi usada a importante a técnica de
representação dos termos chamada de partilha de estrutura ou SS (structure sharing),
na qual se tira partido do facto de diferentes instâncias do mesmo termo diferirem
apenas nas instanciações das suas variáveis.
Bruynooghe desde muito cedo se interessou pelos problemas de gestão de memória
envolvidos no Prolog. A ele se deve um interpretador [Bruynooghe 76] onde pela
primeira vez foi usado um algoritmo de recuperação de memória na pilha de execução
e foi
implementada
a
optimização
TRO (tail
recursion
optimization). Esta
optimização permite substituir certas recursões por iterações, que assim são
executadas sem consumo crescente de memória. Subsequentemente usou num
interpretador escrito em C, datando de 1979, uma técnica de representação dos termos
dita NSS (non-structure sharing) baseada em cópia de estrutura.
A primeira experiência de aplicação de técnicas de compilação à implementação da
linguagem Prolog é devida a David Warren e data de 1977 [Warren 77a]. Nessa
implementação, que deu origem ao conhecido “Dec-10 Prolog”, era gerado código
nativo sendo usada a técnica de partilha de estrutura na representação dos termos.
Entre outras novidades, Warren introduziu a noção de variável local e de variável
global, pilhas de execução múltiplas para permitir recuperação de memória nas fases
deterministas da execução dos programas, e um mecanismo de indexação das
cláusulas pelo primeiro símbolo funcional. O ganho de velocidade conseguido em
relação aos interpretadores de Prolog foi da ordem de 5 a 10 vezes mais. Este ganho é
bastante inferior (cerca de 3 vezes) ao que geralmente se consegue obter na compilação
2. Programação em Lógica
14
das linguagens imperativas tradicionais e justifica-se, em parte, pelo facto de o nível
de pré-tratamento possível, ser condicionado pela ocorrência de variáveis nos
objectos manipulados. Esta circunstância impõe na prática um certo grau de
interpretação durante a execução de programas. De qualquer maneira, a melhoria de
desempenho foi significativa e teve grande importância teórica pois pela primeira
vez, foi demonstrado que a linguagem podia rivalizar em termos de desempenho com a
sua rival natural na área do processamento simbólico: a linguagem Lisp (ver
[Warren 77b]).
Um outro marco fundamental na evolução das implementações do Prolog foi
também protagonizado por D. Warren em 1983 [Warren 83], quando apresentou a
máquina abstracta WAM (Warren abstract machine) que se destinava a ser
implementada por meio de emulação (em software , firmware ou hardware). Esta
incluía significativas melhorias em relação à versão de 1977. As técnicas usadas
incluíam uma representação de termos NSS, separação entre registos de activação e
pontos de escolha, um novo método de optimização chamada LCO (last call
optimization) que generalizava a técnica TRO, e a introdução da noção de
registo-máquina para incrementar as oportunidades de optimização do código. Nesta
máquina era feita uma admirável compatibilização e síntese dos principais
desenvolvimentos que até à altura tinham resultado
de
muita
discussão
e
investigação.
A WAM está na base de algumas das melhores implementações actuais do Prolog, e
só não tem tido maior divulgação devido à sua relativa complexidade aliada ao
hermetismo da escassa informação disponível. Só muito recentemente, surgiu uma
monografia na qual a WAM é finalmente tornada mais acessível: [Aït-Kaci 90].
Durante os anos 80 floresceram implementações de Prolog abrangendo uma gama
vasta de filosofias. Eis exemplos de algumas técnicas de implementação retiradas da
referência [Hermenegildo 89]:
• Compilação para código da WAM ou de evoluções desta: SICStus-Prolog,
SB-Prolog, Quintus-Prolog
• Compilação para código nativo: BIM-Prolog
• Tradução directa para C: Proteus-Prolog
• Concepção de hardware especializado, em muitos casos derivado da WAM: PSI-I,
PSI-II, PLM, IPP, CHI -I, CHI-II, Low-RISC.
Pesando as vantagens e inconvenientes destas aproximações em relação a diversos
factores conflituantes - portabilidade, compacidade do código gerado, velocidade de
execução dos programas, grau de complexidade da implementação,
optimização do código
possível,
facilidade
de
integração
num
nível
de
ambiente
de
programação, adequação à prototipagem e integração de novas ideias, custo
2. Programação em Lógica
15
monetário - parece que na maioria dos casos a melhor será aquela que corresponde à
primeira aproximação, não obstante em termos de velocidade pura, as outras três,
com destaque para a última, deverem merecer preferência.
Para além das evoluções registadas na implementação dos mecanismos de
execução do Prolog, a tecnologia de compilação tem também
sido
alvo
de
significativos desenvolvimentos, sendo actualmente usadas sofisticadas técnicas de
análise global de programas entre as quais de destaca um método geral chamado de
interpretação abstracta [Cousot 77]. Mediante a utilização de diferentes domínios
abstractos, ele permite extrair dos programas informação de natureza diversa,
alguma da qual pode ser usada na optimização de código. É por exemplo exemplo
possível inferir uma grande parte dos modos (entrada, saída ou misto) dos parâmetros
formais dos predicados. Daqui resulta a viabilidade da descoberta do carácter
determinista ou funcional de alguns predicados, e a possibilidade de se fazer um
pré-tratamento parcial de maior número de unificações.
Estão ainda na ordem do dia as implementações de linguagem lógicas em
máquinas paralelas, tanto em arquitecturas multiprocessador de utilização geral
como em arquitecturas especialmente adaptadas. Foi Kowalski quem pela primeira
vez referiu o potencial da programação em lógica na programação de máquinas
paralelas, que advém do facto de o conteúdo declarativo de um programa em lógica ser
independente da estratégia de execução usada [Kowalski 79b]. De modo geral, nas
linguagens procedimentais clássicas, até mesmo o conteúdo lógico dos seus programas
está demasiado comprometido com o modelo clássico de computação de von Newman.
2.3. A WAM
A WAM tem sido na prática reconhecida como um standard para a implementação
de compiladores de Prolog, encontrando-se na base das melhores implementações
actuais da linguagem. Tem sido, além disso, utilizada em algumas importantes áreas
de investigação tais como a demonstração automática de teoremas, o desenho de
hardware especializado para execução altamente eficiente de Prolog e como suporte de
extensões ao paradigma lógico (com destaque para a concorrência). Este trabalho
representa mais um exemplo de aplicação da WAM.
Apesar da WAM estar quase a fazer sete anos, devido a razões diversas o
conhecimento íntimo dos seus mecanismos não tem atingido a divulgação que lhe
faria justiça. Para tornar este trabalho minimamente acessível a um leitor não
familiarizado com ela, pareceu-nos indispensável fazer uma breve apresentação das
suas características mais importantes, o que também servirá de pretexto para a
introdução de alguma terminologia necessária. Somos obrigados no entanto de
ignorar, entre outros aspectos, os intrincados detalhes de baixo nível e a justificação
da configuração da máquina, cujo desenho final resultou de diversas optimizações
2. Programação em Lógica
16
subtis e intrinsecamente ligadas. Para este estudo aprofundado da WAM recomenda-se
a referência, [Aït-Kaci 90].
2.3.1. Representação dos termos
Um termo é representado na WAM por uma célula de memória na qual se
distinguem essencialmente duas zonas: a tag e o valor. A tag serve para distinguir o
tipo do termo o qual pode ser variável, estrutura, lista ou constante. Quanto ao valor
ele constitui uma referência para a memória, excepto no caso das constantes inteiras e
reais em que consiste num valor numérico.
Uma variável livre é representada, por convenção, como uma auto-referência,
enquanto que uma variável instanciada contém o termo que lhe foi atribuído. Daqui
resulta que um conjunto de variáveis ligadas acaba por ser representado por uma lista
ligada.
A forma de representação dos termos usada é a designada de cópia de estrutura, que
se caracteriza pelo facto de a criação de um termo estruturado exigir a cópia explicita
do seu functor e argumentos para posições de memória consecutivas.
2.3.2. Áreas de dados
São usadas na WAM cinco áreas de dados distintas, as quais são seguidamente
apresentadas:
•Área de código
Contém o programa.
•Stack local
Centraliza toda a informação de controlo respeitante
aos
mecanismos de activação de predicados e de retrocesso. Os dois
tipos de estruturas dados usadas nestas tarefas, chamam-se
respectivamente registos de activação e pontos de escolha.
•Heap
Também conhecido por stack global, é constituído pelos termos
criados durante a execução do programa, como resultado das
unificações e da passagem de termos estruturados nas chamadas
de predicados.
•Trail
Pilha onde são guardadas referências para todas as variáveis
instanciadas condicionalmente, para que sejam reinicializadas
quando ocorrer retrocesso.
•PDL
Pilha usada pela rotina de unificação geral.
Os dados que se encontram no stack local e no heap obedecem a diversos
invariantes que garantem a coerência do estado interno da máquina. Estas duas áreas
crescem geralmente na invocação de predicados, e reduzem-se quando ocorre
retrocesso. O stack local contrai-se também sempre que termina, de forma
determinista a execução de um predicado.
2. Programação em Lógica
17
2.3.3. Estruturas de dados de controlo
A activação de uma cláusula implica muitas vezes a criação de um registo de
activação. Este é constituído por um vector, onde são guardadas as suas variáveis
permanentes, um apontador (chamado continuação) que indica o golo de outra
cláusula onde a execução irá prosseguir quando a cláusula corrente terminar, e ainda
outro apontador para o registo de activação da cláusula de continuação. Estes dois
apontadores representam a lista dos golos que aguardam execução, ou seja, no fundo, a
resolvente corrente do sistema de inferência.
A decisão de permitir a existência de variáveis no stack local destina-se a poupar
espaço no heap, já que neste, os dados são bastante persistentes. Introduz no entanto,
no tratamento das variáveis livre, uma pequena complicação, relacionada com a
manutenção dos invariantes da máquina, a qual tem de ser gerida parcialmente em
tempo de compilação e parcialmente em tempo de execução.
Um ponto de escolha é criado sempre que é chamado um predicado não
determinista, no momento exacto que precede a activação da primeira cláusula que
responde à chamada. Representa um instantâneo do estado da computação no
momento da invocação, servindo para restaurar esse estado em caso de retrocesso,
para ser tentada a próxima cláusula. Só é destruído no momento em que não restarem
cláusulas alternativas. O conteúdo dos pontos de escolha é o seguinte: valores dos
argumentos da chamada (têm de ser repostos em cada nova tentativa de satisfação da
chamada), conteúdo dos principais registos da WAM (H, TR, B, CP, E), e referência para
o código da próxima cláusula alternativa.
2.3.4. Registos da WAM
O conjunto de registos da WAM definem o estado corrente da computação. São os
seguintes:
•P
Contador de programa, aponta para a instrução corrente na zona de código.
• CP Continuação de programa, é carregado com o endereço de retorno da chamada
de um predicado, desde que ela não seja a última da cláusula.
•E
Registo de activação corrente.
•B
Ponto de escolha corrente.
• TR Topo do trail.
•H
Topo do heap.
• HB Valor do registo H no ponto de escolha corrente. Permite acelerar o teste de
averiguação da necessidade de memorização de uma variável no trail, o qual é
feito sempre que se instancia uma variável.
2. Programação em Lógica
•S
18
Chamado apontador de estrutura. Trata-se de um apontador para o heap que
desempenha um papel central nas unificações que se processam durante o
emparelhamento de uma cláusula com uma chamada.
• Xi
Conjunto de registos usados para passagem de parâmetros
e
para
armazenamento temporário de valores. Muitas das optimizações que é
possível introduzir no código gerado, baseiam-se no uso destes registos.
Note-se que os registos da WAM são, como a própria máquina, virtuais, sendo
geralmente definidos, na linguagem de implementação, como um simples
vector de células de memória.
2.3.5. Classificação das variáveis
Em relação às variáveis que surgem nas cláusulas do programa fonte, Warren fez
uma distinção entre variáveis permanentes e variáveis temporárias. Simplificando
um pouco a realidade, uma variável diz-se permanente quando o seu conteúdo tiver de
ser preservado ao longo da derivação de vários golos dentro do corpo de uma cláusula.
São armazenadas nos registos de activação das cláusulas a que pertencem, sendo
denotadas por Y i, em que i indica o seu deslocamento em relação à base do registo de
activação. As restantes variáveis, ditas temporárias, são associadas a registos Xi da
WAM, o que é vantajoso em termos de velocidade e de ocupação de memória1.
Importantes optimizações podem ser feitas pelo compilador, através da criteriosa
escolha dos registos a associar às variáveis temporárias.
2.3.6. Optimização da última chamada (LCO) e trimming
Numa cláusula, é perfeitamente natural a circunstância de uma variável
permanente ser referida, por exemplo, no seu último golo. Este facto, à primeira vista,
sugere a necessidade de deixar a eliminação do registo de activação da cláusula só para
depois de ter sido executado o seu último golo, já que caso contrário, algumas
variáveis permanentes deixariam de ter memória associada, o que aparenta ser
catastrófico.
Apesar de tudo, na WAM os registos de activação são por regra desempilhados no
momento que precede a chamada do último golo das cláusulas, já depois dos
argumentos actuais terem sido carregados nos registos Xi . O problema descrito no
parágrafo anterior coloca-se de facto, mas felizmente apenas num caso particular, que
pode ser facilmente antecipado pelo compilador. Trata-se do caso em que, em tempo de
execução, uma variável permanente, ocorrendo no último golo de uma cláusula ao
nível da superfície, se encontra livre ou ligada a uma variável qualquer do registo de
activação prestes a desaparecer. As variáveis assinaladas pelo compilador como
1O valor dos registos X i não é preservado nas invocações de predicados, razão que os impede
de funcionar como variáveis permanentes.
2. Programação em Lógica
19
suspeitas, são designadas como variáveis unsafe, sendo gerados padrões especiais de
código para ela. Em tempo de execução, quando uma variável unsafe é passada como
parâmetro actual da última chamada de uma cláusula, testa-se se ela refere de alguma
forma o registo de activação a ser destruído. Em caso positivo procede-se à sua
transferência para o heap, o que envolve algumas manipulações cujos detalhes não
são aqui explicados.
Esta técnica tem consequências extremamente importantes: redução geral de
consumo de memória no stack local, execução de predicados recursivos deterministas
sem crescimento do stack local, e ausência de necessidade de criação de registos de
activação nas cláusulas com menos de dois golos no corpo. Desta menor frequência na
criação de registos de activação resulta ainda um significativo aumento da velocidade
da máquina.
Na WAM a técnica de optimização da última chamada (LCO), atrás descrita, é ainda
objecto de uma generalização denominada trimming. O trimming consiste na
progressiva redução de tamanho do registo de activação de uma cláusula à medida que
se vai fazendo a sua execução da esquerda para a direita, por libertação do espaço
ocupado pelas variáveis permanentes que vão deixando de ser referidas. A eliminação
destas variáveis levanta problemas semelhantes aos que surgem na aplicação de LCO,
pelo que a noção de variável unsafe e concomitante técnica de transferência para o
heap, são generalizadas aos golos intermédios das cláusulas. O uso de trimming
implica que o compilador faça uma adequada ordenação das variáveis dentro do
registo de activação por forma a maximizar a poupança de memória obtida. O número
de variáveis permanentes a preservar em cada golo do corpo de uma cláusula, é
registado como segundo argumento nas instruções Call Proc, N.
2.3.7. Indexação
Warren reintroduziu na WAM o mecanismo de indexação das cláusulas pelo
primeiro símbolo funcional, que já tinha usado no seu primeiro compilador em 1977.
Trata-se de um método que permite fazer uma filtragem das cláusulas de um predicado
candidatas a emparelhamento, após cada
chamada.
O
ganho
de
velocidade
proporcionado é geralmente muito significativo, já que se evita a exploração de
muitas cláusulas infrutíferas. O caso mais favorável é aquele em que o resultado da
filtragem se reduz a uma única cláusula: o predicado torna-se determinista não sendo
necessário criar qualquer ponto de escolha.
2.3.8. Instruções
Até este momento já descrevemos uma parte substancial da funcionalidade da
WAM; não apresentámos ainda, no entanto, qualquer indicação sobre a natureza das
suas instruções.
2. Programação em Lógica
20
A ideia que se encontra na base da definição de um conjunto de instruções
abstractas para suporte da funcionalidade da WAM é simples: consiste em identificar
todas as operações elementares significativas, procedendo de seguida ao seu
isolamento em instruções máquina específicas. O conjunto básico de instruções da
WAM, de acordo com [Warren 83], compreende um número reduzido de cerca de 40
instruções. Os programas Prolog são codificados em sequências destas instruções. Os
seus argumentos, que são em número não superior a quatro, podem representar
diversas entidades: variável temporária (Xi ), variável permanente (Yi ), functor (F),
predicado (Pred), constante (C), etiqueta de programa (L), valor inteiro pequeno (N), ou
tabela de dispersão (HashTable).
As instruções da WAM agrupam-se nas cinco grandes classes, seguidamente
indicadas:
Instruções Procedimentais - Fazem a gestão dos registos de activação e das
transferências de controlo.
Allocate
Deallocate
Proceed
Execute Pred
Call Pred, N
Instruções Put - Carregam os argumentos actuais nos registos Xi , preparando a
invocação dos predicados.
PutVariable Vn, Xi
PutValue Vn, Xi
PutUnsafeValue Yn, Xi
PutConstant C, Xi
PutStructure F, Xi
PutList Xi
Instruções Get - Fazem a unificação dos argumentos formais das cláusulas com os
argumentos actuais passados em registos Xi .
GetVariable Vn, Xi
GetValue Vn, Xi
GetConstant C, Xi
GetStructure F, Xi
GetList Xi
Instruções Unify - Fazem as unificações correspondentes aos argumentos de termos
estruturados. Funcionam em dois modos: leitura e escrita. Em modo de leitura
unificam os argumentos de duas estruturas; em modo de escrita constróiem os
argumentos de uma nova estrutura. A WAM transita para modo de escrita sempre que
se processa a unificação de uma variável com um termo estruturado: recordemos que a
WAM usa a técnica de cópia de estrutura na representação dos termos.
UnifyVariable Vn
UnifyVoid N
UnifyValue Vn
UnifyConstant C, Xi
UnifyStructure F, Xi
UnifyList Xi
2. Programação em Lógica
21
Instruções de indexação - Dividem-se em duas subclasses que incluem as instruções
de pré-selecção das cláusulas candidatas a responder a uma chamada, e as instruções
de exploração das diversas cláusulas alternativas de um predicado (com gestão dos
pontos de escolha).
SwitchOnTerm Lv, Lc, Ll,Ls
SwitchOnConstant N, HashTable
SwitchOnStructure N, HashTable
TryMeElse L
RetryMeElse L
TrustMe
Try L
Retry L
Trust L
No apêndice B podem ser observadas as definições rigorosas das instruções de uma
máquina abstracta - a CxM -, algumas das quais são idênticas às da WAM. Por sua vez,
no apêndice C encontram-se alguns exemplos de codificação de cláusulas usando as
instruções da máquina CxM, exemplos esses que também dão uma ideia aproximada
de como a codificação é feita na WAM.
22
3
Programação em Lógica Contextual
3.1. Introdução
Ao longo dos últimos anos, o paradigma da programação em lógica tem sido objecto
de múltiplas extensões e variações. Existem dois conjuntos de factores justificativos
deste facto.
Em primeiro lugar, não obstante as inúmeras vantagens que as linguagens lógicas
do tipo do Prolog reconhecidamente proporcionam, algumas importantes limitações
têm sido identificadas. De entre as que habitualmente são mais referidas destacamos:
a estratégia de controlo usada, a utilização indiscriminada da negação como
falhanço, a utilização de predicados extra-lógicos para a modificação dinâmica da
base de dados, inadequação para o tratamento de conhecimento não monotónico e a
inexistência de mecanismos de suporte para aplicação de princípios de engenharia de
software no desenvolvimento de programas.
Em segundo lugar, os investigadores têm constatado da conveniência de ampliar o
poder expressivo e a eficiência dessas linguagens, através da introdução de novos
mecanismos que as tornem mais adaptadas a domínios específicos de aplicação e
ainda, procedendo à sua integração com as mais valiosas facilidades oferecidas por
outros paradigmas de programação: concorrência, funções, objectos e restrições.
A proposta de extensão do paradigma de programação em lógica, que está na base
deste trabalho, e que recebeu o nome de Programação em Lógica Contextual - CxLP -, é
devida a Luís Monteiro e António Porto que a apresentaram em 1989 [Monteiro 89a].
As adições efectuadas ao esquema base tiveram dois objectivos em vista.
3. Programação em Lógica Contextual
23
O primeiro foi o de enriquecer o paradigma com mecanismos para suporte da
aplicação de alguns importantes princípios de engenharia de software: modularidade
e generalidade. Para isso introduziu-se o clássico conceito de módulo, que aqui recebe
o nome de unit. O controlo da visibilidade dos predicados no exterior das units, assim
como as importações, são feitas da forma tradicional mediante declarações
apropriadas. As units podem ser parametrizadas sendo geralmente os valores dos seus
parâmetros outras units.
O segundo objectivo têm a ver com estabelecimento de um modelo computacional
para suporte directo de raciocínio contextual, o qual surge de forma constante em
Inteligência Artificial. A execução de um programa em CxLP corresponde à prova de
golos em relação a contextos os quais se definem como simples sequências de units. Os
contextos podem ser alterados dinamicamente de diversas formas, sendo a mais
notável a que recorre ao uso das chamadas fórmulas de extensão. Estas fórmulas
permitem ampliar o contexto de uma prova com as definições de predicados contidas
numa ou mais units.
Neste capítulo é feita uma descrição sumária, mas suficientemente precisa para os
nossos objectivos, das principais noções básicas envolvidas num sistema prático de
programação em lógica contextual - linguagem CxLP -, sendo ainda
incluída a
definição da sua semântica operacional. Descrições mais aprofundadas e detalhadas
poderão ser encontradas em [Monteiro 89a] e [Monteiro 89c]. No final são
apresentados alguns pequenos exemplos de utilização da linguagem.
3.2. Sintaxe
A sintaxe da linguagem CxLP é uma extensão directa da sintaxe da lógica das
cláusulas de Horn. O seu alfabeto é constituído, para além de nomes de variáveis, de
nomes de funções, e de nomes de predicados, também por nomes de unit. Os termos,
fórmulas atómicas e cláusulas da linguagem são definidos da forma habitual, excepto
no que diz respeito a quatro novos tipos de fórmulas que podem ocorrer no corpo das
cláusulas. São as fórmulas de extensão “U>>G”, fórmulas de salvaguarda de contexto
“>G”, fórmulas de reposição de contexto “<G” e fórmulas de libertação de contexto
“?G”. Nestas fórmulas, U pode ser um designador de unit ou uma variável, e G é uma
fórmula qualquer.
3.3. Units
Em programação em lógica contextual um programa consiste num sistema de
units. Cada unit U caracteriza-se pelos seguintes quatro atributos: etiqueta U L,
definições U D , importações U I e visibilidade U V: Vejamos em que consiste cada um
deles:
3. Programação em Lógica Contextual
24
• Etiqueta U L é um termo u(P 1,...,P n ) (n≥0), onde u é o nome da unit e P 1,...,P n são
variáveis distintas, que recebem o nome de parâmetros da unit. Uma
propriedade
importante
dos
nomes
de
units
é
que
estes
determinam
univocamente a unit que nomeiam.
• Definições U D é um conjunto de cláusulas h:-b que se dizem definidas
localmente em U. Nestas
cláusulas,
além
das
variáveis
normais
cuja
quantificação implícita, como se sabe, abrange toda a cláusula, podem aparecer
também parâmetros da unit cuja quantificação abrange toda a unit. O conjunto
de todos os nomes de predicado definidos numa unit U representa-se por
Definidos(U).
• Importações U I é um conjunto de pares <p,t> onde p é um nome de predicado (que
se diz importado) e t é um termo cujas variáveis são todas parâmetros em U L. O
conjunto de todos os nomes de predicado importados por uma unit U
representa-se por Importados(U).
• Visibilidade U V é um conjunto de nomes de predicados que se dizem visíveis no
exterior de U.
Por definição, os conjuntos U D , U I e U V que intervêm da caracterização de U
obedecem às seguintes restrições:
• Um nome de predicado não pode ser simultaneamente importado e definido
localmente em U.
• Um nome de predicado só pode ser mencionado uma vez no conjunto das
importações.
• Só os nomes de predicado definidos localmente ou importados podem aparecer
na visibilidade de U.
3.4. Designador de Unit
Chama-se designador de unit a qualquer instância da etiqueta U L de uma unit U
existente. Desta forma, é condição necessária e suficiente para que um termo t seja
designador de unit que ele corresponda a uma estrutura cujo functor principal seja o
nome de uma unit existente. O predicado designador_de_unit(t) permite testar se um
termo t é um designador de unit. A instância de unit que é determinada por um
designador de unit t chama-se unit designada e representa-se por |t|.
3.5. Contexto
Um contexto define-se simplesmente como uma pilha de designadores de unit e
representa-se pela simples concatenação desses designadores. Assim em relação ao
contexto uC, o designador de unit u corresponde ao topo do contexto sendo C a sua
3. Programação em Lógica Contextual
25
parte restante. A unit designada pelo topo do contexto corrente, neste caso |u|, recebe o
nome de unit corrente. O contexto vazio é representado por λ.
O contexto varia durante a execução dos programas e determina, em cada momento,
o conjunto de cláusulas a serem consideradas na prova dos golos.
3.6. Nomes dependentes do contexto
Todos os nomes de predicado que sejam referidos nos corpos das cláusulas de uma
unit U e aos quais não correspondam nomes de predicados locais ou importados
dizem-se dependentes
do
contexto. Da
definição
operacional
da
linguagem
apresentada mais adiante, extrai-se que a definição de predicado associada a um
nome dependente do contexto, é a que se encontra na unit designada que se encontra
mais próximo do topo do contexto corrente que possui uma definição visível para esse
nome.
3.7. Contexto histórico
O contexto histórico (ou contexto de nível 2), define-se como uma pilha de
contextos. É representado por uma sequência de contextos separados pelo operador
infixo “•”. Desta forma, em relação ao contexto histórico C•Ψ, o contexto C é o seu topo
sendo Ψ a parte restante. O contexto situado no topo do contexto histórico é aquele que
directamente afecta as derivações efectuadas durante a execução dos programas
recebendo por isso o nome de contexto corrente.
O contexto histórico pode ser alterado durante a execução dos programas. Constitui
um meio de memorização de contextos com vista à sua posterior reposição.
3.8. Regras de inferência
Em programação em lógica contextual as derivações são sempre feitas em relação a
contextos. A forma geral de um elemento da relação de derivação é pois a seguinte:
C•Ψ |M g [θ]
em que C é o contexto corrente, Ψ a parte restante do contexto histórico, g um golo, θ
uma substituição e M o modo da derivação. M toma valores no conjunto {i, e} cujos
elementos representam respectivamente os modos interno e externo que têm de ser
considerados para modelar as restrições de visibilidade que limitam o uso das
definições dos predicados.
Na escrita das regras de inferência usamos, tal como em [Monteiro 89c], a forma de
Plotkin [Plotkin 81]:
Antecedentes
Consequente
Condições
3. Programação em Lógica Contextual
26
onde Consequente é um elemento da relação de derivação, Antecedentes é constituído
por zero, um ou dois elementos da relação de derivação e Condições é um conjunto,
eventualmente vazio, de proposições. A interpretação procedimental de uma regra
destas é a seguinte: para estabelecer o Consequente no caso em que se todos os
elementos de Condições são verdadeiros derivam-se os Antecedentes.
Seguidamente apresenta-se a lista
das
regras
de
inferência
que
definem
operacionalmente a linguagem CxLP e que serviu de referência para a implementação
efectuada. Convém referir desde já que todas as regras são mutuamente exclusivas e
que, como na interpretação procedimental da lógica das cláusulas de Horn, o não
determinismo ocorre apenas ao nível da regra Redução.
True
C•Ψ |M true[ε]
O golo true é derivável em qualquer contexto e modo, usando a substituição vazia.
Conjunção
C•Ψ |M g1 [θ]
(C•Ψ)θ |M g2θ [σ]
C•Ψ |M (g1,g2) [θσ]
Para derivar uma conjunção derivam-se os dois golos no mesmo contexto e modo.
Note-se que tanto o contexto corrente como o contexto histórico podem mudar durante
a derivação de g1, pelo que é necessário fazer a sua reposição para a execução de g2.
Além disso atendendo a que C•Ψ pode conter variáveis, as substituições que resultam
da instanciação de variáveis de g1 também lhe devem ser aplicadas para que g2θ seja
correctamente derivado.
Redução
(uC•Ψ)θ |i bθ [σ]
uC•Ψ |i g [θσ]
{ h :- b ∈ |u|D, θ = mgu(g,h) }
Esta regra aplica-se em modo interno ao caso em que o predicado associado ao golo
atómico g está definido na unit corrente |u|. É feita a redução de g na unit corrente e
prossegue-se com a derivação do corpo da clausula usada nessa redução. A expressão
mgu(g,h) representa o unificador mais geral entre g e h.
Substituição
vC•Ψ|e g [θ]
uC•Ψ |i g [θ]
{ <nome(g),v> ∈ |u|I ,
designador_de_unit(v) }
Em modo interno, se o nome de predicado associado a g for importado a partir de
uma unit v, é feita a substituição de u por v no topo do contexto corrente, e a derivação
de g no novo contexto prossegue em modo externo.
3. Programação em Lógica Contextual
27
Saída
C•Ψ |e g [θ]
uC•Ψ |i g [θ]
{ nome(g) ∉ Definidos(|u|) ∪
Importados(|u|) }
Em modo interno, para derivar um golo atómico g sem definição local ou
importada na unit corrente, passa-se para modo externo e elimina-se o topo do
contexto corrente. A derivação de g prossegue no novo contexto.
Descida
C•Ψ |e g [θ]
uC•Ψ |e g [θ]
{ nome(g) ∉ |u|V }
Em modo externo, caso o nome de predicado do golo g não seja visível na unit
corrente, g é derivado também em modo externo mas no contexto que se obtém do
inicial, eliminando o seu topo.
Entrada
uC•Ψ |i g [θ]
uC•Ψ |e g [θ]
{ nome(g) ∈ |u|V }
Em modo externo, caso o nome do predicado de g seja visível na unit corrente, a
derivação prossegue em modo interno no mesmo contexto.
Extensão
uC•Ψ |e g [θ]
{ designador_de_unit(u) }
C•Ψ |M u >> g [θ]
Para derivar a fórmula de extensão u>>g, em que u é um designador de unit, faz-se a
derivação de g no contexto corrente estendido por u. Esta derivação é efectuada em
modo externo.
Libertação
λ•Ψ |e g [θ]
C•Ψ |M ?g [θ]
O contexto corrente é substituído pelo contexto vazio. Esta regra é útil no caso em
que g é uma formula de extensão de contexto, pois dá a possibilidade da construção de
um contexto novo de raiz.
Salvaguarda
C•C•Ψ |M g [θ]
C•Ψ |M >g [θ]
O contexto corrente é duplicado no topo do contexto histórico prosseguindo a
derivação sem qualquer alteração adicional. Este mecanismo destina-se a memorizar
o contexto no qual se inicia a prova de g para reposição posterior.
3. Programação em Lógica Contextual
28
Reposição
Ψ |e g [θ]
C•Ψ |M <g [θ]
Remove o contexto corrente do topo do contexto histórico tornando portanto
corrente o último contexto que foi salvaguardado.
3.9. Exemplos
Neste ponto vamos ilustrar a utilização da linguagem com alguns exemplos de
aplicação, muito simples, baseados em [Monteiro 89a]. Todos eles apresentam
diversas formas de definir aproximadamente o mesmo programa usando vários dos
novos mecanismos da CxLP. Para cada um destes exemplos, são ainda exibidas uma
ou duas interrogações do sistema, acompanhadas pelas sequências de derivações que
originam.
Cada programa é constituído por um par de units, uma das quais é partilhada por
todos os programas. Trata-se da unit books que contém informação sobre escritores
de livros e que exporta esses dados através do predicado wrote/2:
unit books.
visible wrote/2.
wrote(plato,republic).
wrote(homer,iliad).
A outra unit, chamada authors, define autor como alguém que escreveu um livro.
Encontra-se programada em todos os casos com características genéricas.
Exemplo 1 - wrote/2 dependente de contexto
unit authors.
visible author/1.
author(Person) :- wrote(Person, _).
?- books >> authors >> author(Who).
λ
|i books >> authors >> author(Who)
books
|e books >> author(Who)
(Extensão)
authors.books
|e author(Who)
(Extensão)
authors.books
|i author(Who)
(Entrada)
authors.books
|i wrote(Who, _)
(Redução)
books
|e wrote(Who, _)
(Saída)
books
|i wrote(Who, _)
(Entrada)
books
|i true
(Redução)
sucesso [{Who/plato}]
?- authors >> books >> author(Who).
λ
|i authors >> books >> author(Who)
authors
|e books >> author(Who)
(Extensão)
books.authors
|e author(Who)
(Extensão)
authors
|e author(Who)
(Descida)
authors
|i author(Who)
(Entrada)
3. Programação em Lógica Contextual
authors
λ
falhanço
|i wrote(Who,_)
|i wrote(Who,_)
(Redução)
(Descida)
Exemplo 2 - Extensão de contexto usando parâmetro de unit
unit authors(Works).
visible author/1.
author(Person) :- Works >> wrote(Person, _).
?- authors(books) >> author(Who).
λ
|i authors(books) >> author(Who)
authors(books)
|e author(Who)
(Extensão)
authors(books)
|i author(Who)
(Entrada)
authors(books)
|i books >> wrote(Who, _)
(Redução)
books.authors(books)
|e wrote(Who, _)
(Extensão)
books.authors(books)
|i wrote(Who, _)
(Entrada)
books.authors(books)
|i true
(Redução)
sucesso [{Who/plato}]
Exemplo 3 - Predicado importado de parâmetro de unit
unit authors(Works).
visible author/1.
import wrote/2 from Works.
author(Person) :- wrote(Person, _).
?- authors(books) >> author(Who).
λ
|i authors(books) >> author(Who)
authors(books)
|e author(Who)
(Extensão)
authors(books)
|i author(Who)
(Entrada)
authors(books)
|i wrote(Who, _)
(Redução)
books
|e wrote(Who, _)
(Substituição)
books
|i wrote(Who, _)
(Entrada)
books
|i true
(Redução)
sucesso [{Who/plato}]
Exemplo 4 - Utilização do contexto histórico
unit authors.
visible author/1.
author(Person) :- <wrote(Person, _).
?- authors >> books >> (>author(Who)).
λ
|i authors >> books >> (>author(Who))
authors
|e books>> (>author(Who))
(Extensão)
books.authors
|e >author(Who)
(Extensão)
books.authors•books.authors |e author(Who)
(Salvaguarda)
authors•books.authors
|e author(Who)
(Descida)
authors•books.authors
|i author(Who)
(Entrada)
authors•books.authors
|i <wrote(Person, _)
(Redução)
books.authors
|e wrote(Person, _)
(Reposição)
books.authors
|i wrote(Person, _)
(Entrada)
books.authors
|i true
(Redução)
sucesso [{Who/plato}]
29
30
4
CxM - Máquina abstracta para CxLP
4.1. Introdução
A máquina abstracta que foi definida para suporte da linguagem CxLP recebeu o
nome de “Máquina Contextual”. No entanto ela será habitualmente referida pelo
acrónimo “CxM”. A CxM baseia-se na WAM2, que foi modificada com o objectivo de
suportar todos os mecanismos da linguagem CxLP. Para isso, foram adicionados
novos registos, novas estruturas de dados e novas instruções. Muitas das instruções
herdados da WAM foram igualmente alvo de adaptações, mais ou menos extensas. Na
introdução de todas estas alterações existiu um permanente cuidado em manter as
particularidades da WAM que fazem com que ela seja uma excelente implementação
do Prolog. Houve ainda a preocupação de organizar a nova máquina por forma a que a
sua maior complexidade não prejudicasse de forma significativa a velocidade de
execução de programas escritos em Prolog simples.
Como já dissemos, para além do desenvolvimento de uma implementação eficiente
de CxLP, neste trabalho considerámos o problema da definição de um sistema de
suporte flexível para a linguagem. O tratamento deste problema desceu ao nível da
máquina abstracta tendo sido introduzidos mecanismos na CxM com este fim. Eles
fazem parte da definição oficial da máquina abstracta, todavia, por razões de
organização, são descritos separadamente no capítulo 5.
2 Atendendo a que a publicação [Warren 83] é a referência principal, mesmo obrigatória, para a
WAM, a nomenclatura aí introduzida é seguida de perto, por forma a facilitar a tarefa do leitor
familiarizado com aquele trabalho. O único ponto em que divergimos um pouco, foi na não
consideração dos registos Ai por eles se identificarem com os registos Xi. Esta é uma questão
de pormenor.
4. CxM - Máquina abstracta para CxLP
31
Os mais importantes tópicos de discussão no âmbito da CxM são os seguintes:
política de estabelecimento de ligações entre nomes e definições de predicados, forma
de tratamento dos parâmetros das units, e representação e manipulação de contextos
simples e históricos. Começamos no entanto por dar algumas indicações sobre alguns
aspectos básicos da arquitectura da máquina: a representação dos termos e a
organização da memória.
4.2. Representação dos termos
O esquema da representação dos termos da CxM é, em termos gerais, idêntico ao da
WAM. Um termo é representado por uma palavra de 32 bits na qual se definem as
seguintes três componentes: o valor, que na maior parte dos casos é um endereço que
ocupa 26 bits; a tag, que é uma marca que associa um tipo ao termo, e que ocupa no
máximo 4 bits; e os bits de recolha de lixo que são 2 e se destinam a ser usados pelo
algoritmo de recuperação de memória (garbage collection) da CxM.
Os tipos de termos suportados pela CxM, incluindo os respectivos valores
associados, são os seguintes:
• Variável
O conteúdo de uma variável livre é uma referência para ela própria. O
conteúdo de uma variável instanciada é o valor que lhe está
atribuído.
• Átomo
Apontador para um descritor de átomo.
• Inteiro
Valor inteiro de 29 bits.
• Real
Valor real ocupando 29 bits.
• Estrutura
Apontador para o local da definição de um termo estruturado, o qual
consiste num functor e seus argumentos em células de memória
consecutivas.
• Lista
Apontador para o local da definição da lista, o qual contém os seus
dois argumentos (sem functor portanto). As
listas
têm
uma
representação distinta das outras estruturas, exclusivamente por
razões de eficiência.
Na CxM as tags têm um tamanho base de 4 bits, com a excepção das tags indicativas
de inteiro e real que têm apenas 3 bits para não afectar demasiado a precisão dos
valores numéricos. Da configuração das tags depende muito a eficiência da máquina.
No ponto 6.4 justifica-se a configuração usada na CxM, que é a seguinte:
Tags da CxM
Variável:
Lista:
Estrutura:
Átomo:
Inteiro:
Real:
0000............................
1001............................
1010............................
1011............................
110.............................
111.............................
4. CxM - Máquina abstracta para CxLP
32
4.3. Organização da memória
A organização da memória na CxM difere em alguns aspectos da existente na WAM.
Isto deve-se apenas a uma tentativa de aperfeiçoamento desta máquina, e não a
qualquer necessidade imperiosa relacionada com os contextos.
São 3 as principais áreas de dados da CxM: área de código, stacks e trail.
4.3.1. Área de código
Funciona de forma semelhante à área reservada para a criação de variáveis
dinâmicas das linguagens convencionais, sendo manipulada através das habituais
primitivas de reserva e libertação de memória. É nela que são armazenados os
descritores de átomo, functor, predicado e unit, assim como o código compilado dos
programas e os termos que correspondem à representação externa destes. Para
diminuir a fragmentação da memória, esta área encontra-se dividida em duas partes:
zona permanente e zona dinâmica. Na zona permanente são guardados os objectos que
não podem ser destruídos após criação, ou seja todos os descritores atrás referidos, e
ainda o código dos predicados de sistema. Na zona dinâmica são guardados o código e
os termos-fonte dos programas.
4.3.2. Stacks (heap + stack local)
Nesta zona de memória encontram-se as duas pilhas de execução da máquina: o
heap (ou stack global) e o stack local. O heap contém todos os termos estruturados
criados durante a execução dos programas. Por sua vez, o stack local contém
principalmente informação para controlo da execução dos programas e descrições de
contextos. Essa informação encontra-se organizada em quatro tipos de registo: registo
de activação, ponto de escolha, instância de unit e registo histórico.
As duas pilhas crescem em sentidos opostos, uma para a outra, de forma a que o
espaço livre é partilhado pelas duas. A situação de transbordo de uma pilha é
detectada através de um teste ao tamanho deste espaço livre efectuada em cada
chamada de predicado. Ele deverá ser sempre superior a um dado valor fixo, já que o
compilador garante que entre duas chamadas de predicado esse valor nunca é
excedido.
A zona de espaço livre entre as duas pilhas tem na CxM um aproveitamento muito
peculiar: é usada para colocar a pilha auxiliar usada no algoritmo de unificação geral.
Como será explicado mais tarde, esta opção oferece algumas vantagens em termos de
desempenho da máquina.
Segundo a definição original da WAM, cada uma das suas duas pilhas de execução
encontra-se numa zona distinta de memória, efectuando-se o seu crescimento no
sentido dos endereços crescentes. Esta disposição da memória destina-se a simplificar
a operação de ligação entre duas variáveis livres que, desta forma, envolve apenas
4. CxM - Máquina abstracta para CxLP
33
uma comparação de endereços e uma atribuição. No entanto, esta organização tem a
desvantagem de não tirar o melhor partido da utilização da memória, já que sempre
que o espaço atribuído a uma das pilhas se esgota, o espaço entretanto disponível na
outra não pode ser usado. Na CxM optámos por uma disposição diferente das pilhas
para
evitar
este
problema.
Entretanto
a
eficiência
da
máquina
não
fica
comprometida: não obstante ser necessário efectuar um teste suplementar quando da
ligação de duas variáveis livres, isso é compensado pela maior simplicidade do teste
que determina a necessidade de memorizar uma variável no trail quando ela é
instanciada.
4.3.3. Trail
Trata-se de uma simples pilha na qual, tal como na WAM, são anotados os
endereços de todas as variáveis que têm de ser tornadas livres quando ocorrer
retrocesso.
4.4. Ligações em CxLP
O principal factor que contribui para o poder da linguagem CxLP reside na grande
riqueza de formas de estabelecimento de ligações entre nomes e definições de
predicados. A principal característica de muitas dessas ligações é a de serem
determinadas pelo contexto corrente, que assim se revela como um ambiente de
ligação, segundo a nomenclatura tradicional das linguagens de programação.
Em CxLP existem quatro possibilidades diferentes de estabelecimento de ligações,
determinadas pelas circunstâncias particulares que rodeiam a utilização de cada
nome de predicado. Tendo em conta estas circunstâncias os nomes de predicado
podem ser classificados em quatro grupos:
•
Nomes definidos localmente.
•
Nomes dependentes do contexto.
•
Nomes ocorrendo em fórmulas de extensão.
•
Nomes importados.
Neste subcapítulo, cada um destes tipos de nome é alvo de uma análise individual,
sendo efectuado o estudo dos problemas envolvidos no estabelecimento de cada forma
de ligação. O objectivo é o da definição de mecanismos de ligação tão eficientes quanto
for possível. Esses mecanismos concretizam-se nas instruções de chamada da CxM às
quais será feita uma breve referência.
4.4.1. Ligação dos nomes definidos localmente
Em Prolog, as ligações de todos os nomes de predicado referidos no texto dos
programas, podem ser efectuadas em tempo de compilação, tendo portanto um
4. CxM - Máquina abstracta para CxLP
34
carácter estático. Em CxLP isso não pode ser feito em todos os casos. É no entanto
possível efectuar ligações deste tipo para os nomes de predicado que ocorrem com
maior frequência, que são aqueles para os quais existem definições locais na unit em
que são referidos.
A instrução da CxM gerada pelo compilador para efectuar a chamada de nomes
ligados estaticamente é a instrução Call. Só no caso dessa chamada surgir em último
lugar do corpo de uma cláusula é gerada a instrução Execute. Estas duas instruções na
CxM são idênticas às instruções homónimas da WAM.
4.4.2. Ligação dos nomes dependentes do contexto
Em CxLP a execução de um programa corresponde à prova de golos em relação a
contextos. Os pontos onde de forma mais directa a influência desses contextos se
manifesta na execução dos programas, são aqueles em que faz a derivação de golos
cujos functores principais correspondem a um nome dependente do contexto.
Recordemos que nestes casos a regra usada para estabelecer a ligação é a seguinte: a
definição de predicado associada a um nome dependente do contexto é a que se
encontra na instância de unit mais próxima do topo do contexto que inclui uma
definição visível para esse nome.
Esta regra sugere imediatamente uma forma de ligação completamente dinâmica,
estabelecida a cada invocação, por pesquisa no contexto corrente. Mas esta solução é
pouco eficiente, por causa do tempo dispendido nas buscas.
4.4.2.1. Cache
O tempo gasto nas pesquisas pode ser substancialmente reduzido através do uso de
uma cache em cada contexto, que sirva para registar as ligações dos nomes
dependentes do contexto à medida que vão sendo estabelecidas. A busca atrás referida
será assim efectuada apenas na primeira invocação de cada nome não sendo
necessário repeti-la em chamadas subsequentes. Entretanto este método tem como
pequena desvantagem o tempo dispendido a criar e inicializar a cache, operação esta
que se repete sempre que o contexto é estendido ou alterado por chamada de predicado
importado. No caso de um contexto ficar activo por pouco tempo, a intensidade do uso
da cache pode não ser suficientemente grande para compensar o tempo gasto na sua
criação. Apesar de tudo, em geral, os benefícios deste método superam largamente as
suas desvantagens, pelo que foi o escolhido para implementação.
É importante notar que, no método adoptado, a cache não é mantida quando o
contexto que lhe está associado deixa de ser necessário e é destruído. Por isso, quando
de um eventual regresso ao mesmo contexto, é necessário perder tempo a fazer a sua
reconstrução integral. Surge aqui naturalmente uma interrogação
possibilidade da memorização das caches mais
frequentemente
acerca
usadas
da
para
reutilização. Para isto ser feito, seria necessário resolver o problema fundamental de
4. CxM - Máquina abstracta para CxLP
35
encontrar um esquema associativo que permitisse reconhecer muito rapidamente
uma dada cache como sendo a correspondente a um dado contexto. Ora o facto de os
contextos serem identificados pela lista de nomes dos designadores de units
constituintes, torna este problema complexo, não tendo sido possível encontrar uma
solução suficientemente competitiva em termos de eficiência.
4.4.2.2. Estrutura da cache
Um aspecto muito importante das chamadas dependentes do contexto, e que tem de
ser considerado na definição da estrutura da cache, reside no facto de que após ter sido
encontrada a definição do predicado, este não dever ser executado no contexto da
invocação, mas sim no contexto que resulta deste por eliminação de todas as
instâncias de unit que se encontram acima daquela onde foi encontrada a definição
(cf. regras do derivação Saída e Descida). Isto significa que por cada nome dependente
de contexto que seja referido numa unit, é necessário reservar duas células da cache:
uma serve para memorizar uma referência para o predicado, e a outra o contexto no
qual esse predicado deve ser derivado. Entretanto, de acordo com o que será visto no
ponto 5.3.4, é ainda necessário considerar uma terceira célula, que é usada para
suporte da criação dinâmica de nomes dependentes do contexto.
A CxM tem uma instrução especializada para efectuar a chamada de predicados
dependentes do contexto, CtxDepJump, a qual têm dois argumentos: um functor que
corresponde ao nome invocado (para ser usado na pesquisa inicial) e um número
inteiro que indica a posição na cache associada a esse nome (para as chamadas
subsequentes).
4.4.3. Ligação dos nomes em fórmulas de extensão
Segundo a regra Extensão da definição operacional da linguagem CxLP, a prova de
um golo da forma U>>G resulta na prova do golo interno G, no contexto corrente
estendido pela unit U. Esta prova implica a descoberta no contexto estendido, da
definição de predicado visível com o mesmo nome que G que se encontre mais
próxima do topo do contexto. Ora o contexto corrente é desconhecido em tempo de
compilação. Torna-se portanto patente a ideia de que a ligação do nome do golo G terá
de ser fatalmente de natureza dinâmica.
No entanto existe um aspecto da utilização da linguagem que quando considerado,
permite num grande número de casos estabelecer formas de ligação mais eficientes. É
que regra geral, só existe interesse em usar um golo da forma U>>G quando o nome de
G é visível em U. Esta particularidade pode ser explorada de diversas formas
consoante os termos G e U sejam ou não variáveis.
Consideremos primeiro o caso de um golo u>>g, em que tanto g como u são termos
não variáveis. Se g for visível em u, é possível estabelecer em tempo de ligação, uma
ligação estática entre o nome g e a definição existente em u. Se pelo contrário, g não for
4. CxM - Máquina abstracta para CxLP
36
visível em u, então como só o topo do contexto corrente é conhecido em tempo de
ligação3, ela tem de ser estabelecida dinamicamente a cada invocação do golo de
extensão, por pesquisa no contexto corrente. No primeiro caso usa-se a instrução
CtxExtJump que tem como argumento um predicado, no segundo um instrução
chamada CtxExtJumpBelow que tem como argumento um functor.
Estudemos agora a fórmula U>>g, em que g é um termo não variável e U uma
variável. Este é um caso importante pois ocorre muito frequentemente em units
parametrizadas. Infelizmente o esquema de ligação, aqui também, parece ter de ser
dinâmico, visto que o valor de U só poder ser conhecido em tempo de execução, e poder
variar de forma imprevisível. No entanto como na maior parte destes casos o nome de
g será visível em U, não é de esperar que a demora no estabelecimento da ligação seja
muito grande. De facto, em todos esses casos, o predicado correspondente é logo
encontrado na unit corrente.
Apesar de tudo, como está aqui envolvida uma pesquisa dentro da unit corrente,
torna-se conveniente introduzir uma pequena optimização, que se baseia no facto que
a probabilidade de U representar a mesma unit em duas invocações sucessivas do golo
ser bastante grande (especialmente se U for um parâmetro de uma unit). A optimização
consiste na utilização de uma pequena cache na qual se memoriza o par <unit U,
definição de predicado para g> da última chamada. É assim possível numa chamada
subsequente testar se o valor da variável U não mudou, e neste caso usar a referência
do predicado previamente guardada. Esta optimização é especialmente importante no
caso em que o golo de extensão aparece num predicado recursivo em que U não varia.
A instrução da CxM que é usada para efectuar a chamada de um nome nestas
circunstâncias é a instrução VarCtxExtCall, a qual tem como argumentos o functor
correspondente ao nome invocado e o endereço de um par de palavras de memória que
são usadas como cache.
Restam para estudar os casos U>>G e u>>G em que G e U são variáveis. Aqui
optámos por gerar sempre chamadas do meta-predicado call/1, o que corresponde a
tratar a ligação de forma completamente dinâmica. Repare-se que teria sido possível
usar uma cache semelhante à do caso analisado no parágrafo anterior. Mas a
circunstância da inferior probabilidade de repetição do par <unit, predicado> parecem
não a justificar em geral. Não será no entanto de excluir a sua utilização em algumas
situações particulares (por exemplo no predicado bagof), só possíveis de detectar
através do uso de um compilador-optimizador que efectue análise global de
programas.
3Não pode ser em tempo de compilação pois estamos a assumir compilação separada, e
normalmente a chamada u>>g é feita do exterior de u.
4. CxM - Máquina abstracta para CxLP
37
4.4.4. Ligação dos nomes importados
A invocação de um golo g importado de uma unit U, conduz à prova de g no contexto
que resulta de substituir o topo do contexto corrente, pela instância de unit
correspondente ao termo U (cf. regra Substituição). Isso passa, como de costume, pela
descoberta no novo contexto, da definição de predicado visível com o mesmo nome,
que se encontra mais próxima do topo.
Apesar de ser aqui aparente, ainda mais uma vez, a necessidade de estabelecer a
ligação dinamicamente, acontece que circunstâncias idênticas às que permitiram
efectuar optimizações no caso das fórmulas de extensão, se repetem neste caso.
Concretamente verifica-se que se um predicado g é importado de uma unit U, então a
situação normal é aquela em que g está declarado como visível em U. Se isso se
verificar, e caso U não seja uma variável, é possível estabelecer uma ligação estática
para g, em tempo de ligação usando a instrução Call ou Execute. Se g não for visível
então é necessário usar a instrução ImportJumpBelow que tem características
dinâmicas.
No caso em que U é uma variável (trata-se neste caso necessariamente de um
parâmetro de unit), pode ser usado um método semelhante ao que foi utilizado no golo
U>>g, o qual, recorde-se, envolvia o uso de uma pequena cache para evitar o repetido
restabelecimento da ligação. Neste caso é gerada a instrução VarImportCall que tem os
mesmos argumentos que a instruçãoVarCtxExtCall: o functor correspondente ao
nome invocado e o endereço da cache de duas palavras.
Estes dois casos esgotam todas as possibilidades da importação de nomes.
4.5. Parâmetros das units
A quantificação implícita dos parâmetros de uma unit é diferente da quantificação
implícita das variáveis normais de uma cláusula, pois abrange toda a unit. Isto
significa que os mecanismos existentes na WAM para suporte de variáveis não são
adequados para os implementar. Se insistíssemos muito em usar apenas esses
mecanismos, teríamos de fazer o compilador adicionar a cada predicado pertencente a
uma unit parametrizada, novos argumentos invisíveis, tantos quantos os parâmetros
da unit, como forma de manutenção dos seus valores no âmbito de toda a unit. Este
método é pouco conveniente, tanto em termos de ocupação de memória, como em
termos de velocidade de execução.
O método usado na CxM passa pela introdução de variáveis de um novo tipo, que em
vez de residirem nos registos de activação dos predicados (como as variáveis Y) ou nos
registos da máquina abstracta (como as variáveis X), antes se encontram nas
instâncias de unit que compõem o contexto. A introdução destas novas variáveis, a
que chamaremos “variáveis Z”, obriga à introdução de diversas instruções novas na
4. CxM - Máquina abstracta para CxLP
38
máquina abstracta para lidar com elas. Felizmente as novas instruções são em
número inferior às instruções já existentes para tratamento das variáveis normais.
Isto deve-se ao facto de não serem admitidas estruturas ou constantes como
parâmetros formais das units, ao contrário do que se passa com os argumentos das
cláusulas onde, como se sabe, não há qualquer restrição. Tomando como referência a
WAM, o conjunto de instruções das classes Put e Unify tem de ser ampliado, não sendo
no entanto necessárias novas instruções do tipo Get.
A inicialização dos parâmetros de uma unit é feita no momento da criação das suas
instâncias, com base nos valores dos argumentos actuais que são passados em registos
X.
4.6. Implementação dos contextos
4.6.1. Representação dos contextos
Cada contexto na CxM é representado em memória por uma pilha de objectos
chamados instâncias de unit. Durante a execução dos programas os contextos vão
sendo alterados por adição ou remoção destes objectos.
A disciplina que rege o comportamento dos contextos sugere que a zona de memória
adequada ao seu armazenamento seja o stack local. Com efeito uma das principais
característica do stack local é o facto de ser utilizado para guardar entidades que têm
um certo carácter temporário, sendo esta uma das propriedades das instâncias de unit.
Para provar o carácter volátil destes objectos observe-se que, por exemplo na execução
duma fórmula de extensão u>>g, a instância de unit que é empilhada para a derivação
de g, deixa de ser necessária logo que g tenha sido resolvido deterministicamente ou
falhado. Este comportamento é em tudo idêntico ao dos registos de activação dos
predicados que também são desempilhados naquelas duas circunstâncias.
Os campos que constituem as instâncias de unit são os seguintes:
•U
Apontador para o descritor da unit associada.
•C
Apontador para a instância da unit anterior no mesmo contexto. Este
campo é usado nas buscas que são efectuadas para estabelecimento de
ligações dos nomes dependentes do contexto, e ainda para repor o contexto
no caso das fórmulas de extensão.
•S
Apontador para o topo do contexto anterior à criação desta instância de
unit. É usado apenas no caso particular em que a mudança de contexto é
provocada pela chamada de um predicado importado com o objectivo de
repor o contexto.
• Zi
Os parâmetros da unit. São inicializados a partir dos registos X onde se
encontram os parâmetros actuais da unit.
4. CxM - Máquina abstracta para CxLP
•N
39
Número de nomes dependentes do contexto existentes na unit no momento
da criação desta instância de unit. No fundo indica a dimensão da cache de
nomes dependentes do contexto.
• Ci
Células da cache. Cada nome dependente do contexto da unit tem
associado um índice nesta cache. As células da cache são inicializadas
com
um
valor
(nil)
que
convencionalmente
estabelecida. Posteriormente, sempre
que
a
indica
ligação
ligação
de
um
não
nome
dependente do contexto é estabelecida, fica aqui memorizada para
posterior reutilização. Quando a ligação não pode ser estabelecida por
inexistência de definição aplicável, é usado o endereço da instrução Fail.
A existência do campo N só se justifica se for permitido efectuar em tempo de
execução a adição de novas clausulas à unit, através do uso do predicado de sistema
assert/1 ou suas variantes. Nesse caso torna-se possível a criação dinâmica de nomes
dependentes do contexto para os quais não foi previsto espaço na cache quando ela foi
criada. Assim o campo N serve para detectar referências a índices de células da cache
que excedem os limites desta, caso em que a ligação do nome ao predicado tem de ser
feita dinamicamente a cada invocação. Entretanto, note-se que depois de terem sido
adicionados novos nomes a uma unit, as novas instâncias de unit a serem criadas
futuramente, já terão caches com o tamanho adequado.
4.6.2. Registos para suporte dos contextos
Todos os registos da WAM (P, CP, E, B, H, HB, TR, S, Xi ) mantêm-se na CxM, tendo
sido criados alguns novos para lidar com os contextos.
O registo que indica o contexto corrente chama-se “C” . Contêm em cada momento
uma referência para a instância de unit que se encontra no topo do contexto corrente.
O seu valor pode ser modificado em quatro circunstâncias diferentes das formas que
se a seguir se apresentam:
• Extensão de contexto - O contexto é simplesmente ampliado com uma nova
instância de unit, para a qual C fica a apontar.
• Invocação de predicado importado - A instância de unit que se encontra no topo do
contexto corrente é substituída logicamente por outra instância da unit, para
a qual fica o registo C fica a apontar. Esta substituição é implementada
através da adição ao contexto corrente de uma nova instância de unit, cujo
campo C fica a referir o segundo elemento a contar do topo do contexto em que
foi feita a invocação do predicado importado.
• Invocação de predicado dependente de contexto - O registo C passa a indicar mais
abaixo no contexto corrente, a instância de unit na qual foi encontrada a
definição do predicado. Desta forma o tamanho do contexto corrente é
reduzido.
4. CxM - Máquina abstracta para CxLP
40
• Retrocesso - É reposto o valor de C, que se encontra memorizado no último ponto
de escolha.
Uma mudança do contexto é sempre temporária, mantendo-se apenas durante a
derivação de um golo. Terminada a derivação é sempre necessário repor o contexto,
fazendo o registo C retomar um valor anterior. Nos casos de extensão de contexto e de
chamada
de
predicado
importado,
isso
faz-se
de
forma
simples
usando
respectivamente os campos C e S da instância de unit corrente, que é desempilhada.
O caso da invocação de um predicado dependente de contexto, é bastante mais
complicado de tratar, exigindo a introdução de um novo registo na CxM - o registo
“CC” (context continuation). Este funciona de forma algo semelhante à do registo CP
(continuation pointer) da WAM. No momento em que é feita a chamada do nome
dependente de contexto, o valor corrente de C é copiado para CC sendo o seu valor
preservado nos registos de activação de todos os predicados entretanto invocados.
Finalmente, na execução da instrução Proceed (que faz o retorno do predicado) C
recebe o valor de CC sendo reposto o contexto inicial.
Mas existe ainda outro problema que a invocação de predicados dependentes do
contexto coloca. É que apesar da chamada destes predicados implicar a redução de
tamanho do contexto corrente, todas as instâncias de unit que se encontram acima do
seu novo topo têm de ser preservadas por forma que o contexto antigo possa ser
reposto mais tarde. A solução mais intuitiva para este problema consistiria na
introdução de mais um registo na máquina chamado por exemplo CT (topo do
contexto) que conjuntamente com os registos E e B, ajudaria a determinar o limite
superior da parte a preservar no stack local. No entanto esta solução envolveria duas
percas de eficiência com alguma relevância: em primeiro lugar, a operação de
determinação do topo do stack local ficaria menos eficiente pois passaria a
corresponder à determinação do mínimo entre três valores; em segundo lugar, o uso de
três registos na gestão dos contextos aumentaria demasiado o tamanho dos pontos de
escolha, pelo que as operações de salvaguarda e reposição do estado da máquina se
tornariam mais pesadas. Foi felizmente possível encontrar uma solução que usa
apenas os registos C e CC associados aos contextos, e que mantêm a eficiência da
determinação do topo do stack local da WAM. Passa pela utilização de um novo
registo, chamado L (de local), que vai conter em cada momento o máximo entre o valor
do registo B e o valor do hipotético registo CT, que foi atrás referido. Adaptando
cuidadosamente as instruções da CxM ao seu uso, consegue-se manter plenamente a
eficiência da máquina e ainda evitar a necessidade de guardar o registo L nos pontos
de escolha. Apenas as instruções que implementam a operação cut ficam um pouco
menos eficientes, pois passa a ser necessário fazer explicitamente a recuperação de
espaço no stack local modificando o valor de L. Essa recuperação, na WAM, é feita de
forma indirecta, por alteração do valor do registo B.
4. CxM - Máquina abstracta para CxLP
41
Um aspecto curioso, que resulta das alterações sofridas pelos contextos quando da
chamada de predicados dependentes do contexto, é o facto de o conjunto de contextos
formar uma estrutura de dados bem conhecida: um cacto. O mesmo se passa com os
contextos históricos. Entretanto como essa estrutura já aparecia na WAM, na
organização dos registos de activação em virtude do não-determinismo do Prolog,
podemos observar que em CxLP surgem três tipos distintos de cactos que se
entrelaçam de forma complexa.
4.6.3. Instruções para controlo dos contextos
Existem seis instruções na CxM que permitem fazer o controlo directo do contexto
corrente; três delas são geradas durante a compilação de fórmulas de extensão e as
restantes na compilação de invocações de nomes importados.
A instrução PushContext é usada nas fórmulas de extensão u>>g, em todos os casos
em que u não é uma variável. Ela faz a extensão do contexto corrente, o que
corresponde a empilhar uma nova instância de unit, fazer a sua inicialização e pôr o
registo C a apontar para ela. Os argumentos actuais do designador de unit vêm nos
registos X da CxM. Ao contrário do que se passa com as chamadas de predicados, não é
obrigatório que primeiros registos (X0,X1,.…) sejam usados. Esta opção destina-se a
possibilitar a manutenção das optimizações efectuadas pelo compilador no uso dos
registos, aumentando a eficiência das fórmulas de extensão (cf. 7.5).
O código gerado pelo compilador para os golos de extensão termina sempre com a
instrução
PopContext.
Esta
instrução
testa
se
o
golo
foi
resolvido
deterministicamente, o que pode ser feito facilmente verificando se C é igual a L4; em
caso afirmativo, o espaço ocupado pela instância de unit que se encontra no topo é
libertado fazendo-se L receber o valor antigo de C que se encontra guardado na própria
instância da unit. Finalmente C recebe também esse valor, o que corresponde à
reposição do contexto.
Vejamos um exemplo de utilização destas duas instruções. O código que o
compilador gera para a clausula:
a(X,Y,Z) :- u(Z)>>g(X,Y)
é o seguinte (admitindo que g/2 é visível em u e que portanto foi possível estabelecer
uma ligação estática):
PushContext u 2 0
Call g/2<u>
PopContext
Proceed
Na instrução PushContext, o primeiro argumento é uma referência para a unit
usada; o segundo indica qual o índice do primeiro elemento do grupo de registos usado
4Se existisse um ponto de escolha por cima do topo do contexto corrente, então L estaria a
apontar para ele.
4. CxM - Máquina abstracta para CxLP
42
para passar os argumentos da unit; o terceiro indica o número de variáveis
permanentes da cláusula, que estão activas no ponto de invocação da fórmula de
extensão, e serve para a determinação do topo do stack local, para ser empilhada a
nova instância de unit.
Além das duas instruções referidas, existe ainda uma terceira que é usada nos casos
em que o primeiro argumento da fórmula de extensão é uma variável. Trata-se da
instrução PushVarContext que cria e inicia uma instância da unit com base num
designador de unit que é passado num registo X. Como a unit é variável, esta instrução
é sempre usada em associação com a instrução VarCtxExtCall ou com a chamada do
predicado de sistema call/1.
As três instruções de manipulação do contexto usadas na compilação de predicados
importados, têm um comportamento análogo ao das instruções relacionadas com as
fórmulas de extensão. Os nomes delas são SwitchContextOn, SwitchVarContextOn e
SwitchContextOff. As duas primeiras efectuam a substituição da instância unit que se
encontra no topo do contexto, aplicando-se a primeira ao caso em que a importação é
feita de um designador de unit e a segunda ao caso em que a importação é feita de um
parâmetro de unit. A instrução SwitchContextOff, é executada depois do predicado
importado retornar, repondo o contexto que existia anteriormente.
4.6.4. Fórmulas de libertação de contexto e a unit []
A unit [] (nil) é uma unit pré-definida que intervém de uma forma muito especial na
definição dos contextos simples, encontrando-se na base de todos eles. É nela que
terminam todas as buscas de definições de predicados dependentes do contexto que
não tenham sucesso.
A introdução desta unit destina-se fundamentalmente a apoiar o mecanismo de
implementação das fórmulas de libertação de contexto. Com efeito a fórmula ?G pode
definir-se por recurso à unit [] da seguinte forma:
?G :- []>>G.
Desde que a unit [] não contenha qualquer definição de predicado, a sua presença na
base de todos os contextos pode ser ignorada de um ponto de vista lógico. Por exemplo,
o contexto lógico [books,
authors(books)] é internamente é representado pela
sequência de units [books, authors(books), []], mas este facto pode ser geralmente
ignorado pelo utilizador do sistema se a unit [] estiver vazia. Parece assim ser
conveniente a proibição da adição de definições de predicados na unit [].
No entanto houve um motivo forte, de natureza prática, que nos conduziu à não
imposição de qualquer restrição à utilização da unit []. Trata-se da possibilidade da
sua utilização como zona de dados globais do sistema, que resulta de ela pertencer
simultaneamente a todos os contextos (mesmo ao contexto logicamente vazio). Entre
outras vantagens, o sistema torna-se mais facilmente usável para desenvolver e
4. CxM - Máquina abstracta para CxLP
43
correr programas escritos em Prolog (estes correm no contexto logicamente vazio ao
qual corresponde a unit corrente []), e simplifica-se também o processo de tradução
progressiva de programas Prolog para CxLP. É no entanto importante notar que
quando a unit [] é usada desta forma, a sua presença nos contextos já não pode ser
ignorada do ponto de vista lógico.
4.7. Implementação do contexto histórico
4.7.1. Representação do contexto histórico e registos associados
Um contexto histórico é representado por uma pilha de objectos denominados
registos históricos. A única função um registo histórico é a de memorizar o contexto
corrente para posterior reposição. Na memorização de um contexto basta considerar
simplesmente a referência para o seu topo.
A experiência já obtida no estudo dos contextos simples conduz-nos rapidamente a
um primeiro esquema (tentativo) de representação e gestão dos contextos históricos.
Um registo histórico deverá assim ser constituído por dois campos: um apontador
destinado à memorização do topo de um contexto simples e um apontador para o
registo histórico seguinte dentro do contexto histórico. Os novos registos da máquina
serão dois: C2 que aponta para o topo do registo histórico corrente e CC2 que
memoriza o valor de C2, para posterior reposição, sempre que o contexto histórico é
ampliado (por utilização do operador >) ou reduzido (por utilização do o operador <).
Entretanto o registo L passará a conter sempre o valor mínimo entre o registo B e dois
registos hipotéticos CT e CT2.
Apesar de este método ser já bastante razoável, da sua análise resulta a conclusão
da conveniência de eliminar o registo CC2. É que, apesar da importância das
facilidades oferecidas pelo contexto histórico, elas não precisam de ser usadas com
muita frequência na prática. E a eventual utilização de um registo CC2 afectaria um
pouco a eficiência geral da CxM, mesmo nos casos em que o contexto histórico não
estivesse a ser usado. Como se poderá observar, na descrição do método modificado
que adoptámos, é realmente possível dispensar o registo CC2, desde que estejamos
dispostos a aceitar, na utilização dos mecanismos de salvaguarda e reposição de
contexto, uma pequena perda de eficiência e um dispêndio ligeiramente maior de
memória.
Uma das particularidades do método que usamos, é o facto de pilha que representa
o contexto histórico crescer, tanto quando se faz uma salvaguarda de contexto, como
quando se faz uma reposição de contexto. Isto significa que no novo modelo, é menos
directa a relação entre o contexto histórico conceptual e a estrutura de dados que o
representa. Nas salvaguardas de contexto, o crescimento do contexto histórico tem,
como no modelo anterior, o fim de memorizar o contexto corrente para reposição
4. CxM - Máquina abstracta para CxLP
44
futura. No caso de reposição de contexto, o objectivo da ampliação do contexto
histórico é duplo: em primeiro lugar, serve para memorizar o contexto corrente, para
preparar a futura anulação da reposição de contexto que, como se sabe, é válida apenas
durante a derivação de um golo (este era o papel desempenhado pelo registo CC2); em
segundo lugar, destina-se a guardar uma referência para o registo histórico a usar caso
seja feita nova reposição de contexto (esta acção representa uma simulação da redução
de tamanho do contexto histórico conceptual: a referência indicada corresponde ao
seu novo topo).
Note-se bem que nesta implementação do contexto histórico, nem sempre o registo
que se encontra no seu topo, contém o contexto a ser usado na próxima operação de
reposição. O registo do topo contêm sim um apontador, R2, que referencia o registo
histórico no qual se encontra o contexto a ser a ser usado na próxima operação de
reposição.
Cada registo histórico é assim constituído pelos seguintes três campos:
•C
Referência para o contexto memorizado.
• C2
Apontador para o registo histórico anterior dentro do contexto histórico.
• R2
Referencia para o registo histórico que contém o contexto a ser reposto em
caso de utilização do operador <. Note-se que é possível a auto-referência
caso em que os topos do contexto histórico lógico e do contexto histórico
implementacional coincidem.
4.7.2. Instruções para controlo do contexto histórico
A CxM tem quatro instruções para manutenção do contexto histórico.
O código gerado para a clausula:
c :- >g.
onde é feita uma salvaguarda de contexto, é o seguinte:
PushHistoricalContext 0
Call g/0
PopHistoricalContext
Proceed
A instrução PushHistoricalContext empilha no contexto histórico um registo novo
no qual são guardados o contexto corrente C, o contexto histórico anterior C2 e uma
auto-referência. Desta forma o golo g é derivado já com o contexto corrente
memorizado. A instrução PopHistoricalContext repõe o valor de C2 e liberta ainda o
espaço ocupado pelo topo do contexto histórico caso este tenha sido resolvido
deterministicamente.
O argumento da instrução PushHistoricalContext indica o número de variáveis
permanentes activas na cláusula, no ponto de invocação da fórmula de extensão,
4. CxM - Máquina abstracta para CxLP
45
sendo usado apenas para determinar o topo do stack local, no momento de ser
empilhado o novo registo histórico.
No caso de uma clausula contendo uma operação de reposição de contexto, como no
exemplo:
c :- <g.
o código gerado é o seguinte:
EnterHistoricalContext 0
Call g/0
ExitHistoricalContext
Proceed
A função principal da instrução EnterHistoricalContext é a de repor o contexto que
se encontra no topo do contexto histórico lógico. Mas antes disso ser feito é empilhado
um registo histórico no qual se guarda o contexto corrente C, o valor de C2 e ainda, o
campo R2 do novo topo do contexto histórico lógico (R2 recebe portanto uma
referência para o segundo elemento, contando a partir do topo, do contexto histórico
conceptual que, desta forma, é reduzido).
A instrução ExitHistoricalContext repõe o valor de C e C2, e liberta ainda o espaço
ocupado
pelo
topo
do
contexto
histórico
caso
g
tenha
sido
resolvido
deterministicamente.
4.8. As outras estruturas de dados do stack local
O stack local além de instâncias de unit e registos históricos contém outros dois
tipos de registos herdados da WAM: registos de activação (environments) e pontos de
escolha (choice points). Na CxM estas estruturas de dados mantêm todos os seus
campos tendo sido adicionados alguns novos.
4.8.1. Registos de activação
Os registos de activação na CxM são ampliados com um novo campo, que é usado
para guardar o registo CC. O novo formato é portanto a seguinte:
• CE
Serve para memorizar o valor que do registo E anterior à criação do
registo.
• CP
Salvaguarda o registo CP, pois o seu conteúdo pode ser destruído pela
execução da cláusula associada a este registo de activação.
• CC
Salvaguarda o registo CC, pelas mesmas razões.
• Yi
Variáveis permanentes da clausula associada a este registo de activação.
4.8.2. Pontos de escolha
A CxM tem mais quatro registos que a WAM: C, CC, C2 e L. Destes registos o único
que não precisa de ser salvaguardado nos pontos de escolha é o registo L. Daqui resulta
que o formato dos pontos de escolha da CxM é o seguinte:
4. CxM - Máquina abstracta para CxLP
46
• E, CP, B, TR, H, C, CC, C2
Servem para memorizar os valores dos registos com o mesmo nome.
•P
Endereço do código da próxima cláusula a tentar.
• Ai
Servem para salvaguardar os valores dos argumentos actuais da chamada
do predicado não determinista que provocou a criação deste ponto de
escolha.
4.9. A C-WAM
Existe pelo menos um exemplo de definição de uma máquina abstracta para uma
variante da linguagem CxLP, que é anterior a este trabalho. Trata-se da máquina
C-WAM que se encontra
descrita
na
referência
[Lamma 89].
A
linguagem
implementada suporta a partição de programas em units e a utilização de contextos
como em CxLP. Existem ainda outros mecanismos, de entre os quais se destaca um que
é designado como lazy binding e que suporta uma metodologia de programação
orientada
por
objectos. Não fazem
no
entanto
parte
da
linguagem
units
parametrizadas, nomes de predicado importados e contextos históricos.
Algumas das ideias
da
CxM
foram
directamente
inspiradas
na
C-WAM,
nomeadamente a forma de representação os contextos simples e o mecanismo de
chamada de predicados dependentes do contexto. No entanto, ao nível da realização,
elas foram por nós melhor integradas na filosofia geral da WAM, tendo resultando
numa implementação mais elegante e eficiente.
47
5
Mecanismos de ligação
incremental da CxM
5.1. Introdução
Desde o início deste projecto, que atribuímos muita importância, ao problema da
integração da implementação da nossa linguagem, como componente básica, do seu
ambiente de programação. Esta ideia fundamenta-se no princípio conhecido de que
grande parte das exigências de flexibilidade e velocidade de resposta de um ambiente
de desenvolvimento de programas, terem geralmente de ser tratadas ao nível da
própria implementação da linguagem. Esta preocupação teve um peso considerável no
desenho de todo o sistema de suporte da linguagem, com particular destaque para a
máquina abstracta.
A nossa principal preocupação em termos de ambiente de programação foi a de
evitar, desde logo, a tradicional visão dos programas como produtos acabados que
precisam apenas de ser compilados antes de serem executados. Pretendemos, pelo
contrário, aderir à perspectiva oposta segundo a qual os programas são entidades em
vias de desenvolvimento, portanto geralmente num estado incompleto e mutável. Esta
visão é importante quando consideramos, por exemplo, os processos de depuração e
teste dos programas. Mas ganha especial relevância quando lidamos com os
programas sofisticados e de grande porte, que são correntes na área da Inteligência
Artificial. Nesta situação não é geralmente possível fazer a especificação prévia
completa dos programas, pelo que o seu desenvolvimento acaba por constituir um
verdadeiro processo experimental.
5. Mecanismos de ligação incremental da CxM
48
Torna-se assim fundamental a possibilidade de criar e executar fragmentos de
programa de forma simples e expedita, reduzindo ao mínimo a duração do ciclo
edição-compilação-ligação-teste. Do ponto de vista da escolha da técnica usada para
implementar a linguagem de programação é um facto reconhecido que o uso de um
interpretador favorece esta filosofia, sendo este método adoptado por exemplo nos
ambientes das linguagens Interlisp [Teitelman 81], Cedar [Teitelman 84] e também
nos sistemas Prolog tradicionais. Mas esta técnica penaliza consideravelmente a
velocidade de execução dos programas, pelo que muitas vezes é preciso recorrer a um
compilador para produzir a versão final executável dos programas. Entretanto
existem alguns exemplos de compatibilização da flexibilidade de utilização de uma
linguagem com o uso de compilação: Smalltalk [Goldberg 83], e na área de
programação em lógica, o Prolog da universidade de Syracuse [Bowen 86].
As características modulares de uma linguagem aumentam também as exigências
colocadas ao seu ambiente de programação. A análise deste caso interessa-nos visto
na linguagem CxLP, a noção de módulo (unit) desempenhar um papel basilar.
Classicamente,
a
modularidade
das
linguagens está
associada
aos
ubíquos
mecanismos de compilação separada e de ligação (na área da programação em lógica
um dos mais conhecidos sistemas deste tipo chama-se MProlog [Bendl 80]). Esta fase
de ligação dos módulos, além de contribuir para a impaciência do programador,
muitas vezes impõe-lhe restrições drásticas, pois muitos sistemas obrigam a que
todos os predicados invocados no programa estejam definidos na altura da ligação,
mesmo que a chamada desses predicados nunca se chegue a concretizar! Este é um
problema que também exige
atenção
e
que
não
ocorre,
por
exemplo,
nos
interpretadores visto aí as ligações serem feitas dinamicamente a cada invocação de
predicado.
5.2. O sistema de suporte de CxLP
Tendo presente as considerações do ponto anterior, foi sendo desenvolvido em
simultâneo e de forma integrada com a implementação da linguagem, um sistema
para suporte de CxLP, que pretende ser o núcleo a partir do qual um ambiente de
programação com qualidade possa crescer. A característica mais assinalável deste
sistema consiste na completa fusão entre os ambientes de compilação, ligação e
execução de programas. O programa em desenvolvimento geralmente encontra-se em
memória pronto a ser executado, e todas as alterações que lhe vão sendo introduzidas
pelo programador, são assimiladas de forma rápida e automática no estado interno do
sistema. Isso foi conseguido através do estabelecimento de uma coordenação estreita
entre o compilador de CxLP, a máquina abstracta CxM e o módulo de gestão da base de
dados do sistema.
5. Mecanismos de ligação incremental da CxM
49
Do lado da máquina abstracta, foram criados mecanismos de ligação incremental,
que permitem que todas as ligações possam ser estabelecidas em tempo de execução à
medida que os predicados vão sendo invocados.
Por sua vez, a base de dados do sistema admite ser alterada em qualquer ocasião,
através da utilização de diversos predicados de sistema definidos para o efeito5 . Essas
alterações incluem: adição de clausulas (assert/1), eliminação de cláusulas (retract/1),
eliminação de um nome de predicado (abolish/2), alteração do estado de visibilidade
de um predicado (visible/2, novisible/2), declaração de importação e sua anulação
(import/3, noimport/2). Num sistema convencional qualquer destas alterações
obrigaria à recompilação integral de todas as units afectadas. No nosso sistema
qualquer uma destas mudanças apenas provoca a anulação das ligações que ficam
inválidas, que serão mais tarde restabelecidas em execução.
A compilação é feita incrementalmente, cláusula a cláusula, através do predicado
de sistema assert/1. Note-se que devido ao dinamismo do sistema, durante a
compilação de chamadas de nomes de predicados, não chega sequer a ter significado a
simples ideia do compilador determinar o tipo de ligação a ser estabelecida, já que
esta pode variar ao longo do tempo. Veja-se, por exemplo, o caso da cláusula “a:-b.”: ao
nome “b/0”, dependendo de circunstâncias que podem ir mudando com o tempo, pode
corresponder um nome local, um nome importado ou um nome dependente do
contexto. Já que a informação indicativa do tipo de ligação a estabelecer não pode
ficar no código gerado, é guardada nos descritores de nomes de predicado da base da
dados, para ser usada no momento em que a ligação for estabelecida.
A configuração deste sistema parece responder às necessidades enunciadas no
ponto anterior. É interessante observar que no fundo ele consegue conciliar toda a
flexibilidade do uso de um interpretador com o desempenho de um compilador.
Outra vantagem que ele proporciona, e que não é negligível, é a possibilidade dos
programas escritos em CxLP poderem manipular com facilidade outros programas
escritos na mesma linguagem e já carregados no sistema. Isto permite que o ambiente
de programação possa ser desenvolvido, e posteriormente crescer por adição de novas
ferramentas, usando a própria linguagem.
A flexibilidade do sistema de suporte reside decisivamente na forma como nele são
tratadas as ligações de nomes de predicados. Este é o assunto cuja análise detalhada
ocupa a parte restante deste capítulo.
5 Em geral estes predicados não são chamados directamente pelo utilizador, mas sim pelo
ambiente de programação em resposta a alguma solicitação de alto nível por parte do
utilizador, ou ainda de forma automática durante a edição do programa por exemplo.
5. Mecanismos de ligação incremental da CxM
50
5.3. Manutenção das ligações na CxM
5.3.1. Descritores de nome de predicado
De entre os vários tipos de registos existentes na base de dados do sistema de
suporte - descritores de átomo, de functor, de unit, de cláusula e de nome de predicado estes últimos são os que naturalmente se encontram no centro do processo de
estabelecimento de ligações incrementais da CxM. Para cada nome de predicado que
seja referido numa unit, existe um destes descritores.
A lista completa dos campos constituintes de um descritor de nome de predicado é a
seguinte:
• PredCode
Contém uma referência para o código, a executar quando o nome
de predicado for invocado.
• Inst
Quando usado, contém uma instrução da CxM.
• Pred
Apontador para um descritor de nome predicado. Com excepção
dos nomes que ocorrem em fórmulas de extensão, trata-se de uma
auto-referência.
• Functor
O functor que indica o nome do predicado.
• Unit
Unit à qual pertence este descritor.
• Clauses
Lista das cláusulas que constituem a definição de um nome
definido localmente. Os descritores dos outros tipos de nomes de
predicados têm zero cláusulas associadas.
• CtxDepOffset
Deslocamento na cache de um predicado dependente do contexto.
• ImportTerm
Termo que descreve a unit de onde o nome deste descritor é
importado. Se existir alguma referência a parâmetros de unit
nesse termo, eles são representados por termos da forma
$_unit_parameter(N) em que N indica a ordem do parâmetro
referido.
• ExtUnit
Num nome interveniente numa fórmula de extensão, representa a
unit que provoca essa extensão.
• IdxHConst
• IdxHStruct
• BindType
Usados para guardar apontadores para as tabelas de hash que
podem ser geradas durante a criação do índice de um predicado
associado a um nome definido localmente.
Campo de um tipo enumerado, que indica o tipo de ligação que foi
estabelecida no descritor. Os valores possíveis são: noBind,
indexBind, importBind, otherBinds.
5. Mecanismos de ligação incremental da CxM
51
• IsVisible, IsImported, IsBuiltin, IsPermanent,
• IsStatic, CCoded, KeepSource, NoIndex
Atributos booleanos do nome de predicado.
Como se pode observar os descritores de nome de predicado contêm campos em
número suficiente para possibilitarem a representação qualquer um dos quatro tipos
de nomes existentes em CxLP:
• Para um nome definido localmente, existe a lista de clausulas que define o seu
predicado associado;
• Para um nome importado, a descrição de unit que aparece na sua declaração de
importação;
• Para um nome dependente do contexto, o seu deslocamento dentro das caches
das instâncias da unit a que pertence;
• Para um nome que ocorra numa fórmulas de extensão, a referência para a unit
que determina a extensão do contexto.
O primeiro campo de cada descritor - PredCode -, que serve para guardar o endereço
do código a executar quando o respectivo nome for invocado, geralmente aponta para
o início de um segmento de código constituído por sequência de instruções. Mas como
se verá adiante, existem algumas situações em que pretendemos que ele refira apenas
uma instrução isolada cujos argumentos são atributos do próprio descritor. Nesses
casos, a instrução é colocada no segundo campo do descritor - Inst - de forma a que os
campos que se lhe seguem sejam vistos, do ponto de vista da execução da instrução,
como os seus argumentos.
Todas as invocações de nomes predicados são efectuadas através do respectivo
descritor, para que seja possível o estabelecimento e anulação dinâmica de ligações
usando a indirecção proporcionada pelo campo PredCode.
5.3.2. Estabelecimento das ligações
Num descritor de nome de predicado que não tenha ainda sido ligado, o campo
PredCode aponta sempre para uma instrução da CxM que se encontra no campo Inst, e
que é especializada no estabelecimento de ligações. Como o conjunto de acções a
efectuar para estabelecer uma ligação varia muito com o tipo de nome de predicado,
foram definidas na máquina abstracta quatro instruções de ligação distintas:
MakeIndex, MakeImportBinding, MakeCtxExtBinding e MakeCtxDepBinding.
De modo geral, o estabelecimento de uma ligação consiste na determinação do
endereço do código a executar e na memorização desse endereço no campo PredCode de
um descritor de nome de predicado. Com este método, a ligação depois de efectuada
mantém-se fixa, não havendo perda de eficiência, para além da que resulta das
chamadas de predicado serem feitas usando uma indirecção, o que praticamente não
tem significado.
5. Mecanismos de ligação incremental da CxM
52
Faz-se de seguida uma descrição breve da funcionalidade de cada uma das quatro
instruções de ligação da CxM.
5.3.2.1. MakeIndex
O caso do estabelecimento de uma ligação para um nome definido localmente
parece ser o mais simples de tratar, pois aparentemente basta memorizar em
PredCode, o endereço do código da primeira cláusula do predicado. No entanto isto só
estaria correcto se na CxM não existissem mecanismos de indexação. Como é
suportada indexação, a instrução de ligação tem neste caso a tarefa, bastante mais
complicada, de construir o índice do predicado, sendo a ligação efectuada usando o
endereço do índice construído.
5.3.2.2. MakeImportBinding
No momento do estabelecimento da ligação para nomes importados, toda a
informação necessária está presente no descritor. Consiste no functor do predicado
importado e no termo que descreve a unit de onde se importa.
No estabelecimento da ligação há diversos casos a considerar: a unit pode estar
definida, não existir, ou ainda ser um parâmetro de unit; por sua vez o nome de
predicado pode ser ou não ser visível na unit donde é importado. A instrução
MakeImportBinding chama uma componente do compilador que trata todos estes
casos e cria geralmente um pequeno segmento de código de ligação, no qual se efectua a
chamada do predicado no contexto adequado. As instruções geradas executam em
sequência as seguintes acções: mudança de contexto, chamada do predicado externo,
reposição do contexto inicial, retorno. O caso, pouco frequente, em que o nome de
predicado importado não é visível recebe um tratamento mais simples: faz-se o campo
do seu descritor
PredCode apontar para a instrução ImportJumpBelow, cujo
argumento é um functor e efectua uma busca no contexto corrente, ignorando o seu
topo que, neste caso, não precisa de ser alterado.
5.3.2.3. MakeCtxExtBinding
O tratamento do caso das fórmulas de extensão é mais simples que o dos nomes
importados, visto que a mudança de contexto necessária à invocação do predicado, ter
sido já tratada em tempo de compilação 6 . Como no momento em que a ligação é
efectuada a unit que determinou a extensão de contexto já se encontra no topo do
contexto corrente, basta verificar se o nome de predicado invocado é ou não visível
nessa unit (cf. 4.4.3). Para cada um destes dois casos a ligação estabelece-se fazendo
PredCode apontar, respectivamente, para a instrução CtxExtJump (que tem como
argumento o descritor de nome de predicado externo que é chamado e executa um salto
6 A sintaxe das fórmulas de extensão permite que isto seja feito.
5. Mecanismos de ligação incremental da CxM
53
inter-units) ou para a instrução CtxExtJumpBelow (cujo argumento é um functor e faz
uma busca no contexto corrente ignorando o seu topo).
5.3.2.4. MakeCtxDepBinding
O mecanismo usado no estabelecimento de ligações para nomes dependentes do
contexto, e que se encontra descrito no ponto 4.4.2, tem um carácter altamente
dinâmico, que o torna um caso a ser considerado à parte. Recordemos que a técnica
usada associa a cada nome dependente do contexto algumas células de uma zona de
uma instância da sua unit a que chamámos cache. No fundo essa cache não é mais do
que um ambiente de ligação sendo aí que as ligações são estabelecidas. Para que serve
então a instrução MakeCtxDepBinding? Esta instrução é usada também para efectuar
um determinado tipo de ligação, só que de natureza diversa. Ela associa um nome
dependente do contexto a um deslocamento na cache e informa a unit a que ele
pertence, de que deve reservar as células correspondentes a esse deslocamento em
todas as suas instâncias. Trata-se portanto de uma espécie ligação de nível 2. O
estabelecimento da ligação completa-se, fazendo PredCode apontar para a instrução
CtxDepJump, a qual tem como argumento o deslocamento na cache atrás referido. É
nesta instrução que se encontra codificada toda a lógica de chamada de predicados
dependentes do contexto.
5.3.3. Invalidação das ligações
Existem diversos predicados de sistema (assert, retract, visible, etc) que afectam o
estado interno dos descritores de nome de predicado. Esses predicados de sistema,
podem ser chamados directamente pelo utilizador, mas geralmente são usados pelo
sistema de suporte ou pelo ambiente de programação em resposta a uma solicitação de
mais alto nível.
Muitas das alterações do estado interno dos nomes de predicado afectam a validade
de uma ou mais ligações já estabelecidas. Um dos casos mais simples, por afectar
apenas a ligação existente para o descritor de um único nome de predicado, é o da
adição de uma cláusula a um predicado: a ligação terá de ser restabelecida por
reconstrução do seu índice. No outro extremo da graduação da complexidade,
encontra-se a operação de mudança do estado de visibilidade de um predicado, a qual
pode invalidar múltiplas ligações, tanto de nomes dependentes do contexto, como de
nomes importados ou fórmulas de extensão.
De modo geral, quando um ligação fica inválida existem duas vias possíveis para
lidar com a situação. A primeira consiste em logo após a determinação da sua não
validade fazer o seu restabelecimento imediato. A segunda não é tão directa:
corresponde a trazer de novo as ligações inválidas, para o seu estado inicial de
ligação-por-estabelecer, deixando o seu estabelecimento efectivo para a próxima
invocação do nome. Esta última alternativa mereceu preferência devido a ser habitual
5. Mecanismos de ligação incremental da CxM
54
que as alterações da base de dados sejam feitas de forma agrupada (ex: carregamento
das diversas cláusulas de um predicado). Se a primeira alternativa fosse a escolhida,
as ligações logo depois de recuperadas estariam constantemente a ficar inválidas,
perdendo-se desta forma tempo em vão.
Fazemos de seguida o levantamento completo do efeito que os predicados de
controlo da base de dados têm nas ligações. Todos os predicados referidos actuam
sobre os nomes da unit corrente.
5.3.3.1. Efeitos da alteração do conjunto de cláusulas de uma unit
assert(Clause)
retract(Clauses)
Em relação a estes dois predicados de sistema é invalidada apenas a ligação do
nome de predicado afectado pela operação. Para se desfazer a ligação, é necessário
determinar qual a instrução de ligação da CxM que deve ser usada na circunstância,
tendo em conta os atributos com que o nome de predicado fica após a alteração. Se o
nome ficar sem cláusulas, torna-se um nome dependente do contexto e nesse caso deve
ser instalada a instrução MakeCtxDepBinding no campo Inst do descritor. Caso
contrário a instrução a usar é MakeIndex.
Note-se que este esquema, apesar de ser de forma geral muito prático, pode ter
alguns inconvenientes no caso particular de um predicado muito dinâmico, que esteja
sujeito a constantes alterações. De facto, nestas circunstancias, a maioria das
invocações do predicado acabam por provocar a reconstrução refazer do seu índice. E
como esta operação, pode ser relativamente demorada no caso em que o predicado é
constituído por muitas cláusulas, os benefícios do índice, podem ser ultrapassados
pelo inconveniente da sua constante reconstrução. Para resolver este problema foi
incluído nos descritores de nome de predicado um atributo booleano - NoIndex - o qual
indica se o índice deve afinal se ou não ser construído. Esse atributo é consultado pela
instrução MakeIndex e é posicionado pelo predicado de sistema noindex(Name,Arity).
Esta solução para o caso dos predicados altamente dinâmicos, sendo aceitável, não
é ainda no entanto a melhor, pois passa para a responsabilidade do programador um
decisão que idealmente deveria ser tomada pelo sistema de forma automática. Com
efeito parece viável associar a cada descritor de nome de predicado uma medida do seu
dinamismo, calculada pelo sistema a partir do seu historial de alterações. Durante os
períodos em que esse valor excedesse um determinado limiar, o índice do predicado
não seria reconstruído.
5. Mecanismos de ligação incremental da CxM
55
5.3.3.2. Efeitos da alteração de importação
import(Pred,Arity,UnitDescription)
noimport(Pred,Arity)
As restrições impostas na linguagem CxLP aos nomes de predicado, impossibilitam
a existência nas units, de cláusulas locais associadas a nomes importados. É por esse
motivo que os predicados de sistema import/2 e noimport/2 são apenas aplicáveis a
nomes de predicados sem cláusulas. O seu uso provoca a mudança de tipo dos nomes de
predicados, de dependentes de contexto para importados, e vice-versa. Cada mudança
destas é acompanhada pela anulação de uma eventualmente existente ligação, sendo
usada a instrução de ligação adequada ao tipo com que o nome de predicado fica. As
duas possibilidades são: MakeCtxDepBinding e MakeImportBinding. Neste caso
também só é afectada uma única ligação.
5.3.3.3. Efeitos da mudança de visibilidade
visible(Pred,Arity)
novisible(Pred,Arity)
O caso da mudança de visibilidade de um nome de predicado p pertencente a uma
unit u, é o de tratamento mais complexo pois pode afectar várias ligações ao mesmo
tempo. Como qualquer ligação que não tenha natureza local pode ser atingida por esta
mudança, façamos um levantamento organizado por tipo de ligação, de todas as que
ficam inválidas.
No que diz respeito aos nomes importados, são atingidos todos
os
que
correspondem a declarações de importação do nome p a partir da unit u. Como o tipo
no nome de predicado não muda, é usada a instrução MakeImportBinding para
preparar o seu descritor
para
o
restabelecimento
da
ligação.
Esta
concretizada, terá características completamente diferentes das que
quando
existiam
anteriormente: o segmento de código de ligação é substituído pela instrução
ImportJumpBelow e vice-versa. Para permitir a detecção rápida de todos os
descritores de nome de predicado afectados, a base de dados prevê um acesso
optimizado com base nos functores. O campo ImportedTerm daqueles descritores é
usado nessa detecção.
O caso dos nomes que ocorrem em fórmulas de extensão tem muitas semelhanças
com o dos nomes importados. As ligações aqui afectadas são as que estão associadas a
referências ao nome p, que aparecem em fórmulas de extensão, nas quais a última
unit a estender o contexto foi a unit u (como por exemplo em u>>p, ou a(zz)>>B>>u>>p).
Atendendo a que o tipo das ligações a refazer aqui também não muda, é usada para o
efeito a instrução MakeCtxExtBinding a qual no momento da ligação produzirá
código de ligação diferente do que existia anteriormente: concretamente a instrução
CtxExtJump será substituída pela instrução CtxExtJumpBelow e vice-versa. A
detecção de todas as ligações deste tipo que devem ser invalidadas é feita rapidamente
5. Mecanismos de ligação incremental da CxM
56
usando o acesso privilegiado na base de dados, que foi atrás referido. A selecção dos
descritores de nome de predicado que nos interessam, de entre os que são acessíveis a
partir do functor, é feita com base no seu campo ExtUnit no qual se encontra uma
referência para a unit que determina a extensão do contexto na fórmula de extensão.
Falta só analisar a forma como os nomes dependentes de contexto são afectados
pela mudança de visibilidade de um nome de predicado. Como nos outros casos, esta
mudança não afecta o tipo de nome de predicado que continua a ser dependente de
contexto. Mas desta vez, ao contrário do que acontecia nos dois casos anteriores,
também não invalida a ligação estabelecida pela instrução MakeCtxDepBinding. Esta
recorde-se, atribuia ao nome de predicado apenas um deslocamento nas caches das
instâncias de unit, não existindo qualquer razão para proceder à sua alteração. O
efeito provocado pela mudança de visibilidade de um nome de predicado afecta sim,
algumas das ligações estabelecidas nessas caches. Como este problema é de natureza
diversa daqueles que têm vindo a ser discutidos neste ponto, e por ele merecer especial
relevo, faz-se a sua discussão separadamente no ponto 5.3.4.
5.3.3.4. Efeitos da eliminação de um nome de predicado
abolish(Name,Arity)
O efeito deste predicado de sistema é equivalente ao da chamada sucessiva dos
predicados novisible/2, noimport/2, e finalmente retract/1 para eliminação de todas
as cláusulas do predicado a que se aplica. Desta forma o efeito que abolish/2 tem nas
ligações dos nomes de predicado fica completamente definido a partir de tudo o que foi
discutido nos pontos anteriores.
5.3.4. As ligações dos nomes dependentes do contexto revisitadas
O problema das ligações dos nomes dependentes do contexto já foi objecto de
análise nos pontos 4.4.2 e 4.6. No entanto, no contexto da discussão feita neste
capítulo, o problema da manutenção da coerência dessas ligações necessita de estudo
suplementar.
As alterações do estado da base de dados que têm impacto no estabelecimento das
ligações dos nomes dependentes do contexto, são as que resultam da adição de
clausulas, usando o predicado assert/1, e da mudança do estado de visibilidade de
nomes de predicado, usando visible/2, novisible/2.
5.3.4.1. Adição de cláusulas
Tratemos primeiro o caso da adição de uma nova cláusula a uma unit. As
complicações que aqui se originam têm a ver com a possibilidade de criação dinâmica
de novos nomes dependentes do contexto: basta para isso que o corpo da nova cláusula
contenha invocações de nomes de predicados não definidos localmente nem
importados. Quando o número de predicados dependentes do contexto aumenta, seria
5. Mecanismos de ligação incremental da CxM
óptimo que as caches de todas as
instâncias
dessa
unit
pudessem
57
crescer
simultaneamente, a fim de que as ligações dos novos nomes fosse estabelecida da
forma normal. Mas isto só é possível em relação às novas instâncias de unit criadas
depois da alteração, pois as instâncias de unit já existentes estão encaixadas no stack
local e não podem crescer. Isto significa que durante a execução de um programa
podem
aparecer
instruções
CtxDepJump que tenham
como
argumento,
um
deslocamento na cache correspondente a uma posição não existente. Este problema
obriga a que a instrução efectue um teste suplementar com o fim de ser averiguada a
validade do deslocamento. Caso ele não seja válido a ligação tem de ser feita de forma
completamente dinâmica por pesquisa no contexto sem recurso à utilização da cache.
Este teste de validade do deslocamento implica o conhecimento, do tamanho com que
a cache foi criada, valor esse que é guardado no campo N da instância da unit.
5.3.4.2. Mudança do estado de visibilidade de um nome
A mudança do estado de visibilidade de um nome qualquer tem consequências algo
drásticas em relação às ligações dos nomes dependentes do contexto. Isto deve-se ao
facto de que quando uma destas ligações é estabelecida por pesquisa no contexto
corrente, para um certo nome n, ser usada informação sobre a visibilidade de n em
todas as units que se encontram acima do ponto onde a definição do predicado foi
encontrada. Assim quando se dá uma mudança no estado de visibilidade de n numa
unit qualquer, todas as ligações estabelecidas nas caches, que envolvam esse nome
ficam postas em causa.
Para ser reposto o estado coerente da máquina, a solução naïve, que consiste em
percorrer todas as caches existentes no stack local à procura de ligações inválidas
para serem refeitas, é extremamente inconveniente porque ineficiente.
O método que foi usado para resolver este problema baseia-se na existência de um
número de versão que se associa a cada functor. Sempre que o estado de visibilidade de
um predicado é alterado o número de versão do seu functor é incrementado para
assinalar a mudança de situação. A instrução CtxDepJump usa o número de versão da
seguinte forma: sempre que estabelece uma ligação para o nome n, além de memorizar
na cache a referência do predicado que ficou ligado a n e o contexto onde deve ser
lançada sua execução, guarda também o número de versão corrente de n (a cache tem
de ser portanto constituída por grupos de três células); a partir daí, sempre que a
instrução consultar a cache nas próximas invocações de n, ela compara o número de
versão guardado na cache com o guardado no functor de n: em caso de desfasamento a
ligação precisa de ser refeita, o que se processa imediatamente por pesquisa no
contexto corrente.
5. Mecanismos de ligação incremental da CxM
58
5.3.4.3. Eficiência
Nas ligações de nomes dependentes do contexto, ao contrário do que acontece para
todos os outros tipos de ligação, o preço a pagar pela flexibilidade do sistema de
suporte adquire algum significado. O teste suplementar para verificar a validade do
argumento da instrução que indica o deslocamento na cache, e as manipulações
efectuadas com os números de versão consomem ao todo cerca de 40% do tempo total
de execução da instrução CtxDepJump o que penaliza todas as chamadas de nomes
dependentes do contexto. Entretanto num sistema em que não fosse possível de forma
dinâmica fazer a adição de cláusulas nem a alteração do estado de visibilidade de
nomes de predicado, a chamada de nomes dependentes do contexto seria mais
eficiente, sendo os referidos 40% reduzidos para 15%, que correspondem ao tempo
necessário para testar o preenchimento da posição da cache respectiva. De qualquer
forma a diferença entre estes dois valores - 25% - não parece ser suficientemente
elevada para constituir fonte de preocupação, por se localizar numa única instrução.
59
6
Técnicas de implementação da CxM
6.1. Introdução
Se tomarmos a descrição da máquina abstracta CxM que se encontra no apêndice
B, e a tentarmos codificar directamente usando por exemplo a linguagem C,
verificaremos que a eficiência da implementação obtida deixa muito a desejar,
quando comparada com a da maior parte dos compiladores de Prolog existentes no
mercado. No entanto se fizermos a cuidadosa consideração de todas as oportunidades
para a introdução de optimizações que for possível descobrir, as melhorias de
desempenho
são
muito
substanciais
podendo
facilmente
exceder
os
400%!
Sublinhe-se que isto pode ser feito recorrendo apenas a optimizações de natureza
conceptual, que não resultam da utilização de linguagem máquina.
Este capítulo é dedicado à apresentação das principais técnicas que foram usadas
com o objectivo de incrementar tanto quanto possível a eficiência da nossa máquina.
6.2. Lips!
O nosso protótipo da CxM consiste numa implementação portável da máquina,
escrita na linguagem C. Foi desenvolvida em computadores Macintosh usando o
ambiente de programação Think C, e em computadores VAX usando o compilador de
C, gcc.
Não obstante o sistema se encontrar escrito numa linguagem de alto nível, ele
oferece um desempenho bastante razoável: numa VAXstation 3540 a velocidade do
6. Técnicas de implementação da CxM
60
programa de teste tradicional, o naïve-reverse, excede os 60 KLips. É interessante
comparar este valor com a velocidade de uma das melhores implementações
comerciais do Prolog, o Quintus Prolog v2.4, que na mesma máquina e com o mesmo
programa faz cerca de 95 Klips!
Para a uma justa apreciação destes valores é conveniente notar que a comparação
que eles proporcionam ser muito grosseira. De facto, como o Quintus faz análise
global de programas, esta diferença aumenta ainda mais a seu favor nos programas
complexos da vida real. Em contrapartida a nossa implementação suporta uma
linguagem mais complexa, e está preparada para lidar com predicados dinâmicos sem
penalização de velocidade. Para exemplificar este último aspecto, usando o mesmo
programa de teste num formato dinâmico, o Quintus faz apenas 2.3Klips, que é um
valor mesmo inferior ao obtido no interpretador CProlog que faz 5Klips.
Outros dois compiladores de Prolog, muito conhecidos, são o SB-Prolog e o
SICStus-Prolog; as suas velocidades para o mesmo programa são inferiores a 35 Klips.
Nos diversos pontos que constituem este capítulo, serão feitas algumas referências
ao ganho percentual de velocidade que algumas optimizações da máquina permitiram
alcançar. Esta avaliação se não for usada com cautela pode revelar-se errónea, pois os
valores obtidos, dependem fortemente do estado geral de optimização da máquina no
momento em que as são feitas7. Devido a esta relatividade, nas percentagens que
serão indicadas toma-se sempre por referência uma mesma versão da máquina
(concretamente a do dia em que este capítulo começou a ser escrito - 15 de Junho de
1990). Esses valores reflectirão portanto a situação em que a optimização que estiver a
ser referida ter sido exactamente a última a ser introduzida na máquina.
Em geral, as percentagens indicadas aplicam-se ao programa de teste naïve-reverse
correndo numa VAXstation 3540 usando o compilador gcc. Esta última configuração
foi escolhida devido à capacidade do gcc lidar com registos globais e ao facto de no VAX
ser permitido declarar 6 desses registos desses. Desta forma a torna-se possível
abordar tópicos que em alternativa teriam requerido o uso de assembler na
experimentação.
6.3. Técnica de interpretação
6.3.1. Código threaded
Na implementação do ciclo de interpretação da máquina abstracta foi usada a
técnica chamada de código threaded directo (cf. [Bell 73]). Este método tem as seguintes
duas características distintivas:
7 Por exemplo se uma determinada optimização permite ganhar 1 segundo num programa que
demora 10 segundos a correr parece correcto dizer que o ganho foi de 10%. Mas suponhamos
que suspendemos essa optimização e que nos dedicamos a melhorar outros aspectos da
máquina. Mais tarde quabndo o mesmo programa correr em 5 segundos, a reintrodução da
optimização anterior permite agora uma ganho de 20%.
6. Técnicas de implementação da CxM
61
• Cada instrução da máquina abstracta está codificada numa rotina separada.
• O formato de cada instrução da máquina abstracta consiste no endereço da
rotina que a implementa, seguido de eventuais argumentos.
Usando a linguagem C e assumindo que cada instrução se encontra programada
numa função sem argumentos, o ciclo de interpretação de uma máquina deste tipo é
fácil de escrever:
while( true ) (*PC++)() ;
em que PC (contador de programa) é uma variável da linguagem C do tipo apontador
para função.
6.3.2. Método clássico
O método que mais tradicionalmente se usa para implementar interpretadores de
máquinas abstractas define um formato de instrução próximo do das máquinas
convencionais reais. Nesse método, que chamaremos de método clássico, todas as
instruções têm uma zona inicial fixa de identificação (código de operação), sendo os
argumentos colocados a seguir. Em cada iteração do ciclo de interpretação, é
consultado o código de operação da instrução corrente, que é usado para seleccionar o
código a executar. Este esquema, quando programado em C, é codificado num ciclo
dentro do qual se encontra uma instrução alternativa switch, a qual deverá prever
tantas possibilidades quantas as instruções da máquina abstracta. Desta forma toda
a máquina abstracta fica definida dentro de uma única função.
6.3.3. Comparação
A forma de descodificação das instruções no método descrito em primeiro lugar é
bastante mais simples do que a do método clássico. Numa máquina em que a operação
de chamada de função não seja demasiado ineficiente, o primeiro método é
consequentemente o mais rápido. No entanto se o interpretador for programado em C,
linguagem que permite a utilização de registos locais, o método clássico fica com clara
vantagem. Isto é assim porque o interpretador se encontra todo dentro de uma única
função, tornando-se agora possível declarar os mais importantes registos da máquina
abstracta, como sendo registos da máquina hospedeira.
A linguagem escolhida para o desenvolvimento do protótipo portável da nossa
máquina abstracta foi a linguagem C donde, em coerência com o que foi atrás
afirmado, parece que o método clássico deveria ter sido alvo de escolha. A razão pela
qual isto não aconteceu, deveu-se ao facto de estarmos interessados em usar a corrente
implementação, escrita em C, como base para futuras implementações não portáveis
escritas parcialmente em assembler. Essas implementações, atendendo às suas
características, já terão liberdade para usar os registos da máquina hospedeira. Em
essência o que isto significa é que estamos dispostos em prescindir de uma parte
significativa da eficiência da implementação inicial da máquina, em troca da
6. Técnicas de implementação da CxM
62
perspectiva da existência de futuras versões, as quais, sem compromissos de desenho
inicial, possam atingir elevadas velocidades. Entretanto o facto de o gcc permitir a
declaração de registos globais (contrariando o standard da linguagem C), torna
possível desde já a obtenção de versões da máquina de razoável desempenho.
6.3.4. Eliminação do ciclo de interpretação
O aspecto talvez mais crítico para a velocidade da máquina abstracta reside no seu
ciclo de interpretação. Existem técnicas conhecidas, que permitem reduzir o seu peso
no controlo da máquina recorrendo ao uso de um pouco de assembler. Como este caso é
realmente especial, foi o único em que condescendemos em utilizar de um pouco de
assembler. A técnica usada assume que no código gerado pelo compilador de C, nunca
tem lugar a criação de registos de activação nas invocação de funções desprovidas de
argumentos e variáveis locais. O método consiste em eliminar o ciclo de interpretação
substituindo-o por uma macro escrita em assembler, chamada JumpNext(), que é
colocada no final de cada instrução. Essa macro limita-se a transferir o controlo para
a instrução cujo endereço é apontado correntemente pelo contador de programa
(registo P da CxM) e a incrementá-lo.
O Vax dispõe de uma instrução-máquina que desempenha exactamente essa tarefa.
Trata-se da instrução jmp @(r)+, em que r é um registo. O Mac também possui uma
instrução semelhante, mas não foi possível utilizá-la, pois o Think C não permite a
declaração de registos globais, ficando a macro definida por 4 instruções-máquina.
O ganho de velocidade no Mac foi significativo: 10%. No entanto no Vax foi enorme:
226%. Para além da circunstância de a macro JumpNext() se reduzir a uma única
instrução da máquina hospedeira, esse valor também resulta de no Vax o mecanismo
de invocação de procedimentos ser ineficiente (devido à sua grande generalidade): a
eliminação do ciclo de interpretação permite o ganho do tempo de uma chamada de
função por cada instrução da CxM executada.
6.3.5. Código expandido
Existem muitas instruções da máquina abstracta cujo código de implementação é
extremamente compacto, resumindo-se a uma, duas ou três instruções da máquina
hospedeira. Nestes casos torna-se muito atraente a ideia de substituir no código da
CxM essas instruções pela sua definição expandida em linha.
Usando a nossa forma de codificar as instruções, teríamos necessariamente de
recorrer a um nova instrução, chamada por exemplo BeginInLine, que seria colocada
no inicio de todos os segmentos de código expandido. Essa instrução faria apenas a
cópia do contador de programa da CxM, para o contador de programa da máquina
hospedeira, a qual poderia assim executar o código expandido. É claro que no final de
6. Técnicas de implementação da CxM
63
cada um destes segmentos de código expandido teriam de existir instruções da
máquina hospedeira que retornassem o controlo para a máquina abstracta.
Uma técnica que muitas vezes se usa para simplificar este tipo de inclusão de código
em linha, consiste em alterar a própria representação das instruções da máquina
abstracta, substituindo os seus endereços por instruções de salto em que estes
endereços figuram como argumentos. Desta forma, a expansão de código pode ser feita
livremente, sem ser necessário recorrer a instruções de transferência de controlo
entre a máquina real e a máquina abstracta.
Uma variação do método anterior consiste na utilização de instruções de chamada
de subrotina em substituição das instruções de salto. As vantagens gerais da técnica
mantêm-se, ficando até simplificado o problema da gestão do contador de programa
da máquina abstracta: neste caso ficaria de certa maneira implícito constituindo
permanentemente o topo da pilha de execução da máquina hospedeira. No entanto na
maior parte das máquinas (reais) este método torna-se menos eficiente que o anterior,
pois impede que a máquina abstracta tenha o seu contador de programa num registo, o
que torna por exemplo o acesso aos argumentos das instruções mais lento.
Estas técnicas de inserção de código em linha foram aqui referidas apenas por uma
questão de completude, visto não serem usadas na corrente implementação da CxM.
Elas serão no entanto objecto de exploração futura.
6.4. Tags
No ponto 4.2 já foi descrito o esquema básico utilizado na máquina CxM para
codificar o tipo dos seus termos o qual, como se viu, recorre à utilização de tags. A
frequência com que durante a execução dos programas são efectuados testes para a
determinação do tipo de termos, torna este um aspecto de grande relevância para a
eficiência da máquina. A CxM assume um tamanho de célula de memória de 32 bits,
que é portanto o valor subjacente à discussão que se segue.
Existem duas decisões que é necessário tomar para
a
determinação
das
configurações das tags dos termos: qual o número de bits que devem ser reservados nas
células de memória para a codificação das tags, e quais os padrões de bits a utilizar.
Na concretização destas escolhas, um primeiro factor muito importante a
considerar, é o da frequência com que cada tipo de termo é testado. Quando
analisamos a definição do conjunto das instruções da CxM, verificamos que o teste
que por uma larga margem é mais usado é IsVar(t), o qual como o nome indica, permite
determinar se um dado termo é uma variável ou não. A uma grande distância dele em
termos de frequência, aparecem os testes de lista e de estrutura. Entretanto os testes de
átomo, inteiro e
real,
estão
praticamente
exclusivamente na programação de certos
ausentes;
eles
predicados
de
são
usados
sistema,
os
quase
quais,
comparativamente com as instruções da máquina, não são factor muito relevante
6. Técnicas de implementação da CxM
64
para o desempenho da máquina. Tornou-se desta maneira fácil estabelecer uma
hierarquia entre os tipos dos termos que reflecte a frequência com que são testados:
• Variável
• Lista, Estrutura
• Átomo, Inteiro, Real
Um segundo aspecto que temos de considerar na definição das tags, é a da eficiência
relativa das instruções da máquina hospedeira, para que seja tirado o melhor partido
das instruções de teste e salto existentes, através da escolha das mais eficientes. Esta é
uma tarefa que idealmente deveria ser feita em cada implementação concreta da CxM,
atendendo às características particulares de cada máquina hospedeira. No entanto,
visto não haver assinalável variabilidade nos computadores convencionais em
relação ao tipo de instruções que referimos, é possível extrair algumas conclusões
gerais aplicáveis em muitos casos. É a seguinte a hierarquia (decrescente) de eficiência
de testes que conseguimos obter:
• Teste de sinal
• Teste de bit
• Comparação com constante
• And com constante
• Teste directo da tag
(t>0)
( t & 0x2 == 0 )
( t > 0x276896 )
( t & testList == 0 )
( t & tagMask == intTag )
A eficiência do quarto teste é geralmente equivalente à do terceiro; foi incluído
apenas porque em determinadas circunstâncias ele é mais informativo que o terceiro.
Um último factor a considerar para a definição das tags consiste em evitar a
reserva de demasiados bits nas palavras, por forma a que fique espaço suficiente para
os endereços que nelas são guardados e não comprometer demasiado a precisão dos
valores numéricos.
Os três factores que foram referidos são suficientes para fazer a justificação
completa do sistema básico de tags usado na CxM, e que é o seguinte:
Tags da CxM
Variável:
Lista:
Estrutura:
Átomo:
Inteiro:
Real:
0000............................
1001............................
1010............................
1011............................
110.............................
111.............................
Em relação às variáveis foi usado o método mais eficiente que estava disponível,
tendo sido reservado o bit de sinal para a sua codificação. Além disso, todos os bits da
tag foram deixados a zero, para evitar demoras na operação de extracção do conteúdo
da variável durante as desreferenciações.
IsVar(t) ≡ t > 0
No que diz respeito às tags de listas e estruturas foram usados padrões que,
esquecido o bit de sinal, têm todos os bits iguais a zero, com excepção de um. Isto
permite a utilização de testes do tipo que se encontra em quarto lugar na hierarquia da
6. Técnicas de implementação da CxM
65
eficiência, quando for possível garantir que o termo a ser testado não é uma variável.
Essa garantia pode ser dada em todas as circunstâncias importantes. Note-se que o
teste de lista podia também ser feito usando o teste número 3, através da comparação
com uma constante (tagList). No entanto este método não se generaliza ao caso da
estrutura que já exigiria duas comparações. Por isso em ambos os casos se usa o 4º
teste.
testNoVarList ≡
testNoVarStruct ≡
0x60000000
0x50000000
IsList(t) ≡
IsStruct(t) ≡
IsListNoVar(t) ≡
IsStructNoVar(t) ≡
t
t
t
t
&
&
&
&
tagMask4 = tagList
tagMask4 = tagStruct
testNoVarList == 0
testNoVarStruct == 0
A forma de representação das constantes não é importante pois raramente as suas
tags são testadas directamente. Para testar, por exemplo, se um termo é uma constante
particular, usa-se na comparação todo o conteúdo da célula de memória, incluindo a
tag. O único aspecto que merece aqui especial referência é o facto de se usarem apenas
três bits de tag na representação dos valores numéricos a fim de não ser prejudicada a
sua precisão.
IsAtom(t) ≡
IsInt(t) ≡
IsReal(t) ≡
t & tagMask4 = tagAtom
t & tagMask3 = tagInt
t & tagMask3 = tagReal
Note-se que a utilização de 3/4 bits nas tags dos termos da CxM resulta de um
compromisso entre a eficiência dos testes de tipo e o número de bits usados. A situação
ideal em termos de velocidade seria a de reservar um bit diferente para cada tipo de
termo existente. No entanto isso não seria comportável devido ao excessivo tamanho
com que a tag ficaria.
Em relação a um método naïve de codificação das tags que envolva a utilização de
instruções de teste do 5º tipo em todos os casos, o nosso esquema de representação
proporciona um ganho de velocidade superior a 15%, em todos os casos estudados
(naïve-reverse no Vax, Mac II e Mac Plus). Constata-se por isso que vale a pena, em
cada implementação concreta da CxM, estudar o conjunto de instruções da máquina
hospedeira, com o objectivo de procurar alguma particularidade da qual se possa
extrair ainda mais eficiência. Por exemplo nos VAX, existe uma instrução muito
interessante que tem uma funcionalidade que nas outras máquinas só se consegue
usando duas instruções distintas: testa o bit menos significativo de uma célula de
memória e executa condicionalmente um salto relativo dependendo do valor desse bit.
Isto significa que no Vax é ainda mais eficiente testar o bit menos significativo de uma
palavra que o bit de sinal. A utilização desta instrução permitiu um ganho de cerca de
7% em relação ao esquema básico, o que totaliza um ganho de cerca de 23%
6. Técnicas de implementação da CxM
66
(1.15 * 1.07 = 1.2305) em relação ao esquema naïve. No VAX as tags têm a seguinte
configuração:
Tags da CxM nos VAX
Variável:
Lista:
Estrutura:
Átomo:
Inteiro:
Real:
000............................0
001............................1
010............................1
011............................1
10.............................1
11.............................1
6.5. Rotina de unificação
Um dos objectivos do uso de compilação na implementação de CxLP é o de fazer o
pré-tratamento possível, das unificações que ocorrem nos programas. O compilador,
usando informação estática extraída do programa fonte, consegue assim eliminar
grande parte do tempo dispendido em unificações durante a execução dos programa.
Apesar disso, o dinamismo inerente à execução dos programas nesta linguagem obriga
a que muitas das situações tenham de ser tratadas em tempo de execução, por recurso a
uma rotina de unificação geral. O peso dessa rotina é importante no tempo total de
execução dos programas, o que pode ser confirmado recorrendo a um profiler. Por
exemplo, no predicado naïve-reverse, 10% do tempo total de execução é dispendido
nessa rotina. Este valor pode ser considerado um limiar inferior pois a maioria das
unificações efectuadas no programa têm um carácter superficial: nunca se torna
necessário mergulhar muito fundo na estrutura dos termos para que as unificações se
concretizem. Da análise da definição das instruções que se encontram em apêndice
pode-se constatar que a rotina de unificação é invocada pela maioria das instruções
do tipo get e unify, o que explica a sua importância no desempenho geral da máquina.
A definição da rotina de unificação da CxM encontra-se no apêndice B, na zona da
definição das operações auxiliares mais importantes para o funcionamento da CxM.
Como aí se poderá observar, a rotina usa uma pilha na memorização dos argumentos
das estruturas e listas que, durante a execução do algoritmo, aguardam a sua vez de
serem considerados. Ao contrário da WAM, nós aqui não usamos uma pilha separada
para unificação, mas sim o próprio stack global. Esta decisão baseia-se na
consideração do facto de o registo da CxM que indica o topo do stack local - H -, pela
sua importância, provavelmente se encontrar num registo da máquina hospedeira.
Assim podemos incrementar o seu uso, tirando partido dele durante as unificações.
Isto não introduz nenhuma complicação adicional visto que caso a unificação falhe, o
mecanismo de retrocesso repõe o valor correcto de H; caso a unificação suceda, a pilha
de unificação fica vazia, o que significa que H retoma o valor de entrada na rotina de
unificação. Note-se que no caso de a máquina hospedeira não ter registos suficientes
para usar como variáveis auxiliares do algoritmo de unificação, é sempre possível
usar alguns da CxM (como por exemplo o contador de programa P). Temos também
6. Técnicas de implementação da CxM
67
neste caso o bónus de, em caso de falhanço, serem automaticamente repostos pelo
mecanismo de retrocesso. No entanto em caso de sucesso, é necessário repor o seu
valor inicial, o que obriga a uma salvaguarda inicial.
Outro aspecto que deve ser considerado, consiste no facto de, muitos dos casos que a
rotina de unificação trata, corresponderem a unificações superficiais, que não
chegam a necessitar da pilha de unificação. A rotina deve ter portanto características
optimistas, e só fazer a preparação da estrutura de dados auxiliar da unificação no
momento em que exista a certeza da necessidade da sua utilização. Isto obriga a
duplicar cerca de metade do código da rotina, mas é compensador visto verificar-se um
ganho geral de velocidade geral de cerca de 3% (ou seja 30% na própria rotina).
6.6. Especialização das instruções
Tal como na WAM, existem na CxM diversos exemplos de instruções que são
particularizações de instruções mais gerais. As instruções especializadas têm a
vantagem de serem sempre mais eficientes que as instruções gerais em que se baseiam.
É tarefa do compilador a detecção de todas as oportunidades para a sua utilização.
Como exemplos deste tipo de instruções, temos a instrução UnifyLocalValue que é uma
especialização da instrução UnifyValue, UnifyVoidOne que é uma particularização de
UnifyVoid e as instruções sobre listas que são especializações das instruções sobre
estruturas.
Um tipo de especialização que D. Warren sugere na pág. 20 de [Warren 83] consiste
na criação de novas versões de instruções através da fixação de um ou mais valores
dos seus argumentos. Por exemplo a instrução GetVariable Y2, X1 pode ser substituída
com vantagem por uma instrução sem argumentos chamada GetVariable_2_1. O
ganho que esta optimização proporciona é triplo: ganha-se tempo evitando o
tratamento dos argumentos em tempo de execução; o código da instrução fica mais
eficiente pois as referências aos argumentos são substituídas por referências a
constantes, e finalmente, o código que resulta da compilação fica mais compacto. A
desvantagem desta técnica resulta do facto de a máquina abstracta ficar maior e um
pouco mais complicada, por ter mais instruções.
Esta ideia foi extensamente explorada na CxM. As instruções da CxM mais
compactas ou de uso mais frequente, foram especializadas através da consideração
como casos particulares de todas as referências aos 5 primeiros registos X e às 5
primeiras variáveis Y da máquina. Evidentemente que isto gerou um grande número
de novas instruções tendo elas passado de cerca de 80 para mais de 250. Um dos casos
mais extremos de multiplicação de instruções, é o da instrução GetVariable Yn , Xi que
passou a existir em nada mais do que 36 versões diferentes, como por exemplo:
GetVariable_0_0, GetVariable_4_0, GetVariable_2 Xn , GetVariable_3 Yn, ….
6. Técnicas de implementação da CxM
68
O ganho de compacidade do código gerado que esta técnica proporcionou, é bastante
grande (cerca de 30%), visto a grande maioria dos argumentos das instruções deixarem
simplesmente de aparecer. Um aspecto curioso, consequência deste proliferar de
instruções consiste em que, do ponto de vista da execução da máquina, o efeito obtido
se aproxima daquele que se obteria se o compilador considerasse a definição das
instruções como macros, gerando sempre a sua expansão.
No VAX esta optimização proporcionou um ganho de velocidade de 48%. Entretanto
o aumento de tamanho do código objecto da máquina abstracta foi de cerca de 150%,
ficando a ocupar cerca de 35K de memória. No que respeita ao código fonte da máquina
abstracta, a utilização intensiva de macros permitiu controlar o seu crescimento, que
se cifrou num aumento de cerca de 100%, ficando com 4500 linhas de código C
(excluindo os comentários)
6.7. Utilização de registos da máquina hospedeira
O papel fulcral que os registos da CxM têm na definição do estado corrente da
computação na máquina abstracta, faz com que seja extremamente intensa a sua
utilização durante a execução dos programas. Compreende-se pois o contributo para o
desempenho da máquina que pode proporcionar a utilização de registos da máquina
hospedeira como registos da CxM.
A situação ideal em relação a este aspecto, será aquela em que a máquina
hospedeira disponha de um número de registos suficientemente grande para albergar
todos os registos de controlo da CxM, e ainda alguns registos X. Esta situação ideal
começa a tornar-se cada vez mais comum, pois nas arquitecturas mais recentes, um
número de registos de 32, é já relativamente corrente.
Mas quando os registos da máquina hospedeira registos são um recurso escasso,
torna-se necessário estabelecer uma relação de prioridade entre os registos da CxM,
com o objectivo de descobrir os mais fortes candidatos à utilização dos disponíveis.
Não é possível estabelecer esta relação de forma exacta, atendendo a que depende
significativamente do tipo de programas considerados na avaliação.
De qualquer forma existem alguns registos que se destacam de forma natural. Para
começar, o primeiro candidato é o registo P que é acedido sempre que uma instrução é
executada ou se acede a um argumento. Segue-se de perto o registo S que é usado nas
unificações das cabeças das cláusulas, e que pode ainda servir, sem conflito, para
indicar o modo corrente (escrita ou leitura) da CxM (só este pequeno truque
proporcionou um ganho de 5% de velocidade no VAX). Seguidamente vêm o registo H,
usado na criação de estruturas no stack global, e o registo E, usado na criação e acesso
aos registos de activação (incluindo variáveis permanentes) e ainda na determinação
do topo do stack local. A partir daqui a selecção dos próximos registos é menos clara.
Poderíamos argumentar que o próximo a considerar seria o registo B, pela sua
6. Técnicas de implementação da CxM
69
utilização na criação e preenchimento dos pontos de escolha, que têm numerosos
campos. Mas o facto é que estas operações são menos frequentes que as anteriores,
sendo ainda perfeitamente possível a utilização nelas de um registo auxiliar de
utilização geral (inicializado com o valor de B).
Por sua vez, a colocação de alguns registos X em registos da máquina hospedeira,
apesar de benéfica em termos de desempenho da máquina, tem o inconveniente de
obrigar à especialização de grande número instruções, muitas das quais seria
preferível manter na sua forma geral, devido ao seu grande tamanho ou ao baixo
ganho de velocidade proporcionado.
O compilador gcc no VAX permite a declaração de 6 registos globais. Os registos da
CxM que receberam a honra desta promoção foram os registos P, S, H, E e B.
Definimos ainda como registo uma variável auxiliar, da qual é feito um uso tão
intenso quanto possível. O ganho de velocidade conseguido foi de 148%8.
Note-se que a reserva de todos os registos da máquina hospedeira disponíveis
impede o compilador de C cumprir as declarações register do programa fonte da CxM, e
ainda de fazer optimizações por sua conta, usando registos. No entanto verifica-se na
prática que, se prescindirmos de qualquer um daqueles registos, deixando ao
compilador o critério da sua utilização, o desempenho da máquina baixa de forma
muito significativa.
6.8. Indexação
A indexação é uma técnica usada na WAM, e também na CxM, que permite reduzir
drasticamente o tempo consumido em retrocesso superficial dos programas. Os
métodos usados para fazer indexação na CxM são discutidos no capítulo dedicado à
compilação de CxLP, no ponto 7.6. Esta breve nota pretende apenas referir o enorme
ganho de velocidade que esses métodos proporcionam, e que no naïve-reverse é de
260% (17Klips contra 62 Klips)!
6.9. Penalizações provocadas pelos novos mecanismos
Para avaliar a incidência dos mecanismos relacionados com os contextos na
velocidade de execução de programas CxLP, utilizámos diversas versões do programa
naïve-reverse, as quais diferem entre si apenas na forma de acesso ao predicado
append/3. A versão mais rápida foi, como seria de esperar, a correspondente ao uso de
uma definição local para append/3. Por sua vez a versão que se revelou mais lenta, foi
a correspondente à importação deste predicado de um parâmetro de unit.
8Na versão da CxM, sem registos, usada nesta comparação, P permaneceu num registo para
não ser prejudicada a técnica de interpretação usada.
6. Técnicas de implementação da CxM
70
Durante experimentação foram usadas sempre listas de comprimento 30, sendo
portanto este o número exacto de chamadas (não recursivas) efectuadas de append/3.
As penalizações de velocidade obtidas para os diversos mecanismos testados, no Vax e
num Mac, tomando por referência o mais rápido (chamada de predicado local) foram
as seguintes:
•
•
•
•
•
Predicado importado de designador de unit atómico
Predicado importado de parâmetro de unit
Extensão de contexto usando designador de unit atómico
Extensão de contexto usando parâmetro de unit
Predicado dependente do contexto
Mac
7%
16%
5%
13%
3%
Vax
15%
33%
11%
28%
7%
O aspecto que mais rapidamente chama a atenção, é a grande disparidade dos
valores obtidos nas duas máquinas, a qual se justifica pela grande diferença de grau de
optimização que os compiladores usados suportam. O razoável valor obtido para o
caso dos predicados dependentes do contexto, deve-se ao facto de não envolverem a
criação de novas instâncias de unit, operação relativamente dispendiosa. Estes
valores são apenas indicativos, podendo na prática ser facilmente excedidos, tudo
dependendo das características dos programas usados.
Outra questão importante, é a de se saber em que medida é afectada a execução de
programas escritos em Prolog, em relação à WAM. Na nossa máquina não foi possível
evitar uma certa perda de eficiência nas operações que envolvem salvaguarda e
reposição de registos internos da máquina, por estes serem em maior número do que
na WAM. São as seguintes as instruções afectadas: Allocate, as variantes de
Deallocate, Proceed, TryMeElse, RetryMeElse, TrustMe, Try, Retry, e Trust. Em
algumas destas instruções são efectuadas três afectações suplementares, o que pode
prejudicar o seu desempenho em até 25% (15% em média).
De qualquer forma o prejuízo fica muito diluído pelas restantes instruções,
situando -se geralmente, na prática, bastante abaixo dos 2%. Por exemplo no caso do
naïve-reverse, que usa as instruções Allocate e Deallocate, a perda de velocidade chega
a não ser mensurável nos Vax, por ser inferior à margem de erro do tempo de CPU
fornecido pelo sistema.
Todas estas medições foram também aplicadas à implementação de CxLP efectuada
por Luís Monteiro e Vasco Pedro, que utiliza a técnica de pré-processamento com
tradução para Prolog [Monteiro 89b]. Os valores obtidos foram muito razoáveis
atendendo à técnica usada e ao facto de a eficiência não ter sido uma das preocupações
mais importantes da implementação: 50% de penalização na execução de programas
Prolog, mais cerca de 50% por cada um dos mecanismos expecíficos de CxLP.
71
7
Compilação
7.1. Introdução
A definição de máquinas abstractas constitui uma técnica de implementação de
linguagens de programação de ampla divulgação, e que tem uma especial importância
naquelas que, tal como o Prolog, têm um modelo de computação muito diferente do
que está subjacente aos computadores convencionais. Uma das particularidades mais
importantes desta técnica, reside no facto do conjunto de instruções abstractas ser de
alto nível, estando mais directamente adaptado ao programa fonte, que à máquina
real que vai executar o código objecto. Na perspectiva do compilador este facto é
positivo, pois geralmente significa que o processo de geração de código fica bastante
simples, por vezes mesmo trivial.
Na CxM, tal como na WAM, o conjunto de instruções é de bastante alto nível,
existindo mesmo uma relação relativamente directa entre um símbolo do programa
fonte e uma instrução da máquina. No entanto há um factor que complica o processo
de compilação. Trata-se do conjunto de facilidades que essas máquinas oferecem,
para a introdução de optimizações no código gerado. Estas facilidades não podem ser
ignoradas visto ser nelas que reside a explicação da sua maior velocidade e melhor
utilização da memória, relativamente a outras máquinas abstractas de concepção
mais naïve. Estamos concretamente a referir-nos ao suporte para a noção de registomáquina (os registos X), ao suporte de LCO (last call optimization), e ainda à existência
de instruções com diferentes graus de especialização, cujas condições de utilização
nem sempre são muito fáceis de detectar pelo compilador.
7. Compilação
72
Para o compilador tirar o melhor partido das potencialidades da CxM, ele deve
esforçar-se, portanto, por detectar as circunstâncias em que é possível gerar padrões
de código optimizado. Este problema na sua forma mais ambiciosa, envolve técnicas
sofisticadas de análise global de programas, que tornam o compilador um programa
complexo e, naturalmente, lento. Mas, se restringirmos o problema à compilação de
cláusulas individuais, abstraindo da sua interacção com o resto do programa, o
problema simplifica-se consideravelmente. Continua ainda, no entanto, a ser
possível introduzir importantes optimizações.
7.2. Características gerais do compilador
No nosso sistema, como tem sido dito, considerámos de primordial importância a
flexibilidade de utilização e a velocidade de resposta do sistema de suporte da
linguagem CxLP.
Para concretizar a flexibilidade de utilização foram usados mecanismos de
compilação e ligação incremental, os quais implicam um estilo de compilação
cláusula a cláusula, e impem qualquer tipo de análise global dos programas. Isto não
obsta, no entanto, a que seja incluído no sistema um compilador mais sofisticado,
para processar os programas depois de terem atingido a sua forma final. Um
programa deste tipo, adaptado à linguagem CxLP, não faz parte do âmbito deste
trabalho, mas será eventualmente objecto de trabalho futuro.
Quanto ao aspecto da velocidade de resposta do sistema, o compilador tenta
encontrar o melhor compromisso entre velocidade de compilação e qualidade de
código gerado. Para manter o desempenho do compilador a um nível elevado, ele foi
completamente escrito em C e não na própria linguagem a que serve de suporte, ao
contrário do que é habitual.
7.3. Funcionamento geral e código gerado
São três as principais estruturas de dados usadas pelo compilador: tabela de
variáveis contendo informação sobre todas as variáveis da cláusula a ser compilada,
tabela de registos que indica para cada um dos 256 registos X da CxM o seu estado de
ocupado/livre, e tabela de golos onde para cada golo se indica o tamanho corrente do
registo de activação e o número de variáveis unsafe que nele ocorrem pela última vez.
O código do compilador é constituído por um grande número de funções, muitas delas
recursivas, sendo o seu fluxo geral, durante o tratamento da cabeça ou de um golo da
cláusula, determinado pela estrutura do termo correspondente. O compilador executa
sempre, para cada cláusula, a seguinte sequência de tarefas:
• Faz uma passagem inicial pela cláusula para recolha de informação sobre as
suas variáveis. Essa informação, para cada variável, consiste no seguinte:
endereço, número de ocorrências, número de ordem do primeiro e último golo
7. Compilação
73
em que ocorre, número de ordem do argumento em que ocorre pela última vez no
seu último golo, e indicação se a sua primeira ocorrência na cláusula foi dentro
de uma estrutura.
• Com base na tabela de variáveis, determina o tipo das variáveis (temporárias,
permanentes ou parâmetros de unit), efectuando logo de seguida em relação às
variáveis permanentes, a sua localização nos registos de activação. Esta
operação envolve uma ordenação das variáveis, por forma que o trimming dos
registos de activação possa funcionar correctamente. Todos estes dados são
adicionadas à tabela de variáveis e à tabela de golos.
• Faz a atribuição de registos X às variáveis temporárias que ocorrem na cabeça
da cláusula ou no seu primeiro golo. O algoritmo de atribuição de registos é
descrito mais abaixo no ponto 7.4.
• Faz uma passagem pela cabeça da cláusula, gerando código de acordo com as
regras que se encontram definidas no apêndice B. Durante esta fase a tabela de
variáveis desempenha um papel fundamental no tratamento de todas as
referências a variáveis. Um caso que exige algum cuidados é o das estruturas que
ocorrem na cabeça das cláusulas: é necessário recorrer a uma pilha de termos
auxiliar e fazer uma gestão cuidada dos registos X, os quais, em tempo de
execução, irão ser usados como variáveis auxiliares.
• Gera código para o primeiro golo.
• No início do tratamento de cada golo da cláusula a partir do segundo, faz uma
atribuição de registos às variáveis temporárias que nele ocorrem. A geração de
código é feita segundo as regras do apêndice B e todas as referências a variáveis
passam pela consulta e eventual actualização da tabela de variáveis.
Alguns aspectos de mais detalhe do funcionamento do compilador e do código por
ele gerado merecem aqui referência:
• A
CxM
tem
instruções
especializadas
para
manipulação
de
variáveis
instanciadas com valores globais. O compilador detecta todas as oportunidades
de utilização dessas instruções para aumentar a eficiência do código gerado. Do
estudo das instruções que se encontram no apêndice B, conclui-se que existe a
garantia de uma variável ter um valor global, depois da execução das instruções:
PutXVariable Xi, Xj,
UnifyVoid N,
UnifyValue Xn ,
BuildValue Xn ,
UnifyVariable ψn , e BuildVariable ψn , com ψ ∈ {X,Y,Z}. Todos os descritores de
variáveis que se encontram na tabela de símbolos têm um indicador que é
posicionado sempre que o compilador gera uma destas instruções.
• O compilador tira sempre partido, do facto de o valor de uma variável
permanente ou de um parâmetro de unit se encontrar temporariamente num
registo, para gerar código mais eficiente.
7. Compilação
74
• Os golos que impliquem mudança de contexto necessitam de um tratamento
especial que é abaixo descrito no ponto 7.5.
• Ao contrário do que é indicado em [Warren 83], o nosso compilador só gera a
instrução PutUnsafeVariable Y n no último golo das cláusulas. Isto resulta da
decisão de adiar de um golo o trimming das variáveis permanentes. Em
alternativa àquela instrução, usamos a instrução PutVariable Yn que é mais
rápida e evita a transferência para o stack global de uma variável local, onde
teria um tempo de vida superior ao necessário.
• O problema da detecção de transbordo das pilhas de execução de CxLP é tratado
parcialmente em tempo de execução e parcialmente em tempo de compilação.
Em tempo de execução, a cada chamada de predicado é feito um teste ao espaço
livre na área dos stacks; caso seja inferior a 10 Kb considera-se ocorrência
transbordo. Entretanto se o compilador detectar que numa cláusula, entre duas
chamadas consecutivas, os stacks crescem mais do que 10 Kb, ele sugere ao
utilizador a rescrita da cláusula. Este deverá seguir o conselho se quiser garantir
o correcto tratamento de uma eventual situação de transbordo provocada pela
cláusula. Note-se que esta mensagem é de ocorrência muito pouco frequente, pois
a cláusula terá de conter um golo muito grande para isto acontecer. Este
esquema, além de ser simples, tem a vantagem adicional de ser muito eficiente,
pois localiza os testes de transbordo nas instruções de chamada de predicados.
• A instrução Allocate é sempre gerada, o mais longe possível do início no código
das cláusulas em que surge, por forma a ser evitada a criação desnecessária de
alguns registos de activação, em tempo de execução. Em geral, é colocada
imediatamente antes da primeira referência a uma variável permanente no
primeiro golo da cláusula ou, se esse golo não referir variáveis permanentes, é
colocada antes da instrução Call desse golo. O caso em que o primeiro golo é uma
das fórmulas especiais de CxLP, correspondentes ao uso dos operadores “>>”,
“>”, “<” ou “?”, impõe uma restrição adicional: a instrução Allocate deve de
aparecer algures antes da primeira instrução da CxM, que faça manipulação de
contextos.
• Um cut que ocorra como primeiro golo da cláusula, é traduzido na instrução
NeckCut. Um cut que ocorra mais no interior do corpo da cláusula, é traduzido
na instrução Cut Yn , em que Y n é uma variável permanente. Esta variável é
inicializada com o ponto de escolha corrente, no princípio do código do corpo da
cláusula, pela instrução GetLevel Y. Esta forma de implementar o cut
encontra-se descrita na referência [Warren 88].
• As disjunções são compiladas para um conjunto de predicados anónimos. As
operações cut nas disjunções implicam a adição de um argumento suplementar a
alguns deles.
7. Compilação
75
O compilador, incluindo o módulo que faz indexação de predicados, tem cerca de
2500 linhas de código, excluindo os comentários.
7.4. A tabela de variáveis
O compilador à medida que gera código, vai simulando alguns aspectos da execução
deste, com o objectivo de obter dados que fundamentem a introdução de optimizações.
Esses dados estão todos contidos na tabela de variáveis
Cada descritor de variável é constituído pelos seguintes campos:
• Var
Contém o endereço da variável a que corresponde este descritor.
O caso em que a variável é um parâmetro de unit é uma
excepção. Neste caso este campo contém uma constante inteira
com tag, representando o número de ordem do parâmetro na
unit. O campo Var constitui a chave de acesso aos descritores da
tabela.
• NOccurrences
Número de ocorrências da variável na cláusula.
• FirstGoal
Número de ordem do primeiro golo em que ocorre a variável.
• LastGoal
Número de ordem do último golo em que ocorre a variável.
• LastGoalArg
Número de ordem do último argumento em que ocorre a
variável, dentro do último golo.
• Type
Tipo da variável. O seu valor pertence ao tipo enumerado { temp,
perm, param }.
• IsUnsafe
Valor booleano usado só no caso de a variável ser permanente,
para indicar se ela é unsafe ou não.
• HasGlobalValue Durante o processo de compilação de uma cláusula, este campo
indica se correntemente existe a garantia de instanciação da
variável com um valor global (ou seja, uma constante, um
termo ou uma variável do stack global). Valor inicial: falso.
• WasReferenced
Indica se a variável já foi referenciada alguma vez durante a
geração de código. O código gerado na compilação da primeira
referência a uma variável deve, quando executado, fazer a sua
inicialização como variável livre. Valor inicial: falso, excepto
no caso dos parâmetros de unit que, por natureza, são
inicializados com valores provenientes do exterior da unit.
• FirstStruct
Indica se a variável tem a sua primeira ocorrência dentro de
uma estrutura. Importante para determinar se a variável deve
ser temporária ou permanente.
7. Compilação
• ParamIndex
76
Caso a variável seja um parâmetro de unit, este campo contém o
seu número de ordem.
• PermIndex
Se a variável for permanente, este campo contém a sua posição
dentro dos registos de activação associados à cláusula a que
pertence.
• TempIndex
Um variável independentemente do seu tipo pode, durante a
execução do programa, encontrar-se temporariamente num
registo X da CxM. O compilador à medida que vai gerando
código, vai tomando nota neste campo, do registo X onde ela se
encontra. O valor -1 indica que a variável correntemente não se
encontra em nenhum registo. Valor inicial: -1.
A maior parte da informação incluída na tabela de variáveis é recolhida durante a
fase de análise prévia da cláusula, sendo usada logo a seguir na determinação do valor
de alguns campos que ficam por preencher: Type, IsUnsafe, ParamIndex, PermIndex, e
WasReferenced.
Durante o processo de geração de código a maioria dos campos da tabela de
variáveis
não
sofre
qualquer
alteração.
As
excepções
são
as
seguintes:
HasGlobalValue, WasReferenced e TempIndex.
7.5. Algoritmo de atribuição de registos
O código gerado para um programa CxLP pode ser substancialmente melhorado,
através de uma cuidada atribuição de registos a variáveis temporárias, que reduza ao
mínimo
o número de instruções a executar. O facto de na CxM a passagem de
parâmetros ser efectuada através de registos, está na base da estratégia de atribuição
de registos que usamos, sendo usada de duas formas distintas.
A primeira forma resulta de serem vários os casos em que se pode associar uma
variável temporária a um registo que esteja envolvido na passagem de um parâmetro,
por forma a ser poupada a transferência correspondente à inicialização da variável. É
o que se passa por exemplo na cláusula seguinte:
append([],L,L).
Na forma mais naïve de tratar este caso, dá-se importância ao facto de dentro da
cláusula os registos X0, X1 e X2 já estarem ocupados pelos argumentos actuais da
chamada: desta forma atribui-se o primeiro registo livre - X3- à variável temporária
L. O código correspondente a esta atribuição de registos é o seguinte:
append/3: GetNil X0
GetVariable X3,X1
GetValue X3,X2
Proceed
7. Compilação
77
Mas uma análise mais cuidada, permite concluir que é vantajoso associar o registo
X1, onde vem o segundo argumento de append/3, à variável L, já que ela é inicializada
com o valor desse argumento. O código gerado para a nova atribuição de registos fica
mais compacto:
append/3: GetNil X0
GetValue X1,X2
Proceed
A outra forma de tirar partido da forma de passagem de parâmetros, consiste em
fazer uma análise prévia do próximo golo a ser compilado, e associar, desde logo,
determinadas variáveis temporárias a registos que intervenham na passagem de
parâmetros, e que já estejam, de qualquer forma, comprometidos com a passagem dos
valores das variáveis. Por exemplo a atribuição óptima de registos para a cláusula:
append([H|L0],L1,[H|L2]) :- append(L0,L1,L2).
é {L0/X0, L1/X1, L2/X2}, à qual corresponde o código:
append/3: GetList X0
UnifyVariable X3
UnifyVariable X0
GetList X2
UnifyVariable X3
UnifyVariable X2
Execute append/3
Neste caso o código da cabeça da cláusula está organizado de tal forma que da sua
execução resulta o carregamento automático dos registos para a chamada do golo que
se encontra no corpo.
Infelizmente, ao contrário do que se passa nestes dois casos, nem sempre é possível
encontrar uma atribuição de registos que permita a introdução de
optimizações, já
que podem surgir conflitos irresolúveis entre os dois critérios que considerámos. Por
exemplo na cláusula:
p(X,Y) :- q(Y,X).
a sua cabeça recomenda a atribuição de registos {X/X0, Y/X1}, mas o seu corpo
recomenda {Y/X0, X/X1}. Nesta situação extrema, qualquer que seja a atribuição
escolhida é necessário recorrer ao uso de um registo auxiliar e a diversas operações de
transferência entre registos. Eis o melhor código que é possível conseguir neste caso:
p/2:
PutValue X0,X2
PutValue X1,X0
PutValue X2,X1
Execute q/1
Ocorrem na prática muitas situações de natureza menos simples do que as três que
analisámos, para as quais a determinação de uma boa atribuição de registos, que leve
em conta todas as restrições existentes, exige alguma elaboração. Em [Debray 86] e
[Janssens 88] são apresentados algoritmos que produzem bons resultados9. No
9Apesar de nenhum deles ter a pretensão de efectuar uma atribuição de registos ideal.
7. Compilação
78
entanto, estes algoritmos têm a desvantagem de aumentar de forma muito sensível o
tempo de compilação, pois fazem uma análise relativamente complexa da cláusula a
ser compilada, consumindo em particular bastante tempo na detecção e tratamento
prévio dos conflitos.
Como no nosso sistema considerámos o tempo de compilação como um factor a ser
reduzido, eventualmente à custa de uma pequena perca de qualidade do código gerado,
desenvolvemos um algoritmo de atribuição de registos optimista, no sentido em que
não consome demasiado tempo a prevenir-se contra a ocorrência de eventuais
conflitos. Geralmente, só depois da ocorrência destes, é que são tomadas providências
para os resolver. Esta ideia é semelhante à do algoritmo II (conflict resolution) em
[Debray 86], apesar de ser realizada de uma forma diferente, em termos de forma e
conteúdo,
para
evitar
a
manipulação
de
conjuntos
pelo
algoritmo.
Este
é
suficientemente bom para gerar código óptimo nos três exemplos atrás apresentados,
não sendo muito frequente a produção de código de qualidade inferior.
O nosso algoritmo de atribuição de registos começa a actuar logo depois de
terminada a primeira fase da compilação, que corresponde ao preenchimento da
tabela de variáveis. Ele ocupa-se em primeiro lugar da cabeça e do primeiro golo da
cláusula, fazendo um percurso sequencial dos seus argumentos: para cada variável
temporária encontrada a nível superficial na n-ésima posição que ainda não tenha
registo associado, se o registo de ordem n estiver disponível, ele fica imediatamente
adstrito à variável. Desta forma, parte das variáveis temporárias ficam logo com
registo atribuído. Mais tarde, durante a geração de código para a cabeça e para o
primeiro golo da cláusula, sempre que for referenciada uma variável temporária sem
registo associado, é-lhe feita simplesmente a atribuição do registo livre de número de
ordem mais baixo.
As situações de conflito ocorrem, quando se torna necessário usar um registo para
passagem de um parâmetro na derivação de um golo, e ele está ligado a uma variável
temporária cujo valor não se pode perder, pelo facto de ser usada ainda mais à frente.
Nesse caso, a variável temporária tem de ser associada a um registo diferente, e o seu
conteúdo transferido para este registo, o que é feito por geração da instrução PutValue
Xi, Xj. Para a escolha do novo registo Xj ser efectuada, é feita uma análise do primeiro
golo da cláusula com o objectivo de determinar se essa variável ocorre mais à frente ao
primeiro nível dos argumentos do golo. Se assim for, é escolhido o registo
correspondente à sua posição no golo; caso contrário, usa-se simplesmente o registo
disponível que tenha menor ordem. No primeiro caso, a escolha pode
por
coincidência, incidir sobre um registo já atribuído a uma variável temporária, o que
7. Compilação
79
provoca nova situação de conflito, que é resolvida aplicando recursivamente o
algoritmo.
No tratamento dos golos da cláusula a partir do segundo não surgem conflitos, o
que simplifica bastante as coisas. Para cada golo procede-se à anulação das
associações entre registos e variáveis que venham de trás, e analisam-se os seus
argumentos para a atribuição de registos às variáveis temporárias que ocorram
isoladas ao nível da superfície. As outras variáveis temporárias são tratadas quando
forem referenciadas pela primeira vez pelo compilador, durante a fase de geração de
código, sendo ligadas a registos que estejam disponíveis na altura.
7.6. Golos que mudam de contexto
7.6.1. Passagem de parâmetros para units
Na geração de código para fórmulas de extensão, houve o cuidado de reduzir ao
mínimo os inconvenientes causados ao algoritmo de atribuição de registos pelos
padrões de código gerado para as mudanças de contexto. Para isso, foi decidido que na
passagem de argumentos para os designadores de unit não fosse obrigatório usar os
registos da CxM a partir do registo X0, como se faz nas invocações de predicados, mas
antes que existisse a liberdade de usar um conjunto consecutivo de registos qualquer.
Desta forma os designadores de unit nas fórmulas de extensão não se tornam
obstrutivos à introdução de optimizações no golo em que aparecem.
Por exemplo na cláusula
a(X,Y) :- u(Y)>>b(X).
se a variável Y tivesse de ser passada no registo X0 para a unit u, o prejuízo seria
grande pois, não podendo X0 ser ligado à sua variável natural X, seríamos obrigados a
efectuar múltiplas transferências entre registos no código gerado. Mas existindo a
possibilidade de passar Y no registo X1, tudo se simplifica de tal forma, que não chega
mesmo a ser necessário fazer qualquer transferência entre registos. O código
produzido neste caso reduz-se ao seguinte:
PushContext u 1 0
Call b/1
PopContext
Proceed
no qual o segundo argumento de PushContext indica que os parâmetros actuais da
unit, são passados usando os registos a partir de X1 inclusivamente.
Esta regra para a passagem de parâmetros em designadores de units aplica-se da
mesma forma a mudanças de contexto provocadas por invocação de nomes de
predicado importados.
7. Compilação
80
7.6.2. Tratamento de referências a parâmetros de units
Um outro problema que as mudanças de contexto originam tem a ver com o código
de tratamento de referências a parâmetros de units, que sejam efectuadas dentro de
fórmulas de extensão. Consideremos a seguinte definição parcial, da unit u que
contêm o predicado a/2:
unit u(P).
…
a(X,Y) :- v(Y)>>b(X,P).
…
À primeira vista o código gerado para a cláusula parece dever ser o seguinte
(compare com o exemplo anterior):
PushContext v 1 0
PutValue Z0 X1
Call b/1
PopContext
Proceed
No entanto este código não está correcto pois a instrução PutValue Z0 X1 será
sempre executada após concretizada a mudança de contexto, numa situação em que Z0
já não refere o parâmetro P, como pretendido, mas sim o primeiro parâmetro da unit
v. Este problema pode ser facilmente resolvido pela transferência de Z0 para um
registo antes de ser feita a mudança de contexto. O código corrigido fica assim:
PutValue Z0 X2
PushContext u 1 0
PutValue X2 X1
Call b/1
PopContext
Proceed
Três outras situações em que este problema ocorre também a propósito do
parâmetro de unit P são indicadas seguidamente:
unit u(P).
…
a(X,Y) :- u(Y) >> v(P) >> b(X).
a(X) :- < b(X,Y,P).
a(X) :- ? b(X,P).
…
Quando o compilador processa golos cuja execução possa de alguma forma provocar
uma mudança de contexto, ele faz um percurso preliminar completo de todas as partes
dos golos afectadas pela mudança, gerando instruções de transferência para registos
livres, dos valores de todos os parâmetros de unit que sejam referidos. Esses registos
desempenham depois o papel de parâmetros de unit em todo o código gerado para o
golo, mesmo nas partes não afectadas pela mudança de contexto para máxima
eficiência.
7. Compilação
81
7.7. Indexação
Neste ponto são discutidos os mecanismos de indexação usados na CxM. Eles
resultaram de uma extensa revisão do método usado na WAM, que foi adaptado às
exigências do nosso sistema. Para facilitar a compreensão das ideias apresentadas
neste subcapítulo, vamos utilizar diversas vezes como exemplo, um predicado - a/1 com a seguinte definição:
a(1).
a(2).
a(1).
a(3).
a(1).
a(X) :- write(var).
a(2+3).
a(2).
7.7.1. Índice
O objectivo do índice é o de reduzir o tempo dispendido em retrocesso superficial
(shallow backtraking) durante a execução dos programas. Isso consegue-se através de
uma filtragem das cláusulas de um predicado candidatas a emparelhamento, após
cada chamada. Em geral, podem ser ignoradas todas aquelas em relação às quais é
possível garantir antecipadamente falhanço nas unificações das cabeças das
cláusulas, com base nos valores dos argumentos da chamada.
No esquema de indexação da CxM, a selecção das cláusulas é efectuada, tal como na
WAM, apenas com base no valor do primeiro dos argumentos da chamada. Por esse
motivo o registo X0 da máquina é denominado de registo de indexação.
Antes de entrarmos nos aspectos práticos da construção dos índices na CxM,
vejamos primeiro a forma como no código de um predicado, é feita a ordenação das
suas diversas cláusulas constituintes. Conforme se exemplifica seguidamente usando
o predicado a/1, isso é feito, fazendo preceder o código de cada cláusula, por uma
instrução da família TryMeElse/RetryMeElse/TrustMe.
a/1:
C1a:
C1:
C2a:
C2:
C3a:
C3:
C4a:
C4:
C5a:
C5:
C6a:
C6:
TryMeElse C2a
GetConstant 1 X0
Proceed
RetryMeElse C3a
GetConstant 2 X0
Proceed
RetryMeElse C4a
GetConstant 1 X0
Proceed
RetryMeElse C5a
GetConstant 3 X0
Proceed
RetryMeElse C6a
GetConstant 1 X0
Proceed
RetryMeElse C7a
PutConstant “var” X0
write/1 ; predicado de sistema
Proceed
7. Compilação
C7a:
C7:
C8a:
C8:
82
RetryMeElse C8a
GetStruct +/2 X0
UnifyConstant 2
UnifyConstant 3
Proceed
TrustMe
GetConstant 2 X0
Proceed
A cadeia de instruções TryMeElse/RetryMeElse/TrustMe, é percorrida em tempo de
execução, no caso em que X0 contém uma referência a uma variável livre (a qual não
permite que seja efectuada qualquer filtragem), ou quando, por algum motivo, não foi
construído um índice. Com ela, todas as cláusulas alternativas de um predicado são
consideradas na ordem correcta. Quando ocorre a adição ou remoção de cláusulas de
um predicado, a cadeia que lhe corresponde é fácil de alterar, pois o código das
cláusulas não precisa de se encontrar numa zona contígua de memória.
7.7.2. Índice rápido
A ideia subjacente ao esquema principal de indexação da CxM - índice rápido - é
muito simples. Baseia-se na determinação de todas as possíveis sequências de
cláusulas a serem percorridas em tempo de execução, em função do valor do registo X0.
As cadeias de cláusulas são traduzidas pelo compilador em sequências de
instruções Try/Retry/Trust, sendo a selecção da sequência correspondente ao valor de
X0 efectuada por instruções especiais. O índice rápido inicia-se sempre pela instrução
SwitchOnTerm V, C, L, S, que efectua um salto para uma das etiquetas V, C, L, ou S
consoante o tipo do valor de X0, seja respectivamente uma variável, uma constante,
uma lista não vazia ou uma estrutura. Entretanto se no primeiro argumento das
cláusulas de um predicado aparecerem pelo menos duas constantes diferentes e/ou
duas estruturas com functores diferentes, são ainda usadas, respectivamente, as
instruções SwitchOnConstant Tablesize Table Else, e SwitchOnStruct Tablesize Table
Else, as quais permitem determinar rapidamente o início da cadeia de cláusulas
associada a um valor de X0, usando tabelas de hash.
Eis o índice rápido para o nosso predicado a/1 (note que as etiquetas Ci estão
definidas acima, no código das cláusulas do predicado).
a/1_idx:
L1:
T1:
V1:
V2:
V3:
SwitchOnTerm C0, L1, C6, L2
SwitchOnConstant 4, T1, C6
1: V1,
2: V2,
3: V3
Try C1
Retry C3
Retry C5
Trust C6
Try C2
Retry C6
Trust C8
Try C4
Trust C6
7. Compilação
L2:
83
Try C6
Trust C7
Neste código podemos observar que existem 4 cadeias de cláusulas (etiquetadas por
V1, V2, V3 e L2), sendo a mais extensa a que corresponde à constante 1. Esta cadeia, que
surge no código etiquetada por V1, é constituída pelas cláusulas de ordem 1, 3, 5, e 6.
Outro aspecto que merece referência é o facto de a cláusula nº 6 aparecer em todas as
cadeias: isto é resultado do seu argumento ser uma variável.
Só as cadeias de cláusulas não singulares são são representadas por instruções
Try/Retry/Trust. As cadeias constituídas por uma única cláusula são tratadas
mediante um simples salto para o início do seu código dentro do predicado. Isto é o que
se passa com as referências à etiqueta C6 nas duas primeiras instruções do índice.
Entretanto as referências a cadeias de cláusulas vazias são representadas pelo
endereço da instrução Fail. Este é um caso que não aparece no nosso exemplo visto
nele intervir uma variável.
7.7.3. Índice compacto
A técnica de indexação que acabou de ser descrita foi a mais eficiente que
conseguimos conceber com base apenas no registo X0, sendo por isso usada na CxM na
maioria dos casos. Mas existem algumas circunstâncias em que é desaconselhável o
seu uso, por se verificar a criação de índices excessivamente grandes. Isso acontece
para predicados com numerosas cláusulas, nas quais o primeiro argumento apresenta
valores muito diversificados, além de diversas ocorrências de variáveis. Recordemos
que para cada valor diferente do primeiro argumento é criada uma cadeia distinta de
instruções do tipo Try/Retry/Trust, e ainda que as cláusulas com variáveis ocorrem
em todas essas cadeias.
Quando uma situação destas é descoberta pelo compilador, este constrói um índice
de outro tipo, que é um pouco menos rápido, mas, em contrapartida,
é
significativamente mais compacto. Partindo do esquema de indexação descrito no
ponto anterior, a ideia que seguimos foi a de por em evidência todas as referências a
cláusulas que tenham uma variável por primeiro argumento. Para isso o compilador
define uma partição na sequência de cláusulas, na qual cada subsequência obedece à
seguinte disjunção de condições: ou é uma sequência constituída por uma única
cláusula com variável no primeiro argumento, ou então é uma sequência máximal de
cláusulas não tendo variáveis por primeiro argumento. As diferentes subsequências
da
partição
são
exploradas
usando
basicamente
instruções
TryMeElse/RetryMeElse/TrustMe sendo cada subsequência tratada a nível interno
pelo método anterior. Neste esquema a primeira instrução do índice é sempre
JumpOnVar Label que testa se X0 é uma variável livre, caso em que é dado um salto
para o início do código do predicado, que é identificado pela etiqueta Label.
7. Compilação
84
No caso do predicado a/1, que temos vindo a usar como exemplo, existem as
seguintes três subsequências de cláusulas: [1,2,3,4,5], [6], [7,8]. O código gerado pelo
compilador, se ele tomasse a opção de usar este tipo de índice, o que neste caso não é
verdade, seria o seguinte:
a/1_idx2: JumpOnVar C0
T1:
V1:
TryMeElse L1
SwitchOnConstant 4, T1, fail
1: V1,
2: C2,
3: C4
Try C1
Retry C3
Trust C5
L1:
Retry C6
L2:
TrustMe
SwitchOnTerm internal_error, C8, fail, C7
No tratamento da segunda subsequência, pelo facto ela se resumir a uma única
cláusula, não foi necessário seguir o caso geral, que prevê a utilização da instrução
RetryMeElse seguida do código da subsequência: no caso presente esse código
resumir-se-ia a um salto para a etiqueta C6, pelo que a instrução Retry C6 pode ser
usada com vantagem.
Este índice é menos rápido que o anterior, porque durante a sua exploração é
efectuado geralmente um maior número de operações de manipulação de pontos de
escolha as quais são das mais pesadas operações da CxM. Note-se inclusivamente que
em muitas circunstâncias podem existir em simultâneo dois pontos de escolha activos
da responsabilidade de um mesmo índice.
7.7.4. Índice super-rápido
Em alguns casos particulares, mas que ocorrem com frequência em zonas
críticas10 de programas CxLP, o compilador usa duas instruções de indexação, que são
especializações da instrução SwitchOnTerm, e que permitem efectuar ganhos
significativos de velocidade. São as instruções SwitchOnList e SwitchOnFunctor.
A instrução SwitchOnList é usada em substituição da instrução SwitchOnTerm no
índice de todos os predicados que tenham as seguintes duas características: possuir
uma única cláusula com uma lista não vazia por primeiro argumento, e possuir uma
única cláusula com uma constante por primeiro argumento, sendo essa constante o
átomo []. É admitida a existência de mais cláusulas, mas estas terão de ter variáveis ou
estruturas no primeiro
argumento.
Predicados
iteradores
sobre
frequentemente esta forma.
10Uma zona crítica, é um segmento de código de execução muito frequente.
listas
têm
7. Compilação
85
A primeira instrução da cláusula que tem o átomo [] por primeiro argumento, é
sempre GetNil X0 e a primeira instrução da cláusula que contém a lista, é GetList X0 .
Estas duas instruções repetem muitos testes e acções efectuadas pela instrução
SwitchOnTerm, o que explica a criação da instrução SwitchOnList, já que esta
combina a funcionalidade de SwitchOnTerm, GetNil X0 e GetList X0 . Assim quando a
instrução SwitchOnList passa o controlo para uma das duas cláusulas especiais, ela
salta por cima da primeira instrução, ignorando-a simplesmente.
A instrução SwitchOnFunctor tem características semelhantes às da instrução
SwitchOnList com a diferença de se aplicar a outros fuctores que não o functor
ponto “./2”, e de não impor qualquer restrição em relação às constantes no primeiro
argumento.
O ganho que esta pequena optimização proporcionou foi de cerca de 20% no caso do
predicado append/2, testado num computador Vax.
7.7.5. Na WAM
A maior parte das técnicas de indexação usadas na CxM, e que foram atrás
apresentadas, constituem adaptação de ideias já presentes na WAM, sendo importante
referir que, por exemplo, o nosso índice compacto é semelhante aos índices da
máquina de D. Warren. A única diferença essencial entre eles reside no facto de na
WAM, as instruções de indexação serem embutidas pelo compilador no próprio código
das
cláusulas,
ficando
misturadas
com
as
instruções
TryMeElse/RetryMeElse/TrustMe, o que favorece ainda mais a compacidade do
código. No entanto a flexibilidade de alteração dos predicados fica por causa disso
muito comprometida, já que a adição ou remoção de cláusula impõe a recompilação
integral do predicado.
7.8. Compilador optimizador
A presente versão do sistema (CxLP v0.9) não inclui um compilador que faça
análise global de programas. Um tal programa seria útil para processar os programas
que já tenham atingido a sua forma final, e se preparam para ser usados pela
comunidade de utilizadores. No entanto foi já previsto o suporte para um tal eventual
compilador que admite-se, será escrito em CxLP.
Um compilador optimizador precisa de fazer uma distinção entre predicados
dinâmicos e predicados estáticos, pois as optimizações que ele efectua baseiam-se na
circunstância de estes últimos não serem modificáveis durante a execução dos
programas.
Em relação aos predicados estáticos, o compilador optimizador, depois de para
cada um deles analisar a definição e condições de utilização, compila as suas
cláusulas gerando listas de instruções da CxM. Essas cláusulas e respectivo código são
7. Compilação
86
depois adicionadas à base de dados através o predicado de sistema assert/2 (ver
exemplo do utilização no apêndice A). Terminada a compilação de cada predicado, o
compilador declara-o estático, usando a primitiva de sistema static/2. Daí em diante
o predicado compilado não pode sofrer qualquer alteração que não seja a remoção
integral por meio do predicado abolish/2.
Quanto aos predicados dinâmicos, eles poderão ser tratados pelo compilador do
sistema, o qual é invocado usando o predicado assert/1.
7.9. Outras linguagens
No âmbito da linguagem Prolog, é relativamente frequente a utilização de
pré-processamento, com tradução para Prolog, para a prototipagem de certas
linguagens. Este método tem a grande vantagem de constituir a mais rápida forma
disponível para implementar uma nova linguagem, mas tem a desvantagem de o
sistema resultante não ser muito prático de usar. Efectivamente o sistema torna-se
geralmente muito lento na fase de desenvolvimento dos programas, pois ao tempo de
compilação se associa sempre o tempo de pré-processamento; além disso existe o
inconveniente de os programas ao serem listados, não aparecerem na forma original
em que foram introduzidos, mas sim sob a forma de código processado.
Uma alternativa ao uso de pré-processamento, que resolve estes dois problemas, e
que em alguns casos exige um esforço não muito maior de implementação, consiste na
adaptação do compilador existente no sistema CxLP, à geração de código para as
cláusulas da nova linguagem. Isto torna-se especialmente prático se a semântica da
linguagem permitir aproveitar sem alteração, algumas das mais importantes
componentes do compilador, como a parte de gestão da tabela de variáveis ou o
algoritmo de atribuição de registos.
Evidentemente que se a nova linguagem for muito mais potente que a CxLP a
inadequação da máquina CxM vai revelar-se na baixa velocidade de execução dos
programas. Mas existem casos, como por exemplo o do UNL-Prolog [Porto 87], em que
desta forma se pode obter uma implementação plenamente satisfatória da linguagem.
87
8
Outras Componentes do Sistema
8.1. Predicados de sistema
Nesta implementação de CxLP decidimos considerar todos os predicados de sistema
como fazendo parte integrante da própria definição da linguagem. A alternativa seria
situá-los ao mesmo nível dos predicados definidos pelo utilizador, agrupando-os
dentro de uma unit pré-definida, de onde teriam de ser importados antes de poderem
ser utilizados. Foram várias as razões da opção tomada:
• Poupa-se o trabalho de escrita das declarações de importação, que seriam
sempre grande número;
• Dispensa a utilização do mecanismo de importação de predicados, que em CxLP
é uma operação com alguns custos de eficiência, por envolver uma mudança de
contexto;
• Os predicados de sistema comportam-se como estando definidos localmente em
todas as units, o que simplifica a sua utilização em relação ao método
alternativo, no qual teríamos de considerar sempre o facto de a sua execução ser
feita num contexto diferente: eventualmente muitos teriam de ser chamados,
memorizando o contexto corrente com o operador de salvaguarda de contexto
“>”;
8. Outras Componentes do Sistema
88
• Com esta opção a CxLP torna-se uma extensão directa do Prolog podendo
executar directamente os seus programas11.
A lista completa dos predicados de sistema da versão corrente da CxLP, encontra-se
em apêndice para tornar mais prática a sua consulta. Muitos deles são adaptações dos
predicados que se encontram definidos na referência clássica [Clocksin 81], os quais
geralmente se consideram constituir o núcleo básico de predicados de sistema de
qualquer implementação de Prolog. Dentro dessa linha tentámos definir também um
conjunto de predicados reduzido, mas suficientemente completo, adequado à
linguagem CxLP. Os novos predicados introduzidos relacionam-se principalmente
com a manipulação de units e contextos.
Descrevemos seguidamente de forma sucinta os aspectos mais relevantes da
implementação dos predicados de sistema.
8.1.1. Predicados deterministas escritos em C
Recordemos que na técnica de interpretação usada na máquina CxM - código
threaded - o código gerado é constituído essencialmente por uma sequência de
endereços das funções que definem as instruções da máquina abstracta. Ora como
cada predicado de sistema determinista, escrito em C, está também implementado
numa função, surge imediatamente a ideia de inserir directamente o seu endereço no
código gerado.
Esta foi a solução adoptada. Tem a particularidade interessante de colocar os
predicados de sistema ao mesmo nível das instruções da máquina abstracta, com os
benefícios de eficiência que daí advêm. Entretanto este método obriga a que, na
programação dos predicados de sistema, tenham de ser tomados os mesmos cuidados
que são tomados na programação das instruções da máquina abstracta, ou seja: as
funções que definem os predicados não têm argumentos, não têm variáveis locais, e
terminam com a macro JumpNext() (cf. 6.3.4).
8.1.2. Predicados de sistema não deterministas escritos em C
Alguns dos mais importantes predicados de sistema não deterministas são escritos
parcialmente em C, sendo o controlo do não-determinismo feito com código CxM. As
sequências de instruções utilizadas para esse efeito são extremamente eficientes, mas
infelizmente não podem ser geradas pelo compilador a partir de qualquer definição de
predicado escrito em CxLP, por corresponderem a padrões de código considerados à
partida como absurdos. Por esse motivo para cada predicado destes é usada uma
definição aproximada escrita em CxLP, incluída no ficheiro de inicialização do
11Na prática isto não é bem assim pois o Prolog não é uma linguagem estandartizada. Quando
se transporta um programa Prolog de uma implementação para outra é muitas vezes
necessário fazer algumas alterações.
8. Outras Componentes do Sistema
89
sistema CxBoot, sendo efectuada, depois da compilação, uma pequena correcção ao
código gerado.
Este é um pequeno truque que permite duplicar a eficiência do predicado repeat/0 e
que foi usado também nos predicados: clause/2, retract/1, visible_predicate/1,
invisible_predicate/1,
imported_predicate/2,
e
builtin_predicate/1.
Vamos
exemplificá-la com os predicados repeat/0 e clause/2.
repeat/0
A definição do predicado repeat/0 que se encontra no ficheiro CxBoot e que se
encontra obviamente errada, é a seguinte:
repeat.
repeat.
Desta forma o compilador ao processar este predicado gera o seguinte código
máquina:
repeat/0:
L:
TryMeElse L 0
Proceed
TrustMe 0
Proceed
Depois da cláusula compilado o predicado, a primeira instrução da segunda cláusula é
então substituída pela instrução de RetryMeElse, resultando o código:
repeat/0:
L:
TryMeElse L 0
Proceed
RetryMeElse L 0
Proceed
que já corresponde a um repeat/0 correcto.
Note-se entretanto que a utilização da definição habitual:
repeat.
repeat :- repeat.
resulta em código de muito inferior qualidade:
repeat/0:
L:
TryMeElse L 0
Proceed
TrustMe 0
Execute repeat/0
Com efeito neste segundo método, por cada iteração são executadas quatro instruções
(em vez de duas) e é criado e destruído inutilmente um ponto de escolha.
clause/2
O predicado de sistema clause/2 tem de manter um estado interno que lhe permita
determinar a próxima solução a gerar. De entre as vantagem que o método de
implementação do repeat/0 mostrou, existe uma da qual tiramos partido para
resolver o problema: trata-se do facto de ser usado sempre o mesmo ponto de escolha
durante toda a actividade do predicado. A nossa solução passa pela adição de novos
campos ao ponto de escolha para funcionarem como variáveis de estado, o que se
consegue facilmente pela adição de argumentos artificiais ao predicado associado.
8. Outras Componentes do Sistema
90
A definição de clause/2 que se encontra no ficheiro de inicialização do sistema usa
dois predicados auxiliares - $_clause/2 e $_clause/3 - o primeiro dos quais está
escrito em C:
clause(H,B) :- $_clause(H,B,[]).
$_clause(H,B,_) :- $_clause(H,B).
$_clause(H,B,_) :- $_clause(H,B).
Após a compilação destas definições, o código gerado para $_clause/3 é sujeito a
uma alteração interna semelhante à que foi efectuada para o predicado repeat/0, o que
converte aquele predicado também num gerador infinito.
O terceiro argumento de $_clause/3 é artificial, funcionando como variável de
estado do predicado $_clause/2 cujo estado inicial é representado pelo átomo [].
Quando não há mais soluções a gerar, a instrução da CxM DiscardAndFail é chamada
do interior de $_clause/2, sendo anulado o ponto de escolha.
8.1.3. Predicados de sistema escritos em CxLP
Por uma questão de conveniência muitos predicados de sistema foram escritos
totalmente em CxLP, como por exemplo: consult/1, reconsult/1, listing/0, listing/1, e
all/0. Todos os predicados carregados na unit [] no momento em que é executado o golo
“$_protect_all” passam a ser considerados predicados de sistema. Este golo é
executado automaticamente logo após o carregamento do ficheiro inicialização,
CxBoot.
8.2. Analisador sintáctico
Uma componente importante do sistema CxLP é o analisador sintáctico, que serve
para fazer a tradução de representações textuais de termos nas suas representações
internas. A sintaxe suportada é a dita de Edimburgo (usada habitualmente no Prolog),
não tendo sido necessário introduzir grandes
modificações
motivadas
pelas
características especiais da CxLP. Realmente a única alteração registada foi a da
adição de suporte para a detecção de referências a parâmetros de units, nos termos
lidos.
A sintaxe Edimburgo é definida por uma gramática pertencente à categoria das
gramáticas de operadores [Aho 86], que são conhecidas pela relativa facilidade de
escrita de parsers do tipo shift-reduce eficientes para elas. A definição do analisador
sintáctico, que neste caso recebe o nome de parser de precedência de operadores, passa
pela definição de relações de precedência entre a maior parte dos símbolos terminais
da gramática. Os símbolos usados para designar essas relações são os símbolos, “<”,
“>”, e “=”.
O parser funciona da seguinte forma: à medida que vai analisando o texto de
entrada da esquerda para a direita, vai empilhando todos os símbolos terminais até
que apareca um par relacionado por >; então começa a descer na pilha até encontrar
8. Outras Componentes do Sistema
91
um par de símbolos terminais relacionados por <; o conjunto de terminais delimitado
por < e > é reduzido; e o processo continua até que o termo em análise tenha sido
reduzido no seu todo.
A parte mais importantes da definição do analisador consiste na determinação da
(eventual) relação de precedência entre cada par de símbolos. Para os pares que não
envolvem operadores, esta relação tem carácter estático, podendo ser definida num
quadro de duas entradas. No caso de dois operadores de diferentes prioridades, op1 e
op2, se op1 tiver prioridade superior a op2 então a relação de precedência é a inversa,
isto é op1< op2. Finalmente para dois operadores de igual prioridade, a relação de
precedência é determinada com base nas suas associatividades. As regras relativas a
este caso podem também ser codificadas numa tabela de duas entradas.
No nosso sistema seguimos muito de perto a descrição pormenorizada de um
analisador sintáctico para Prolog, que se encontra na referência [Kluzniak 85] (págs.
203-212). Nesta referência encontra-se inclusivamente uma implementação completa
do analisador escrita em Prolog (págs. 264-272). No entanto não usámos esse código
directamente pois as nossas exigências de eficiência geral do sistema, em particular
do processo de compilação, impunham um analisador escrito completamente em C.
8.3. Tratamento de erros
No decurso da execução de programas CxLP muitos tipos de erros podem ocorrer
sendo assinalados por mensagens apropriadas. Os erros que mais importantes são os
seguintes: divisão por zero, erro na leitura de um termo, chamada de um predicado de
sistema com argumentos errados, falta de memória na área de código, transbordo das
pilhas de execução e execução de uma fórmula de reposição de contexto sem que
previamente tenha sido salvaguardado qualquer contexto. No nosso sistema todos
estes erros, com excepção dos erros de sintaxe, são fatais pois provocam a imediata
reinicialização da máquina e o relançamento do monitor de comandos.
Para proporcionar às aplicações CxLP algum controlo sobre situações de erro, foi
definida a primitiva de sistema error_handler/1, que permite indicar um predicado
alternativo ao monitor de comandos. No entanto, atendendo a que nessa altura todo o
contexto do erro se encontra já irremediavelmente perdido, geralmente esse predicado
pouco mais poderá fazer de útil, do que actuar como um monitor de comandos
específico da aplicação.
8.4. Colector de lixo do heap
Na CxM são mantidas todas as técnicas inerentes ao funcionamento da WAM que
têm por objectivo manter um certo controlo sobre o consumo de memória, e que são as
seguintes:
8. Outras Componentes do Sistema
92
• Repartição dos dados criados em tempo de execução por duas diferentes áreas stack local e heap - para possibilitar recuperação de espaço no stack local
durante a exploração dos ramos deterministas das árvores de derivação.
• Utilização de LCO (last call optimization) para incrementar o volume de
memória recuperado no stack local durante as fases deterministas de execução
dos programas.
• Recuperação de memória no stack local, heap e trail sempre que ocorre
retrocesso.
• Não memorização no trail das variáveis que vão deixar de existir quando for
feito retrocesso para o ponto de escolha corrente.
• Recuperação de memória no stack local e trail resultante da execução do
predicado cut.
Um aspecto importante do esquema apresentado, é o facto de a recuperação de
espaço do heap só ser efectuada em retrocesso, o que implica que os dados incluídos no
heap tenham em geral um tempo de vida bastante superior à dos dados contidos no
stack local. Não é pois de surpreender que, durante a execução dos programas, uma
parte importante do conteúdo do heap seja constituída por informação redundante.
Assim nos casos em que a ocupação do heap se aproxima do seu limite máximo, é
importante que sejam tomadas medidas para nos libertarmos do lixo nele contido, já
que a alternativa seria a de o programa não poder continuar a correr. O problema da
detecção dos termos redundantes e posterior compactação do heap, é um problema
complexo mas bastante bem estudado no caso da WAM, existindo mesmo descrições
publicadas de alguns algoritmos. Em geral nestes algoritmos distinguem-se duas
fases: na primeira fase é efectuada uma busca exaustiva de todos os termos acessíveis
os quais são marcados de uma forma especial; na segunda fase é feita a compactação
do heap sendo eliminados todos os termos não marcados. A adaptação de qualquer
destes algoritmos à CxM não é muito complicada pois basta considerar, na
determinação dos termos acessíveis, os novos objectos presentes no stack local: as
instâncias de unit e os registos históricos.
A escrita do módulo de colecta de lixo da CxM, que só por si é suficientemente
complexa para constituir um projecto de programação autónomo, está em fase de
desenvolvimento pelo aluno finalista de Eng. Informática e bolseiro António Páscoa.
O algoritmo que está a ser usado como base do trabalho é o descrito na referência
[Appleby 88]. Eventualmente será tirado bom partido dos mecanismos aí descritos
para recolha de lixo segmentada, os quais permitem considerar individualmente
segmentos do heap delimitados implicitamente
por
dois
pontos
de
escolha
consecutivos. Esperamos que a utilização desta técnica, orientada por uma cuidadosa
8. Outras Componentes do Sistema
93
política de aplicação, permita reduzir consideravelmente o tempo total dispendido
nesta tarefa.
8.5. Colector de lixo da área de código
A eliminação de cláusulas usando por exemplo a primitiva retract/1 levanta um
problema importante: em geral quando uma cláusula é removida, o espaço de
memória por ela ocupado não pode ser imediatamente reaproveitado, pois existe a
possibilidade de ela estar ligada a uma chamada de predicado ainda activa ou ser
reactivada após retrocesso.
Outro problema semelhante a este, ocorre quando um índice ou um segmento de
código de ligação de nome importado é invalidado. O espaço ocupado também não pode
ser libertado imediatamente, pois também eles podem estar envolvidos numa
chamada ainda activa.
Estes problemas foram resolvidos por recurso a um colector de lixo adaptado às
circunstâncias. O colector de lixo da área de código recorre a uma tabela onde vão
sendo memorizados os endereços dos objectos eliminados durante a execução dos
programas. Em condições de falta de memória - tabela cheia ou área de código
esgotada -, o algoritmo percorre os pontos de escolha e registos de activação que se
encontram no stack local, obtendo todas as referências neles feitas a código CxM.
Estas referências são depois usadas para determinar de entre os objectos eliminados,
todos aqueles que são, directa ou indirectamente, acessíveis. O espaço ocupado pelos
objectos não acessíveis é então libertado.
Além das duas ocasiões limite de falta de memória que referimos, este algoritmo é
também ocasionalmente executado automaticamente pelo monitor de comandos do
sistema, em situações em que o nível de ocupação do stack local é baixo, o que permite
uma rápida execução do algoritmo.
8.6. Monitor de Comandos
O monitor de comandos (top level) do sistema segue o estilo de funcionamento
habitual de um interpretador de Edimburgo, com algumas pequenas adições. O prompt
habitual é o seguinte:
[…] ?-
onde a lista indica o contexto corrente em que o monitor de comandos está a correr.
Geralmente essa lista é vazia o que indica que o contexto corrente é vazio, e que a unit
corrente é a unit []. Existem dois comandos para controlar o contexto em que corre o
monitor de comandos: o comando “push u” que cria um nova instância do monitor,
correndo no contexto estendido por u, e o comando “pop” que permite regressar à
instância anterior.
94
9
Conclusão
Acabámos de descrever neste trabalho, um sistema de programação em lógica
contextual (CxLP v0.9) que estende directamente a linguagem Prolog. Nele se
demonstra a possibilidade de implementar com razoável eficiência os mecanismos
específicos da programação em lógica contextual, e de forma a praticamente não
comprometer a velocidade de programas escritos em Prolog.
O sistema já se encontra praticamente operacional, sendo bastante agradável de
usar devido à sua funcionalidade externa, indistinguível da de um interpretador, e à
sua boa velocidade de resposta em todas as situações, incluindo o arranque do
sistema, a compilação de cláusulas e a execução de programas.
O código fonte é bastante extenso compreendendo cerca de 14000 linhas de 20
caracteres em média (excluindo comentários). Cerca de metade deste código destina-se
ao suporte dos novos mecanismos da linguagem CxLP, o que dá uma boa medida do
acrescido trabalho que a sua implementação dá, em relação ao Prolog. É importante,
no entanto, salientar que em termos de dificuldade intrínseca de implementação, ser
correcto afirmar que a linguagem CxLP se situa dentro do mesmo nível de magnitude
que o Prolog.
O número de versão do sistema actual é 0.9, não sendo portanto esta, ainda, a sua
primeira versão oficial. Com efeito falta ainda terminar o desenvolvimento do
colector de lixo do heap e desenvolver um debugger usando o modelo clássico das
quatro portas de Byrd (cf. [Clocksin 81]). Algumas adições importantes a fazer depois
disso, serão: suporte para database references, ampliação do conjunto de predicados
de sistema tomando por referência o standard da indústria Quintus-Prolog, criação de
9. Conclusão
95
biblioteca de programas utilitários, suporte para gramáticas de cláusulas definidas, e
criação de facilidades para armazenamento e carregamento de programas já
compilados (fast save & load).
Existem, entretanto, algumas componentes do sistema cujo aperfeiçoamento ainda
é possível, como é o caso do compilador, para melhoria do código gerado (desde que a
velocidade de compilação não seja muito comprometida), ou da máquina abstracta,
para aumento da sua velocidade (por modificação ou criação de novas de instruções: a
ideia que está na base do índice super-rápido, por exemplo, tem um campo mais vasto
de aplicação).
96
Apêndices
97
A
Predicados de sistema
A.1. Introdução
Apresentamos aqui exaustivamente os predicados de sistema da versão 0.9 do
sistema CxLP. Muitos deles correspondem basicamente aos predicados de sistema
tradicionais do Prolog, mas no contexto da linguagem CxLP a operacionalidade de
alguns teve de sofrer algumas modificações. No que respeita aos predicados
completamente novos, a maior parte destina-se a fazer o controlo das units e seu
conteúdo e a fornecer mecanismos para meta-programação usando contextos. Um
predicado especialmente útil é o predicado chk/0”, que simula a fase de ligação dos
ambientes de desenvolvimento de programas tradicionais com vista à detecção prévia
de situações anómalas. As futuras versões de CxLP fornecerão um conjunto de
predicados mais rico, eventualmente compatível com o Quintus-Prolog.
No ponto
8.1
são
descritos
os
aspectos
mais
relevantes
relacionados
a
implementação dos predicados de sistema.
A.2. Sucesso e falhanço
true
Sucede sempre.
fail
Falha sempre.
A.3. Controlo
! (cut)
Congela todas as alternativas criadas após a chamada do
predicado onde ocorre. Só funciona de forma estática quando
embebido no código das cláusulas. Se for usado de forma
interpretada como na cláusula:
a :- X = !, X.
A. Predicados de sistema
98
surge a mensagem: “Interpreted 'cut' doesn't work.”. Na maior
parte dos compiladores de Prolog, o cut comporta-se de forma
semelhante ao nosso, com a diferença de a mensagem de aviso
não ser emitida.
repeat
Serve para gerar múltiplas soluções usando retrocesso. A sua
definição poderia ser definida como se indica seguidamente, mas
a nossa implementação usa internamente um processo mais
eficiente:
repeat.
repeat :- repeat.
call(X)
Sucede se e só se X suceder no contexto corrente.
Semelhante ao anterior mas ignora as restrições de visibilidade
unsafe_call(X)
existentes nas units do contexto corrente.
X
Equivalente a call(X).
abort
Reinicializa o sistema passando o controlo para o monitor de
comandos (top level).
halt
Pára o interpretador emitindo a mensagem: “CxLP halted!”.
A.4. Manipulação de golos
X,Y
Conjunção de golos.
X;Y
Disjunção de golos.
not X
Sucede sse X falhar no contexto corrente. Definido em CxLP como:
not X :- X, !, fail.
not _.
\+ X
Idêntico a not X.
check(X)
Sucede sse X suceder, mas não instância as variáveis. Definido
como:
check(X) :- not not X.
side_effects(X)
É apenas uma designação diferente para o predicado
check(X) que deve ser usada quando estamos interessados apenas
nos efeitos laterais de uma derivação.
once(X)
Deriva X deterministicamente. Definido como:
once(X) :- X, !.
U>>X
Deriva X no contexto corrente, estendido pela unit designada por
U.
A. Predicados de sistema
99
Deriva X guardando previamente o contexto corrente no contexto
>X
histórico.
Deriva X desempilhando previamente
<X
o
topo
do
contexto
histórico.
If->Then
Deriva Then sse If suceder. A definição é a seguinte:
If -> Then :- If, !, Then
If->Then;Else Deriva Then ou Else consoante If suceda ou não. Definido como:
If -> Then ; Else :- If, !, Then.
If -> Then ; Else :- !, Else.
findall(X,G,L)
L é a lista de todos os termos da forma X que satisfazem o golo G.
A.5. Gestão das units e do seu conteúdo
Os predicados de gestão da base de dados do Prolog foram modificados em CxLP
para actuarem sobre a unit corrente. Assim, por exemplo, para adicionarmos a
cláusula
“rei(‘Henriques, A.’, Portugal)”.
à
unit
reis,
basta
executar
o
golo
“reis>>assert(rei(‘Henriques, A.’, Portugal)).”. Foram também introduzidos alguns
predicados para controlo de atributos de predicados e para acesso ao conteúdo das
units.
units(L)
Unifica L com a lista de átomos que nomeiam todas as units
correntemente existentes, excepto a unit pré-definida [].
create_unit(U,V)
Cria a unit U caso ainda não exista. U e V são termos
equivalentes aos que resultariam da leitura do termo que
descreve a unit usando o predicado read(U,V). Assim, para criar a
unit
authors(Works),
deve
invocar-se
“create_unit(authors(Works), [Works=‘Works’])”. Em geral não é
necessário usar esta primitiva
directamente
visto
que
os
predicados consult/1 e reconsult/1 a utilizam sempre que se torna
necessário criar uma nova unit.
clear_unit(U) Elimina o conteúdo da unit nomeada pelo átomo U. Não é possível
eliminar totalmente uma unit previamente criada devido a
poderem existir referências a ela noutras units.
asserta(T)
Adiciona a cláusula T no início do seu predicado na unit corrente.
Esta operação
faz
a
compilação
da
cláusula T
e a sua
memorização como termo-fonte.
asserta(T,C)
Semelhante ao predicado anterior, com a diferença de que o
compilador não chega a ser chamado pois o segundo argumento C
já contêm a lista do código a ser usado. Este predicado destina-se a
ser usado por um eventual futuro compilador-optimizador,
A. Predicados de sistema
100
escrito em CxLP. Entretanto pode ser utilizado já em experiências
de escrita em assembler da CxM. É preciso alguma cautela, pois a
utilização de código absurdo tem
muitas
vezes
resultados
catastróficos. Eis um exemplo de utilização:
asserta((a(X,Y) :- a(Y,X)),
[put_value(x0,x2),
put_value(x1,x0),
put_value(x2,x0),
execute(a/2)]).
As instruções são automaticamente especializadas pelo sistema
quando for caso disso.
assertz(T)
Como asserta(T) mas a cláusula é adicionada no fim de seu
predicado.
assertz(T,C)
Como asserta(T,C) mas a cláusula é adicionada no fim de seu
predicado.
assert(T)
Equivalente a assertz(T).
assert(T,C)
Equivalente a assertz(T,C).
assertx(T)
Semelhante a assertz(T), mas só pode ser usado imediatamente a
seguir à leitura do termo T por meio de uma das variantes do
predicado read. É mais rápido que o predicado assertz porque o
compilador, neste caso, usa a tabela de variáveis já construída
pelo analisador sintáctico. Este predicado permite aumentar a
eficiência dos predicados consult/1 e reconsult/1 por exemplo.
H :- B
Adiciona a cláusula indicada à unit corrente. O seu código é:
(H :- B) :- assert((H :- B)),
writep((H :- B)),
writeln(' asserted.').
retract(T)
Elimina cláusulas da unit corrente que unifiquem com T. É
removida uma cláusula por cada tentativa de satisfação com
sucesso. Aplica-se a todos os predicados com cláusulas existentes
na unit corrente, mesmo aos não visíveis.
retractall(T) Elimina todas as cláusulas da unit corrente que unifiquem com T.
abolish(A,N)
O predicado A/N é removido. Também se aplica a nomes de
predicados importados, que são removidos da unit corrente.
clause(H,B)
Permite percorrer, usando retrocesso, todas as cláusulas da unit
corrente cuja cabeça unifique com H e cujo corpo unifique com B.
listing(A/N)
Lista o predicado A/N da unit corrente.
listing(A)
Lista
todos
os
predicado
da
unit
independentemente da sua aridade.
corrente,
chamados
A,
A. Predicados de sistema
listing
101
Lista o conteúdo da unit corrente, sendo assinalados os predicado
visíveis e importados. Para listar, por exemplo, a unit authors
fazer authors>>listing.
all
Lista o conteúdo de todas as units existentes na base de dados da
CxLP.
code(A/N)
Lista o código CxM do predicado A/N da unit corrente. A/N pode
ser um predicado de sistema.
code(A)
Lista o código CxM de todos os predicado da unit corrente,
chamados A, independentemente da sua aridade.
consult(File) Adiciona as cláusulas e declarações de visibilidade e importação
existentes no ficheiro File à unit corrente. Se o ficheiro se iniciar
por um termo da forma “unit U.” então o resto do seu conteúdo é
carregado na unit U, que é criada caso não exista ainda.
Semelhante ao predicado anterior com a diferença que
reconsult(File)
todos os predicados a que corresponda uma cláusula em File são
completamente redefinidos.
visible A/N
novisible(A,N)
O nome de predicado A/N fica visível na unit corrente.
O nome de predicado A/N fica invisível na unit corrente.
import A/N from U
Define o nome de predicado A/N como sendo importado
de U. U pode ser um designador de unit ou um parâmetro da unit
corrente.
noimport(A,N) Anula qualquer declaração de importação que exista a respeito do
nome de predicado A/N.
noindex(A,N)
Indica que a técnica de indexação suportada pela CxM não deve
ser aplicada ao predicado A/N.
protect(A,N)
O predicado A/N deixa de poder sofrer qualquer alteração. Todos
os predicados de sistema estão protegidos desta forma.
static(A,N)
A única alteração que o predicado A/N pode sofrer é a completa
remoção usando o predicado abolish/2.
visible_predicate(T)
Este predicado pode ser usado tanto para teste como para
iterar sobre o conteúdo da unit corrente. Como predicado de teste
sucede se T for um termo da forma P/N correspondente a um
predicado visível na unit corrente. Se T for uma variável, usando
retrocesso, T vai sendo sucessivamente instanciado com pares
P/N, correspondentes aos functores de todos os predicados
visíveis existentes na unit corrente.
A. Predicados de sistema
invisible_predicate(P)
102
O que se disse em relação ao predicado anterior
aplica-se aqui mutatis mutandis a predicados não importados
que não tenham objecto de nenhuma declaração de visibilidade.
imported_predicate(P,U)
Semelhante
ao
anterior.
Note-se
que
os
3
conjuntos de nomes - visíveis, invisíveis e importados - da forma
como são aqui entendidos, constituem uma partição do conteúdo
das unit.
builtin_predicate(P)
Do tipo dos anteriores este predicado
aplica-se
a
predicados de sistema.
user_predicate(P)
Disjunção de visible_predicate(P) com invisible_predicate(P).
any_predicate(P)
Disjunção de user_predicate(P) com builtin_predicate(P).
A.6. Contextos
Os predicados seguintes permitem aceder aos contextos correntes, simples e
histórico, e obter os valores dos parâmetros da unit corrente de forma indexada.
Destinam-se em grande medida à utilização em meta-programação.
context(C)
Unifica C com uma lista representando o contexto lógico corrente
(portanto sem a unit terminal []). Os elementos da lista são todos
designadores de unit.
context_top(T)
Unifica T com o designador da unit corrente. Este predicado foi
definido apenas por razões de eficiência, visto o predicado
context(C) poder ser usado em alternativa.
historic_context(H)
Unifica H com uma lista representando o contexto
histórico corrente. Os elementos de H são listas que representam
contextos.
unit_parameter(N,V)
Unifica V com o valor corrente do parâmetro de ordem N
(>=1) da unit corrente.
make_unit_parameter(N,UP)
Um termo da forma “$_unit_parameter(N)” é
invariavelmente tratado pelo compilador como representando o
parâmetro da unit corrente de ordem N. Se por algum motivo
tivermos necessidade de usar aquele termo como representante de
si mesmo, não podemos simplesmente escrevê-lo no código dos
programas. A solução consiste em criar o termo dinamicamente,
o que evita a sua análise por parte do compilador. Para isso pode
usar-se o predicado:
make_unit_parameter(N,UP) :- UP =.. [$_unit_parameter,N].
A. Predicados de sistema
103
A.7. Classificação de termos
var(X)
Testa se X é uma variável não instanciada.
novar(X)
Testa se X é um termo não variável.
atom(X)
Testa se X é um átomo.
integer(X)
Testa se X é um valor inteiro.
real(X)
Testa se X é um valor real.
number(X)
Testa se X é um valor numérico.
atomic(X)
Testa se X é um átomo ou um valor numérico.
unit_designator(X) Testa se X é um designador de unit. Um designador de unit é
um termo não variável, cujo functor principal é um nome de unit
existente.
A.8. Manipulação de estruturas
functor(T,F,N)
T é uma estrutura com o functor F e aridade N. Se T não estiver
instanciado F e N têm de o estar.
arg(N,T,A)
A é o argumento de ordem N da estrutura T. N e T têm de estar
instanciados.
X =.. L (univ) L é a lista consistindo no functor
de X seguido dos seus
argumentos. Definido em CxLP, usando o predicado auxiliar
$_=../2, como:
T =.. [F|As] :- $_=..(As,T,F,0).
$_=..([],T,F,N) :- functor(T,F,N), !.
$_=..([A|As],T,F,N) :N1 is N+1, $_=..(As,T,F,N1), !, arg(N1,T,A).
name(A,L)
L é uma lista de inteiros constituída pelos códigos dos caracteres
constituintes do átomo L.
A.9. Igualdade
X = Y
Unifica X com Y.
X \= Y
Equivalente a not X = Y.
X == Y
Sucede sse os dois argumentos forem duas ocorrências do mesmo
termo.
X \== Y
Equivalente a not X == Y.
A. Predicados de sistema
104
A.10. Avaliação de expressões aritméticas e comparação de
números
X is Y
Y deve estar instanciado com uma estrutura que possa ser
interpretada como uma expressão aritmética. O valor dessa
expressão é avaliado e unificado com X. O resultado da avaliação é
convertido para inteiro sempre que a sua parte decimal for zero
ou muito próxima. Os operadores disponíveis são: +/2, -/2, */2,
//2, mod/2, cputime/0 e heapused/0. “cputime” indica o tempo
total de CPU que foi usado desde que o sistema arrancou.
“heaptime” indica o espaço total ocupado na zona de código da
CxM (o nome deve-se a uma questão de compatibilidade com o
C-Prolog).
X
X
X
X
X
X
=:= Y
=\= Y
< Y
> Y
>= Y
=< Y
Predicados de comparação de valores numéricos.
A.11. Gestão de ficheiros
Eis os predicados de alteração dos canais correntes de entrada e saída. Neste
momento é apenas suportado o fluxo de dados de e para os ficheiros em memória
secundária. No entanto num sistema de janelas deverá feita a sua adequada
generalização. Existem dois
canais
pré-definidos
ambos
de
nome
user que
representam o teclado do computador e o seu dispositivo de visualização.
see(S)
O canal corrente de entrada passa a ser o designado pelo átomo S.
seeing(S)
S é unificado com o nome da canal corrente de entrada.
seen
Fecha o canal corrente de entrada. O canal user torna-se corrente.
tell(S)
O canal corrente de saída passa a ser o designado por S.
telling(S)
S é unificado com o nome da canal corrente de saída.
told
Fecha o canal corrente de saída. O canal user torna-se corrente.
A.12. Entradas e Saídas
Todos os predicados de entrada e saída que aqui se descrevem são determinísticos.
Estão definidos alguns predicados de leitura e escrita que consideram a necessidade de
reconhecimento do nome dos parâmetros da unit corrente nos termos processados.
read(X)
Unifica X com o próximo termo no canal de entrada corrente. Em
fim de canal é produzido o átomo end_of_file.
A. Predicados de sistema
readp(X)
105
Semelhante a read(X) mas desta vez são considerados os nomes
dos parâmetros da unit corrente, com o objectivo de reconhecer a
sua presença no termo lido. Os parâmetros são representados por
termos
da
forma
“$_unit_parameter(N)”
em que
N(>=1)
representa a ordem do parâmetro lido.
read(X,Y)
Unifica X com o próximo termo do canal de entrada corrente, e Y
com uma lista de pares “V=‘nome’” onde se indica o nome de todas
as variáveis do termo.
readp(X,Y)
Semelhante a read(X,Y) mas sendo feito o reconhecimento dos
parâmetros da unit corrente.
write(X)
Escreve o termo X no canal corrente de saída. Existe um
codificação especial para os nomes das variáveis que surjam. São
respeitadas todas as definições de operadores correntemente
definidas.
writep(X)
Escreve o termo X no canal corrente de saída tal como write(X).
Qualquer termo da forma “$_unit_parameter(N)” é substituído
pelo nome do parâmetro da unit corrente de ordem N, se existir.
write(X,Y)
Semelhante a write(X) mas desta vez são respeitados os nomes das
variáveis que se encontram definidos em Y usando um lista de
pares “V=‘nome’”.
writep(X,Y)
Semelhante a write(X,Y) mas sendo feito o tratamento dos nomes
dos parâmetros da unit corrente.
writeln(X)
writeln(X) :- write(X), nl.
writepln(X)
writepln(X) :- writep(X), nl.
display(X)
Semelhante a write(X) mas desta vez são ignoradas todas as
declarações de operadores existentes.
op(X,Y,Z)
Permite declarar operadores. X é a precedência do operador que se
trata de um valor inteiro entre 0 e 1200, variando a precedência de
forma inversamente proporcional ao seu valor. Y indica a
posição e associatividade do operador, podendo ser um dos
seguintes átomos: fx, fy, xf, yf, xfx, xfy, yfx, yfy. Z é o nome do
operador, ou uma lista de nomes de operador. Este predicado
sucede sse a definição do operador for legal.
O conjunto de declarações que define o conjunto de predicados
pré-definido é o seguinte:
op(1200, fx, [(:-), (?-)]).
op(1200, xfx, (:-)).
op(1100, xfy, (';')).
op(1050, xfy, ('->')).
A. Predicados de sistema
106
op(1000, xfy, (',')).
op( 900, fy, [\+, not, unit, visible,
import, push]).
op( 800, xfy, from).
op( 700, xfx, [=:=, =\=, <, >=, >,
=<, is, =..]).
op( 700, xfx, [ ==, \==, =, \=]).
op( 700, xfy, >>).
op( 700, fy, [ >, <]).
op( 500, yfx, [+, -]).
op( 500, fx, [+, -, \]).
op( 400, yfx, [*, /, div, <<, >>]).
op( 300, xfx, mod).
reset_ops
Repõe o estado inicial da tabela de operadores do sistema, fazendo
portanto a anulação de todas as adições e alterações efectuadas
desde o início da entrada no sistema.
get0(X)
X é unificado com o código do próximo carácter do canal de
entrada. No fim de canal é produzido o valor 26.
get(X)
X é unificado com o código do próximo carácter do canal de
entrada imprimível. No fim de canal é produzido o valor 26.
skip(X)
São ignorados todos todos os caracteres do ficheiro de entrada até
ser encontrado um cujo código unifique com X.
put(X)
Escreve o carácter de código X no canal corrente de saída.
nl
Escreve uma mudança de linha no canal corrente de saída.
tab(X)
Escreve X brancos no canal corrente de saída.
A.13. Diversos
statistics
Exibe diversa informação sobre o estado corrente do sistema,
concretamente a ocupação das diversas zonas de memória da CxM
e o tempo de CPU usado desde que o sistema começou a correr.
status
Exibe informação sobre o conjunto de indicadores de estado da
CxM que são descritos em status/2.
status(I,S)
Serve para controlar o valor de alguns indicadores de estado
existentes na CxM. I é um átomo que selecciona o indicador de
estado em que estamos interessados. S é unificada com o valor
corrente do indicador, podendo ser uma variável ou um dos
átomos on ou off. Os valores possíveis para I são os seguintes:
• specialize
Controla como é feita a especialização de instruções referida
no ponto 6.6. Valor por defeito: on.
• keep_source
Todos os predicados criados durante períodos em que este
indicador
esteja
a
off
não
memorizam
os
termos
correspondentes às cláusulas que os constituem, sendo
A. Predicados de sistema
107
economizada desta forma cerca de 35% de memória. No
entanto este facto impede a aplicação de algumas primitivas
de sistema a estes predicados, concretamente: clause/2,
retract/1 e retractall/1. Valor por defeito: off.
• diagnose_anomalies
Durante a execução dos programas todas as
situações menos normais são
assinaladas,
como
por
exemplo a invocação de um predicado não existente, ou a
pesquisa no contexto corrente provocada por referência a
um predicado importado de uma unit, na qual não está
declarado como visível. Valor por defeito: on.
• import_search
Se estiver off altera um pouco a semântica normal da
chamada de predicados importados, provocando falhanço
imediato
(e
produzindo
uma
mensagem
se
diagnose_anomalies estiver on) sempre o predicado não
esteja declarado como visível na unit de onde é importado.
Valor por defeito: on.
• ctx_ext_search Se estiver off altera um pouco a semântica normal das
fórmulas de extensão, provocando falhanço imediato (e
produzindo uma mensagem se diagnose_anomalies estiver
on) sempre o predicado não esteja declarado como visível na
unit que estende o contexto. Valor por defeito: on.
• indexing
Permite desligar a indexação de todos os predicados criados
enquanto o indicador estiver a off. Valor por defeito: on.
• abort_on_syntax_error Se estiver on o predicado abort/0 é chamado
sempre que ocorrer algum erro sintáctico durante o uso de
alguma das variantes do predicado read.
• trace
Caso esteja on mostra durante a execução dos programas
todas as chamadas de predicados com os respectivos
argumentos e contexto corrente. Neste momento a única
ferramenta para depuração de programas é esta, o que
reconhecemos, não é suficiente. Valor por defeito: off.
chk
Faz uma análise das relações de dependência entre as units
existentes
assinalando
todas
as
referências
a
predicados
importados de uma unit na qual não estejam declarados como
visíveis, e ainda todas as fórmulas de extensão da forma U>>P,
em que P não é visível em U. O objectivo é a detecção de algumas
situações de erro que de outra maneira só poderiam ser detectadas
em tempo de execução. A detecção dinâmica de erros não é segura,
A. Predicados de sistema
108
pois é frequente passarem despercebidos alguns erros, mesmo
após extensivos testes ao programa.
$_sys_chk
Invoca uma rotina, que faz alguns testes sobre a máquina
hospedeira e sobre a própria CxM, com vista a detectar eventuais
problemas e a facilitar o seu transporte.
$_protect_all Protege
todos os predicados de sistema carregados até ao
momento. É chamado após o carregamento do ficheiro CxBoot,
com o objectivo de proteger todos os predicados de sistema.
error_handler(Handler)
O
predicado
que
por
defeito
é
activado
automaticamente quando ocorre um erro de sistema, é o que
corresponde ao monitor de comandos do sistema. Usando o
predicado error_handler/1 é possível indicar um outro predicado
sem argumentos para ser usado em alternativa. A chamada
“error_handler([])” repõe o estado inicial.
109
B
Operações Básicas e Instruções da CxM
B.1. Introdução
Apresenta-se neste apêndice a especificação das instruções da máquina CxM, assim
como das principais operações básicas nela usadas. A procura de concisão e clareza da
descrição levou-nos a eliminar da descrição todos os aspectos que não tivessem a ver
directamente com a essência da funcionalidade da máquina. Os principais aspectos
ignorados foram os seguintes: a interacção das instruções com o ambiente de
desenvolvimento dos programas (debugger por exemplo), os testes de transbordo das
pilhas (estas são consideradas como tendo dimensão infinita) e as múltiplas
optimizações de pormenor introduzidas durante a codificação das instruções.
B.2. Pseudo-código
A descrição de todas as instruções e operações básicas é efectuada numa notação
muito semelhante à da linguagem dos comandos guardados - GCL - de E. Dijkstra
[Dijkstra 76]. Esta linguagem foi escolhida devido à extrema compacidade e elegância
com que permite fazer a especificação de algoritmos.
Em GCL existem duas construções para controlo do fluxo de execução dos
programas: a construção alternativa if … fi e a construção repetitiva do … od. O
interior dessas construções consiste num conjunto de comandos guardados cada um
dos quais tem a forma: “<guarda> → <comando>”. Um comando guardado só pode ser
executado se a sua guarda for verdadeira. Entretanto se várias guardas de um mesmo
B. Operações Básicas e Instruções da CxM
110
conjunto de comandos guardados forem verdadeiras simultaneamente, a escolha
entre elas é efectuada de forma não determinista.
A instrução skip representa a instrução vazia. A afectação de variáveis é indicada
usando o operador “←”. A linguagem suporta todos os operadores lógicos e relacionais
habituais.
A semântica que atribuímos à construção if … fi é aqui um pouco diferente da
original. Enquanto na GCL a ausência de guardas com valor lógico verdadeiro no seu
conjunto de comandos guardados da instrução a tornam equivalente a abort, na
nossa versão essa ausência tem mesmo efeito que a instrução da CxM, Fail. Tiramos
partido disto para tornar as especificações das instruções da máquina mais
compactas: de facto a instrução Fail nunca precisa de ser usada de forma explicita.
Além da alteração anterior introduzimos também algumas adições à GCL: funções
com o comando associado return, e ainda registos de dados e apontadores.
Em relação aos apontadores consideramos que todos eles referem simples palavras
de memória. A operação de desreferenciação representa-se pelo operador unário
prefixo “*” de forma que se V for uma referência, “*V” representa a palavra apontada
por V. Definem-se as operações de soma e subtracção entre um apontador e um inteiro
da seguinte forma: “V+n” representa uma referência para n palavras à frente daquela
que é apontada por V; “V-m” uma referência para m palavras atrás.
Em relação aos registos de dados, a notação “R(F)” indica o campo F do registo de
dados indicado por R.
B.3. Operações básicas da CxM
Apresentam-se aqui as operações básicas da máquina CxM, as quais são usadas
como funções auxiliares pelas instruções da máquina abstracta.
IsLocalVar(v)
return IsVar(v) and v >= H
Testa se v é uma variável local, isto é se ela encontra no stack local.
IsGlobalVar(v)
return IsVar(v) and v < H
Testa se v é uma variável global, isto é, se ela encontra no heap.
IsCurrEnvVar(v)
return IsLocalVar(v) and v < E
Testa se v é uma variável pertencente ao registo de activação do predicado corrente.
IsToTrailVar(v)
return v < HB or v >= B
Testa se a variável v precisa de ser memorizada no trail para futura reposição. As condições
de memorização são as seguintes: ou a variável é global e definida antes da posição do topo do
heap no momento da criação do último ponto de escolha (valor indicado pelo registo HB), ou a
variável é local e definida antes do último ponto de escolha.
B. Operações Básicas e Instruções da CxM
111
ResetVar(v)
*v ← v
Torna a variável v livre.
PushVar(sp)
ResetVar(sp)
sp ← sp + 1
return sp - 1
Empilha uma variável livre na pilha cujo topo é referido por sp.
Drf(v)
do
IsVar(v) and v <> *v → v ← *v
od
return v
Determina o valor da variável v através do percurso completo da sua cadeia de referências.
Trail(v)
if
IsToTrailVar(v) → Push(TR, v)
not IsToTrailVar(v) → skip
fi
Memoriza uma variável no trail caso isso seja necessário.
Assign(v, a)
Trail(v)
*v ← a
Instancia a variável v com o valor a.
Bind(v1, v2)
if
v1 < v2 →
if
v1 > v2 →
fi
if
v1 = v2 →
fi
skip
IsGlobalVar(v1) → Assign(v2, v1)
not IsGlobalVar(v1) → Assign(v1, v2)
IsGlobalVar(v2) → Assign(v1, v2)
not IsGlobalVar(v2) → Assign(v2, v1)
fi
Unifica duas variáveis livres. Esta operação, relativamente à WAM, exige o teste suplementar
IsGlobalVar(.), devido à nova disposição dos stacks.
B. Operações Básicas e Instruções da CxM
112
Unify(t1, t2)
saveH ← H
Push(H, t1)
Push(H, t2)
do H <> saveH →
t1 ← Pop(H)
t2 ← Pop(H)
if
IsVar(t1) →
if
IsVar(t2) → Bind(t1, t2)
not IsVar(t2) → Assign(t1, t2)
fi
not IsVar(t1) →
if
IsVar(t2) → Assign(t2, t1)
not IsVar(t2) →
if
t1 = t2 → skip
IsList(t1) and IsList(t2) →
Push(H, ListTail(t1))
Push(H, ListTail(t2))
Push(H, ListHead(t1))
Push(H, ListHead(t2))
IsStruct(t1) and IsStruct(t2)
and StructFunctor(t1) = StructFunctor(t2) →
dotimes(i, StructArity(t1))
( Push(H, StructArgs(t1)i))
Push(H, StructArgs(t2)i)) )
fi
fi
fi
od
Unifica dois termos quaisquer. O stack global é usado como pilha auxiliar. A CxM não
suporta occurs check por razões de eficiência. No entanto, caso a sua adição venha a ser
desejada, bastará modificar esta operação.
RestoreTrail(b)
do TR <> b →
t ← Pop(TR)
ResetVar(t)
do
Liberta as variáveis que se encontram no trail até ao nível b.
TidyTrail()
v ← B(TR)
do v < TR →
if
IsToTrailVar(*v) → v ← v + 1
not IsToTrailVar(*v) → *v ← Pop(TR)
fi
do
Recupera no trail o espaço correspondente a todas as variáveis que nele se encontram
desnecessariamente. Esta operação é usada apenas pelas instruções de cut.
GTopOfLocalStack(EnvSize)
if
L < E → return L
L >= E → return E - EnvSize
fi
Determina o topo do stack local com base no argumento EnvSize, o qual é suposto indicar o
tamanho corrente do registo de activação que se encontra activo. Como se sabe, o tamanho dos
registos de activação varia dinamicamente devido ao seu trimming.
B. Operações Básicas e Instruções da CxM
113
TopOfLocalStack()
return GTopOfLocalStack(*(CP - 1))
Determina o topo do stack local com base no segundo argumento de uma instrução Call.
Esse argumento encontra-se exactamente na posição anterior à do endereço de retorno do
predicado correntemente activo (indicado pelo registo CP) e indica o tamanho do registo de
activação do predicado que fez a chamada, no ponto em que ela foi efectuada.
FindVisiblePredicate(Functor, Unit)
pred ← GetUnitPredicate(Functor, systemUnit)
if
pred <> nil → return pred
pred = nil → skip
fi
pred ← GetUnitPredicate(Functor, Unit)
if
pred <> nil and PredVisible(pred) → return pred
not (pred <> nil and PredVisible(pred)) → return nil
fi
Para um dado functor, procura uma definição de predicado visível numa unit. A unit que
contêm os predicados de sistema é considerada em primeiro lugar pois todos os predicados
que nela estão definidos são considerados locais a todas as units.
SearchContextBelow(Functor)
do true →
if
C(U) = nilUnit → return failPredicate
C(U) <> nilUnit → C ← C(C)
fi
pred ← FindVisiblePredicate(Functor, C(U))
if
pred <> nil → return pred
pred = nil → skip
fi
od
Procura uma definição de predicado visível para um dado functor no contexto corrente, mas
sem considerar o seu topo. Como se pode observar, a base do contexto corrente é determinada
pela unit [].
SearchContext(Functor)
pred ← FindVisiblePredicate(Functor, C(U))
if
pred = nil → return SearchContextBelow(Functor)
pred <> nil → return pred
fi
Procura uma definição de predicado visível, com base no seu functor, no contexto corrente.
SaveState(arity, previousB)
B(C) ← C
B(CC) ← CC
B(C2) ← C2
B(E) ← E
B(CP) ← CP
B(B) ← previousB
B(B0) ← B0
B(TR) ← TR
B(H) ← H
HB ← B(H)
dotimes(n, arity) B(A)n ← Xn
Guarda todos os registos da CxM que são necessários para repor posteriormente o estado
da máquina. O argumento arity indica o número de registos X a salvaguardar e o argumento
previousB o ponto de escolha anterior àquele que está a ser preenchido.
B. Operações Básicas e Instruções da CxM
114
RestoreState(arity)
C ← B(C)
CC ← B(CC)
C2 ← B(C2)
E ← B(E)
CP ← B(CP)
B0 ← B(B0)
RestoreTrail(B(TR))
H ← B(H)
dotimes(n, arity) Xn ← B(A)n
Repõe um estado da máquina previamente guardado. arity indica o número de registos X a
repor.
DiscardLastChoice()
B ← B(B)
HB ← B(H)
Repõe o último ponto de escolha anterior.
InitCxM()
H ← stacksBegin
TR ← trailBegin
E ← B ← B0 ← stacksEnd
C ← stacksEnd - SizeOf(UnitInstance)
C(S) ← C(C) ← CC ← C
C(U) ← topUnit
C(N) ← 0
C2 ← C - SizeOf(HistoricalRegister)
C2(R2) ← C2(C2) ← C2
C2(C) ← C
L ← C2Base ← C2
Inicia a máquina abstracta. É empilhada uma instância da unit [], que define o contexto vazio
inicial e ainda um registo histórico. Este é permanentemente apontado pelo registo da máquina
C2Base, o qual é utilizado na detecção de tentativas de reposição contextos que não tenham
sido previamente guardados.
B.4. Instruções procedimentais e de controlo
Esta classe de instruções encarrega-se principalmente da gestão da invocação de
predicados, o que inclui a transferência de controlo e a criação de registos de
activação. Incluímos as instruções de tratamento do cut também nesta categoria.
Allocate
save ← E
E ← TopOfLocalStack()
E(E) ← save
E(CP) ← CP
E(CC) ← CC
Esta instrução aparece na zona inicial do código de todas as cláusulas que tenham pelo
menos dois golos no corpo, e ainda nas cláusulas em que o seu único golo é uma das fórmulas
especiais da linguagem CxLP: extensão, salvaguarda, reposição e libertação de contexto. Cria
um novo registo de activação no topo do stack local, memorizando nele os registos E, CP e CC.
Call Pred N
B0 ← B
CP ← P + 2
P ← PredCode(Pred)
A instrução Call termina geralmente o código associado à chamada de um golo. Pred é a
referência do predicado chamado, e N é o número de variáveis no registo de activação neste
ponto da cláusula. O valor guardado no registo B0 é utilizado mais tarde se alguma das
cláusulas do predicado invocado contiver um cut. O registo CP memoriza o endereço de retorno
do predicado chamado. A transferência de controlo é concretizada pela alteração do valor de P.
B. Operações Básicas e Instruções da CxM
115
CallVar
functor ← PrepareCall(X0)
pred ← SearchContext(functor)
if
IsCPred(pred) → P++
Jump(PredCode(pred))
IsPrologPred(pred) →
B0 ← B
CP ← P + 1
P ← PredCode(pred)
fi
Esta instrução implementa o meta-call da linguagem CxLP. O termo que representa o golo a
ser derivado encontra-se no registo X0. A rotina PrepareCall copia os argumentos desse termo
para os registos X0, X1, …, produzindo como valor o seu functor principal. A determinação do
predicado a ser chamado exige uma pesquisa no contexto corrente.
Execute Pred
B0 ← B
P ← PredCode(Pred)
A instrução Execute termina, em geral, o código das cláusulas que têm exactamente um golo
no seu corpo. É semelhante à instrução Call com a diferença que não posiciona o registo CP.
DeallocateAndExecute Pred
CP ← E(CP)
CC ← E(CC)
E ← E(E)
B0 ← B
P ← PredCode(Pred)
Esta instrução termina, em geral, o código das cláusulas que têm mais dos que um golo no
seu corpo. Começa por repor o valor dos registos E, CP, e CC, e passa depois o controlo para o
predicado Pred.
ExecuteVar
functor ← PrepareCall(X0)
pred ← SearchContext(functor)
if
IsCPred(pred) → P ← Address(Proceed)
Jump(PredCode(pred))
IsPrologPred(pred) →
B0 ← B
P ← PredCode(pred)
fi
A instrução ExecuteVar termina o código das cláusula cujo corpo é constituído por apenas
um meta-call. É semelhante à instrução CallVar com a diferença que não posiciona o registo
CP.
DeallocateAndExecuteVar
CP ← E(CP)
CC ← E(CC)
E ← E(E)
functor ← PrepareCall(X0)
pred ← SearchContext(functor)
if
IsCPred(pred) → P ← Address(Proceed)
Jump(PredCode(pred))
IsPrologPred(pred) →
B0 ← B
P ← PredCode(pred)
fi
A instrução DeallocateAndExecuteVar termina o código das cláusulas com mais do que um
golo, e cujo último golo seja um meta-call. Começa por repor o valor dos registos E, CP, e CC,
sendo a parte restante da instrução igual a ExecuteVar.
B. Operações Básicas e Instruções da CxM
116
Proceed
P ← CP
C ← CC
Esta instrução termina o código de todas as cláusulas unitárias. Posiciona os registos P e C
com os valores guardados em CP e CC respectivamente.
DeallocateAndProceed
P ← E(CP)
C ← CC ← E(CC)
E ← E(E)
Esta instrução termina todas as cláusulas não unitárias cujo último golo seja uma das
fórmulas especiais da linguagem CxLP: extensão, salvaguarda, reposição e libertação de
contexto.
NeckCut
if
B < B0 →
B ← B0
HB ← B(H)
L ← Min(B,C,C2)
TidyTrail()
B >= B0 →
skip
fi
Esta instrução é gerada no início do código do corpo das cláusulas cujo primeiro golo seja
um cut. Os pontos de escolha situados acima daquele que é indicado indicado por B0 são
eliminados, e a informação que se torna redundante no trail é eliminada.
GetLevel Yn
Yn ← B0
Esta instrução é gerada no início do código do corpo das cláusulas que tenham um cut
internamente. O valor de B0 é copiado para a variável permanente Yn.
Cut Yn
if
B < Yn →
B ← Yn
HB ← B(H)
L ← Min(B,C,C2)
TidyTrail()
B >= Yn → skip
fi
Esta instrução é gerada no ponto de utilização de um cut que se situe depois do primeiro
golo da cláusula. Os pontos de escolha situados acima daquele que é indicado indicado por Yn
são eliminados, e a informação que fica redundante no trail é eliminada.
Fail
P ← B(P)
Usa-se em todos os pontos do código onde o predicado fail/0 é chamado. O registo P é posto
a apontar para a próxima cláusula alternativa, que se encontra registada no último ponto de
escolha. A instrução apontada por P, e que é executada logo a seguir é uma das quatro que
repõem um estado previamente guardado: RetryMeElse, TrustMe, Retry, Trust.
DiscardAndFail
B ← B(B)
HB ← B(H)
L ← Min(B,C,C2)
P ← B(P)
Elimina o último ponto de escolha e considera a próxima cláusula alternativa.
B. Operações Básicas e Instruções da CxM
117
B.5. Instruções Put
Estas instruções correspondem aos argumentos dos golos do corpo cláusula e
carregam os registos X com os argumentos actuais das chamadas de predicados. A
única instrução deste tipo adicionada na CxM, em relação à WAM, foi a instrução
PutValue Zn, Xi que se destina a ser usada nos casos em que um parâmetro de uma unit
ocorre num argumento de um golo. Além disso as instruções PutStructure e PutList
não colocam aqui a máquina em modo de escrita, pois no corpo das cláusulas todas as
instruções da classe Unify foram substituídas pelas instruções correspondentes da
classe Build.
PutVariable Yn, Xi
ResetVar(Yn)
Xi ← Yn
Esta instrução é gerada para um argumento de um golo que seja uma variável permanente
livre. A variável Yn é tornada livre, e a sua referência copiada para Xi .
PutVariable Xn, Xi
Xi ← Xn ← PushVar(H)
Esta instrução é gerada para um argumento do último golo que seja uma variável livre. É
criada uma variável livre nova no topo do heap, e Xi e Xn são postos a apontar para ela.
PutVariableOne Xn
Xn ← PushVar(H)
Semelhante a PutVariable Xn , Xi usa-se no caso em que i = n.
PutValue ψn, Xi
; ψ ∈ { X, Y, Z }
Xi ← ψn
Esta instrução é gerada para um argumento de um golo que seja uma variável instanciada.
ψn é simplesmente copiado para Xi .
PutUnsafeValue Yn, Xi
t ← Drf(Yn)
if
IsCurrEnvVar(t) →
Xi ← PushVar(H)
Assign(t, Xi)
not IsCurrEnvVar(t) → Xi ← t
fi
Esta instrução é gerada apenas no último golo da cláusula, na primeira referência que aí é
feita a uma variável unsafe. Se a variável depois de desreferenciada apontar para uma variável
situada no registo de activação corrente (prestes a ser eliminado por uso de LCO), ela é
transferida para o topo do heap. Quer isto suceda quer não, o valor com que a variável fica é
copiado para Xi.
PutConstant ϑ, Xi
Xi ← ϑ
Gerada para os argumentos constantes de um golo. A constante é simplesmente copiada
para X i .
PutNil Xi
Xi ← []
Gerada quando um argumento de um golo é o átomo []. Este átomo é simplesmente copiado
para X i .
B. Operações Básicas e Instruções da CxM
118
PutStructure Φ, Xi
Xi ← TagStruct(H)
Push(H, Φ)
Indica o início de uma estrutura que aparece como num argumento de um golo. Xi recebe um
apontador para estrutura com o endereço do topo do heap onde é empilhado o functor.
PutList Xi
Xi ← TagList(H)
Indica o início de uma lista que aparece num argumento de um golo. Xi recebe um apontador
para lista com o endereço do topo do heap, que é o local onde os seus dois argumentos serão a
seguir empilhados.
B.6. Instruções Get
Estas instruções
são
geradas
para
a
cabeça
das
cláusulas
e
fazem
o
emparelhamento dos seus argumentos formais com os argumentos actuais da
chamada dos predicados, que são recebidos nos registos X da máquina. A única
instrução adicionada na CxM, em relação à WAM, foi a instrução GetValue Z n , X i
que se destina a ser usada nos casos em que um parâmetro de uma unit ocorre na
cabeça de uma cláusula ao nível da superfície.
GetVariable Yn, Xi
Yn ← Xi
Esta instrução é gerada para todas as ocorrências de variáveis livres ao nível da superfície
da cabeça da cláusula. Ela copia simplesmente o valor do registo X i para a variável Yn.
GetValue Xn, Xi
if
Unify(Xn, Xi) → Xn ← Drf(Xn)
fi
Esta instrução é gerada para todas as ocorrências de variáveis temporárias instanciadas ao
nível da superfície da cabeça da cláusula. Os dois registos são unificados. O resultado
desreferenciado fica em Xn.
GetValue ψn, Xi
; ψ ∈ { Y, Z }
if
Unify(ψn, Xi) → skip
fi
Esta instrução é gerada para todas as ocorrências de variáveis permanentes instanciadas
ou parâmetros de unit na cabeça da cláusula ao nível da superfície. ψn e Xi são simplesmente
unificados.
GetConstant ϑ, Xi
t ← Drf(Xi)
if
IsVar(t) → Assign(t, ϑ)
t = ϑ → skip
fi
Esta instrução representa a constante ϑ ocorrendo como argumentos da cláusula. Se o
resultado for uma variável então esta é instanciada com ϑ. Caso contrário se o resultado for
diferente de ϑ ocorre retrocesso.
B. Operações Básicas e Instruções da CxM
119
GetNil Xi
t ← Drf(Xi)
if
IsVar(t) → Assign(t, [])
t = [] → skip
fi
Esta instrução representa o átomo [] ocorrendo como argumento da cláusula. Se o resultado
for uma variável então esta é instanciada com []. Caso contrário se o resultado for diferente de []
ocorre retrocesso.
GetStructure Φ, Xi
t ← Drf(Xi)
if
IsVar(t) →
Assign(t, TagStruct(H))
Push(H, Φ)
SetWriteMode()
IsStruct(t) and StructFunctor(t) = Φ →
S ← StructArgs(t)
SetReadMode()
fi
Indica o início de uma estrutura que ocorre na cabeça de uma cláusula. O registo Xi é
desreferenciado. Se o resultado for uma variável, então esta recebe um apontador para o topo
do heap, marcado com a tag estrutura. Além disso é ainda empilhado o functor Φ e posta a
máquina em modo de escrita. Se o resultado for uma estructura com functor Φ, então o registo S
é posto a apontar para o seu primeiro argumento e a máquina é posta em modo de leitura. Nos
casos restante ocorre retrocesso.
GetList Xi
t ← Drf(Xi)
if
IsVar(t) →
IsList(t) →
Assign(t, TagList(H))
SetWriteMode()
S ← ListArgs(t)
SetReadMode()
fi
Indica o início de uma estrutura que ocorre na cabeça de uma cláusula. O registo Xi é
desreferenciado. Se o resultado for uma variável então esta recebe um apontador para o topo do
heap, marcado com a tag lista e a máquina é posta em modo de escrita. Caso o resultado seja
uma lista então o registo S é posto a apontar para o seu primeiro argumento e a máquina é
posta em modo de leitura. Nos casos restante ocorre retrocesso.
B.7. Instruções Unify
Estas instruções, geradas no nosso sistema apenas na cabeça das cláusulas,
correspondem a argumentos de estruturas ou listas e o seu funcionamento depende do
modo corrente: leitura ou escrita. Em modo de leitura fazem-se unificações com
estruturas pré-existentes e em modo de escrita constroem-se novas estruturas. Na
WAM essas instruções também são utilizadas no corpo das cláusulas, mas como nesse
contexto funcionam sempre em modo de escrita, foram substituídas pelas instruções
mais compactas e eficientes da classe Build.
As únicas instruções deste tipo adicionadas na CxM, em relação à WAM, foram as
instruções UnifyValue Zn e UnifyLocalValue Zn que se destinam a ser usada nos casos
em que um parâmetro de uma unit ocorre na cabeça de uma cláusula dentro de uma
estrutura ou lista.
B. Operações Básicas e Instruções da CxM
120
UnifyVoid N
if
WriteMode() → dotimes(i,N) PushVar(H)
ReadMode() → S ← S + N
fi
Representa N variáveis consecutivas de ocorrência única, nos argumentos duma estrutura
da cabeça da cláusula. Consoante o modo corrente seja de escrita ou de leitura, assim são
empilhadas N variáveis livres no topo do heap, ou são saltados os próximos N argumentos
apontados por S.
UnifyVoidOne
if
WriteMode() → PushVar(H)
ReadMode() → S ← S + 1
fi
Especialização da instrução anterior para N = 1.
UnifyVariable ψn
; ψ ∈ { X, Y }
if
WriteMode() → ψn ← PushVar(H)
ReadMode() → ψn ← *S
S ← S + 1
fi
Esta instrução é gerada para argumentos de estruturas da cabeça que sejam variáveis livres.
Em modo de escrita ψn recebe um apontador para uma nova variável livre que é empilhada no
heap. Em modo de leitura o próximo argumento apontado por S é copiado para ψn.
UnifyValue Xn
if
WriteMode() → Push(H, Xn)
ReadMode() → if
Unify(Xn, *S) →
Xn ← Drf(Xn)
S ← S + 1
fi
fi
Esta instrução é gerada para argumentos de estruturas da cabeça que sejam variáveis
temporárias instanciadas com um valor global. Em modo de escrita o valor da variável é
simplesmente empilhado no heap. Em modo de leitura o argumento apontado por S é unificado
com a variável, sendo o resultado desreferenciado deixado na variável.
UnifyValue ψn
; ψ ∈ { Y, Z }
if
WriteMode() → Push(H, ψn)
ReadMode() → if
Unify(ψn, *S) → S ← S + 1
fi
fi
Esta instrução é gerada para argumentos de estruturas da cabeça que sejam variáveis
permanentes ou parâmetros de unit instanciados com um valor global. Em modo de escrita o
valor da variável é simplesmente empilhado no heap. Em modo de leitura o argumento
apontado por S é unificado com a variável.
B. Operações Básicas e Instruções da CxM
121
UnifyLocalValue Xn
if
WriteMode() →
t ← Drf(Xn)
if
IsLocalVar(t) →
Xn ← PushVar(H)
Assign(t, Xn)
not IsLocalVar(t) →
Xn ← t
Push(H, t)
fi
ReadMode() → if
Unify(Xn, *S) →
X ← Drf(Xn)
S ← S + 1
fi
fi
Esta instrução é gerada para argumentos de estruturas da cabeça que sejam variáveis
temporárias instanciadas com um valor não necessariamente global. Em modo de escrita o
valor da variável é empilhado no heap se não for uma referência para uma variável local. Caso
contrário ela é transferida para o topo do heap ficando X n a apontar para ela. Em modo de
leitura a instrução funciona como UnifyValue Xn .
UnifyLocalValue ψn
; ψ ∈ { Y, Z }
if
WriteMode() →
t ← Drf(ψn)
if
IsLocalVar(t) → Assign(t, PushVar(H))
not IsLocalVar(t) → Push(H, t)
fi
ReadMode() → if
Unify(ψn, *S) → S ← S + 1
fi
fi
Esta instrução é gerada para argumentos de estruturas da cabeça que sejam variáveis
permanentes ou parâmetros de unit instanciadas com um valor não necessariamente global.
Em modo de escrita o valor da variável é empilhado no heap se não for uma referência para uma
variável local. Caso contrário ela é transferida para o topo heap. Em modo de leitura a instrução
funciona como UnifyValue ψn .
UnifyConstant ϑ
if
WriteMode() → Push(H, ϑ)
ReadMode() → t ← Drf(*S)
S ← S + 1
if
IsVar(t) → Assign(t, ϑ)
t = ϑ → skip
fi
fi
Representa um argumento de uma estrutura da cabeça que é uma constante. Em modo de
escrita a constante é empilhada no heap. Em modo de leitura a constante é unificada com o
argumento apontado por S.
UnifyNil
if
WriteMode() → Push(H, [])
ReadMode() → t ← Drf(*S)
S ← S + 1
if
IsVar(t) → Assign(t, [])
t = [] → skip
fi
fi
Especialização da instrução anterior para ϑ = [].
B. Operações Básicas e Instruções da CxM
122
B.8. Instruções Build
Estas instruções são geradas apenas no corpo das cláusulas nos argumentos de
estruturas ou listas. Não existem na WAM.
BuildVoid N
dotimes(i,N) PushVar(H)
Representa N variáveis consecutivas de ocorrência única, nos argumentos de um estrutura
ocorrendo num golo da cláusula. São empilhadas N variáveis livres no topo do heap.
BuildVoidOne
PushVar(H)
Especialização da instrução anterior para n = 1.
BuildVariable ψn
; ψ ∈ { X, Y }
ψn ← PushVar(H)
Esta instrução é gerada para argumentos de estruturas que ocorram em golos do corpo que
sejam variáveis livres. ψn recebe um apontador para uma nova variável livre que é empilhada no
heap.
BuildValue ψn
; ψ ∈ { X, Y, Z }
Push(H, ψn)
Esta instrução é gerada para argumentos de estruturas de golos do corpo da cláusula que
sejam variáveis instanciadas com um valor global. O valor da variável é simplesmente
empilhado no heap.
BuildLocalValue Xn
t ← Drf(Xn)
if
IsLocalVar(t) →
Xn ← PushVar(H)
Assign(t, Xn)
not IsLocalVar(t) → Push(H, t)
fi
Esta instrução é gerada para argumentos de estruturas de golos do corpo da cláusula que
sejam variáveis temporárias instanciadas com um valor não necessariamente global. O valor da
variável é empilhado no heap se não for uma referência para uma variável local. Caso contrário
ela é transferida para o topo heap ficando Xn a apontar para ela.
BuildLocalValue ψn
; ψ ∈ { Y, Z }
t ← Drf(ψn)
if
IsLocalVar(t) → Assign(t, PushVar(H))
not IsLocalVar(t) → Push(H, t)
fi
Esta instrução é gerada para argumentos de estruturas de golos do corpo da cláusula, que
sejam variáveis permanentes ou parâmetros de unit instanciadas com um valor não
necessariamente global. O valor da variável é empilhado no heap se não for uma referência
para uma variável local. Caso contrário ela é transferida para o topo heap.
BuildConstant ϑ
Push(H, ϑ)
Representa uma constante como argumento de uma estrutura num golo da cláusula. Ela é
apenas empilhada no heap.
BuildNil
Push(H, [])
Especialização da instrução anterior para ϑ = [].
B. Operações Básicas e Instruções da CxM
123
B.9. Instruções de indexação
As instruções de indexação servem para ligar entre si as diversas cláusulas que
constituem um procedimento, e para efectuar uma pré-selecção das cláusulas a serem
consideradas após a invocação de um predicado, com base no valor do primeiro
argumento. Em relação à WAM surgem aqui diversas alterações: as instruções
SwitchOnConstant e SwitchOnStructure têm mais um argumento que se destina ao
suporte
do
índice
rápido,
foram
adicionadas
novas
instruções,MakeIndex,
SwitchOnList, SwitchOnFunctor e JumpOnVar, e a gestão dos pontos de escolha
recorre à utilização do novo registo L.
MakeIndex Pred
DoIndex(Pred)
P ← PredCode(Pred)
Esta é a instrução de ligação da CxM que se aplica a nomes de predicados definidos
localmente. Tal como as outras instruções de ligação, ela nunca é gerada pelo compilador mas
sim pelo módulo gestor da base de dados do sistema, que a coloca no campo Inst do descritor
do predicado nas circunstâncias descritas em 5.3. A instrução começa por chamar um módulo
do compilador que trata da construir o índice se valer a pena, e estabelece a ligação para o
predicado mediante a alteração do valor de PredCode(Pred). O controlo é então passado para o
código do predicado.
TryMeElse Next Arity
save ← B
L ← B ← TopOfLocalStack() - Arity - SizeOf(ChoicePoint)
B(P) ← Next
SaveState(Arity, save)
Esta instrução precede o código da primeira cláusula de um predicado composto por várias.
Ela cria um ponto de escolha e guarda nele o estado corrente da máquina. Arity representa a
aridade do predicado constituindo o número de registos X a salvaguardar no ponto de escolha.
Next é o endereço da próxima cláusula a ser considerada quando houver retrocesso.
RetryMeElse Next Arity
B(P) ← Next
RestoreState(Arity)
L ← B
Esta instrução precede o código de uma cláusula intermédia de um predicado composto por
várias. Ela repõe o estado guardado no último ponto de escolha e guarda nele o endereço da
próxima cláusula a considerada quando houver retrocesso.
TrustMe Arity
L ← B + Arity + SizeOf(ChoicePoint)
RestoreState(Arity)
B ← B(B)
HB ← B(H)
Esta instrução precede o código da última cláusula de um predicado composto por várias.
Ela repõe o estado guardado no último ponto de escolha eliminando-o seguidamente.
Try Label
arity ← *(Label - 1)
save ← B
L ← B ← TopOfLocalStack() - arity - SizeOf(ChoicePoint)
B(P) ← P + 1
SaveState(arity, save)
P ← Label
A instrução Try indica a primeira cláusula de uma sequência de cláusulas com a mesma
chave. Ela cria um ponto de escolha e guarda nele o estado corrente da máquina. Label é o
B. Operações Básicas e Instruções da CxM
124
endereço do início do código da cláusula a executar. Em caso de retrocesso será executada a
instrução Retry ou Trust que se encontra a seguir. A aridade do predicado é obtida acedendo ao
segundo argumento da instrução de indexação que se encontra no início da cláusula referida
por Label.
Retry Label
arity ← *(Label - 1)
B(P) ← P + 1
RestoreState(arity)
L ← B
P ← Label
A instrução Retry indica uma cláusula intermédia de uma sequência de cláusulas com a
mesma chave. Ela repõe o estado salvaguardado no último ponto de escolha e posiciona nele o
endereço da instrução seguinte, a ser considerado quando houver retrocesso.
Trust Label
arity ← *(Label - 1)
L ← B + arity + SizeOf(ChoicePoint)
RestoreState(arity)
B ← B(B)
HB ← B(H)
P ← Label
A instrução Trust indica a última cláusula de uma sequência de cláusulas com a mesma
chave. Ela repõe o estado guardado no último ponto de escolha eliminando-o seguidamente. O
controlo é então passado para o código da última cláusula do predicado.
SwitchOnTerm V C L S
t ← Drf(X0)
if
IsVar(t) → P ← V
IsAtomic(t) → P ← C
IsList(t) → P ← L
IsStruct(t) → P ← S
fi
Esta instrução inicia sempre o índice rápido e também algumas sub-sequências
constituintes do índice compacto (cf. 7.7). Ela passa o controlo para um de quatro diferentes
endereços, consoante o tipo do valor de X0 depois de desreferenciado. V, C, L, e S são os
endereços associados respectivamente a variável, constante, lista e estrutura.
SwitchOnList V C L S
t ← Drf(X0)
if
IsVar(t) → P ← V
IsAtomic(t) → if t = [] → P ← C fi
IsList(t) → P ← L
S ← ListArgs(t)
SetReadMode()
IsStruct(t) → P ← S
fi
Esta é uma especialização da instrução SwitchOnTerm. Aplica-se a um predicado que entre
as suas diversas cláusulas tenha apenas uma cujo primeiro argumento seja o átomo [], e outra
cujo primeiro argumento seja uma lista. A instrução executa logo no seu corpo as instruções
GetList X0 e GetNil X0, e salta por cima dessas instruções no código das cláusulas.
B. Operações Básicas e Instruções da CxM
125
SwitchOnFunctor V C L S
t ← Drf(X0)
if
IsVar(t) → P ← V
IsAtomic(t) → P ← C
IsList(t) → P ← L
IsStruct(t) →
if StructFunctor(t) = *(S-1) →
P ← S
S ← StructArgs(t)
SetReadMode()
fi
fi
Esta é uma especialização da instrução SwitchOnTerm. Aplica-se a um predicado que entre
as suas diversas cláusulas tenha apenas uma cujo primeiro argumento seja uma estrutura. A
instrução executa logo no seu corpo a instrução GetStruct Φ, X0, e saltando por cima dela no
código da cláusula.
JumpOnVar Label
t ← Drf(X0)
if
IsVar(t) → P ← V
not IsVar(t) → skip
fi
Esta instrução surge sempre, e apenas, no início do índice compacto (cf. 7.7.3). Ela passa o
controlo para o endereço Label se o valor de X0 depois de desreferenciado for uma variável.
SwitchOnConstant N Table Else
t ← Drf(X0)
res ← HashVal(t,N,Table)
if
res <> nil → P ← res
res = nil → P ← Else
fi
Esta instrução é gerada para controlar o acesso a um grupo de cláusulas cujos primeiros
argumentos sejam constantes. Table é o endereço de uma tabela de dispersão na qual, para
cada uma dessas constantes, está registado o endereço do código a executar. Se o valor de X0
não estiver previsto na tabela, o controlo passa para o endereço Else. N é uma potência de 2 que
indica o tamanho da tabela de dispersão.
SwitchOnStructure N Table Else
t ← Drf(X0)
t ← StructFunctor(t)
res ← HashVal(t,N,Table)
if
res <> nil → P ← res
res = nil → P ← Else
fi
Esta instrução é parecida com a anterior e aplica-se a grupos de cláusulas cujos primeiros
argumentos sejam estruturas. A selecção é efectuada na tabela de dispersão Table com base no
functor principal do primeiro argumento da chamada.
B.10. Instruções para fórmulas de extensão
Estas são todas as instruções específicas para tratamento das fórmulas de
extensão. Existem instruções para estender e contrair o contexto corrente, e
instruções para efectuar chamadas de nomes que ocorrem em fórmulas de extensão.
B. Operações Básicas e Instruções da CxM
126
PushContext Unit FirstReg EnvSize
n ← UnitNEnvCells(Unit)
L ← C ← GTopOfLocalStack(EnvSize) - n - SizeOf(UnitInstance)
C(U) ← Unit
C(C) ← CC
C(N) ← n
dotimes(i, n) C(Cache)3*i ← 0
dotimes(i, UnitArity(Unit)) Zi ← Xi+FirstReg
CC ← C
Esta instrução é gerada para as fórmulas de extensão U>>G nos casos em que U é um
designador de unit. A instrução precede o código do golo G. Ela empilha no stack local uma nova
instância de unit e preenche os seus diversos campos. Unit é uma referência para a unit que
estende o contexto, FirstReg o índice do registo X a partir do qual vêm os argumentos do
designador de unit e EnvSize é o tamanho do registo de activação corrente no ponto em que
surge a fórmula. Os parâmetros da unit (variáveis Z) são inicializados a partir dos registos X, e
as posições da cache das chamadas dependentes do contexto correspondentes ao número de
versão são inicializadas com um valor impossível, neste caso zero, para forçar o
estabelecimento de ligações na fase inicial de utilização da cache. No final CC recebe C: sendo
a lógica da utilização do registo CC semelhante à da utilização de CP aquela atribuição poderia
ser feita em todas as chamadas de predicado; no entanto para não prejudicar os programas que
não usem contextos, a atribuição é feita nas instruções de expansão e contracção do contexto
sempre na espectativa que uma dessas chamadas seja feita.
PushVarContext UseReg EnvSize
t ← Drf(XUseReg)
Unit ← TermToUnit(t)
if
Unit <> nil → skip
fi
n ← UnitNEnvCells(Unit)
L ← C ← GTopOfLocalStack(EnvSize) - n - SizeOf(UnitInstance)
C(U) ← Unit
C(C) ← CC
C(N) ← n
dotimes(i, n) C(Cache)3*i ← 0
dotimes(i, UnitArity(Unit)) Zi ← Drf(StructArgs(t)i)
CC ← C
Esta instrução é gerada para as fórmulas de extensão U>>G nos casos em que U é uma
variável. Ela precede o código do golo G. Empilha no stack local uma nova instância de unit e
preenche os seus campos. O argumento UseReg é o índice do registo X onde se encontra o
designador da unit que estende o contexto e EnvSize e o tamanho do registo de activação
corrente no ponto em que surge a fórmula. Os parâmetros da unit (variáveis Z) são inicializados
a partir dos argumentos do designador de unit que se encontra no registo X UseReg. A forma da
inicialização da cache e a razão da transferência de C para CC são explicados na instrução
anterior.
PopContext
if
L = C → L ← C + C(N) + SizeOf(UnitInstance)
L <> C → skip
fi
C ← CC ← C(C)
Esta instrução é gerada em todas as fórmulas de extensão U>>G aparecendo imediatamente
a seguir ao código do golo G. Em primeiro lugar ela remove a instância de unit que se encontra
no topo do contexto corrente, caso o golo G tenha sido resolvido deterministicamente. Isto pode
ser detectado através de uma comparação de L com C pois aquela condição verifica-se se e só
se a instância da unit estiver no topo do stack local. Seguidamente os valores de C e CC são
repostos.
B. Operações Básicas e Instruções da CxM
127
MakeCtxExtBinding Pred
DoCtxExtBind(Pred)
P ← PredCode(Pred)
Esta é a instrução de ligação da CxM que se aplica a nomes de predicado que surgem no
interior das fórmulas de extensão de contexto. Tal como as outras instruções de ligação, ela é
gerada pelo módulo gestor da base de dados do sistema, que a coloca no campo Inst do
descritor do predicado nas circunstâncias descritas em 5.3. A instrução começa por chamar um
módulo do compilador que estabelece a ligação para o predicado mediante a alteração do valor
de PredCode(Pred). O controlo é então passado para esse endereço.
CtxExtJump ExternPred
P ← PredCode(ExternPred)
Esta instrução encontra-se nos descritores de nomes de predicado que ocorrem em
fórmulas de extensão, nos casos em que foi possível estabelecer uma ligação estática em
virtude do facto desse nome ser visível na unit que estendeu o contexto. Ela tem como
argumento o descritor de nome de predicado externo chamado, e executa um simples salto
inter-units, passando o controlo para o código desse predicado.
CtxExtJumpBelow Functor
P ← PredCode(SearchContextBelow(Functor))
Esta instrução encontra-se nos descritores de nomes de predicados que ocorrem em
fórmulas de extensão, nos casos em que esse nome não é visível na unit que estendeu o
contexto. Ela tem como argumento o functor indicador do nome de predicado externo chamado,
e efectua uma busca no contexto corrente de uma definição visível aplicável. O topo do contexto
é ignorado na busca visto que na altura do estabelecimento da ligação (feita pela instrução
MakeCtxExtBinding) ter sido determinada a inexistência de definição adequada nele.
VarCtxExtCall Functor UCache
if
C(U) = UCache(Unit) → pred ← UCache(Pred)
C(U) <> UCache(Unit) → pred ← FindVisiblePred(C(U), Functor)
UCache(Unit) ← C(U)
UCache(Pred) ← pred
fi
B0 ← B
CP ← P + 1
if
pred <> nil → P ← PredCode(pred)
pred = nil → P ← PredCode(SearchContextBelow(Functor)))
fi
É gerada para fórmulas da forma U>>g em que U é variável, para fazer a chamada do nome
associado ao golo g. Esta instrução usa uma pequena cache de duas palavras que permite
detectar se o valor de U se mantém desde a última chamada. Se assim for usa-se a definição de
predicado que se encontra nessa cache, caso contrário procura-se na unit corrente a definição
de predicado, que é de imediato memorizada na cache. Finalmente efectua-se a chamada do
predicado assim obtido. Note-se que, apesar de ser improvável, pode acontecer que o nome do
golo g não esteja visível em U: nesse caso é sempre necessário efectuar uma busca no contexto
corrente, não podendo neste caso a definição de predicado obtida ficar memorizada na cache
por razões de coerência desta.
B.11. Instruções de importação
Estas são as instruções de tratamento de chamadas de nomes importados. Existem
instruções específicas para manipular o contexto corrente e instruções para efectuar
chamadas de nomes importados.
B. Operações Básicas e Instruções da CxM
128
SwitchContextOn Unit FirstReg
n ← UnitNEnvCells(Unit)
L ← C ← TopOfLocalStack() - n - SizeOf(UnitInstance)
C(U) ← Unit
C(S) ← CC
C(C) ← CC(C)
C(N) ← n
dotimes(i, n) C(Cache)3*i ← 0
dotimes(i, UnitArity(Unit)) Zi ← Xi+FirstReg
CC ← C
Esta instrução é gerada pelo compilador, quando produz o segmento de código de ligação
que faz a chamada do nome de predicado de um golo g, importado de um designador de unit U.
Esta instrução aparece sempre antes da instrução de chamada de g. É muito semelhante à
instrução PushContext pois também empilha uma instância de unit no stack local e inicia-a. A
única diferença importante reside no facto de esta operação não fazer uma extensão de
contexto, mas sim uma substituição da instância de unit do topo do contexto. Por isso o campo
C da nova instância de unit toma o mesmo valor que o campo C do anterior topo do contexto. O
topo do contexto anterior é por sua vez guardado no campo S, para posterior reposição.
SwitchVarContextOn UseReg
t ← Drf(XUseReg)
Unit ← TermToUnit(t)
if
Unit <> nil → skip
fi
n ← UnitNEnvCells(Unit)
L ← C ← TopOfLocalStack() - n - SizeOf(UnitInstance)
C(U) ← Unit
C(S) ← CC
C(C) ← CC(C)
C(N) ← n
dotimes(i, n) C(Cache)3*i ← 0
dotimes(i, UnitArity(Unit)) Zi ← Drf(StructArg(t, i))
CC ← C
Esta instrução é gerada pelo compilador quando produz o segmento de código de ligação que
faz a chamada do nome de predicado de um golo g importado de um parâmetro de unit U. A
instrução aparece sempre antes da instrução de chamada de g. É muito semelhante à instrução
PushVarContext com apenas a diferença de não fazer uma extensão de contexto, mas sim uma
substituição lógica da instância de unit que se encontra topo do contexto.
SwitchContextOff
if
L = C → L ← C + C(N) + SizeOf(UnitInstance)
L <> C → skip
fi
C ← CC ← C(S)
Esta instrução aparece no segmento de código de ligação que faz a chamada do nome de
predicado de um golo g, importado de um parâmetro de unit U. A instrução aparece depois da
instrução de chamada de g. Em primeiro lugar ela remove a instância de unit que se encontra no
topo do contexto corrente, caso o golo g tenha sido resolvido deterministicamente.
Seguidamente os valores de C e CC são repostos usando o campo S dessa instância de unit.
MakeImportBinding Pred
DoImport(Pred)
P ← PredCode(Pred)
Esta é a instrução de ligação da CxM que se aplica a nomes de predicado importados. É
gerada pelo módulo gestor da base de dados do sistema, que a instala no descritor do predicado
como é explicado em 5.3. A instrução começa por chamar um módulo do compilador que gera
um segmento de código onde o predicado importado é chamado no contexto modificado. O
controlo passa seguidamente para esse código. Existe mais informação sobre esta instrução no
ponto 5.3.2.2.
B. Operações Básicas e Instruções da CxM
129
ImportJumpBelow Functor
P ← PredCode(SearchContextBelow(Functor))
Esta instrução encontra-se nos descritores de nomes de predicados importados, nos casos
em que esse nome não é visível no designador de unit de onde a importação é feita. Ela tem
como argumento o functor indicador do nome de predicado chamado, e efectua uma busca no
contexto corrente de uma definição visível aplicável. O topo do contexto é ignorado na busca
visto que na altura do estabelecimento da ligação (feita pela instrução MakeImportBinding), ter
sido determinada a inexistência de definição adequada nele (de facto o topo do contexto nem
chega a ser mudado antes da execução desta instrução, por tal se revelar desnecessário).
VarImportCall Functor UCache
if
C(U) = UCache(Unit) → pred ← UCache(Pred)
C(U) <> UCache(Unit) → pred ← FindVisiblePred(C(U), Functor)
UCache(Unit) ← C(U)
UCache(Pred) ← pred
fi
B0 ← B
CP ← P + 1
if
pred <> nil → P ← PredCode(pred)
pred = nil → P ← PredCode(SearchContextBelow(Functor)))
fi
Esta instrução é gerada nas chamadas de predicados importados de parâmetros de unit. Ela
usa uma pequena cache de duas palavras que permite detectar se o valor de U se mantém desde
a última chamada. A descrição que aqui se apresenta é rigorosamente igual à da instrução
VarCtxExtCall. As diferenças entre as duas situam-se a um nível de que aqui não está a ser
considerado, que é o da sua relação com o ambiente de programação, neste caso as facilidades
de depuração (ver descrição do predicado status/2).
B.12. Instruções para nomes dependentes do contexto
Existem apenas as duas seguintes instruções relacionadas com as chamadas de
nomes dependentes do contexto.
MakeCtxDepBinding Pred
DoCtxDepBind(Pred)
P ← PredCode(Pred)
Esta é a instrução de ligação da CxM que se aplica a nomes de predicado dependentes do
contexto. É gerada pelo módulo gestor da base de dados do sistema, que a instala no descritor
do nome de predicado. De acordo com o que foi dito no ponto 5.3.2.4 esta instrução associa um
deslocamento na cache ao nome dependente do contexto e instala a instrução CtxDepJump,
que tem por argumento esse deslocamento, no descritor de predicado. O controlo passa então
para essa instrução.
B. Operações Básicas e Instruções da CxM
130
CtxDepJump Functor CacheOffset
if
CacheOffset < C(N) →
if
C(Cache)CacheOffset = Version(Functor) →
P ← PredCode(C(Cache)CacheOffset+1)
C ← C(Cache)CacheOffset+2
C(Cache)CacheOffset <> Version(Functor) →
CC(Cache)CacheOffset ← Version(Functor)
CC(Cache)CacheOffset+1 ←
SearchContextBelow(Functor))
CC(Cache)CacheOffset+2 ← C
P ← PredCode(C(Cache)CacheOffset+1)
fi
CacheOffset >= C(N) → P ← PredCode(SearchContextBelow(Functor))
fi
Esta instrução aplica-se à chamada de nomes dependentes do contexto. Não é gerada pelo
compilador mas sim pela instrução MakeCtxDepBinding. Ela testa primeiro o argumento
CacheOffset verificando se ele é abrangido pela cache da instância da unit corrente. Em caso
negativo tem de ser feita dinamicamente uma procura no contexto corrente de uma definição de
predicado visível compatível com o argumento Functor. Em caso afirmativo compara-se a
versão corrente do functor com aquela que se encontra memorizada na cache. Se os valores
forem iguais isto significa que a informação da cache para aquele nome está actualizada
podendo ser usada imediatamente. Se os valores forem diferentes a informação da cache para
esse nome tem de ser actualizada o que envolve uma pesquisa no contexto corrente.
B.13. Instruções de gestão do contexto histórico
Estas instruções são usadas no controlo do contexto histórico.
PushHistoricalContext EnvSize
save ← C2
L ← C2 ← GTopOfLocalStack(EnvSize)) - SizeOf(HistoricalRegister)
C2(C) ← C
C2(C2) ← save
C2(R2) ← C2
Esta instrução é gerada para as fórmulas de salvaguarda de contexto >G, aparecendo
sempre antes do código do golo G. Ela empilha no stack local um novo registo histórico e
preenche os seus campos. Guarda em particular o contexto corrente no campo C e uma
auto-referência no campo R2. Recordemos que no esquema de representação dos contextos
históricos (ver 4.4.7.1) o campo R2 do registo histórico que se encontra no topo, indica o topo do
registo histórico conceptual. Assim fica justificado o uso da auto-referência pois neste caso os
topos dos contextos históricos, implementacional e lógico, coincidem. O argumento EnvSize é o
tamanho do registo de activação corrente, no ponto em que surge a fórmula.
PopHistoricalContext
if
L = C2 → L ← C2 + SizeOf(HistoricalRegister)
L <> C2 → skip
fi
C2 ← C2(C2)
Esta instrução é gerada para as fórmulas de salvaguarda de contexto >G, aparecendo
sempre logo depois do código do golo G. O registo histórico do topo é desempilhado, sendo
recuperado o seu espaço, caso o golo G tenha sido resolvido deterministicamente. Esta
condição pode ser detectado através de uma simples comparação de L com C2.
B. Operações Básicas e Instruções da CxM
131
EnterHistoricalContext EnvSize
conceptualTop ← C2(R2)
if
conceptualTop = C2Base → Error("No saved context")
conceptualTop <> C2Base → skip
fi
save ← C2
L ← C2 ← GTopOfLocalStack(EnvSize)) - SizeOf(HistoricalRegister)
C2(C) ← C
C2(C2) ← save
C2(R2) ← conceptualTop(C2)(R2)
C ← CC ← conceptualTop(C)
Esta instrução é gerada para as fórmulas de reposição de contexto <G, aparecendo sempre
antes do código do golo G. Ela repõe o contexto situado no topo do contexto histórico
conceptual e, além disso, empilha no stack local um novo registo histórico onde memoriza o
contexto corrente (pois a reposição de contexto é temporária) e o novo topo do contexto
histórico conceptual, que se reduz (apesar do implementacional aumentar).
ExitHistoricalContext
if
L = C2 → L ← C2 + SizeOf(HistoricalRegister)
L <> C2 → skip
fi
C ← CC ← C2(C)
C2 ← C2(C2)
Esta instrução é gerada para as fórmulas de reposição de contexto <G, aparecendo sempre
depois do código do golo G. O registo histórico do topo é desempilhado, sendo recuperado o
espaço ocupado por ele, caso o golo G tenha sido resolvido deterministicamente. Além disso o
estado dos registos C e CC anterior à reposição do contexto é restaurado.
132
C
Exemplos de código gerado
Exibimos aqui alguns exemplos de codificação de cláusulas na CxM, muitos dos
quais são extraídos de [Warren 83], o que facilita o estabelecimento de uma
comparação com o código gerado para a WAM. Todas as listagens de código foram
obtidas, usando o disassembler incorporado no sistema, que é invocado através do
predicado code/2. O código foi compilado com o indicador do sistema specialize
desligado (cf. predicado status/2 no apêndice A), a fim de o código ficar mais legível.
qsort([],R,R).
qsort([X|L],R0,R) :split(L,X,L1,L2), qsort(L1,R0,[X|R1]), qsort(L2,R1,R).
f5c44 SwitchOnList f4bf0 f4c04 f4c88 FAIL f4cc0
f5c58 Proceed
f4ccc
f4cd8
f4bf0 TryMeElse f4c74 3
f4ce4
f4bfc GetNil X0
f4cf0
f4c04 GetXValue X1 X2
f4cfc
f4c10 Proceed
f4d04
f4d0c
f4c74 TrustMe 3
f4d14
f4c80 GetList X0
f4d20
f4c88 Allocate
f4d2c
f4c8c UnifyYVariable Y5
f4d38
f4c94 UnifyXVariable X0
f4d44
f4c9c GetYVariable Y4 X1
f4ca8 GetYVariable Y2 X2
f4cb4 PutYValue Y5 X1
PutYVariable Y3 X2
PutYVariable Y0 X3
Call split/4 6
PutYValue Y3 X0
PutYValue Y4 X1
PutList X2
BuildYValue Y5
BuildYVariable Y1
Call qsort/3 4
PutUnsafeValue Y0 X0
PutYValue Y1 X1
PutYValue Y2 X2
DeallocateAndExecute qsort/3
C. Exemplos de código gerado
compile(Clause, Instructions) :preprocess(Clause, C1),
translate(C1, Symbols),
number_variables(Symbols, 0, N, Saga),
complete_saga(0, N, Saga),
allocate_registers(Saga),
generate(Symbols, Instructions).
f4f70
f4f74
f4f80
f4f8c
f4f98
f4fa4
f4fb0
f4fbc
f4fc8
f4fd4
f4fe0
Allocate
GetYVariable Y1 X1
PutYVariable Y4 X1
Call preprocess/2 5
PutYValue Y4 X0
PutYVariable Y0 X1
Call translate/2 5
PutYValue Y0 X0
PutConstant 0 X1
PutYVariable Y3 X2
PutYVariable Y2 X3
f4fec
f4ff8
f5004
f5010
f501c
f5028
f5034
f5040
f504c
f5058
Call number_variables/4 4
PutConstant 0 X0
PutYValue Y3 X1
PutYValue Y2 X2
Call complete_saga/3 4
PutYValue Y2 X0
Call allocate_registers/1 3
PutUnsafeValue Y0 X0
PutYValue Y1 X1
DeallocateAndExecute generate/2
d(U*V, X, (DU*V)+(U*DV)) :- d(U,X,DU), d(V,X,DV).
f5178
f5184
f518c
f5190
f5198
f51a4
f51b0
f51b8
f51c0
f51cc
GetStructure */2 X0
UnifyXVariable X0
Allocate
UnifyYVariable Y2
GetYVariable Y1 X1
GetStructure +/2 X2
UnifyXVariable X3
UnifyXVariable X4
GetStructure */2 X3
UnifyXVariable X2
f51d4
f51dc
f51e8
f51f0
f51f8
f5204
f5210
f521c
f5228
f5234
UnifyYValue Y2
GetStructure */2 X4
UnifyXValue X0
UnifyYVariable Y0
PutYValue Y1 X1
Call d/3 3
PutYValue Y2 X0
PutYValue Y1 X1
PutYValue Y0 X2
DeallocateAndExecute d/3
test :- do(parse(s(np,vp),[birds,fly],[])).
f5378
f5380
f5388
f538c
f5394
f539c
f53a4
PutList X1
BuildConstant 'fly'
BuildNil
PutList X2
BuildConstant 'birds'
BuildXValue X1
PutStructure s/2 X1
f53b0
f53b8
f53c0
f53cc
f53d4
f53dc
f53e0
BuildConstant 'np'
BuildConstant 'vp'
PutStructure parse/3 X0
BuildXValue X1
BuildXValue X2
BuildNil
Execute do/1
f5b74
f5b7c
f5b84
f5b8c
f5b94
f5b9c
f5ba4
f5bac
f5bb4
Try f56d8
Retry f5758
Retry f5804
Trust f5840
Try f5618
Retry f56d8
Trust f5758
Try f5664
Retry f56d8
q(X + Y) :- q(X).
q(X + Y) :- q(Y).
q(trace) :- trace.
q(notrace) :- notrace.
q(nl) :- nl.
q(X) :- sys(X).
q(X) :- ext(X).
q(q(X)) :- q(X).
q(repeat).
q(repeat) :- q(repeat).
q(true).
f5b40 SwitchOnTerm f5478 f5b64 f5b54 f5bf4
f5b54 Try f56d8
f5b5c Trust f5758
f5b64 SwitchOnConstant f5ac0 8 f5b54
nl f5bac
repeat f5b74
trace f5bc4
notrace f5b94
true f5bdc
133
C. Exemplos de código gerado
f5bbc
f5bc4
f5bcc
f5bd4
f5bdc
f5be4
f5bec
f5bf4
f5c04
f5c0c
f5c14
f5c1c
f5c24
f5c2c
f5c34
f5c3c
Trust f5758
Try f5594
Retry f56d8
Trust f5758
Try f56d8
Retry f5758
Trust f58a0
SwitchOnStructure f5b24 2 f5b54
+/2 f5c04
q/1 f5c24
Try f5484
Retry f54f0
Retry f56d8
Trust f5758
Try f56d8
Retry f5758
Trust f57a0
Proceed
f5478
f5484
f5490
f5498
f549c
TryMeElse f54e4 1
GetStructure +/2 X0
UnifyXVariable X0
UnifyVoidOne
Execute q/1
f54e4
f54f0
f54fc
f5500
f5508
RetryMeElse f5588 1
GetStructure +/2 X0
UnifyVoidOne
UnifyXVariable X0
Execute q/1
f5588 RetryMeElse f560c 1
f5594 GetConstant 'trace' X0
f55a0 Execute trace/0
f560c RetryMeElse f5658 1
f5618 GetConstant 'notrace' X0
f5624 Execute notrace/0
f5658
f5664
f5670
f5674
RetryMeElse f56cc 1
GetConstant 'nl' X0
nl/0
Proceed
f56cc RetryMeElse f574c 1
f56d8 Execute sys/1
f574c RetryMeElse f5794 1
f5758 Execute ext/1
f5794
f57a0
f57ac
f57b4
RetryMeElse f57f8 1
GetStructure q/1 X0
UnifyXVariable X0
Execute q/1
f57f8 RetryMeElse f5834 1
f5804 GetConstant 'repeat' X0
f5810 Proceed
f5834
f5840
f584c
f5858
RetryMeElse f5894 1
GetConstant 'repeat' X0
PutConstant 'repeat' X0
Execute q/1
f5894 TrustMe 1
f58a0 GetConstant 'true' X0
f58ac Proceed
a(X,Y) :- Y >>b(X).
a(X,Y) :- X >>b(Y).
a(X,Y) :- hello(x,Y) >> (>b(X)).
f5920
f592c
f5930
f593c
f5944
f5948
TryMeElse f5990 2
Allocate
PushVarContext X1 0
VarCtxExtCall b/1
PopContext
DeallocateAndProceed
f5990
f599c
f59a0
f59ac
f59b8
f59c0
RetryMeElse f5a44 2
Allocate
PushVarContext X0 0
PutXValue X1 X0
VarCtxExtCall b/1
PopContext
f59c4 DeallocateAndProceed
f5a44
f5a50
f5a54
f5a60
f5a6c
f5a7c
f5a84
f5a90
f5a94
f5a98
TrustMe 2
Allocate
PutConstant 'x' X2
PutXValue X1 X3
PushContext hello 2 0
PushHistoricalContext 0
Call b/1@hello 0
PopHistoricalContext
PopContext
DeallocateAndProceed
unit authors(Work).
import wrote/2 from Work.
author(X) :- wrote(X,_).
wrote/2:
f4fd0 Allocate
f4fd4 PutZValue Z0 X2
f4fe0 SwitchVarContextOn X2
f4fe8 VarImportCall wrote/2
f4ff0 SwitchContextOff
f4ff4 DeallocateAndProceed
author/1:
f4d5c TryMeElse f4e58 1
f4d68 PutVariableOne X1
f4d70 Execute wrote/2
134
135
Bibliografia
[Aït-Kaci 90]
Aït-Kaci, H.: “The WAM: A (Real) Tutorial”, Digital, Paris Research Laboratory,
Janeiro 1990
[Aho 86]
Aho, A.; Sethi, R.; Ullman, J.: “Compilers, Principles, Techniques and Tools”
Addison Wesley 1986
[Appleby 88]
Appleby, K.; Carlsson, M.; Haridi, S.; Sahlin D.: “Garbage Collection for Prolog
based on WAM” em Communications of the ACM, Vol. 31, Nº 6, Junho 1988
[Bacha 87]
Bacha, H: “Meta-level Programming: a Compiled Approach”, em Proc. 4º ICLP,
Melbourne, Australia, MIT Press, 1987
[Bacha 88]
Bacha, H: “Meta-Prolog Design and Implementation”, em Proc. 5º ICLP, USA, MIT
Press, 1988
[Battani 73]
Battani, G.; Meloni, H.: “Interpréteur du language de programmation Prolog””,
Groupe d’Intelligence Artificielle, Université d’Aix-Marseille, 1973
[Bell 73]
Bell, J.: “Threaded code”, em Communications of the ACM, Vol. 16, 370-372, 1973
[Bendl 80]
Bendl, J.; Köves, P; Szeredi P.: “The MProlog System”, em Tärnlund 1980, pp.201209
Bibliografia
136
[Bowen 83]
Bowen, L.; Byrd D.; Clocksin W.: “A Portable Prolog Compiler”, em Logic
Programming Workshop ‘83
[Bowen 86]
Bowen, K.; Buettner K.; Cicekli I.; Turk A.: “The Design and Implementation of a
High-Speed Incremental Portable Prolog Compiler”, em Proc. 3º ICLP, London,
Springer-Verlag, 1986
[Bruynooghe 76]
Bruynooghe, M: “An Interpreter for Predicate Logic Programs: Part I”, Report CW
10, Applied Mathematics and Programming Division, Katholieke Universiteit,
Leuven, Belgica 1976
[Bruynooghe 82]
Bruynooghe, M: “The Memory Management of Prolog Implementations”, em Logic
Programming, Academic Press, 1982
[Buettner 86]
Buettner, K.: “Fast Decompilation of Compiler Prolog Clauses”, em Proc. 3º ICLP,
London, Springer-Verlag, 1986
[Caneghem 86]
Caneghem, M.: “L’Anatomie de Prolog”, Inter Editions, Paris, 1986
[Clocksin 81]
Clocksin, W; Mellish, C.: “Programming in Prolog”, Springer-Verlag, 1981
[Clocksin 85]
Clocksin, W: “Implementation Techniques for Prolog Data Bases”, em Software Practice and Experience, vol.15, 1985
[Colmerauer 72]
Colmerauer, A.; Kanoui, H.; Pasero, R.; Roussel, P.: “Un système de communication
homme-machine en français”, Groupe d’Intelligence Artificielle, Université
d’Aix-Marseille, Outubro de 1972
[Colmerauer 75]
Colmerauer, A.: “Les grammaires de métamorphose, ”, Groupe d’Intelligence
Artificielle, Université d’Aix-Marseille, Novembro de 1975
[Colmerauer 85]
Colmerauer, A.: “Prolog in 10 Figures”, em Communications of the ACM, Vol. 28,
1296-1310, 1985
[Cousot 77]
Cousot, P.; Cousot, R.: “Abstract Interpretation: A Unified Lattice Model for Static
Analisys of Programs by Construction or Approximation of Fixpoints”, em Conf.
Rec. 4th ACM Symp. on Princ. of Programming Languages, 1977
[Debray 86a]
Debray, S.: “Register Allocation in a Prolog Machine”, em Proc. Symp. on Logic
Programming, Salt Lake City, USA, 1986
[Debray 86b]
Debray, S.; Warren D.: “Automatic Mode Inference for Prolog Programs”, em Proc.
Symp. on Logic Programming, Salt Lake City, USA, 1986
Bibliografia
137
[Debray 86c]
Debray, S.; Warren D.: “Detection and Optimization of Functional Computations
in Prolog”, em Proc. 3º ICLP, Londres, 1986
[Dewar 75]
Dewar, R.: “Indirect Threaded Code”, em Communications of the ACM, Vol. 18, 330331, 1975
[Dijkstra 76]
Dijkstra, E.: “A Discipline of Programming”, Prentice Hall, 1976
[Gabriel 85]
Gabriel, J.; Lindholm, T.; Lusk, E.; Overbeek, R.: “A Tutorial on the Warren
Abstract Machine”, Argonne National Laboratory, 1985
[Goldberg 83]
Goldberg, A.; Robson D.: “Smalltalk-80, The Language and Its Implementation”,
Addison Wesley, 1983
[Goldberg 83]
Goldberg, A.:“Smalltalk-80,
Addison Wesley, 1983
The
Interactive
Programming
Environment”,
[Goodwin 81]
Goodwin, J.: “Why Programming Environments Needs Dynamic Data Types”, IEEE
Transactions on Software Engineering, val.SE-7,No.5, 1981
[Emden 81]
Emden, M.: “An Algorithm for Interpreting Prolog Programs”, Department of
Computer Science, University of Waterloo, Ontário, Canada, Research Report CS81-28, Setembro 1981
[Green 68]
Green, C.: “Theorem-Proving by Resolution as a Basis for Question-Answering
Systems”, Machine Intelligence 4, B. Meltzer e D. Michie (Eds.), Edinburgh
University Press, 1968
[Hermenegildo 89]
Hermenegildo, M.: “High-Performance Prolog Implementation: the WAM and
Beyond”, Tutorial, 6º ICLP, Lisboa, Portugal, 1989
[Hogger 84]
Hogger, C.J.: “Introduction to Logic Programming”, Academic Press, 1984
[Janssens 88]
Janssens, G.; Demoen, B.; Marien, A.: “Improving the Register Allocation in WAM
by reordering unification”, em Proc. 5º ICLP, USA, MIT Press, 1988
[Kerninghan 87]
Kerninghan B.; Ritchie D. "The C programming language". Prentice-Hall, 1987
[Klint 81]
Klint, P.: “Interpretation Techniques”, em Software - Practice and Experience,
vol.11, 1981
[Kluzniak 85]
Kluzniak, F.; Bien J.: “Prolog for Programmers”, Academic Press, 1985
Bibliografia
138
[Kowalski 74]
Kowalski, R.; van Emden: “The Semantic of predicate logic as programming
language”, DCL memo 73, University of Edinburgh, 1974
[Kowalski 79a]
Kowalski, R.: “Logic for Problem Solving”, North-Holland, 1979
[Kowalski 79b]
Kowalski, R.: “Algorithm = Logic + Control”, Communications of the ACM, 22,
1979
[Krasner 83]
Krasner, G.: “Smalltalk-80, Bits of History, Words of Advice”, Addison Wesley,
1983
[Lamma 89]
Lamma, E.; Mello P.; Natali A.: “The design of an Abstract Machine for Efficient
Implementation of Contexts in Logic Programming”, em Proc. 6º ICLP, Lisboa,
Portugal, MIT Press, 1989
[Lloyd 87]
Lloyd, W.: “Foundations of Logic Programming”, Springer-Verlag, 1987
[Maier 88]
Maier, D.; Warren, D. S.: “Computing with Logic”, Benjamin Cummings Publishing
Company, 1988
[Mamede 89]
Mamede M.: “Programação em Lógica por Restrições”, Report 39/89 - DI/UNL,
Universidade Nova de Lisboa, 1989
[Martelli 82]
Martelli, A.; Montanari, U.: “An Efficient Unification Algorithm”,
Transactions on Programming Languages and Systems, 4, 2, 1982
ACM
[Mellish 82]
Mellish, C.: “An Alternative to Structure Sharing in the Implementation of a
Prolog Interpreter”, em Logic Programming, Academic Press, 1982
[Mellish 85]
Mellish, C.: “Some Global Optimizations for a Prolog Compiler”, em Journal of
Logic Programming, 1, 1985
[Miller 86]
Miller, D.: “A Theory of Modules for Logic Programming”, em Proc. Symp. on Logic
Programming, Salt Lake City (USA), 1986
[Monteiro 89a]
Monteiro, L.; Porto A.: “Contextual Logic Programing”, em Proc. 6º ICLP, Lisboa,
Portugal, MIT Press, 1989
[Monteiro 89b]
Monteiro, L.; Pedro. V.: “Cactus - a CxLP Preprocessor”, Internal Report - DI/UNL,
Universidade Nova de Lisboa, 1989
[Monteiro 89c]
Monteiro, L.; Porto A.: “Description of a Basic System for Contextual Logic
Programing”, Report 36/89 - DI/UNL, Universidade Nova de Lisboa, 1989
Bibliografia
139
[Moss 86]
Moss, C.: “CUT & PASTE - defining the impure Primitives of Prolog”, em Proc. 3º
ICLP, London, Springer-Verlag, 1986
[Odette 87]
Odette, L.: “How to Compile Prolog”, em AI Expert, Agosto 1987
[Pereira 80]
Pereira, L.M.; Porto A.: “An Interpreter for Logic Programs using Selective
Backtracking”, Report 3/80, Centro de Informática da Universidade Nova de
Lisboa, 1980
[Pereira 82]
Pereira, L.M.; Porto A.: “Selective backtracking for logic programs”, em Logic
Programming, Academic Press, 1982
[Plotkin 81]
Plotkin, G.D.: “A Structural Approach to Operational Semantics”, DAIMI
Technical Report FN-19, Computer Science Department, Aarhus University, 1981
[Porto 87]
Porto A., Pereira L. M., Trindade L.: “UNL Prolog User’s Guide Manual”,
Departamento de Informática, Universidade Nova de Lisboa, Maio de 1987
[Robinson 65]
Robinson, J.: “A Machine-Oriented Logic Based on the Resolution Principle”,
Journal of the ACM 12, 23-41, 1965
[Robinson 80]
Robinson, J.; Sibert E.: “Logic Programming in Lisp”, Research Report, School of
Computer and Information Science, Syracuse University, New York, 1980
[Roussel 75]
Roussel, P.: “Prolog, Manuel de Référence et d'Utilisation”, Groupe d'Intelligence
Artificielle, Université d'Aix-Marseille, 1975
[Russinoff 89]
Russinoff, D.: “A Verified Prolog Compiler for the Warren Abstract Machine”, MCC
Technical Report ACT-ST-292-89, Microelectronics and Computer Technology
Corp., Austin, USA, Julho 89
[Sterling 86]
Sterling, L.; Shapiro E.: “The Art of Prolog”, MIT Press, 1986
[Tick 84]
Tick, E.; Warren, D.: “Towards a Pipelined Prolog Processor”, em Proc. Symp. on
Logic Programming, Atlantic City (USA), 1984
[Teitelman 81]
Teitelman, W; Masinter L.: “The Interlisp Programming Environment”, IEEE
Computer, 1981
[Teitelman 84]
Teitelman, W: “A Tour Through Cedar”, IEEE Software, 1984
[Turk 86]
Turk A.: “Compiler Optimizations for the WAM”, em Proc. 3º ICLP, London,
Springer-Verlag, 1986
Bibliografia
140
[van Emden 76]
van Emden, M; Kowalskli, R.: “The semantics of predicate logic as a programming
language”, Journal of the ACM 23(4), 1976
[Warren 74]
Warren, D.: “Warplan: A System for Generating Plans”, Memo 76, University of
Edinburgh, 1974
[Warren 77a]
Warren, D.: “Implementing Prolog: compiling predicate logic programs, DAI Report
39-40, University of Edinburgh,1977.
[Warren 77b]
Warren, D.; Pereira, L.M.; Pereira F.: “Prolog - The Language and its
Implementation Compared with Lisp”, em Proc. of the Symposium on Artificial
Intelligence and Programming Languages, SIGPLAN Notices, Vol 12, N. 8, e SIGART
Newsletters, Nº 64, Agosto 1977
[Warren 80]
Warren, D.: “Logic Programming and Compiler Writing”, Software - Practice and
Experience, Vol.10, 1980
[Warren 83]
Warren, D.: “An Abstract Prolog Instruction Set”, SRI Technical Note 309, SRI
International, 1983
[Warren 88]
Warren, D.: “Implementation of Prolog”, Lecture notes, Tutorial nº 3, Symp. on
Logic Programming, Seattle, USA, 1988