Eu uso árvores de objetos de domínio nos meus aplicativos Java há anos. Recentemente, passei a usá-las em Clojure. Em cada caso, descobri que o padrão Visitor é uma ferramenta confiável para a manipulação de árvores de dados. Porém há diferenças na maneira como o padrão funciona em uma linguagem funcional versus orientada a objeto, e nos resultados que se obtém.

Neste artigo, eu reexamino árvores de domínio e o padrão Visitor para a linguagem Java, e abordo várias implementações do visitor usando Clojure. Sendo uma linguagem funcional, o Clojure traz novos truques para a consulta e manipulação de dados. Especificamente, descobri que integrar zippers funcionais no padrão Visitor produz benefícios eficientes, os quais eu explorarei.

Manipulação de árvores simbólicas

Um exemplo de árvore simbólica é a representação de um plano de consulta SQL, que possui operações como filtro, junção, união e projeto. Estas operações trabalham juntas para formar uma série de computações a partir de dados de fonte para produzir o resultado de uma consulta.

Por exemplo, a consulta na Lista 1 descreve a junção das tabelas Depto e Funcionário. A consulta filtra alguns dos resultados onde o nome do departamento é "TI" e retorna uma concentração de nomes e sobrenomes de funcionários. O resultado deve retornar o nome completo de todos os funcionários do departamento de TI.

SELECT Employee.First || ' ' || Employee.Last
FROM Dept, Employee
WHERE Dept.ID = Employee.Dept_ID
  AND Dept.Name = 'IT'

É possível então examinar a representação da árvore simbólica equivalente deste plano de consulta na Figura 1. Conceitualmente, linhas de dados relacionais (tuplas) fluem pelos nós de operação no plano de consulta de baixo para cima. Os resultados finais da consulta são tirados da parte de cima.

Ao usar uma árvore de nós como esta, é necessário realizar operações na árvore como um todo. As operações possíveis incluem:

• Coletar todas as tabelas citadas no plano de consulta.
• Coletar todas as colunas usadas em uma subárvore.
• Descobrir o nó de junção superior no plano de consulta.
• Combinar um padrão na árvore e modificar a árvore.

A última operação é particularmente útil, pois permite realizar manipulações simbólicas na árvore. Ao usar o padrão de Filter Pushdown, primeiramente deve-se combinar um padrão no gráfico, e então modificar a árvore no ponto da combinação. Este é o padrão de Filter Pushdown para ser combinado:

• Nó do filtro F diretamente acima de um nó de Junção J.
• F possui um critério que envolve apenas uma única tabela.
• J é uma junção interna.

É possível aplicar uma manipulação de árvore para mover o nó de Filtro abaixo do nó de Junção em direção ao nó de Tabela relacionado. Manipulações como essa (suportadas pela teoria relacional apropriada) são a peça principal dos otimizadores de consulta de banco de dados. A árvore resultante é exibida na Figura 2:

O padrão Visitor é geralmente usado para separar uma estrutura de dados (a árvore, neste caso) dos algoritmos que operam na estrutura de dados. Ainda neste artigo, demonstrarei uma implementação orientada a objeto em código Java e uma variante funcional em Clojure.

Voltar para parte superior

Visitors na linguagem Java

Se quisermos implementar um padrão Visitor em Java, é necessário primeiramente representar os nós como classes de Java. Podemos desenvolver uma hierarquia básica, como mostrado na Figura 3. A maioria destas classes são suportes de dados simples. Por exemplo, a classe Junção contém uma expressão de junção-esquerda, uma expressão de junção direita, um tipo de junção, e um critério de junção.

Note que todos os objetos na hierarquia de domínio implementam a interface Visitável e o métodoacceptVisitor algo parecido com:

public void acceptVisitor(Visitor visitor) {
  visitor.visit(this);
}

Esse método acceptVisitor implementa o despacho duplo, permitindo a escolha de método para depender não apenas do tipo de objeto concreto, mas também do tipo de visitor.

As classes de visitor são mostradas na Figura 4. A interfaceVisitor de base contém um método de visita para cada tipo concreto no domínio. O AbstractVisitor implementa versões vazias de todos estes métodos para tornar visitors escritos concretos mais fáceis.

Navegação de Visitor

Além de visitar cada nó, o visitor deve decidir quais nós devem ser visitados como filhos do nó atual. É possível incluir a navegação em cada visitor, mas é melhor separar as preocupações da navegação e da operação. Na verdade, pode-se pensar na descoberta de filhos pelo tipo como uma operação do visitor que pode ser encapsulada no próprio visitor. NavigationVisitor captura a operação de navegação de árvore e permite que um visitor mais leve junte-se à operação.

Dê uma olhada nos métodos do NavigationVisitor:

public void visit(Join j) {
    visitor.visit(j);
    j.getCriteria().acceptVisitor(this);
    j.getLeft().acceptVisitor(this);
    j.getRight().acceptVisitor(this);
  }

NavigationVisitor transfere para outra instância de visitor, porém embarca a navegação de filho. Um visitor de exemplo pode coletar todas as instâncias de Coluna na árvore inteira, e seria algo como: Lista 2:

package visitors;

import java.util.HashSet;
import java.util.Set;

import visitors.domain.Column;

public class CollectColumnsVisitor extends AbstractVisitor {
  private final Set<Column> columns = new HashSet<Column>();
  
  public Set<Column> getColumns() {
    return this.columns;
  }
  
  @Override
  public void visit(Column c) {
    columns.add(c);
  }
}

Quando este visitor descobre uma Coluna na árvore, ela a armazena no conjunto de todas as colunas vistas até então. Uma vez que o visitor termina, é possível resgatar o conjunto inteiro de Colunas, como demonstrado na Lista 3:

Node tree = createTree();
CollectColumnsVisitor colVisitor = new CollectColumnsVisitor();
NavigationVisitor v = new NavigationVisitor(colVisitor);
tree.acceptVisitor(v);
System.out.println("columns = " + colVisitor.getColumns());

Quando esta estrutura básica estiver no lugar, é possível adicionar qualquer uma das seguintes otimizações:

• Visitors de navegação que executam navegação pré, pós ou customizada
• Prevenção do uso da árvore toda
• Mutação da árvore durante a visitação

Voltar para parte superior

Complexidade incidental em visitors Java

O padrão Visitor na linguagem Java lida parcialmente com o clássico problema de expressão. Cunhada por Philip Wadler, o problema de expressão define os dados de um programa como um conjunto de casos (tipos) e um conjunto de operações para aqueles casos. Imagine estes como as duas dimensões de uma tabela. É possível adicionar novos tipos de dados e novas operações em recompilar e reter tipos estáticos?

O padrão Visitor cria um cenário onde é fácil adicionar operações (novos visitors) no conjunto de tipos de dados existentes. Adicionar novos tipos de dados (classes) é difícil, entretanto, uma vez que o padrão Visitor requer um método visit() para todos os tipos concretos. É possível aliviar isso ao ter uma classe abstrata que contenha implementações vazias de todos os métodos para todos os visitors. Neste caso, é possível modificar apenas a classe abstrata e o código será compilado. Os Visitors não atendem ao padrão de não serem recompilados, mas eles minimizam as alterações necessárias para adicionar uma nova operação. Se for considerado também que adicionar um novo tipo acontece com menor frequência do que adicionar uma operação, o padrão geral é promissor: certamente melhor do que codificar uma nova operação em um novo método em todos os tipos concretos.

Implementar o padrão Visitor na linguagem Java permite satisfazer algumas metas básicas, e também incorre a complexidade incidental: métodos visit() padronizados em cada classe concreta, definindo visitors de navegação, e mais. Alavancar as ferramentas de programação funcionais do Clojure para implementar o padrão Visitor é uma maneira de contornar esta complexidade incidental, ainda programando a JVM.

Voltar para parte superior

Árvores em Clojure

Clojure fornece um conjunto de estruturas de dados persistente e imutável: listas, vetores, mapas, conjuntos e filas. Observe que persistente aqui se refere a uma propriedade de modificação de dados, e não ao armazenamento de dados.

Quando uma estrutura de dados persistente é "modificada", os dados não são alterados. Ao invés disso, uma nova versão imutável da estrutura de dados é retornada. Compartilhamento estrutural é a técnica usada para tornar as estruturas de dados persistentes do Clojure eficientes. O compartilhamento estrutural é baseado na imutabilidade de dados para tornar o compartilhamento possível entre instâncias de dados novas e antigas.

A imutabilidade também permite simplificar a ideia de simultaneidade e fornece leituras baratas de dados compartilhados. Se os dados são imutáveis, eles podem ser lidos sem a aquisição de um bloqueio. Se alguma outra ameaça "altera" os dados, o resultado será uma instância diferente dos dados, que podem compartilhar grande parte da estrutura interna. Na linguagem de programação funcional, estruturas de dados persistentes também são importantes para o desenvolvimento de funções puras, livres de efeitos colaterais.

Estruturas de dados persistentes do Clojure

Tornar uma estrutura de dados de lista conectada básica persistente é o exercício mais fácil; aqui, uma lista em Clojure é limitada a um var chamado "a":

(def a (list 1 2 3))

Clojure é uma variante da Lisp, então a avaliação ocorre primeiramente lendo uma expressão como uma estrutura de dados Clojure (geralmente uma lista), então avaliando cada expressão na estrutura de dados. Finalmente, o primeiro item da lista é evocado como uma função, com o resto dos itens como argumentos. A forma especial "def" criará uma variável com espaço para nome identificada pelo primeiro símbolo onde o valor é a expressão a seguir. Cada valor nesta lista conectada fica em uma célula que contém um valor e um indicador para a próxima célula (ou nil para marcar o final da lista), como mostrado na Figura 5:

Se um novo valor for adicionado ao topo da lista, isso é chamado de criação (ou "cons-ing") uma nova lista. A nova lista compartilhará todas as células da original:

(def b (cons 4 a))

É possível utilizar rest ou outras funções para acessar outras partes da lista, mas as novas listas criadas a partir da lista original ainda compartilharão a estrutura original. Duas funções principais para a operação em listas (e outras sequências de valores) são first (que retorna o primeiro item) e rest (que retorna uma lista do resto dos itens).

(def c (cons 5 (rest a)))

A principal diferença no modo de usar as estruturas de dados em Clojure em comparação a Java é que elas não são alteradas no local. Em vez disso, uma atualização é descrita e uma nova referência para uma estrutura imutável que reflete as alterações é recebida. Ao considerar uma árvore de nós onde cada nó é uma estrutura de dados imutável, é necessário considerar como modificar um nó o nós dentro da árvore sem modificar a árvore inteira.

Três nós

Antes de considerar a questão da manipulação da árvore, será considerada a estrutura de dados que será usada para definir cada nó da árvore. Queremos um conjunto bem definido de propriedades para cada tipo de nó. Também é útil se cada nó da árvore possui um tipo visível ao Clojure, que pode ser usado ao escolher uma implementação de função durante o tempo de execução.

Ao considerar um conjunto de chaves e valores, a escolha óbvia em Clojure é o mapa, que armazena pares de valores chaves. A amostra de código na Listagem 4 demonstra como criar um mapa, adicionar e obter valores:

user> (def alex {:name "Alex" :eyes "blue"})
#'user/alex
user> alex
{:name "Alex", :eyes "blue"}
user> (:name alex)
"Alex"
user> (assoc alex :married true)
{:married true, :name "Alex", :eyes "blue"}
user> alex
{:name "Alex", :eyes "blue"}

Cada uma das chaves no mapa é uma palavra chave em Clojure, que sempre avalia a si mesma e é idêntica à mesma palavra chave usada em nenhum outro lugar. É idiomático usar palavras chaves como chaves em um mapa. Palavras chaves são também funções. Quando invocadas com um mapa, funções de palavra chave procuram a si mesmas no mapa e retorna seus próprios valores.

A adição de entradas no mapa é feito com assoc ("associar"), e a remoção é feita com dissoc ("dissociar"). Se um mapa for impresso, haverá vírgulas entre as entradas do mapa, mas isso é puramente para fins de legibilidade; as vírgulas são tratadas como espaços em branco em Clojure. Ao fim do Lista 4, assoc um novo mapa será retornado e impresso, mas o mapa original permanecerá inalterado. Os dois mapas compartilharão estruturalmente os mesmos dados.

Mapas digitados

Lista 5 exibem algumas funções úteis usadas na criação de mapas com um bem conhecido :type . Este tipo será usado posteriormente para dar fim a comportamento polimórfico. A função node-type extrai o "tipo" de nó com base no :type .

(ns zippers.domain
  (:require [clojure.set :as set]))

(defn- expected-keys? [map expected-key-set]
  (not (seq (set/difference (set (keys map)) expected-key-set))))

(defmacro defnode
  "Create a constructor function for a typed map and a well-known set of
   fields (which are validation checked). Constructor will be
     (defn new-&node-type> [field-map])."
  [node-type [& fields]]
  (let [constructor-name (symbol (str "new-" node-type))]
    `(defn ~constructor-name [nv-map#]
       {:pre [(map? nv-map#)
              (expected-keys? nv-map# ~(set (map keyword fields)))]}
       (assoc nv-map# :type (keyword '~node-type)))))

(defn node-type [ast-node] (:type ast-node))

É possível encontrar muitos recursos novos e avançados na Lista 5, mas não entre em pânico! Este código está incluso para o programador avançado de Lisp ou Clojure, e não é essencial entender cada detalhe. A parte principal da listagem é o macro defnode que usa o tipo de nó e um vetor de nomes de campo, e cria uma função de construtor para a criação de mapas daquele tipo. Quando o construtor é chamado, os campos sendo passados são verificados para determinar se eles correspondem aos campos esperados, e um erro é acionado caso contrário. Um dos benefícios do Clojure como uma variante de Lisp é que o código é um dado (também chamado de homoiconicidade). Macros exploram este fato ao manipularem o código como dados antes da avaliação.

Lista 6 implementa o equivalente Clojure das classes de domínio Java:

(defnode column [table column])
(defnode compare-criteria [left right])
(defnode concat [args])
(defnode filter [criteria child])
(defnode join [type left right])
(defnode project [projections child])
(defnode table [name])
(defnode value [value])

Utilização das árvores

Nosso desafio agora é utilizar uma árvore de mapas em Clojure, analisá-la ou manipulá-la. Como árvores Clojure são estruturas de dados imutáveis, qualquer manipulação requer o retorno de uma árvore nova e modificada. Como primeira etapa, é possível pensar na implementação da linguagem Java do padrão Visitor e tentar algo similar. Queremos definir uma operação que aborde nossa árvore de mapas, procure por um padrão na árvore, e aplique uma manipulação naquele ponto.

Por exemplo, é possível procurar por funções concat com todos os valores de sequência literais, e então concentrar os argumentos em um valor de sequência, como na Figura 8:

Similar à solução do Visitor, é possível implementar uma operação eval-concat para cada tipo de nó na árvore usando um método diverso. Em Clojure, um método diverso é um tipo especial de função que divida a invocação em duas etapas. Quando a função é invocada, uma função de envio customizado é avaliada com os argumentos da função. O valor de envio é então usado para escolher uma das muitas implementações de função.

(defmulti <function-name> <dispatch-function>)
(defmethod <function-name> <dispatch-value> [<function-args>] <body>)

Um método diverso é definido por dois macros: defmulti e defmethod. Estes macros estão unidos pelo <nome da função>. O macro defmulti especifica a função de envio para ser usada quando for primeiro invocada, e outros recursos opcionais. Haverá muitas implementações defmethod , cada uma especificando um valor de envio que aciona a execução, e um corpo de funções para ser executado no acionamento.

Envio de um tipo

A função de envio mais comum em Clojure é simplesmente a função de classe , como a invocação da implementação de função com base no tipo do argumento de função único passado para o método diverso.

Nesse exemplo, cada nó é um mapa, e queremos usar a função node-type para distinguir entre os diferentes tipos de mapas representando cada nó. Criamos então implementações do método diverso para cada tipo que queremos lidar, usando o defmethod.

S a função de envio não determina nenhuma possibilidade de combinação de método diverso, um valor de envio :default será chamado, assumindo que ele existe. No nosso exemplo, usamos uma implementação:default para especificar que todos os nós não listados devem retornar eles mesmos sem modificação. Isso é um caso de base útil, similar à classe de base Visitor no padrão Visitor clássico.

Lista 7 está a implementação completa do método diverso eval-concat . Neste exemplo, vemos o uso de funções como new-concat e new-compare-criteria, que foram criados pelo macro defnode que chamamos de volta na Lista 5.

(defmulti eval-concat node-type)
(defmethod eval-concat :default [node] node)
(defmethod eval-concat :concat [concat]
           (let [arg-eval (map eval-concat (:args concat))]
             (if (every? string? arg-eval)
               (string/join arg-eval)
               (new-concat {:args arg-eval}))))
(defmethod eval-concat :compare-criteria [{:keys (left right) :as crit}]
           (new-compare-criteria {:left (eval-concat left)
                                  :right (eval-concat right)}))

Lista 8 é um exemplo do método diverso eval-concat em uso. Este exemplo cria uma pequena árvore de nós, e então executa o método diverso eval-concat naqueles nós para descobrir uma concat de literais de cadeia de caractere. Ele então os substitui pela cadeia de caractere concatenada.

(def concat-ab (new-concat {:args ["a" "b"]}))
(def crit (new-compare-criteria {:left concat-ab
                                 :right "ab"}))

(eval-concat crit)

Observe que o eval-concat na Lista 7 resolve o problema apenas parcialmente. Para uma solução completa, é necessário criar um defmethod para cada classe que possa possuir uma expressão, portanto, concat . Embora isso não seja difícil de ser feito, é um trabalho tedioso.

Especificamente, grande parte do "peso" da solução envolve analisar a estrutura de dados. Toda a modificação atual da árvore é isolada no :concat defmethod. Seria melhor se a análise da estrutura de dados fosse uma operação separada e genérica.

Análise de dados com clojure.walk

A API principal do Clojure inclui uma biblioteca, clojure.walk, que é especificamente para a análise de estruturas de dados. A funcionalidade da biblioteca é baseada em uma função principal chamada walk, embora walk seja raramente chamada diretamente. Ao invés, é muito mais comum acessar a funcionalidade por meio de prewalk e postwalk . Ambas as funções utilizam a árvore em profundidade de primeira ordem, porém eles diferem se o nó é visitado antes ou após seus filhos. Ambas as versões precisam de uma função para aplicar em cada nó que retorna um nó de substituição (ou o nó original).

Por exemplo, Lista 9 exibe um postwalk operando em uma árvore heterogênea de dados. Primeiro movemos a árvore e passamos uma função que meramente imprime o nó sendo visitado e devolve o nó. Então chamamos postwalk, passando em uma função que procura integrar e incrementar um por um, deixando o resto inalterado.

user> (def data [[1 :foo] [2 [3 [4 "abc"]] 5]])
#'user/data

user> (require ['clojure.walk :as 'walk])
nil

user> (walk/postwalk #(do (println "visiting:" %) %) data)
visiting: 1
visiting: :foo
visiting: [1 :foo]
visiting: 2
visiting: 3
visiting: 4
visiting: abc
visiting: [4 abc]
visiting: [3 [4 abc]]
visiting: 5
visiting: [2 [3 [4 abc]] 5]
visiting: [[1 :foo] [2 [3 [4 abc]] 5]]
[[1 :foo] [2 [3 [4 "abc"]] 5]]

user> (walk/postwalk #(if (number? %) (inc %) %) data)
[[2 :foo] [3 [4 [5 "abc"]] 6]]

O uso de postwalk e prewalk é benéfico porque eles já entendem como mover quase todas as estruturas de dados Clojure principais — como vetores, listas, conjuntos, e mapas (exceções incluem mapas armazenados e registros). Ao utilizar clojure.walk, não é necessário especificar nenhum código de navegação; ao invés, fornece-se apenas o código essencial que encontra o nó e o modifica.

Vamos aplicar o postwalk em nosso problema eval-concat a partir da Lista 10. Quando encontramos um nó do tipo :concat, verificamos se ele pode ser avaliado e retornar um novo valor no lugar do original :concat .

(defn eval-concat [node]
  (if (and (= :concat (node-type node))
            (every? string? (:args node)))
     (string/join (:args node))
     node))

(defn walk-example
  [node]
  (walk/postwalk eval-concat node))

Essa é uma implementação muito mais satisfatória. Toda a análise é lidada dentro do postwalk e precisamos apenas fornecer a função para encontrar e modificar a árvore no lugar.

Recursão no padrão Visitor

Um problema com o padrão Visitor original e esta implementação com postwalk é que o padrão é recursivo (veja Figura 9). Ao avaliar a função de modificação no nó, todas as análises de nós pais são na pilha. Isso é óbvio na implementação do Visitor, onde você vê todas as chamadas recursivas ao eval-concat . Mas mesmo se isto esteja realmente oculto no postwalk, a estrutura é a mesma.

A recursão não é necessariamente ruim. — Ele é fácil de entender e para pequenas árvores é raramente u problema. Mas no caso de árvores maiores, é preferível analisar interativamente, para preservar a memória. A questão é: podemos implementar o padrão Visitor sem recursão?

Zippers funcionais do Clojure

Uma solução bem conhecida para o problema de análise e modificação de uma árvore na programação funcional é o zipper, descrito celebremente por Gérard Huet (veja Recursos). Um zipper é uma maneira de representar uma estrutura de dados com um contexto local, como navegação (iteração) e modificação do contexto atual. São, na maior parte, constantes. Todas as alterações são locais ao contexto.

Um zipper de árvore é tipicamente composto por um caminho a partir da raiz ao local atual na árvore, mais o contexto da subárvore no nó focal. O nome "zipper" se refere ao movimento para cima e para baixo na árvore como um zipper, com a parte acima do nó focal como a parte aberta do zipper e o estado local como a parte fechada.

Em uma árvore típica, o acesso constante é disponível apenas na raiz (o nó referenciado por outro código). Os Zippers permitem que o nó focal viaje pela árvore, tendo acesso constante aonde quer que esteja (não incluindo o tempo para chegar ao nó). Uma maneira comum de pensar sobre os zippers é que eles são como uma árvore de elásticos: é possível "pegar" a árvore em qualquer ponto, e este se torna como uma raiz com caminhos para a esquerda, direita e para os pais, a partir do nó focal.

A estrutura de dados do nó focal é comumente referida como um local, ou "loc." O local contém a subárvore atual e o caminho para a raiz. Vamos considerar uma versão simplificada da estrutura de árvore pequena da Figura 8. Desta vez, vamos simplificar o exemplo usando vetores, ao invés de mapas.

Figura 10 ilustra como a estrutura de local muda quando analisamos a árvore, aqui indo para baixo (sempre para o primeiro filho à esquerda), e depois para a direita, e então para baixo. Em cada caso, o novo nó se torna o ponto focal e o resto da árvore é representado como nós da esquerda, da direita e nós pais, em relação ao foco.

Enquanto analisamos a árvore, as alterações são locais ao nó focal atual, significando operações constantes exceto para cima. Este é o principal benefício dos zippers.

Zippers em Clojure

A API principal do Clojure contém uma implementação de zipper elegante no clojure.zip, com a API mostrada na Lista 11. Eu dividi a funcionalidade da API em diversas categorias: criação, contexto, navegação, enumeração, e modificação.

As funções de construction permitem a criação de um novo zipper (ou seja, um local). A principal função para a criação de novos zippers é zipper, que é baseada em três funções principais:

• ramificação escolhe um nó e retorna o que for possível para que aquele nó tenha um filho.
• filhos utiliza um nó e retorna o filho daquele nó.
• make-node escolhe um nó, um novo conjunto de filho, e retorna uma nova instância.

As funções seq-zip, vector-zip, e xml-zip são ajudantes que chamam zipper com implementações predefinidas para sequências, vetores, e árvores em XML. (Esta implementação não analisa XML — ela espera uma estrutura de dados que representa XML, emitida por clojure.xml/parse.)

;; Construction
(zipper [branch? children make-node root]) - creates new zipper
(seq-zip [root]) - creates zipper made from nested seqs
(vector-zip [root]) - creates zipper made from nested vectors
(xml-zip [root]) - creates zipper from xml elements 

;; Context
(node [loc]) - return node at current location
(branch? [loc]) - return whether the location is a branch in the tree
(children [loc]) - return the children of a location’s node
(make-node [loc node children]) - make a new node for loc with the old node and the new 
   children
(path [loc]) - return a seq of nodes leading to this location from the root
(lefts [loc]) - return a seq of nodes to the left 
(rights [loc]) - return a seq of nodes to the right

;; Navigation
(left [loc]) - move to left sibling or return nil if none
(right [loc]) - move to right sibling or return nil if none
(leftmost [loc]) - move to leftmost sibling or self
(rightmost [loc]) - move to rightmost sibling or self
(down [loc]) - move to the leftmost child of the current location
(up [loc]) - move to the parent of the current location
(root [loc]) - move all the way to the root and return the root node 

;; Enumeration
(next [loc]) - move to the next node in a depth-first walk 
(prev [loc]) - move to the previous node in a depth-first walk
(end? [loc]) - at end of depth-first walk

;; Modification
(insert-left [loc item]) - insert a new left sibling
(insert-right [loc item]) - insert a new right sibling
(insert-child [loc item]) - insert a new leftmost child under current node
(append-child [loc item]) - inserts a new rightmost child under current node
(replace [loc node] - replaces the current node with a new node 
(edit [loc edit-fn args]) - replace the current node with the results of edit-fn
(remove [loc]) - remove the current node and moves to the previous node in a depth-first 
   walk

As funções de contexto fornecem informações sobre o local atual na árvore e as funções de navegação devem ser baseadas na discussão anterior. Lista 12 mostra um exemplo de como usar as funções de contexto e de navegação para se movimentar e examinar a árvore:

> (def vz (zip/vector-zip [:compare [:concat "a" "b"] "ab"]))
> (println (zip/node (zip/down vz)))
:compare
> (println (zip/rights (zip/down vz)))
([:concat a b] ab)
> (println (zip/node (zip/right (zip/down vz))))
[:concat a b]
> (println (zip/node (zip/down (zip/right (zip/down vz)))))
:concat

Interação de Zipper

As funções de enumeração de um zipper permitem analisar a árvore inteira em ordem de profundidade, como mostra a Figura 11. Esse percurso é interessante porque é interativo, e não recursivo, o que é uma diferença chave entre o percurso de zipper e o anterior clojure.walk .

Um visitor de árvore com zippers

As funções de enumeração e de edição do zipper fornecem as ferramentas para desenvolver um visitor com base em zipper, que consiste na iteração da árvore e da execução da função visitor em cada nó. Podemos juntar estas ferramentas, como mostrado na Listagem 13:

(defn tree-edit [zipper matcher editor]
  (loop [loc zipper]
    (if (zip/end? loc)
      (zip/root loc)
      (if-let [matcher-result (matcher (zip/node loc))]
        (recur (zip/next (zip/edit loc (partial editor matcher-result))))
        (recur (zip/next loc))))))

A função tree-edit usa uma estrutura de zipper , uma função deequiparador e um editor . Esta função começa com a forma especial de Clojure loop, que cria um alvo para o recur no final da função. No Clojure, loop/recur indica recursão de cauda e não consome frames de pilhas como outras chamadas recursivas. A chamada zip/next itera para o próximo nó em uma movimentação de profundidade pela árvore.

A iteração termina quando zip/end? retorna verdadeiro. Neste momento, zip/root irá subir para o topo da árvore, aplicando qualquer alteração pelo caminho, e retornará para o nó raiz. No caso sem término, a função equiparador é aplicada ao atual local. Se forem correspondentes, o nó e o resultado do equiparador são passados para a função de editor para uma possível modificação, e a iteração continua do nó modificado. Do contrário, a iteração continua do nó original. A função parcial aplica parcialmente uma função com um subgrupo de seus argumentos e retorna um novo com poucos argumentos. Neste caso, aplicamos parcialmente editor para que o edit receba uma nova função com a assinatura apropriada.

Precisamos também de uma implementação de zipper que possa lidar com as estruturas de dados Clojure padrão durante o percurso. O zipper de árvore na Lista 14 implementa as funções que fazem com que os tipos de coleção principais permitam qualquer estrutura de dados Clojure construídas daqueles tipos para se tornarem um zipper: ramificação, filhos, e make-node. Eu escolho usar um método diverso para cada função do zipper, o que permite estender dinamicamente este zipper posteriormente para outros tipos, ao simplesmente adicionar um novo defmethod .

(defmulti tree-branch? class)
(defmethod tree-branch? :default [_] false)
(defmethod tree-branch? IPersistentVector [v] true)
(defmethod tree-branch? IPersistentMap [m] true)
(defmethod tree-branch? IPersistentList [l] true)
(defmethod tree-branch? ISeq [s] true)

(defmulti tree-children class)
(defmethod tree-children IPersistentVector [v] v)
(defmethod tree-children IPersistentMap [m] (seq m))
(defmethod tree-children IPersistentList [l] l)
(defmethod tree-children ISeq [s] s)

(defmulti tree-make-node (fn [node children] (class node)))
(defmethod tree-make-node IPersistentVector [v children]
           (vec children))
(defmethod tree-make-node IPersistentMap [m children]
           (apply hash-map (apply concat children)))
(defmethod tree-make-node IPersistentList [_ children]
           children)
(defmethod tree-make-node ISeq [node children]
           (apply list children))
(prefer-method tree-make-node IPersistentList ISeq)

(defn tree-zipper [node]
  (zip/zipper tree-branch? tree-children tree-make-node node))

Avaliação de Concat

Na Lista 15, nós revisamos nosso problema de avaliação da função concat ao criar uma função de equiparação (para descobrir nós de concat com argumentos literais de cadeia) e uma função de editor (par avaliar o concat). A função can-simplify-concat age como a função de equiparação e a função simplify-concat age como o editor.

(defn can-simplify-concat [node]
  (and (= :concat (node-type node))
       (every? string? (:args val))))

(defn simplify-concat [_ node]
  (string/join (:args node)))

(defn simplify-concat-zip [node]
  (tree-edit (tree-zipper node) 
             can-simplify-concat 
             simplify-concat))

(simplify-concat-zip crit)

Até agora, nós alcançamos quase o mesmo nível de complexidade essencial do que a implementação clojure.walk na Lista 10. Uma diferença entre a Lista 10 e a Lista 15 é que a versão de percurso é combinada com as parte de "equiparação" e "edição", que são separadas na versão zipper. Outra diferença é que, internamente, a versão zipper utiliza um percurso recursivo de cauda da estrutura de dados, ao invés de um percurso recursivo. Isso reduz o uso de memória durante a interação, porque a profundidade da pilha é constante, ao invés de dependente da altura da árvore.

Um visitor de árvore ainda melhor

Ao examinar visitors que são úteis na prática revelou diversas categorias comuns com base na meta do visitor:

• Descobridor procura pelo primeiro nó combinando alguns critérios e retornando ele.
• Coletor procura por todos os nós combinando alguns critérios e retornando ele.
• Transformador procura por uma combinação na árvore, altera a árvore neste ponto, e retorna ele.
• Gerador de evento percorre a árvore e ativa eventos (de DOM a SAX).a SAX).

Claro, é possível encontrar outras combinações curiosas e extensões destas categorias ao começar a usar e manipular árvores na prática. Nossa função tree-edit atual não permite que o visitor indique que a iteração deve parar, ou para carregar o estado pelo percurso, então é difícil criar visitor Localizadores ou Coletores sem utilizar suportes de estado externos.

Outra observação após escrever criar muitos visitors é que algumas partes comuns da funcionalidade devem ser reutilizáveis entre os visitors. Por exemplo, o descobridor e o coletor estão procurando avaliar um critério em um nó e determinar se o nó combina com o critério. Idealmente, gostaríamos de reutilizar uma função que faça isso para ambas as causas. Similarmente, é útil criar visitors que possam verificar por causas que devam causar o pulo para o próximo nó ou o aborto completo da iteração.

Lista 16 mostra um visitor avançado que aplica um conjunto de visitors em cada nó, passa o estado por meio da iteração, e permite uma saída adiantada de um nó ou de uma iteração inteira. Note as duas funções em uso aqui:

• A função tree-visitor é similar à tree-edit previamente discutida. Ela itera pela árvore por meio do zipper e termina com end?. Em cada nó, o tree-visitor chama o visit-node, nossa segunda função. A diferença primária no tree-visitor é que a função visit-node retorna vários itens: um new-node, um new-state, e um stop . Se stop for verdadeiro, a iteração irá parar imediatamente. O estado é possui initial-state e é passado por meio da iteração, permitindo que as funções do visitor o manipulem da maneira desejada. Ao fim do tree-visitor, o estado final e a árvore final são retornados.
• visit-node possui uma lista de funções do visitor, cada uma com uma assinatura (fn [node state]) que retorna um mapa de contexto, que pode conter os principais :node, :state, :stopou :jump. Se :node ou :state forem retornados, eles são substituições para o nó ou estado que está vindo. A passagem de :jump indica que a iteração deve pular para o próximo nó e pular todos os visitor remanescentes para este nó. A passagem de :stop indica que a iteração deve parar completamente.

(defn visit-node 
  [start-node start-state visitors]
  (loop [node start-node
         state start-state
         [first-visitor & rest-visitors] visitors]
    (let [context (merge {:node node, :state state, :stop false, :next false}
                         (first-visitor node state))
          {new-node :node
           new-state :state
           :keys (stop next)} context]
      (if (or next stop (nil? rest-visitors))
        {:node new-node, :state new-state, :stop stop}
        (recur new-node new-state rest-visitors)))))

(defn tree-visitor
  ([zipper visitors]
     (tree-visitor zipper nil visitors))
  ([zipper initial-state visitors]
     (loop [loc zipper
            state initial-state]
       (let [context (visit-node (zip/node loc) state visitors)
             new-node (:node context)
             new-state (:state context)
             stop (:stop context)          
             new-loc (if (= new-node (zip/node loc))
                       loc
                       (zip/replace loc new-node))
             next-loc (zip/next new-loc)]
         (if (or (zip/end? next-loc) (= stop true))
           {:node (zip/root new-loc) :state new-state}
           (recur next-loc new-state))))))

Uso de funções de visitor avançadas

Então, o que podemos fazer com nosso novo e melhorado visitor? Lista 17 mostra um exemplo de coletor que procuro por cadeias em nossa árvore. A função string-visitor procura por um nó de cadeia de caractere e retorna um estado atualizado que captura o nó. A função string-finder chama o tree-visitor com o string-visitor e retorna o estado final.

(defn string-visitor
  [node state]
  (when (string? node)
    {:state (conj state node)}))

(defn string-finder [node]
  (:state
   (tree-visitor (tree-zipper node) #{} [string-visitor])))

Podemos facilmente criar um descobridor, também. — Vamos criar um que descubra o primeiro nó de um certo tipo na Lista 18. A função combinada é como nossas principais funções de visitor, mas é necessário um tipo de nó para ser procurado no início. Quando find-first chama o visitor, ele aplica parcialmente o tipo no matched, produzindo uma função que apenas usa o nó e o estado como esperado. Note que a função combinada retorna stop=true para sair da iteração.

(defn matched [type node state]
  (when (of-type node type)
    {:stop true
     :state node}))

(defn find-first [node type]
  (:state
   (tree-visitor (tree-zipper node) [(partial matched type)])))

Passagem de funções diversas

Até agora, nós não realmente alavancamos a habilidade de passar diversas funções. O segredo aqui é que queremos decompor a funcionalidade em nossos visitors em partes menores, e então recombiná-las para desenvolver uma funcionalidade composta. Por exemplo: na Lista 18, nós reescrevemos nosso avaliador concat para procurar por nós :concat (função 1) que possuem todas as cadeias (função 2), para então avaliar o concat (função 3).

O primeiro tipo de visitor avaliador é gerado na função genérica "on". Esta função retorna uma função de visitor anônima que pulará para o próximo nó se o nó não for do tipo correto. Esta função é completamente reutilizável por qualquer cadeia de visitors que precise avaliar opcionalmente o resto da cadeia com base no tipo. A segunda funçãoall-strings gera similarmente um visitor condicional para um nó concat com todos os argumentos de cadeia de caractere.

Finalmente, criamos um método diverso para lidar com a avaliação, chamado eval-expr. Neste caso, o padrão selecionado para avaliar qualquer coisa é retornar a si mesmo. Adicionamos implementações adicionais para :concat e :compare-criteria. Este método diverso torna-se um visitor com o node-eval .

Montar esta cadeia de visitors em um visitor composto é fácil nochained-example, mostrado na Lista 19:

(defn on [type]
  (fn [node state]
    (when-not (of-type node type)
      {:jump true})))

(defn all-strings []
  (fn [{args :args} _]
    (when-not (every? string? args)
      {:jump true})))

(defmulti eval-expr node-type)
(defmethod eval-expr :default [x] x)
(defmethod eval-expr :concat [{args :args :as node}]
           (string/join args))
(defmethod eval-expr :compare-criteria [{:keys (left right) :as node}]
           (if (= left right) true node))

(defn node-eval [node state]
  {:node (eval-expr node)})

(defn chained-example [node]
  (:node
   (tree-visitor (tree-zipper node)
                 [(on :concat)
                  (all-strings)
                  node-eval])))

É fácil reutilizar várias partes desta implementação (como as funções on e node-eval ) em outras cadeias de visitor. A noção de uma cadeia de visitors oferece um quadro muito flexível com muitas opções para como você estrutura e reutiliza os visitors na árvore.

Voltar para parte superior

Fazer mais com os visitor Clojure

Este artigo apenas arranhou a superfície do uso de zippers no padrão Visitor; o propósito disso é atiçar seu apetite para uma exploração maior. Por exemplo, você deve ter notado que as estruturas do on e all-strings na Lista 18 são parecidas. Ambas são funções que ativam um filtro no visitor. Ao invés de funções de cadeia que contém filtros, poderíamos colocar um visitor de filtro em condições compostas usando os conectores Clojure normais. A inclusão de macros customizados para criar e combinar estas condições pode tornar o código mais combinável.

Na verdade, as bibliotecas de combinação de padrão (como a nova biblioteca Clojure core.match; vejaRecursos) permite especificar padrões com curingas que devem combinar com a estrutura de dados. Não é difícil integrar uma biblioteca de combinação de padrão com o visitor de árvore para chegar a um ponto onde visitors podem alavancar os padrões de árvores. Esta é uma etapa eficiente para abordar seu problema nos termos de seu problema, permitindo que a linguagem em si não atrapalhe.

Outro aspecto do padrão Visitor não examinado com cuidado aqui é a ordem de iteração. Na Revelytix, nós sempre percorremos os nós na ordem e profundidade da enumeração de zipper. Em alguns casos, podemos realmente querer percorrer estes nós na ordem reversa, pular certos nós ou subárvores, ou algo mais. A iteração consiste essencialmente em três operações: star (descobre o local de início do nó raiz); next (dado um local, descobre o próximo local, e end? (é o atual local o final da iteração?). É fácil abstrair estas funções na nossa função de visitor de árvore atual e permitir estratégias pré-fabricadas e de iteração.

Em Clojure, todos os códigos são também dados que acabam sendo armazenados como árvores de s-expression. É possível então usar todas as técnicas descritas neste artigo não apenas para modificar seus dados, mas para modificar seu código. É possível encontrar exemplos disto nas utilidades macro mais avançadas da API principal do Clojure.

Espero que você possa usar as ideias apresentadas aqui para desenvolver seus próprios visitors em Clojure ou na sua linguagem de escolha, e possa continuar explorando maneiras de estruturar e manipular seus dados. Consulte a seção Recursos para um link do download de todo código e exemplo usado neste artigo, armazenados no Github.

Agradecimentos

Muito obrigado aos meus colegas da Revelytix que desenvolveram códigos similares aos que estão neste artigo para o uso em nossos próprios produtos. Em particular, tenho uma dívida com David McNeil pelas muitas horas falando de ideias e soluções em um quadro branco ou em Emacs, assim como por fazer o trabalho pesado para estender bibliotecas como clojure.walk, clojure.zip, e matchure.

Sou grato também ao meu colega Alex Hall por ver a necessidade e por fazer a implementação da melhoria da iteração de pós-ordem.

Recursos

Aprender

• Saiba mais sobre o Clojure no developerWorks:
  • "A linguagem de programação Clojure" (Michael Galpin, 2009)
  • "Clojure e Simultaneidade" (Michael Galpin, 2010)
  • "Resolvendo o problema da expressão com Clojure 1.2" (Stuart Sierra, 2010)
  • "Usando CouchDB com Clojure" (Ryan Senior, 2011)
  
  
• Consulte Entrada do zipper na Wikipedia e o método documentação de Haskell para uma visão geral dos zippers.
  
  
• Gérard Huet apresentou o conceito de zippers no artigo "Functional Pearl: The Zipper" (Journal of Functional Programming, Volume 7, Cambridge University Press, 1997).
  
  
• Em mais sobre os zippers do Clojure, veja a apresentação em vídeo de Luke VanderHart sobre Blip.tv (2010).
  
  
• Brian Marick's "'Editing' trees in Clojure with clojure.zip" (Exploration Through Example, 2010) é um tutorial de introdução ao clojure.zip.
  
  
• Consulte "Pattern Matching & Predicate Dispatch" (David Nolen, NYC Clojure Users Group, 2011) para uma introdução ao core.match.
  
  
• Philip Wadler, um designer principal da Haskell, definiu o problema de expressão em 1998, quando era um pesquisador na Bell Labs.
  
  
• "Ideal Hash Trees" (Philip Bagwell, Es Grands Champs, Volume 1195, 2001) descreve a estrutura de dados no coração das estruturas de dados persistentes do Clojure.
  
  

Obter produtos e tecnologias

• Faça o Download do código fonte e dos exemplos deste artigo.
  
  
• Faça o Download de core.match: uma biblioteca de correspondência de padrão e envio de predicado para Clojure.
  
  

Sobre o autor

Alex Miller é engenheiro senior da Revelytix, desenvolvendo tecnologia de consulta de Web semântica federada. Ele trabalha com Clojure em tempo integral há dois anos. Antes da Revelytix, Alex foi supervisor técnico na Terracotta, engenheiro na BEA Systems e arquiteto chefe na MetaMatrix. Seus interesses incluem Java, simultaneidade, sistemas distribuídos, linguagens e projeto de software. Alex gosta de usar o Twitter como @puredanger e publicar no blog em http://tech.puredanger.com. Alex é o fundador da conferência de desenvolvedores Strange Loop e do grupo Lambda Lounge para o estudo de linguagens funcionais e dinâmicas. Ele gosta de nachos.

Classificar este artigo

Comentários

Voltar para parte superior

Índice

• Manipulação de árvores simbólicas
• Visitors na linguagem Java
• Complexidade incidental em visitors Java
• Árvores em Clojure
• Utilização das árvores
• Zippers funcionais do Clojure
• Um visitor de árvore com zippers
• Um visitor de árvore ainda melhor
• Fazer mais com os visitor Clojure
• Recursos
• Sobre o autor
• Comentários

Conheça a IBM da sua cidade

A IBM está mais perto do que você imagina!

---

Saiba mais