LazyWeb: Escolhendo um framework

November 11th, 2009 § 7 comments § permalink

Um amigo de Belo Horizonte me consultou esses dias sobre uma questão fundamental para a aplicação que ele está planejando começar a escrever nos próximos dias: framework de programação usar (e por extensão, qual linguagem)?

Como minha experiência nos últimos tempos tem sido confessadamente restrita a Rails e alguns experimentos em outros, resolvi apelar para a caridade dos meus leitores. Qual framework você usaria para seu próximo projeto?

Esse meu amigo não tem problemas com linguagens de programação em si. De fato, a não ser que seja algo tão esotérico quando Haskell ou Erlang, ele é capaz de se familiarizar com uma linguagem ou framework em alguns dias.

Obviamente, não posso dar muitos detalhes sobre a aplicação, mas dá para dizer que o objetivo é escalar gradualmente. Ela não precisar começar escalando para o mundo inteiro, mas um caminho seria bom. Um outro detalhe nesse aspecto é que a aplicação é comparativamente particionada: um usuário terá acesso a alguns itens e compartilhará esse acesso com algumas dezenas ou centenas de pessoas. Esses itens possuem moldes variáveis e seriam bom ter flexibilidade na criação do mesmos.

Finalmente, hospedagem é uma questão também. Não necessariamente preço, mas facilidade. Linode é uma opção mas preferivelmente algo que possa ser colocado em alguma coisa pequena e ir escalando conforme a necessidade, no estilo do Heroku (o que limitaria a Rails, claro). Python parece uma boa opção, mas ele precisa de evidências.

E aí, alguém anima a ajudar um pobre compadre em armas? 😀

Treetop: Implementando Brainfuck

October 1st, 2009 § 1 comment § permalink

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.

Treetop: Depuração

September 30th, 2009 § 0 comments § permalink

Introdução

Continuando a série sobre Treetop, o objetivo desse artigo é falar um pouco sobre a depuração de gramáticas. Muitas vezes, o mecanismo de verificação do que a gramática está esperando, ilustrado no primeiro artigo, não é suficiente para identificar porque um reconhecimento está faltando–especialmente quando a gramática se torna mais complexa.

Parte da depuração consiste, na verdade, em tentar evitar erros mais primários. Outra parte consiste em usar alguns mecanismos para identificar problemas quando os erros primários já foram removidos. Falaremos de cada um deles na seqüência.

Evitando erros comuns

Um detalhe que deixei de fora no primeiro artigo é que uma PEG representa um parser descendente recursivo. E uma das fraquezas desse tipo de parser é que eles não são capazes de lidar com recursividade à esquerda.

Por exemplo, veja a regra abaixo:

string-of-a := string-of-a 'a' | 'a'

A lógica dita que isso deveria reconhecer uma seqüência de caracteres “a”. Na prática, isso não acontecer porque a regra está escrita de tal forma que para reconhecer a produção “string-of-a” seria necessário reconhecer “string-of-a” em seguida, o que leva, necessariamente, a recursividade infinita.

Existem packrat parsers que são capazes de lidar com isso mas não é o caso do Treetop. Existem técnicas formais para lidar com isso mas geralmente a melhor opção é criar uma regra que faça o processamento indireto do que se precisar e, com alguma criatividade, reescrever o necessário em uma fase posterior.

Para ilustrar ainda mais o ponto, veja a gramática abaixo que é uma variação da que estamos usando.

value := [0-9]+ / '(' expression ')'
product := expression (('*' / '/') expression)*
sum := expression (('+' / '-') expression)*
expression := product / sum / value

O problema com esse é que para saber o que é uma expressão, precisamos saber o que é um produto. Mas, para saber um produto, precisamos também saber o que é uma expressão.

A solução é simples:

expression := sum
sum := product (('+' / '-')) product)*
product := value (('*' / '/')) value)*
value := number / '(' expression ')'
number := [0-9]+

Um segundo ponto é utilizar apropriadamente operadores de lookahead para ajudar a remover ambigüidades da gramática. O uso dos mesmos é especialmente necessário por conta do modo como o operador de escolha ordenada trabalha. Como a segunda opção somente é considerada caso a primeira falhe, algumas vezes é necessário especificar cenários de falha na primeira para forçar a segunda a acontecer.

Suponha, por exemplo, que você tenha a seguinte gramática:

expression := numeric_expression / string_expression
numeric_expression := identifier ('+' identifier)*
string_expression := identifier ('||' identifier)*
identifier := [a-z]+

O problema dessa gramática é que a regra string_expression jamais será reconhecida. O que acontece é que para tentar descobrir se uma expressão é numérica, o parser precisa encontrar um identificador. Quando isso acontece, como a regra numeric_expression já possui um reconhecimento parcial, o parser tenta então encontrar o terminal +. Se isso não acontece–porque há um terminal ||–o parser aborta por não ter como seguir naquela regra.

Uma solução simples para resolver a ambigüidade é olhar para a frente e somente dizer que algo é uma expressão numérica se o identificador não for seguido por um operador que atue sobre strings. A gramática ficaria assim então:

expression := numeric_expression / string_expression
numeric_expression := identifier !'||' ('+' identifier)*
string_expression := identifier ('||' identifier)*
identifier := [a-z]+

Na maioria dos casos, isso é tudo o que você precisa para resolver a situação. Uma outra alternativa, é claro, é condensar as duas expressões, já que elas são essencialmente equivalentes, e fazer a diferenciação semântica em uma fase posterior (na análise semântica, mais ao ponto).

Um terceiro ponto é saber distinguir bem os separadores necessários para reconhecimento dos terminais. Em muitos casos, o modo mais simples é ideal. Algumas vezes, entretanto, é preciso usar alguma sofisticação. Para ilustrar, usando um exemplo da própria documentação do Treetop, teríamos algo como:

rule end_keyword
  'end' ![a-zA-Z0-9_]
end

Essa regra reconhece uma palavra chave end em uma linguagem em que palavras chaves podem ser seguidas por pontuação qualquer mas não por caracteres alfanuméricos.

Representações gráficas

Em muitos casos, é interessante visualizar o que o Treetop está reconhecendo. Para isso, uma característica interessante do mesmo adicionada em versões recentes é a habilidade de gerar um arquivo para o Graphviz. O uso é bem simples.

>> require "treetop"
=> true
>> require "simple_math"
=> true
>> p = SimpleMathParser.new
=> #
>> p.parse("1+2*3-(4/5)").write_dot_file("results")
=> nil

O resultado é um arquivo results.dot que pode ser processado em uma imagem como no exemplo abaixo:

~$ dot -Tpng results.dot > results.png

A imagem final ficaria assim:

Parsing 1+2*3-(4/5)

Essa é uma maneira fácil de ver como o Treetop reconhecer a sintaxe de maneira mais básica.

Capturando a execução

Uma última forma de capturar o resultado da execução é interceptar as chamadas do parser gerado pelo Treetop. Essa é a forma menos confiável porque depende do conhecimento da estrutura interna do Treetop, que pode mudar a qualquer momento. Apesar disso, mesmo com adaptações necessárias de quando em quando, é uma boa forma de saber o que o Treetop está fazendo por trás das cenas.

A primeira coisa a fazer é gerar o arquivo do parser em si:

~$ tt simple_math.rb

Isso gera o parser em sua forma final, ao invés de compilá-lo cada vez que o require é feito.

A partir disso, é possível construir sobre os módulos que o Treetop gerou. Existe um módulo default com o nome que foi dado a gramática–no nosso caso, esse módulo é o SimpleMath. Em um arquivo simplemathdebug.rb, poderíamos ter o seguinte código:

require "treetop"
require "simple_math"

module SimpleMath
  
  def __depth
    @__depth ||= 0
  end
  
  def __inc_depth
    @__depth = __depth + 1
  end

  def __dec_depth
    @__depth = __depth - 1
  end
  
end

SimpleMath.instance_methods.each do |method|
  
  next unless method =~ /^_nt_(.*)$/
  
  rule = $1
  
  SimpleMath.send(:alias_method, ("_old" + method).to_sym, method.to_sym)
  
  SimpleMath.send(:define_method, method.to_sym) do
    puts (" " * __depth) + rule
    __inc_depth
    result = send("_old" + method)
    __dec_depth
    result
  end  
  
end

O que o código acima faz é interceptar as chamadas aos métodos que começam com _nt_, que são os métodos que efetivamente implementam o reconhecimento de produções e rastrear a profundidade em que estão sendo chamados para exibir a ordem em que as mesmas foram feitos.

Veja um exemplo de chamada:

>> require "simple_math_debug"
=> true
>> p = SimpleMathParser.new
=> #
>> p.parse("1+2*3")
expression
 term
  factor
   number
  factor
 expression
  term
   factor
    number
   term
    factor
     number
    factor
  term
=> SyntaxNode+Expression0 offset=0, "1+2*3" (expression,term):
  SyntaxNode offset=0, "1":
    SyntaxNode offset=0, "1"
  SyntaxNode offset=1, "+"
  SyntaxNode+Term0 offset=2, "2*3" (factor,term):
    SyntaxNode offset=2, "2":
      SyntaxNode offset=2, "2"
    SyntaxNode offset=3, "*"
    SyntaxNode offset=4, "3":
      SyntaxNode offset=4, "3"
>> p.parse("1+")
expression
 term
  factor
   number
  factor
 expression
  term
   factor
    number
   factor
  term
 term

Essa é uma maneira simples de saber o que está acontecendo e de ver se há falhas no reconhecimento específico de alguma regra. Como algumas regras podem ser bem complexas em sua implementação, esse tipo de estratégia permite uma visualização das entradas e saídas dos métodos.

Conclusão

Embora o Treetop seja relativamente simples em sua implementação, em alguns momentos é preciso quebrar a abstração e olhar o que está sob o código externalizado. As técnicas acima podem ajudar a resolver problemas comuns que vão surgir durante a implementação de uma linguagem qualquer.

No próximo artigo, um bônus: uma linguagem Turing-complete implementada usando o Treetop para análise sintática.

Nota: Para seguir a série completa, siga a categoria Treetop deste blog.

Treetop: Usando árvores sintáticas

September 29th, 2009 § 0 comments § permalink

Introdução

Continuando a série sobre Treetop, vamos evoluir a utilização do parser de interpretação direta para um formato mais sofisticado que leve em conta outras características de processamento posterior. Na maioria dos casos, interpretação direta é suficiente para extrair da linguagem o necessário para a transformação ou execução. Algumas vezes, entretanto, as estruturas reconhecidas precisarão de algum refinamento ou recombinação posterior que fazer valer a pena um formato intermediário.

Para ilustrar isso, vamos usar a mesma gramática dos exemplos anteriores para gerar uma árvore sintática formalizada para as estruturas reconhecidas. E para fazer isso, vamos também usar algumas características adicionais do Treetop que gerar código mais elegante e com acoplamento menor.

Nossa gramática inicial permanece a mesma, como visto abaixo:

grammar SimpleMath

  rule expression
    term ('+' / '-') expression / 
    term
  end
  
  rule term
    factor ('*' / '/') term / 
    factor
  end
  
  rule factor
    '(' expression ')' / 
    number
  end
  
  rule number
    [0-9]+
  end
  
end

Usando módulos adicionais

Além de permitir a inserção de código Ruby diretamente na gramática, o Treetop permite duas outras formas de extensão da gramática. Uma dessas formas é definir classes específicas que herdam de SyntaxNode e permitem injeção de código manual no run-time do Treetop. Uma segunda forma, ainda mais elegante, é a definição de módulos que serão automaticamente utilizados pelo Treetop através do mecanismo usual de mixins do Ruby. Esse é o método que utilizaremos agora.

Vamos dizer que queremos transformar as produções reconhecidas pela linguagem definida por nossa gramática em uma árvore sintática específica para a mesma que possa ser guardada e posteriormente executada.

Obviamente, estamos usando uma linguagem tão simples que não há muitos benefícios em fazer isso. Mas, muitas vezes, isso faz sentido até por razões de performance. Digamos, por exemplo, que você esteja extraindo uma representação que será executada várias vezes com parâmetros diferentes. Não vale a pena executar o parsing a cada momento, utilizando o código diretamente injetado. Para esses momentos, uma representação sintática definida e específica para o domínio é bem mais interessante.

Para deixar as coisas mais interessantes, vamos modificar a nossa gramática acima para permitir que variáveis externas seja definidas e utilizadas, como por exemplo, para computar a expressão (b * b) - (4 * a * c) onde a, b e c são parâmetros variáveis fornecidos pelo ambiente de execução.

A gramática ficaria assim:

grammar SimpleMath

  rule expression
    term ('+' / '-') expression / 
    term
  end
  
  rule term
    factor ('*' / '/') term / 
    factor
  end
  
  rule factor
    '(' expression ')' / 
    primary
  end
  
  rule primary
    variable /
    number
  end
  
  rule variable
    [a-z]+
  end
  
  rule number
    [0-9]+
  end
  
end

Como é fácil perceber, não mudamos muita coisa. Existe agora uma regra adicional que define uma primária que pode ser um número ou uma variável e uma variável é simples um identificador alfabético simples.

Nossa árvore sintática será definida por uma coleção de nós com tipos que representam as várias estruturas que queremos ter no final. Por exemplo, queremos representar operações (um nó com um operador e dois operadores), variáveis e constantes. Essa é uma representação que definimos e que não necessariamente corresponde à árvore sintática reconhecida inicialmente pelo parser. Estamos transformando uma representação em outra.

A primeira coisa que precisamos, então é definir essas classes. Em um arquivo adicional, chamado simplemathast.rb, vamos inserir o seguinte código inicial:

class Constant
  
  def initialize(value)
    @value = value
  end
  
end

O código é trivial e, inicialmente, só define como vamos armazenar as informações. É fácil perceber que não estamos assumindo absolutamente nada sobre os dois operandos (left_side e right_side) na classe Operation. Os dois operandos podem ser outros nós da árvore tão complexos ou simples como necessário, ou seja, podem ser outras operações ou variáveis ou constantes.

O que precisamos agora é uma forma de construir a nossa árvore. Para isso, vamos interceptar a execução do parser usando módulos adicionais que serão inseridos nos nós sintáticos do Treetop para gerar o que precisamos.

A primeira coisa a fazer é adaptar a gramática. Como no artigo anterior, vamos começar de modo simples, reconhecendo somente números. A gramática ficaria assim:

grammar SimpleMath

  rule expression
    term ('+' / '-') expression / 
    term
  end
  
  rule term
    factor ('*' / '/') term / 
    factor
  end
  
  rule factor
    '(' expression ')' / 
    primary
  end
  
  rule primary
    variable /
    number
  end
  
  rule variable
    [a-z]+
  end
  
  rule number
    [0-9]+ <NumberPredicate>
  end
  
end

Veja a notação em negrito. Essa notação pede ao Treetop que introduza um módulo chamado NumberPredicate no nó sintático que reconhece números. Os métodos disponíveis no módulo serão, conseqüentemente, disponibilizados para o nó.

Para definir esse módulo, vamos usar um arquivo chamado simplemathext.rb com o seguinte conteúdo inicialmente:

module NumberPredicate
  
  def build
    Constant.new(text_value.to_f)
  end
  
end

O código define um módulo que será injetado no reconhecimento da produção number da gramática e que possui um método build que fará a construção inicial da árvore sintática. Esse método será usado para geração final da árvore. Vamos ver o método em execução no irb:

>> require "treetop"
=> true
>> require "simple_math_ast"
=> true
>> require "simple_math_ext"
=> true
>> require "simple_math_4"
=> true
>> p = SimpleMathParser.new
=> #
>> p.parse("1")
=> SyntaxNode+NumberPredicate offset=0, "1" (build):
  SyntaxNode offset=0, "1"
>> p.parse("1").build
=> #

Note como o nó sintático que representa o número agora possui automaticamente o módulo NumberPredicate adicionado e como o método build também faz parte do mesmo. Um problema que temos é a visualização da árvore, que pode ficar complicada à medida que mais nós são adicionados. Para resolver isso, uma maneira conveniente é utilizar S-expressions para gerar a visualização. A implementação é trivial:

class Constant
  
  def initialize(value)
    @value = value
  end
  
  def to_sexp
    [:constant, @value]
  end
  
end

E o resultado agora poderia ser visto com mais clareza:

>> p.parse("1").build.to_sexp
=> [:constant, 1.0]

A implementação de variáveis é similar. O nó da árvore sintática seria descrito no arquivo simplemathast.rb como mostrado abaixo:

class Variable
  
  def initialize(name)
    @name = name
  end
  
  def to_sexp
    [:variable, @name]
  end
  
end

class Constant
  
  def initialize(value)
    @value = value
  end
  
  def to_sexp
    [:constant, @value]
  end
  
end

Precisamos então criar o predicado que gera esse novo nó. No arquivo simplemathext.rb, o código ficaria assim:

module VariablePredicate

  def build
    Variable.new(text_value.downcase.to_sym)
  end
  
end

module NumberPredicate
  
  def build
    Constant.new(text_value.to_f)
  end
  
end

Finalmente, a gramática seria modificada para reconhecer isso:

grammar SimpleMath

  rule expression
    term ('+' / '-') expression / 
    term
  end
  
  rule term
    factor ('*' / '/') term / 
    factor
  end
  
  rule factor
    '(' expression ')' / 
    primary
  end
  
  rule primary
    variable /
    number
  end
  
  rule variable
    [a-z]+ <VariablePredicate>
  end
  
  rule number
    [0-9]+ <NumberPredicate>
  end
  
end

Usando o código, teríamos a possibilidade de fazer algo assim:

>> p.parse("x")
=> SyntaxNode+VariablePredicate offset=0, "x" (build):
  SyntaxNode offset=0, "x"
>> p.parse("x").build.to_sexp
=> [:variable, :x]

Implementar o nó que reconhece operações é também uma tarefa relativamente simples. Primeiro, temos o código do nó em si:

class Operation
  
  def initialize(operator, left_side, right_size)
    @operator = operator
    @left_side = left_side
    @right_side = right_size
  end
  
  def to_sexp
    [@operator, @left_side.to_sexp, @right_side.to_sexp]
  end
  
end

class Variable
  
  def initialize(name)
    @name = name
  end
  
  def to_sexp
    [:variable, @name]
  end
  
end

class Constant
  
  def initialize(value)
    @value = value
  end
  
  def to_sexp
    [:constant, @value]
  end
  
end

Note o uso recursivo dos lados esquerdo e direito na implementação do método to_sexp.

A implementação do predicado é um pouco maior agora já que precisamos lidar com dois casos: operações simples e expressões que estão entre parênteses (da mesma fora que fizemos no artigo anterior). A maneira mais simples é usar não um, mas dois predicados:

module NestedExpressionPredicate
  
  def build
    expression.build
  end
  
end

module OperationPredicate
  
  def build
    Operation.new(operator.text_value.downcase.to_sym, 
      operand1.build, operand2.build)
  end
  
end

module VariablePredicate

  def build
    Variable.new(text_value.downcase.to_sym)
  end
  
end

module NumberPredicate
  
  def build
    Constant.new(text_value.to_f)
  end
  
end

Usaremos o primeiro predicado para construir as expressões entre parênteses. Nesse caso, não precisamos construir a expressão simplesmente já que queremos somente ignorar os parênteses e construir a árvore da expressão aninhada. Por outro lado, o predicado da expressão já constrói um nó formal, da maneira que precisamos. Inserir isso na gramática é simples:

grammar SimpleMath

  rule expression
    operand1:term operator:('+' / '-') operand2:expression <OperationPredicate> / 
    term
  end
  
  rule term
    operand1:factor operator:('*' / '/') operand2:term <OperationPredicate> / 
    factor
  end
  
  rule factor
    '(' expression ')' <NestedExpressionPredicate> / 
    primary
  end
  
  rule primary
    variable /
    number
  end
  
  rule variable
    [a-z]+ 
  end
  
  rule number
    [0-9]+ 
  end
  
end

Note que estamos nomeando terminais para uso nos módulos. As regras são as mesmas que descrevemos no último artigo.

Com isso pronto, podemos reconhecer expressões inteiras:

>> p.parse("x").build.to_sexp
=> [:variable, :x]
>> p.parse("1+1").build.to_sexp
=> [:+, [:constant, 1.0], [:constant, 1.0]]
>> p.parse("x+1").build.to_sexp
=> [:+, [:variable, :x], [:constant, 1.0]]
>> p.parse("x+1-y").build.to_sexp
=> [:+, [:variable, :x], [:-, [:constant, 1.0], [:variable, :y]]]
>> p.parse("(b*b)-(4*a*c)").build.to_sexp
=> [:-, 
    [:*, [:variable, :b], [:variable, :b]], 
    [:*, [:constant, 4.0], [:*, [:variable, :a], [:variable, :c]]]]

A última linha foi quebrada para facilitar o entendimento da expressão gerada.

Se você observar agora somente o resultado de uma chamada ao método build, verá claramente que as estruturas estão aninhadas, com nós do tipo Operation codificando esse aninhamento.

É fácil perceber que não há muito mistério na criação de árvores sintáticas derivadas. Caso você queira ver um exemplo bem sofisticado disso, o projeto Cucumber é uma boa opção. Para parsing das estórias, o projeto usa um linguagem bem sofisticada descrita com o Treetop.

Interpretando a árvore sintática

Agora que temos uma árvore, podemos continuar executando a representação descrita pela árvore. Existem várias maneiras de fazer isso, mas a mais simples é usar a própria árvore recursivamente. Podemos criar um método run em cada nó que devolve o valor executado do mesmo. Esse método precisa receber algum tipo de ambiente para que variáveis possam receber seus valores. É fácil perceber que podemos gerar um árvore uma única vez e processá-la múltiplas vezes usado ambientes diferentes.

A maneira mais simples de implementar um ambiente é passar um hash que contenha as variáveis. A implementação, que é trivial, ficaria assim:

class Operation
  
  def initialize(operator, left_side, right_size)
    @operator = operator
    @left_side = left_side
    @right_side = right_size
  end
  
  def run(env = {})
    @left_side.run(env).send(@operator, @right_side.run(env))
  end
  
  def to_sexp
    [@operator, @left_side.to_sexp, @right_side.to_sexp]
  end
  
end

class Variable
  
  def initialize(name)
    @name = name
  end
  
  def run(env = {})
    env[@name] || (raise "The variable #{@name} is undefined")
  end
  
  def to_sexp
    [:variable, @name]
  end
  
end

class Constant
  
  def initialize(value)
    @value = value
  end
  
  def run(env = {})
    @value
  end
  
  def to_sexp
    [:constant, @value]
  end
  
end

Estamos usando exatamente a mesma técnica descrita no artigo anterior, recursivamente operando sobre a árvore para chegar a um resultado final. A diferença é que, nesse caso, estamos utilizando somente três tipos de nós nomeados. Poderíamos, é claro, ter feito algo mais sofisticado usando um nó diferente para cada operação mas isso seria mais do que precisamos no momento.

O código em operação ficaria assim:

>> require "rubygems"
=> false
>> require "treetop"
=> true
>> require "simple_math_ext"
=> true
>> require "simple_math_ast"
=> true
>> require "simple_math_4"
=> true
>> p = SimpleMathParser.new
=> ...
>> ast = p.parse("(b*b)-(4*a*c)").build
=> ...
>> ast.run(:a => 1, :b => 2, :c => 3)
=> -8.0
>> ast.run(:a => 0, :b => 2, :c => 10)
=> 4.0
>> ast.run(:a => 3.2, :b => 4.1, :c => 1.8)
=> -6.23
>> ast.run(:a => 0, :c => 0)
RuntimeError: The variable b is undefined

Alguns resultados foram elididos na representação acima mas é fácil ver como o código funciona. Mesmo o caso em que uma variável não é declarada, é possível capturar e processar o erro. De certa forma, isso representa um nível incipiente de análise semântica do código–que, nesse caso, aborta na primeira tentativa. Seria igualmente possível continuar o processamento e capturar todas as variáveis não declaradas de uma só vez.

Conclusão

Nesse artigo vimos que é possível processar o reconhecimento de uma linguagem qualquer com o parser gerado pelo Treetop em qualquer nível de sofisticação desejado. Obviamente, o exemplo que estamos usando é bem simples mas a mesma técnica poderia ser usada para realizar qualquer tipo de interpretação ou compilação desejada.

Um extensão possível do código acima, que pode ficar como um exercício, é implementar algum sistema de double dispatching para realizar geração de código (C, por exemplo), que faça o trabalho necessário.

No próximo artigo, veremos algumas técnicas rápidas para a depuração básica e identificação de erros em gramáticas Treetop.

Nota: Para seguir a série completa, siga a categoria Treetop deste blog.

Treetop: Interpretação direta

September 28th, 2009 § 2 comments § permalink

Introdução

Continuando a série sobre Treetop, é hora de ver como realmente utilizar um parser para produzir resultados de execução. Até o momento, vimos somente como montar a gramática e como obter uma árvore que pode ser utilizada de alguma forma.

Como a árvore sintática que o parser gera já é bem completa, a tentação seria de usar a mesma e processá-la recursivamente através de um rotina que identificasse os dados necessários ou alguma espécie de pattern com o Visitor.

Não é uma estratégia de todo ruim, mas o Treetop provê mecanismos para ajudar nisso sem a necessidade de processar a árvore diretamente nó a nó; antes, é possível processar somente os nós necessários e já fazer algum tipo de interpretação direta dos elementos reconhecidos da linguagem.

Esse processamento pode ser feito de duas maneiras. Primeiro, pela injeção de código Ruby diretamente no parser, permitindo o processamento posterior através de algum callback. Segundo, pela construção de alguma árvore sintática específica à linguagem que espelhe a árvore inicial gerada mas de uma maneira mais processável, por assim dizer.

O tema desse artigo é a primeira técnica, que veremos logo a seguir.

Introduzindo código Ruby no parser

Vamos voltar a nossa gramática inicial:

grammar SimpleMath

  rule expression
    term ('+' / '-') expression / 
    term
  end
  
  rule term
    factor ('*' / '/') term / 
    factor
  end
  
  rule factor
    '(' expression ')' / 
    number
  end
  
  rule number
    [0-9]+
  end
  
end

Digamos que queremos ter o resultado da expressão aritmética que está sendo reconhecida pela linguagem. O processo não é complicado.

Obviamente, precisamos começar tendo o valor dos números que compõem a unidade final da gramática. Em seguida, pelo modo como nossa gramática está estruturada, precisamos ter o valor da multiplicação ou divisão entre fatores e termos, expresso pela segunda regra. E assim por diante.

Uma pergunta é: por que não precisamos de processar cada um das regras. A resposta está na própria forma como a gramática é reconhecida. Em última instância, por exemplo, um termo é também um fator (como expresso pela segunda opção dentro da regra term). E, pelo mesmo ponto de vista, um fator, em última instância pode ser um número. Isso implica que em alguns casos, basta o reconhecimento da regra final para permitir o acesso.

Vamos aplicar, então, esse conhecimento à gramática, reconhecendo inicialmente números. A gramática ficaria assim:

grammar SimpleMath

  rule expression
    term ('+' / '-') expression / 
    term
  end
  
  rule term
    factor ('*' / '/') term / 
    factor
  end
  
  rule factor
    '(' expression ')' / 
    number
  end
  
  rule number
    [0-9]+ {
      def eval
        text_value.to_f
      end
    }
  end
  
end

Note o código Ruby entre as chaves, em negrito. Essa é a forma que o Treetop usa para inserir código diretamente dentro do nó sintático que aquela regra representa.

O código acima introduz um novo método chamado eval ao nó que reconhece a regra números. Esse código diz que o valor daquele nó é o seu valor textual convertido para um número de ponto flutuante. O método text_value é inerente ao Treetop e existe em todos os nós.

Podemos usar agora isso da seguinte maneira:

>> require "treetop"
=> true
>> require "simple_math"
=> true
>> p = SimpleMathParser.new
=> #
>> p.parse("1")
=> SyntaxNode+Number0 offset=0, "1" (eval):
  SyntaxNode offset=0, "1"
>> p.parse("1").eval
=> 1.0

Note duas coisas. Primeiro, o método eval está disponível diretamente na árvore sintática, como mostrado pelo resultado do parsing. Segundo, embora a regra inicial da gramática seja expression, somente a regra number foi reconhecida dessa vez. Isso prova o que foi explicado acima, sobre o cascateamento de expressões.

Note também o uso de próprio nome de uma regra (expression nesse caso) dentro do método. Qualquer não-terminal dentro de uma regra será exposto pelo Treetop dessa forma.

Vamos agora evoluir para reconhecer fatores, a regra imediatamente acima que usa números ou reconhece uma expressão dentro de parênteses. A idéia é a mesma e a implementação é igualmente simples.

grammar SimpleMath

  rule expression
    term ('+' / '-') expression / 
    term
  end
  
  rule term
    factor ('*' / '/') term / 
    factor
  end
  
  rule factor
    '(' expression ')' {
      def eval
        expression.eval
      end
    } /
    number
  end
  
  rule number
    [0-9]+ {
      def eval
        text_value.to_f
      end
    }
  end
  
end

Agora é possível fazer a interpretação de expressões como a mostrada abaixo, o que constrói o nosso próximo nível:

>> require "treetop"
=> true
>> require "simple_math"
=> true
>> p = SimpleMathParser.new
=> #
>> p.parse("(1)")
=> SyntaxNode+Factor1+Factor0 offset=0, "(1)" (expression,eval):
  SyntaxNode offset=0, "("
  SyntaxNode+Number0 offset=1, "1" (eval):
    SyntaxNode offset=1, "1"
  SyntaxNode offset=2, ")"
>> p.parse("(1)").eval
=> 1.0

Com isso pronto, é hora de reconhecer multiplicação e divisão, ou seja, operações sobre termos, o nosso próximo item nas regras. A modificação não é muito mais complexa:

grammar SimpleMath

  rule expression
    term ('+' / '-') expression / 
    term
  end
  
  rule term
    factor operator:('*' / '/') term {
      def eval
        factor.eval.send(operator.text_value.to_sym, term.eval)
      end
    } / 
    factor
  end
  
  rule factor
    '(' expression ')' {
      def eval
        expression.eval
      end
    } /
    number
  end
  
  rule number
    [0-9]+ {
      def eval
        text_value.to_f
      end
    }
  end
  
end

Esse código faz uso de uma característica nova do Treetop: a possibilidade de nomear um não-terminal ou terminal reconhecido para uso na implementação internal. No caso acima, como o resultado do reconhecimento da regra pode ser tanto o sinal de adição quando o de multiplicação dentro da escolha ordenada entre parênteses, precisamos de uma forma para referenciar isso. O label colocado à frente do não-terminal se encarrega disso, criando um novo método que o representa e pode ser usado como qualquer outro termo interno.

O código também faz uso do fato de que o Ruby é uma linguagem (quase que) 100% orientada a objetos e que mesmo elementos primitivos da linguagens podem receber mensagens.

Para que não conhece detalhes do Ruby, essencialmente, o código acima faz o seguinte:

  • Avalia o fator, o lado esquerdo da expressão. Esse método eval foi introduzido no passo anterior;
  • Avalia o termo restante, o lado direito da expressão;
  • Finalmente, envia o método representado pelo operador ao termo, com o parâmetro sendo o resultado do termo.

Digamos que o fator tenha tido como resultado 2 e o termo tenha tido o resultado 3 como o operador +. A expressão final é equivalente a:

2.send(:+, 3) # => 2 + 3 = 5

Para fechar a interpretação, o código que lida com termos é o mesmo:

grammar SimpleMath

  rule expression
    term operator:('+' / '-') expression {
      def eval
        term.eval.send(operator.text_value.to_sym, expression.eval)
      end
    } / 
    term
  end
  
  rule term
    factor operator:('*' / '/') term {
      def eval
        factor.eval.send(operator.text_value.to_sym, term.eval)
      end
    } / 
    factor
  end
  
  rule factor
    '(' expression ')' {
      def eval
        expression.eval
      end
    } /
    number
  end
  
  rule number
    [0-9]+ {
      def eval
        text_value.to_f
      end
    }
  end
  
end

Agora é possível rodar expressões arbitrárias como demonstrado abaixo:

>> require "treetop"
=> true
>> require "simple_math"
=> true
>> p = SimpleMathParser.new
=> #
>> p.parse("1+2*3").eval
=> 7.0
>> p.parse("(1+2)*3").eval
=> 9.0
>> p.parse("(1+2)*(3-4)").eval
=> -3.0
>> p.parse("(1+2)*(3-4/5)").eval
=> 6.6

Como é possível ver, as regras de precedência normais são reconhecidas. Isso acontece pela forma como a gramática foi desenhada e não por causa de propriedades inerentes da linguagens.

Caso fosse possível acompanhar a execução de cada expressão acima, seria fácil perceber que os métodos são recursivamente invocados para gerar o resultado final, ou seja, para a expressão (1+2)*(3-4/5), o processo acontece da seguinte forma:

      1.0 +
      2.0
    3.0
  3.0 *
      3.0 -
          4.0 /
          5.0
      0.8
    2.2
  2.2 =
6.6

Conclusão

Como esse artigo demonstra, introduzir código Ruby em um parser gerado pelo Treetop é algo bem simples e facilmente controlável. Embora o artigo tenha mostrado somente a inserção de um método simples, é possível introduzir qualquer quantidade de métodos, públicos ou não, para utilização.

Por exemplo, para uma gramática um pouco diferente (mostrada abaixo de forma incompleta), utilizando não-terminais para operadores, seria simples fazer algo do tipo:

grammar SimpleMath

  rule expression 
    operand1:term operator:SUM_OP operand2:expression {
      operator.apply(operand1, operand2)
    } / 
    term 
  end
  
  rule SUM_OP 
    '+' {
      def apply(operand1, operand2)
        operand1 + operand2
      end
    } / 
    '-' {
      def apply(operand1, operand2)
        operand1 - operand2
      end
    }
  end    
  
   # ...
  
end

Como é possível ver, não há limite para o que se possa fazer com essa técnica.

Até o momento, vimos como usar uma gramática para não só reconhecer uma linguagem formal como também para executar instruções sobre essa linguagem. Na maioria dos casos, isso é suficiente mesmo para tarefas mais complexas. Entretanto, algumas vezes é necessário utilizar um reconhecimento mais sofisticado. Esse será o tema do próximo artigo.

Nota: Para seguir a série completa, siga a categoria Treetop deste blog.

Treetop: Básico

September 25th, 2009 § 10 comments § permalink

Introdução

Uma das tarefas mais comuns em programação é transformar uma representação qualquer de dados e/ou código em outra necessária para a execução de uma tarefa.

Quem acompanha o meu blog há mais tempo, sabe que eu sou um grande fã de Domain Specific Languages, uma das formas de fazer esse tipo de transformação sem sair do escopo da própria linguagem em que se está desenvolvendo. Muitas vezes, entretanto, é necessário algum tipo de conversão mais específica–uma compilação, por assim dizer.

Existem várias formas de fazer esse tipo de compilação mais específica, que podem ser baseadas em estruturas tão “simples” como expressões regulares a estruturas bem mais complexas como gramáticas livre de contexto (CFG) que lidam com ambigüidades e recursividade de maneira mais completa. De uma forma mais simples, tanto expressões regulares como CFGs são linguagens formais que, por sua vez, expressam como uma outra linguagem específica pode ser gerada ou analisada para criar a transformação necessária.

Esse tipo de formalização é válida para qualquer transformação e é exatamente a mesma técnica, por exemplo, aplicada na descrição de uma linguagem de programação. O que varia, na maioria dos casos, é a complexidade final da linguagem que está sendo descrita, que limita o tipo de gramática e formalização que precisa ser usada. Para ilustrar isso, considere o seguinte exemplo em C:

x * y;

A princípio, isso pode ser interpretado como uma simples multiplicação de duas variáveis x e y cujo valor é descartado sem ser usado. Por outro lado, isso também pode ser interpretado com a declaração de uma variável y que é um ponteiro deferenciado do tipo x. Esse tipo de ambigüidade e complexidade limita quais ferramentas e técnicas podem ou precisam ser utilizadas. Um exemplo final dessa ambigüidade é o problema do else solto.

Nos últimos anos, uma técnica ou ferramenta que tem surgido com uma alternativa para tornar o trabalho de definição de linguagens e transformações de maneira mais fácil são as Parsing Expression Grammars, das quais o Treetop, assunto desse artigo, é um gerador.

Uma parsing expression grammars (ou PEG) é um tipo de gramática formal que descreve uma linguagem e pode ser usada para criar a base de uma transformação mais específica e mais poderosa do que uma simples linguagem de domínio baseada em uma linguagem de programação qualquer.

Uma característica fundamental de uma PEG é que ela é, por definição, analítica, isto é, ela reconhece texto em uma linguagem e gera uma árvore sintática do que reconheceu--ou, obviamente, falha. Isso difere da capacidade geradora de outras classes de gramáticas que são capazes, como o nome indica, de gerar todas as possíveis expressões representadas por uma linguagem formal.

Uma outra característica fundamental de uma PEG é que ela não pode ser ambígua. Dado um texto qualquer a ser reconhecido como uma parte de linguagem, aquele texto possui uma e somente uma árvore sintática. Isso não quer dizer que a linguagem não seja capaz de ter construtos ambíguos--eles somente não serão reconhecidos diretamente na fase em que a PEG está envolvida e requerem algum processamento posterior. Significa, entretanto, que se há alguma ambigüidade inerente na linguagem que precise ser resolvida em tempo de análise sintática, uma PEG não será capaz de lidar com a mesma.

Finalmente, uma terceira característica de uma implementação de PEG é que a fase de análise léxica e análise sintática são feitas de uma única vez.

Para terminar com essa breve introdução teórica--que, por admissão, nem arranha a superfície do assunto--um item final é que a implementação do parser de uma PEG possui certas características de performance de execução que podem inviabilizar a implementação de uma gramática qualquer. Para lidar com isso, normalmente a implementação é feita usando um packrat parser, que é uma forma de implementação que troca uso de memória para conseguir rodar em tempo linear. Basta dizer que o Treetop é um exemplo desse tipo de gerador, criando packrat parser em Ruby puro.

Descrevendo uma PEG

A descrição de uma PEG, ou seja, a formalização de qual linguagem a mesma reconhece usa uma notação que mistura elementos de expressões regulares e BNF, com uma interpretação ligeiramente diferente para tornar o reconhecimento mais simples.

Os elementos fundamentais dessa notação são:

  • Uma regra de início da gramática
  • Um conjunto de terminais, isto é, elementos que geram uma representação final da linguagem, que não podem ser quebrados em unidades menores sem perder significado
  • Um conjunto de não-terminais, isto é, elementos que podem ser decompostos em outros, inclusive em referências a si próprios
  • Um conjunto de regras que descrevem essa decomposição

Essas regras podem ser definidas pelos seguintes operadores:

  • Seqüência: e1 e2 -- a regra é composta por esses dois elementos na ordem dada
  • Escolha ordenada: e1 / e2 -- a regra é composta por um ou outro dos elementos
  • Zero ou mais: e*
  • Um ou mais: e+
  • Opcional: e?
  • Predicado E: &e
  • Predicado Não: !e

A regra acima que explica a diferença essencial entre uma PEG e uma CFG é que o operador de escolha é ordenado, ist é, se a primeira alternativa tem sucesso, a segunda é completamente ignorada. Não existe então a possibilidade de que duas árvores sintáticas sejam geradas. Em caso de ambigüidade, a escolha ordenada pode ser usada para escolher uma cominho específico.

Além disso, os predicados E e Não podem ser usados para remover ainda mais ambigüidades por permitir olhar à frente nas regras que estão sendo analisadas e tomar decisões com base nisso. Por exemplo, é possível dizer que uma regra qualquer é válida desde que não seja seguida por tais e tais construtos. A possibilidade de olhar à frente (lookahead) de maneira ilimitada é responsável pelas complicações mencionadas acima que requerem a implementação de packrat parsers.

Para dar um exemplo de uma gramática e tornar esse questão toda mais real, vamos olhar uma gramática capaz de reconhecer expressões matemáticas simples:

expression := term ('+' / '-') expression / term
term := factor ('*' / '/') term / factor
factor := '(' expression ')' / number
number := [0-9]+

A gramática acima descreve as seguintes regras:

  • Uma expressão é um termo, seguido de um operador de adição ou subtração, seguido de uma outra expressão OU um simples termo;
  • Um termo, por sua vez, é um fator seguido de uma operador de multiplicação ou divisão, seguido por um outro termo OU um simples fator;
  • Um fator é uma expressão entre parênteses OU um número;
  • Finalmente, um número é uma seqüência de um ou mais dígitos.

Note o uso do operador de escolha ordenada para descrever as regras. Por ser ordenado, o operador automaticamente estabelece regras de precedência, ou seja, uma adição, por aparecer primeiro, tem maior precedência do que uma subtração. O mesmo é válido para a multiplicação e divisão.

Por outro lado, isso não significa que haja automaticamente uma precedência específica entre regras diferentes. No caso acima, pela forma como as regras estão estruturadas, multiplicação e divisão possuem maior precedência do que subtração e adição por serem reconhecidas primeiro.

Uma outra maneira de descrever a mesma gramática é:

expression := sum
sum := product (('+' / '-')) product)*
product := value (('*' / '/')) value)*
value := number / '(' expression ')'
number := [0-9]+

Ambas as formalizações acima descrevem a mesma gramática de formas diferentes. A árvore final gerada será diferentes mas tem a mesma interpretação. A grande diferença, talvez, seja que a segunda gramática é mais fácil de entender do que a primeira, embora mais difícil de ser estendida.

Essa gramática descreve as seguintes regras:

  • Uma expressão é uma soma;
  • Uma soma é uma seqüência de zero ou mais adições ou subtrações de produtos;
  • Um produto é uma seqüência de zero ou mais multiplicações ou divisões de valores;
  • Um valor é um número ou uma expressão entre parênteses;
  • Finalmente, um número é uma seqüência de um ou mais dígitos.

Dependendo de como o parser é gerado, pode ser mais ou menos fácil lidar com uma gramática em particular. Nesse caso, a escolha de quais produções são especificadas pela gramática pode ser crucial para facilitar a implementação da linguagem.

Note que as gramáticas acima não descrevem reconhecimento de espaços brancos entre as produções. A gramática acima reconheceria 1+2*3 mas não 1 + 2 * 3. Para mudar isso, algo a mais ter que ser definido. Mostrando um pedaço de uma gramática adaptada, as regras ficaram, por exemplo:

value := [0-9]+ / '(' spaces? expression spaces? ')'
spaces := [ \t\r\n]+

Essa é uma visão simples do processamento de espaços opcionais, mas válida.

Usando o Treetop

Depois de toda essa introdução é hora de finalmente colocar o Treetop em ação. Assumindo que você tenha uma versão recente do Ruby, a instalação do Treetop é simples:

~$ sudo gem install treetop

Com o Treetop instalado, podemos escreve a nossa gramática. Não coincidentemente, a sintaxe do Treetop é uma PEG em também--para completar, inclusive, o Treetop possui é capaz de fazer o seu próprio bootstrap e esse é o seu método atual de desenvolvimento.

A sintaxe é bastante trivial. Usando a primeira gramática acima de exemplo, teríamos algo assim:

grammar SimpleMath

  rule expression
    term ('+' / '-') expression / term
  end
  
  rule term
    factor ('*' / '/') term / factor
  end
  
  rule factor
    '(' expression ')' / number
  end
  
  rule number
    [0-9]+
  end
  
end

Essa é uma forma simples e direta de expressar a gramática. É possível, porém, ter uma gramática tão sofisticada e legível quanto se deseje. Veja a mudança abaixo para descrever exatamente a mesma gramática de maneira um pouco mais legível:

grammar SimpleMath

rule expression term SUM_OP expression / term end

rule term factor MUL_OP term / factor end

rule factor LPARENS expression RPARENS / number end

rule number [0-9]+ end

rule SUM_OP '+' / '-' end

rule MUL_OP '*' / '/' end

rule LPARENS '(' end

rule RPARENS ')' end

end

A diferença é que está possui mais elementos não-terminais--o que não impacta de forma alguma o processamento da mesma--mas impacta talvez seu uso já que elementos que seriam anteriormente inseridos diretamente na árvore como terminais, não gerando sub-expressões, agora o fazem. Veremos mais sobre isso adiante.

Usar a gramática acima, é fácil. Digamos que a gramática tenha sido salva em um arquivo chamado simple_math.rb. Para carregar isso em um programa Ruby, basta usar:

require "treetop"
Treetop.load "simple_math"

O resultado é a disponibilização de um parser chamada SimpleMathParser que reconhece a gramática em questão. Se o arquivo possui a extensão .treetop é possível usar require diretamente:

require "treetop"
require "simple_math"

Para usar o parser, basta instanciá-lo e tentar o parsing de uma expressão qualquer:

>> require "treetop"
=> true
>> require "simple_math"
=> true
>> p = SimpleMathParser.new
=> #
>> p.parse("1+2*3")
=> SyntaxNode+Expression0 offset=0, "1+2*3" (term,expression):
  SyntaxNode offset=0, "1":
    SyntaxNode offset=0, "1"
  SyntaxNode offset=1, "+"
  SyntaxNode+Term0 offset=2, "2*3" (factor,term):
    SyntaxNode offset=2, "2":
      SyntaxNode offset=2, "2"
    SyntaxNode offset=3, "*"
    SyntaxNode offset=4, "3":
      SyntaxNode offset=4, "3"

Note o resultado de um parsing bem sucedido: uma árvore sintática válida que expressa cada elemento da linguagem e o que foi reconhecido em cada ponto da mesma. Note que a árvore possui um detalhamento preciso de cada nó, incluindo terminais e não terminais.

Note que cada nó da árvore sintática é uma instância da classe SyntaxNode anotada com elementos que fornecem uma indicação do que aquele nó representa. Os nomes Expression0 e Term0 representam módulos Ruby que implementam detalhes dos nós sintáticos. Da mesma forma, os nomes entre parênteses (term, expression, etc) são as partes da linguagem reconhecidas dentro daquele nó.

Caso você queira ver o parser como ele realmente foi gerado, basta fazer o seguinte:

~$ tt simple_math.treetop

Um arquivo simple_math.rb será gerado com a implementação do parser em si. O código é bem legível e demonstra como o Treetop faz o reconhecimento descendente e mutuamente excludente dos terminais e não-terminais.

Continuando, vejamos o que acontece em caso de falha:

>> p.parse("1+2*")
=> nil
>> p.failure_reason
=> "Expected ( at line 1, column 5 (byte 5) after *"

Como essa é uma gramática simples, a mensagem pode não ser tão informativa. Mesmo assim, ela fornece uma indicação precisa do que é esperado e fica para o implementador a tarefa de converter isso em mensagens úteis de acordo com o contexto necessário.

Um exercício interessante, que fica para o leitor, é fazer com que a gramática anterior seja capaz de reconhecer espaços.

Conclusão

Até o momento, vimos uma breve introdução teórica e como criar a gramática em si. Ter somente a capacidade de reconhecer uma linguagem, entretanto, não é algo muito útil. Precisamos agora fazer um uso das informações. Para isso, o Treetop oferece duas formas bem convenientes de acessar o que a árvore sintática reconhecida. No próximo artigo, portanto, veremos como fazer esse uso.

Nota: Para seguir a série completa, siga a categoria Treetop deste blog.

Eu fico com a baleia

April 8th, 2009 § 23 comments § permalink

Essa história toda do Twitter me impressionou particularmente por um aspecto: como pessoas que jamais tiveram experiência com sistemas de grande porte acham que são capazes de dar opiniões completamente válidas sobre os mesmos (independentemente de que linguagem usam ou preferem).

Eu não vou ofender meus leitores dizendo que tenho vasta experiência no assunto, e também não vou cometer o erro de dizer que sei alguma coisa a mais do que um bom engenheiro de software saberia. Minha experiência mais recente com o assunto–atual, por assim dizer–é acompanhar o desenvolvimento de uma aplicação que no momento serve 60 milhões de page views por mês e cujo crescimento mensal tem sido constante pelos últimos meses.

Essa aplicação é escrita inteiramente em Ruby on Rails e olhando os desafios que manter, evoluir e operar essa aplicação representam, eu já tenho toda simpatia pelos engenheiros do Twitter. Manter uma aplicação do porte do Twitter no ar, com toda a complexidade distribuída que o núcleo do mesmo precisa é algo para se aplaudir.

O que torna mais impressionante como as pessoas são rápidas para assumir que o código do Twitter é uma completa porcaria. Mesmo que fosse–e mesmo assumindo que pode ser–as críticas nesse aspecto ainda são completamente inválidas. Por mais que uma aplicação acrua débitos ténicos, o balanço entre os mesmos e o valor entre ao usuário–que é inegável no caso do Twitter–é uma decisão de negócio inquestionável.

Martin Fowler fala muito bem desse balanço um texto seu sobre débitos ténicos:

The metaphor also explains why it may be sensible to do the quick and dirty approach. Just as a business incurs some debt to take advantage of a market opportunity developers may incur technical debt to hit an important deadline. The all too common problem is that development organizations let their debt get out of control and spend most of their future development effort paying crippling interest payments.

Do meu ponto de vista, o fato de que o Twitter experimentou com outras tecnologias, fez benchmarks de plataformas, procurou melhores soluções é uma indicador claro de que estão tentando resolver seus débitos. Pedir mais do que isso é assumir uma postura de arrogância e desconhecimento, principalmente de como negócios são operados e de como código real é produzido.

Admitir publicamente problemas e tentar criar um discurso é algo que respeito; dizer coisas do tipo “As far as I’m concerned, Twitter is a case-study in how Ruby on Rails does scale, even in their hands”, por outro lado, é algo que tira qualquer possibilidade de um discurso racional. Os fanboys e pundits da comunidade Rails tem muito do que se envergonhar no seu tratamento da questão.

Programadores não operam em mundos ideais. E até que os detratores do Twitter me mostrem que fizeram o seu dever de casa em lidar com essas questões, eu fico com o Twitter e sua baleinha simpática. Proper for humans, after all.

O brouhaha sobre o Twitter e por que evangelistas puristas de linguagens/frameworks são imbecis

April 5th, 2009 § 10 comments § permalink

O cantinho de desenvolvimento de Rails na Web está quente de novo com a discussão sobre o fato de que o Twitter está reescrevendo alguns de seus sistemas de backend em Scala (1, 2, 3. 4). A coisa toda começou com a palestra que o Alex Payne, desenvolvedor responsável pela API do Twitter, deu no Web 2.0 Expo SF.

Obviamente, os evangelistas do Rails já pularam em cima da oportunidade para despejar baboseira sobre o assunto como se a questão fosse a mais importante do mundo e como se o mundo Rails estive para implodir depois das declarações bombásticas do Alex Payne.

Eu me rio.

Eu estou indo para uma década e meia de desenvolvimento esse ano, quase todos na Web. Não é muito mas foi o suficiente para por sistema em produção usando Object Pascal, C/C++, VBScript, PHP, Python, Ruby, Perl, Java, C#, Smalltalk para citar algumas das linguagens que já usei em vários e vários frameworks. Caramba, eu cheguei a desenvolver um framework Web mais um ORM em Delphi que foram usados em produção para um sistema durante quatro anos até que o projeto foi eventualmente reescrito em alguma coisa mais recente depois que eu já saíra do mesmo há muito.

O que eu aprendi nesse anos em relação a linguagens e frameworks é que todos são bons e todos são ruins e que evangelismo purista é uma das expressões mais ridículas no mundo de desenvolvimento. Qualquer desenvolvedor que se sinta compelido a defender sua linguagem/framework (e pior, os que fazem isso uma carreira como os vários Javamen, Rubymen, Scalamen, Whatever-Language-Men que existem por aí) não merecem um aceno patético de respeito.

Eu assisti a palestra do Payne na Web 2.0 Expo e o que vi foi alguém em amor com uma tecnologia nova. A palestra (como a maioria das outras técnicas no evento) foi corrida e não apresentou nada concreto. De fato, durante quase 20 minutos tudo o que Payne fez foi falar sobre as características de Scala e como ela é fantástica sem apresentar um exemplo de código que fosse. Foi o suficiente para despertar curiosidade sobre a linguagem mas não prova nada–como não deveria. No meio da apresentação, Payne fez a declaração que suscitou a ira da comunidade Rails: O Twitter está movendo vários dos seus sistemas de backend para Scala onde o Ruby não está agüentando. Por algum motivo, isso foi distorcido para dizer que Rails não escala e o resto é história.

Eu já dei minha resposta sobre a questão do Rails escalar ou não em um tom mais irônico mas as pessoas parecem gostar de perder tempo sobre isso. Evangelistas de Rails, principalmente, adoram a questão. Parece que há um fator magnético associado à afirmação. Fale isso e caem dúzias de Railers incensados do céu.

O fato de que tecnologias não escalam mas design sim parece passar inteiramente despercebido. Eu já vi sistemas limpos em Rails que não são capazes de servir pouco mais do que algumas dezenas de usuários em hardware similar ao que a empresa para qual eu trabalho usa para extrair 60 milhões de requisições por mês de um backend em puro Rails. Rails escala? Pergunta errada.

Assim, quando um Obie Fernandez diz que sua resposta evangelística ao evangelístico Payne é razoável, eu digo: Bullshit! (Só não vou dizer que é pior porque veio do homem que quer o mercado Rails todo para si porque seria maldade. Ops, que maldade…) Mais engraçado do que isso só ver nego pulando de uma conclusão para outra usando o mesmo artigo como base para evitar ficar associado com o estigma. Sigh…

Anyway, para resumir meus devaneios aqui. Se você é um programador de uma linguagem/framework só que precisa defender sua tecnologia a cada rumor, precisa seriamente repensar sua carreira. Eu, por mim, acredito em segundas chances.

Flog, analisando complexidade em Ruby

November 13th, 2008 § 0 comments § permalink

Flog é outro analisador de complexidade para Ruby. Diferentemente do Saikuro, que mede a complexidade ciclomática real do código, o Flog tem o propósito de mostrar padrões de tortuosidade no seu código. É mais uma ferramenta interessante e de fácil uso para analisar a evolução da complexidade do seu código:

Instalação

Para instalar o Flog, basta rodar o comando gem:

~$ sudo gem install flog

Esse comando instala a gem em si e um executável que pode ser usado na linha de comando.

Um programa de exemplo

Para demonstrar o uso da ferramenta, vamos utilizar o mesmo exemplo que mostrarmos no artigo sobre o uso do Saikuro.

require "test/unit"

class DocumentHasher

def initialize(object, options = {}) @object = object @options = options end

def hash hash = { :id => @object.id } if @options[:fields] @options[:fields].each do |field| hash[field] = @object.send(field) end end if @options[:extrafields] @options[:extrafields].each do |field| hash[field] = @object.send(field.tos + "field") end end hash end

def self.hash(object, options = {}) self.new(object, options).hash end

end

class DocumentHasherTest < Test::Unit::TestCase

Struct.new("HashExample", :id, :title, :author)

TITLEFIELD = "Test" AUTHORFIELD = "Author" EXTRA_FIELD = "Extra"

def setup @object = Struct::HashExample.new(1, TITLEFIELD, AUTHORFIELD) class << @object def extra_field "Extra" end end end

def testhashid result = DocumentHasher.hash(@object) assert_equal 1, result[:id] end

def testhashfields result = DocumentHasher.hash(@object, :fields => [:title, :author]) assertequal TITLEFIELD, result[:title] assertequal AUTHORFIELD, result[:author] end

def testhashextrafields result = DocumentHasher.hash(@object, :fields => [:title, :author], :extrafields => [:extra]) assertequal EXTRAFIELD, result[:extra] end

end

Salve esse arquivo para um arquivo chamado hasher.rb e rode-o com o comando abaixo para verificar sua execução:

~$ ruby hasher.rb

Utilização

Com esse programa, podemos rodar o Flog. O comando é simples:

~$ flog hasher.rb

Resultado inicial

O resultado da execução acima pode ser visto na listagem abaixo:

Total Flog = 57.7 (7.2 +/- 62.8 flog / method)

DocumentHasher#hash: (27.3)
     9.0: send
     8.6: assignment
     5.8: []
     5.4: branch
     2.8: each
     1.9: to_s
     1.7: +
     1.5: new
     1.3: hash
     1.3: id
DocumentHasherTest#setup: (8.3)
     6.5: sclass
     1.3: assignment
     1.3: new
     0.4: lit_fixnum

Note que o método hash possui um fator de "tortuosidade" de 27 e que os maiores culpados são o envio de mensagens (send) e atribuições. A "tortuosidade" total do programa está em 57.7, que representa o cômputo de todos os métodos do programa.

Alterando o programa

Para fins de exemplo, podemos tentar reduzir a complexidade do método hash como fizemos no artigo anterior usando o exemplo abaixo:

require "test/unit"

class DocumentHasher
  
  def initialize(object, options = {})
    @object = object
    @options = options
  end
  
  def hash  
    hash = { :id => @object.id }
    build_fields(hash, @options[:fields] || {})
    build_extra_fields(hash, @options[:extra_fields] || {})
    hash
  end
  
  def self.hash(object, options = {})
    self.new(object, options).hash
  end
  
  protected
  
  def build_fields(hash, fields)
    fields.each do |field|
      hash[field] = @object.send(field)
    end
  end
  
  def build_extra_fields(hash, fields)
    fields.each do |field|
      hash[field] = @object.send(field.to_s + "_field")
    end
  end    
  
end

class DocumentHasherTest < Test::Unit::TestCase
  
  Struct.new("HashExample", :id, :title, :author)
  
  TITLE_FIELD = "Test"
  AUTHOR_FIELD = "Author"
  EXTRA_FIELD = "Extra"
  
  def setup
    @object = Struct::HashExample.new(1, TITLE_FIELD, AUTHOR_FIELD)
    class << @object
      def extra_field
        "Extra"
      end
    end
  end
  
  def test_hash_id
    result = DocumentHasher.hash(@object)
    assert_equal 1, result[:id]
  end

  def test_hash_fields
    result = DocumentHasher.hash(@object, 
      :fields => [:title, :author])
    assert_equal TITLE_FIELD, result[:title]
    assert_equal AUTHOR_FIELD, result[:author]    
  end

  def test_hash_extra_fields
    result = DocumentHasher.hash(@object, 
      :fields => [:title, :author], 
      :extra_fields => [:extra])
    assert_equal EXTRA_FIELD, result[:extra]
  end
  
end

Rodando o comando novamente, teríamos:

Total Flog = 58.1 (5.3 +/- 10.3 flog / method)

DocumentHasher#hash: (10.7)
     3.2: []
     3.0: branch
     2.6: assignment
     1.5: new
     1.3: build_extra_fields
     1.3: hash
     1.3: build_fields
     1.3: id
DocumentHasher#build_extra_fields: (9.4)
     4.2: send
     2.8: assignment
     1.8: to_s
     1.6: +
     1.3: branch
     1.3: each
DocumentHasherTest#setup: (8.3)
     6.5: sclass
     1.3: assignment
     1.3: new
     0.4: lit_fixnum
DocumentHasherTest#test_hash_fields: (7.0)
     3.0: []
     2.6: assert_equal
     1.3: hash
     1.3: assignment

Note que a complexidade dos métodos caiu substancialmente. Os métodos estão mais simples e mais balanceados. A "tortuosidade" geral subiu um pouco com a adição de algumas chamadas, mas, analisando os métodos individualmente é possível observar que a somatória de complexidade dos três métodos envolvidos é menor do que a complexidade original. Mais uma vez, o código está mais legível e mais testável.

Conclusão

O Flog representa uma métrica arbitrária de complexidade que, mesmo assim, pode ser usada para acompanhar o desenvolvimento de um base de código. Um exemplo disso pode ser visto no texto do Carlos Villela mostrando a evolução do código do Rails ao longo dos anos.

Como de usual, sugestões, críticas e dúvidas são bem-vindos. No próximo artigo, esfolando o seu código Ruby com mais ferramentas de análise de complexidade.

Flay, eliminando repetições em código Ruby

November 13th, 2008 § 2 comments § permalink

Flay é uma ferramenta útil para cercear repetições de código em programas Ruby. Analisando o código semanticamente, o Flay é capaz de pegar repetições em casos que geralmente passam despercebidos no melhor dos códigos.

Em algumas casos, a repetição será inevitável e mesmo necessária para deixar o código mais legível. Geralmente, entretanto, repetição significa código que ainda não está DRY o suficiente.

Instalação

Para instalar o Flay, basta rodar o comando gem:

~$ sudo gem install flay

Esse comando instala a gem em si e um executável que pode ser usado na linha de comando.

Um exemplo

Para demonstrar o uso da ferramenta, vamos rodar o Flay contra o código mais recente do Active Record:

O resultado (um trecho apenas), depois de alguns minutos de trabalho com a CPU a 100%, é o seguinte:

Matches found in :defn (mass = 290)
  ./test/cases/associations/join_model_test.rb:237
  ./test/cases/associations/join_model_test.rb:262
  ./test/cases/associations/join_model_test.rb:271
  ./test/cases/associations/join_model_test.rb:623
  ./test/cases/associations/join_model_test.rb:650

Matches found in :defn (mass = 270)
  ./test/cases/validations_test.rb:929
  ./test/cases/validations_test.rb:937
  ./test/cases/validations_test.rb:945
  ./test/cases/validations_test.rb:953
  ./test/cases/validations_test.rb:961
  ./test/cases/validations_test.rb:969

Matches found in :defn (mass = 236)
  ./test/cases/validations_i18n_test.rb:491
  ./test/cases/validations_i18n_test.rb:510
  ./test/cases/validations_i18n_test.rb:529
  ./test/cases/validations_i18n_test.rb:549

Matches found in :scope (mass = 204)
  ./test/migrations/duplicate/3_innocent_jointable.rb:12
  ./test/migrations/interleaved/pass_1/3_innocent_jointable.rb:12
  ./test/migrations/interleaved/pass_2/3_innocent_jointable.rb:12
  ./test/migrations/interleaved/pass_3/3_innocent_jointable.rb:12
  ./test/migrations/missing/4_innocent_jointable.rb:12
  ./test/migrations/valid/3_innocent_jointable.rb:12

Matches found in :call (mass = 172)
  ./test/models/author.rb:64
  ./test/models/project.rb:17

Matches found in :defn (mass = 171)
  ./test/cases/validations_test.rb:977
  ./test/cases/validations_test.rb:991
  ./test/cases/validations_test.rb:1079

Note especialmente código que está sendo repetido em arquivos diferentes. No caso acima, como o código está em arquivos de teste, é provável que a repetição seja desejável para não poluir o escopo dos mesmos.

Vamos tomar um outra caso na biblioteca em si:

Matches found in :if (mass = 165)
  ./lib/active_record/associations/has_and_belongs_to_many_association.rb:82
  ./lib/active_record/associations/has_many_association.rb:100
  ./lib/active_record/associations/has_many_through_association.rb:194

O código repetido em questão é o seguinte:

if @reflection.options[:counter_sql]
  @counter_sql = interpolate_sql(@reflection.options[:counter_sql])
elsif @reflection.options[:finder_sql]
  # replace the SELECT clause with COUNT(*), preserving any hints within /* ... */
  @reflection.options[:counter_sql] = @reflection.options[:finder_sql].sub(/SELECT (\/\*.*?\*\/ )?(.*)\bFROM\b/im) { "SELECT #{$1}COUNT(*) FROM" }
  @counter_sql = interpolate_sql(@reflection.options[:counter_sql])
else
  @counter_sql = @finder_sql
end

Vendo os arquivos, é possível observar que o código é o mesmo. Considerando que os três arquivos representam classes com um pai em comum seria possível reduzir a repetição movendo o código para um método a classe pai.

Esse tipo de repetição tende a sumir com refatoramentos e o código acima provavelmente sumirá por um processo similar (alguém se habilita para um patch?).

Conclusão

Como é possível perceber, o Flay representa mais uma forma de observar o seu código em busca de coisas que podem ser melhoradas. É claro que isso não deve ser converter em uma obsessão de remover toda e qualquer repetição, o que demoraria mais tempo do que codificar coisas novas.

Como de usual, sugestões, críticas e dúvidas são bem-vindos.

Where Am I?

You are currently browsing the Ruby category at Superfície Reflexiva.