Introdução
Continuando a série sobre Treetop, é hora de brincar um pouco mais com todos os conceitos envolvidos e implementar uma linguagem Turing-complete.
Para não complicar as coisas, vamos usar uma linguagem bem simples, que demonstre os conceitos e não fique presa em detalhes de sintaxes. Brainfuck, apesar do nome, é uma boa escolha. Extremamente minimalista–possui somente oito comandos usando oito símbolos–permite uma implementação rápida e ao mesmo tempo permite brincar com os vários conceitos que estamos vendo. Tudo bem, eu admito que ela é um Turing tarpit mas serve com uma base interessante para esse artigo.
Brainfuck consiste em oito comandos, como mencionado acima, que manipulam um espaço de células de memória. Um ponteiro de instrução é definido para a primeira instrução e os comandos manipulam esse ponteiro para executar as várias instruções. Como cada comando é um simples símbolo, a ambigüidade da gramática é nula. Qualquer outro símbolo dentro do programa é ignorado e pode ser usado como uma comentário.
Os comandos da linguagem são:
- >, incrementa o ponteiro de dados;
- <, decrementa o ponteiro de dados;
- +, incrementa o byte apontado pelo ponteiro de dados;
- -, decrementa o byte apontado pelo ponteiro de dados;
- ., escreve o valor do byte apontado pelo ponteiro de dados;
- ., lê um byte e armazena no endereço apontado pelo ponteiro de dados;
- [, se o byte no endereço atual do ponteiro de dados é zero, pula para frente até o próximo comando ];
- ], se o byte no endereço atual do ponteiro de dados não é zero, pula para trás até o próximo comando [.
Reconhecendo a linguagem
Vamos olhar então como ficaria a gramática da linguagem:
grammar Brainfuck
rule program
instruction*
end
rule instruction
loop /
simple /
comment
end
rule loop
'[' instructions:instruction* ']‘
end
rule simple
‘>’ /
‘<' /
'+' /
'-' /
',' /
'.'
end
rule comment
[^\[\]><+-,.]
end
endA descrição da gramática é simples:
- Um programa é uma série de zero ou mais instruções;
- Uma instruções pode ser composta--ou seja, um loop, denotado pelos comandos
[e]--, uma instrução simples, ou um comentário (que é qualquer caractere que não seja uma instrução); - Dentro de um loop, podem existir zero ou mais instruções.
Podemos ver que a gramática funciona executando comandos como abaixo:
>> require "rubygems"
=> false
>> require "treetop"
=> true
>> require "brainfuck"
=> true
>> p = BrainfuckParser.new
=> #
>> p.parse("><+-[]")
=> SyntaxNode offset=0, "><+-[]":
SyntaxNode offset=0, ">"
SyntaxNode offset=1, "<"
SyntaxNode offset=2, "+"
SyntaxNode offset=3, "-"
SyntaxNode+Loop0 offset=4, "[]":
SyntaxNode offset=4, "["
SyntaxNode offset=5, ""
SyntaxNode offset=5, "]" Note que os comentários também são marcados por nós sintáticos, já que estamos processando os mesmos. Obviamente, quando da interpretação do programa, precisaremos eliminá-los.
Criando uma árvore sintática
A partir da gramática, o nosso objetivo é criar uma árvore manipulável, eliminando comentários, agrupando instruções de loop e preparando um ambiente para a execução em si.
Podemos usar a mesma técnica que usamos nos artigos anteriores.
Primeiro, definimos uma representação sintática. O arquivo brainfuck_ast.rb ficaria assim inicialmente:
class Program
attr_reader :instructions
def initialize(instructions)
@instructions = instructions
end
end
class Instruction
attr_reader :command
def initialize(command)
@command = command
end
end
class Loop
attr_reader :instructions
def initialize(instructions)
@instructions = instructions
end
endEfetivamente, precisamos somente de três tipos de nós: o programa em si, para servir como um container inicial do ambiente, instruções simples e loops.
A seguir precisamos reconhecer isso em nossa gramática. Mostrando a gramática adaptada em um único passo, teríamos algo assim:
grammar Brainfuck
rule program
instruction* <ProgramPredicate>
end
rule instruction
loop /
simple /
comment
end
rule loop
'[' instructions:instruction* ']' <LoopPredicate>
end
rule simple
'>' <InstructionPredicate> /
'<' <InstructionPredicate> /
'+' <InstructionPredicate> /
'-' <InstructionPredicate> /
',' <InstructionPredicate> /
'.' <InstructionPredicate>
end
rule comment
[^\[\]><+-,.] <CommentPredicate>
end
endE finalmente, o arquivo contendo as extensões, brainfuck_ext.rb, ficaria assim:
module Common
def build_elements(elements)
elements.
select { |element| element.respond_to?(:build) }.
collect { |element| element.build }
end
end
module ProgramPredicate
include Common
def build
Program.new(build_elements(elements))
end
end
module LoopPredicate
include Common
def build
Loop.new(build_elements(instructions.elements))
end
end
module InstructionPredicate
def build
Instruction.new(text_value)
end
end
module CommentPredicate
endNo código acima, primeiro definimos um módulo comum que pode ser incluído em outros e possui um método que seleciona instruções que podem ser utilizadas. Depois definimos módulos para o que precisamos processar. E finalmente ignoramos os comentários.
Interpretando
Agora precisamos converter o código acima em um interpretador. A implementação é trivial e vamos acompanhá-la passo a passo, escrevendo o arquivo brainfuck_int.rb, que conterá o interpretador:
class BrainfuckInterpreter
def initialize(commands)
@ast = BrainfuckParser.new.parse(commands).build
end
endEsse método inicializa o interpretador recebendo uma série de comandos na forma de uma string e construindo uma árvore sintática final da mesma.
O próximo passo é começar a execução em si. Um interpretador Brainfuck deve inicialmente alocar um espaço de memória para execução e inicializar o ponteiro de instruções. Em seguida, deve seguir de instrução em instrução, rodando o comando em questão. O método que faz isso é o seguinte:
class BrainfuckInterpreter
def initialize(commands)
@ast = BrainfuckParser.new.parse(commands).build
end
def execute
@addresses = [0] * 3000
@pointer = 0
execute_ast_node(@ast)
end
endEsse método inicializa o espaço de instruções e o ponteiro e em seguida chama a execução de um nó da árvore. Embora esse nó sempre seja um nó do tipo Program, o método está preparado para executar qualquer instrução.
Na seqüência, está a implementação do método execute_ast_node:
class BrainfuckInterpreter
def initialize(commands)
@ast = BrainfuckParser.new.parse(commands).build
end
def execute
@addresses = [0] * 3000
@pointer = 0
execute_ast_node(@ast)
end
protected
def execute_ast_node(ast)
send("execute_" + ast.class.name.downcase, ast)
end
endO método é simplesmente um dispatch para o método apropriado para lidar com o tipo de nó em si.
O nó program é o que possui a implementação mais simples. Com o mesmo representa somente uma lista de instruções, a execução consiste em nada mais do que rodar essa lista, pedindo a execução de cada nó filho. A implementação fica, então, como mostrado abaixo:
class BrainfuckInterpreter
def initialize(commands)
@ast = BrainfuckParser.new.parse(commands).build
end
def execute
@addresses = [0] * 3000
@pointer = 0
execute_ast_node(@ast)
end
protected
def execute_ast_node(ast)
send("execute_" + ast.class.name.downcase, ast)
end
def execute_program(ast)
ast.instructions.each { |instruction| execute_ast_node(instruction) }
end
endA implementação dos nós instruction é igualmente simples:
class BrainfuckInterpreter
def initialize(commands)
@ast = BrainfuckParser.new.parse(commands).build
end
def execute
@addresses = [0] * 3000
@pointer = 0
execute_ast_node(@ast)
end
protected
def execute_ast_node(ast)
send("execute_" + ast.class.name.downcase, ast)
end
def execute_program(ast)
ast.instructions.each { |instruction| execute_ast_node(instruction) }
end
def execute_instruction(ast)
case ast.command
when '>'
@pointer += 1
when '<'
@pointer -= 1
when '+'
@addresses[@pointer] += 1
when '-'
@addresses[@pointer] -= 1
when ','
@addresses[@pointer] = STDIN.getc
when '.'
STDOUT.print @addresses[@pointer].chr
end
end
endPara cada instrução, executamos a instrução correspondente. As duas primeiras simplesmente movem o ponteiro de instrução--não estamos aqui, executando qualquer tipo de testes para evitar instruções inválidas. A duas instruções seguintes não movem o ponteiro de dados e simplesmente manipulam o dado que está no endereço especificado. Finalmente, as demais instruções lêem um byte da entrada padrão para o endereço atual ou emitem o byte atual para a saída padrão.
Finalmente, temos a implementação de um loop que também é trivial:
class BrainfuckInterpreter
def initialize(commands)
@ast = BrainfuckParser.new.parse(commands).build
end
def execute
@addresses = [0] * 3000
@pointer = 0
execute_ast_node(@ast)
end
protected
def execute_ast_node(ast)
send("execute_" + ast.class.name.downcase, ast)
end
def execute_program(ast)
ast.instructions.each { |instruction| execute_ast_node(instruction) }
end
def execute_instruction(ast)
case ast.command
when '>'
@pointer += 1
when '<'
@pointer -= 1
when '+'
@addresses[@pointer] += 1
when '-'
@addresses[@pointer] -= 1
when ','
@addresses[@pointer] = STDIN.getc
when '.'
STDOUT.print @addresses[@pointer].chr
end
end
def execute_loop(ast)
while @addresses[@pointer] != 0
ast.instructions.each { |instruction| execute_ast_node(instruction) }
end
end
endA implementação simplesmente verifica se o endereço atual contém um valor nulo e caso contrário continua a execução das instruções aninhadas. Isso é o mesmo que pular para frente a para trás nos operadores [ e ].
Para completar o quadro e facilitar a execução, podemos incluir métodos auxiliares:
class BrainfuckInterpreter
def initialize(commands)
@ast = BrainfuckParser.new.parse(commands).build
end
def execute
@addresses = [0] * 3000
@pointer = 0
execute_ast_node(@ast)
end
def self.run(commands)
BrainfuckInterpreter.new(commands).execute
end
def self.run_file(file)
BrainfuckInterpreter.new(File.readlines(file).join).execute
end
protected
def execute_ast_node(ast)
send("execute_" + ast.class.name.downcase, ast)
end
def execute_program(ast)
ast.instructions.each { |instruction| execute_ast_node(instruction) }
end
def execute_instruction(ast)
case ast.command
when '>'
@pointer += 1
when '<'
@pointer -= 1
when '+'
@addresses[@pointer] += 1
when '-'
@addresses[@pointer] -= 1
when ','
@addresses[@pointer] = STDIN.getc
when '.'
STDOUT.print @addresses[@pointer].chr
end
end
def execute_loop(ast)
while @addresses[@pointer] != 0
ast.instructions.each { |instruction| execute_ast_node(instruction) }
end
end
endE com isso, podemos testar um programa. Abra um novo arquivo chamado brainfuck_test.rb e introduza o seguinte código:
require "rubygems"
require "treetop"
require "brainfuck"
require "brainfuckext"
require "brainfuckast"
require "brainfuck_int"
code = <<-EOF
+++ +++ +++ + initialize counter (cell #0) to 10
[ use loop to set the next four cells to 70/100/30/10
> +++ +++ + add 7 to cell #1
> +++ +++ +++ + add 10 to cell #2
> +++ add 3 to cell #3
> + add 1 to cell #4
<<< < - decrement counter (cell #0)
]
>++ . print 'H'
>+. print 'e'
+++ +++ +. print 'l'
. print 'l'
+++ . print 'o'
>++ . print ' '
<<+ +++ +++ +++ +++ ++. print 'W'
>. print 'o'
+++ . print 'r'
--- --- . print 'l'
--- --- --. print 'd'
>+. print '!'
>. print '\n'
EOF
BrainfuckInterpreter.run(code)
O código está "comentado" (lembre-se que comandos não reconhecidos são ignorados). Se você rodar o programa agora, obterá o resultado desejado:
~$ ruby brainfuck_test.rb
Hello World!Pronto! Você agora possui um interpretador funcional--embora seriamente lento e incrivelmente complexo de se programar--de uma linguagem computacionalmente completa, capaz de realizar qualquer tarefa que você deseje executar.
Um outro teste interessante é rodar o código que imprime a canção 99 bottles of beer on the wall, cuja versão em Brainfuck é um pesadelo. Você verá que, embora lento, o código consegue imprimir as linhas com relativa facilidade.
Comparando a velocidade de uma versão Ruby e uma versão Brainfuck da canção temos os resultados (Ruby 1.9; iMac 2.8Ghz recente rodando Snow Leopard):
~$ time 99.bf
real 0m0.679s
user 0m0.586s
sys 0m0.045s
~$ time 99.rb
real 0m0.016s
user 0m0.006s
sys 0m0.006sDigamos que imprimir caracteres um a um não é uma forma eficiente de se trabalhar. Obviamente, double dispatching também não é uma técnica boa em todos os casos e vai adicionar um certo overhead em troca de flexibilidade. Mas, mesmo removendo o tempo de carga do Ruby, não haveria tantas melhoras no programa.
Conclusão
Como esse artigo vimos como fazer a cadeia completa de implementação, incluindo a implementação de um interpretador funcional. Mesmo que a implementação seja bem simples, as lições são as mesmas para qualquer outra linguagem e o limite está mais na sintaxe e semântica do que nas técnicas em si. Um exercício para o leitor é implementar um otimizador para Brainfuck que agrupe instruções iguais e efetue as operações em uma única passagem. Aqui, é claro, cabe uma aviso: implementações de linguagens generalizadas de programação obviamente precisam de muito mais do que isso para funcionar bem. O Treetop oferece uma conveniência quando velocidade máxima de execução não é o desejado e sim velocidade de implementação.
Com isso encerramos essa série sobre Treetop. Eventualmente, é possível que eu escreva um artigo sobre a implementação de uma linguagem menos minimalista, mas no momento não há tempo para isso. Espero que o tempo gasto lendo esses artigos tenha sido proveitoso.
Nota: Para ver a série completa, siga a categoria Treetop deste blog.
Bom, tenho alguma coisa para fazer nas férias, já que não deu para acompanhar (prá valer) toda a série.
Muito bom assim mesmo!