Visitor pattern em interpretadores: um uso específico para um pattern incomum

Design patterns são velhos conhecidos dos programadores. Os clássicos vinte e três padrões de soluções para problemas comuns foram introduzidos em 1994 pela Gang of Four no livro Design Patterns: Elements of Reusable Object-Oriented Software.

Os problemas que eles endereçam, no entanto, não são uniformemente comuns. Uma pesquisa rápida no Github mostra que existem 190 milhões de menções ao termo adapter em código, enquanto o termo flyweight retorna apenas 858 mil resultados, um número 200 vezes menor!

Sendo assim, eu não deixei de ficar surpreso quando encontrei por acaso um uso prático do visitor enquanto lia Crafting Interpreters de Robert Nystrom. Caso você também se interesse pela construção de interpretadores, eu recomendo a leitura, caso esteja aqui só pelos patterns, eu vou resumir o problema e mostrar como o visitor se aplica.

Syntax trees

Após o reconhecimento dos tokens (identificadores, símbolos, literais, etc.), o interpretador constrói uma syntax tree para que possa reconhecer expressões e realizar o que a fase da interpretação exige (interpretar, avaliar, analisar, etc.)

Conversão de tokens em uma syntax tree. Os tokens separados (esq.) são reorganizados em uma árvore (dir.) que pode ser avaliada de baixo para cima, resolvendo primeiro a soma e depois a atribuição.

Ao construir as classes que representam os diferentes tipos de nós da árvore, vemos que existem algumas possibilidades para expressões: unárias, binárias, literais, agrupamentos, etc. Cada uma com um comportamento específico e portanto implementando diferentes métodos para interpretação, avaliação, etc.

Exemplo de como podemos estruturar as classes para expressões unárias e binárias cada uma com um método para avaliar a expressão.

O problema surge na hora que pensamos em estender nosso interpretador. Ao adicionar um novo tipo de expressão, implementamos os métodos necessários e tudo bem, mas ao tentar adicionar uma nova fase ao interpretador precisamos alterar todas as classes de expressões existentes, o que não é ideal.

Em seus exemplos, Nystrom usa Java, mas frequentemente discute as vantagens e desvantagens de uma linguagem orientada a objetos para a construção de interpretadores versus uma linguagem funcional. Nesse caso, ele argumenta que pattern matching, comum em linguagens funcionais, apenas inverte o problema: torna fácil adicionar novos passos ao interpretador, mas torna difícil adicionar novos tipos de expressão.

Podemos pensar nesse problema como uma tabela onde cada célula representa um comportamento de uma expressão em específico. Nessa tabela é fácil adicionar linhas, mas é difícil adicionar colunas.

Uma tabela ilustrando a implementação da syntax tree. Cada linha corresponde a um tipo de expressão e cada coluna a uma nova fase da interpretação. Adicionar novos tipos de expressões é como adicionar novas linhas e adicionar novas fases é como adicionar novas colunas. Como as classes agrupam funcionalidade por linha, adicionar colunas é mais complexo do que adicionar linhas.

Visitor ao resgate

Segundo Nystrom, visitor é o pattern menos compreendido. Muitos o ligam ao ato de navegar em árvores, o que ele argumenta não ser o único caso de uso. O fato de o estarmos usando em uma árvore, segundo ele, é mera coincidência.

Na prática, lembrando da tabela da seção anterior, o visitor separa as colunas em suas próprias tabelas. Nesse caso, adicionar um novo comportamento (uma nova fase do nosso interpretador) se resume a criar duas novas classes sem modificar as que já existem, como era o nosso objetivo.

Novo diagrama de implementação agora usando o visitor. Cada fase da interpretação está contida em um visitor (tabelas à dir.). Cada nova expressão precisa implementar o método accept() e não precisamos mais alterar a implementação das outras expressões.

No exemplo a seguir vemos como ficam as classes de expressão.

Exemplos de como a implementação mostrada anteriormente ficaria com a utilização do visitor.

Você deve ter notado que com essa abordagem, adicionar novos tipos de expressão se resume a criar a nova classe de expressão com o método accept e adicionar os passos nos visitors adequados, enquanto para adicionar novas fases de interpretação, basta adicionar um novo visitor e descrever o comportamento para cada expressão.

Não é uma solução perfeita, ainda precisamos alterar algumas classes para adicionar um novo tipo de expressão, mas a chave aqui é a separação de responsabilidades. Enquanto antes, adicionar uma nova fase exigia alterar um conjunto de classes de expressão, agora cada visitor é responsável por apenas uma fase, então as alterações necessárias fazem sentido.

Por fim, não existe linguagem perfeita para resolver esse problema, no entanto a aplicação desse pattern incomum nos permitiu resolver a situação de um modo elegante. Me pergunto quais outras aplicações podemos encontrar na natureza.

Agradeço ao Victor Pereira (Salah) pela revisão.