November 28th, 2009 §
Hoje, sábado de sol, está acontecendo o Dev In Sampa, um evento de desenvolvedores para desenvolvedores. Se você não conseguiu participar por algum motivo, pode acompanhar um pouco pelo livestream do evento–as palestras estão excelentes. Mas não se preocupe, as palestras estão sendo filmadas também e serão disponibilizadas após o evento.
Eu participei falando sobre a criação de linguagens de programação e para os que já querem ver alguma coisa, segue abaixo a apresentação do SlideShare:
O repositório da toy language que eu criei para demonstração já está disponível também no GitHub. Só não espere muito do código já que ele foi produzido em pouco tempo em madrugadas disponíveis. 
Para o resto, a caixa de comentários está aberta.
November 11th, 2009 §
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? 
November 9th, 2009 §
O Lucas Húngaro, que trabalhou comigo na WebCo, escreveu há poucos dias um artigo muito bom sobre a dificuldade de dissociar nomes e funções em projetos de software e sobre sua visão do processo de desenvolvimento e arquitetura. Desnecessário dizer, concordo essencialmente com tudo o que ele diz, com algumas pequenas ressalvas.
O leitor atento do blog deve estar se perguntando agora: mas, há menos de uma semana, você não disse que lidera uma equipe separada de arquitetura onde trabalha agora–isso não é uma contradição? Na verdade, não. Antes de responder a questão, porém, peço que o leitor me acompanhe por algumas considerações.
Como o Lucas menciona eu seu texto, o tópico de arquitetura de software é bastante controverso. De fato, ao longo das quase sete décadas desde que existe algum processo de desenvolvimento, nunca se chegou a um consenso sobre o que esse termo realmente significa. Ano após ano, novos artigos e livros são escritos para explicar o que se entende pela prática e metáforas abundam.
Eu não vou dizer que tenho a palavra final sobre o assunto, é claro. Nos últimos anos, entretanto, eu tenho pensado continuamente sobre o tema, especialmente como uma reflexão sobre o meu trabalho e cheguei a uma conclusão de que minha visão é bastante similar à advogada por Fred Brooks, com algumas pequenas diferenças que refletem minha experiência própria.
Brooks, na palestra que assisti, propôs o seguinte postulado: “Não há tecnologias ingênuas no Ocidente”. O que ele quis dizer com isso é que em qualquer domínio de conhecimento, a faixa de conhecimento e habilidades exigidas é maior do que uma única pessoa pode dominar em um dado projeto.
Ele usou como exemplo o caso de fabricantes de shampoo que usam simulações do fluxo de fluidos viscosos para garantir que as lâminas misturadoras não separem a emulsão de camadas triplas do produto final; adicionalmente, ele também comentou sobre uma fábrica de bolos em que a receita do dia é modificada pela análise química dos ingredientes que chegam a cada dia na planta.
O fato é que esse tipo de especialização de engenharia é uma constante reconhecida mesmo por metodologias ágeis em que a multi-disciplinaridade das equipes é exigida como uma das premissas para o funcionamento do processo.
Por conta disso, Brooks chega à conclusão de que a única maneira de atingir algum nível de consistência e integridade no desenho arquitetural de um sistema é obter uma visão única de como as estruturas devem se comportar no seu nível mais alto: em outras palavras, criar a arquitetura de um sistema.
Em seu livro Computer Architecture: Concepts and Evolution (escrito em parceria com Gerrit A. Blaauw), Brooks define arquitetura de sistemas computacionais da seguinte forma:
The architecture of a computer system we define as the minimal set of properties that determine what programs will run and what results they will produce. The architecture is thus the system’s functional appearance to its immediate user, the conceptual structure and functional behavior as seen by one who programs in machine language.
Eu ressaltei the minimal set of properties porque isso representa uma dos grandes desentendimentos sobre o que arquitetura de software realmente significa e quais são os entregáveis da mesma. Como Brooks e Blaauw apontam, se arquitetura é o conjunto mínimo de propriedades de um sistema, existem outras coisas que, por definição não são arquiteturais e que ainda assim precisam existir para que a implementação suceda.
Nesse sentido, podemos fazer uma distinção bem clara entre a arquitetura e o design de um sistema para entender o desdobramento do projeto de um sistema qualquer. Enquanto a arquitetura existe mais no nível do mapeamento e organização fundamental de um sistema, como entendida através de seus componentes, os relacionamentos entre esses e sua distribuição em domínios de tempo, economia (sim, porque dinheiro também é arquitetura) e escala, o design está mais centrado no domínio de resolução de problemas e planejamento para implementação da solução.
Em outras palavras, a arquitetura é voltada a atingir necessidades de negócio através de blocos maiores de construção do sistema enquanto o design é a disseminação técnica desses objetivos em algoritmos, sub-sistemas e escolhas de implementação.
O que leva à conclusão, por parte de Brooks, e com a qual eu concordo, de que para que se consiga integridade conceitual e estrutural da arquitetura, a figura de um arquiteto-chefe é necessária. Isso é óbvio quando se pensa no negócio como um todo e seus desdobramentos em múltiplas responsabilidades, projetos, sistemas de sistemas e relacionamentos da construção do software em si.
Uma palavra-chave aqui que ajuda esclarecer a distinção aqui é grande porte. Por grande porte, eu quero dizer projetos com um escopo grande ou com grandes características de distribuição. Como Brooks mesmo elabora em seus textos e palestras, se o sistema é pequeno o suficiente, não é necessário que exista uma distinção entre arquitetura, design e implementação. Brooks, na verdade, vai além ao sugerir que o arquiteto e implementador sejam uma única pessoa. Para projetos de porte maior, entretanto, sem uma visão consistente é impossível conseguir a consistência necessária entre as partes.
O arquiteto de sistemas, em outras palavras, é alguém que é capaz de enxergar o projeto com um todo, necessariamente além do escopo de um time qualquer de implementação, mesmo quando o design que esse time está seguindo é auto-contido dentro das premissas daquele time e somente se comunica com externalidades através de protocolos e convenções arquiteturas definidas anteriormente.
Como um exemplo disso, em uma de suas palestras, Brooks menciona uma discussão que ele teve com a pessoal responsável pela arquitetura de sistemas do Global Positioning System (GPS). Esse arquiteto entendia que o sistema como um todo era baseada na interação complexa entre muitos componentes (satélites e outros) e que a moeda corrente entre esses sistema era tempo, dividido em micro-segundos. Ainda mais, o arquiteto via como sua responsabilidade garantir que cada processo conseguisse a fatia necessária de micro-segundos para sua operação–com, como Brooks colocou, bastante micro-segundos sobrando em seus bolsos para resgatar partes do sistema que estivessem em dificuldade.
E isso é o que realmente eu entendo por arquitetura de sistemas. Aos proponentes de arquitetura emergente–tão comum entre praticantes de metodologias ágeis–a implicação é clara: é simplesmente impossível que arquitetura nesse porte, dessa complexidade, venha algum dia a emergir de times separados, trabalhando em componentes próprios, com suas próprias necessidades. Primeiro, por conta da onipresente necessidade de integridade conceitual e, segundo, por conta da degradação de comunicação à medida que o sistema de torna mais complexo e decisões maiores são cristalizada em um conjunto de constraints e especificações–o que Brooks chama de style sheet do projeto.
Volto a Brooks aqui para afirmar o ponto de que um comitê não é um bom lugar para se buscar integridade arquitetural:
Textbook examples of design are almost always “way too simple,” said Brooks. In particular, they ignore the fact that complexity often forces designs to change halfway through, and these changes then involves many other changes. Finally, there is no substitute for “the dreariness of labour and the loneliness of thought”–even though it has been joked that committees are a place where people seek refuge from that.
O arquiteto de sistemas é, em última instância, como Brooks também coloca, um advogado do usuário. Ele advoga pelo usuário em termos funcionais, em termos econômicos, e em termos de escala. Como mostrado na citação acima, o arquiteto de sistemas representa a aparência funcional do sistema para seu usuário imediato, visto pela lente de alguém que programa em linguagem de máquina. E, sim, é um papel técnico.
Para citar Brooks mais uma vez:
Computer architecture, like other architecture, is the art of determining the needs of the user of a structure and then designing to meet those needs as effectively as possible within economic and technological constraints. Architecture must include engineering considerations, so that the design will be economical and feasible; but the emphasis in architecture is on the needs of the user, whereas in engineering the emphasis is on the needs of the fabricator.
Note a diferença em ênfase como colocada por Brooks: arquitetura enfatiza as necessidades do usuário enquanto engenharia enfatiza as necessidades do construtor.
As implicações são bastante óbvias e essencialmente respondem à questão da minha concordância com o que o Lucas disse e com o fato de que eu lidero uma equipe de arquitetura: as necessidades de desenvolvimento são completamente diferentes.
Tirando um exemplo da minha própria experiência, quando eu trabalhava na WebCo, tínhamos apenas dois produtos: Brasigo e BlogBlogs. Por mais complexos que ambos sistemas fossem, suas necessidades arquiteturais eram comparativamente pequenas. Da mesma forma, por mais similares que ambos fossem (aplicações escritas em Rails, virtualizadas, com gargalo em banco de dados, etc), havia poucas conexões arquiteturais para que a figura de um arquiteto-chefe fosse necessária.
E, de fato, pelo tamanho dos projetos, podíamos ter, sem problemas, a figura de um arquiteto em cada time, servindo como líder técnico, ponto focal em discussões entre produtos, alguém como senioridade o suficiente para fazer um papel de mentor para membros mais novos da equipe.
Esse não é o caso em minha posição atual, na Abril Digital. Não só a complexidade dos sistemas é maior, tanto em escala como em distribuição, como a relação entre eles é mais porosa e necessitando de coordenação. Construir um sistema de sistemas constituído de dezenas de sub-sistemas, cada um com suas necessidades, escopo e papel é fundamentalmente diferente de construir um único produto, com limites e condições bem específicos. Não estamos construindo algo do tamanho de um sistema de GPS, claro, mas estamos construindo coisas que possuem necessidades maiores que simplesmente as de um único escopo.
Por conta disso, surge a necessidade de arquitetura como uma colaboração de papéis empregando arquitetos de sistemas e arquitetos de software (chamados de tech leaders internamente) para chegar a um design final coerente.
Isso é ainda mais fundamental em projetos terceirizados que, em um ponto ou outro, precisam se encaixar em nossa infra-estrutura e arquitetura em múltiplos times e instâncias de sistemas. Uma equipe dedicada serve para ajudar nessa coordenação, oferecendo visões do problema. O gap arquitetural é assim resolvido já que existe uma rodovia arquitetural contendo épicos que guiam a quebra de sistemas nas partes necessárias.
Dessa quebra nascem preocupações que podem ser traduzidas no design emergente em cada equipe, contribuindo ao final, para o retorno ao pool arquitetural de conceitos e implementações feitas no ato de descoberta que é o processo de desenvolvimento.
Eu acredito nessa colaboração de papéis como essencial para garantir a agilidade. Citando um dos artigos de Martin Fowler:
This kind of architect must be very aware of what’s going on in the project, looking out for important issues and tackling them before they become a serious problem. When I see an architect like this, the most noticeable part of the work is the intense collaboration. In the morning, the architect programs with a developer, trying to harvest some common locking code. In the afternoon, the architect participates in a requirements session, helping explain to the requirements people the technical consequences of some of their ideas in non-technical terms–such as development costs.
Nesse artigo, Fowler usa uma versão limitada do que Brooks diz para definir um tipo de arquiteto não desejável. E Fowler está correto: usar o argumento de Brooks simplesmente para suportar alguém que simplesmente “toma as decisões mais importantes” não faz sentido.
Isso tudo que foi dito anteriormente não significa, também, que essa arquitetura de sistemas não possa falhar. Ela falha, sim, e algumas vezes catastroficamente. E, na maioria das vezes, a falha pode ser rastreada para decisões que foram tomadas em pontos errados do processo por problemas de comunicação ou de definição de escopo resultado em design inconsistente pelo qual ninguém quer tomar a responsabilidade. A falha, nesse caso, é de todos envolvidos no processo.
Para resumir toda a conversa, considerando que esse texto acabou quase se tornando um ensaio, eu concordo com o Lucas: cada time deve ter o seu arquiteto. Mas acredito também que, para projetos com maior escopo, deve existir um nível mais alto de arquitetura–e por mais alto aqui não quero dizer em termos de uma elite ou de conhecimento mas simplesmente um papel que defina o que é mais alto simplesmente porque tecnicamente, alguém define que esse é o nível mais alto necessário.
Esse arquiteto, dentro do time, é um desenvolvedor sênior capaz de fazer decisões de design em colaboração com seus pares, praticar a mentoria, planejar e executar escolhas de implementação, atuando em conjunto com um time de arquitetos de sistemas que está preocupado com o todo e que não tenta, de forma alguma, forçar decisões de implementação ou design, que busca embasar suas decisões pela velha métrica do running code and rough consensus, que pratica código diariamente pelos meios necessários.
O que significa, essencialmente, que a arquitetura não tem que ser fechada no começo e permanecer imutável depois disso. Ao contrário, precisa evoluir como qualquer outra parte do sistema na percepção do que funciona e do que não funciona. Como Kent Beck diz:
The process of building architecture should have lots of feedback built in and it should be kept simple, because extra elements in the architecture introduce instability and unpredictability. The big difference from current practice is that: “I would stop apologizing for architecting this way,” he says
Espero com esses monte de palavras ter clarificado um pouco a visão do que andei escrevendo aqui nos últimos tempos. Obrigado ao Lucas por fornecer a oportunidade de uma discussão boa como essa–espero que ela continue, por sinal.
Aos leitores que tiveram paciência de chegar até esse ponto, quais são suas visões e comentários sobre o assunto? A caixa de comentários lhes espera impacientemente.
November 3rd, 2009 §
Desde que comecei a trabalhar com uma forma ou outra de metodologias ágeis, um dos assuntos que sempre me causou reflexão foi a questão de como lidar com arquitetura em um ambiente ágil. Obviamente, eu não sou o único que se questiona sobre isso: a discussão em torno de Big Design Up Front é tão velha quando a própria indústria. Existe uma polarização imensa sobre o assunto e é bem raro encontrar alguém que tenha desenvolvido alguma idéia que se encaixe no meio do caminho.
De fato, proponentes de metodologias ágeis geralmente gravitam em torno do que se comumente denomina design emergente, ou seja, a criação e concepção de conceitos arquiteturais–especialmente os não funcionais–ao longo do processo de amadurecimento da própria solução.
Duas coisas me levaram a repensar sobre o assunto nos últimos dias.
A primeira foi participar de uma palestra dada por ninguém menos do que Fred Brooks. Brooks é um dos autores mais influentes sobre a questão de arquitetura e design e eu sempre tive uma concordância forte com seus pontos de vista, especialmente no que tangem à necessidade de centralização de arquitetura como fonte de integridade conceitual em uma solução. O Mítico Homem-Mês toca profundamente nesse questão–de fato o livro pode ser considerado uma coleção de ensaios em torno desse tema–e Brooks sempre volta-se para essa necessidade de design arquitetural prévio para garantir soluções sólidas.
A segunda coisa que me levou a pensar sobre o assunto foi um tweet de Brian Foote, reportando da OOPSLA:
When we extol the benefits of architecture emerging in agile, we are really saying developers are better architects than Architects. #oopsla
Foote, conhecido pelo seu trabalho com Joseph Yoder, Big Ball of Mud, em que descreve a estruturação impensada de sistemas resultando em algo impossível de manter e impossível de se confiar, está correto em sua avaliação.
É claro que, nesse ponto, muita gente deve estar pensando que eu sou um elitista, que, de uma forma ou outra, considero arquitetos melhores do que desenvolvedores. Meu cargo atual pode até dar a entender isso–sou um gerente de arquitetura e engenharia de software na empresa onde trabalho–mas esse não é caso.
De fato, se eu tivesse hoje que me descrever em um currículo, eu teria bastante dificuldade de me conceituar em uma categoria qualquer. Eu poderia colocar que sou um desenvolvedor, já que faço isso. Também poderia colocar que sou um arquiteto, igualmente válido para o que faço. Poderia recorrer aos tradicionais programador ou analista de sistemas. A verdade é que sou tudo isso.
Para mim, um arquiteto não é alguém que atingiu um estado de santificação tal que pode abandonar os conturbados e lamacentos meandros da programação e recolher-se em sua torre de marfim para dispensar sua sabedoria sobre as massas menos iluminadas. Antes, tenho certeza de que a maioria dos meus colegas que se descrevem como arquitetos concordariam que arquitetura é mais uma questão de atuação e experiência do que de grau ou de talento nato. Eu não trabalharia com um desenvolvedor que não fosse capaz de responder por sua arquitetura e também não trabalharia com um arquiteto incapaz de codificar um algoritmo qualquer. Tentar extrair uma coisa da outra seria uma violação das premissas.
Voltando ao ponto, é justamente aí que entra a figura que Brooks descreve, o arquiteto-chefe que, por experiência, treinamento e sensibilidade adquiridos na prática, é capaz de guiar um sistema à integridade conceitual necessária para o seu bom desenvolvimento.
O que resolve, finalmente, para mim, a questão de emergência em metodologias ágeis. Eu acredito que, sim, deve haver arquitetura propriamente dita em qualquer projeto, mesmo os que subscrevem a metodologias ágeis e acho que isso nunca esteve fora da visão dos criadores das mesmas. Antes, essa é uma visão equivocada do que deve ou não emergir dentro das mesmas, que é a solução em si.
Arquitetura, por definição, é algo que precisa ser feito antes até um certo ponto, mesmo que depois sofra as mudanças necessárias por sua própria evolução gradual. Ela não pode ser estática–exceto em circunstâncias especiais que normalmente quase nenhum desenvolvedor encontrará ao longo de sua carreira–mas também não pode ser completamente ad hoc já que isso seria pouco mais do que pensar apenas no que está imediatamente adiante, sem se preocupar com os temas maiores que podem afetar o trabalho.
Em última instância, a arquitetura então não é necessariamente emergente: a solução o é. E por solução aqui, eu entendo o conjunto completo representado pelo produto, sua arquitetura, seu desenvolvimento e sua transição em produção. A responsabilidade de um arquiteto é traduzir o backlog, ou seja qual for seu equivalente, em temas conceituais que possuem integridade em conjunto e que levam a um desenvolvimento das características do software a seu tempo e com as suas necessidades atendidas.
Esse é um gap que fica claro na maior parte da discussão sobre arquitetura e metodologias ágeis e que precisa ser tratado mais freqüentemente pela literatura e seus proponentes.
Para finalizar, essa é apenas uma visão rápida do que tenho pensado nos últimos tempos sobre o assunto. Espero ter deixado minha visão um pouco mais clara do que estava em discussões passadas aqui no blog. Como sempre, comentários e discussões adicionais são sempre bem-vindos.
October 27th, 2009 §
syn•er•gy |ˈsinərjē|
noun
the interaction or cooperation of two or more organizations, substances, or other agents to produce a combined effect greater than the sum of their separate effects
— Apple’s Mac OS X Dictionary
A definição acima não é muito padrão mas expressa bem o conceito em que a palavra é entendida hoje em dia. Sinergia vem do grego sunergos, que literalmente significa trabalhar em conjunto.
Em inglês, a palavra data de cerca de 1650, e tinha um sentido bastante medicinal, podendo indicar tanto a ação cooperativa entre dois ou mais músculos do corpo para a realização de um esforço ou a ação combinada de medicamentos ou drogas para criar um estímulo maior no paciente.
O Wikitionary define sinergia também com o “comportamento de um sistema que não pode ser previsto pelo comportamento de suas partes”, o que é uma definição bastante interessante e diversa do sentido necessariamente positivo que a palavra ganhou nas últimas décadas.
De fato, sinergia hoje em dia é considerada uma buzzword, uma palavra sem significado para indicar a vontade de que algum esforço conjunto qualquer resulte em mais lucro, para qualquer valor de lucro, do que um esforço individual das partes envolvidas–a palavra-chave na mudança de definição aqui sendo “vontade” versus o efeito real.
No meu trabalho com arquitetura de software, entretanto, sinergia é algo que faz sentido naturalmente no desenho de sistemas. De fato, sistemas de sistemas tender a exibir isso de uma forma quase que óbvio já que não é possível desenhar os mesmos de outra forma. Não é sem motivo que a página na Wikipedia que explica o conceito usa sinergismo, uma variação de sinergia para explicar a motivação primária desse objetivo. O Unix é um exemplo bem óbvio disso e algumas pessoas chegam a se referir a isso como o Tao do Unix pelo fato de que as peças se encaixam com tal perfeição que é impossível pensar em trabalhar de outra forma.
Sistemas de sistemas fazem sentido em praticamente qualquer situação em que a complexidade das partes individuais torne o sistema final potencialmente (e exponencialmente) difícil de ser descrito de maneira consistente.
Essa é uma das razões, inclusive, pela qual as pessoas se decepcionam tanto com frameworks como Rails ou Django quando precisam de expandir aplicações já existentes para níveis maiores de complementaridade ou escalabilidade. Frameworks fechados simplesmente não exibem esse tipo de sinergia integral necessária para garantir que os princípios aplicáveis em aplicações menores sejam os mesmos de aplicações maiores. O resultado é que, essencialmente, todos esses princípios são violados à medida que o sistema precisa crescer resultando em um entendimento completamente diferente do que se desejava a princípio. Funciona, mas sem elegância ou beleza.
A despeito do significado amortecido, uma reflexão cuidadosa sobre sinergia e sua aplicabilidade ao desenho de sistemas faria bem a qualquer desenvolvedor ou arquiteto de sistemas. Sapir-Whorf sendo fraca ou não, um entendimento real é impossível se o vocabulário natural é desprezado.
October 22nd, 2009 §
Ontem, cortesia da Caelum, tive oportunidade de ver Fred Brooks falar sobre desenvolvimento, arquitetura de sistemas e colaboração entre times.
O evento, lançamento da tradução brasileira de seu trabalho mais famoso–O Mítico Homem-Mês–contou com várias outras palestras e uma sessão de Q&A com Brooks mas, infelizmente, só pude participar dos quarenta ou cinqüenta minutos que ele passou discorrendo sobre o assunto. Mesmo assim, foi muito bom ver o velho professor–ele está com quase 80 anos atualmente–falando sobre assuntos que eram relevantes em 1975, quando o livro foi impresso pela primeira vez, e que ainda são relevantes hoje, quase 40 anos depois.
O Mítico Homem-Mês é um livro que qualquer pessoa que desenvolve ou gerencia algum processo de desenvolvimento de software deveria ler. Apesar da ironia do próprio Brooks ao dizer que seu livro é como uma Bíblia de Engenharia de Software, porque “todo mundo lê mas ninguém faz nada sobre o assunto”, o livro permanece uma influência seminal entre todos os trabalhos que foram feitos no campo nos últimos 30 anos, especialmente entre os responsáveis por grande parte das metodologias de desenvolvimento que são usadas atualmente.
Um dos pontos interessantes da palestra–e algo que que só tem um conhecimento superficial do livro não notaria–é que Brooks possui uma visão particular de desenvolvimento que vai muito contra o que se fala hoje em termos de desenvolvimento “ágil”. Um dos exemplos engraçados disso foi quando um dos participantes, ao final da palestra, perguntou o que ele pensava sobre o papel da arquitetura e design colaborativos dentro de um time ágil–um time de Scrum, digamos. Brooks declarou enfaticamente, em resposta à insistência do participante, que, sem um arquiteto-chefe, nada que fosse feito teria a consistência–a integridade conceitual, por assim dizer–necessária para o bom desenvolvimento do software.
Falando sobre colaboração, Brooks apontou o papel do trabalho solo de grandes artistas e realizadores como essencial para a criação de obras duradouras. Mesmo no contexto de colaboração, ele diz, as maiores equipes raramente passam de uma colaboração complementar entre duas pessoas. Mais do que isso resulta em difusão da integridade conceitual da obra em face a desafios maiores.
Inclusive, comparando com o modelo de colaboração de projetos de código livre ou aberto, Brooks aponta o fato de que, nesses projetos, os construtores e clientes geralmente são os mesmos e isso torna o desenvolvimento algo completamente diferente. Há integridade conceitual, sim, não do sistema como um todo mas de suas partes. Isso pode realmente ser comprovado de maneira fácil do desenvolvimento dos grandes projetos como o Linux onde uma pessoa retém a visão intelectual mais profunda do desenvolvimento e onde as partes são íntegras entre si por via de convenções–style sheets de desenvolvimento, como Brooks denomina o processo.
Em suma, a visão de Brooks é refrescante em tempos em que metodologias ágeis estão em voga em uma compreensão real do que elas representam. É bom ver alguém que pensou exaustivamente sobre o assunto–e que está pronto para lançar mais um livro sobre suas reflexões ao longo dos anos–mostrar o que realmente importa no desenvolvimento. Raros são os times e empresas que possuem maturidade para ver as coisas dessa forma.
Minha única tristeza na participação do evento foi não ter podido pedir a Brooks para autografar meu exemplar–que repousa em Belo Horizonte à espera de uma mudança futura para São Paulo.
October 1st, 2009 §
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.
September 30th, 2009 §
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:
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.
September 29th, 2009 §
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.
September 28th, 2009 §
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.
