Treetop: Implementando Brainfuck

October 1st, 2009 § 1 comment

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
  
end

A 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
  
end

Efetivamente, 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
  
end

E 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
  
end

No 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
    
end

Esse 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
    
end

Esse 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
    
end

O 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
    
end

A 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
    
end

Para 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
  
    
end

A 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
    
end

E 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.006s

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

Tagged

§ One Response to Treetop: Implementando Brainfuck

Leave a Reply

Your email address will not be published. Required fields are marked *

What's this?

You are currently reading Treetop: Implementando Brainfuck at Superfície Reflexiva.

meta