ctp.di.fct.unl.ptctp.di.fct.unl.pt/~amd/publications/1990-tese-mestrado.pdf · 2 Resumo Programação em lógica contextual, ou CxLP, é um novo esquema de programação que enriquece

IMPLEMENTAÇÃO DE UM SISTEMA DEPROGRAMAÇÃ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 Electrotécnica e de

Computadores.

Departamento de Informática

Universidade Nova de Lisboa

2825 Monte da Caparica

Portugal

IMPLEMENTAÇÃO DE UM SISTEMA DEPROGRAMAÇÃO EM LÓGICA

CONTEXTUAL

Artur Miguel de Andrade Vieira Diaslicenciado em Engenharia Informática

pela

FACULDADE DE CIÊNCIAS E TECNOLOGIA

UNIVERSIDADE NOVA DE LISBOA

Tese submetida para satisfação parcial dos requisitos doprograma 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

ResumoProgramaçã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.

AbstractContextual 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 ............................................................................................................ 71.1. Apresentação ............................................................................................. 71.2. Organização ............................................................................................... 81.3. Agradecimentos ......................................................................................... 91.4. Orientação.................................................................................................. 10

2. Programação em Lógica ....................................................................................... 112.1. Origens e características da programação em lógica ................................ 112.2. Um pouco da história das implementações de Prolog .............................. 132.3. A WAM ....................................................................................................... 15

2.3.1. Representação dos termos .............................................................. 162.3.2. Áreas de dados ................................................................................. 162.3.3. Estruturas de dados de controlo ..................................................... 172.3.4. Registos da WAM ............................................................................. 172.3.5. Classificação das variáveis ............................................................ 182.3.6. Optimização da última chamada (LCO) e trimming ....................... 182.3.7. Indexação ........................................................................................ 192.3.8. Instruções ........................................................................................ 19

3. Programação em Lógica Contextual .................................................................... 223.1. Introdução ................................................................................................. 223.2. Sintaxe ....................................................................................................... 233.3. Units .......................................................................................................... 233.4. Designador de Unit .................................................................................... 243.5. Contexto ..................................................................................................... 24

Índice 4

3.6. Nomes dependentes do contexto ................................................................ 253.7. Contexto histórico ..................................................................................... 253.8. Regras de inferência .................................................................................. 253.9. Exemplos ................................................................................................... 28

4. CxM - Máquina abstracta para CxLP .................................................................. 304.1. Introdução ................................................................................................. 304.2. Representação dos termos ......................................................................... 314.3. Organização da memória .......................................................................... 32

4.3.1. Área de código ................................................................................. 324.3.2. Stacks (heap + stack local) .............................................................. 324.3.3. Trail ................................................................................................ 33

4.4. Ligações em CxLP ....................................................................................... 334.4.1. Ligação dos nomes definidos localmente ....................................... 334.4.2. Ligação dos nomes dependentes do contexto .................................. 34

4.4.2.1. Cache ................................................................................. 344.4.2.2. Estrutura da cache ............................................................ 35

4.4.3. Ligação dos nomes em fórmulas de extensão ................................. 354.4.4. Ligação dos nomes importados ...................................................... 37

4.5. Parâmetros das units ................................................................................ 374.6. Implementação dos contextos ................................................................... 38

4.6.1. Representação dos contextos .......................................................... 384.6.2. Registos para suporte dos contextos ............................................... 394.6.3. Instruções para controlo dos contextos ......................................... 414.6.4. Fórmulas de libertação de contexto e a unit [] ................................ 42

4.7. Implementação do contexto histórico ...................................................... 434.7.1. Representação do contexto histórico e registos associados ........... 434.7.2. Instruções para controlo do contexto histórico ............................. 44

4.8. As outras estruturas de dados do stack local ............................................ 454.8.1. Registos de activação ...................................................................... 454.8.2. Pontos de escolha ............................................................................ 46

4.9. A C-WAM .................................................................................................... 46

5. Mecanismos de ligação incremental da CxM ...................................................... 475.1. Introdução ................................................................................................. 475.2. O sistema de suporte de CxLP ..................................................................... 485.3. Manutenção das ligações na CxM ............................................................. 50

5.3.1. Descritores de nome de predicado .................................................. 505.3.2. Estabelecimento das ligações ......................................................... 51

5.3.2.1. MakeIndex ........................................................................ 525.3.2.2. MakeImportBinding ........................................................ 525.3.2.3. MakeCtxExtBinding ......................................................... 525.3.2.4. MakeCtxDepBinding ........................................................ 52

5.3.3. Invalidação das ligações ................................................................. 535.3.3.1. Efeitos da alteração do conjunto de cláusulas de uma unit ...... 545.3.3.2. Efeitos da alteração de importação .................................. 555.3.3.3. Efeitos da mudança de visibilidade ................................. 555.3.3.4. Efeitos da eliminação de um nome de predicado ............. 56

5.3.4. As ligações dos nomes dependentes do contexto revisitadas ......... 565.3.4.1. Adição de cláusulas .......................................................... 56

Índice 5

5.3.4.2. Mudança do estado de visibilidade de um nome .............. 575.3.4.3. Eficiência .......................................................................... 58

6. Técnicas de implementação da CxM ................................................................... 596.1. Introdução ................................................................................................. 596.2. Lips! ............................................................................................................ 596.3. Técnica de interpretação ........................................................................... 60

6.3.1. Código threaded .............................................................................. 606.3.2. Método clássico ............................................................................... 616.3.3. Comparação .................................................................................... 616.3.4. Eliminação do ciclo de interpretação ............................................ 626.3.5. Código expandido ............................................................................ 62

6.4. Tags ............................................................................................................ 636.5. Rotina de unificação .................................................................................. 666.6. Especialização das instruções ................................................................... 676.7. Utilização de registos da máquina hospedeira ......................................... 686.8. Indexação ................................................................................................... 696.9. Penalizações provocadas pelos novos mecanismos ................................. 69

7. Compilação .......................................................................................................... 717.1. Introdução ................................................................................................. 717.2. Características gerais do compilador ....................................................... 727.3. Funcionamento geral e código gerado ....................................................... 727.4. A tabela de variáveis ................................................................................. 757.5. Algoritmo de atribuição de registos .......................................................... 767.6. Golos que mudam de contexto ................................................................... 79

7.6.1. Passagem de parâmetros para units ............................................... 797.6.2. Tratamento de referências a parâmetros de units ......................... 80

7.7. Indexação ................................................................................................... 817.7.1. Índice ............................................................................................... 817.7.2. Índice rápido ................................................................................... 827.7.3. Índice compacto .............................................................................. 837.7.4. Índice super-rápido ......................................................................... 847.7.5. Na WAM ........................................................................................... 85

7.8. Compilador optimizador .......................................................................... 857.9. Outras linguagens ...................................................................................... 86

8. Outras Componentes do Sistema ......................................................................... 878.1. Predicados de sistema ............................................................................... 87

8.1.1. Predicados deterministas escritos em C ........................................ 888.1.2. Predicados de sistema não deterministas escritos em C ............... 888.1.3. Predicados de sistema escritos em CxLP ........................................ 90

8.2. Analisador sintáctico ............................................................................... 908.3. Tratamento de erros .................................................................................. 918.4. Colector de lixo do heap ............................................................................. 918.5. Colector de lixo da área de código .............................................................. 938.6. Monitor de Comandos ............................................................................... 93

9. Conclusão ............................................................................................................. 94

Índice 6

Apêndices ................................................................................................................... 96

A. Predicados de sistema .......................................................................................... 97A.1. Introdução ................................................................................................. 97A.2. Sucesso e falhanço ..................................................................................... 97A.3. Controlo ..................................................................................................... 97A.4. Manipulação de golos ................................................................................ 98A.5. Gestão das units e do seu conteúdo ............................................................ 99A.6. Contextos ................................................................................................... 102A.7. Classificação de termos ............................................................................. 103A.8. Manipulação de estruturas ........................................................................ 103A.9. Igualdade .................................................................................................... 103A.10. Avaliação de expressões aritméticas e comparação de números ............. 104A.11. Gestão de ficheiros ..................................................................................... 104A.12. Entradas e Saídas ...................................................................................... 104A.13. Diversos ..................................................................................................... 106

B. Operações Básicas e Instruções da CxM ............................................................... 109B.1. Introdução ................................................................................................. 109B.2. Pseudo-código ............................................................................................ 109B.3. Operações básicas da CxM ......................................................................... 110B.4. Instruções procedimentais e de controlo .................................................. 114B.5. Instruções Put ............................................................................................ 117B.6. Instruções Get ............................................................................................ 118B.7. Instruções Unify ........................................................................................ 119B.8. Instruções Build ......................................................................................... 122B.9. Instruções de indexação ............................................................................ 123B.10. Instruções para fórmulas de extensão ...................................................... 125B.11. Instruções de importação .......................................................................... 127B.12. Instruções para nomes dependentes do contexto ...................................... 129B.13. Instruções de gestão do contexto histórico ............................................... 130

C. Exemplos de código gerado .................................................................................. 132

Bibliografia ............................................................................................................... 135

7

1Introduçã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

2Programaçã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.


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


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, nível de

optimização do código possível, facilidade de integração num ambiente de

programação, adequação à prototipagem e integração de novas ideias, custo


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


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.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.


• S 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 Yi, 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 Xi não é preservado nas invocações de predicados, razão que os impedede funcionar como variáveis permanentes.


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.


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.AllocateDeallocateProceedExecute PredCall Pred, N

Instruções Put - Carregam os argumentos actuais nos registos Xi, preparando a

invocação dos predicados.PutVariable Vn, XiPutValue Vn, XiPutUnsafeValue Yn, XiPutConstant C, XiPutStructure F, XiPutList Xi

Instruções Get - Fazem a unificação dos argumentos formais das cláusulas com os

argumentos actuais passados em registos Xi.

GetVariable Vn, XiGetValue Vn, XiGetConstant C, XiGetStructure F, XiGetList 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 VnUnifyVoid NUnifyValue VnUnifyConstant C, XiUnifyStructure F, XiUnifyList Xi


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,LsSwitchOnConstant N, HashTableSwitchOnStructure N, HashTableTryMeElse LRetryMeElse LTrustMeTry LRetry LTrust 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

3Programaçã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 UL,

definições UD, importações UI e visibilidade UV: Vejamos em que consiste cada um

deles:


• Etiqueta UL é um termo u(P1,...,Pn) (n≥0), onde u é o nome da unit e P1,...,Pn 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 UD é 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 UI é 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 UL. O

conjunto de todos os nomes de predicado importados por uma unit U

representa-se por Importados(U).

• Visibilidade UV é um conjunto de nomes de predicados que se dizem visíveis no

exterior de U.

Por definição, os conjuntos UD, UI e UV 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 UL 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


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 CondiçõesConsequente


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.

TrueC•Ψ |M true[ �ε]

O golo true é derivável em qualquer contexto e modo, usando a substituição vazia.

ConjunçãoC•Ψ |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θ [σ]

{ h :- b ∈ |u|D, θ = mgu(g,h) }uC•Ψ |i g [θσ]

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çãovC•Ψ|e g [θ]

{ <nome(g),v> ∈ |u|I, designador_de_unit(v) }uC•Ψ |i g [θ]

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.


SaídaC•Ψ |e g [θ]

{ nome(g) ∉ Definidos(|u|) ∪Importados(|u|) }uC•Ψ |i g [θ]

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.

DescidaC•Ψ |e g [θ]

{ nome(g) ∉ |u|V }uC•Ψ |e g [θ]

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.

EntradauC•Ψ |i g [θ]

{ nome(g) ∈ |u|V }uC•Ψ |e g [θ]

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ãouC•Ψ |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.

SalvaguardaC•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.


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)


authors |i wrote(Who,_) (Redução)

λ |i wrote(Who,_) (Descida)falhanço

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}]

30

4CxM - 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.

2Atendendo a que a publicação [Warren 83] é a referência principal, mesmo obrigatória, para aWAM, a nomenclatura aí introduzida é seguida de perto, por forma a facilitar a tarefa do leitorfamiliarizado com aquele trabalho. O único ponto em que divergimos um pouco, foi na nãoconsideração dos registos Ai por eles se identificarem com os registos Xi. Esta é uma questãode 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: 0000............................Lista: 1001............................Estrutura: 1010............................Átomo: 1011............................Inteiro: 110.............................Real: 111.............................


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


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


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 acerca da

possibilidade da memorização das caches mais frequentemente usadas para

reutilização. Para isto ser feito, seria necessário resolver o problema fundamental de


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


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, enormalmente a chamada u>>g é feita do exterior de u.


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


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.


• N 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 indica ligação não

estabelecida. Posteriormente, sempre que a ligação de um 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.


• 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.


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 0Call g/2<u>PopContextProceed

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 aapontar para ele.


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


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


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 0Call g/0PopHistoricalContextProceed

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,


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 0Call g/0ExitHistoricalContextProceed

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:


• E, CP, B, TR, H, C, CC, C2Servem 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

5Mecanismos 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.


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.

5Em geral estes predicados não são chamados directamente pelo utilizador, mas sim peloambiente de programação em resposta a alguma solicitação de alto nível por parte doutilizador, ou ainda de forma automática durante a edição do programa por exemplo.


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 Usados para guardar apontadores para as tabelas de hash que

podem ser geradas durante a criação do índice de um predicadoassociado a um nome definido localmente.

• BindType 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.


• 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.


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ção6. 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

6A sintaxe das fórmulas de extensão permite que isto seja feito.


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


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.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 quando

concretizada, terá características completamente diferentes das que 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


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


óptimo que as caches de todas as instâncias dessa unit pudessem 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.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

6Té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:

7Por exemplo se uma determinada optimização permite ganhar 1 segundo num programa quedemora 10 segundos a correr parece correcto dizer que o ganho foi de 10%. Mas suponhamosque suspendemos essa optimização e que nos dedicamos a melhorar outros aspectos damáquina. Mais tarde quabndo o mesmo programa correr em 5 segundos, a reintrodução daoptimização anterior permite agora uma ganho de 20%.


• 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


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


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 ausentes; eles são usados quase

exclusivamente na programação de certos predicados de sistema, os quais,

comparativamente com as instruções da máquina, não são factor muito relevante


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 ( t > 0 )• Teste de bit ( t & 0x2 == 0 )• Comparação com constante ( t > 0x276896 )• And com constante ( t & testList == 0 )• Teste directo da tag ( 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: 0000............................Lista: 1001............................Estrutura: 1010............................Átomo: 1011............................Inteiro: 110.............................Real: 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


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 ≡ 0x60000000

testNoVarStruct ≡ 0x50000000

IsList(t) ≡ t & tagMask4 = tagList

IsStruct(t) ≡ t & tagMask4 = tagStruct

IsListNoVar(t) ≡ t & testNoVarList == 0

IsStructNoVar(t) ≡ t & 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) ≡ t & tagMask4 = tagAtom

IsInt(t) ≡ t & tagMask3 = tagInt

IsReal(t) ≡ 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%


(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: 000............................0Lista: 001............................1Estrutura: 010............................1Átomo: 011............................1Inteiro: 10.............................1Real: 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


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, ….


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


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 paranão ser prejudicada a técnica de interpretação usada.


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:Mac Vax

• Predicado importado de designador de unit atómico 7% 15%• Predicado importado de parâmetro de unit 16% 33%• Extensão de contexto usando designador de unit atómico 5% 11%• Extensão de contexto usando parâmetro de unit 13% 28%• Predicado dependente do contexto 3% 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

7Compilaçã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 registo-

má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 Yn 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 Yn é 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 76

• ParamIndex 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 X0GetVariable X3,X1GetValue X3,X2Proceed

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 X0GetValue X1,X2Proceed

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 X0UnifyVariable X3UnifyVariable X0GetList X2UnifyVariable X3UnifyVariable X2Execute 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,X2PutValue X1,X0PutValue X2,X1Execute 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 0Call b/1PopContextProceed

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 0PutValue Z0 X1Call b/1PopContextProceed

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 X2PushContext u 1 0PutValue X2 X1Call b/1PopContextProceed

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: TryMeElse C2aC1: GetConstant 1 X0

ProceedC2a: RetryMeElse C3aC2: GetConstant 2 X0




ProceedC6a: RetryMeElse C7aC6: PutConstant “var” X0

write/1 ; predicado de sistemaProceed

7. Compilação 82

C7a: RetryMeElse C8aC7: GetStruct +/2 X0

UnifyConstant 2UnifyConstant 3Proceed

C8a: TrustMeC8: 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: SwitchOnTerm C0, L1, C6, L2L1: SwitchOnConstant 4, T1, C6T1: 1: V1,

2: V2,3: V3

V1: Try C1Retry C3Retry C5Trust C6

V2: Try C2Retry C6Trust C8

V3: Try C4Trust C6

7. Compilação 83

L2: Try C6Trust 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

TryMeElse L1SwitchOnConstant 4, T1, fail

T1: 1: V1,2: C2,3: C4

V1: Try C1Retry C3Trust C5

L1: Retry C6

L2: TrustMeSwitchOnTerm 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 listas têm

frequentemente esta forma.

10Uma zona crítica, é um segmento de código de execução muito frequente.

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

8Outras 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. Quandose transporta um programa Prolog de uma implementação para outra é muitas vezesnecessário fazer algumas alterações.


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: TryMeElse L 0Proceed

L: TrustMe 0Proceed

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:


L: RetryMeElse L 0Proceed

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:


L: TrustMe 0Execute 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.


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


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:


• 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


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

9Conclusã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

APredicados 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.

unsafe_call(X) Semelhante ao anterior mas ignora as restrições de visibilidade

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.


>X Deriva X guardando previamente o contexto corrente no contexto

histórico.

<X Deriva X desempilhando previamente 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,


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 corrente, chamados A ,

independentemente da sua aridade.


listing 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.

reconsult(File) Semelhante ao predicado anterior com a diferença que

todos os predicados a que corresponda uma cláusula em File são

completamente redefinidos.

visible A/N O nome de predicado A/N fica visível na unit corrente.

novisible(A,N) 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.


invisible_predicate(P) 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.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.10. Avaliação de expressões aritméticas e comparação denú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 =:= YX =\= YX < YX > YX >= YX =< 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.


readp(X) 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, ('->')).


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


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,


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

BOperaçõ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çõesde memorização são as seguintes: ou a variável é global e definida antes da posição do topo doheap no momento da criação do último ponto de escolha (valor indicado pelo registo HB), ou avariável é local e definida antes do último ponto de escolha.


ResetVar(v)

*v ← v

Torna a variável v livre.

PushVar(sp)

ResetVar(sp)sp ← sp + 1return sp - 1

Empilha uma variável livre na pilha cujo topo é referido por sp.

Drf(v)

doIsVar(v) and v <> *v → v ← *v

odreturn v

Determina o valor da variável v através do percurso completo da sua cadeia de referências.

Trail(v)

ifIsToTrailVar(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)

ifv1 < v2 → if

IsGlobalVar(v1) → Assign(v2, v1)

not IsGlobalVar(v1) → Assign(v1, v2)

fiv1 > v2 → if

IsGlobalVar(v2) → Assign(v1, v2)

not IsGlobalVar(v2) → Assign(v2, v1)

fiv1 = v2 → skip

fi

Unifica duas variáveis livres. Esta operação, relativamente à WAM, exige o teste suplementarIsGlobalVar(.), devido à nova disposição dos stacks.


Unify(t1, t2)

saveH ← HPush(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)

finot IsVar(t1) →

ifIsVar(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)) )

fifi

fiod

Unifica dois termos quaisquer. O stack global é usado como pilha auxiliar. A CxM nãosuporta occurs check por razões de eficiência. No entanto, caso a sua adição venha a serdesejada, 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 →

ifIsToTrailVar(*v) → v ← v + 1

not IsToTrailVar(*v) → *v ← Pop(TR)

fido

Recupera no trail o espaço correspondente a todas as variáveis que nele se encontramdesnecessariamente. Esta operação é usada apenas pelas instruções de cut.

GTopOfLocalStack(EnvSize)

ifL < E → return L

L >= E → return E - EnvSize

fi

Determina o topo do stack local com base no argumento EnvSize, o qual é suposto indicar otamanho corrente do registo de activação que se encontra activo. Como se sabe, o tamanho dosregistos de activação varia dinamicamente devido ao seu trimming.


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 dopredicado correntemente activo (indicado pelo registo CP) e indica o tamanho do registo deactivaçã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

fipred ← 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 quecontêm os predicados de sistema é considerada em primeiro lugar pois todos os predicadosque 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)

fipred ← FindVisiblePredicate(Functor, C(U))if


pred = nil → skip

fiod

Procura uma definição de predicado visível para um dado functor no contexto corrente, massem considerar o seu topo. Como se pode observar, a base do contexto corrente é determinadapela unit [].

SearchContext(Functor)

pred ← FindVisiblePredicate(Functor, C(U))if

pred = nil → return SearchContextBelow(Functor)


fi

Procura uma definição de predicado visível, com base no seu functor, no contexto corrente.

SaveState(arity, previousB)

B(C) ← CB(CC) ← CCB(C2) ← C2B(E) ← EB(CP) ← CPB(B) ← previousBB(B0) ← B0B(TR) ← TRB(H) ← HHB ← B(H)dotimes(n, arity) B(A)n ← Xn

Guarda todos os registos da CxM que são necessários para repor posteriormente o estadoda máquina. O argumento arity indica o número de registos X a salvaguardar e o argumentopreviousB o ponto de escolha anterior àquele que está a ser preenchido.


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 arepor.

DiscardLastChoice()

B ← B(B)HB ← B(H)

Repõe o último ponto de escolha anterior.

InitCxM()

H ← stacksBeginTR ← trailBeginE ← B ← B0 ← stacksEndC ← stacksEnd - SizeOf(UnitInstance)C(S) ← C(C) ← CC ← CC(U) ← topUnitC(N) ← 0C2 ← C - SizeOf(HistoricalRegister)C2(R2) ← C2(C2) ← C2C2(C) ← CL ← C2Base ← C2

Inicia a máquina abstracta. É empilhada uma instância da unit [], que define o contexto vazioinicial e ainda um registo histórico. Este é permanentemente apontado pelo registo da máquinaC2Base, o qual é utilizado na detecção de tentativas de reposição contextos que não tenhamsido 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 ← EE ← TopOfLocalStack()E(E) ← saveE(CP) ← CPE(CC) ← CC

Esta instrução aparece na zona inicial do código de todas as cláusulas que tenham pelomenos dois golos no corpo, e ainda nas cláusulas em que o seu único golo é uma das fórmulasespeciais da linguagem CxLP: extensão, salvaguarda, reposição e libertação de contexto. Criaum novo registo de activação no topo do stack local, memorizando nele os registos E, CP e CC.

Call Pred N

B0 ← BCP ← P + 2P ← PredCode(Pred)

A instrução Call termina geralmente o código associado à chamada de um golo. Pred é areferência do predicado chamado, e N é o número de variáveis no registo de activação nesteponto da cláusula. O valor guardado no registo B0 é utilizado mais tarde se alguma dasclá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.


CallVar

functor ← PrepareCall(X0)

pred ← SearchContext(functor)if

IsCPred(pred) → P++

Jump(PredCode(pred))IsPrologPred(pred) → B0 ← B

CP ← P + 1P ← PredCode(pred)

fi

Esta instrução implementa o meta-call da linguagem CxLP. O termo que representa o golo aser derivado encontra-se no registo X0. A rotina PrepareCall copia os argumentos desse termopara os registos X0, X1, …, produzindo como valor o seu functor principal. A determinação dopredicado a ser chamado exige uma pesquisa no contexto corrente.

Execute Pred

B0 ← BP ← PredCode(Pred)

A instrução Execute termina, em geral, o código das cláusulas que têm exactamente um golono 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 ← BP ← PredCode(Pred)

Esta instrução termina, em geral, o código das cláusulas que têm mais dos que um golo noseu corpo. Começa por repor o valor dos registos E, CP, e CC, e passa depois o controlo para opredicado Pred.

ExecuteVar

functor ← PrepareCall(X0)


IsCPred(pred) → P ← Address(Proceed)


P ← PredCode(pred)fi

A instrução ExecuteVar termina o código das cláusula cujo corpo é constituído por apenasum meta-call. É semelhante à instrução CallVar com a diferença que não posiciona o registoCP.

DeallocateAndExecuteVar

CP ← E(CP)CC ← E(CC)E ← E(E)functor ← PrepareCall(X0)


IsCPred(pred) → P ← Address(Proceed)


P ← PredCode(pred)fi

A instrução DeallocateAndExecuteVar termina o código das cláusulas com mais do que umgolo, 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.


Proceed

P ← CPC ← CC

Esta instrução termina o código de todas as cláusulas unitárias. Posiciona os registos P e Ccom 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 dasfórmulas especiais da linguagem CxLP: extensão, salvaguarda, reposição e libertação decontexto.

NeckCut

ifB < 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 sejaum cut. Os pontos de escolha situados acima daquele que é indicado indicado por B0 sãoeliminados, 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 cutinternamente. O valor de B0 é copiado para a variável permanente Yn.

Cut Yn

ifB < 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 primeirogolo da cláusula. Os pontos de escolha situados acima daquele que é indicado indicado por Ynsã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 é postoa apontar para a próxima cláusula alternativa, que se encontra registada no último ponto deescolha. A instrução apontada por P, e que é executada logo a seguir é uma das quatro querepõ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.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 permanentelivre. 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)

ifIsCurrEnvVar(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ávelsituada 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 ϑ, XiXi ← ϑ

Gerada para os argumentos constantes de um golo. A constante é simplesmente copiadapara Xi.

PutNil Xi

Xi ← []

Gerada quando um argumento de um golo é o átomo []. Este átomo é simplesmente copiadopara Xi.


PutStructure Φ, XiXi ← 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 aseguir 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 Zn, Xi

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ícieda cabeça da cláusula. Ela copia simplesmente o valor do registo Xi para a variável Yn.

GetValue Xn, Xi

ifUnify(Xn, Xi) → Xn ← Drf(Xn)

fi

Esta instrução é gerada para todas as ocorrências de variáveis temporárias instanciadas aonível da superfície da cabeça da cláusula. Os dois registos são unificados. O resultadodesreferenciado fica em Xn.

GetValue ψn, Xi ; ψ ∈ { Y, Z }

ifUnify(ψn, Xi) → skip

fi

Esta instrução é gerada para todas as ocorrências de variáveis permanentes instanciadasou parâmetros de unit na cabeça da cláusula ao nível da superfície. ψn e Xi são simplesmente

unificados.

GetConstant ϑ, Xit ← Drf(Xi)

ifIsVar(t) → Assign(t, ϑ)t = ϑ → skip

fi

Esta instrução representa a constante ϑ ocorrendo como argumentos da cláusula. Se oresultado for uma variável então esta é instanciada com ϑ. Caso contrário se o resultado fordiferente de ϑ ocorre retrocesso.


GetNil Xi

t ← Drf(Xi)

ifIsVar(t) → Assign(t, [])

t = [] → skip

fi

Esta instrução representa o átomo [] ocorrendo como argumento da cláusula. Se o resultadofor uma variável então esta é instanciada com []. Caso contrário se o resultado for diferente de []ocorre retrocesso.

GetStructure Φ, Xit ← Drf(Xi)

ifIsVar(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 topodo heap, marcado com a tag estrutura. Além disso é ainda empilhado o functor Φ e posta amá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. Noscasos restante ocorre retrocesso.

GetList Xi

t ← Drf(Xi)

ifIsVar(t) → Assign(t, TagList(H))

SetWriteMode()IsList(t) → 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 doheap, marcado com a tag lista e a máquina é posta em modo de escrita. Caso o resultado sejauma 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.


UnifyVoid N

ifWriteMode() → dotimes(i,N) PushVar(H)

ReadMode() → S ← S + N

fi

Representa N variáveis consecutivas de ocorrência única, nos argumentos duma estruturada cabeça da cláusula. Consoante o modo corrente seja de escrita ou de leitura, assim sãoempilhadas N variáveis livres no topo do heap, ou são saltados os próximos N argumentosapontados por S.

UnifyVoidOne

ifWriteMode() → PushVar(H)

ReadMode() → S ← S + 1

fi

Especialização da instrução anterior para N = 1.

UnifyVariable ψn ; ψ ∈ { X, Y }

ifWriteMode() → ψn ← PushVar(H)

ReadMode() → ψn ← *S

S ← S + 1fi

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

ifWriteMode() → Push(H, Xn)

ReadMode() → if

Unify(Xn, *S) → Xn ← Drf(Xn)

S ← S + 1fi

fi

Esta instrução é gerada para argumentos de estruturas da cabeça que sejam variáveistemporá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 é unificadocom a variável, sendo o resultado desreferenciado deixado na variável.

UnifyValue ψn ; ψ ∈ { Y, Z }

ifWriteMode() → Push(H, ψn)ReadMode() → if

Unify(ψn, *S) → S ← S + 1

fifi

Esta instrução é gerada para argumentos de estruturas da cabeça que sejam variáveispermanentes ou parâmetros de unit instanciados com um valor global. Em modo de escrita ovalor da variável é simplesmente empilhado no heap. Em modo de leitura o argumentoapontado por S é unificado com a variável.


UnifyLocalValue Xn

ifWriteMode() → t ← Drf(Xn)

ifIsLocalVar(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 + 1fi

fi

Esta instrução é gerada para argumentos de estruturas da cabeça que sejam variáveistemporárias instanciadas com um valor não necessariamente global. Em modo de escrita ovalor da variável é empilhado no heap se não for uma referência para uma variável local. Casocontrário ela é transferida para o topo do heap ficando Xn a apontar para ela. Em modo deleitura a instrução funciona como UnifyValue Xn.

UnifyLocalValue ψn ; ψ ∈ { Y, Z }

ifWriteMode() → t ← Drf(ψn)

ifIsLocalVar(t) → Assign(t, PushVar(H))

not IsLocalVar(t) → Push(H, t)

fiReadMode() → if

Unify(ψn, *S) → S ← S + 1

fifi

Esta instrução é gerada para argumentos de estruturas da cabeça que sejam variáveispermanentes 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 umavariável local. Caso contrário ela é transferida para o topo heap. Em modo de leitura a instruçãofunciona como UnifyValue ψn.

UnifyConstant ϑ

ifWriteMode() → Push(H, ϑ)ReadMode() → t ← Drf(*S)

S ← S + 1if

IsVar(t) → Assign(t, ϑ)t = ϑ → skip

fifi

Representa um argumento de uma estrutura da cabeça que é uma constante. Em modo deescrita a constante é empilhada no heap. Em modo de leitura a constante é unificada com oargumento apontado por S.

UnifyNil

ifWriteMode() → Push(H, [])

ReadMode() → t ← Drf(*S)

S ← S + 1if

IsVar(t) → Assign(t, [])

t = [] → skip

fifi

Especialização da instrução anterior para ϑ = [].


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 estruturaocorrendo 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 quesejam 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 quesejam variáveis instanciadas com um valor global. O valor da variável é simplesmenteempilhado no heap.

BuildLocalValue Xn

t ← Drf(Xn)

ifIsLocalVar(t) → Xn ← PushVar(H)

Assign(t, Xn)


fi

Esta instrução é gerada para argumentos de estruturas de golos do corpo da cláusula quesejam variáveis temporárias instanciadas com um valor não necessariamente global. O valor davariável é empilhado no heap se não for uma referência para uma variável local. Caso contrárioela é 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))


fi

Esta instrução é gerada para argumentos de estruturas de golos do corpo da cláusula, quesejam variáveis permanentes ou parâmetros de unit instanciadas com um valor nãonecessariamente global. O valor da variável é empilhado no heap se não for uma referênciapara 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.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 definidoslocalmente. Tal como as outras instruções de ligação, ela nunca é gerada pelo compilador massim pelo módulo gestor da base de dados do sistema, que a coloca no campo Inst do descritordo predicado nas circunstâncias descritas em 5.3. A instrução começa por chamar um módulodo compilador que trata da construir o índice se valer a pena, e estabelece a ligação para opredicado mediante a alteração do valor de PredCode(Pred). O controlo é então passado para ocódigo do predicado.

TryMeElse Next Arity

save ← BL ← B ← TopOfLocalStack() - Arity - SizeOf(ChoicePoint)B(P) ← NextSaveState(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 aaridade 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) ← NextRestoreState(Arity)L ← B

Esta instrução precede o código de uma cláusula intermédia de um predicado composto porvárias. Ela repõe o estado guardado no último ponto de escolha e guarda nele o endereço dapró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 ← BL ← B ← TopOfLocalStack() - arity - SizeOf(ChoicePoint)B(P) ← P + 1SaveState(arity, save)P ← Label

A instrução Try indica a primeira cláusula de uma sequência de cláusulas com a mesmachave. Ela cria um ponto de escolha e guarda nele o estado corrente da máquina. Label é o


endereço do início do código da cláusula a executar. Em caso de retrocesso será executada ainstrução Retry ou Trust que se encontra a seguir. A aridade do predicado é obtida acedendo aosegundo argumento da instrução de indexação que se encontra no início da cláusula referidapor Label.

Retry Label

arity ← *(Label - 1)B(P) ← P + 1RestoreState(arity)L ← BP ← Label

A instrução Retry indica uma cláusula intermédia de uma sequência de cláusulas com amesma chave. Ela repõe o estado salvaguardado no último ponto de escolha e posiciona nele oendereç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 mesmachave. Ela repõe o estado guardado no último ponto de escolha eliminando-o seguidamente. Ocontrolo é então passado para o código da última cláusula do predicado.

SwitchOnTerm V C L S

t ← Drf(X0)

ifIsVar(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ênciasconstituintes do índice compacto (cf. 7.7). Ela passa o controlo para um de quatro diferentesendereços, consoante o tipo do valor de X0 depois de desreferenciado. V , C, L, e S são osendereços associados respectivamente a variável, constante, lista e estrutura.

SwitchOnList V C L S

t ← Drf(X0)


IsAtomic(t) → if t = [] → P ← C fi


S ← ListArgs(t)SetReadMode()

IsStruct(t) → P ← S

fi

Esta é uma especialização da instrução SwitchOnTerm. Aplica-se a um predicado que entreas suas diversas cláusulas tenha apenas uma cujo primeiro argumento seja o átomo [], e outracujo primeiro argumento seja uma lista. A instrução executa logo no seu corpo as instruçõesGetList X0 e GetNil X0, e salta por cima dessas instruções no código das cláusulas.


SwitchOnFunctor V C L S

t ← Drf(X0)if

IsVar(t) → P ← V

IsAtomic(t) → P ← C


IsStruct(t) → if StructFunctor(t) = *(S-1) → P ← S

S ← StructArgs(t)SetReadMode()

fifi

Esta é uma especialização da instrução SwitchOnTerm. Aplica-se a um predicado que entreas suas diversas cláusulas tenha apenas uma cujo primeiro argumento seja uma estrutura. Ainstrução executa logo no seu corpo a instrução GetStruct Φ, X0, e saltando por cima dela nocódigo da cláusula.

JumpOnVar Label

t ← Drf(X0)


not IsVar(t) → skip

fi

Esta instrução surge sempre, e apenas, no início do índice compacto (cf. 7.7.3). Ela passa ocontrolo 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 primeirosargumentos sejam constantes. Table é o endereço de uma tabela de dispersão na qual, paracada uma dessas constantes, está registado o endereço do código a executar. Se o valor de X0não estiver previsto na tabela, o controlo passa para o endereço Else . N é uma potência de 2 queindica 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 primeirosargumentos sejam estruturas. A selecção é efectuada na tabela de dispersão Table com base nofunctor 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.


PushContext Unit FirstReg EnvSize

n ← UnitNEnvCells(Unit)L ← C ← GTopOfLocalStack(EnvSize) - n - SizeOf(UnitInstance)C(U) ← UnitC(C) ← CCC(N) ← ndotimes(i, n) C(Cache)3*i ← 0

dotimes(i, UnitArity(Unit)) Zi ← Xi+FirstRegCC ← C

Esta instrução é gerada para as fórmulas de extensão U>>G nos casos em que U é umdesignador de unit. A instrução precede o código do golo G. Ela empilha no stack local uma novainstância de unit e preenche os seus diversos campos. Unit é uma referência para a unit queestende o contexto, FirstReg o índice do registo X a partir do qual vêm os argumentos dodesignador de unit e EnvSize é o tamanho do registo de activação corrente no ponto em quesurge a fórmula. Os parâmetros da unit (variáveis Z) são inicializados a partir dos registos X, eas posições da cache das chamadas dependentes do contexto correspondentes ao número deversão são inicializadas com um valor impossível, neste caso zero, para forçar oestabelecimento de ligações na fase inicial de utilização da cache. No final CC recebe C: sendoa lógica da utilização do registo CC semelhante à da utilização de CP aquela atribuição poderiaser feita em todas as chamadas de predicado; no entanto para não prejudicar os programas quenão usem contextos, a atribuição é feita nas instruções de expansão e contracção do contextosempre na espectativa que uma dessas chamadas seja feita.

PushVarContext UseReg EnvSize

t ← Drf(XUseReg)

Unit ← TermToUnit(t)if

Unit <> nil → skip

fin ← UnitNEnvCells(Unit)L ← C ← GTopOfLocalStack(EnvSize) - n - SizeOf(UnitInstance)C(U) ← UnitC(C) ← CCC(N) ← ndotimes(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 é umavariável. Ela precede o código do golo G. Empilha no stack local uma nova instância de unit epreenche os seus campos. O argumento UseReg é o índice do registo X onde se encontra odesignador da unit que estende o contexto e EnvSize e o tamanho do registo de activaçãocorrente no ponto em que surge a fórmula. Os parâmetros da unit (variáveis Z) são inicializadosa partir dos argumentos do designador de unit que se encontra no registo XUseReg. A forma dainicialização da cache e a razão da transferência de C para CC são explicados na instruçãoanterior.

PopContext

ifL = C → L ← C + C(N) + SizeOf(UnitInstance)

L <> C → skip

fiC ← CC ← C(C)

Esta instrução é gerada em todas as fórmulas de extensão U>>G aparecendo imediatamentea seguir ao código do golo G. Em primeiro lugar ela remove a instância de unit que se encontrano topo do contexto corrente, caso o golo G tenha sido resolvido deterministicamente. Isto podeser 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ãorepostos.


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 nointerior 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 dodescritor do predicado nas circunstâncias descritas em 5.3. A instrução começa por chamar ummódulo do compilador que estabelece a ligação para o predicado mediante a alteração do valorde 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 emfórmulas de extensão, nos casos em que foi possível estabelecer uma ligação estática emvirtude do facto desse nome ser visível na unit que estendeu o contexto. Ela tem comoargumento o descritor de nome de predicado externo chamado, e executa um simples saltointer-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 emfórmulas de extensão, nos casos em que esse nome não é visível na unit que estendeu ocontexto. 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çãoMakeCtxExtBinding) ter sido determinada a inexistência de definição adequada nele.

VarCtxExtCall Functor UCache

ifC(U) = UCache(Unit) → pred ← UCache(Pred)

C(U) <> UCache(Unit) → pred ← FindVisiblePred(C(U), Functor)

UCache(Unit) ← C(U)UCache(Pred) ← pred

fiB0 ← BCP ← P + 1if

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 nomeassociado ao golo g. Esta instrução usa uma pequena cache de duas palavras que permitedetectar se o valor de U se mantém desde a última chamada. Se assim for usa-se a definição depredicado que se encontra nessa cache, caso contrário procura-se na unit corrente a definiçãode predicado, que é de imediato memorizada na cache. Finalmente efectua-se a chamada dopredicado assim obtido. Note-se que, apesar de ser improvável, pode acontecer que o nome dogolo g não esteja visível em U: nesse caso é sempre necessário efectuar uma busca no contextocorrente, não podendo neste caso a definição de predicado obtida ficar memorizada na cachepor 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.


SwitchContextOn Unit FirstReg

n ← UnitNEnvCells(Unit)L ← C ← TopOfLocalStack() - n - SizeOf(UnitInstance)C(U) ← UnitC(S) ← CCC(C) ← CC(C)C(N) ← ndotimes(i, n) C(Cache)3*i ← 0

dotimes(i, UnitArity(Unit)) Zi ← Xi+FirstRegCC ← C

Esta instrução é gerada pelo compilador, quando produz o segmento de código de ligaçãoque 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 decontexto, mas sim uma substituição da instância de unit do topo do contexto. Por isso o campoC da nova instância de unit toma o mesmo valor que o campo C do anterior topo do contexto. Otopo 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

fin ← UnitNEnvCells(Unit)L ← C ← TopOfLocalStack() - n - SizeOf(UnitInstance)C(U) ← UnitC(S) ← CCC(C) ← CC(C)C(N) ← ndotimes(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 quefaz a chamada do nome de predicado de um golo g importado de um parâmetro de unit U. Ainstrução aparece sempre antes da instrução de chamada de g. É muito semelhante à instruçãoPushVarContext com apenas a diferença de não fazer uma extensão de contexto, mas sim umasubstituição lógica da instância de unit que se encontra topo do contexto.

SwitchContextOff

ifL = C → L ← C + C(N) + SizeOf(UnitInstance)

L <> C → skip

fiC ← CC ← C(S)

Esta instrução aparece no segmento de código de ligação que faz a chamada do nome depredicado de um golo g, importado de um parâmetro de unit U. A instrução aparece depois dainstrução de chamada de g. Em primeiro lugar ela remove a instância de unit que se encontra notopo 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 predicadocomo é explicado em 5.3. A instrução começa por chamar um módulo do compilador que geraum segmento de código onde o predicado importado é chamado no contexto modificado. Ocontrolo passa seguidamente para esse código. Existe mais informação sobre esta instrução noponto 5.3.2.2.


ImportJumpBelow Functor

P ← PredCode(SearchContextBelow(Functor))

Esta instrução encontra-se nos descritores de nomes de predicados importados, nos casosem que esse nome não é visível no designador de unit de onde a importação é feita. Ela temcomo argumento o functor indicador do nome de predicado chamado, e efectua uma busca nocontexto corrente de uma definição visível aplicável. O topo do contexto é ignorado na buscavisto que na altura do estabelecimento da ligação (feita pela instrução MakeImportBinding), tersido determinada a inexistência de definição adequada nele (de facto o topo do contexto nemchega a ser mudado antes da execução desta instrução, por tal se revelar desnecessário).

VarImportCall Functor UCache

ifC(U) = UCache(Unit) → pred ← UCache(Pred)

C(U) <> UCache(Unit) → pred ← FindVisiblePred(C(U), Functor)

UCache(Unit) ← C(U)UCache(Pred) ← pred

fiB0 ← BCP ← P + 1if

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. Elausa uma pequena cache de duas palavras que permite detectar se o valor de U se mantém desdea última chamada. A descrição que aqui se apresenta é rigorosamente igual à da instruçãoVarCtxExtCall. As diferenças entre as duas situam-se a um nível de que aqui não está a serconsiderado, que é o da sua relação com o ambiente de programação, neste caso as facilidadesde 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 docontexto. É gerada pelo módulo gestor da base de dados do sistema, que a instala no descritordo nome de predicado. De acordo com o que foi dito no ponto 5.3.2.4 esta instrução associa umdeslocamento 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ãopara essa instrução.


CtxDepJump Functor CacheOffset

ifCacheOffset < C(N) →

ifC(Cache)CacheOffset = Version(Functor) →

P ← PredCode(C(Cache)CacheOffset+1)

C ← C(Cache)CacheOffset+2C(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)

fiCacheOffset >= C(N) → P ← PredCode(SearchContextBelow(Functor))

fi

Esta instrução aplica-se à chamada de nomes dependentes do contexto. Não é gerada pelocompilador mas sim pela instrução MakeCtxDepBinding. Ela testa primeiro o argumentoCacheOffset verificando se ele é abrangido pela cache da instância da unit corrente. Em casonegativo tem de ser feita dinamicamente uma procura no contexto corrente de uma definição depredicado visível compatível com o argumento Functor. Em caso afirmativo compara-se aversão corrente do functor com aquela que se encontra memorizada na cache. Se os valoresforem iguais isto significa que a informação da cache para aquele nome está actualizadapodendo ser usada imediatamente. Se os valores forem diferentes a informação da cache paraesse 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 ← C2L ← C2 ← GTopOfLocalStack(EnvSize)) - SizeOf(HistoricalRegister)C2(C) ← CC2(C2) ← saveC2(R2) ← C2

Esta instrução é gerada para as fórmulas de salvaguarda de contexto >G, aparecendosempre antes do código do golo G. Ela empilha no stack local um novo registo histórico epreenche os seus campos. Guarda em particular o contexto corrente no campo C e umaauto-referência no campo R2. Recordemos que no esquema de representação dos contextoshistóricos (ver 4.4.7.1) o campo R2 do registo histórico que se encontra no topo, indica o topo doregisto histórico conceptual. Assim fica justificado o uso da auto-referência pois neste caso ostopos dos contextos históricos, implementacional e lógico, coincidem. O argumento EnvSize é otamanho do registo de activação corrente, no ponto em que surge a fórmula.

PopHistoricalContext

ifL = C2 → L ← C2 + SizeOf(HistoricalRegister)

L <> C2 → skip

fiC2 ← C2(C2)

Esta instrução é gerada para as fórmulas de salvaguarda de contexto >G, aparecendosempre logo depois do código do golo G. O registo histórico do topo é desempilhado, sendorecuperado o seu espaço, caso o golo G tenha sido resolvido deterministicamente. Estacondição pode ser detectado através de uma simples comparação de L com C2.


EnterHistoricalContext EnvSize

conceptualTop ← C2(R2)if

conceptualTop = C2Base → Error("No saved context")

conceptualTop <> C2Base → skip

fisave ← C2L ← C2 ← GTopOfLocalStack(EnvSize)) - SizeOf(HistoricalRegister)C2(C) ← CC2(C2) ← saveC2(R2) ← conceptualTop(C2)(R2)C ← CC ← conceptualTop(C)

Esta instrução é gerada para as fórmulas de reposição de contexto <G, aparecendo sempreantes do código do golo G. Ela repõe o contexto situado no topo do contexto históricoconceptual e, além disso, empilha no stack local um novo registo histórico onde memoriza ocontexto corrente (pois a reposição de contexto é temporária) e o novo topo do contextohistórico conceptual, que se reduz (apesar do implementacional aumentar).

ExitHistoricalContext

ifL = C2 → L ← C2 + SizeOf(HistoricalRegister)

L <> C2 → skip

fiC ← CC ← C2(C)C2 ← C2(C2)

Esta instrução é gerada para as fórmulas de reposição de contexto <G, aparecendo sempredepois do código do golo G. O registo histórico do topo é desempilhado, sendo recuperado oespaço ocupado por ele, caso o golo G tenha sido resolvido deterministicamente. Além disso oestado dos registos C e CC anterior à reposição do contexto é restaurado.

132

CExemplos 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 PutYVariable Y3 X2f5c58 Proceed f4ccc PutYVariable Y0 X3

f4cd8 Call split/4 6f4bf0 TryMeElse f4c74 3 f4ce4 PutYValue Y3 X0f4bfc GetNil X0 f4cf0 PutYValue Y4 X1f4c04 GetXValue X1 X2 f4cfc PutList X2f4c10 Proceed f4d04 BuildYValue Y5

f4d0c BuildYVariable Y1f4c74 TrustMe 3 f4d14 Call qsort/3 4f4c80 GetList X0 f4d20 PutUnsafeValue Y0 X0f4c88 Allocate f4d2c PutYValue Y1 X1f4c8c UnifyYVariable Y5 f4d38 PutYValue Y2 X2f4c94 UnifyXVariable X0 f4d44 DeallocateAndExecute qsort/3f4c9c GetYVariable Y4 X1f4ca8 GetYVariable Y2 X2f4cb4 PutYValue Y5 X1

C. Exemplos de código gerado 133

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 Allocate f4fec Call number_variables/4 4f4f74 GetYVariable Y1 X1 f4ff8 PutConstant 0 X0f4f80 PutYVariable Y4 X1 f5004 PutYValue Y3 X1f4f8c Call preprocess/2 5 f5010 PutYValue Y2 X2f4f98 PutYValue Y4 X0 f501c Call complete_saga/3 4f4fa4 PutYVariable Y0 X1 f5028 PutYValue Y2 X0f4fb0 Call translate/2 5 f5034 Call allocate_registers/1 3f4fbc PutYValue Y0 X0 f5040 PutUnsafeValue Y0 X0f4fc8 PutConstant 0 X1 f504c PutYValue Y1 X1f4fd4 PutYVariable Y3 X2 f5058 DeallocateAndExecute generate/2f4fe0 PutYVariable Y2 X3

d(U*V, X, (DU*V)+(U*DV)) :- d(U,X,DU), d(V,X,DV).

f5178 GetStructure */2 X0 f51d4 UnifyYValue Y2f5184 UnifyXVariable X0 f51dc GetStructure */2 X4f518c Allocate f51e8 UnifyXValue X0f5190 UnifyYVariable Y2 f51f0 UnifyYVariable Y0f5198 GetYVariable Y1 X1 f51f8 PutYValue Y1 X1f51a4 GetStructure +/2 X2 f5204 Call d/3 3f51b0 UnifyXVariable X3 f5210 PutYValue Y2 X0f51b8 UnifyXVariable X4 f521c PutYValue Y1 X1f51c0 GetStructure */2 X3 f5228 PutYValue Y0 X2f51cc UnifyXVariable X2 f5234 DeallocateAndExecute d/3

test :- do(parse(s(np,vp),[birds,fly],[])).

f5378 PutList X1 f53b0 BuildConstant 'np'f5380 BuildConstant 'fly' f53b8 BuildConstant 'vp'f5388 BuildNil f53c0 PutStructure parse/3 X0f538c PutList X2 f53cc BuildXValue X1f5394 BuildConstant 'birds' f53d4 BuildXValue X2f539c BuildXValue X1 f53dc BuildNilf53a4 PutStructure s/2 X1 f53e0 Execute do/1

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 f5b74 Try f56d8f5b54 Try f56d8 f5b7c Retry f5758f5b5c Trust f5758 f5b84 Retry f5804f5b64 SwitchOnConstant f5ac0 8 f5b54 f5b8c Trust f5840

nl f5bac f5b94 Try f5618repeat f5b74 f5b9c Retry f56d8trace f5bc4 f5ba4 Trust f5758notrace f5b94 f5bac Try f5664true f5bdc f5bb4 Retry f56d8

C. Exemplos de código gerado 134

f5bbc Trust f5758f5bc4 Try f5594f5bcc Retry f56d8f5bd4 Trust f5758f5bdc Try f56d8f5be4 Retry f5758f5bec Trust f58a0f5bf4 SwitchOnStructure f5b24 2 f5b54

+/2 f5c04q/1 f5c24

f5c04 Try f5484f5c0c Retry f54f0f5c14 Retry f56d8f5c1c Trust f5758f5c24 Try f56d8f5c2c Retry f5758f5c34 Trust f57a0f5c3c Proceed

f5478 TryMeElse f54e4 1f5484 GetStructure +/2 X0f5490 UnifyXVariable X0f5498 UnifyVoidOnef549c Execute q/1

f54e4 RetryMeElse f5588 1f54f0 GetStructure +/2 X0f54fc UnifyVoidOnef5500 UnifyXVariable X0f5508 Execute q/1

f5588 RetryMeElse f560c 1f5594 GetConstant 'trace' X0f55a0 Execute trace/0

f560c RetryMeElse f5658 1f5618 GetConstant 'notrace' X0f5624 Execute notrace/0

f5658 RetryMeElse f56cc 1f5664 GetConstant 'nl' X0f5670 nl/0f5674 Proceed

f56cc RetryMeElse f574c 1f56d8 Execute sys/1

f574c RetryMeElse f5794 1f5758 Execute ext/1

f5794 RetryMeElse f57f8 1f57a0 GetStructure q/1 X0f57ac UnifyXVariable X0f57b4 Execute q/1

f57f8 RetryMeElse f5834 1f5804 GetConstant 'repeat' X0f5810 Proceed

f5834 RetryMeElse f5894 1f5840 GetConstant 'repeat' X0f584c PutConstant 'repeat' X0f5858 Execute q/1

f5894 TrustMe 1f58a0 GetConstant 'true' X0f58ac Proceed

a(X,Y) :- Y >>b(X).a(X,Y) :- X >>b(Y).a(X,Y) :- hello(x,Y) >> (>b(X)).

f5920 TryMeElse f5990 2f592c Allocatef5930 PushVarContext X1 0f593c VarCtxExtCall b/1f5944 PopContextf5948 DeallocateAndProceed

f5990 RetryMeElse f5a44 2f599c Allocatef59a0 PushVarContext X0 0f59ac PutXValue X1 X0f59b8 VarCtxExtCall b/1f59c0 PopContext

f59c4 DeallocateAndProceed

f5a44 TrustMe 2f5a50 Allocatef5a54 PutConstant 'x' X2f5a60 PutXValue X1 X3f5a6c PushContext hello 2 0f5a7c PushHistoricalContext 0f5a84 Call b/1@hello 0f5a90 PopHistoricalContextf5a94 PopContextf5a98 DeallocateAndProceed

unit authors(Work).import wrote/2 from Work.author(X) :- wrote(X,_).

wrote/2:f4fd0 Allocatef4fd4 PutZValue Z0 X2f4fe0 SwitchVarContextOn X2f4fe8 VarImportCall wrote/2f4ff0 SwitchContextOff

f4ff4 DeallocateAndProceed

author/1:f4d5c TryMeElse f4e58 1f4d68 PutVariableOne X1f4d70 Execute wrote/2

mailto:b/1@hello

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 Prologbased 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, MITPress, 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.201-209

Bibliografia 136

[Bowen 83]Bowen, L.; Byrd D.; Clocksin W.: “A Portable Prolog Compiler”, em LogicProgramming Workshop ‘83

[Bowen 86]Bowen, K.; Buettner K.; Cicekli I.; Turk A.: “The Design and Implementation of aHigh-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 CW10, Applied Mathematics and Programming Division, Katholieke Universiteit,Leuven, Belgica 1976

[Bruynooghe 82]Bruynooghe, M: “The Memory Management of Prolog Implementations”, em LogicProgramming, 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 communicationhomme-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’IntelligenceArtificielle, 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 StaticAnalisys 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 LogicProgramming, 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 Computationsin Prolog”, em Proc. 3º ICLP, Londres, 1986

[Dewar 75]Dewar, R.: “Indirect Threaded Code”, em Communications of the ACM, Vol. 18, 330-331, 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 WarrenAbstract 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, The Interactive Programming Environment”,Addison Wesley, 1983

[Goodwin 81]Goodwin, J.: “Why Programming Environments Needs Dynamic Data Types”, IEEETransactions on Software Engineering, val.SE-7,No.5, 1981

[Emden 81]Emden, M.: “An Algorithm for Interpreting Prolog Programs”, Department ofComputer Science, University of Waterloo, Ontário, Canada, Research Report CS-81-28, Setembro 1981

[Green 68]Green, C.: “Theorem-Proving by Resolution as a Basis for Question-AnsweringSystems”, Machine Intelligence 4, B. Meltzer e D. Michie (Eds.), EdinburghUniversity Press, 1968

[Hermenegildo 89]Hermenegildo, M.: “High-Performance Prolog Implementation: the WAM andBeyond”, 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 WAMby 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 programminglanguage”, 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 EfficientImplementation 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 PublishingCompany, 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”, ACMTransactions on Programming Languages and Systems, 4, 2, 1982

[Mellish 82]Mellish, C.: “An Alternative to Structure Sharing in the Implementation of aProlog Interpreter”, em Logic Programming, Academic Press, 1982

[Mellish 85]Mellish, C.: “Some Global Optimizations for a Prolog Compiler”, em Journal ofLogic Programming, 1, 1985

[Miller 86]Miller, D.: “A Theory of Modules for Logic Programming”, em Proc. Symp. on LogicProgramming, 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 LogicPrograming”, 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 SelectiveBacktracking”, Report 3/80, Centro de Informática da Universidade Nova deLisboa, 1980

[Pereira 82]Pereira, L.M.; Porto A.: “Selective backtracking for logic programs”, em LogicProgramming, Academic Press, 1982

[Plotkin 81]Plotkin, G.D.: “A Structural Approach to Operational Semantics”, DAIMITechnical 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 ofComputer and Information Science, Syracuse University, New York, 1980

[Roussel 75]Roussel, P.: “Prolog, Manuel de Référence et d'Utilisation”, Groupe d'IntelligenceArtificielle, Université d'Aix-Marseille, 1975

[Russinoff 89]Russinoff, D.: “A Verified Prolog Compiler for the Warren Abstract Machine”, MCCTechnical Report ACT-ST-292-89, Microelectronics and Computer TechnologyCorp., 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. onLogic Programming, Atlantic City (USA), 1984

[Teitelman 81]Teitelman, W; Masinter L.: “The Interlisp Programming Environment”, IEEEComputer, 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 programminglanguage”, Journal of the ACM 23(4), 1976

[Warren 74]Warren, D.: “Warplan: A System for Generating Plans”, Memo 76, University ofEdinburgh, 1974

[Warren 77a]Warren, D.: “Implementing Prolog: compiling predicate logic programs, DAI Report39-40, University of Edinburgh,1977.

[Warren 77b]Warren, D.; Pereira, L.M.; Pereira F.: “Prolog - The Language and itsImplementation Compared with Lisp”, em Proc. of the Symposium on ArtificialIntelligence and Programming Languages, SIGPLAN Notices, Vol 12, N. 8, e SIGARTNewsletters, Nº 64, Agosto 1977

[Warren 80]Warren, D.: “Logic Programming and Compiler Writing”, Software - Practice andExperience, Vol.10, 1980

[Warren 83]Warren, D.: “An Abstract Prolog Instruction Set”, SRI Technical Note 309, SRIInternational, 1983

[Warren 88]Warren, D.: “Implementation of Prolog”, Lecture notes, Tutorial nº 3, Symp. onLogic Programming, Seattle, USA, 1988

Documents

ctp.di.fct.unl.ptctp.di.fct.unl.pt/~amd/publications/1990-tese-mestrado.pdf · 2 Resumo Programação em lógica contextual, ou CxLP, é um novo esquema de programação que enriquece