Teste de fogo: fatorial recursivo

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.