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.

Domain Specific Languages: Considerações Finais

January 11th, 2008 § 0 comments § permalink

Este é o quinto artigo em uma série sobre DSL, ou Linguagens Específicas de Domínio. O primeiro artigo introduziu o assunto explicando o que é uma DSL e como elas podem melhorar e simplificar o código de uma aplicação. O segundo artigo mostrou o processo de transformação de um problema usual em um problema resolvido por uma DSL. O terceiro artigo mostrava a implementação de uma DSL simples, usando as características básicas de meta-programação do Ruby. Por fim, o quarto artigo mostrava uma implementação mais complexa ilustrando outras técnicas úteis.

Neste último artigo, é explorar rapidamente alguns temas relacionados e mostrar o que está vindo por aí. Com a popularidade do Ruby e outras linguagens dinâmicas e funcionais, o assunto está se tornando cada vez mais estudado e vale a pena acompanhar o que está acontecendo.

Quando usar uma DSL

Muitos programadores, em seu primeiro contato com o tema, decidem que todo e qualquer problema podem ser resolvidos com uma DSL. Com o ditado diz, se você tem um martelo tudo se parece com um prego. O resultado são programas povoados de pequenas linguagens que precisam de uma grande quantidade de código para conversarem em si.

Embora seja possível–e em alguns casos interessante–coordenar interfaces entre uma DSL e outra, isso reduz consideravelmente os benefícios de isolar um problema, reduzir o seu foco e isolar a complexidade do código relacionado. Quando se começa a pensar na interface que uma DSL vai prover para outra DSL, a questão pode ficar complicada.

Para que está começando, o uso de DSL vai ser mais interessante em duas áreas: envolver código legado em interfaces mais acessíveis e refatorar seqüências complexas em algo mais gerenciável. Não é que uma DSL só sirva para essas duas tarefas. Mas, na minha experiência, é onde estão os maiores ganhos para quem está começando.

A partir daí, progredir para a elaboração de ferramentas internas mais complexas e finalmente chegar ao uso de ferramentas externas é um caminho mais tranqüilo.

Interfaces fluentes

Um termo que recentemente está sendo associado ao uso de DSL é interfaces fluentes. Como Martin Fowler–um dos criadores do termo–menciona nesse artigo, o termo é basicamente intercambiável com DSL e representa uma forma de concatenar chamadas em algo mais fluido e legível.

Um exemplo bem simples disso são os manipuladores de data no Rails:

(4.months + 5.years).from_now

Esse código pode ser lido naturalmente e seu intento é evidente de imediato. O objetivo de uma interface fluente é justamente realizar essa transição–o código imperativo e fixo é convertido em algo flexível e de fácil leitura.

Para linguagens que não possui capacidade específica de meta-programação, interfaces fluentes podem ser a maneira mais fácil de implementar uma DSL. Em C# 2.0, por exemplo, seria fácil dizer algo do tipo:

broker.ProcessFile(fileName).Using(MyService).
  MapColumn("A1").ToField("Name").FormattedAs(typeof(String)).
  MapColumn("A2").ToField("Date").FormattedAs(typeof(DateTime)).
    WithOptions("Year").As(DateTime.Today).
  MapColumn("A3").ToField("OrderId").FormattedAs(typeof(Integer)).
    WithOptions("Unique").As(True).
    WithOptions("EagerLoading").As(False)

O código é necessariamente mais verboso do que seria se a meta-programação fosse mais evidente na linguagem mas ainda é mais legível do que se estivesse quebrado em múltiplas classes e implementações.

Se você precisa usar uma linguagem que não é tão flexível, buscar linguagens fluentes pode ser uma estratégia bem interessante para a implementação de uma DSL.

Testando

Como a implementação de uma DSL geralmente envolve muita mágica, por assim dizer, testar a mesma pode se tornar algo complicado quando o escopo de execução dos blocos está sendo modificado ou é dinâmico–principalmente em linguagens onde os próprios mecanismos de teste implementam uma DSL com toda a dinâmica adjacente.

Nesses casos, a melhor estratégia não é estar a própria DSL, mas testar o que ele está gerando. Pode parecer que isso não dá um cobertura interessante, mas há um equivalência óbvia entre as duas coisas. Escolher os exemplos apropriados não é difícil e é possível exercitar todos os aspectos da geração simples observando o que ela está fazendo.

Quando a DSL possui um produto bem específico e final, a situação se torna ainda mais simples e o teste desse produto é uma validação automática.

Finalmente, o código que usa a DSL pode estar testado naturalmente já que o contexto encapsulado da DSL é isolado nesse caso.

O futuro próximo

Vários assuntos e tecnologias estão surgindo em torno do potencial de linguagens específicas. Entres eles estão geradores baseados em DSL com modificações two-way, language workbenches e programação orientada a linguagens.

Geradores de código estão entre as ferramentas mais vilipendiadas na história da programação, embora a sua utilidade seja inquestionável. De fato, usuários de linguagens cujo afinidade com DSL é patente, como Smalltalk, sempre utilizaram geradores de código em profusão e sem efeitos detrimentais para o código.

O maior problema com geração de código, entretanto, é que poucas vezes a geração é reversível. Isto, modificações no código gerado não são refletidas para o template usado. Uma DSL pode resolver isso servindo tanto de modelo como de código final, permitindo que haja uma correspondência direta entre as duas esferas. Esse é o tipo de problema que será mais e mais resolvido por linguagens específicas.

Language Workbench, por sua vez, é um novo termo cunhado por Martin Fowler para representar uma nova classe de ferramentas que permitem manipular uma DSL de maneira mais formal e persistente. De certa forma, eles estão para DSL como ferramentas de modelagem estão para UML diferindo, é claro, pela extrema flexibilidade. O uso de language Workbenches permite desenhar, testar e documentar uma DSL de uma maneira similar à criação de código.

Obviamente esse tipo de ferramenta ainda está em sua infância mas é algo que também será mais e mais utilizado nos próximos anos. O artigo de Fowler é uma fonte primária de informações e vale a pena se lido inteiramente–até porque fornece uma boa visão dos temas relacionados.

Finalmente, programação orientada a linguagem é outro assunto que está ganhando proeminência nos últimos meses. Originalmente, o termo se referia à mesma classe de soluções representada por linguagens específicas de domínio mas atualmente está se tornando um sinônimo para linguagens sintática e semanticamente flexíveis.

Isso e algo que linguagens como Lisp e Scheme vem fazendo há décadas mas que agora está sendo também traduzido para linguagens mais em voga como JavaScript e Ruby. Um bom exemplo disse é OMeta, uma sub-linguagem (no sentido de estar incorporada a outra) para extensões gramaticais.

Fechando o ciclo

Terminamos aqui a nossa série sobre DSL e esperamos que o tempo que você empregou lendo os textos tenha sido proveitoso, ajudando a completar o seu conhecimento. Quaisquer dúvidas, sugestões e correções podem ser deixadas nos comentários associados às entradas e os mesmos serão incorporados ao texto de acordo com as possibilidades.

Domain Specific Languages: Implementando mágica

January 10th, 2008 § 0 comments § permalink

Este é o quarto artigo em uma série sobre DSL, ou Linguagens Específicas de Domínio. O primeiro artigo introduziu o assunto explicando o que é uma DSL e como elas podem melhorar e simplificar o código de uma aplicação. O segundo artigo mostrou o processo de transformação de um problema usual em um problema resolvido por uma DSL. Finalmente, o terceiro artigo mostrava a implementação de uma DSL simples, usando as características básicas de meta-programação do Ruby.

Neste quarto artigo, mostraremos como implementar uma DSL um pouco mais complexa usando características adicionais de meta-programação do Ruby como a method_missing e proxies. Os exemplos serão necessariamente simples para não tornar o artigo muito extenso mas mostrarão o que é preciso para utilizar tais.

O problema

Para demonstrar as características acima, vamos utilizar o mesmo problema de definir regras para um jogo de Eleusis mas com o seguinte formato:

r1 = rule "Rule 1" do
  
  black means { its.suit.is_clubs | its.suit.is_spades }
  red means { its.suit.is_diamonds | its.suit.is_hearts }
  
  even means { its.value.is_even }
  odd means { its.value.is_odd }

  odd after { black & black }
  even after { red & red & red }
  
end

r1.run("2 of clubs", "3 of spades", "ace of clubs", "2 of hearts", 
       "2 of diamonds", "3 of hearts", "queen of clubs", 
       "ace of spades")

Note que agora estamos usando uma linguagem ainda mais próxima de uma definição verbal. Obviamente, vários elementos do próprio Ruby permanecem já que existem limites para o que pode ser modificado na linguagem básica.

Esse exemplo, como o anterior, não é capaz de processar todas as regras possíveis do jogo, e não possui qualquer recuperação de erro. Apesar disso, ele serve para ilustrar os conceitos que podem tornar uma DSL ainda mais efetiva na representação de seu problema.

Implementação

Como a classe Card que declaramos no arquivo anterior não sofreu qualquer mudança, não reproduziremos o seu código aqui.

Um detalhe de implementação geralmente associado com o desenho de qualquer DSL que faz uso de proxies ou interceptação de métodos é uma espécie de classe que chamamos de blank slate. Essas classes não possuem qualquer método de instância além do básico para o seu funcionamento interno dentro do Ruby.

O uso dessas classes atende dois propósitos dentro do desenho de uma DSL. Primeiro, permite identificar de uma forma mais rápida e precisa erros de interceptação de métodos, especialmente quando operadores estão sendo sobrepostos. Segundo, permite limpar quaisquer métodos adicionais que tenham sido acrescentados por outras bibliotecas reduzindo o risco de colisões.

A implementação que usaremos para a nossa class blank slate é a seguinte:

class BlankSlate
  
  KEEPER_METHODS = %w(__id__ __send__ inspect 
    class instance_eval hash)
  
  (instance_methods - KEEPER_METHODS).each do |v|
    next if v[-1] == ?? || v[-1] == ?!
    undef_method(v)
  end
  
end

Com exceção dos métodos essenciais, a classe acima não define qualquer outro método de instância. Sendo assim, qualquer classe derivada da mesma começara somente com os métodos mais básicos possíveis.

Com essa classe podemos começar a nossa implementação. O nosso arquivo básico, derivado do exemplo anterior e com as modificações necessárias da DSL, é o seguinte:

require "card"

class BlankSlate
  
  KEEPER_METHODS = %w(__id__ __send__ inspect
    class instance_eval hash)
  
  (instance_methods - KEEPER_METHODS).each do |v|
    next if v[-1] == ?? || v[-1] == ?!
    undef_method(v)
  end
  
end

class Rule < BlankSlate
  
  def initialize(name, &block)
    @name = @name
    @groups = {}
    @paths = []
    instance_eval(&block)
  end

  def run(*specs)
    cards = specs.collect { |spec| Card.from_string(spec) }
    rules = cards.zip(@paths * ((cards.length / @paths.length) + 1))
    rules.each_with_index do |pair, i|
      unless @groups[pair.last].include?(pair.first)
        puts "Rule failed at item #{i + 1}: " +
        "#{pair.first} did't match group #{pair.last.to_s}"
        return
      end
    end
    puts "Rule matched all cards."
  end

end

def rule(name, &block)
  Rule.new(name, &block)
end

r1 = rule "Rule 1" do
  
  black means { its.suit.is_clubs | its.suit.is_spades }
  red means { its.suit.is_diamonds | its.suit.is_hearts }
  
  even means { its.value.is_even }
  odd means { its.value.is_odd }

  odd after { black & black }
  even after { red & red & red }
  
end

r1.run("2 of clubs", "3 of spades", "ace of clubs", "2 of hearts", 
       "2 of diamonds", "3 of hearts", "queen of clubs", 
       "ace of spades")

O primeiro passo agora é implementar o método means que define as cartas que compõem uma regra. Esse método recebe um bloco com um método interno chamada its que pode ser usado para definir conjuntos de cartas através de expressões simples.

Podemos ter, como mostrado acima, black means { its.suit.is_clubs | its.suit.is_spades } para dizer “preto significa que seu naipe é copas ou espadas” e assim por diante. E, como veremos no resto da implementação, a sintaxe permite o uso de | e & para representar, respectivamente, o operador lógico ou e o operador lógico e.

A implementação do método é simples, sendo simplesmente uma delegação para a execução do próprio bloco:

class Rule < BlankSlate
  
  # ...
  
  protected

   def means(&block)
     instance_eval(&block)
   end
  
end

A execução real acontece através do método its, que é implementado assim:

class Rule < BlankSlate
  
  # ...
  
  protected

  def its
    FilterProxy.new
  end
  
end

Mais uma vez, temos uma delegação, agora para uma classe que servirá com um proxy para a invocação dos métodos necessários. Essa classe é implementada como descrito abaixo:

class FilterProxy < BlankSlate
  
  attr_reader :cards
  
  def |(proxy)
    @cards += proxy.cards
    self
  end
  
  def &(proxy)
    @cards.reject! { |card| !proxy.cards.include?(card) }
    self
  end

  protected
  
  def method_missing(name, *args)
    if [:suit, :face, :value].include?(name)
      @message = name
      self
    elsif name == :is_any_of
      @cards = Card.all.select { |card| 
        args.include?(card.send(@message)) 
      }
      self
    elsif name.to_s =~ /^is_(.*)$/
      if $1 == "odd"
        @cards = Card.all.select { |card| 
          card.send(@message) % 2 != 0 
        }
      elsif $1 == "even"
        @cards = Card.all.select { |card| 
          card.send(@message) % 2 == 0 
        }
      else
        @cards = Card.all.select { |card| 
          card.send(@message) == $1.to_sym 
        }
      end
      self
    else
      super
    end
  end
  
end

A classe FilterProxy possui duas atribuições: implementar a união e interseção de regras–através dos operadores & e |–e interceptar as mensagens emitadas na criação de critérios de grupo.

A união e interseção são simples. Elas são feitas entre duas instâncias da classe FilterProxy e retornam a primeira delas, alterada com a operação em questão. Como estamos descartando os objetos no bloco, isso não é um problema embora talvez seja mais interessante implementar a criação de uma classe pura se termos a intenção de filtrar mais extensivamente. Como estamos implementando uma seqüência simples, não vamos nos importar com esse detalhe agora.

O método method_missing é que implementa o grosso do trabalho, interceptando os métodos que são necessários para fazer os filtros funcionarem.

A primeira condição verifica se a mensagem é uma que a classe Card response. Se sim, a mensagem é salva para o próximo passo.

A segunda condição verifica se a mensagem é o método is_any_of que, com base na mensagem anteriormente salva e uma série de possíveis respostas, verifica quais cartas atendem a esse critério.

Finalmente, mensagens no formato is_<name> (como is_odd ou is_clubs) são implementadas de maneira similar, com um bloco que verifica se a resposta necessária atende a mensagem que foi passada.

Caso a mensagem não seja interceptada, o comportamento padrão é invocado, delegando a execução para a classe pai que, no caso, simplesmente faz o tratamento de erros.

A próxima implementação é o próprio método method_missing na class Rule, que lidará com os nomes dos grupos que estão sendo declarados. Essa implementação inicial fica da seguinte forma:

class Rule < BlankSlate
  
  # ...
  
  protected

  def method_missing(name, *args)
    if args.first.kind_of?(FilterProxy)
      @groups[name] = args.first.cards
    else
      super
    end
  end
  
end

Essa primeira implementação verifica se o primeiro argumento passado para uma mensagem qualquer é uma instância de FilterProxy. Caso seja, um grupo é definido com as cartas selecionadas pelo filtro. Qualquer outro desvio no processamento de mensagens gera um erro nesse momento.

Agora é hora de implementar o método after que também usa um bloco. A implementação é idêntica à do método means:

class Rule < BlankSlate
  
  # ...
  
  protected

  def after(&block)
    instance_eval(&block)
  end

end

Mais uma vez, estamos delegando o processamento à interceptação de mensagens. Para que isso funcione, precisamos alterar o método method_missing, que ficará da seguinte forma:

class Rule < BlankSlate
  
  # ...
  
  protected

  def method_missing(name, *args)
    if @groups[name]
      if args.size == 0
        GroupProxy.new(name)
      else
        @paths += args.first.sequence
        @paths << name
      end
    elsif args.first.kind_of?(FilterProxy)
      @groups[name] = args.first.cards
    else
      super
    end
  end

end

O código acima verificar se um grupo existe com aquela mensagem. Caso o grupo não exista, o processamento anterior é mantido. Se, entretanto, o grupo existir, temos duas respostas possíveis.

Primeiro, o método foi invocado sem argumentos. Isso significa que ele está sendo usado em uma definição da seção after, como pode ser visto pela regra. Nesse caso, um proxy é criado para tratar do processamento do bloco.

Segundo, o método foi invocado com argumentos. Isso significa que o mesmo está sendo usado como prefixo para uma regra after. Nesse caso, os argumentos são coletados para formar as regras que serão processadas. Como a regra define condições inversas, os grupos dentro do bloco são inseridos em primeiro lugar seguidos pelo grupo cujo nome é a própria mensagem.

A implementação da classe GroupFilter é trivial e pode ser vista abaixo:

class GroupProxy < BlankSlate
  
  attr_accessor :sequence
  
  def initialize(*sequence)
    self.sequence = sequence
  end
  
  def &(proxy)
    GroupProxy.new(*(@sequence + proxy.sequence))
  end
  
end

Temos duas situações possíveis. Primeiro, a inicialização, que simplesmente recebe uma série de nomes de grupos a ser mantida. Segundo, a união, que combina o conjunto atual com o conjunto sendo passado para formar um novo conjunto que é retornado em seguida.

Com isso nossa implementação está completa e pode ser utilizada na criação de regras razoavelmente complexas. É possível, por exemplo, definir grupos no seguinte formato:

black_and_even means { 
  (its.suit.is_clubs | its.suit.is_spades) & 
  its.value.is_even 
}

Como é fácil observar, é possível obter uma considerável expressividade mesmo com um código razoavelmente simples. Embora, obviamente, seja necessário muito mais do que isso para implementar qualquer regra Eleusis possível, o código acima já ilustra um caminho possível com uma legibilidade boa em relação ao domínio que a DSL trata.

Com isso encerramentos este exercício. No próximo artigo, algumas considerações finais sobre o que está sendo feito atualmente no campo e como resolver alguns problemas comum.

Domain Specific Languages: Uma implementação simples

January 9th, 2008 § 0 comments § permalink

Este é o terceiro artigo em uma série sobre DSL, ou Linguagens Específicas de Domínio. O primeiro artigo introduziu o assunto explicando o que é uma DSL, como elas podem melhorar e simplificar o código de uma aplicação e, finalmente, mostrando alguns exemplos usados pela maioria dos desenvolvedores. O segundo artigo mostrou o processo de transformação de um problema usual em um problema resolvido por uma DSL e a simplificação resultante da mudança.

Neste terceiro artigo, mostraremos como implementar uma DSL simples usando Ruby e quais são os passos necessários para que a mesma represente o intento do que estamos querendo fazer. Como esse é um exemplo inicial, somente os passos mais básicos da criação de um DSL serão mostrados. Em artigos posteriores, mostraremos outras técnicas mais avançadas.

A DSL que criaremos será baseada na descrição de regras do meu jogo de cartas preferido, Eleusis. Eleusis é um jogo que não depende de qualquer tipo de sorte e procura simular o processo indutivo de descobertas científicas. Funciona bem para grupos de três a oito pessoas embora o grupo ideal esteja entre quatro e cinco jogadores.

Em linhas gerais as regras são as seguintes:

  • A cada rodada, um jogadores diferente é o carteador. O jogo termina quando todos jogadores tiverem passado pelo papel de carteador;
  • O carteador inventa uma regra secreta que os outros jogadores devem descobrir;
  • Cada jogador que não o carteador recebe quatorze cartas iniciais;
  • O carteador coloca a primeira carta do jogo, que deve atender à primeira carta de sua regra;
  • Os outros jogadores se alteram colocando uma carta que supõem atender a regra;
  • Se acertarem, a carta fica após as outros cartas já jogadas;
  • Se errarem, são penalizados com duas cartas extras, e a carta errada é colocada perpendicularmente à ultima carta jogada;
  • A rodada termina quando um dos jogadores fica sem cartas (supostamente porque descobriu a regra e conseguiu descartar todas as castas que tinha em mãos);
  • O jogo termina quando todos jogadores tiverem ocupado a posição de carteador.

As regras inventadas podem variar de simples a complexas. Uma regra simples seria, por exemplo, jogar uma carta de copas seguida por uma de ouros seguida por uma de paus seguida por uma de espadas e assim por diante. Uma regra complexa seria jogar uma carta vermelha se a última foi par ou preta se a última foi ímpar. Uma bom carteador sabe equilibrar a complexidade de suas regras.

Mas, chega de explicar o jogo. A DSL que criaremos será uma linguagem para descrever as regras que podem ser criadas no jogo, descrevendo o intento da mesma através de construções simples. A regra também terá um método que, ao receber um grupo de cartas, dirá se esse grupo se conforma à regra.

Uma regra de exemplo poderia ser algo da forma abaixo:

r1 = rule "Rule 1" do
  
  group :black, :is => [:clubs, :spades]
  group :red, :is => [:diamonds, :hearts]
  
  group :even do |card|
    card.value % 2 == 0
  end
  
  group :odd do |card|
    card.value % 2 != 0
  end

  get :black, :black
  get :odd
  get :red, :red, :red
  get :even
  
end

Para fins desse exercício não usaremos nenhum grupo pré-definido ou suportaremos regras com recombinações, ou seja, regras que dependem de valores anteriores de cartas jogadas.

Depois que a regra está definida, ela pode ser usada para verificar um grupo qualquer de cartas. Por exemplo, poderíamos usar algo assim:

r1.run("2 of clubs", "3 of spades", 
       "ace of clubs", "2 of hearts")

Ao rodar esse teste, seremos informados se as cartas atendem à regra ou qual a primeira delas a falhar e o por quê.

Como você pode perceber ao ler o trecho que código que representa a regra, a mesma soa quase como uma descrição textual do que está acontecendo. Obviamente, como a sintaxe de uma linguagem qualquer não pode ser completamente flexível, algumas partes da definição não serão tão bem especificadas, mas o ganho em legibilidade é óbvio.

Da mesma forma, o código acima atende aos critérios de uma DSL:

  • Ele resolve um único problema, a descrição de uma regra do jogo
  • Ele reduz o foco do problema ao descrever a regra de uma forma mais intuitiva
  • Ele esconde o código complexo por trás de métodos simples

A criação da DSL em sim pode ser agora quebrada em alguns passos simples. Antes de começar, assumiremos, porém, que a seguinte classe representa as cartas que são usadas pela regra (partes do código foram formatadas diferentemente do comum em Ruby para se encaixar melhor do texto):

SUITS = [:clubs, :diamonds, :spades, :hearts].freeze

FACES = [:ace, :two, :three, :four, :five, :six, :seven, :eight,
         :nine, :ten, :jack, :queen, :king].freeze

class InvalidCardError < StandardError; end

class Card

  include Comparable

  def initialize(face, suit)
    @value = FACES.index(face) + 13 * SUITS.index(suit)
  rescue
    raise InvalidCardError
  end

  def face
    FACES[@value % 13]
  end

  def suit
    SUITS[@value / 13]
  end
  
  def value
    FACES.index(face) + 1
  end

  def eql?(card)
    @value == card.instance_variable_get(:@value)
  end

  def <=>(card)
    @value <=> card.instance_variable_get(:@value)
  end
  
  def to_s
    "#{face} of #{suit}"
  end

  def self.all
    @@all_cards ||= SUITS.inject([]) { |m, s| 
      m + FACES.collect { |f| Card.new(f, s) } 
    }
  end
  
  def self.from_string(spec)
    spec.downcase!
    if spec.length == 2
      parts = spec.split(//)
    else
      parts = spec.split("of").collect { |p| p.strip }
    end
    if parts.first =~ /\d+/
      face = FACES[parts.first.to_i - 1]
    elsif ["a", "j", "q", "k"].include?(parts.first)
      face = FACES.detect { |face| face.to_s[0,1] == spec[0,1] }
    else
      face = parts.first.to_sym
    end
    if parts.last.length == 1
      suit = SUITS.detect { |suit| suit.to_s[0,1] == parts.last }
    else
      suit = parts.last.to_sym
    end
    Card.new(face, suit)
  end

end

Queremos representar a nossa regra com uma classe que possa ser passada adiante e cujos métodos possam ser acessados por qualquer código interessado nos mesmos.

Nosso código inicial, então, seria algo assim:

require "card"

class Rule
  
  def initialize(name)
  end
  
  def group(name, items = nil)
  end
  
  def get(*groups)
  end
  
  def run(*specs)
    puts "Not implemented"
  end
  
end

r1 = Rule.new("Rule 1")

r1.group(:black, [:clubs, :spades])
r1.group(:red, [:diamonds, :hearts])

r1.group(:even) do |card| 
  card.value % 2 == 0
end

r1.group(:odd) do |card| 
  card.value % 2 != 0
end

r1.get(:black, :black)
r1.get(:odd)
r1.get(:red, :red, :red)
r1.get(:even)

r1.run("2 of clubs", "3 of spades", 
       "ace of clubs", "2 of hearts")

Ainda não tem muito a ver com o que queremos, mas já é um começo. Podemos fazer o código funcionar implementado os métodos necessários.

O método initialize ficaria assim, inicializando as variáveis internas da classe:

class Rule
  
  def initialize(name)
    @name = name
    @groups = Hash.new([])
    @path = []    
  end

  # ...

end

O próximo método é get, igualmente simples, guardando os grupos que serão rotacionados para formar a regra:

class Rule
  
  def get(*groups)
    @path += groups
  end

  # ...

end

O método group é um pouco mais elaborado já que envolve duas interfaces diferentes:

class Rule
  
  def group(name, items = nil)
    if items.kind_of?(Array)
      @groups[name] = []
      items.each do |group|
        @groups[name] += Card.all.select { |card|
          (card.suit == group) ||
          (card.face == group) 
        }
      end
    elsif block_given?
      @groups[name] = Card.all.select { |card| yield card }
    end    
  end

  # ...

end

A primeira parte do método verifica se o parâmetros items foi passado. Se o mesmo é um Array contendo uma combinação de naipes ou faces, o código procura no grupo de todas as cartas possíveis as que possuem o naipe ou face passado. As cartas recuperadas são então guardadas como um grupo específico. Se o parâmetro item não foi passado e um bloco existe, o bloco é usado sobre o mesmo grupo de todas as cartas para escolher aquelas que atendem ao critério do bloco.

Finalmente temos o método run que define o processamento da regra em si:

class Rule
  
  def run(*specs)
    cards = specs.collect { |spec| Card.from_string(spec) }
    rules = cards.zip(@path * ((cards.length / @path.length) + 1))
    rules.each_with_index do |pair, i|
      unless @groups[pair.last].include?(pair.first)
        puts "Rule failed at item #{i + 1}: " +
        "#{pair.first} did't match group #{pair.last.to_s}"
        return
      end
    end
    puts "Rule matched all cards."
  end

  # ...

end

A implementação segue a seguinte lógica:

  • As descrições das cartas passadas são convertidas nas cartas equivalentes.
  • Essas cartas são pareadas com as posições equivalentes na regra. Como a regra pode ser menor do que o número de cartas passadas, as regras são duplicadas até que forem uma lista com o mesmo comprimento das cartas. O método zip é usado então para fazer o pareamento final.
  • Para cada par, a carta é verificada para ver se existe dentro do grupo pareado. Se a carta existe, o processamento continua. Se não, o processamento é abortado com a mensagem necessária.

Se você roda o programa agora, verá que o mesmo funciona e que você pode criar regras diferentes e verificá-las contra qualquer conjunto de cartas.

O objetivo agora é transformar o código acima em algo mais legível, que se aproxime mais de uma linguagem de definição de regras.

Esse processo é surpreendentemente simples. O primeiro passo é executar o código de definição dentro de um bloco. Por mais trivial que isso seja, a mudança dá a impressão de agrupamento ao código e o torna mais interessante. A mudança necessária é a seguinte:

class Rule
  
  def initialize(name)
    @name = name
    @groups = Hash.new([])
    @path = []    
    yield self
  end

  # ...

end

O método initialize agora requer um bloco que pode ser usado para encapsular as chamadas aos métodos internos da classe. Nesse ponto pode ser interessante mover os métodos get e group para a seção protected para evitar acesso externo aos mesmos. A chamada a yield invoca o bloco passado ao método e dá ao mesmo como parâmetro a própria instância sendo criada.

Com a mudança acima, a criação da regra pode ser mudada para:

r1 = Rule.new("Rule 1") do |r|

  r.group(:black, [:clubs, :spades])
  r.group(:red, [:diamonds, :hearts])

  r.group(:even) do |card| 
    card.value % 2 == 0
  end

  r.group(:odd) do |card| 
    card.value % 2 != 0
  end

  r.get(:black, :black)
  r.get(:odd)
  r.get(:red, :red, :red)
  r.get(:even)

  r.run("2 of clubs", "3 of spades", 
    "ace of clubs", "2 of hearts")
      
end

Já podemos ver que o código se assemelha mais a uma linguagem separada embora o uso do parâmetro não seja tão interessante.

Para conseguir eliminar o parâmetro precisamos de um pouco de mágica que consiste em invocar o código dentro do bloco como se ele fosse parte da própria classe. Embora yield também invoque o bloco, a invocação é realizada no contexto em que o bloco foi criado, ou seja, fora da classe. Se conseguirmos invocar o bloco dentro da classe, não precisaremos referenciar a instância e poderemos remover o código desnecessário.

class Rule
  
  def initialize(name, &block)
    @name = name
    @groups = Hash.new([])
    @path = []    
    instance_eval(&block)
  end

  # ...

end

Para entender a mudança, precisamos entender duas outras coisas. Primeiro, que block é uma parâmetro de bloco. Em Ruby, blocos de código são considerados variáveis passíveis de manipulação tanto como qualquer outra valor primitivo ou instâncias de classe. De fato, um bloco é nada mais que uma instância da classe Proc. Como tal, possuem não só o código associado como métodos que podem ser invocados sobre esse código. Para explicar isso, veja o seguinte código:

p = Proc.new { |a, b| a + b }
puts p.call(1, 2)

O código acima criar um bloco que recebe dois parâmetros e devolve a sua soma. Logo em seguida o bloco é invocado com dois parâmetros e imprime o resultada do invocação. Como é fácil perceber, blocos também são variáveis de primeira classe tanto quanto qualquer outro tipo. Sendo assim, eles podem ser passados como parâmetros que é exatamente o que estamos fazendo em nosso código.

Como blocos geralmente são passados como parâmetros escondidos, pelo uso das palavras-chave do...end ou {...}, o Ruby usa &amp; para expor o bloco. O significado de &amp; é o seguinte: pegue o bloco de código passado como parâmetro para o método, coloque-o na variável cujo nome está após o &amp; e não o execute até que o mesmo seja invocado implicitamente. O método yield, ao contrário, não precisa da variável e simplesmente executa o bloco quando usado.

No caso do método initialize estamos pegando esse bloco passado como parâmetro e transferindo sua execução para o método instance_eval. Esse método faz exatamente o que diz: recebe um bloco de código e o executa como se o bloco fosse local à classe. Mais uma vez precisamos de &amp; para indicar que o bloco será passado como parâmetro e não explicitamente através de do...end ou {...}.

Com essa mudança, nossa regra fica assim:

r1 = Rule.new("Rule 1") do

  group(:black, [:clubs, :spades])
  group(:red, [:diamonds, :hearts])

  group(:even) do |card| 
    card.value % 2 == 0
  end

  group(:odd) do |card| 
    card.value % 2 != 0
  end

  get(:black, :black)
  get(:odd)
  get(:red, :red, :red)
  get(:even)

  run("2 of clubs", "3 of spades", 
     "ace of clubs", "2 of hearts")
      
end

Estamos agora bem próximos do resultado final. Precisamos apenas de alguns ajustes.

Podemos, para começar esses ajustes, criar um método para envolver a chamada à classe e simplesmente retorná-la. Fazemos isso com:

def rule(name, &block)
  Rule.new(name, &block)
end

Note mais uma vez o uso de &amp; para passar o bloco adiante. Usando esse método, o bloco será passado três vezes como parâmetro até sua execução final.

Esse método deixa a regra assim:

r1 = rule("Rule 1") do

  group(:black, [:clubs, :spades])
  group(:red, [:diamonds, :hearts])

  group(:even) do |card| 
    card.value % 2 == 0
  end

  group(:odd) do |card| 
    card.value % 2 != 0
  end

  get(:black, :black)
  get(:odd)
  get(:red, :red, :red)
  get(:even)

  run("2 of clubs", "3 of spades", 
     "ace of clubs", "2 of hearts")
      
end

Esse é basicamente o resultado que queríamos. Os dois últimos ajustes farão o resto. Um ajuste no método group para usar um Hash pode deixá-lo mais livre:

class Rule
  
  def group(name, options = {})
    if options[:is].kind_of?(Array)
      @groups[name] = []
      options[:is].each do |group|
        @groups[name] += Card.all.select { |card|
          (card.suit == group) ||
          (card.face == group) 
        }
      end
    elsif block_given?
      @groups[name] = Card.all.select { |card| yield card }
    end    
  end

  # ...

end

E finalmente, podemos remover os parênteses desnecessários da regra, que fica assim:

r1 = rule "Rule 1" do

  group :black, :is => [:clubs, :spades]
  group :red, :is => [:diamonds, :hearts]

  group :even do |card| 
    card.value % 2 == 0
  end

  group :odd do |card| 
    card.value % 2 != 0
  end

  get :black, :black
  get :odd
  get :red, :red, :red
  get :even

end

r1.run("2 of clubs", "3 of spades", 
      "ace of clubs", "2 of hearts")

Finalmente temos o resultado que queríamos. Como é fácil perceber pelos passados dados, o grosso da transformação envolveu o uso de blocos para esconder as chamadas.

Basicamente qualquer DSL mais simples pode usar uma estratégia similar. De fato, a maioria das DSL encontradas como exemplo usam exatamente esse tipo de código, embora o mesmo tenha alguns problemas de integração com testes, especialmente no que tange ao uso de ferramentas como RSpec.

No próximo artigo veremos dois outros exemplos da aplicação de DSL usando algumas técnicas diferentes para criar possibilidades ainda mais interessantes.

Domain Specific Languages: Do problema à DSL

January 8th, 2008 § 6 comments § permalink

Este é o segundo artigo em uma série sobre DSL, ou Linguagens Específicas de Domínio. O primeiro artigo introduziu o assunto explicando o que é uma DSL, como elas podem melhorar e simplificar o código de uma aplicação e, finalmente, mostrando alguns exemplos usados pela maioria dos desenvolvedores.

Neste segundo artigo, explicaremos com um problema comum pode ser transformado em uma DSL para exemplificar o processo de pensamento por trás da criação de uma linguagem que se propõe a resolver um problema específico em uma aplicação.

Como veremos abaixo, uma DSL pode converter um problema espinhoso em algo relativamente trivial. Para dar uma idéia do impacto desse tipo de simplificação, uma das aplicações que eu desenvolvi recentemente envolve a análise de segurança de barragens. Como todo consultor de segurança diria, barragens tendem sempre a cair e o problema é saber quando e como evitar isso. Para descobrir esses dados, o programa agrega diversas informações e permite que o consultor extrapole previsões de risco para a instalação e tome as medidas apropriadas.

Uma das mais importantes informações adquiridas pelo programa são dados de instrumentação. Esses dados podem ser digitados no sistema ou coletados automaticamente em leitores apropriados. Para um dado cliente, o programa pode suportar se meia dúzia a milhares de instrumentos variante de dez a quarenta tipos diferentes. Em muitos casos, uma nova instalação do programa também evolve a criação de uma interface para um novo tipo de instrumento e tudo o que está associado ao mesmo: leituras, programação, projeções, gráficos, impressão e uma série de outros benefícios.

A estrutura criada pelo programa é relativamente flexível e permite a inserção de novos instrumentos de uma maneira comparativamente simples. O problema é integrar toda a lógica relacionada a um instrumento no resto do sistema. Da maneira como o programa está estruturado, isso é feito por classes específicas que lidam com cada tipo de instrumento. E, embora a integração final seja simples, testar cada um desses instrumentos é algo demorado.

A solução encontrada foi criar uma DSL para descrever especificações de instrumentos e criar toda a infra-estrutura necessária. Testando a DSL uma única vez seria a garantia de que todos instrumentos estariam automaticamente testados e não seria necessário nos preocuparmos com cada detalhe de implementação. Isso foi feito e o tempo de incorporação de um novo instrumento caiu de uma semana para duas horas. Os erros são mínimos e a aplicação tem funcionado bem ao contento de seus usuários.

Esse é o poder de uma DSL.

Um problema

Para mostrar essa variação de expressividade de uma forma bem prática, vamos imaginar um problema relativamente simples, também baseado em uma experiência recente minha. A solução que encontramos é parecida ao que Martin Fowler descreve em seu artigo sobre o mesmo tema de modo que toda similaridade não é coincidência.

Em uma das nossas aplicações, um dos problemas a serem resolvidos era a importação diária de várias planilhas que chegam em um centro de produção do cliente. Esses arquivos são gerados por aplicações de terceiros, aos quais não tínhamos acesso e variavam constantemente em seu formato. Alguns de mês para mês, outros de semana para semana. Parte do contrato, portanto, era criar uma forma simples de mapear esses arquivos de modo que mudanças pudessem ser tratados com eficiência. De fato, com um pouco de treinamento, mesmo os usuários da aplicação seriam capazes de elaborar novos mapeamentos e lidar com as variações mais comuns da importação.

Para facilitar, o exemplo será dado em Ruby, embora a linguagem original tenha sido o C# dentro de uma aplicação usando ASP.NET.

A maneira convencional de resolver um problema assim é criar um framework de processamento. Isso incluiria:

  • Uma classe para descrever formatos de leitura dos arquivos
  • Uma classe para descrever configurações de ambiente
  • Uma classe para ler arquivos que receberia esses formatos e devolveria registros processados
  • Uma classe para mapear os registros processados e passá-los a um serviço interno da aplicação
  • Uma classe para juntar todas acima em uma interface mais simples

Uma solução

Uma implementação simples, consistiria então de algo assim:

class Configuration
  def initialize(config_file); end
end

class Format
  def initialize(configuration); end
  def define_field(name, column, type, options); end
end

class Reader
  def initialize(configuration, filename, format); end
  def process; end
end

class Service; end
class MyService < Service; end

Essas classes seriam usadas da seguinte forma:

config = Configuration.new("config.yaml")

format = Format.new(config)
format.define_field("name", "a1", String)
format.define_field("date", "a2", Date, :year => Date.today.year)
format.define_field("order_id", "a3", Integer, :unique => true)

service = MyService.new

reader = Reader.new(config, "data.csv", format)

reader.process do |item|
  service.process(item.name, item.date, item.order_id)
  service.dispatch
end

Esse processo de resolução do problema é trivial e fácil de ser acompanhado. De fato, essa a estratégia que a maioria dos programadores escolhe ao resolver esse tipo de situação. A solução é flexível, pode ser entendida facilmente na presença de relativamente pouca documentação, e não oferece desafios à implementação.

A única coisa que a implementação acima não faz, e isso é o mais importante, é declarar o intento do processo que está sendo codificado. E aqui entra o maior valor de uma DSL.

Intento

O maior valor que uma DSL pode trazer a um problema é deixar claro o intento do mesmo na solução. Uma DSL, pela sua proximidade com uma linguagem de programação, possui a expressividade dessas últimas mas procura ser limitada naquilo que pode expressar justamente para conseguir reduzir a complexidade adjacente.

Se uma DSL é expandida com toda sorte de construções, ela deixa de ser uma DSL e se torna uma linguagem completa. Isso não impede é claro, que linguagens completas sejam implementadas com características de uma DSL. De fato, macros em Lisp ou Scheme e muito da gramática de Smalltalk são estruturadas para facilitar a criação de construções idiomáticas dentro de um programa que podem ser usadas com uma forma de DSL.

Em última instância, o objetivo de uma DSL, então, é fornecer intento ao código, ou seja, fazer com que o mesmo seja auto-documentado, que o próprio fato de ler o trecho em questão já revele o necessário para a compreensão mesmo. Uma DSL não é senão uma outra forma de abstrair a complexidade. Nesse sentido, elas sucedem historicamente a programação estrutura e a orientação a objetos, algo sobre o qual voltaremos a falar em breve.

Reduzindo o problema

Considerando a implementação mostrada, que, embora não seja muito complexa, não descreve apropriadamente o intento do código, como podemos convertê-la para uma DSL que faça isso? A solução é relativamente simples:

process_file :named => "data.csv", :using => MyService do
  map_column :a1, :to_field => :name, :formatted_as => String
  map_column :a2, :to_field => :date, :formatted_as => Date,
    :with_options => { :year => Date.today.year }
  map_column :a3, :to_field => :order_id, 
    :formatted_as => Integer,
    :with_options => { :unique => true }
end

Uma outra opção seria:

process_file("data.csv").using(MyService) do
  map_column(:a1).to_field(:name).formatted_as(String)
  map_column(:a2).to_field(:date).formatted_as(Date).
    with_options(:year => Date.today.year)
  map_column(:a3).to_field(:order_with).formatted_as(Integer).
    with_options(:unique => true)
end

Ambas são igualmente válidas no sentido que declaram o intento do código e podem ser lidas quase como um texto descrevendo o que estão executando.

É importante lembrar que uma DSL esconde a complexidade do código–ele não elimina a necessidade de escrever o código. Uma DSL bem projetado, entretanto, pode reduzir o código a ser escrito codificando instruções comuns em formatos mais acessíveis. Embora o caso mostrado acima seja um caso simples, a redução de código chega a 30% em termos brutos e com um ganho imenso em termos de legibilidade.

Em nosso próximo artigo, veremos a implementação de uma DSL em Ruby e como aproveitar os recursos que uma linguagem com meta-programação oferece para isso.

Domain Specific Languages: Introdução

January 7th, 2008 § 10 comments § permalink

Esse é o primeiro artigo de uma série sobre DSLDomain Specific Languages ou Linguagens Específicas de Domínio–que deve se estender por três ou quatro artigos.

O objetivo é explicar um pouco sobre o que é uma DSL e como você pode usá-las para facilitar o seu trabalho de programação, reduzindo e melhorando o seu código de maneira significativa. O conteúdo é baseado em palestras que eu dei anteriormente mas com algumas outras considerações que o tempo não permitiu durante as mesmas.

Linguagens

Um dos meus referenciais em relação ao aprendizado de programação é tentar seguir o que Alan Perlis disse sobre o assunto:

Se uma linguagem não é capaz de afetar o modo como você pensa sobre programação, não vale a pena aprendê-la.

Eu não sei se Perlis estava pensando em como linguagens podem afetar o modo como você programa, mas isso é algo que sempre me vêm à mente quando eu penso no que Perlis disse. Há uma cadeia lógica quando se pensa em linguagens, paradigmas e sintaxe. Paradigmas afetam a sintaxe da linguagem e a sintaxe afeta como você programa. Disso se segue que o desenho da linguagem necessariamente afeta como você programa. Isso parece óbvio mas o fato é que mesmo variações entre linguagens imperativas–o paradigma de maior sucesso na história da programação–podem ter um impacto significativo em com um programador é capaz de descrever os problemas em um dado domínio.

A extensão natural dessa progressão lógica é pensar o que poderia ser feito caso fosse possível implementar a sua própria linguagem. Um paradigma diferente ou uma sintaxe diferente poderiam modificar a maneira com um problema é tratado e simplificar enormemente sua resolução.

O que uma DSL se propõe a fazer é exatamente isso: tratar um problema específico, dentro de um domínio qualquer, através da criação de uma linguagem própria para o mesmo. E embora isso seja possível em maior ou menor grau em virtualmente qualquer linguagem de programação, existem certas características que facilitam esse tipo de programação. Um forte protocolo para objetos, uma sintaxe flexível e a capacidade de interceptar características da linguagem são essenciais para o aproveitamento máximo de uma DSL.

Nessa série de artigos usaremos Ruby para isso, embora os mesmos princípios possam ser aplicados em qualquer outra linguagem.

O que realmente é uma DSL?

O que hoje está se tornando conhecido como DSL atualmente já teve vários nomes dependendo da comunidade em que as mesmas eram usadas. Alguns desses nomes são:

  • Pequenas linguagens: comunidade Unix
  • Macros: usuários de Lisp e Scheme
  • Linguagens de aplicação: BI e analistas
  • Linguagens orientadas ao problema: designers de linguagens de programação

Não importa qual o nome, todos esses rótulos se referem ao mesmo conceito: linguagens (isto é, formas de expressar algum conceito) específicas (ou seja, com um propósito bem definido) de domínio (pertencentes a uma classe particular de problemas). Uma DSL é circunscrita por três definições:

  • Ela resolve um problema específico. Em outras palavras, uma DSL não tenta abarcar todos os problemas possíveis de uma aplicação, mas se fixas em um único deles. Pode existir cooperação entre várias linguagens para resolver um problema maior, mas uma DSL resolve um único problema.
  • Ela estreita o foco do domínio. Uma DSL permite que um domínio específico tenha o seu escopo reduzido através da abstração que a mesma providencia. Podem ser necessárias várias linguagens para esconder todo um problema, mas cada uma dela resolve uma parte e esconde a mesma atrás de uma abstração mais simples.
  • Ela esconde a complexidade do código. A DSL não pode ser mais complicada do que o código que pretende substituir. A abstração deve ser inequívoca mas com uma interface significativamente reduzida.

Com base em todos esses conceitos é fácil perceber que usamos várias dessas linguagens:

  • Um Makefile, por exemplo, usa uma DSL que permite especificar como determinados arquivos devem ser compilados/montados para formar uma aplicação.
  • Comandos para o shell de um sistema operacional são uma DSL para manipular os fluxos de entrada e saída de programas sendo executados. Um script é uma mera aplicação dessa linguagem.
  • SQL é uma linguagem específica para a definição e recuperação de dados descritos em um formato relacional. Por mais sofisticado que seja, ele se resume a quatro operações básicas: selecionar, inserir, atualizar e excluir.
  • Todo arquivo XML ou SGML é uma DSL em si própria. Assim, o HTML e o XHTML são aplicações específicas que também forma uma DSL por sua vez.

Um dos exemplos mais interessantes de uma DSL é a linguagem usada pelo Graphviz. Essa linguagem, chamada de DOT permite a criação de virtualmente qualquer tipo de grafo através de comandos simples e intuitivos. O código abaixo é um exemplo simples:

digraph finite_state_machine 
{
    rankdir = LR;
    size = "8,5"
    
    node [shape = doublecircle]; LR_0 LR_3 LR_4 LR_8;
    node [shape = circle];
    
    LR_0 -> LR_2 [ label = "SS(B)" ];
    LR_0 -> LR_1 [ label = "SS(S)" ];
    LR_1 -> LR_3 [ label = "S($end)" ];
    LR_2 -> LR_6 [ label = "SS(b)" ];
    LR_2 -> LR_5 [ label = "SS(a)" ];
    LR_2 -> LR_4 [ label = "S(A)" ];
    LR_5 -> LR_7 [ label = "S(b)" ];
    LR_5 -> LR_5 [ label = "S(a)" ];
    LR_6 -> LR_6 [ label = "S(b)" ];
    LR_6 -> LR_5 [ label = "S(a)" ];
    LR_7 -> LR_8 [ label = "S(b)" ];
    LR_7 -> LR_5 [ label = "S(a)" ];
    LR_8 -> LR_6 [ label = "S(b)" ];
    LR_8 -> LR_5 [ label = "S(a)" ];
}

O resultado é o seguinte:

É fácil observar pela galeria de exemplos desse pacote que o uso da DSL esconde uma complexidade enorme por trás das cenas mas é bem específica no problema que resolve.

Uma DSL é uma linguagem, mas ela não se propõe a ser completa. Ao contrário de linguagens de programação que possui construções específicas para lidar com problemas genéricos de condições, iterações e definições, uma DSL é um conjunto limitado de comandos que descrevem um intento específico sobre um problema específico.

Interna versus Externa

Uma DSL pode ser interna ou externa. Uma DSL externa geralmente pode ser utilizada pelos usuários finais da aplicação–e muitas vezes eles são o público real das mesmas–possuindo tratamento de erro mais específico para o domínio que resolvem. Em contrapartida, uma DSL internal normalmente é usada pelos próprios programadores da aplicação e não possui um tratamento de erros tão robusto porque assume que sua utilização será mais constrita.

O foco dos nossos artigos são as linguagens internas embora os princípios aqui discutidos também possam ser utilizados nas externas. O nosso objetivo é mostrar como a aplicação de linguagens internas pode reduzir o código necessário para uma aplicação e simplificar o processo de testes.

Em nosso próximo artigo veremos como um problema comum pode ser convertido de sua implementação normal para usar uma DSL que o torna mais compacto e inteligível.

Where Am I?

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