PROJAVA: Um Tradutor de Prolog para Java · que os diferentes paradigmas que comp˜oem o Holo s˜ao traduzidos para o paradigma imperativo/orientado a objetos da linguagem Java. A

UNIVERSIDADE CATOLICA DE PELOTAS

ESCOLA DE INFORMATICA

CURSO DE CIENCIA DA COMPUTACAO

PROJAVA: Um Tradutor de

Prolog para Java

por

AUGUSTO MECKING CARINGI

Projeto de Graduacao submetido como requi-

sito parcial a obtencao do grau de Bacharel em

Ciencia da Computacao.

Orientador: Prof. Jorge L. V. Barbosa

Co-Orientadores: Prof. Adenauer C. Yamin

Prof. Luiz A. M. Palazzo

Pelotas, Novembro de 2002

2

Dedico, in memoriam, a minha avo,

Noemi de Assumpcao Osorio Caringi.

3

Quem, de tres milenios,

Nao e capaz de se dar conta

Vive na ignorancia, na sombra,

A merce dos dias, do tempo.

Johann Wolfgang von Goethe

4

SUMARIO

LISTA DE FIGURAS 6

LISTA DE TABELAS 7

RESUMO 8

ABSTRACT 9

1 INTRODUCAO 10

1.1 O Contexto do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.2 Principais Contribuicoes do Autor . . . . . . . . . . . . . . . . . . . . 13

1.3 Estrutura do Texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 HOLOPARADIGMA 15

2.1 Contexto e Motivacao . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2 Hololinguagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.3 Holojava . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3 PROLOG 19

3.1 Origens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.2 Implementacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.3 O Modelo de Execucao Prolog . . . . . . . . . . . . . . . . . . . . . . 19

3.4 WAM: Warren Abstract Machine . . . . . . . . . . . . . . . . . . . . 20

3.5 Tecnica de Binarizacao . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.6 Sistemas Prolog em Java . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.6.1 jProlog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.6.2 Prolog Cafe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4 PROJAVA 24

4.1 Visao Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4.2 Estrutura de um Tradutor . . . . . . . . . . . . . . . . . . . . . . . . 24

4.3 JavaCC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

5

4.4 JJTree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.5 Definicao da Gramatica Prolog . . . . . . . . . . . . . . . . . . . . . 29

4.6 Arvore de Sintaxe Abstrata . . . . . . . . . . . . . . . . . . . . . . . 31

5 IMPLEMENTACAO 33

5.1 Ambiente de Execucao do Prolog Cafe . . . . . . . . . . . . . . . . . 33

5.2 Indexacao de Clausulas . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5.3 Funcionamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5.4 Estrutura do Codigo Traduzido . . . . . . . . . . . . . . . . . . . . . 35

5.5 Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

5.6 Limitacoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

6 CONCLUSOES 40

7 REFERENCIAS BIBLIOGRAFICAS 42

A Gramatica Prolog para o JavaCC 45

B Programas Prolog usados nos benchmarks 49

B.1 Arvore Genealogica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

B.2 Serie de Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

B.3 Manipulacao de Listas . . . . . . . . . . . . . . . . . . . . . . . . . . 49

B.4 Torres de Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

C Exemplo de Codigo Traduzido: Fibonacci 51

D Exemplo de Holoprograma 55

6

LISTA DE FIGURAS

FIGURA 1 Polıtica de Conversao de Holo para Java . . . . . . . . . . . 18

FIGURA 2 Gerenciamento de Arquivos na Conversao de Holo para Java 18

FIGURA 3 Modulos do Prolog Cafe . . . . . . . . . . . . . . . . . . . . 23

FIGURA 4 Diagrama de Execucao . . . . . . . . . . . . . . . . . . . . 23

FIGURA 5 Diagrama de Geracao do Parser . . . . . . . . . . . . . . . 29

FIGURA 6 Gramatica Prolog . . . . . . . . . . . . . . . . . . . . . . . 31

FIGURA 7 Exemplo de Arvore de Sintaxe Abstrata . . . . . . . . . . . 32

FIGURA 8 Funcionamento Interno do PROJAVA . . . . . . . . . . . . 35

FIGURA 9 Diagrama de Traducao de Prolog para Java . . . . . . . . . 35

7

LISTA DE TABELAS

TABELA 1 Principais Opcoes do JavaCC . . . . . . . . . . . . . . . . . 27

TABELA 2 Tipo de Producoes do JavaCC . . . . . . . . . . . . . . . . 28

TABELA 3 Classes Java que modelam os termos Prolog . . . . . . . . . 33

TABELA 4 Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . 38

8

RESUMO

O Holoparadigma foi desenvolvido com as seguintes motivacoes: exploracao

do paralelismo implıcito, atuar sobre arquiteturas distribuıdas, trabalhar com mul-

tiplos paradigmas e explorar a execucao dos multiplos paradigmas de forma par-

alela e distribuıda. Com o objetivo de validar o modelo no menor prazo de tempo

possıvel, foi implementada uma ferramenta para traducao de codigo Holo para codigo

Java. Algumas abstracoes da Hololinguagem podem ser traduzidas diretamente para

Java; outras, entretanto, necessitam de programas adicionais. Este trabalho se en-

quadra nesse contexto e contribuira para integracao da programacao em logica ao

Holoparadigma. Seu objetivo e a implementacao de um modulo para traducao de

Prolog para Java. Este modulo sera responsavel pela traducao das acoes modulares

logicas da Hololinguagem em codigo Java, substituindo o modulo utilizado anteri-

ormente, o qual apresenta serios problemas de desempenho.

Palavras-chave: Holoparadigma, Holojava, Prolog, Tecnicas de traducao Prolog,

Programacao Multiparadigma

9

ABSTRACT

Holoparadigm was developed with the following motivations: to exploit the

implicit parallelism, to be run in distributed architectures, to work with multiple

paradigms and to explore the execution of multiple paradigms in a parallel and dis-

tributed manner. With the goal of validating the model in the shortest time possible,

was implemented a tool for the translation of Holo code to Java. Some abstractions

of Hololanguage could be translated direct to Java, others however need additional

programs. This work is fit in this context and will contribute to the integration of

logic programming to Holoparadigm. Its goal is the implementation of a module

to translate Prolog to Java. This module will be responsible for the translation of

Hololanguage’s modular logic actions to Java code, replacing the previously used

module which have serious performance problems.

Keywords: Holoparadigm, Holojava, Prolog, Prolog translation techniques,

Multiparadigm Programming

10

1 INTRODUCAO

Maior produtividade na programacao pode ser obtida atraves da escolha do

paradigma de programacao mais apropriado ao tratamento do problema, entretanto,

no desenvolvimento de sistemas de software complexos, muitas vezes, um unico

paradigma nao e suficiente. Nesses casos, a melhor abordagem e a programacao

multiparadigma (HORSPOOL 1996).

Linguagens de programacao tradicionais (baseadas no paradigma imperativo)

sao criticadas por nao possuırem embasamento matematico, pela dificuldade que elas

trazem ao desenvolvimento de software, por nao possuirem clareza e por forcarem

o programador a pensar de maneira sequencial. Por outro lado, quase a totali-

dade de sistemas implementados para uso industrial e comercial sao desenvolvidos

em linguagens imperativas, ficando os paradigmas “alternativos” restritos ao meio

academico. Provavelmente isso se atribua ao fato de que a transicao-de-estados,

conceito fundamental da programacao imperativa, seja, na verdade, um paradigma

muito util para resolver problemas praticos.

Contudo, torna-se claro que certos tipos de problemas sao resolvidos de muito

melhor forma atraves de paradigmas nao-imperativos. “Resolvidos de muito mel-

hor” forma significa que a solucao e mais clara, mais legıvel, mais concisa e que ele

modela de uma maneira muito melhor o problema tratado (HORSPOOL 1996).

Um dos principais representantes dos “paradigmas nao-convencionais” e o

paradigma da programacao em logica, paradigma este que tem como modelo com-

putacional a logica do calculo de predicados; conforme COLMERAUER (1992), o

termo “programacao em logica” e devido a Robert Kowalski, que vislumbrou a pos-

sibilidade de utilizacao da logica como linguagem de programacao.

Prolog, por sua vez, e a linguagem pioneira e principal representante do

paradigma da programacao em logica. De acordo com COLMERAUER (1992),

Prolog, que e a abreviacao de “PROgrammation en LOGique”, foi desenvolvida no

inıcio da decada de 70 por ele e seus colegas, na Universidade de Marselha. Desde

11

entao, a linguagem foi alvo de intensas pesquisas e, entre as suas principais areas de

aplicacao, destacam-se:

• Sistemas baseados em conhecimento;

• Sistemas de bases de dados;

• Sistemas especialistas;

• Processamento da linguagem natural;

• Engenharia de software;

• Prova automatica de teoremas;

• Construcao de compiladores;

• Computacao simbolica.

Segundo STERLING (1994), um programa logico e um conjunto de axiomas,

ou regras, que definem relacoes entre objetos. A computacao de um programa logico

e uma deducao de consequencias do programa. Um programa define um conjunto

de consequencias, que sao seu significado. A arte da programacao em logica consiste

em construir programas concisos e elegantes que apresentem o significado desejado.

Umas das principais ideias da programacao em logica e de que um algoritmo e

constituıdo por dois elementos disjuntos: a logica e o controle. O componente logico

corresponde a definicao do que deve ser solucionado, enquanto o componente de

controle estabelece como a solucao pode ser obtida. O programador precisa somente

descrever o componente logico de um algoritmo, deixando o controle da execucao a

cargo do sistema computacional. Isto possibilita que o programador simplesmente

especifique o problema, ao inves de ter que descrever o procedimento para solu-

ciona-lo (PALAZZO, 1997). Este alto poder de expressao, aliado a capacidade de

exploracao do paralelismo implıcito da linguagem Prolog, a torna umas das pecas-

chave do Holoparadigma.

HORSPOOL (1996) e BARBOSA (2002) analisam as diferentes tecnicas de

programacao multiparadigma. A Hololinguagem e classificada como uma linguagem

12

multiparadigma de unificacao total, porem, com o objetivo de testar os holopro-

gramas no menor espaco de tempo possıvel, foi desenvolvida uma ferramenta que

traduz codigo Holo para codigo Java, neste caso, a abordagem utilizada para fins

de execucao consiste na programacao multiparadigma baseada em traducao, posto

que os diferentes paradigmas que compoem o Holo sao traduzidos para o paradigma

imperativo/orientado a objetos da linguagem Java.

A ferramenta Holojava, a qual tem seu funcionamento detalhado no capıtulo

2, realiza a traducao dos holoprogramas para Java atraves de um mapeamento das

construcoes Holo para construcoes Java. Entretanto, alguns aspectos nao possuem

equivalentes em Java; nesses casos, sao utilizadas ferramentas adicionais, Tratando-

se especificamente do codigo Prolog, a ferramenta utilizada ate entao para traducao

era o Prolog Cafe, contudo, o baixo desempenho deste software, bem como a ne-

cessidade do domınio desta tecnologia de traducao, foram os fatores motivadores do

presente trabalho.

1.1 O Contexto do Trabalho

O Holoparadigma (BARBOSA, 2001) foi desenvolvido com as seguintes mo-

tivacoes: exploracao do paralelismo implıcito, atuar sobre arquiteturas distribuıdas,

trabalhar com multiplos paradigmas e explorar a execucao destes de forma paralela

e distribuıda.

Este trabalho se enquadra neste contexto e tem por objetivo central a imple-

mentacao de um novo tradutor de codigo fonte Prolog para codigo fonte Java, com

o intuito de substituir o utilizado anteriormente, o qual possui serios problemas de

desempenho.

O foco do trabalho e a integracao do paradigma da programacao em logica

ao Holoparadigma, atraves do novo tradutor.

13

1.2 Principais Contribuicoes do Autor

Alem de participar de discussoes sobre os aspectos relativos a integracao do

paradigma da programacao em logica ao Holoparadigma, destaca-se a atuacao do

autor nos seguintes aspectos do trabalho:

• Identificacao da origem do problema de desempenho do tradutor utilizado

posteriormente;

• Definicao da melhor abordagem para sanar o gargalo de desempenho;

• Identificacao da necessidade de aproveitamento do ambiente de execucao

do Prolog Cafe;

• Implementacao do novo tradutor.

1.3 Estrutura do Texto

O presente trabalho esta dividido em seis capıtulos, de forma a introduzir o

leitor gradativamente no tema proposto.

O primeiro capıtulo e a introducao, onde foram apresentados os objetivos, o

contexto do do trabalho e tambem as contribuicoes do autor.

No segundo capıtulo, sao introduzidos conceitos referentes ao Holoparadigma

e tecnologias relacionadas, incluindo Holojava, a ferramenta de traducao de Holo

para Java.

O terceiro capıtulo trata da linguagem Prolog, sua historia, suas principais

caracterısticas, fundamentos e tecnicas de implementacao, alem do tradutor atual-

mente utilizado na Holojava: Prolog Cafe.

Nos capıtulo quatro e cinco, sao descritos respectivamente, o modelo pro-

posto para o novo tradutor e sua implementacao e, no sexto, estao as conclusoes

deste trabalho.

14

A gramatica Prolog no formato da ferramenta JavaCC utilizada no desen-

volvimento do tradutor PROJAVA esta no anexo A. No anexo B, por sua vez, estao

os programas em Prolog utilizados nos testes de traducao e benchmarks. A listagem

completa do programa que calcula Fibonacci traduzido para Java pode ser encon-

trada no anexo C e, finalmente, o anexo D contem um exemplo de programa na

Hololinguagem.

15

2 HOLOPARADIGMA

2.1 Contexto e Motivacao

Conforme BARBOSA (2002), o Holoparadigma (de forma abreviada, Holo) e

um modelo multiparadigma que possui uma semantica simples e distribuıda. Atraves

dessa semantica, o modelo estimula a exploracao automatica da distribuicao (dis-

tribuicao implıcita). O estımulo a distribuicao implıcita e seu principal objetivo.

O paralelismo implıcito propoe a deteccao automatica do paralelismo e sua

exploracao atraves de mecanismos inseridos no software basico dos sistemas com-

putacionais. Por sua vez, nos ultimos anos, os sistemas distribuıdos tem recebido

cada vez mais atencao, tanto dos centros de pesquisa quanto das empresas. Nesse

contexto, torna-se interessante a integracao dos temas paralelismo implıcito e sis-

temas distribuıdos em um topico de pesquisa denominado distribuicao implıcita

(BARBOSA, 2002).

O Holoparadigma possui como unidade de modelagem os entes e, como

unidade de informacao, os sımbolos. Um ente elementar e organizado em tres

partes: interface, comportamento e historia. Um ente composto possui a mesma

organizacao de um ente elementar, no entanto, suporta a existencia de outros entes

na sua composicao (entes componentes). Cada ente possui uma historia. A historia

fica encapsulada no ente e, no caso dos entes compostos, e compartilhada pelos entes

componentes.

De acordo com BARBOSA (2002), um ente elementar assemelha-se a um

objeto do paradigma orientado a objetos. Do ponto de vista estrutural, a principal

diferenca consiste na historia, a qual atua como uma forma alternativa de comu-

nicacao e sincronizacao. Um ente composto assemelha-se a um grupo. Neste caso,

a historia atua como um espaco compartilhado vinculado ao grupo.

16

2.2 Hololinguagem

Conforme BARBOSA (2002), a Hololinguagem (de forma abreviada Holo),

implementa os conceitos propostos pelo Holoparadigma. Suas principais carac-

terısticas sao:

• multiparadigma: Holo integra multiplos paradigmas basicos. Atualmente,

estao integrados os paradigmas imperativo, em logica e orientado a objetos;

• sem tipos e orientada ao processamento simbolico: o sımbolo e a unidade

de informacao do Holoparadigma. A Hololinguagem e baseada no proces-

samento de sımbolos e nao possui tipos de dados;

• integracao da atribuicao e unificacao: as variaveis logicas sao manipuladas

atraves da unificacao (paradigma em logica), mas tambem existe suporte

para atribuicao;

• programacao de alta ordem: Holo suporta programacao de alta ordem,

isto significa que sımbolos representandos entes e suas partes podem ser

manipulados atraves de variaveis;

• blackboard hierarquico: exite suporte a varios nıveis de blackboard;

• suporte a Holoclonagem: Holo implementa a clonagem multipla e seletiva

como proposto no Holoparadigma;

• mobilidade: a mobilidade logica e suportada explicitamente, ja a mobili-

dade fısica fica a cargo do ambiente de execucao;

• suporte a concorrencia: existe suporte a concorrencia entre acoes e entre

entes;

• sintaxe logica compatıvel com Prolog: os aspectos logicos da sintaxe da

linguagem sao compatıveis com a linguagem Prolog;

• sintaxe imperativa baseada no Pascal: os aspectos imperativos da sin-

taxe sao baseados no Pascal, pela sua simplicidade e algumas semelhancas

sintaticas com Prolog.

17

Um holoprograma e formado por descricoes de entes (entes estaticos), as

quais sao formadas por Cabeca e Corpo. A cabeca contem o nome de um ente,

seus argumentos e uma descricao de sua clonagem. O corpo e formado por duas

partes: Comportamento e Historia. A historia e um blackboard que pode ser acessado

pelas acoes, pelos entes componentes ou pela propria historia. O comportamento e

constituıdo por um conjunto de acoes que implementam a funcionalidade, existindo

cinco tipos diferentes:

• Acao Logica (Logic Action - LA): acao formada por um unico predicado

logico (uma ou mais clausulas com mesmo nome e aridade);

• Acao Imperativa (Imperativa Action - IA): acao formada por uma funcao

imperativa;

• Acao Modular Logica (Modular Logic Action - MLA): acao formada por

um modulo que encapsula acoes logicas;

• Acao Modular Imperativa (Modular Imperative Action - MIA): acao for-

mada por um modulo que encapsula acoes imperativas;

• Acao Multiparadigma (Multiparadigm Action - MA): acao que suporta o

encapsulamento de LAs e IAs.

2.3 Holojava

De acordo com BARBOSA (2001), visando a realizacao de testes de Holo-

programas (programas em Holo) no menor espaco de tempo possıvel, foi criada uma

ferramenta de conversao de programas, denominada HoloJava. Esta ferramenta con-

verte programas em Holo (linguagem origem) para programas em Java (linguagem

destino). Esta tecnica e bastante usada na avaliacao de novas linguagens, pois a

utilizacao de uma linguagem destino que possua uma plataforma (compilacao e ex-

ecucao) ja disponıvel antecipa a realizacao de testes e a difusao de resultados da

pesquisa.

Diversos estudos indicam que Java pode ser utilizada como linguagem inter-

mediaria na construcao de compiladores. Java suporta diretamente varias abstracoes

18

do Holoparadigma (acoes imperativas, concorrencia, etc). No entanto, algumas car-

acterısticas de Holo nao sao suportadas (acoes logicas, blackboard e mobilidade).

Por outro lado, existem bibliotecas que complementam a plataforma Java e podem

ser utilizadas para implementacao dos aspectos nao suportados. Por exemplo, acoes

logicas em Prolog Cafe (BANBARA, 1999), historia em Jada ou JavaSpaces e mo-

bilidade fısica em Voyager ou Horb. A figura 1 mostra detalhadamente esta polıtica

de conversao.

Criação de um objeto (comando new)encapsulado em uma thread eatualização da HoloTree

Clonagem de Transiçãosuportando concorrênciainter−ente (ação clone)

Mobilidade lógica(ação move)

Reorganização da HoloTree econtrole de membership nos entes envolvidos

Afirmação para a história(símbolo "!")

Inserção de um fato no espaço Jada(método "out")

Pergunta não destrutiva bloqueantepara a história (símbolo ".")

Pergunta destrutiva bloqueantepara a história (símbolo "#")

Obtenção de um fato no espaço Jada(método "read")

Obtenção de um fato no espaço Jada(método "in")

Obtenção de um fato no espaço Jada(método "read_nb")

Obtenção de um fato no espaço Jada(método "in_nb")

ClasseEnte estático

Ação Imperativa (IA) Método

Ação Modular Lógica (MLA) Classes em Java (Prolog Café)

Invocação explícita Mensagem

História

Holo Java

Espaço de objetos em Jada

Pergunta não−bloqueante destrutivapara a história (símbolo "?#")

Pergunta não−bloqueante e não−destrutiva para a história (símbolo "?")

FIGURA 1: Polıtica de Conversao de Holo para Java

A figura 2 ilustra como e feito o gerenciamento dos arquivos na conversao

de Holo para Java. E utilizado no exemplo o programa datamining.holo, o qual

e composto de 3 entes e uma acao modular logica (MLA); a listagem completa do

19

programa esta no anexo D.

HoloJava

Prolog Café

JVM

Compilador Java

1

2

3

4

datamining.holo

holo.java miner.javamine.java fib.pl

MLAEnteEnteEnte

holo.class + *.class

PRED_fib_2.java

Predicado fib/2

holo mine miner fib

FIGURA 2: Gerenciamento de Arquivos na Conversao de Holo para Java

Atraves de benchmarks realizados em BARBOSA (2001a), foi possıvel con-

statar o baixo desempenho do Prolog Cafe. Em um programa Holo de 73 linhas, das

quais apenas 12 compondo uma MLA, 98,93% do tempo total de conversao foi gasto

pelo Prolog Cafe na traducao da MLA, e os resultados se repetiram em diferentes

programas, a conversao de um programa sem MLAs chegou a ser 105 vezes mais

rapida se comparada a um programa com MLAs. Baseado em tal fato, a utilizacao

das acoes modulares logicas foi considerada um ponto crıtico no desempenho da

conversao.

20

3 PROLOG

3.1 Origens

O nome “Prolog”, abreviacao de “PROgrammation en LOGique”, foi inven-

tado em Marselha no ano de 1972, ele foi escolhido por Philippe Roussel para desig-

nar um software projetado para implementar um sistema de comunicacao homem-

maquina em linguagem natural (COLMERAUER, 1992). A ideia chave por tras da

programacao em logica e que, computacao pode ser expressa como deducao contro-

lada.

3.2 Implementacao

A implementacao de Prolog tem uma longa historia. Os primeiros sistemas

foram implementados pelo grupo em torno de Colmerauer, em Marselha, sendo que

o primeiro interpretador foi escrito em 1972, em Algol. Se, por um lado, foi demon-

strado que era possıvel a implementacao de uma linguagem baseada na logica do

calculo de predicados, por outro, foi constatado que o principal problema era o baixo

desempenho.

O primeiro compilador Prolog foi escrito por David Warren em conjunto com

Fernando e Luıs Pereira em 1977. Esse compilador provou que era possıvel executar

Prolog com desempenho semelhante ao das linguagens imperativas tradicionais e

contribuiu muito para o sucesso da linguagem Prolog.

3.3 O Modelo de Execucao Prolog

As duas partes basicas de um interpretador Prolog sao a parte de unificacao

e a de resolucao. A resolucao e bastante simples, ela consiste em um mecanismo de

resolucao-SLD simplificado, que procura as clausulas de cima para baixo e avalia os

objetivos da esquerda para a direita. Esta estrategia leva ao mecanismo de retrocesso

(backtracking) e ao layout usual das areas de dados e pilha. A resolucao manipula a

21

pilha de alocacao, chamada de procedimentos, e o backtracking.

Unificacao em Prolog e definida como a seguir:

• duas constantes unificam se elas sao iguais;

• duas estruturas unificam se seus functores (nome e aridade) sao iguais e

todos os argumentos unificarem;

• duas variaveis livres unificam e sao amarradas juntas;

• uma variavel livre e uma constante ou estrutura unificam e a constante ou

estrutura e amarrada a variavel.

3.4 WAM: Warren Abstract Machine

Seis anos apos o desenvolvimento de seu compilador, David Warren apresen-

tou um novo conjunto de instrucoes abstratas Prolog. Este novo Prolog Engine veio

a se tornar muito popular com o nome Warren Abstract Machine (WAM). Desde

entao, ele tem sido a base para praticamente todas as implementacoes Prolog a par-

tir do ano de 1983. O Objetivo da WAM e de servir como um modelo simples e

eficiente de implementacao para interpretadores de byte code, bem como geradores

de codigo nativo.

GRUNE et al. (2001) analisam o fato de que enquanto poucos codigos in-

termediarios para linguagens imperativas alcancaram mais que fama local, o codigo

WAM se tornou um padrao de fato, e isso pode refletir a complexidade da tarefa de

compilar Prolog.

O modelo de execucao da WAM e mais semelhante ao das linguagens imper-

ativas do que qualquer outro modelo. A principal ideia e a divisao da unificacao

em duas partes, a copia dos argumentos do objetivo chamador para registradores de

argumentos e entao a unificacao destes registradores de argumentos com a cabeca da

clausula chamada. Isto e muito semelhante a passagem de parametros para funcoes

em linguagens imperativas como C.

22

De acordo com GRUNE et al. (2001), as instrucoes da WAM lidam com itens

como a selecao da clausula adequada a usar na deducao de um fato, unificacao sob

varias circunstancias e backtracking. Alem disso, a WAM faz toda a alocacao de

memoria, empregando, para isso, cinco pilhas.

3.5 Tecnica de Binarizacao

Conforme LINDGREN (1994), um problema fundamental em executar Pro-

log, consiste em como mapear eficientemente o controle (incluindo recursao e back-

tracking) para um hardware convencional. A solucao tradicional para este problema,

e traduzir codigo Prolog em instrucoes para uma maquina abstrata que gerencie as

estruturas de controle da linguagem Prolog. Tipicamente isso e realizado atraves da

WAM ou uma variante dela, outra abordagem, entretanto, e a tecnica de binarizacao.

A ideia chave do “Prolog Binario” e a transformacao das clausulas con-

vencionais em clausulas binarias utilizando Continuation Passing Style (CPS). A

essencia da tecnica de CPS consiste em inserir um argumento adicional em cada

predicado, que representa o proximo predicado a ser executado em caso de sucesso.

Pesquisas na area de linguagens funcionais demonstraram que a tecnica de CPS pode

expressar o controle de uma computacao de uma maneira muito semelhante ao que

os graficos de controle de fluxo fazem para as linguagens imperativas (LINDGREN,

1994).

BinProlog, um sistema Prolog muito eficiente desenvolvido por Paul Ta-

rau (TARAU, 1990) demonstrou as vantagens e desvantagens desta abordagem

de implementacao. Em “Prolog Binario”, uma clausula tem no maximo um sub-

objetivo, dessa forma, a regra de controle da resolucao-SLD que era implıcita, torna-

se explıcita. O codigo a seguir ilustra como uma clausula normal pode ser transfor-

mada em uma clausula binaria.

nrev([],[]).

nrev([H|T],R) :-

nrev(T,L), append(L,[H],R).

23

nrev([],[],Cont) :- call(Cont).

nrev([H|T],R,Cont) :-

nrev(T,L, append(L,[H],R,Cont)).

KRALL (2002) tambem analisa os pros e contras deste metodo de imple-

mentacao, o qual e motivado pelas simplificacoes que se tornam possıveis no sistema

de execucao. BinProlog, por exemplo, utiliza uma versao muito simplificada da

WAM, entretanto, algumas desvantagens, como maior consumo de memoria, se tor-

nam presentes.

3.6 Sistemas Prolog em Java

A implementacao de sistemas eficientes Prolog em Java e atualmente alvo de

pesquisas (BANBARA, 1999). O numero de sistemas deste tipo cresce a cada dia:

BirdLand’s Prolog in Java, CKI Prolog, DGKS Prolog, JavaLog, Jinni, JP, jProlog,

LL, MINERVA, W-Prolog e Prolog Cafe. Destes, apenas jProlog e Prolog Cafe sao

tradutores, os outros sao interpretadores.

3.6.1 jProlog

jProlog foi o primeiro conversor de Prolog para Java, desenvolvido em 1996

por Bart Demoen e Paul Tarau, ele se baseia na tecnica binarizacao (TARAU, 1990).

O sistema consiste em um conjunto de classes Java que dao suporte a ex-

ecucao, incluindo uma serie de predicados built-in e um tradutor escrito em Prolog.

O tradutor nao suporta o bootstraping de forma que e necessario um sistema Prolog

(SICSTus por exemplo) para realizar a conversao. Para executar o codigo, uma vez

que ele tenha sido traduzido, basta uma maquina virtual Java.

Conforme informacoes obtidas no site do projeto, JPROLOG (2002), o tradu-

tor foi escrito em Prolog por dois motivos: a falta de um gerador de parsers em Java

eficiente na epoca do projeto (1996), e as facilidades oferecidas pela linguagem Pro-

log para tal tipo de tarefa, incluındo a extensao DCG (Gramatica de Clausulas

Definidas).

24

3.6.2 Prolog Cafe

Conforme BANBARA (1999), Prolog Cafe e uma ferramenta que traduz

codigo fonte de um superconjunto de Prolog, chamado LLP (Linear Logic Pro-

gramming Language), para codigo fonte Java. O programa foi desenvolvido por

Mutsunori Banbara e Naoyuki Tamura, tendo por base o jProlog. Benchmarks

tambem realizados por BANBARA (1999) demonstram que o codigo gerado e 2,2

vezes mais rapido se comparado ao codigo do jProlog.

Alem do tradutor, o programa consiste de um ambiente de execucao para o

codigo traduzido, o qual e fortemente inspirado na WAM e um conjunto de predi-

cados built-in alguns escritos diretamente em Java e outros traduzidos a partir do

Prolog. A figura 3 ilustra os modulos da ferramenta, e a figura 4, por sua vez, mostra

como e feita a execucao.

O sistema possui duas versoes do mesmo tradutor, ambos com a mesma fun-

cionalidade, um implementado em Prolog e outro em Java, este ultimo sendo obtido

atraves da tecnica de bootstraping, isto e, o tradutor em Prolog e usado como entrada

para ele proprio, obtendo como saıda um tradutor em Java. De acordo com AHO

(1995), bootstraping consiste em utilizar as facilidades oferecidas por uma linguagem

para compilar a si mesma.

Predicados Built−inescritos em Java

execução (termos, algoritmode unificação, etc.)

Classes que dão suporte a

Prolog CaféProlog Café

bootstrapped)(acompanha versão

Tradutor de Prologpara Java

escrito em Prolog

Ambiente de Execuçãopara o código traduzido

FIGURA 3: Modulos do Prolog Cafe

25

Máquina Virtual Java (JVM)

Sistema Operacional

Código Traduzido

de Prolog para Java dão suporte a execução do código

Conjunto de classes Java que

traduzido

Ambiente de Execução

FIGURA 4: Diagrama de Execucao

26

4 PROJAVA

4.1 Visao Geral

Uma vez identificado que o baixo desempenho da ferramenta Prolog Cafe

deve-se ao fato de o tradutor ser bootstrapped, e reconhecendo que o ambiente de

execucao da mesma e fruto de muitos anos de pesquisa relacionada a traducao de

Prolog para linguagens imperativas, chegou-se a conclusao que a melhor abordagem

seria reescrever o tradutor, a partir do zero, totalmente em Java, porem aprovei-

tando as classes que dao suporte a execucao do codigo traduzido.

Para que isto seja possıvel, basta que o novo tradutor seja capaz de gerar um

codigo compatıvel com o run-time environment ja existente. Alem disso, tal abor-

dagem minimiza o impacto de adaptacao a Holojava de um modulo de traducao de

Prolog para Java totalmente diferente do que ja vinha sendo utilizado.

4.2 Estrutura de um Tradutor

O trabalho de um tradutor pode ser dividido basicamente em tres partes:

1. Analise lexica

2. Analise Sintatica

3. Geracao do Codigo

As primeiras duas fases compoem o nucleo do sistema e envolvem o entendi-

mento do programa fonte e a verificacao da correcao lexica e sintatica. A esse

processo damos o nome de parsing.

A funcao do analisador lexico e obter e dividir os tokens no programa fonte.

Um token e uma peca significativa do fonte, como uma palavra chave, pontuacao ou

literais como numeros ou strings, trechos que sao descartados incluem espacos em

27

branco e comentarios.

A analise sintatica consiste em obter uma cadeia de tokens provenientes

do analisador lexico e verificar se a mesma atende as especificacoes sintaticas da

gramatica da linguagem. Conforme AHO (1995) existem tres tipos gerais de anal-

isadores sintaticos: “metodo universal”, “top-down” e “bottom-up”. Atraves do

metodo universal e possıvel trabalhar com qualquer gramatica, analisadores de tal

classe sao muito ineficientes. Os do tipo “top-down” e “bottom-up”, bem mais efi-

cientes, trabalham somente com determinadas subclasses das gramaticas, mas que

sao, contudo, suficientemente expressivas para descrever as construcoes sintaticas

das linguagens de programacao.

Para implementacao, duas abordagens podem ser utilizadas, escrever o anal-

isador lexico e o analisador sintatico manualmente ou fazer uso de ferramentas que

realizam a geracao automatica de tais tipos de software a partir de determinadas

regras. Na decada de 50, com o advento dos primeiros compiladores, a construcao de

analisadores, especialmente os sintaticos, era considerada uma tarefa ardua. Desde

entao, muita teoria foi desenvolvida na area, com grande destaque para a Teoria das

Linguagens Formais, de modo que, atualmente, a construcao manual e desconsider-

ada na maior parte dos casos, deixando-se tal tarefa para ferramentas automatizadas.

Existe uma serie de ferramentas deste tipo, sendo as mais conhecidas, os

tradicionais lex (gerador de analisadores lexicos) e yacc (gerador de analisadores

sintaticos) que advem do mundo Unix; tais programas, porem, nao geram codigo

em Java. Dentro da gama de ferramentas que geram codigo Java, uma destacou-se

como padrao: JavaCC (Java Compiler Compiler). E interessante observar que tal

classe de software tambem e conhecida como Compilador de Compiladores. Outro

fator que determinou a adocao do JavaCC foi a previa utilizacao do mesmo no pro-

jeto Holoparadigma, posto que o parser da Hololinguagem e gerado atraves dele.

Tendo o processo de parsing sido executado com sucesso e nao gerado nen-

hum erro, o sistema tera uma representacao interna do programa a qual pode ser

facilmente manipulada pelo ultimo estagio do tradutor: o gerador de codigo, que,

ao contrario do parser, precisa ser escrito manualmente a fim de se obter o compor-

28

tamento desejado.

4.3 JavaCC

JavaCC e um gerador de parsers “top-down” em Java. Essa classe de parsers

tambem e conhecida como “descendente recursivo” e constroi a arvore de derivacao

a partir da raiz em direcao as folhas, permitindo o uso de gramaticas mais gerais

do que os parsers “bottom-up” que operam de forma inversa, sendo a sua unica

limitacao a impossibilidade da utilizacao de producoes com recursao a esquerda, o

que poderia ocasionar recursao infinita (PANKAJ, 2002). A estrutura do tipo de

analisador gerado e identica a especificacao da gramatica, o que pode ser visto como

um fator a mais de facilidade.

A ferramenta agrega as funcionalidades de gerador de analisador lexico e ger-

ador de analisador sintatico; dessa forma, o arquivo de especificacao da gramatica

contem tanto as especificacoes lexicas quanto as sintaticas, tornando facil a sua

manutencao.

Os recursos de analise lexica sao semelhantes aos da ferramenta “lex”, sendo

o “Token Manager” o componente responsavel pelo reconhecimento dos tokens da

gramatica, seu funcionamento consiste em reconhecer e retornar os mesmos para o

parser. Sua implementacao e basicamente um automato finito nao-determinıstico.

Estrutura de um Arquivo de Gramatica JavaCC:

Opc~oes JavaCC

Parser_Begin(Identificador)

Codigo

Parser_End(Identificador)

Produc~oes

A secao de opcoes e uma secao opcional onde sao especificados varios parame-

tros para customizacao do parser gerado, ela inicia pela palavra reservada options,

29

seguida por uma lista de uma ou mais opcoes. A tabela 1 lista as opcoes mais uti-

lizadas.

Nome da Opcao DescricaoLOOKAHED O valor padrao desta opcao e 1, ela especifica

o numero de tokens que devem ser “olhadosadiante” antes de ser tomada uma decisao emum ponto de escolha.

STATIC Esta e uma opcao booleana que tem comovalor padrao verdadeiro. Ela implica quetodos os metodos e variaveis de classe saodefinidos como estaticos no Token Managere no parser

DEBUG PARSER O valor padrao desta opcao e falso, quandoativada ela faz o parser prover informacoesadicionais em tempo de execucao.

JAVA UNICODE ESCAPE O valor padrao e falso. Quando ativada, estaopcao permite lidar com fluxos de entrada noformato Unicode.

TABELA 1: Principais Opcoes do JavaCC

A secao de Codigo, que fica entre Parser Begin( Identificador ) e Parser end(

Identificador ), tambem e chamada de Java Compilation Unit e contem codigo

Java opcional para instanciacao do parser, caso ele nao seja chamado atraves de uma

classe externa.

A ultima secao e a mais importante; uma gramatica usada para especificar a

sintaxe de uma linguagem de programacao consiste em um conjunto de producoes.

Uma producao e uma regra pela qual uma sequencia de sımbolos terminais e nao-

terminais sao reduzidos a um nao terminal, JavaCC permite a definicao de quatro

tipos de producoes, conforme a tabela 2:

4.4 JJTree

JJTree e um pre-processador para o JavaCC, que insere acoes para criacao de

uma arvore de sintaxe abstrata (AST - Abstract Syntax Tree) em varios lugares, em

30

Tipo da Producao Descricao“Javacode” Em certos casos e difıcil especificar con-

strucoes livres de contexto para determi-nadas gramaticas, este tipo de producao per-mite inserir codigo Java ao inves de umaproducao EBNF para lidar com estes casosespeciais.

“Expressao Regular” Estas producoes sao utilizadas para definiras entidades lexicas da gramatica, tambemconhecidas como tokens, que serao posterior-mente trabalhados pelo “Token Manager”.

“EBNF” Esta e a maneira padrao de especificargramaticas JavaCC. Uma producao EBNFpossui o formato: NT → α, onde NT eum unico sımbolo nao-terminal e α e umasequencia de zero ou mais terminais e/ounao-terminais.

“Token Manager” As declaracoes nesta secao sao embutidas no“Token Manager” gerado e sao acessıveis apartir das acoes lexicas.

TABELA 2: Tipo de Producoes do JavaCC

31

uma gramatica JavaCC. A saıda do JJTree e entao processada pelo JavaCC para

criacao do parser (JJTREE, 2002). A figura 5 ilustra esse processo.

Com a simples especificacao de uma gramatica para o JavaCC, obtemos um

parser, entretanto, tal software somente servira para determinar se um dado pro-

grama atende ou nao as regras da gramatica. Para que o processo de parsing gere

algum resultado (interpretacao do programa, traducao para uma linguagem destino,

etc.) e necessario programacao adicional.

O JavaCC permite a insercao de trechos de codigo Java associados a cada

producao da gramatica, tais codigos podem ter como objetivo a geracao direta de

um novo programa na linguagem destino. Outra abordagem, que traz maior flexibil-

idade, e a insercao de codigo para geracao de uma estrutura de dados representando

o programa fruto do parsing, a qual e conhecida como Arvore de Sintaxe Abstrata.

O JJTree faz isto automaticamente, inserindo acoes semanticas para criacao da AST

e gerando algumas classes que modelam a estrutura da mesma.

Por padrao, para cada sımbolo nao-terminal da gramatica, o JJTree gera

codigo para construcao de um nodo na arvore. Por exemplo, um nao-terminal

chamado Term dara origem a uma classe chamada ASTTerm. Posteriormente, a

arvore de sintaxe abstrata pode ser manipulada atraves de uma API do JJTree.

4.5 Definicao da Gramatica Prolog

Foi utilizado um subconjunto da gramatica Prolog definida pelo padrao ISO,

a sintaxe completa da linguagem Prolog pode ser encontrada em SCOWEN (1993).

A gramatica Prolog e relativamente simples, pois nao contem palavras reservadas.

Um programa em logica consiste basicamente de uma sequencia de clausulas, por

sua vez, cada clausula pode ser um fato ou uma regra. Um fato possui apenas uma

cabeca, enquanto uma regra possui uma cabeca e um corpo. O tipo de dado basico

da linguagem Prolog e o “termo”, um termo pode ser uma constante, uma variavel,

uma lista ou um termo composto, uma constante, por sua vez, pode ser um atomo

ou um numero.

32

para o JAVACC

Gramática Prolog

JJTREE

Gramática Prolog Anotada

para o JAVACC

JAVACC

gramática e gera uma ASTacordo com as regras da

análise léxica e sintática dePrograma Java que faz a

FIGURA 5: Diagrama de Geracao do Parser

Uma das caracterısticas nao suportadas na versao atual e a definicao dinamica

de operadores. O padrao ISO Prolog especifica que novos operadores podem ser

definidos em tempo de execucao, linguagens como C++ permitem a redefinicao

de novos comportamentos semanticos para operadores ja existentes, recurso con-

hecido como sobrecarga de operadores; entretanto, Prolog permite alem disso, a

utilizacao de qualquer sımbolo como novo operador. Uma vez que estes operadores

nao estao presentes nas regras gramaticais da linguagem, torna-se uma tarefa um

pouco complexa seu tratamento. PANKAJ (2002) propoe um metodo para lidar

com operadores dinamicos com o JavaCC.

Conforme GRUNE et al. (2001), as gramaticas livres de contexto constituem

o formalismo essencial para descrever a estrutura de programas em uma linguagem

de programacao. De acordo com AHO (1995), tais gramaticas foram introduzidas

por Chomsky como parte de um estudo das linguagens naturais e seu uso na especi-

33

ficacao de linguagens de programacao emergiu independentemente.

O conceito de gramatica livre de contexto, consistindo de sımbolos termi-

nais, nao-terminais, producoes e sımbolo nao-terminal inicial, independe da notacao

utilizada para escrever a gramatica, contudo, uma notacao se destacou, conhecida

como Backus-Naur Form, ou simplesmente BNF, a qual foi utilizada pela primeira

vez nos anos 60 para descrever a sintaxe da linguagem Algol (SETHI 1996). Pos-

teriormente, foi desenvolvida uma extensao para a notacao BNF, chamada EBNF

(Extended Backus-Naur Form), permitindo a especificacao de listas de elementos

e elementos opcionais. O objetivo da EBNF nao e adicionar novos recursos e sim

conveniencia, de forma que tudo que pode ser especificado em EBNF tambem pode

ser especificado em BNF.

A figura 6 utiliza a notacao EBNF para representar as producoes da gramatica.

O seguinte padrao e utilizado:

• [...] ou (...)? implica 0 ou 1 ocorrencia de qualquer construcao dentro

dos parenteses/chaves.

• (...)+ implica 1 ou mais ocorrencias de qualquer construcao dentro dos

parenteses.

• (...)* implica 0 ou mais ocorrencias de qualquer construcao dentro dos

parenteses.

As strings entre os sımbolos “〈” e “〉” denotam os sımbolos terminais da

gramatica, ja os trechos entre aspas compoem tokens da linguagem. A figura 6

contem a especificacao da gramatica no formato EBNF, a versao para o JavaCC

esta no anexo A.

4.6 Arvore de Sintaxe Abstrata

A gramatica livre de contexto previamente listada e utilizada para verificar

se um programa atende as regras da sintaxe Prolog. Alem disso, o parser deve

construir uma representacao interna do programa; a essa representacao interna em

forma de arvore damos o nome de Arvore de Sintaxe Abstrata (Abstract Syntax Tree

34

Program ::= (Clause)+ <EOF>Clause ::= Head (":-" Body)? "."Head ::= Atom ("(" Terms ")")?Body ::= Goal ("," Goal)*Goal ::= ((Atom ( "(" Terms ")" )? ) | Expression | <CUTOPERATOR>)Terms ::= Term ("," Term )*Term ::= (Atom ("(" Terms ")" )* | List | Variable | Number)List ::= "[" (Terms ("|" Term)?)? "]"Expression ::= Variable (RelExpression | MatExpression)RelExpression ::= <RELOPERATOR> (Variable | Number)MatExpression ::= <ISOPERATOR> (Variable | Number)

(<ADDOPERATOR> (Variable | Number))?Atom ::= <ATOM>Variable ::= <VARIABLE>Number ::= <NUMBER>

FIGURA 6: Gramatica Prolog

- AST). A fase seguinte do tradutor, o gerador de codigo, ira trabalhar com esta

estrutura para a construcao do programa Java.

O estilo orientado a objetos de construir a arvore se da com a criacao uma

classe para cada sımbolo nao-terminal da gramatica, isto e feito automaticamente

pela ferramenta JJTree, a figura 7 ilustra graficamente a arvore gerada para a

clausula familia(X,Y) :- pai(X,Z),pai(Z,Y).

35

Clause

Program

Atom (familia) Terms

Head

Term Term

Variable (X) Variable (Y)

Goal Goal

Body

Atom (pai) Terms Atom (pai) Terms

Term Term

Variable (Y)

Term Term

Variable (X) Variable (Z) Variable (Z)

FIGURA 7: Exemplo de Arvore de Sintaxe Abstrata

36

5 IMPLEMENTACAO

5.1 Ambiente de Execucao do Prolog Cafe

O run-time environment do Prolog Cafe consiste em um conjunto de classes

Java que dao suporte a execucao do codigo traduzido. A classe principal, Prolog.java,

implementa entre outras coisas os registradores, a area de dados e a rotina de

unificacao. Existem algumas outras classes que trabalham em conjunto, provendo,

por exemplo, estruturas para o gerenciamento do backtracking. E interessante ob-

servar que o mecanismo de funcionamento de tais classes e fortemente inspirado na

WAM, provando, mais uma vez, a influencia da mesma em todas as implementacoes

Prolog subsequentes a ela.

Para cada tipo de termo Prolog, existe uma classe Java equivalente, a qual e

uma sub-classe da classe abstrata Term:

Classe DescricaoVariableTerm Cria um objeto representando uma variavel

logica.IntegerTerm Representa os valores do tipo inteiro.SymbolTerm Esta classe cria objetos representando

atomos.ListTerm Modela as listas Prolog.StructureTerm Cria um objeto representando um termo

composto, um termo composto consiste emum functor e uma sequencia de um ou maistermos chamados argumentos

TABELA 3: Classes Java que modelam os termos Prolog

De acordo com BANBARA (1997), a definicao da classe abstrata Term torna

facil a manipulacao em Java de vetores de termos, uma vez que, em um vetor do

tipo Term, pode ser colocado qualquer objeto que seja uma sub-classe dele.

37

5.2 Indexacao de Clausulas

Uma das tecnicas de otimizacao utilizadas pelo Prolog Cafe, e que teve seu

comportamento mantido no PROJAVA e conhecida como indexacao de clausulas

(clause indexing); seu objetivo e reduzir o numero de clausulas para serem testadas

e evitar a criacao de pontos de escolha, sempre que possıvel. Os resultados sao

execucao mais eficiente e menor consumo de memoria.

A otimizacao mais trivial realizada por qualquer sistema Prolog e tentar ape-

nas as clausulas de um procedimento especıfico ao inves de testar todas as clausulas

do programa, durante a busca por alguma clausula unificante. A indexacao de

clausulas e um pouco mais complexa: apenas as clausulas em que o primeiro argu-

mento unifica com o objetivo sao selecionadas.

Todas as clausulas do predicado append/3 a seguir tem como primeiro ar-

gumento uma lista Prolog, atraves da tecnica de indexacao de clausulas, em uma

consulta do tipo append(teste, teste, teste). Como o primeiro argumento da

consulta e um atomo, o resultado seria falha, sem mesmo precisar testar sequer uma

unica clausula do predicado.

append([],L,L).

append([H|L],L1,[H|R]) :-

append(L,L1,R).

5.3 Funcionamento

O nome do programa Prolog a ser traduzido e passado via linha de comando

ao tradutor, entra entao em acao o parser. Caso o programa atenda as regras lexicas

e sintaticas da gramatica Prolog e nenhum erro ocorra, o processo criara uma rep-

resentacao interna em forma de arvore: a figura 8 ilustra graficamente os modulos

internos da ferramenta. A tarefa agora cabe ao gerador de codigo, o primeiro passo

e percorrer a arvore em busca de informacoes uteis como o nome e aridade dos pred-

icados e o numero de clausulas de cada predicado. Para cada predicado, tambem

e analisado o tipo do primeiro argumento de cada clausula, informacoes estas rele-

38

vantes para o recurso de clause indexing.

Colhidos estes primeiros dados sobre o programa, comeca a gravacao das

classes Java em disco, um predicado por vez, e gerada a classe base, que representa

o ponto de entrada e entao as classes adicionais para clada clausula. A operacao

consiste em percorrer os ramos da arvore de sintaxe abstrata correspondentes a cada

clausula e gerar o codigo Java equivalente. A figura 9 mostra o processo completo,

desde a leitura do arquivo Prolog ate obtencao do bytecode Java. A execucao do

codigo traduzido segue o mesmo modelo demonstrado na figura 4 no capıtulo 3.

Código fonte Prolog

Código fonte Java

Análise Sintática

Análise Léxica

Tradutor PROJAVA

Geração da Árvorede Sintaxe Abstrata

Geração doCódigo Java

FIGURA 8: Funcionamento Interno do PROJAVA

39

Código fonte Prolog

Código fonte Java

Compilador javac

Java bytecode

Tradutor PROJAVA

FIGURA 9: Diagrama de Traducao de Prolog para Java

5.4 Estrutura do Codigo Traduzido

A estrutura do codigo traduzido segue o mesmo modelo do Prolog Cafe, para

cada predicado e criado um arquivo .java contendo uma classe publica, que consiste

no ponto de entrada do predicado, e uma classe adicional privada, para cada clausula

do mesmo. Tomando como exemplo o predicado pai/2 a seguir, e criado um arquivo

com o nome PRED pai 2.java.

pai(leonardo, augusto).

pai(leonardo, alberto).

A classe publica, representando o entry point, e uma sub-classe de Predicate,

o seu metodo construtor recebe os argumentos passados ao predicado e os coloca

40

em variaveis de instancia (arg1, arg2); o metodo exec() e responsavel pela ex-

ecucao, ele coloca os argumentos nos registradores da engine, seta o argumento de

continuacao e entao faz uma chamada ao metodo call(). Este, por sua vez, cuida

da chamada as clausulas do predicado atraves de uma construcao herdada da WAM

(switch on term()) que implementa a indexacao de clausulas.

public class PRED_pai_2 extends Predicate

{

static Predicate fail_0 = new PRED_fail_0();

static Predicate pai_2_1 = new PRED_pai_2_1();

static Predicate pai_2_2 = new PRED_pai_2_2();

static Predicate pai_2_var = new PRED_pai_2_var();

public Term arg1, arg2;

public PRED_pai_2(Term a1, Term a2, Predicate cont)

{

arg1 = a1;

arg2 = a2;

this.cont = cont;

}

public PRED_pai_2(){}

public void setArgument(Term[] args, Predicate cont)

{

arg1 = args[0];

arg2 = args[1];

this.cont = cont;

}

public Predicate exec()

{

engine.aregs[1] = arg1;


41

engine.cont = cont;

return call();

}

public Predicate call()

{

engine.setB0();

return engine.switch_on_term(

pai_2_var,

fail_0,

pai_2_var,

fail_0,

fail_0

);

}

public int arity()

{

return 2;

}

public String toString()

{

return "pai(" + arg1 + ", " + arg2 + ")";

}

}

Para cada clausula e criada uma sub-classe da classe “base” do predicado,

sendo o metodo exec() o responsavel pelo codigo da clausula. O primeiro passo

entao e a obtencao dos argumentos que estao nos registradores do ambiente de ex-

ecucao atraves da desreferencia. A desreferencia e necessaria, porque caso o conteudo

do registrador seja uma variavel, esta pode estar ligada a outra variavel, e assim su-

cessivamente, de forma que e preciso seguir a trilha de ponteiros de uma variavel

logica ate encontrar o “ultimo da lista”. Tambem e setado o parametro de con-

tinuacao, que indica o proximo predicado a ser executado em caso de sucesso.

42

O codigo seguinte dentro do metodo exec() tenta fazer a unificacao dos

argumentos com o termos da clausula, a engine prove o metodo unify() que im-

plementa o algoritmo de unificacao. Caso algum termo nao unifique, e chamado o

metodo engine.fail(), que ira se encarregar de tomar acao certa no caso de falha.

final class PRED_pai_2_1 extends PRED_pai_2

{

static SymbolTerm s1 = SymbolTerm.makeSymbol("leonardo");

static SymbolTerm s2 = SymbolTerm.makeSymbol("augusto");


{

Term a1, a2;

a1 = engine.aregs[1].dereference();


this.cont = engine.cont;

if ( !s1.unify(a1, engine.trail) ) return engine.fail();


return cont;

}

}

5.5 Benchmarks

O teste de desempenho compara o tempo que os tradutores levam para con-

verter o codigo Prolog em codigo Java. O desempenho de execucao dos programas

traduzidos nao foi alvo de benchmarks, posto que o codigo gerado pelos dois tradu-

tores e muito semelhante.

Foi possıvel constatar que o tradutor PROJAVA e em media dez vezes mais

rapido no processo de traducao, contudo, vale observar que, na realidade, e o Prolog

Cafe que apresenta um desempenho muito baixo, por ser um programa relativamente

43

Programa No de linhas Prolog Cafe PROJAVA Speedupfamilia.pl 15 5.406s 0.515s 10.50fibo.pl 9 4.753s 0.499s 9.53listas.pl 23 5.446s 0.530s 10.28hanoi.pl 11 5.443s 0.523s 10.41

TABELA 4: Benchmarks

grande em Prolog que foi traduzido para Java e possui todo overhead de emulacao

Prolog em Java.

5.6 Limitacoes

Algumas caracterısticas do tradutor que faz parte do software Prolog Cafe

ainda nao foram completamente implementadas no PROJAVA, entre elas: o suporte

completo a termos compostos aninhados e expressoes, tambem aninhadas. O trata-

mento de tais recursos e de natureza altamente recursiva e, o suporte completo a

eles sera incorporado a versoes futuras do PROJAVA.

44

6 CONCLUSOES

Enquanto o Holoparadigma nao contar com um compilador e uma maquina

virtual multiparadigma capazes de tratar os diferentes paradigmas suportados da

forma mais otimizada possıvel, a abordagem de traducao para Java e a alternativa

mais viavel. Entretanto, a ferramenta responsavel pela conversao das acoes modu-

lares logicas da Hololinguagem para Java sofria de serios problemas de desempenho

relativos ao tempo de traducao.

Atraves de constacoes empıricas foi possıvel verificar que:

• o baixo desempenho devia-se ao fato de o tradutor ter sido escrito em

Prolog, e entao ser auto-traduzido para obtencao de uma versao do mesmo

em Java;

• o modelo de codigo gerado e fruto de muitos anos de pesquisa primeira-

mente na traducao de Prolog para C, e entao de Prolog para Java, de forma

que este modelo poderia permanecer sem modificacoes.

Dessa forma, o trabalho consistiu em implementar um novo tradutor capaz

de gerar codigo compatıvel com o que e gerado pelo Prolog Cafe, afim de que se

pudesse fazer o aproveitamento das classes Java que dao suporte a execucao do

codigo traduzido. Para isso, foi necessario o estudo de toda a teoria que envolve a

construcao de um software de tal natureza. A ferramenta JavaCC foi utilizada para

geracao do front-end do tradutor, enquanto o gerador de codigo foi implementado

manualmente. Atraves de benchmarks, foi possıvel verificar que este novo tradutor

e cerca de 10 vezes mais rapido que o conversor do Prolog Cafe.

Trabalhos futuros:

• Aperfeicoamento da ferramenta PROJAVA para suportar uma gama maior

de recursos da linguagem Prolog, como por exemplo, suporte completo a

termos compostos aninhados;

• Uma das principais motivacoes do Holoparadigma e a exploracao do paral-

ismo implıcito, fato que nao esta sendo realizado para o paradigma logico.

45

Futuras versoes do PROJAVA poderiam gerar codigo Java, que se utilizaria

de multiplas linhas de execucao (threads) para exploracao do paralelismo;

• Conhecimento na realizacao do trabalho pode servir de base para o suporte

do paradigma da programacao em logica, em uma futura maquina virtual

multiparadigma.

46

7 REFERENCIAS BIBLIOGRAFICAS

AHO, Alfred V.; SETHI, Ravi; ULLMAN, Jefrrey D. Compi-

ladores: Princıpios, Tecnicas e Ferramentas. Rio de Janeiro:

LTC Editora, 1995. 344p.

AIT-KACI, Hassan. Warren’s Abstract Machine: A Tutorial Re-

construction. The MIT Press (out of print), 1991. Disponıvel

em http://isg.sfu.ca/~hak

APPEL, A. W. Compiling with Continuations. Cambridge Uni-

veristy Press, 1992.

BANBARA, M.; TAMURA N. Java implementation of a linear

logic programming language. In proceedings of Post-JICSLP’98

Workshop on Parallelism and Implementation Technology for

Logic Programming Languages. 1997.

BANBARA, M.; TAMURA, N. Translating a Linear Logic Pro-

gramming Language into Java. Workshop on Parallelism and

Implementation Technology (Constraint) Logic Programming

Languages, Las Cruces, p. 19-39, December. 1999.

BARBOSA, Jorge L. V.; DU BOIS, Andre R.; FRANCO, Laerte

K.; GEYER, Claudio F. R. Traduzindo Holo para Java. 2001.

BARBOSA, Jorge L. V.; Geyer, Claudio F.R. Integrating Logic

Blackboards and Multiple Paradigm for Distributed Software

Development. Proceedings of Intr. Conference on Parallel

and Dist. Processing Techniques and Applications (PDPTA).

June. 2001.

BARBOSA, Jorge L. V.; “Holoparadigma: um Modelo Multi-

paradigma Orientado ao Desenvolvimento de Software Dis-

tribuıdo”. Porto Alegre: CPGCC da UFRGS, 2002. 221p.

(Teste, Doutorado em Ciencia da Computacao).

47

COLMERAUER A.; ROUSSEL, P. The birth of Prolog. Novem-

bro. 1992.

GRUNE, Dick; BAL, Henri E.; JACOBS, Ceriel J. H.; LANGEN-

DOEN, Koen G. Projeto Moderno de Compiladores: Imple-

mentacao e Aplicacoes. Rio de Janeiro: Campus, 2001. 671p.

HORSPOOL, R. N.; LEVY, M. R. Translator-Based Multiparadigm

Programming.

JavaCC - The Java Parser Generator. http://www.webgain.

com/products/metamata/java_doc.html, Dezembro. 2001.

JJTree. http://www.webgain.com/products/java_cc/jjtree.

html, Novembro, 2002.

jProlog. http://www.cs.kuleuven.ac.be/~bmd/PrologInJava/,

Novembro, 2002.

KRALL, A. Implementation Techniques for Prolog.

LINDGREN, Thomas. A Continuation-Passing Style for Prolog.

Technical Report 86. Uppsala University. 1994.

PALAZZO, L. A. M. Introducao a Programacao PROLOG. Pelotas:

EDUCAT, 1997. 353p.

PANKAJ, G. The Design and Implementation of Prolog Parser

Using JavaCC. University of North Texas. Maio de 2002.

(Dissertacao, Mestrado em Ciencia da Computacao)

SETHI, Ravhi. Programming Languages: Concepts & Consructs.

Murray Hill, New Jersey: Addison-Wesley, 1997. 640p. 2.ed.

SCOWEN, R. S. �Draft prolog standard, Technical Report ISO/IEC

JTC1 SC22 WG17 N110, International Organization for Stan-

dardization, 1993.

48

STERLING, L; SHAPIRO, E. The Art of Prolog 2.ed. Cam-

bridge: MIT Press, 1994. 509 p.

TARAU, P.; BOYER, M. Elementary Logic Programs. Proceed-

ings of Programming Language Implementation and Logic

Programming, number 456 in Lecture Notes in Computer Sci-

ence, paginas 159-173. Springer: Agosto. 1990.

TARAU, P. Jinni: Intelligent Mobile Agent Programming at the

Intersection of Java and Prolog. PAAM’9, The Practical Ap-

plications Company. 1999.

WERNER, Otilia. Uma Maquina Abstrata Estendida para o

Paralelismo E na Programacao em Logica. Porto Alegre:

CPGCC da UFRGS, 1994. 150p. (Dissertacao, Mestrado

em Ciencia da Computacao).

49

A Gramatica Prolog para o JavaCC

options

{

MULTI = true;

}

PARSER_BEGIN(PrologParser)

public class PrologParser

{

public static void main(String arguments[]) throws ParseException

{

}

}

PARSER_END(PrologParser)

SPECIAL_TOKEN : /* Comments */

{

<SINGLE_LINE_COMMENT1: "%" (~["\n","\r"])* ("\n"|"\r"|"\r\n")>

| <SINGLE_LINE_COMMENT2: "//" (~["\n","\r"])* ("\n"|"\r"|"\r\n")>

| <MULTI_LINE_COMMENT: "/*" (~["*"])* "*" (~["/"] (~["*"])* "*")* "/">

}

SKIP:

{

" " | "\t" | "\r" | "\n"

}

TOKEN: /* Operators */

{

< CUTOPERATOR : "!" >

| < ADDOPERATOR : "+" | "-" >

| < MULOPERATOR : "*" | "/" | "mod" >

| < RELOPERATOR : "=" | "==" | "!=" | ">" | "<" | ">=" | "<=" >

| < ISOPERATOR : "is" >

| < MATOPERATOR : <ADDOPERATOR> | <MULOPERATOR> >

}

50

TOKEN: /* Numeric constants */

{

< NUMBER: (<DIGIT>)+ >

| < #DIGIT: ["0" - "9"] >

| < CHAR_LITERAL: "’" (~["’","\\","\n","\r"])* "’" >

}

TOKEN: /* Function names */

{

< VARIABLE: ( (<HICASE> | "_" ) ( <ANYCHAR> )* ) >

| < ATOM: ( <LOCASE> ) ( <ANYCHAR> )* >

| < #ANYCHAR: ( <LOCASE> | <HICASE> | <DIGIT> | "_" ) >

| < #LOCASE: ["a"-"z"] >

| < #HICASE: ["A"-"Z"] >

}

ASTProgram Program() :

{}

{

(Clause())+ <EOF>

{ return jjtThis; }

}

void Clause() :

{}

{

Head() [ ":-" Body() ] "."

}

void Head() :

{}

{

Atom() [ "(" Terms() ")" ]

}

void Body() :

{}

{

Goal() ("," Goal())*

}

51

void Goal() :

{}

{

((Atom() [ "(" Terms() ")" ]) | Expression() | <CUTOPERATOR>)

}

void Terms() :

{}

{

Term() ("," Term())*

}

void Term() :

{}

{

Atom() ("(" Terms() ")")* | List() | Variable() | Number()

}

void List() :

{}

{

"[" [ Terms() ["|" Term()]] "]"

}

void Expression() :

{}

{

Variable() (RelExpression() | MatExpression())

}

void RelExpression() :

{ Token t; }

{

t = <RELOPERATOR> (Variable() | Number())

{

jjtThis.setOp(t.image);

}

}

void MatExpression() :

52

{ Token t = null; }

{

<ISOPERATOR> (Variable() | Number()) [ t = <ADDOPERATOR> (Variable() | Number()) ]

{

jjtThis.setOp(t.image);

}

}

void Atom() :

{ Token t; }

{

t = <ATOM>

{

jjtThis.setName(t.image);

}

}

void Variable() :

{ Token t; }

{

t = <VARIABLE>

{


}

}

void Number() :

{ Token t; }

{

t = <NUMBER>

{


}

}

53

B Programas Prolog usados nos bench-

marks

B.1 Arvore Genealogica

familia(X,Y) :- pai(X,Z),pai(Z,Y).

familia(X,Y) :- pai(X,Z),mae(Z,Y).

familia(X,Y) :- mae(X,Z),pai(Z,Y).

familia(X,Y) :- mae(X,Z),mae(Z,Y).

pai(nadir,jorge).

pai(nadir,bia).

pai(nadir,sergio).

pai(sergio,antonio).

pai(sergio,helena).

mae(zita,jorge).

mae(zita,bia).

mae(zita,sergio).

mae(bia,victoria).

mae(bia,catarina).

B.2 Serie de Fibonacci

fib(1,1).

fib(2,1).

fib(M,N) :-

M > 2,

M1 is M-1,

M2 is M-2,

fib(M1,N1),

fib(M2,N2),

N is N1+N2.

B.3 Manipulacao de Listas

listas(T,L,Z,K) :-

gera_lista(T,L),

54

nrev(L,Z),

size(Z,K).

nrev([],[]).

nrev([H|L],R) :-

nrev(L,R1),

append(R1,[H],R).

append([],L,L).


append(L,L1,R).

gera_lista(0,[]).

gera_lista(N,[Ca|Co]) :-

Ca is N - 1,

gera_lista(Ca,Co).

size([],0).

size([X|Y],T) :-

size(Y,Z),

T is Z + 1.

B.4 Torres de Hanoi

hanoi(1,A,B,C,[mv(A,C)]).

hanoi(N,A,B,C,M) :-

N > 1, N1 is N - 1,

hanoi(N1,A,C,B,M1),

hanoi(N1,B,A,C,M2),

append(M1,[mv(A,C)],T),

append(T,M2,M).

append([],L,L).


append(L,L1,R).

55

C Exemplo de Codigo Traduzido: Fibonacci

// Generated Java file by ProJava

// A Prolog to Java source-to-source translation system

// September 2002

// Author: Augusto Mecking Caringi

import jp.ac.kobe_u.cs.prolog.lang.*;

public class PRED_fib_2 extends Predicate

{

static Predicate fail_0 = new PRED_fail_0();

static Predicate fib_2_1 = new PRED_fib_2_1();



static Predicate fib_2_var = new PRED_fib_2_var();

public Term arg1, arg2;

public PRED_fib_2(Term a1, Term a2, Predicate cont)

{

arg1 = a1;

arg2 = a2;

this.cont = cont;

}

public PRED_fib_2(){}

public void setArgument(Term[] args, Predicate cont)

{

arg1 = args[0];

arg2 = args[1];

this.cont = cont;

}


{



engine.cont = cont;

56

return call();

}

public Predicate call()

{

engine.setB0();

return engine.switch_on_term(

fib_2_var,

fib_2_var,

fail_0,

fail_0,

fail_0

);

}

public int arity()

{

return 2;

}

public String toString()

{

return "fib(" + arg1 + ", " + arg2 + ")";

}

}

final class PRED_fib_2_var extends PRED_fib_2

{

static Predicate fib_2_var_1 = new PRED_fib_2_var_1();


{

return engine.jtry(fib_2_1, fib_2_var_1);

}

}

final class PRED_fib_2_var_1 extends PRED_fib_2

{

static Predicate fib_2_var_2 = new PRED_fib_2_var_2();


{

57

return engine.retry(fib_2_2, fib_2_var_2);

}

}

final class PRED_fib_2_var_2 extends PRED_fib_2

{


{

return engine.trust(fib_2_3);

}

}

final class PRED_fib_2_1 extends PRED_fib_2

{

static IntegerTerm s1 = new IntegerTerm(1);



{

Term a1, a2;






return cont;

}

}


{




{

Term a1, a2;




58



return cont;

}

}


{


{

Term a1, a2, a3, a4, a5, a6;




a3 = engine.makeVariable();




Predicate p1 = new PRED_$plus_3(a5, a6, a2, cont);

Predicate p2 = new PRED_fib_2(a4, a6, p1);

Predicate p3 = new PRED_fib_2(a3, a5, p2);

Predicate p4 = new PRED_$minus_3(a1, new IntegerTerm(2), a4, p3);

Predicate p5 = new PRED_$minus_3(a1, new IntegerTerm(1), a3, p4);

return new PRED_$greater_than_2(a1, new IntegerTerm(2), p5);

}

}

59

D Exemplo de Holoprograma

// datamining.holo

//******************** ENTE PRINCIPAL ********************

holo() // Ente principal.

{

holo() // Acao guia.

{

writeln(’HOLO: Vou criar tres minas e um mineiro’),

clone(mine(1),mine_d1), // Cria a primeira mina.

clone(mine(2),mine_d2), // Cria a segunda mina.

clone(mine(3),mine_d3), // Cria a terceira mina.

clone(miner,miner_d), // Cria o mineiro.

for X := 1 to 3 do // Aguarda pelos resultados da mineracao.

{

history#list(#Ident,#Num,#Fibo), // Obtem o resultado de uma mineracao.

writeln(’HOLO: Terminou a mineracao da mina:’,Ident),

writeln(’HOLO: Fibonacci de ’,Num,’ e ’,Fibo)

}

writeln(’HOLO: Terminou a mineracao’)

}

}

//******************** ENTE MINA *******************

mine()

{

mine(Ident)

{

writeln(’MINA ’,Ident,’: Fui criada’)

}

history // A historia da mina de cada mina possui

{ // o mesmo conteudo. O primeiro numero

list(1,2). // identifica a mina. O segundo e o numero

list(2,4). // usado para o calculo do Fibonacci.

list(3,6).

}

}

60

//******************** ENTE MINEIRO *******************

miner()

{

miner()

{

writeln(’MINEIRO: Inicio da mineracao.’),

move(self,mine_d1), // Passo 1 - Entra na mina 1

mining(1,Num1,Res1), // Passo 2 - Minera a mina 1

move(self,out), // Passo 3 - Sai da mina 1

out(history)!list(1,Num1,Res1), // Passo 4 - Salva o resultado 1









writeln(’MINEIRO: Fim da mineracao.’)

}

mining(Ident,Num,Result) // IA que realiza a mineracao.

{

out(history)#list(Ident,#Num), // Minera a historia externa para

// obtencao de um dado.

fib(Num,#Result) // Chama a MLA para determinar Fibonacci.

}

fib/2() // Acao Modular Logica (MLA) que calcula Fibonacci.

{

fib(1,1).

fib(2,1).

fib(M,N) :-

M > 2,

M1 is M-1,

M2 is M-2,

fib(M1,N1),

fib(M2,N2),

N is N1+N2.

}

}

Documents

PROJAVA: Um Tradutor de Prolog para Java · que os diferentes paradigmas que comp˜oem o Holo s˜ao traduzidos para o paradigma imperativo/orientado a objetos da linguagem Java. A