Forem: Alex Sandro Garzão

Teste de fogo: fatorial recursivo

Alex Sandro Garzão — Tue, 13 Aug 2024 21:58:59 +0000

Para quem não está acompanhando o POJ (Pascal on the JVM) é um compilador que transforma um subset de Pascal para JASM (Java Assembly) de forma que possamos usar a JVM como ambiente de execução.

Na última postagem foi implementado o suporte ao read/readln de Pascal, funções que possibilitam a leitura de dados da entrada padrão (stdin). Nesta publicação vamos concluir um dos objetivos do POJ: ler um número da entrada padrão e calcular o fatorial de forma recursiva.

Como estamos compilando para a JVM faz-se necessário detalhar o funcionamento de vários pontos desta incrível máquina virtual. Com isso, em vários momentos eu detalho o funcionamento interno da JVM bem como algumas das suas instruções (opcodes).

Fatorial recursivo, a cereja do bolo :-)

Como citado no início do projeto um dos objetivos era podermos calcular o fatorial de forma recursiva, lendo o número a ser calculado da entrada padrão. As implementações no POJ até o momento possibilitaram este objetivo:

Hello world: criou a base de código do projeto com ANTLR, parser e geração de código Java Assembly;
Operadores de adição, subtração, multiplicação, divisão e o início das sentenças condicionais - if: iniciou o suporte aos operadores bem como o suporte inicial às senteças condicionais;
Repeat, while e for: suporte às estruturas de repetição;
Funções em Pascal: implementação de funções recursivas.

Agora chegou o momento de validar o que foi desenvolvido até o momento. Dito isso, a partir do programa Pascal abaixo:

program fatorial;

var numero : integer;

function fatorial(n : integer) : integer;
begin
    if n<0 then fatorial := 0
    else begin
        if n<=1 then fatorial := 1
        else fatorial := n * fatorial(n-1);
    end;
end;

begin
    write('Introduza numero inteiro: ');
    readln(numero);
    writeln;
    writeln('O fatorial de ', numero, ' e: ', fatorial(numero));
end.

O POJ gera corretamente o seguinte assembly:

// Code generated by POJ 0.1
public class fatorial {
    public static numero I

    static fatorial(I)I {
        iload 0
        sipush 0
        if_icmpge L4
        iconst 1 
        goto L5
    L4: iconst 0 
    L5: ifeq L1
        sipush 0
        istore 100
        goto L2
    L1: iload 0
        sipush 1
        if_icmpgt L9
        iconst 1 
        goto L10
    L9: iconst 0 
    L10:ifeq L6
        sipush 1
        istore 100
        goto L7
    L6: iload 0
        iload 0
        sipush 1
        isub 
        invokestatic fatorial.fatorial(I)I 
        imul 
        istore 100
L7: L2: iload 100
        ireturn 
    }

    public static main([java/lang/String)V {
        getstatic java/lang/System.out java/io/PrintStream
        ldc "Introduza numero inteiro: "
        invokevirtual java/io/PrintStream.print(java/lang/String)V

        invokestatic java/lang/System.console()java/io/Console
        invokevirtual java/io/Console.readLine()java/lang/String
        invokestatic java/lang/Integer.parseInt(java/lang/String)I
        putstatic fatorial.numero I

        getstatic java/lang/System.out java/io/PrintStream
        invokevirtual java/io/PrintStream.println()V

        getstatic java/lang/System.out java/io/PrintStream
        ldc "O fatorial de "
        invokevirtual java/io/PrintStream.print(java/lang/String)V

        getstatic java/lang/System.out java/io/PrintStream
        getstatic fatorial.numero I
        invokevirtual java/io/PrintStream.print(I)V

        getstatic java/lang/System.out java/io/PrintStream
        ldc " e: "
        invokevirtual java/io/PrintStream.print(java/lang/String)V

        getstatic java/lang/System.out java/io/PrintStream
        getstatic fatorial.numero I
        invokestatic fatorial.fatorial(I)I 
        invokevirtual java/io/PrintStream.print(I)V

        getstatic java/lang/System.out java/io/PrintStream
        invokevirtual java/io/PrintStream.println()V

        return
    }
}

Enfim, o fim

Aqui chegamos ao final desta jornada de aprendizado com este projeto.

Algumas coisas interessantes da área de compiladores podem ser exploradas com este projeto (como otimização de código gerado). Quem sabe em futuro breve iniciamos uma nova série com otimizações :-)

Código completo do projeto

O repositório com o código completo do projeto e a sua documentação está aqui.

Lendo dados da entrada padrão (stdin)

Alex Sandro Garzão — Wed, 07 Aug 2024 00:01:05 +0000

Na última postagem foi abordado contextos (do parser) e sentenças aninhadas. Nesta publicação vamos falar sobre as alterações necessárias para possibilitar a leitura de dados da entrada padrão (stdin), isso utilizando a função read/readln do Pascal.

Lendo dados de stdin (entrada padrão)

Standard input (stdin) é o stream do qual um programa lê seus dados de entrada. Até o momento tínhamos suporte ao stdout (saída padrão) apenas.

Neste commit foi implementado um programa em Java para entendermos como a JVM lida com stdin:

public class InputData {
    public static String name;
    public static int age;

    public static void main(String[] args) {
        name = System.console().readLine();
        age = Integer.parseInt(System.console().readLine());
        System.out.println("You entered string " + name);
    }

Quando desassemblamos o arquivo class obtemos o assembly abaixo. Trechos irrelevantes foram omitidos, bem como o trecho original (em Java) que deu origem ao assembly foi inserido com ";;":

 1: public class InputData {
 2:     ;; public static String name;
 3:     public static name java/lang/String
 4: 
 5:     ;; public static int age;
 6:     public static age I
 7:
 8:     public static main([java/lang/String)V {
 9:         ;; name = System.console().readLine();
10:         invokestatic java/lang/System.console()java/io/Console
11:         invokevirtual java/io/Console.readLine()java/lang/String
12:         putstatic InputData.name java/lang/String
13:
14:         ;; age = Integer.parseInt(System.console().readLine());
15:         invokestatic java/lang/System.console()java/io/Console
16:         invokevirtual java/io/Console.readLine()java/lang/String
17:         invokestatic java/lang/Integer.parseInt(java/lang/String)I
18:         putstatic InputData.age I
19:
20:         ;; System.out.println("You entered string " + name);
21:         getstatic java/lang/System.out java/io/PrintStream
22:         getstatic InputData.name java/lang/String
23:         invokedynamic makeConcatWithConstants(java/lang/String)java/lang/String {
                invokestatic java/lang/invoke/StringConcatFactory.makeConcatWithConstants(java/lang/invoke/MethodHandles$Lookup, java/lang/String, java/lang/invoke/MethodType, java/lang/String, [java/lang/Object)java/lang/invoke/CallSite
                ["You entered string "]
            }
24:
25:         invokevirtual java/io/PrintStream.println(java/lang/String)V
26:
27:         return
    }
}

Com este exemplo foi possível identificar que para ler dados da stdin era necessário utilizar a instrução System.console().readLine() (linhas 11 e 16). E como readLine() retorna uma string, para lermos números era necessário converter com o uso da função Integer.parseInt (linha 17).

Dito isso, a partir do programa Pascal abaixo:

program NameAndAge;
var
    myname: string;
    myage: integer;
begin
    write('What is your name? '); readln(myname);
    write('How old are you? '); readln(myage);
    writeln;
    writeln('Hello ', myname);
    writeln('You are ', myage, ' years old');
end.

O POJ foi ajustado para gerar o seguinte JASM:

// Code generated by POJ 0.1
public class name_and_age {
    ;; var myname: string;
    public static myname java/lang/String

    ;; var myage: integer;
    public static myage I

    ;; procedure main
    public static main([java/lang/String)V {
        ;; write('What is your name? ');
        getstatic java/lang/System.out java/io/PrintStream
        ldc "What is your name? "
        invokevirtual java/io/PrintStream.print(java/lang/String)V

        ;; readln(myname);
        invokestatic java/lang/System.console()java/io/Console
        invokevirtual java/io/Console.readLine()java/lang/String
        putstatic name_and_age.myname java/lang/String

        ;; write('How old are you? ');
        getstatic java/lang/System.out java/io/PrintStream
        ldc "How old are you? "
        invokevirtual java/io/PrintStream.print(java/lang/String)V

        ;; readln(myage);
        invokestatic java/lang/System.console()java/io/Console
        invokevirtual java/io/Console.readLine()java/lang/String
        invokestatic java/lang/Integer.parseInt(java/lang/String)I
        putstatic name_and_age.myage I

        ;; writeln;
        getstatic java/lang/System.out java/io/PrintStream
        invokevirtual java/io/PrintStream.println()V

        ;; writeln('Hello ', myname);
        getstatic java/lang/System.out java/io/PrintStream
        ldc "Hello "
        invokevirtual java/io/PrintStream.print(java/lang/String)V
        getstatic java/lang/System.out java/io/PrintStream
        getstatic name_and_age.myname java/lang/String
        invokevirtual java/io/PrintStream.print(java/lang/String)V
        getstatic java/lang/System.out java/io/PrintStream
        invokevirtual java/io/PrintStream.println()V

        ;; writeln('You are ', myage, ' years old');
        getstatic java/lang/System.out java/io/PrintStream
        ldc "You are "
        invokevirtual java/io/PrintStream.print(java/lang/String)V
        getstatic java/lang/System.out java/io/PrintStream
        getstatic name_and_age.myage I
        invokevirtual java/io/PrintStream.print(I)V
        getstatic java/lang/System.out java/io/PrintStream
        ldc " years old"
        invokevirtual java/io/PrintStream.print(java/lang/String)V
        getstatic java/lang/System.out java/io/PrintStream
        invokevirtual java/io/PrintStream.println()V

        return
    }
}

Este commit implementa as alterações necessárias no parser do POJ.

Aqui está o PR completo.

Próximos passos

Na próxima publicação vamos concluir um dos objetivos deste projeto: cálculo do fatorial de forma recursiva.

Código completo do projeto

O repositório com o código completo do projeto e a sua documentação está aqui.

Sentenças aninhadas

Alex Sandro Garzão — Wed, 31 Jul 2024 00:00:19 +0000

Na última postagem resolvemos alguns bugs importantes, em especial na geração do assembly. Nesta publicação vamos falar sobre como gerar corretamente o assembly para sentenças aninhadas.

Contextos

Uma das funcionalidades necessárias para lidarmos corretamente com sentenças aninhadas é a possibilidade de termos vários contextos no parser. Isso ocorre porque se o parser assume um contexto apenas, sentenças de controle aninhadas que geram labels e saltos (como if, for, while e repeat) gerariam o endereçamento de saltos incorretamente.

Existem duas formas de lidar com contextos, que são:

Parser recursivo
Empilhar contextos

Usualmente eu utilizaria a abordagem de parser recursivo. Porém, para podermos implementar um parser recursivo com o ANTLR, pela forma como a gramática foi estruturada no POJ, seria necessário injetar código diretamente na gramática, uma abordagem pouco recomendada. Em função disso optou-se pela abordagem de empilhar contextos.

Como já existia uma implementação de pilha que monitorava os tipos que o parser empilhou/desempilhou na JVM, para não ter que criar mais uma pilha para um tipo específico, optou-se por criar uma stack genérica neste PR. Além de poder aproveitar esta implementação posteriormente, ainda posso refatorar o código antigo e remover a stack específica existente.

Neste commit o parser foi alterado para empilhar/desempilhar corretamente os contextos das funções. Basicamente no início do parser de uma função o contexto é empilhado, e no seu final o contexto é desempilhado.

Sentenças aninhadas

Sentenças de controle como if, for, while e repeat funcionavam corretamente. Porém, caso houvesse sentenças aninhadas, o POJ não guardava contexto e acaba por gerar erroneamente os labels e saltos. Aqui e aqui foi abordado como funciona a geração do assembly para estas sentenças de controle.

Para o exemplo abaixo, que contém um if aninhado dentro de outro, o POJ gerava erroneamente os labels e saltos necessários:

program NestedIfs;
begin
  if (1 > 2) then
    if (2 > 3 ) then
      writeln('1 > 2 and 2 > 3')
    else
      writeln('1 > 2 and 2 <= 3')
  else
    writeln('1 <= 2');
end.

Este bug era conhecido e eu optei por resolvê-lo no momento em que o parser tivesse suporte a contextos.

Neste commit foi criado a estrutura LabelsContext contendo os seguintes labels:

Else: necessário para o caso do if com else;
NextStatement: contém o label da próxima instrução;
IterationStart: indica o teste da estrutura de repetição no caso de while, repeat e for.

Para validar a correta geração do assembly foram criados testes para validar if's aninhados, repeat's aninhados, while's aninhados bem como for's aninhados. Aqui foi criado os testes para validar a geração do assembly no caso de funções recursivas. Além disso foi necessário atualizar o assembly esperado de todos os testes existentes. Por fim, neste PR foi atualizado o parser para utilizar a nova estrutura de contextos.

Aqui está o PR completo destas modificações. Aqui temos o commit contendo as mudanças para o correto funcionamento da sentença if, aqui o commit referente ao repeat, aqui o commit referente ao while e aqui o commit referente ao for.

Próximos passos

Na próxima publicação vamos falar sobre entrada de dados. Agora falta pouco para concluirmos um dos objetivos deste projeto: ler um número da entrada padrão e calcular o seu fatorial.

Código completo do projeto

O repositório com o código completo do projeto e a sua documentação está aqui.

Resolução de alguns bugs

Alex Sandro Garzão — Tue, 23 Jul 2024 19:12:12 +0000

Na última postagem implementamos o suporte às functions do Pascal.

Nesta publicação vamos falar sobre coisas bacanas? Nem tanto rsrsrs. Desta vez só vamos falar de bugs mesmo :-)

Bug referente aos parâmetros passados ao programa pela linha de comando

Quando implementei a declaração de variáveis eu não atentei para o fato de que, na JVM, a primeira variável na função principal é o args, um array que contém os argumentos passados para o programa. Com isso neste PR eu reservo a primeira posição implicitamente para args.

Bug ao lidar com variáveis locais e globais

Como os programas em Pascal de teste continham apenas variáveis globais eu não havia notado um erro grave na geração do JASM. No momento em que criei programas que continham variáveis globais e locais percebi que algo de errado não estava certo rsrsrs.

A partir do programa Pascal abaixo:

program global_var_declaration;
var
    globalvar : integer;
begin
    globalvar := 123;
    write (globalvar);
end.

O POJ gerava o seguinte JASM:

// Code generated by POJ 0.1
public class global_var_declaration {
    public static main([java/lang/String)V {
        ;; globalvar := 123;
        bipush 123
        istore 1

        ;; write (globalvar);
        getstatic java/lang/System.out java/io/PrintStream
        iload 1
        invokevirtual java/io/PrintStream.print(I)V

        return
    }
}

Para tentar identificar o problema criei um programa em Java equivalente ao programa em Pascal acima:

public class GlobalVarDeclaration {
    public static int globalVar;

    public static void main(String[] args) {
        globalVar = 123;
        System.out.println(globalVar);
    }
}

Quando desassemblei o class eu obtive o seguinte assembly:

 1: public class GlobalVarDeclaration {
 2:     public static globalVar I
 3:
 4:     public static main([java/lang/String)V {
 5:         bipush 123
 6:         putstatic GlobalVarDeclaration.globalVar I
 7:
 8:         getstatic java/lang/System.out java/io/PrintStream
 9:         getstatic GlobalVarDeclaration.globalVar I
10:         invokevirtual java/io/PrintStream.println(I)V
11:
12:         return
13:     }
14: }

Neste momento percebi a declaração "public static globalVar I" (linha 2) e as instruções putstatic (linha 6) e getstatic (linha 9). O esperado eram as instruções astore e istore utilizadas pelo POJ até o momento. Lendo a documentação da JVM percebi que o POJ estava declarando as variáveis globais como se fossem variáveis locais de uma função para a JVM :-D

Enfim, até o momento o POJ estava usando (erroneamente) os opcodes aload/iload/astore/istore para variáveis globais, mas o correto seria declarar as variáveis como públicas (como na linha 2) e utilizar o getstatic/putstatic.

Com isso o código foi refatorado aqui para que a tabela de símbolos consiga lidar com declarações locais e globais. E aqui o código foi refatorado para que a tabela de símbolos consiga gerar as instruções corretas para as variáveis locais e globais.

A geração de código JASM foi alterada aqui para lidar com a nova tabela de símbolos bem como limpar as declarações locais após o término de uma função ou procedimento.

Com isso, a partir do programa Pascal abaixo:

program GlobalVarDeclaration;
var
    globalvar : integer;
begin
    globalvar := 123;
    write (globalvar);
end.

O POJ passou a gerar corretamente o seguinte JASM:

// Code generated by POJ 0.1
public class global_var_declaration {
    public static globalvar I

    public static main([java/lang/String)V {
        ;; globalvar := 123;
        bipush 123
        putstatic global_var_declaration.globalvar I

        ;; write (globalvar);
        getstatic java/lang/System.out java/io/PrintStream
        getstatic global_var_declaration.globalvar I
        invokevirtual java/io/PrintStream.print(I)V

        return
    }
}

Próximos passos

Na próxima publicação vamos falar sobre contextos e sentenças aninhadas.

Código completo do projeto

O repositório com o código completo do projeto e a sua documentação está aqui.

Suporte às funções do Pascal

Alex Sandro Garzão — Sun, 07 Jul 2024 17:20:08 +0000

Na última postagem tivemos algumas melhorias na captura de erros, suporte a operadores relacionais para o tipo string e a possibilidade de definir (e utilizar) as procedures do Pascal.

Nesta publicação vamos abordar o suporte às funções (functions) do Pascal. Falta pouco para podemos concluir o último objetivo do projeto: ler um número da entrada padrão e calcular o seu fatorial.

Suporte às funções (functions) do Pascal

Até o momento tínhamos como definir e invocar às procedures do Pascal. A partir deste PR é possível também definir bem como invocar as functions do Pascal.

Neste commit foi implementado um programa em Java para entender como a JVM lida com a definição e a chamada de funções. A partir do programa Java abaixo:

public class FunctionCall {
    public static void main(String[] args) {
        System.out.println("Hello from main!");
        System.out.println(myMethod());
    }

    static String myMethod() {
        return "Hello from myMethod!";
    }
}

Quando desassemblamos o class obtemos o seguinte assembly:

1:  public class FunctionCall {
2:      public static main([java/lang/String)V {
3:          getstatic java/lang/System.out java/io/PrintStream
4:          ldc "Hello from main!"
5:          invokevirtual java/io/PrintStream.println(java/lang/String)V
6:
7:          getstatic java/lang/System.out java/io/PrintStream
8:          invokestatic FunctionCall.myMethod()java/lang/String
9:          invokevirtual java/io/PrintStream.println(java/lang/String)V
10:
11:         return
12:     }
13:
14:     static myMethod()java/lang/String {
15:         ldc "Hello from myMethod!"
16:
17:         areturn
18:     }
19: }

Com este exemplo foi possível identificar que:

Para invocar um método a JVM utilizou a instrução "invokestatic FunctionCall.myMethod()java/lang/String" (linha 8) onde:
- invokestatic é a instrução que recebe como argumento a assinatura completa do método a ser chamado;
- FunctionCall é o nome da classe;
- myMethod()java/lang/String é assinatura completa do método com seus parâmetros (neste exemplo nenhum) e o tipo de retorno (neste exemplo java/lang/String);
Instrução areturn (linha 17) encerra a função e deixa na pilha a string de retorno.

Dito isso, a partir do programa Pascal abaixo:

program function_call_wo_params;

function myfunction : string;
begin
    myfunction := 'Hello from myfunction!';
end;

begin
    writeln('Hello from main!');
    writeln(myfunction());
end.

O POJ foi ajustado para gerar o seguinte JASM:

// Code generated by POJ 0.1
public class function_call_wo_params {
    ;; function myfunction : string;
    static myfunction()java/lang/String {
        ldc "Hello from myfunction!"
        astore 100   ;; Posição 100 guarda o retorno da função
        aload 100    ;; Empilha o retorno da função
        areturn      ;; Deixa "Hello from myfunction!" na pilha
    }

    ;; procedure principal (main)
    public static main([java/lang/String)V {
        ;; writeln('Hello from main!');
        getstatic java/lang/System.out java/io/PrintStream
        ldc "Hello from main!"
        invokevirtual java/io/PrintStream.print(java/lang/String)V
        getstatic java/lang/System.out java/io/PrintStream
        invokevirtual java/io/PrintStream.println()V

        ;; writeln(myfunction());
        getstatic java/lang/System.out java/io/PrintStream
        invokestatic function_call_wo_params.myfunction()java/lang/String 
        invokevirtual java/io/PrintStream.print(java/lang/String)V
        getstatic java/lang/System.out java/io/PrintStream
        invokevirtual java/io/PrintStream.println()V

        return
    }
}

Os mais atentos devem ter notado o "astore 100" acima e pensado:

Por que guardar o retorno da função em uma variável local? Isso se deve ao fato de que em Pascal o valor de retorno de uma função pode ser definido N vezes durante a função, mas só podemos empilhar um resultado na JVM;
Por que na posição 100? As variáveis locais de uma função ou procedimento iniciam na posição 0 então arbitrariamente foi escolhido a posição 100 para guardar o retorno;
Mas não seria possível otimizar para que neste exemplo somente fosse gerado a instrução ldc "Hello from myfunction!" seguida da instrução areturn? Sim, seria, mas o POJ não implementa a fase de otimizações existente em compiladores de mercado, algo que pode ser implementado futuramente.

Este commit implementa o suporte ao tipo "function" na tabela de símbolos e no parser.

Nos exemplos acima as funções não tinham argumentos. Neste commit foi implementado o resultado esperado para funções com argumentos. Com isso a partir do programa Pascal abaixo:

program function_call_with_two_params;

function addvalues(value1, value2: integer) : integer;
begin
    addvalues := value1 + value2;
end;

begin
    writeln('2+4=', addvalues(2, 4));
end.

O POJ gerou corretamente o seguinte JASM:

// Code generated by POJ 0.1
public class function_call_with_two_params {
    ;; function addvalues(value1, value2: integer) : integer;
    static addvalues(I, I)I {
        ;; addvalues := value1 + value2;
        iload 0
        iload 1
        iadd 
        istore 100
        iload 100

        ireturn 
    }

    ;; procedure main
    public static main([java/lang/String)V {
        ;; writeln('2+4=', ...);
        getstatic java/lang/System.out java/io/PrintStream
        ldc "2+4="
        invokevirtual java/io/PrintStream.print(java/lang/String)V
        getstatic java/lang/System.out java/io/PrintStream

        ;; aqui código para invocar addvalues(2, 4)
        sipush 2
        sipush 4
        invokestatic function_call_with_two_params.addvalues(I, I)I 

        ;; aqui código para invocar writeln com retorno addvalues
        invokevirtual java/io/PrintStream.print(I)V
        getstatic java/lang/System.out java/io/PrintStream
        invokevirtual java/io/PrintStream.println()V

        return
    }
}

Próximos passos

Nas próximas publicações vamos falar sobre contextos, bugs encontrados, sentenças aninhadas, entrada de dados e concluir o último dos objetivos deste projeto: cálculo do fatorial de forma recursiva.

Código completo do projeto

O repositório com o código completo do projeto e a sua documentação está aqui.

Captura de erros, operadores relacionais para string e procedures

Alex Sandro Garzão — Sun, 26 May 2024 19:32:08 +0000

Para quem não está acompanhando, o POJ (Pascal on the JVM) é um compilador que transforma um subset de Pascal para JASM (Java Assembly) de forma que possamos usar a JVM como ambiente de execução.

Na última postagem foi adicionado suporte às estruturas de repetição repeat, while e for.

Melhorias na saída de erros

Sempre que existia um erro léxico, sintático ou semântico no código Pascal, o POJ apenas listava os erros gerados sem nenhum tipo de abstração. Além disso, a compilação seguia normalmente.

Para implementar melhorias, as seguintes modificações foram realizadas:

Neste commit o código foi alterado para que a análise léxica, sintática e semântica retornem os erros encontrados;
Neste commit foi criada uma classe customizada de erros para ser utilizada pelo runtime do ANTLR. Com isso podemos obter os erros encontrados pelo parser bem como realizar o tratamento adequado;
Neste commit o código principal do POJ obtém os possíveis erros gerados, lista eles e aborta o processo de compilação quando necessário;
Neste commit foram introduzidos programas em Pascal inválidos bem como a saída de erros esperada. Com isso os testes automatizados, além de validarem a saída esperada de programas válidos (Java Assembly), também verificam a saída de erros esperada a partir de programas inválidos (lista de erros).

Aqui está o PR completo.

Operadores relacionais para o tipo String

Até o momento tínhamos o suporte aos operadores relacionais apenas para o tipo inteiro (integer).

Neste commit foi implementado um programa em Java para entendermos como a JVM lida com os operadores relacionais para o tipo String. A partir do programa Java abaixo:

public class IfWithStrings {
   public static void main(String[] args) {
      String v1 = "aaa";
      String v2 = "bbb";
      if (v1.compareTo(v2) > 0)
         System.out.println("v1>v2");
      else
         System.out.println("v1<=v2");
   }
}

Quando desassemblamos o arquivo class obtemos o assembly abaixo. Trechos irrelevantes foram omitidos, bem como o trecho original (em Java) que deu origem ao assembly foi inserido com ";;":

public class IfWithStrings {

    ;; public static void main(String[] args)
    public static main([java/lang/String)V {

        ;; String v1 = "aaa";
        ldc "aaa"
        astore 1

        ;; String v2 = "bbb";
        ldc "bbb"
        astore 2

        ;; v1.compareTo(v2)
        aload 1
        aload 2
        invokevirtual java/lang/String.compareTo(java/lang/String)I

        ;; if (v1.compareTo(v2) > 0)
        ifle label3

        ;; System.out.println("v1>v2");
        getstatic java/lang/System.out java/io/PrintStream
        ldc "v1>v2"
        invokevirtual java/io/PrintStream.println(java/lang/String)V
        goto label5

        ;; System.out.println("v1<=v2");
        label3:
        getstatic java/lang/System.out java/io/PrintStream
        ldc "v1<=v2"
        invokevirtual java/io/PrintStream.println(java/lang/String)V

        label5:
        return
    }
}

Com este exemplo foi possível identificar que para comparar duas strings a JVM obtém da pilha as strings e executa o método "compareTo" da classe String. Este método compara as strings e empilha o seguinte resultado:

-1, caso o 1o valor seja menor que o segundo;
0, caso os dois valores sejam iguais;
+1, caso o 2o valor seja maior que o primeiro.

Dito isso, a partir do programa Pascal abaixo:

program IfWithStrings;
begin
  if ( 'aaa' > 'bbb' ) then
    write('true')
  else
    write('false');
end.

O POJ foi ajustado para gerar o seguinte JASM:

// Code generated by POJ 0.1
public class if_with_strings {
    public static main([java/lang/String)V {

        ;; if ( 'aaa' > 'bbb' ) then
        ldc "aaa"
        ldc "bbb"
        invokevirtual java/lang/String.compareTo(java/lang/String)I
        iflt L3
        iconst 1 
        goto L4

    L3: iconst 0 

    L4: ifeq L1

        ;; write('true')
        getstatic java/lang/System.out java/io/PrintStream
        ldc "true"
        invokevirtual java/io/PrintStream.print(java/lang/String)V
        goto L2

    L1: ;; write('true')
        getstatic java/lang/System.out java/io/PrintStream
        ldc "false"
        invokevirtual java/io/PrintStream.print(java/lang/String)V

    L2: return
    }
}

Este commit implementa a chamada ao método String.compareTo bem como a geração do teste (iflt) citados acima.

Aqui está o PR completo.

Chamada de procedures

Até o momento tínhamos que implementar todo o código no bloco principal (main) do programa em Pascal. Neste PR foi implementado o suporte à chamada de procedures. Reforçando que, em Pascal, uma procedure é o equivalente a uma function que não retorna um resultado.

Neste commit foi implementado um programa em Java para entender como a JVM lida com a chamada de procedures (funções sem retorno). A partir do programa Java abaixo:

public class ProcedureCall {
   public static void main(String[] args) {
      System.out.println("Hello from main!");
      myMethod();
   }

   static void myMethod() {
      System.out.println("Hello from myMethod!");
   }
}

Quando desassemblamos o class obtemos o seguinte assembly:

public class ProcedureCall {

    ;; public static void main(String[] args)
    public static main([java/lang/String)V {

        ;; System.out.println("Hello from main!");
        getstatic java/lang/System.out java/io/PrintStream
        ldc "Hello from main!"
        invokevirtual java/io/PrintStream.println(java/lang/String)V

        ;; myMethod();
        invokestatic ProcedureCall.myMethod()V

        return
    }

    ;; static void myMethod()
    static myMethod()V {

        ;; System.out.println("Hello from myMethod!");
        getstatic java/lang/System.out java/io/PrintStream
        ldc "Hello from myMethod!"
        invokevirtual java/io/PrintStream.println(java/lang/String)V

        return
    }
}

Com este exemplo foi possível identificar que para invocar uma procedure a JVM utiliza a instrução "invokestatic ProcedureCall.myMethod()V" onde:

invokestatic é a instrução que recebe como argumento a assinatura completa do método a ser chamado;
ProcedureCall é o nome da classe;
myMethod()V é assinatura completa do método com seus parâmetros (neste exemplo nenhum) e o tipo de retorno (neste exemplo V - void - que indica nenhum).

Dito isso, a partir do programa Pascal abaixo:

program procedure_call_wo_params;

procedure myprocedure;
begin
    write('Hello from myprocedure!');
end;

begin
    write('Hello from main!');
    myprocedure();
end.

O POJ foi ajustado para gerar o seguinte JASM:

// Code generated by POJ 0.1
public class procedure_call_wo_params {

    ;; procedure myprocedure;
    static myprocedure()V {

        ;; write('Hello from myprocedure!');
        getstatic java/lang/System.out java/io/PrintStream
        ldc "Hello from myprocedure!"
        invokevirtual java/io/PrintStream.print(java/lang/String)V

        return
    }

    ;; bloco principal (main)
    public static main([java/lang/String)V {

        ;; write('Hello from main!');
        getstatic java/lang/System.out java/io/PrintStream
        ldc "Hello from main!"
        invokevirtual java/io/PrintStream.print(java/lang/String)V

        ;; myprocedure();
        invokestatic procedure_call_wo_params.myprocedure()V 

        return
    }
}

Este commit implementa o suporte ao tipo "procedure" na tabela de símbolos.

Este commit implementa o suporte a geração do assembly correto. Para tal, o POJ precisa lidar com contextos (procedure sendo interpretada) para saber quando está interpretando o código de um procedimento ou do bloco principal.

Passagem de argumentos para o procedimento

Até então tínhamos a chamada de procedimentos funcional, mas sem argumentos. Neste commit foi implementado um programa em Java para identificar como a JVM lida com a passagem de argumentos. No exemplo é possível ver que, assim como com outros opcodes, no início de sua execução o procedimento retira seus argumentos da pilha. Com isso basta empilhar os argumentos antes de invocar o procedimento.

Dito isso, a partir do programa Pascal abaixo:

program procedure_call_add_numbers;

procedure add(value1, value2: integer);
begin
    write(value1 + value2);
end;

begin
    add(4, 6);
end.

O POJ gera o seguinte JASM:

// Code generated by POJ 0.1
public class procedure_call_add_numbers {

    ;; procedure add(value1, value2: integer);
    static add(I, I)V {

        ;; write(value1 + value2);
        getstatic java/lang/System.out java/io/PrintStream
        iload 0 ;; carrega o parâmetro 0 (value1)
        iload 1 ;; carrega o parâmetro 1 (value2)
        iadd 
        invokevirtual java/io/PrintStream.print(I)V

        return
    }

    ;; Bloco principal (main)
    public static main([java/lang/String)V {
        ;; add(4, 6);
        sipush 4
        sipush 6
        invokestatic procedure_call_add_numbers.add(I, I)V 

        return
    }
}

Para o correto suporte à chamada com argumentos foi necessário acrescentar na tabela de símbolos os tipos dos argumentos dos procedimentos. Por sua vez, para a correta invocação dos procedimentos, o parser teve que validar bem como gerar o assembly corretamente conforme a assinatura do procedimento.

Aqui está o PR completo.

Próximos passos

Na próxima publicação vamos falar sobre funções, entrada de dados e, se possível, concluir um dos objetivos deste projeto: cálculo do fatorial de forma recursiva.

Código completo do projeto

O repositório com o código completo do projeto e a sua documentação está aqui.

Estruturas de repetição: repeat, while e for

Alex Sandro Garzão — Fri, 12 Apr 2024 02:40:48 +0000

Na última postagem eu tinha mais algumas funcionalidades para comentar, mas para facilitar a compreensão achei mais prudente separar em mais de uma postagem.

Como estamos compilando para a JVM faz-se necessário detalhar o funcionamento de várias pontos desta incrível máquina virtual. Com isso em vários momentos eu detalho o funcionamento interno da JVM bem como algumas das suas instruções.

Declaração de variáveis

Apesar de importante, declaração de variáveis em Pascal não era a minha próxima meta, mas sim estruturas de controle como for, while e repeat. Mas, para podermos exemplificar e corretamente implementar estas estruturas, a declaração de variáveis torna-se essencial.

Após todo o aprendizado no desenvolvimento do POJ (todas as postagens estão aqui) foi relativamente fácil alterar o parser bem como gerar o assembly para declarar as variáveis em Java Assembly.

A partir do programa Pascal abaixo:

program VarDeclarations;
var
    msg1, msg2 : string;
begin
    msg1 := 'Message 1!';
    msg2 := 'Message 2!';
    writeln (msg1);
    writeln (msg2);
end.

O POJ gera o seguinte JASM:

// Code generated by POJ 0.1
public class var_declarations {
    public static main([java/lang/String)V {

        ;; msg1 := 'Message 1!';
        ldc "Message 1!"
        astore 1

        ;; msg2 := 'Message 2!';
        ldc "Message 2!"
        astore 2

        ;; writeln (msg1);
        getstatic java/lang/System.out java/io/PrintStream
        aload 1
        invokevirtual java/io/PrintStream.print(java/lang/String)V
        getstatic java/lang/System.out java/io/PrintStream
        invokevirtual java/io/PrintStream.println()V

        ;; writeln (msg2);
        getstatic java/lang/System.out java/io/PrintStream
        aload 2
        invokevirtual java/io/PrintStream.print(java/lang/String)V
        getstatic java/lang/System.out java/io/PrintStream
        invokevirtual java/io/PrintStream.println()V

        return
    }
}

Cabe aqui salientar que, para facilitar a compreensão, no exemplo acima as linhas iniciando com ";;" contém o trecho em Pascal que originou o JASM.

Em relação aos exemplos anteriores agora estamos utilizando duas novas instruções da JVM:

astore <N>: retira da pilha uma string e armazena no slot de variáveis N
aload <N>: carrega na pilha a string existente no slot de variáveis N

A alteração mais significativa é que agora o POJ gera uma tabela de símbolos compartilhada durante todo o processo de compilação.

Para quem tiver interesse, o PR que implementa a declaração de variáveis está aqui.

Estrutura de controle Repeat

De posse de todo o conhecimento obtido até aqui, e com os pré-requisitos para implementarmos as estruturas de repetição de Pascal (sentença if, operadores relacionais e booleanos), optamos por iniciar com a estrutura "Repeat Until" por ser a mais simples dentre as estruturas de repetição.

Abaixo temos a sintaxe do Repeat:

1:    repeat            
2:        <bloco código>
3:    until <condição>;

O POJ implementa o seguinte comportamento:

Na linha 1, ao reconhecer o token repeat, gera e emite um label (L1) que indica onde inicia o laço de repetição
Na linha 2 o bloco de código é traduzido para JASM
Na linha 3 a condição é avaliada e, caso seja válida (true) a execução salta para L1

Vamos a um exemplo que imprime os números de 10 até 19. A partir do programa Pascal abaixo:

program RepeatExample;
var
    i: integer;
begin
    i := 10;
    repeat
        writeln ('i=', i);
        i := i + 1;
    until i = 20;
end.

O POJ gera o seguinte JASM:

// Code generated by POJ 0.1
public class repeat_example {
    public static main([java/lang/String)V {

        ;; i := 10;
        sipush 10
        istore 1

    L1: ;; repeat
        ;; writeln ('i=', i);
        getstatic java/lang/System.out java/io/PrintStream
        ldc "i="
        invokevirtual java/io/PrintStream.print(java/lang/String)V
        getstatic java/lang/System.out java/io/PrintStream
        iload 1
        invokevirtual java/io/PrintStream.print(I)V
        getstatic java/lang/System.out java/io/PrintStream
        invokevirtual java/io/PrintStream.println()V

        ;; i := i + 1;
        iload 1
        sipush 1
        iadd 
        istore 1

        ;; until i = 20;
        iload 1
        sipush 20
        if_icmpne L2
        iconst 1 
        goto L3

    L2: iconst 0 

    L3: ifeq L1
        return
    }
}

Neste JASM não foram utilizadas novas instruções da JVM. Mais detalhes sobre estas instruções podem ser obtidas na postagem anterior.

Para quem tiver interesse o PR que implementa a estrutura Repeat está aqui.

Estrutura de controle While

Dando sequências às estruturas de controle, a próxima estrutura implementada foi a While.

A estrutura While pode ser vista como uma variação da Repeat, onde no caso do Repeat o teste é executado no final enquanto que no While o teste é executado no início. Repeat sempre executa o bloco de código pelo menos uma vez, enquanto que o While executa 0 ou mais vezes.

Abaixo temos a sintaxe do While:

1:    while <condição> do
2:    begin
3:        <bloco código>
4:    end;

O POJ implementa o seguinte comportamento:

Na linha 1, ao reconhecer o token while, executa os seguintes passos:
- gera e emite um label (L1) que indica onde está o condicional do while
- gera um label (L2) que indica o término do while
- avalia a condição e, caso seja inválida (false) a execução salta para L2
A linha 2 apenas indica o início do bloco
Na linha 3 o bloco de código é traduzido para JASM
Na linha 4 são executados os seguintes passos:
- a execução salta para L1
- emite o label L2

Vamos a um exemplo. A partir do programa Pascal abaixo:

program WhileExample;
var
    i: integer;
begin
    i := 10;
    while i < 20 do
    begin
        writeln ('i=', i);
        i := i + 1;
    end;
end.

O POJ gera o seguinte JASM:

// Code generated by POJ 0.1
public class while_example {
    public static main([java/lang/String)V {

        ;; i := 10;
        sipush 10
        istore 1

    L1: ;; while i < 20 do
        iload 1
        sipush 20
        if_icmpge L3
        iconst 1 
        goto L4

    L3: iconst 0 

    L4: ifeq L2

        ;; writeln ('i=', i);
        getstatic java/lang/System.out java/io/PrintStream
        ldc "i="
        invokevirtual java/io/PrintStream.print(java/lang/String)V
        getstatic java/lang/System.out java/io/PrintStream
        iload 1
        invokevirtual java/io/PrintStream.print(I)V
        getstatic java/lang/System.out java/io/PrintStream
        invokevirtual java/io/PrintStream.println()V

        ;; i := i + 1;
        iload 1
        sipush 1
        iadd 
        istore 1

        ;; end; (do while)
        goto L1

    L2: return
    }
}

Em comparação com os exemplos anteriores, não foram utilizadas novas instruções da JVM.

Para quem tiver interesse o PR que implementa a estrutura "While" está aqui.

Estrutura de controle For

Por ser considerada a mais complexa das estruturas de controle citadas nesta publicação (repeat, while e for), propositadamente o For foi deixado por último.

Abaixo temos a sintaxe do For:

1:  for <var> := <início> to <fim> do
2:  begin
3:      <bloco código>
4:  end;

O POJ implementa o seguinte comportamento:

Na linha 1, ao reconhecer o token for, são executados os seguintes passos:
- inicializa <var> com o valor <início>
- gera e emite um label (L1) que indica onde está o condicional do for
- gera um label (L2) que indica o término do for
- avalia se <var> é <= a <fim> e, caso seja inválida (false) a execução salta para o label L2
A linha 2 apenas indica o início do bloco
Na linha 3 o bloco de código é traduzido para JASM
Na linha 4 são executados os seguintes passos:
- incrementa <var> em 1 unidade
- a execução salta para o label L1
- emite o label L2

Para a sua correta implementação o for engloba as seguintes tarefas:

inicializar a variável definida no for
incrementar/decrementar esta variável automaticamente no final do laço
validar no início da sentença se o bloco deve ser executado

Vamos ao exemplo. A partir do programa Pascal abaixo:

program ForExample;
var
    i: integer;
begin
    for i := 10 to 19 do
    begin
        writeln ('inc i=', i);
    end;
end.

O POJ gera o seguinte JASM:

// Code generated by POJ 0.1
public class for_example {
    public static main([java/lang/String)V {

        ;; i := 10
        sipush 10
        istore 1

    L1: ;; i <= 19 ?
        iload 1
        sipush 19
        if_icmpgt L2

        ;; writeln ('inc i=', i);
        getstatic java/lang/System.out java/io/PrintStream
        ldc "inc i="
        invokevirtual java/io/PrintStream.print(java/lang/String)V
        getstatic java/lang/System.out java/io/PrintStream
        iload 1
        invokevirtual java/io/PrintStream.print(I)V
        getstatic java/lang/System.out java/io/PrintStream
        invokevirtual java/io/PrintStream.println()V

        ;; i := i + 1
        iload 1
        sipush 1
        iadd 
        istore 1

        ;; end; (do for)
        goto L1

    L2: return
    }
}

Para quem tiver interesse o PR que implementa a estrutura For está aqui.

Maiores informações

O repositório com o código completo do projeto e a sua documentação está aqui.

Novos operadores e a sentença if

Alex Sandro Garzão — Thu, 04 Apr 2024 23:48:53 +0000

A sensação que tenho é que nestas últimas 2 semanas o projeto evoluiu muito. Espero que gostem :-)

Tenho várias novidades, mas aqui vou comentar apenas sobre os novos operadores implementados (multiplicação, divisão, relacionais e booleanos) e a sentença if.

Após resolver a pegadinha da precedência de operadores existente na gramática original (mais informações aqui) foi relativamente fácil implementar os novos operadores. Além do que escrevi vários exemplos em Java para analisar os opcodes gerados pelo JavaC.

Abaixo detalharei mais sobre o JASM (Java Assembly) gerado pelo POJ.

Operadores de multiplicação e divisão

Após o aprendizado gerando o JASM para soma e subtração, foi relativamente fácil gerar o assembly para multiplicação e divisão.

A partir do programa Pascal abaixo:

program MulDivIntegers;
begin
  writeln (8*4/2);
end.

O POJ gera o seguinte JASM:

// Code generated by POJ 0.1
public class mul_div_integers {
    public static main([java/lang/String)V {
        getstatic java/lang/System.out java/io/PrintStream
        ;; multiplica 8 * 4
        sipush 8
        sipush 4
        imul
        ;; divide o resultado por 2
        sipush 2
        idiv
        ;; desempilha e imprime um inteiro
        invokevirtual java/io/PrintStream.println(I)V
        return
    }
}

Vale aqui relembrar que a JVM é uma stack based machine, ou seja, é uma máquina baseada em pilha. Isso quer dizer que suas instruções utilizam uma pilha para realizar as suas operações.

No assembly acima getstatic, sipush, imul, idiv, invokevirtual e return são mnemônicos do Java Assembly. Possuem a seguinte finalidade:

getstatic: obtém uma referência de um método estático de uma classe
sipush <N>: empilha o inteiro N
imul: desempilha dois inteiros e empilha a multiplicação destes valores
idiv: desempilha dois inteiros e empilha a divisão destes valores
invokevirtual: desempilha dois valores (método a ser invocado e parâmetro) e executa
return: finaliza a execução do método

Na prática o par getstatic/invokevirtual serve para invocar o println, responsável por enviar dados para a saída padrão. O "I" em println(I) indica que será exibido um inteiro. E para saber qual método println invocar, o POJ precisa fazer o tracking dos tipos de dados que estão sendo empilhados/desempilhados na JVM.

Na tabela abaixo é possível ver as instruções geradas a partir da expressão "8*4/2" bem como o estado da pilha da JVM após a execução de cada instrução:

Instrução	Estado pilha após instrução
sipush 8	[ 8 ]
sipush 4	[ 8, 4 ]
imul	[ 32 ]
sipush 2	[ 32, 2 ]
idiv	[ 16 ]

No final da execução a pilha contém o resultado esperado de 8*4/2: 16.

Operadores relacionais e a sentença if

Para corretamente implementarmos os operadores relacionais (>, <, >=, <=, = e <>) foi necessário introduzir as instruções da JVM relacionadas à condicionais (ifs) e saltos (goto e labels). Sim, o famigerado goto existe na JVM, e faz todo sentido existir :-)

Vamos a um exemplo com if/then/else. A partir do programa Pascal abaixo:

program IfWithIntegers;
begin
  if ( 111 < 222 ) then
    write('true')
  else
    write('false');
end.

O POJ gera o seguinte JASM:

// Code generated by POJ 0.1
public class if_with_integers {
    public static main([java/lang/String)V {
        ;; se 111 >= 222 salta para L1
        sipush 111
        sipush 222
        if_icmpge L1
        ;; imprime true
        getstatic java/lang/System.out java/io/PrintStream
        ldc "true"
        invokevirtual java/io/PrintStream.print(java/lang/String)V
        goto L2
    L1: ;; imprime false
        getstatic java/lang/System.out java/io/PrintStream        
        ldc "false"
        invokevirtual java/io/PrintStream.print(java/lang/String)V
    L2: return
    }
}

Em relação ao exemplo anterior agora estamos utilizando novas instruções:

if_icmpge <label>: desempilha dois inteiros e salta para o label indicado se o primeiro valor for maior ou igual ao segundo
labels: no exemplo acima "L1:" e "L2:"
goto <label>: salta para o label indicado

A instrução if_icmpge faz parte de um conjunto amplo de instruções de teste e salto. O "ge" (de if_icmpge) é a abreviatura de "greater or equal". Outras variações são gt (greater than), eq (equal), ne (not equal), lt (less than) e le (less or equal).

Na tabela abaixo é possível ver as instruções geradas a partir do assembly acima bem como o estado da pilha da JVM após a execução de cada instrução:

Label	Instrução	Estado pilha após instrução
	sipush 111	[ 111 ]
	sipush 222	[ 111, 222 ]
	if_icmpge L1	[ ]
	getstatic ...	[ getstatic ]
	ldc "true"	[ getstatic, "true" ]
	invokevirtual ...
	goto L2
L1	~~getstatic ...~~
	~~ldc "false"~~
	~~invokevirtual ...~~
L2	return

As instruções ~~marcadas desta forma~~ não são executadas durante o fluxo de execução deste programa.

No final da execução o programa exibe a saída esperada: "true".

Vale ressaltar que a condição utilizada na geração do assembly (ge) é a inversa do programa em pascal (<). Esta técnica facilita a geração do assembly para os casos onde a sentença if somente tem o então (then), sem o senão (else).

Vamos a um exemplo com if/then (sem o else). A partir do programa Pascal abaixo:

program IfWithIntegers;
begin
  if ( 111 < 222 ) then
    write('true');
end.

O POJ gera o seguinte JASM:

// Code generated by POJ 0.1
public class if_with_integers {
    public static main([java/lang/String)V {
        ;; se 111 >= 222 salta para L1
        sipush 111
        sipush 222
        if_icmpge L1
        ;; imprime true
        getstatic java/lang/System.out java/io/PrintStream
        ldc "true"
        invokevirtual java/io/PrintStream.print(java/lang/String)V
        goto L2
  L1:L2:return
    }
}

Os mais atentos podem ter notado que o último goto (goto L2) é desnecessário. O código gerado está funcionalmente correto, apesar de não otimizado. Não só esta otimização bem como várias outras podem ser implementadas futuramente no POJ.

Operadores booleanos and e or

Para implementarmos os operadores booleanos (and e or) foi necessário introduzir as seguintes instruções:

iand: desempilha dois inteiros, executa o and e empilha o resultado
ior: desempilha dois inteiros, executa o or e empilha o resultado
ifeq <label>: desempilha o último valor, e caso igual a 0 salta para o label indicado
iconst <N>: empilha o inteiro N

Vamos a um exemplo. A partir do programa Pascal abaixo:

program IfWithAnd;
begin
  if ( 111 < 222) and ( 222 < 333 ) then
    write('true')
  else
    write('false');
end.

O POJ gera o seguinte JASM:

// Code generated by POJ 0.1
public class if_with_and {
    public static main([java/lang/String)V {
        sipush 111    ;; se 111 >= 222 salta para L1
        sipush 222
        if_icmpge L1
        iconst 1      ;; carrega true (1) na pilha
        goto L2
    L1: iconst 0      ;; carrega false (0) na pilha
    L2: sipush 222    ;; se 222 >= 333 salta para L3
        sipush 333
        if_icmpge L3
        iconst 1      ;; carrega true (1) na pilha
        goto L4
    L3: iconst 0      ;; carrega false (0) na pilha
    L4: iand          ;; se algum teste falhou salta para L5
        ifeq L5
        ;; imprime true
        getstatic java/lang/System.out java/io/PrintStream
        ldc "true"
        invokevirtual java/io/PrintStream.print(java/lang/String)V
        goto L6
    L5: ;; imprime false
        getstatic java/lang/System.out java/io/PrintStream
        ldc "false"
        invokevirtual java/io/PrintStream.print(java/lang/String)V
    L6: return
    }
}

Vale aqui ressaltar que a JVM não possui os tipos booleanos true e false. Estes tipos são emulados através dos inteiros 1 e 0, respectivamente. Para tal utilizamos as instruções "iconst 1" e "iconst 0".

Na tabela abaixo é possível ver as instruções geradas a partir do assembly acima bem como o estado da pilha da JVM após a execução de cada instrução:

Label	Instrução	Estado pilha após instrução
	sipush 111	[ 111 ]
	sipush 222	[ 111, 222 ]
	if_icmpge L1	[ ]
	iconst 1	[ 1 ]
	goto L2	[ 1 ]
L1	~~iconst 0~~
L2	sipush 222	[ 1, 222 ]
	sipush 333	[ 1, 222, 333 ]
	if_icmpge L3	[ 1 ]
	iconst 1	[ 1, 1 ]
	goto L4
L3	~~iconst 0~~
L4	iand	[ 1 ]
	ifeq L5	[ ]
	getstatic ...	[ getstatic ]
	ldc "true"	[ getstatic, "true" ]
	invokevirtual ...
	goto L6
L5	~~getstatic ...~~
	~~ldc "false"~~
	~~invokevirtual ...~~
L6	return

No final da execução o programa exibe a saída esperada: "true".

Operador booleano not

Até aqui falamos sobre os operadores and e or. E o operador not? Vamos a um exemplo.

A partir do programa Pascal abaixo:

program IfWithAndNot;
begin
  if not(( 111 < 222) and ( 222 < 333 )) then
    write('true')
  else
    write('false');
end.

O POJ gera o seguinte JASM:

// Code generated by POJ 0.1
public class if_with_and_not {
    public static main([java/lang/String)V {
        sipush 111   ;; se 111 >= 222 salta para L1
        sipush 222
        if_icmpge L1
        iconst 1     ;; carrega true (1) na pilha
        goto L2
    L1: iconst 0     ;; carrega false (0) na pilha
    L2: sipush 222   ;; se 222 >= 333 salta para L3
        sipush 333
        if_icmpge L3
        iconst 1     ;; carrega true (1) na pilha
        goto L4
    L3: iconst 0     ;; carrega false (0) na pilha
    L4: iand         ;; se testes foram ok salta para L5
        ifne L5
        iconst 1     ;; carrega true (1) na pilha
        goto L6
    L5: iconst 0     ;; carrega false (0) na pilha
    L6: ifeq L7
        ;; imprime true
        getstatic java/lang/System.out java/io/PrintStream
        ldc "true"
        invokevirtual java/io/PrintStream.print(java/lang/String)V
        goto L8
    L7: ;; imprime false
        getstatic java/lang/System.out java/io/PrintStream
        ldc "false"
        invokevirtual java/io/PrintStream.print(java/lang/String)V
    L8: return
    }
}

Vale aqui ressaltar que apesar da JVM ter as instruções iand e ior, ela não possui uma instrução como inot. Esta "negação" da operação deve ser implementada com ifne e labels. O ifne (if not equal) salta para o label indicado caso o último valor da pilha não seja zero.

Na tabela abaixo é possível ver as instruções geradas a partir do assembly acima bem como o estado da pilha da JVM após a execução de cada instrução:

Label	Instrução	Estado pilha após instrução
	sipush 111	[ 111 ]
	sipush 222	[ 111, 222 ]
	if_icmpge L1	[ ]
	iconst 1	[ 1 ]
	goto L2	[ 1 ]
L1	~~iconst 0~~
L2	sipush 222	[ 1, 222 ]
	sipush 333	[ 1, 222, 333 ]
	if_icmpge L3	[ 1 ]
	iconst 1	[ 1, 1 ]
	goto L4	[ 1, 1 ]
L3	~~iconst 0~~
L4	iand	[ 1 ]
	ifne L5	[ ]
	~~iconst 1~~
	~~goto L6~~
L5	iconst 0	[ 0 ]
L6	ifeq L7
	~~getstatic ...~~
	~~ldc "true"~~
	~~invokevirtual ...~~
	~~goto L8~~
L7	getstatic ...	[ getstatic ]
	ldc "false"	[ getstatic, "false" ]
	invokevirtual ...
L8	return

No final da execução o programa exibe a saída esperada: "false".

"Perrengue" com JASM e uma grata surpresa

No início do projeto tive que decidir entre gerar o arquivo class diretamente ou utilizar um assemblador de Java Assembly. Optei por utilizar o JASM, um assemblador Java em que rapidamente consegui rodar alguns exemplos.

Eis que em pleno feriado (29/3, sexta-feira santa), após gerar o assembly para o operador not, ao executar o JASM ele simplesmente gerava um "NullPointerException". Fiz alguns testes mas não identifiquei nada estranho no assembly gerado pelo POJ.

Como é o usual entrei no github do JASM e tentei identificar algum bug relacionado, mas não havia nada. Como o projeto é pouco movimentado eu já estava esperando por alguma mudança drástica no POJ: ter que escolher outro assemblador ou gerar o arquivo class diretamente.

Antes que alguém diga "o JASM é open source, contribui lá". Até pensei nisso, mas eu não sei programar em Java, e sendo bem sincero, não é uma das linguagens que eu tenha interesse em aprender :-)

Bom, abri uma issue no JASM, e para minha surpresa, em menos de 1 hora o mantenedor respondeu e identificou o problema. Inicialmente eu estava utilizando a instrução "iconst_1" (ao invés de "iconst 1"). A JVM tem a instrução "iconst_1", mas como é uma otimização da instrução "iconst 1", o JASM não a implementa. Enfim, ajustei para "iconst 1" e tudo funcionou.

Maiores informações

O repositório com o código completo do projeto e a sua documentação está aqui.

Operadores de adição e subtração

Alex Sandro Garzão — Sat, 23 Mar 2024 18:06:02 +0000

Faz mais de um mês desde a última publicação sobre o projeto. Culpa da correria do dia-a-dia :-D

Após a primeira versão, que conseguia compilar e executar o "Hello world!" em Pascal na JVM, fiz alguns avanços neste último mês. Os mais relevantes foram:

Concatenação de strings
Soma e subtração de inteiros

Conforme citado em uma publicação anterior, o POJ (Pascal on the JVM) lê um programa Pascal e gera o JASM (Java Assembly) para posteriormente ser transformado em um arquivo class e executado na JVM.

Para exemplificar o que o POJ faz, abaixo temos um exemplo em Pascal que concatena três strings:

program ConcatStrings;
begin
  writeln ('Hello ' + 'world ' + 'again!');
end.

Abaixo temos o JASM gerado pelo POJ:

// Code generated by POJ 0.1
public class concat_three_strings {
  public static main([java/lang/String)V {
    getstatic java/lang/System.out java/io/PrintStream
    ldc "Hello "
    ldc "world "
    invokedynamic makeConcatWithConstants(java/lang/String, java/lang/String)java/lang/String {
      invokestatic java/lang/invoke/StringConcatFactory.makeConcatWithConstants(java/lang/invoke/MethodHandles$Lookup, java/lang/String, java/lang/invoke/MethodType, java/lang/String, [java/lang/Object)java/lang/invoke/CallSite 
      [""] 
    }
    ldc "again!"
    invokedynamic makeConcatWithConstants(java/lang/String, java/lang/String)java/lang/String {
      invokestatic java/lang/invoke/StringConcatFactory.makeConcatWithConstants(java/lang/invoke/MethodHandles$Lookup, java/lang/String, java/lang/invoke/MethodType, java/lang/String, [java/lang/Object)java/lang/invoke/CallSite 
      [""] 
    }
    invokevirtual java/io/PrintStream.println(java/lang/String)V
    return
  }
}

A partir deste assembly utilizamos o JASM (assemblador de Java Assembly) para criar o arquivo class final.

Testes End2End

Para auxiliar no desenvolvimento, além dos testes unitários agora temos uma pasta com exemplos em pascal e a saída esperada em JASM. Com isso temos testes End2End no POJ que validam a entrada (exemplos em Pascal) com a saída esperada (JASM).

Validação de tipos

Outra funcionalidade implementada foi a validação de tipos. Apesar da JVM validar a tipagem dos dados, é extremamente recomendado que o POJ valide o código Pascal para não gerar um arquivo JASM inválido.

Para exemplificar, o código abaixo está sintaticamente correto, mas semanticamente incorreto porque em Pascal não é possível somar strings com inteiros.

program Hello;
begin
  writeln ('Hello ' + 1);
end.

Para realizar esta tipagem o parser agora mantém uma pilha com os tipos de dados que estão sendo empilhados na JVM. Com isso, nas operações de soma e subtração o tipo dos dados são validados durante a análise semântica.

Concatenação de strings, soma e subtração de inteiros

Algumas modificações foram realizadas no parser para reconhecer a expressão "expression additiveoperator expression" (trecho da gramática abaixo).

expression
  : expression op = relationaloperator expression # RelOp
  | expression op = ('*' | '/') expression        # MulDivOp
  | expression op = additiveoperator expression   # AddOp
  | signedFactor                                  # ExpSignedFactor
  ;

Esta expressão é responsável pela derivação tanto da soma bem como da subtração de strings e inteiros.

O "# AddOp" na gramática acima é uma anotação do ANTLR que permite que cada regra da gramática possa ser facilmente identificada durante o parser. Com esta anotação o ANTLR gera um método (ExitAddOp abaixo) que será executado sempre que o parser terminar o reconhecimento da expressão.

func (t *TreeShapeListener) ExitAddOp(ctx *parsing.AddOpContext) {
  // Check pascal types.
  pt1 := t.pst.Pop()
  pt2 := t.pst.Pop()
  if pt1 != pt2 {
    t.jasm.AddOpcode("invalid types")
    return
  }

  // Get operator.
  op := ctx.GetOp().GetText()
  switch {
  case op == "+":
    switch pt1 {
    case String:
      t.GenAddStrings()
    case Integer:
      t.GenAddIntegers()
    default:
      t.jasm.AddOpcode("invalid type in add")
    }
  case op == "-":
    switch pt1 {
    case Integer:
      t.GenSubIntegers()
    default:
      t.jasm.AddOpcode("invalid type in sub")
    }
  }
}

Este método inicia retirando os últimos 2 tipos da pilha e verificando se possuem o mesmo tipo. Após isso é verificado qual o operador (+ ou -) e, baseado no operador e no tipo do dado, executado o método que irá gerar o JASM. Neste ponto o código também indica uma operação inválida (como no caso da subtração de strings, que é uma operação inválida em Pascal).

Como exemplo temos abaixo o método GenAddStrings, responsável por gerar o JASM para concatenar duas string, invocado no trecho acima:

func (t *TreeShapeListener) GenAddStrings() {
t.jasm.StartInvokeDynamic(`makeConcatWithConstants(java/lang/String, java/lang/String)java/lang/String`)
  t.jasm.AddOpcode(`invokestatic java/lang/invoke/StringConcatFactory.makeConcatWithConstants(java/lang/invoke/MethodHandles$Lookup, java/lang/String, java/lang/invoke/MethodType, java/lang/String, [java/lang/Object)java/lang/invoke/CallSite`)
  t.jasm.AddOpcode(`[""]`)
  t.jasm.FinishInvokeDynamic()
  t.pst.Push(String)
}

O jasm (em t.jasm) é um objeto que auxilia na geração do JASM, podendo emitir assinaturas de métodos, classes (do Java Assembly) bem como os opcodes.

Vale observar a última linha do trecho acima: t.pst.Push(String). "pst" (pascal stack type) é a pilha que guarda os tipos dos dados. Neste caso, como foi reconhecida uma concatenação de strings, e foi emitido código para concatená-las, estamos também inserindo o tipo String na pst.

Até este ponto reconhecemos o operador, o tipo do dado, realizamos uma validação de tipos e geramos código para executar a operação. Mas e as strings e os inteiros? Como eles são carregados para a pilha da JVM?

Na gramática os strings e os inteiros de um programa Pascal são considerados "símbolos terminais" e derivam a partir da regra signedFactor existente na regra expression (vide trecho da gramática acima). E o parser, baseado nas regras instrumentadas em Go, sempre que reconhece estes símbolos terminais automaticamente gera o JASM para carregá-los na pilha da JVM.

No trecho abaixo é possível ver que ao terminar o reconhecimento de uma string o método ExitString gera o opcode ldc (load constant) seguido da string a ser carregada na pilha da JVM. O ctx.GetText() é disponibilizado pelo runtime Go do ANTLR e permite obter o valor do símbolo terminal, que no nosso caso é a string.

func (t *TreeShapeListener) ExitString(ctx *parsing.StringContext) {
  str := ctx.GetText()
  t.jasm.AddOpcode("ldc", "\""+str+"\"")
  t.pst.Push(String)
}

A "pegadinha" da precedência de operadores

No site do ANTLR tem a gramática pronta de Pascal. Porém, apesar de reconhecer corretamente os programas em Pascal, esta gramática não lida corretamente com a precedência de operadores. A forma recomendada no próprio site do ANTLR é similar ao exemplo abaixo:

grammar Expr;
prog:   (expr NEWLINE)* ;
expr:   expr ('*'|'/') expr
    |   expr ('+'|'-') expr
    |   INT
    |   '(' expr ')'
    ;
NEWLINE : [\r\n]+ ;
INT     : [0-9]+ ;

Com isso a derivação do parser não respeitava a precedência de operadores e o POJ gerava um JASM errado.

Por exemplo, para o trecho em Pascal abaixo:

writeln (8-4-2);

O correto seria o POJ gerar o seguinte assembly:

getstatic java/lang/System.out java/io/PrintStream
sipush 8
sipush 4
isub 
sipush 2
isub 
invokevirtual java/io/PrintStream.println(I)V

No exemplo acima atentem para a localização dos opcodes isub.

Basicamente o assembly acima é executado na JVM da seguinte forma:

Instrução	Descrição instrução	Estado pilha após instrução
sipush 8	Empilha o inteiro 8	[ 8 ]
sipush 4	Empilha o inteiro 4	[ 8, 4 ]
isub	Retira os 2 últimos elementos da pilha (8 e 4), subtrai e empilha o resultado (4)	[ 4 ]
sipush 2	Empilha o inteiro 2	[ 4, 2 ]
isub	Retira os 2 últimos elementos da pilha (4 e 2), subtrai e empilha o resultado (2)	[ 2 ]

No final da execução a pilha contém o resultado esperado de 8-4-2: 2.

Porém por não lidar corretamente com a precedência de operadores, a partir da gramática original era gerado o assembly abaixo. Reparem novamente na localização dos opcodes isub:

getstatic java/lang/System.out java/io/PrintStream
sipush 8
sipush 4
sipush 2
isub 
isub 
invokevirtual java/io/PrintStream.println(I)V

E o assembly acima é executado na JVM da seguinte forma:

Instrução	Descrição instrução	Estado pilha após instrução
sipush 8	Empilha o inteiro 8	[ 8 ]
sipush 4	Empilha o inteiro 4	[ 8, 4 ]
sipush 2	Empilha o inteiro 2	[ 8, 4, 2 ]
isub	Retira os 2 últimos elementos da pilha (4 e 2), subtrai e empilha o resultado (2)	[ 8, 2 ]
isub	Retira os 2 últimos elementos da pilha (8 e 2), subtrai e empilha o resultado (6)	[ 6 ]

Com isso o resultado do assembly acima era 6 :-)

O repositório com o código completo do projeto e instruções sobre como criar o executável bem como executar os testes está aqui.

Compilando o "Hello world" em Pascal

Alex Sandro Garzão — Mon, 19 Feb 2024 21:55:43 +0000

Como citei anteriormente, eu iria iniciar o projeto de um novo compilador, open source, em Go. Basicamente, o POJ (Pascal on the JVM) possibilita que seja executado um subset de Pascal na JVM. Mais detalhes sobre o projeto nesta postagem aqui.

A primeira meta do projeto era conseguir compilar e executar o "Hello world" em Pascal na JVM. Apesar de parecer simples, envolvia uma série de tarefas como:

Definir qual gerador de parsers será utilizado: realizei alguns testes com o ANTLR e, apesar de alguns "perrengues" no início, optei por ele;
Encontrar uma gramática de Pascal pronta no formato do ANTLR: isso foi bem tranquilo, já que no repositório do ANTLR existe a gramática pronta para várias linguagens;
Ajustar a gramática para reconhecer o subset de Pascal esperado: no momento, apenas removi algumas sintaxes que realmente não serão utilizadas;
No parser identificar a definição de procedimentos no Pascal para determinar o bloco principal: isso gerou um pouco de trabalho por falta de conhecimento minha sobre a V4 do ANTLR (usei muito a V2 e V3 anteriormente);
Encontrar um montador Java Assembly: o mais conhecido é o Jasmin, mas não consegui rodar os exemplos simples (talvez por imperícia minha, enfim), então acabei optando pelo JASM porque rapidamente consegui executar os exemplos;
POJ gerar um código assembly Java válido para o JASM: aqui a dificuldade foi entender como a V4 do ANTLR funciona para obter os tokens no código em Go;
Criar o README inicial: tentei criar o mínimo necessário, mas já tem as instruções sobre como criar o binário, executar o POJ, executar o "Hello world" na JVM, entre outros.

No momento, dos exemplos citados na postagem anterior, apenas o exemplo do "Hello world" funciona no POJ. Claro que variações deste exemplo, como várias chamadas a writeln funcionam também:

program Hello;
begin
  writeln ('Hello world1!');
  writeln ('Hello world2!');
  writeln ('Hello world3!');
end.

Para possibilitar a execução de outros programas em Pascal, nas próximas semanas vou focar em recursos como:

Declaração e uso de variáveis;
Entrada e saída de dados (terminal);
Instrução If/Else, For, Repeat e While;
Operações aritméticas;
Declaração e uso de procedures e funções;
Uso de funções recursivas.

Para quem se interessou, o repositório do projeto é este aqui.

Pascal rodando na JVM

Alex Sandro Garzão — Tue, 30 Jan 2024 22:20:48 +0000

Compiladores é um dos temas do qual tenho muito interesse. Inclusive estou publicando alguns projetos antigos meus nesta série aqui.

Porém, como comentei em uma publicação desta série, vou iniciar uma abordagem mais prática onde irei construir um compilador "from scratch", passo-a-passo, de código aberto, tanto para consolidar alguns temas abordados bem como para termos algo concreto.

Sobre o desafio

Compiladores são, por natureza, projetos que eu considero desafiadores e complexos. E para termos um objetivo claro e, dentro do possível, simples para este projeto, o que vamos fazer é implementar uma nova solução para o trabalho de faculdade que comentei nesta publicação: rodar um subset de Pascal na JVM. Para tal, iremos criar um compilador que entende este subset de Pascal e gera o arquivo class para ser executado na JVM.

Como a minha criatividade para criar nomes de projetos é baixa, vou batizar o projeto de POJ (Pascal On the JVM). Se alguém tiver um nome bacana, eu aceito :-)

Visão macro do projeto

Na solução anterior (mais detalhes aqui) o compilador gerava o arquivo class diretamente. Porém, para tentar simplificar a nossa solução, vou abstrair a geração do arquivo class utilizando um montador Java Assembly qualquer (Figura abaixo). Com isso o nosso compilador (POJ) será responsável por ler um programa contendo código Pascal e gerar o assembly Java equivalente enquanto o montador será responsável por ler este assembly e gerar o arquivo class para ser executado na JVM.

Entendo que seja uma proposta válida no momento, mas só após alguns testes com montadores assembly Java será possível validar esta proposta. Caso não seja encontrado um montador que atenda as necessidades do projeto, teremos que partir para gerar o arquivo class diretamente.

Assim como no projeto anterior, para facilitar o desenvolvimento do compilador eu optei por utilizar um gerador de parsers. Desde 2003 sou fã do ANTLR, que além de fornecer uma integração interessante entre a análise léxica e sintática, também utiliza EBNF para especificar a gramática da linguagem. Além disso, ANTLR gera código para diversas linguagens, entre elas Go :-)

A Figura abaixo contém as etapas necessárias para criarmos o nosso compilador (POJ). A partir da gramática da linguagem Pascal, o ANTLR gera o parser em Golang. A partir deste código Go gerado iremos instrumentar as regras necessárias, tanto na análise léxica bem como na sintática. Após isso utilizaremos o compilador do Go para gerar o binário do POJ.

Subset aceito

Quando falamos em subset de Pascal entendam um programa Pascal válido, mas com um conjunto reduzido de instruções e operações:

Declaração de variáveis utilizando os tipos básicos: integer, real, boolean e string;
Estruturas condicionais: If/Else;
Estruturas de repetição: For, While, Repeat;
Entrada e saída de dados via console: Write, WriteLn, Read, ReadLn;
Operações matemáticas com precedência de operadores: soma, subtração, divisão, multiplicação e módulo;
Declaração de blocos de código: procedures e funções.

Exemplos de programas aceitos

Abaixo é possível ver o clássico “Hello world!” em Pascal:

program Hello;
begin
  writeln ('Hello world!');
end.

Abaixo temos o cálculo do fatorial, de forma recursiva:

program fatorial;

var numero : integer;

function fatorial(n : integer) : integer;
begin
    if n<0 then fatorial := 0
    else begin
        if n<=1 then fatorial := 1
        else fatorial := n * fatorial(n-1);
    end;
end;

begin
    write('Introduza numero inteiro: ');
    readln(numero);
    writeln;
    writeln('O fatorial de ', numero, ' e: ', fatorial(numero));
end.

Abaixo temos um exemplo com entrada e saída de dados:

program NameAndAge;
var
  MyName: String;
  MyAge : Byte;
begin
  Write('What is your name? '); Readln(MyName);
  Write('How old are you? '); Readln(MyAge);
  Writeln;
  Writeln('Hello ', MyName);
  Writeln('You are ', MyAge, ' years old');
end.

Para quem tiver interesse de ver a execução destes programas, sugiro utilizar o Free Pascal Compiler no momento. Nas próximas semanas poderemos utilizar o POJ para tal :-)

Por que refazer?

Uma dúvida comum talvez seja: por que refazer? Por que não melhorar o projeto anterior?

Bom, eu até encontrei o código antigo, de 1999, do projeto de faculdade. Mas esta versão utiliza o JavaCC e Java, tecnologias que praticamente só utilizei naquele período. Aprender Java e ajustar um código Java de 1999 não está nos meus objetivos. E como pretendo manter e evoluir este projeto, optei por reescrevê-lo em tecnologias que tenho mais interesse como ANTLR e Go.

Por que JVM?

Outra dúvida comum talvez seja: porque foi escolhida a JVM? Em 1999 foi utilizada a especificação 1.1 da JVM, e garanto que havia pouca documentação na época. O motivo da escolha da JVM foi porque, dentre as VMs da época, a JVM era stack based machine, o que simplifica (e muito) a geração do bytecode. Isso porque, além de necessitar de poucas operações, todas as operações da máquina virtual operam sobre a pilha. Já VMs register based necessitam de um conjunto maior de operações e precisam lidar com a alocação de registradores (mesmo que estes sejam virtuais). Para quem tiver interesse de ler mais sobre, aqui tem uma publicação bem interessante sobre este tópico. Isso sem falar que a JVM já é utilizada por várias linguagens além do Java, como Clojure, Lisp, Scala e Kotlin, isso só citando algumas das mais conhecidas.

Ambiente para desenvolvimento e execução de aplicações escritas em HoloLinguagem

Alex Sandro Garzão — Tue, 02 Jan 2024 18:15:54 +0000

Durante o seu doutorado na UFRGS o professor Jorge Barbosa criou o Holoparadigma, um novo paradigma de programação que dava suporte ao desenvolvimento de aplicações distribuídas. Algumas características deste paradigma (citados mais abaixo) facilitavam (e muito) o desenvolvimento de aplicações móveis, algo bem inovador para a época (ano de 2000, aproximadamente).

Como prova de conceito deste novo paradigma foi criado um ambiente de desenvolvimento e execução de aplicações (figura abaixo).

Nesta figura temos os seguintes componentes:

Programa Holo: Programa escrito em HoloLinguagem, uma linguagem de programação acadêmica que implementa o HoloParadigma
HoloJava: Compilador que traduz um programa em HoloLinguagem para código Java
Compilador Java (JavaC): Compilador que processa o código gerado pelo HoloJava e gera o bytecode para ser executado na JVM
Máquina Virtual Java (JVM): Máquina virtual que executa o bytecode gerado pelo JavaC

O principal objetivo desde ambiente era possibilitar a execução dos exemplos em HoloLinguagem.

Abaixo temos um exemplo em HoloLinguagem que demonstra como o paralelismo e a sincronia são explorados. Entes são um conceito elementar do HoloParadigma, sendo similares às classes do paradigma OO. Neste exemplo o Holo, que é o ente principal de um programa, cria dois novos entes (a partir de ente_paralelo) e aguarda que terminem sua execução. Para sincronia é utilizado um blackboard (o history) onde cada ente insere a chave "terminei" em conjunto com o seu ID. Por sua vez, o ente Holo aguarda em history o término dos entes.

holo() {
   holo() {
      writeln('Exemplo que demonstra paralelismo e sincronia'),
      clone(ente_paralelo(1), ente_paralelo1),
      clone(ente_paralelo(2), ente_paralelo2), 
      for X := 1 to 5 do {
         writeln('Ente holo esta na iteracao ', X)
      }
      // aguarda o término dos entes clonados
      history#terminei(#Id),
      // informa qual ente terminou
      writeln('Ente ', Id, ' terminou...'),
      // aguarda o término dos entes clonados
      history#terminei(#Id),
      // informa qual ente terminou
      writeln('Ente ', Id, ' terminou...')
   }
}

ente_paralelo() {
   ente_paralelo(Id) {
      for X := 1 to 20 do {
         writeln('Ente ', Id, ' esta na iteracao ', X)
      }
      // sinaliza na história externa que terminou
      out(history)!terminei(Id)
   }
}

Porém, durante o seu doutorado, não foi possível explorarem alguns recursos da HoloLinguagem, em especial alguns conceitos da computação móvel como mover aplicações em execução para outros dispositivos e o compartilhamento de dados entre aplicações distribuídas.

É neste momento que eu entro no projeto. Em 2002 o tema do meu TCC na UNISINOS foi sobre como criar um ambiente de desenvolvimento e execução para aplicações escritas em HoloLinguagem. Meu orientador foi o Barbosa, um professor fantástico 🙂

Na época tínhamos 3 opções para implementar estes conceitos da computação móvel e explorar ainda mais as potencialidades da HoloLinguagem:

Implementar através de bibliotecas e usar a estrutura atual do projeto: neste caso teríamos que alterar o compilador (HoloJava) para que reconhecesse os novos comandos e criar as bibliotecas necessárias
Implementar diretamente na JVM através de novos opcodes: neste caso, além de alterar a JVM, teríamos que alterar o JavaC ou então gerar diretamente bytecode para a JVM
Criar uma nova VM com suporte a estes novos conceitos: neste caso teríamos que criar um novo compilador e uma nova VM

Entendi que seria mais interessante (e divertido) a última opção, o famoso “reinventar a roda”, e foi o que eu fiz 🙂

A figura abaixo contém a proposta do meu TCC: implementar um novo ambiente para o desenvolvimento e execução de aplicações escritas em HoloLinguagem. Seguindo alguns aprendizados de um projeto anterior, optei por criar também o HoloAssembly, uma linguagem intermediária para facilitar os testes e a implementação do projeto.

Nesta figura temos os seguintes componentes:

Programa Holo: Programa escrito em HoloLinguagem que implementa o HoloParadigma
HoloC: É o compilador que traduz aplicações escritas em HoloLinguagem para HoloAssembly, uma linguagem intermediária
HoloASM: É o montador assembly responsável por traduzir HoloAssembly para o bytecode que a HoloVM entende
HoloVM: É a máquina virtual (VM) capaz de dar suporte à execução das aplicações de forma distribuída

Aqui tem um artigo publicado no WSCAD de 2002 sobre o meu TCC.

Como gerador de parsers utilizei o YAPG (Yet Another Parser Generator), um projeto pessoal que irei abordar em outra publicação. Basicamente o YAPG tinha como entrada uma gramática EBNF da HoloLinguagem contendo ações codificadas em C++, o que resultava em um parser em C++ que entendia código escritos na HoloLinguagem e executava as ações determinadas. Este parser nada mais era que o HoloC. Da mesma forma, o HoloASM também era gerado através do YAPG.

Para exemplificar o processo de compilação do HoloC vou usar o “Hello world” em HoloLinguagem abaixo:

holo() {
   holo() {
      writeln('Hello world !!!')
   }
}

Para o código acima o HoloC gerava o seguinte código em HoloAssembly:

holo
    holo( )
        ;; V1 := 'Hello world !!!',
        lsb     'Hello world !!!'
        sv      V1
        ;; writeln(V1)
        lv      V1
        wr   
        wrln 
    end
end

Por sua vez, o HoloASM gerava o seguinte bytecode para a HoloVM:

Header
    Magic number : 0xB0 0xCA 0xBA 0xBE
    File type    : HoloVM Version 0.1
    Major version: 0
    Minor version: 1

Constant pool size: 4
    000:    Size:   4   Type: 1-->[symbol]    Info: [holo]
    001:    Size:   6   Type: 1-->[symbol]    Info: [holo/0]
    002:    Size:  15   Type: 3-->[string]    Info: [Hello world !!!]
    003:    Size:   2   Type: 3-->[string]    Info: [V1]

Static beings count: 1
    Being cpindex: [000]-->[holo]
    Action count : 1
    Action 0
        Action cpindex: [001]-->[holo/0]
        Bytecode size : 9
            000:    lsb    [002]-->[Hello world !!!]
            002:    sv     [003]-->[V1]
            004:    lv     [003]-->[V1]
            006:    wr
            007:    wrln
            008:    ret

Quem conhece a estrutura da JVM vai perceber as semelhanças com o assembly da HoloVM. E, assim como a JVM, a HoloVM é uma stack based machine.

Posso dizer que foi um projeto muito divertido, mas que gerou muito trabalho, muito mesmo. Mas o resultado compensou o esforço :-)

Sei que muita coisa ficou "vaga", em especial sobre o HoloAssembly e a HoloVM. Infelizmente não tenho nada funcional para compartilhar. Encontrei parte do código destes projetos em backups antigos, mas não consegui nem rodar eles localmente. Enfim, muito do material que coloquei nesta publicação foram retirados das apresentações da época.

Mas, para tentar compensar a falta de detalhes aqui, logo que possível vou iniciar um projeto open source de um compilador. Já adianto que este novo projeto será em Go e irei utilizar um gerador de parsers bem conhecido.

Feedbacks são muito bem-vindos :-)