Clojure, Midje e Emacs

April 17th, 2011 § 0 comments § permalink

Esses dias comecei a brincar mais sério com o Clojure e decidi gastar um tempinho configurando o meu ambiente para a linguagem. Foi mais simples do que eu pensava, embora alguns passos dependam de configurações do lado do projeto também.

A primeira coisa é instalar o ambiente. Eu estava usando anteriormente uma versão solta em um diretório mas como o uso o Mac OS X, decidi usar o brew:

~$ brew install clojure clojure-contrib
~$ brew install leiningen
~$ lein plugin install swank-clojure 1.3.0

O primeiro comando instala o Clojure e algumas bibliotecas opcionais (que todo mundo usa na verdade) e o segundo instala uma das ferramentas de build mais usadas para a linguagem (que será útil depois para os projetos).

Finalmente, o último comando instala o plugin do Swank para o Clojure, para ser usado com o Slime. Isso também assume que este último esteja instalado. Caso contrário, basta seguir as instruções oficiais. Um único detalhe é que a versão do Swank usado pelo swank-clojure não gosta muito do autodoc do Slime–basta não carregá-lo (o que é padrão).

Em segundo lugar, o que precisei adicionar ao meu .emacs foi o seguinte:

(require 'clojure-mode)
(require 'midje-mode)
(require 'clojure-jump-to-file)

(add-hook 'clojure-mode-hook 
          (lambda ()
            (progn (midje-mode)
                   (paredit-mode +1)
                   (setq inferior-lisp-program "/usr/local/bin/clj"))))

(eval-after-load 'clojure-mode
  '(define-clojure-indent
    (fact 'defun)
    (facts 'defun)
    (against-background 'defun)
    (provided 0)))

O código acima assume que o diretório onde o clojure-mode e o midje-mode estão está apropriadamente adicionado as caminhos de carregamento do Emacs.

As primeiras três linhas são os requires necessários para carregar o ambiente. O midje-mode é um modo para o Midje, um framework de testes para o Clojure que me pareceu mais interessante que a opção padrão, o clojure.test.

O hook eu useu para carregar automaticamente o midje-mode em arquivos .clj para não precisar fazer uma distinção entre testes e arquivos comuns. Eu gosto de usar o paredit também mas é opcional. Finalmente, eu configuro qual é o aplicativo do Clojure em si.

O código para depois da carga do clojure-mode é usado somente para configurar indentações específicas para o Midje e é opcional também.

Para criar os projetos em si, é hora de usar o Leiningen:

~$ lein new my-project

Isso cria um diretório my-project já configurado com tudo o que é necessário para um projeto básico (com um arquivo .gitignore de bônus).

O próximo passo é configurar as dependências do Midje no arquivo project.clj:

(defproject books "1.0.0-SNAPSHOT"
  :description "My project"
  :dependencies [[org.clojure/clojure "1.2.1"]
                 [org.clojure/clojure-contrib "1.2.0"]]
  :dev-dependencies [[midje "1.1"]])

Depois disso é só usar o comando abaixo para atualizar as dependências:

~$ lein deps

É interessante também copiar a tarefa do lein que roda os comandos do Midje: é simplesmente baixar o arquivo midje.clj e copiá-lo para um diretório chamado leiningen dentro do projeto. Depois disso é possível rodar o comando lein midje para conferir os testes.

Com isso, já é possível usar lein swank para iniciar uma conexão dentro do projeto e, depois de abrir algum arquivo do mesmo no Emacs, rodar slime-connect para conectar o Emacs ao Slime. Um vídeo bom para introduação ao Midje no Emacs está disponível no YouTube. As mensagens quando um teste passa são bem divertidas. :)

Happy hacking!

Compilando o LLVM como uma biblioteca no Mac OS X 10.6

January 15th, 2011 § 0 comments § permalink

Esses dias andei brincando um pouco com o projeto ruby-llvm, cujo propósito é criar bindings em Ruby para o LLVM usando o Ruby-FFI. Para aprender sobre o projeto, adicionei alguns testes para a funcionalidade já existente e corrigi alguns pequenos problemas.

Para fazer isso, eu precisei compilar a biblioteca compartilhada do LLVM, que na maioria das plataformas é algo trivial. De fato, normalmente só é necessário especificar o flag abaixo no script de configuração:

./configure --enabled-shared

Eu uso o brew, na verdade, mas o princípio é o mesmo:

brew install llvm --shared

Entretanto, a compilação acima, embora passe limpa no Mac OS X, resulta nos seguintes erros quando a biblioteca é carregada no Ruby-FFI:

dyld: loaded: /Users/<user>/llvm/2.8/lib/libLLVM-2.8.dylib
dyld: lazy symbol binding failed: Symbol not found: 
    __ZN4llvm2cl6Option11addArgumentEv
  Referenced from: /Users/<user>/llvm/2.8/lib/libLLVM-2.8.dylib
  Expected in: flat namespace

dyld: Symbol not found: __ZN4llvm2cl6Option11addArgumentEv
  Referenced from: /Users/<user>/llvm/2.8/lib/libLLVM-2.8.dylib
  Expected in: flat namespace

Trace/BPT trap

Depois de algumas investigações e uma troca de e-mails com Takanori Ishikawa, eu cheguei ao seguinte patch que resolve o problema e permite que o LLVM seja compilado limpa e corretamente como uma biblioteca compartilhada:

diff --git a/Makefile.rules b/Makefile.rules
index 9cff105..44d5b2d 100644
--- a/Makefile.rules
+++ b/Makefile.rules
@@ -497,7 +497,7 @@ ifeq ($(HOST_OS),Darwin)
   # Get "4" out of 10.4 for later pieces in the makefile.
   DARWIN_MAJVERS := $(shell echo $(DARWIN_VERSION)| sed -E
's/10.([0-9]).*/\1/')

-  SharedLinkOptions=-Wl,-flat_namespace -Wl,-undefined,suppress \
+  SharedLinkOptions=-Wl,-undefined,dynamic_lookup \
                     -dynamiclib
   ifneq ($(ARCH),ARM)
     SharedLinkOptions += -mmacosx-version-min=$(DARWIN_VERSION)

As opções acima mudam os namespaces para o padrão de dois níveis do OS X e a resolução de nomes para acontecer em tempo de execução.

Usar essas opções não parecer ter causado qualquer problema em outras partes do LLVM mas eu estou curioso para entender porque não são usadas por padrão pelo projeto, especialmente considerando que muitos outros projetos fazem justamente isso como descobri depois. De fato, as opções anteriores parecem ser um legado dos dias pré-10.3 do Mac OS X. De qualquer forma, fiz essa pergunta na lista LLVM-dev.

Enquanto isso, o patch funciona para mim. Também disponibilizei uma versão modificada para o brew. YMMV.

Sobre linguagens de programação, desespero e raiva

November 16th, 2009 § 3 comments § permalink

Isso é lindo:

[T]he State of the End-User Environment / Programming Onion…

So, in a confluence of events, I have been lately looking at Scala and yesterday spent some time looking at Pike / Thompson / Google et. al.’s “Go” language for “systems programming.” And Guido halts Python syntactic evolution before the job is done…

And it fills me with despair and anger.

Language designers in general: You are IN THE WAY. Go here:

http://www.rebol.com/oneliners.html

…then do us all a favor and don’t resist the urge to fall on that wakizashi when your shame overcomes you.

Jeff Bone

Leia mais em [FoRK] Programming languages, operating systems, despair and anger. A sensação com Go foi exatamente a que eu tive: conceitos razoavelmente interessantes empacotados em uma sintaxe que só ajuda a piorar o que havia antes.

É claro que não há balas de prata, mas há de se pensar em algo que quebre o molde que estamos usando nas últimas décadas.

LazyWeb: Escolhendo um framework

November 11th, 2009 § 7 comments § permalink

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

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

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

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

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

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

Simples complexidade

November 5th, 2009 § 0 comments § permalink

Everything should be made as simple as possible, but not simpler.

— Albert Einstein

Estava lendo hoje o texto do pessoal do GitHub sobre como eles bolaram a arquitetura de suas aplicações para escalar para a enorme quantidade não só de acesso mas também de cenários de uso que a aplicação apresenta.

O texto é um exemplo excelente de como eles conseguiram sinergia arquitetural através da combinação criativa de aplicações proprietárias customizadas especificamente para o que precisam e reuso de sistemas de sistemas para atender cenários diferentes que, no final das contas, convergem para o mesmo padrão de uso.

De fato, o texto todo me lembrou da citação acima de Einstein de como as coisas deve ser simples ao ponto máximo possível mas não mais simples do que isso. Tomada de um ponto de vista bem pragmático, a arquitetura do GitHub é bastante complexa, apresentando dezenas de partes separadas que se falam coerentemente para servir uma única requisição. Eu gosto especialmente de como um uso judicioso de NIH contribuiu para a solução como um todo–uma aplicação bem clara de simplicidade e elegância.

A propósito, é bem interessante também acompanhar os textos da Anchor, que fez a arquitetura da nova solução de provimento do GitHub. Como é fácil perceber nos textos anteriores, a solução foi desenhada a despeito da infra-estrutura existente mas, obviamente, com o objetivo de ser relativamente simples–novamente, tão simples quanto possível–de ser migrada.

Isso é essencialmente o que eu estava falando quando escrevi o gap arquitetural: enquanto, sim, é possível evoluir a solução e deixá-la emergir–exatamente o que o GitHub fez–é virtualmente impossível escapar da necessidade de uma arquitetura específica, planejada, para obter a consistência e integridade desejados.

Em resumo, um caso muito bom para aprendizado.

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 § 6 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.

Where Am I?

You are currently browsing the Programação category at Superfície Reflexiva.