Посетители деревьев Clojure

Совершенствование модели Java Visitor с помощью функциональных зипперов

Исследователь языка JVM Алекс Миллер недавно обнаружил преимущества реализации модели Visitor с помощью Clojure, функционального варианта языка Lisp для виртуальной машины Java. В этой статье он рассматривает модель Visitor, демонстрируя ее использование при обходе данных дерева в Java-программах, а затем переписывает ее с добавлением функциональных зипперов Clojure.

Алекс Миллер, старший инженер, Revelytix

Алекс МиллерАлекс Миллер (Alex Miller), старший инженер компании Revelytix, занимается созданием технологии запросов для федерированного семантического интернета. Последние два года он работает исключительно с Clojure. До прихода Revelytix Алекс был техническим специалистом компании Terracotta, инженером BEA Systems и главным архитектором ПО MetaMatrix. В круг его интересов входят Java, параллельная обработка, распределенные системы, языки программирования и разработка программного обеспечения. Алекс занимается твитингом под псевдонимом @puredanger и блоггингом под псевдонимом http://tech.puredanger.com. Он - организатор конференции разработчиков Strange Loop и группы по изучению функциональных и динамических языков Lounge Lambda. Еще он ― большой любитель мексиканского начос.



06.04.2012

В своих Java-приложениях я много лет использую деревья объектов типа доменов. В последнее время я делаю это с помощью Clojure. Каждый раз я убеждаюсь, что модель Visitor ― это надежный инструмент для работы с деревьями данных. Но в функциональных и объектно-ориентированных языках эта модель работает по-разному и дает разные результаты.

О языке Clojure

Clojure представляет собой динамичный и функциональный вариант языка программирования Lisp, написанный специально для JVM. Читайте о Clojure на портале developerWorks:

В этой статье я рассматриваю деревья доменов и модель Visitor для языка Java, а затем предлагаю несколько реализаций посетителя (visitor) с использованием Clojure. Будучи функциональным языком, Clojure предоставляет новые средства для запросов и манипуляций с данными. В частности, я обнаружил, что интеграция функциональных зипперов в модель Visitor дает значительные преимущества, о которых я расскажу.

Управление символическими деревьями

Один из примеров символического дерева (symbolic tree) ― это представление плана SQL-запросов с такими операциями, как filter, join, union и project. Эти операции работают вместе, выполняя ряд вычислений над исходными данными для получения результирующего запроса.

Например, запрос, приведенный в листинге Листинг 1, описывает объединение таблиц Dept и Employee. Запрос отфильтровывает некоторые результаты, относящиеся к отделу IT, и возвращает конкатенацию имен и фамилий его сотрудников. Результатом должен быть список полных имен всех сотрудников отдела IT.

Листинг 1. Пример SQL-запроса
SELECT Employee.First || ' ' || Employee.Last
FROM Dept, Employee
WHERE Dept.ID = Employee.Dept_ID
  AND Dept.Name = 'IT'

Теперь можно рассмотреть эквивалентное представление символического дерева этого плана запроса, приведенное на рисунке Рисунок 1. Концептуально строки реляционных данных (кортежи) проходят через узлы операций в плане запросов снизу вверх. Затем в вершине извлекаются окончательные результаты запроса.

Рисунок 1. Символическое представление дерева SQL-запроса
Символическое представление дерева SQL-запроса

При использовании подобного дерева с узлами нужно выполнять операции над деревом в целом. К числу возможных операций относятся:

  • сбор всех таблиц, указанных в плане запроса;
  • сбор всех столбцов, используемых в поддереве;
  • поиск верхнего общего узла в плане запроса;
  • сопоставление модели с деревом и внесение в дерево изменений.

Последняя операция особенно полезна, поскольку она позволяет производить символические манипуляции с деревом. Используя модель Filter Pushdown, можно сначала наложить ее на граф, а затем изменить дерево в точке совмещения. Вот модель Filter Pushdown, которую нужно совместить:

  • узел Filter F расположен непосредственно над узлом Join J;
  • у F есть критерии, которые включает в себя только одну таблицу;
  • J представляет собой внутреннее соединение.

Затем можно проделать операцию с деревом, переместив узел Filter под узел Join в направлении соответствующего узла Table. Такие манипуляции (при поддержке соответствующей реляционной теории) лежат в основе оптимизаторов запросов к базе данных. Результирующее дерево показано на рисунке Рисунок 2.

Рисунок 2. Результат применения модели оптимизации Filter Pushdown
График, показывающий результат применения модели оптимизации Filter Pushdown

Модель Visitor часто используется для отделения структуры данных (в данном случае, дерева) от алгоритмов, которые работают над структурой данных. Ниже я продемонстрирую как объектно-ориентированную реализацию на языке Java, так и функциональный вариант на Clojure.


Посетители на языке Java

Чтобы реализовать модель Visitor на языке Java, сначала нужно представить узлы в виде классов Java. Основные иерархии можно построить, как показано на рисунке Рисунок 3. Большинство этих классов ― простые держатели данных (data holders). Например, класс Join содержит выражение для присоединения слева, выражение для присоединения справа, тип соединения и критерий присоединения.

Рисунок 3. Классы доменов Java
UML-схема классов доменов Java

Обратите внимание, что все объекты в иерархии доменов реализуют интерфейс Visitable и метод acceptVisitor, который выглядит вот так:

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

Этот метод acceptVisitor реализует двойную диспетчеризацию, позволяя выбранному вызову метода зависеть не только от типа конкретного объекта, но и от типа посетителя.

Классы посетителей представлены на рисунке Рисунок 4. Базовый интерфейс Visitor содержит метод посещения для каждого конкретного типа в домене. AbstractVisitor реализует пустые версии всех этих методов для облегчения написания конкретных посетителей.

Средства навигации посетителей

Помимо посещения каждого узла, посетитель должен решить, какие узлы следует посетить в качестве дочерних узлов текущего узла. Можно наделить средствами навигации каждого посетителя, но лучше отделить задачи навигации от операций. На самом деле, задачу определения дочерних узлов на уровне типов можно рассматривать как операцию посетителя, которую можно инкапсулировать в самого посетителя. NavigationVisitor берет на себя операции навигации по дереву и делает путешествующего посетителя более легким.

Рисунок 4. Интерфейсы посетителя
UML-схема интерфейсов посетителя

Рассмотрим методы NavigationVisitor:

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

NavigationVisitor полагается на другой экземпляр посетителя, но берет на себя навигацию среди дочерних узлов. Например, посетитель может собирать все экземпляры Column по всему дереву и в этом случае будет выглядеть как в листинге Листинг 2.

Листинг 2. CollectColumnsVisitor
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);
  }
}

Когда этот посетитель находит объект Column в дереве, он сохраняет его в множестве всех столбцов, которые уже найдены. По завершении можно извлечь полный набор объектов Column, как показано в листинге Листинг 3.

Листинг 3. Вызов CollectColumnsVisitor
Node tree = createTree();
CollectColumnsVisitor colVisitor = new CollectColumnsVisitor();
NavigationVisitor v = new NavigationVisitor(colVisitor);
tree.acceptVisitor(v);
System.out.println("columns = " + colVisitor.getColumns());

При наличии этой базовой структуры можно добавить любой из следующих способов оптимизации:

  • навигация посетителей с выполнением операций предварительной, окончательной или специальной навигации;
  • исключение обхода всего дерева;
  • изменение дерева при посещении.

Излишняя сложность посетителей на языке Java

Модель Visitor на языке Java частично решает классическую задачу выражения. Сформулированная Филиппом Уодлером, задача выражения (expression problem) определяет данные программы как множество случаев (типов данных) и множество операций с этими случаями. Представьте их себе в виде двух измерений таблицы. Можно ли добавлять новые типы данных и новые операции без повторной компиляции и с сохранением статических типов?

Модель Visitor создает ситуацию, в которой добавление операций (новые посетители) к множеству существующих типов данных выполняется очень легко. Однако добавлять новые типы данных (классы) к посетителям труднее, так как для всех конкретных типов модели Visitor требуется метод visit(). Эту задачу можно несколько упростить с помощью абстрактного суперкласса, который содержит пустые реализации всех методов для всех посетителей. В этом случае можно изменить только абстрактный класс, и код готов. Посетители не соответствуют требованию отсутствия перекомпиляции, но минимизируют число изменений, необходимых для добавления новой операции. Если учесть также, что добавление нового типа происходит значительно реже, чем добавление новой операции, общая модель дает хороший компромисс: конечно, это лучше, чем введение новой операции в новый метод для всех конкретных типов.

Хотя реализация модели Visitor на языке Java позволяет достичь некоторых основных целей, она также вносит дополнительную сложность: шаблонные методы visit() в каждом конкретном классе, определение навигации для посетителей и т.п. Один из способов обойти эту дополнительную сложность, в то же время сохранив программирование на JVM, ― использование инструментов функционального программирования Clojure для реализации модели Visitor.


Деревья в Clojure

Clojure предоставляет базовый набор постоянных, неизменных структур данных: списки, векторы, map-таблицы, множества и очереди. Обратите внимание, что свойство постоянства здесь относится к изменению данных, а не к хранению данных.

Когда постоянная структура данных "модифицируется", данные не изменяются. Вместо этого возвращается новая неизменная версия структуры данных. Структурный обмен ― это способ сделать постоянные структуры данных Clojure эффективными. Структурный обмен опирается на неизменность данных, чтобы обеспечить возможность обмена между старыми и новыми экземплярами данных.

Неизменность позволяет также упростить определение параллельности и облегчить чтение данных при обмене. Если данные неизменны, их можно считывать без блокирования. Если другой поток "изменяет" данные, результатом будет другой экземпляр данных с близкой внутренней структурой. В функциональном языке программирования постоянные структуры данных важны также для написания чистых функций, свободных от побочных эффектов.

Постоянные структуры данных Clojure

Сделать простую структуру данных типа связанного списка постоянной очень легко; вот список на Clojure, привязанный к переменной с именем "а":

(def a (list 1 2 3))

Clojure представляет собой вариант Lisp, так что оценка происходит путем прочтения выражения как структуры данных Clojure (как правило, это список) с последующей оценкой каждого выражения в структуре данных. После этого первый элемент списка вызывается как функция с остальными элементами в качестве аргументов. Специальная форма def создает переменную пространства имен с определением в первом символе и значением в последующем выражении. Каждое значение в этом связанном списке хранится в ячейке, содержащей значение и указатель на следующую ячейку (или nil, что указывает на конец списка), как показано на рисунке 5.

Рисунок 5. Связанный список
Схема связанного списка

Если затем добавить в начало списка новое значение, это называется построением нового списка (constructing, или cons-ing). Новый список будет содержать все элементы оригинала:

(def b (cons 4 a))
Рисунок 6. Построение связанного списка
Схема построения связанного списка

Для доступа к другим частям списка можно использовать функцию rest и другие функции, но новые списки, созданные из первоначального списка, сохраняют исходную структуру. Две основные функции для работы со списками (и другими последовательностями значений) ― это first (возвращает первый элемент) и rest (возвращает список остальных элементов).

(def c (cons 5 (rest a)))
Рисунок 7. Другие элементы связанного списка
Другие элементы связанного списка

Функциональные структуры данных

Другие постоянные структуры Clojure, такие как векторы и map-таблицы (maps), реализуются с помощью отображаемых проб хэш-массива (hash-array mapped tries), как описано у Фила Багуэлла в "Идеальных хэш-деревьях" (см. раздел Ресурсы). Эта работа выходит за рамки настоящей статьи, но все основные структуры данных Clojure используют эту технику.

Основное отличие при использовании структур данных Clojure вместо Java заключается в том, что мы не изменяем их, а лишь описываем изменение и получаем новую ссылку на неизменную структуру, отражающую эти изменения. При рассмотрении дерева узлов, в котором каждый узел представляет собой структуру неизменных данных, нужно подумать о том, как изменить узел или узлы внутри дерева, не изменяя всего дерева.

Узлы дерева

Прежде чем рассмотреть вопрос о манипуляциях с деревом, рассмотрим структуру данных, которую мы будем использовать для определения каждого узла дерева. Для каждого типа узла нужен четко определенный набор свойств. Полезно также, если каждый узел дерева содержит тип, видимый для Clojure, который можно использовать при выборе реализации функции на этапе выполнения.

При рассмотрении набора ключей и значений очевидным выбором в Clojure является map-таблица, в которой хранятся пары ключ-значение. Пример кода, приведенный в листинге 4, демонстрирует, как создать такую таблицу, добавить в нее значения и извлечь значения из этой таблицы.

Листинг 4. Map-таблица в Clojure
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"}

Каждый из ключей map-таблицы – это ключевое слово Clojure, значение которого всегда есть само это слово и которое идентично тому же ключевому слову, используемому в любом другом месте. Ключевые слова принято использовать в качестве ключа map-таблицы. Ключевые слова также являются функциями. При вызове с map-таблицей функции ключевых слов находят себя в таблице и возвращают собственное значение.

Добавление записей в map-таблицу осуществляется с помощью функции assoc (associate), а удаление ― с помощью функции dissoc (dissociate). Если распечатать map-таблицу, вы увидите запятые между записями, но это исключительно для удобства чтения; в Clojure запятые трактуются как пробелы. В конце листинга Листинг 4assoc возвращает и распечатывает новую map-таблицу, а оригинальная таблица остается неизменной. Структурно обе таблицы содержат в основном одни и те же данные.

Типизированные map-таблицы

В листинге Листинг 5 приведены некоторые вспомогательные функции, которые используются для создания map-таблиц с известным ключом :type. Этот тип будет использоваться ниже для управления полиморфным поведением. Функция node-type по ключу :type извлекает из узла его тип.

Листинг 5. Реализация типизированных узлов дерева
(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))

В листинге вам может встретиться множество новых и расширенных функций Листинг 5, но не паникуйте! Этот код включен для опытных программистов, работающих на Lisp или Clojure, и не обязательно понимать каждую деталь. Основу листинга составляет макрос defnode, который принимает тип узла и вектор имен полей, а затем создает функцию конструктора для составления map-таблиц этого типа. При вызове конструктора передаваемые поля проверяются на предмет соответствия ожидаемым полям, и в случае несоответствия выдается сообщение об ошибке. Одним из преимуществ Clojure как варианта Lisp является то, что код ― это данные (так называемая гомоиконичность). Макросы используют этот факт для манипулирования кодом как данными перед его анализом.

В листинге Листинг 6 приведен Clojure-эквивалент классов домена Java.

Листинг 6. Типы доменов Clojure - zippers/core.clj
(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])

Обход деревьев

Теперь наша задача ― взять дерево map-таблиц Clojure и обойти его или манипулировать им. Так как деревья Clojure – это неизменные структуры данных, любая манипуляция требует создания нового, модифицированного дерева. В качестве первого шага можно вспомнить нашу реализацию модели Visitor на языке Java и попробовать нечто подобное. Мы хотим определить операцию, которая обходит наше дерево map-таблиц, находит в нем модель и применяет манипуляцию в этой точке.

Например, можно искать функции concat с любыми значениями строковых литералов, а затем соединять аргументы в строку, как показано на рисунке 8.

Рисунок 8. Преобразование дерева для вычисления функции concat
Преобразование дерева для вычисления функции concat

Как и в нашем решении Visitor на Java, для каждого типа узла дерева с помощью мультиметода можно реализовать операцию eval-concat. В Clojure мультиметод ― это особый вид функции, которая разбивает вызов на два этапа. При вызове функции вызывается специальная диспетчерская функция с аргументами этой функции. Затем результирующее значение dispatch-value используется для выбора одной из многих возможных реализаций функции.

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

Мультиметод определяется двумя макросами: defmulti и defmethod. Эти макросы связаны друг с другом значением <function-name>. Макрос defmulti указывает диспетчерскую функцию, которая будет использоваться при первом вызове, а также некоторые другие дополнительные функции. Будет много реализаций defmethod, каждая из которых определяет значение dispatch-value, вызывающее выполнение, а также тело функций, выполняемое при их запуске.

Диспетчеризация по типу

Наиболее распространенной диспетчерской функцией в Clojure служит функция class, когда вызов реализации функции зависит от типа единственного аргумента функции, передаваемого мультиметоду.

В нашем примере каждый узел представляет собой map-таблицу, и мы хотим использовать функцию node-type для выбора между различными типами map-таблиц, представляющих каждый узел. Затем, используя defmethod, создаем реализацию мультиметода для каждого типа, которым мы хотим управлять.

Если диспетчерская функция не выявляет никаких возможностей для совмещения мультиметода, вызывается значение диспетчерской функции :default, если оно существует. В нашем примере реализация :default используется для указания того, что все неуказанные узлы должны возвращать сами себя без изменений. Это полезный базовый вариант, подобный базовому классу Visitor в классической модели Visitor.

Листинг Листинг 7 представляет собой полную реализацию мультиметода eval-concat. В этом примере используются такие функции, как new-concat и new-compare-criteria, которые были созданы макросом defnode, вызванным в листинге Листинг 5.

Листинг 7. Обход дерева с помощью мультиметода
(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)}))

Листинг Листинг 8 представляет собой пример мультиметода eval-concat в действии. Этот пример создает небольшое дерево узлов, а затем выполняет в этих узлах мультиметод eval-concat, чтобы вычислить concat строковых литералов. После этого они заменяются объединенной строкой.

Листинг 8. Использование мультиметода eval-concat
(def concat-ab (new-concat {:args ["a" "b"]}))
(def crit (new-compare-criteria {:left concat-ab
                                 :right "ab"}))

(eval-concat crit)

Обратите внимание, что eval-concat в листинге Листинг 7 лишь частично решает поставленную задачу. Для полного решения нужно создать defmethod для каждого класса, который может содержать выражение, и, следовательно, узел concat. Это не трудная, но кропотливая работа.

В частности, важное место в решении занимает обход структуры данных. Вся фактическая модификация дерева выделена в :concat defmethod. Было бы лучше, если бы обход структуры данных представлял собой отдельную родовую операцию.

Обход данных с помощью библиотеки clojure.walk

В основной API Clojure входит библиотека clojure.walk, специально предназначенная для обхода структуры данных. Функциональность этой библиотеки основана на базовой функции walk, хотя она редко вызывается напрямую. Вместо нее гораздо чаще используются функции prewalk и postwalk. Обе они обходят дерево в порядке углубления, но различаются тем, что посещают каждый узел до или после его дочерних узлов. Обе версии в каждом узле применяют функцию, которая возвращает заменяющий узел (или оригинальный узел).

Например, в листинге Листинг 9 показана операция postwalk над неоднородным деревом данных. Сначала мы обходим дерево и передаем функцию, которая просто распечатывает и возвращает посещенный узел. Затем вызываем функцию postwalk, передавая ей функцию, которая ищет целые числа и увеличивает их на единицу, оставляя все остальное неизменным.

Листинг 9. Функция postwalk за работой
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]]

Функции postwalk и prewalk удобны тем, что они "умеют" обходить почти все основные структуры данных Clojure - такие как векторы, списки, множества, и map-таблицы (исключение составляют отсортированные map-таблицы и записи). При использовании clojure.walk не нужно писать никакого кода для навигации, создается только основной код, который находит нужный узел и изменяет его.

Применим postwalk для решения нашей задачи eval-concat из листинга Листинг 10. Найдя узел типа :concat, мы проверяем, можно ли его оценить и вернуть новое значение узла вместо оригинального узла :concat.

Листинг 10. Решение задачи eval-concat с помощью postwalk
(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))

Это гораздо лучшая реализация. Все управление обходом осуществляется внутри postwalk, и нам остается только добавить функцию поиска и изменения дерева.

Рекурсия в модели Visitor

Одна из проблем как оригинальной модели Visitor, так и ее реализации с помощью postwalk состоит в том, что эта модель рекурсивна (см. рисунок Рисунок 9). При вычислении функции модификации в узле все результаты обхода родительских узлов находятся в стеке. Это хорошо видно в реализации Visitor с ее рекурсивными вызовами функции eval-concat. В postwalk они скрыты, но структура остается такой же.

Рисунок 9. Рекурсивные вызовы с помощью clojure.walk
Рекурсивные вызовы с помощью clojure.walk

Рекурсия - это не обязательно плохо; она понятна и для небольших деревьев едва ли составляет проблему. Но в случае более крупных деревьев предпочтительнее делать несколько проходов, чтобы сэкономить память. Вопрос в том, можно ли реализовать модель Visitor без рекурсии?

Функциональные зипперы Clojure

В функциональном программировании решением проблемы обхода и модификации дерева служит зиппер (zipper), наиболее известное описание которого составил Жерар Юэ (см. раздел Ресурсы). Зиппер ― это способ представления структуры данных с помощью локального контекста, так что время навигации (итерации) и изменения о отношению к текущему контексту в основном постоянно. Все изменения локальны по отношению к контексту.

Зиппер дерева, как правило, представляет собой путь от корня к текущей позиции в дереве, плюс контекст поддерева в фокальном узле. Название "zipper" (застежка-молния) намекает на движение по дереву вверх и вниз, причем та часть, которая выше фокального узла, соответствует расстегнутой части молнии, а локальное состояние ― застегнутой части.

В обычном дереве постоянное время доступа возможно только в корне (узел, на который ссылается другой код). Зипперы позволяют фокальному узлу перемещаться по дереву, так что постоянное время доступа сохраняется везде, где бы он ни находился (без учета времени перемещения до этого узла). Часто зипперы изображают в виде дерева из резиновых лент: его можно "подвесить" за любой узел, и тот становится корнем, а левый, правый и родительские пути будут "свисать" из этого фокального узла.

Структуру данных фокального узла обычно называют локалью (location), или loc. В локаль входят текущее поддерево и путь к корню. Рассмотрим упрощенную версию небольшой древовидной структуры, изображенной на рисунке Рисунок 8. На этот раз мы упростим пример, используя векторы, а не map-таблицы.

Листинг Рисунок 10 иллюстрирует, как меняется структура локали по мере обхода дерева, в данном случае сначала вниз (всегда к первому дочернему узлу слева), затем вправо и опять вниз. В каждом случае фокальной точкой становится новый узел, а остальная часть дерева представлена левыми узлами, правыми узлами и родительскими узлами по отношению к фокусу.

Рисунок 10. Структура локали зиппера при обходе дерева
Наглядное представление структуры локали зиппера при обходе дерева.

По мере обхода дерева изменения локальны по отношению к текущему фокальному узлу, то есть все операции выполняются за одно и то же время, за исключением движения вверх. Это главное преимущество зипперов.

Зипперы в Clojure

Основной API Clojure содержит элегантную реализацию зиппера в файле clojure.zip, API которого показан в листинге Листинг 11. Я разделил все функции API на несколько категорий: создание, контекст, навигация, подсчет и изменение.

Функции для создания позволяют создать новый зиппер (то есть, локаль). Основная функция для создания новых зипперов ― функция zipper, которая базируется на трех ключевых функциях:

  • branch? принимает узел и отвечает, может ли этот узел иметь дочерние узлы;
  • children принимает узел и возвращает его дочерние узлы;
  • make-node принимает узел, новый набор дочерних узлов и возвращает новый экземпляр узла.

Функции seq-zip, vector-zip и xml-zip ― это вспомогательные функции, которые вызывают zipper с заданными реализациями последовательностей, векторов и XML-деревьев. (Эта реализация не анализирует XML - она ожидает структуру данных, соответствующую XML, от clojure.xml/parse.)

Листинг 11. clojure.zip API
;; Construction
(zipper [branch? children make-node root]) - 	создает новый зиппер
(seq-zip [root]) - создает зиппер из вложенных последовтельностей
(vector-zip [root]) - создает зиппер из вложенных векторов
(xml-zip [root]) - 	создает зиппер из XML-элементов  

;; Context
(node [loc]) - возвращает узел в текущем положении
(branch? [loc]) - указывает, является ли данное положение точкой ветвления дерева
(children [loc]) - возвращает дочерние узлы данного узла
(make-node [loc node children]) - создает новый узел локали из старого узла и 
новых дочерних узлов 
   
(path [loc]) - возвращает последовательность узлов, предшествующих данному 
положению, начиная с корня
(lefts [loc]) - возвращает последовательность узлов слева 
(rights [loc]) - возвращает последовательность узлов справа

;; Navigation
(left [loc]) - ереходит к левому узлу-брату или возвращает ноль, если его нет
(right [loc]) - переходит к правому узлу-брату или возвращает ноль, если его нет
(leftmost [loc]) - переходит к крайнему дочернему узлу-брату слева или остается на месте
(rightmost [loc]) - переходит к крайнему дочернему узлу-брату справа или остается на месте
(down [loc]) - переходит к крайнему левому дочернему узлу текущей локали
(up [loc]) - переходит к родительскому узлу текущей локали
(root [loc]) - проходит весь путь до корня и возвращает корневой узел 

;; Enumeration
(next [loc]) - 	переходит к следующему узлу в порядке углубления 
(prev [loc]) - 	переходит к предыдущему узлу в порядке углубления
(end? [loc]) - 	конец обхода углубления

;; Modification
(insert-left [loc item]) - 	вставка нового узла-брата слева
(insert-right [loc item]) - 	вставка нового узла-брата справа
(insert-child [loc item]) - 	вставка нового крайнего левого дочернего узла под 
текущим узлом
(append-child [loc item]) - 	вставка нового крайнего правого дочернего узла под 
текущим узлом
(replace [loc node] - 	замена текущего узла новым узлом 
(edit [loc edit-fn args]) - 	замена текущего узла результатом операции edit-fn
(remove [loc]) - 	удаление текущего узла и переход к предыдущему узлу в порядке 
углубления

Функции контекста предоставляют информацию о текущем местоположении в дереве, а функции навигации должны быть хорошо понятны после вышеизложенных обсуждений. В листинге Листинг 12 приведен пример того, как использовать функции контекста и навигации, чтобы обойти дерево и проанализировать его.

Листинг 12. Обход дерева векторов с помощью зиппера
> (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

Итерация зиппера

функции подсчета зиппера позволяют обойти все дерево в порядке углубления, как показано на рисунке Рисунок 11. Этот обход интересен тем, что он итерационный, а не рекурсивный ― это основное различие между обходом с помощью зипперов и описанной выше реализацией clojure.walk.

Рисунок 11. Итерационный обход дерева с помощью зипперов
Обход дерева с помощью зипперов.

Посетитель дерева с применением зипперов

Функции зипперов для подсчета и редактирования дают нам инструменты, позволяющие создать посетителя на основе зиппера, который перебирает узлы дерева и выполняет функцию visitor в каждом из них. Эти инструменты можно соединить, как показано в листинге 13.

Листинг 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))))))

Функция tree-edit принимает структуру зиппера, функцию matcher и функцию editor. Эта функция начинается со специальной формы Clojure loop, которая в конце создает цель для recur. В Clojure loop/recur указывает на концевую рекурсию и не использует записи активации, как другие рекурсивные вызовы. Вызов zip/next переходит к следующему узлу дерева в порядке углубления.

Итерация заканчивается, когда функция zip/end? возвращает значение "истинно". В то же время zip/root поднимется (zip/up) к вершине дерева, применяя на своем пути любые изменения, и возвратит корневой узел. В случае бесконечной итерации к текущему loc применяется функция matcher. В случае совпадения узел и результат этой функции передаются в функцию editor для возможной модификации, и итерация продолжается, начиная с модифицированного узла. В противном случае итерация продолжается с первоначального узла. Функция partial применяет функцию частично с подмножеством ее аргументов и возвращает новую, в которой аргументов меньше. В данном случае мы частично применяем функцию editor, так что edit получает новую функцию с соответствующей подписью.

Необходима также реализация зиппера, способная в процессе обхода работать со стандартными структурами данных Clojure. Функция tree-zipper из листинга Листинг 14 выполняет функции, к которым относятся основные типы collection, что позволяет любой структуре данных Clojure, построенной из этих типов, стать зиппером: branch?, children и make-node. Я решил для каждой функции зиппера использовать мультиметод, что позволит позднее динамически дополнять этот зиппер другими типами, просто за счет добавления новых реализаций метода defmethod.

Листинг 14. Реализация зиппера для дерева
(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))

Вычисление concat

В листинге Листинг 15 мы возвращаемся к нашей задаче вычисления concat путем создания функции match (для поиска узлов concat с литерально-строчными аргументами) и функции editor (для вычисления concat). Функция can-simplify-concat выступает в роли функции matcher, а simplify-concat - в роли функции editor.

Листинг 15. Вычисление concat с помощью zipper 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)

Пока мы добились практически того же уровня сложности, что и при реализации с применением clojure.walk в листинге Листинг 10. Одно из различий между Листинг 10 и Листинг 15 заключается в том, что версия walk объединяет части match и edit, которые в версии zipper разделены. Другим отличием является то, что внутренне версия зиппера использует линейный обход структуры данных методом концевой рекурсии, вместо рекурсивного обхода. Это уменьшает объем памяти, используемой во время итерации, так как глубина стека остается постоянной, а не определяется высотой дерева.

Еще более совершенный посетитель дерева

Изучение полезных на практике посетителей дает несколько общих категорий, которые различаются целью посещения:

  • Finder ищет первый узел, соответствующий определенным критериям, и возвращает его;
  • Collector ищет все узлы, соответствующие определенным критериям, и возвращает их;
  • Transformer ищет совпадения в дереве, изменяет дерево в этом узле и возвращает его;
  • Event generator обходит дерево и вызывает события (как DOM для SAX).

Конечно, начав использовать деревья и управлять ими на практике, можно найти много других любопытных комбинаций и дополнений для этих категорий. Наша нынешняя функция tree-edit не позволяет посетителю указать, что итерацию следует прекратить, или переносить состояние в процессе обхода, так что трудно создать посетителей типа Finder или Collector без использования внешних хранителей состояния.

Еще одно наблюдение после написания многих посетителей состоит в том, что некоторые общие функциональные части должны допускать возможность многократного использования разными посетителями. Например, как finder, так и collector оценивают критерии для узла и определяют, соответствует ли узел этим критериям. В идеале хотелось бы повторно использовать функцию, которая решает эти задачи в обоих случаях. Аналогично, полезно создать посетителей, способных проверять случаи, которые должны вызывать переход к следующему узлу или полное прерывание итерации.

В листинге Листинг 16 показан усовершенствованный посетитель, который применяет множество посетителей в каждом узле, передает состояние по всей итерации и допускает преждевременный выход из узла или всей итерации. Обратите внимание на две функции, которые здесь используются:

  • функция tree-visitor аналогична функции tree-edit, которая обсуждалась выше. Она обходит дерево с помощью зиппера и завершается кодом end?. В каждом узле tree-visitor вызывает нашу вторую функцию, visit-node. Основная особенность tree-visitor заключается в том, что функция visit-node возвращает несколько значений: new-node, new-state и флаг stop. Если значение stop истинно, итерация немедленно прекращается. Состояние предваряется значением initial-state и передается через всю итерацию, позволяя функциям посетителей управлять им как угодно. В конце tree-visitor возвращаются конечное состояние и конечное дерево.
  • Visit-node берет список функций посетителей, каждая из которых подписана (fn [node state]); тот возвращает контекстную map-таблицу, содержащую ключи :node, :state, :stop или :jump. Если возвращается значение :node или :state, оно заменяет входящий узел или состояние. Передача :jump указывает на то, что итерация должна перейти к следующему узлу, пропустив всех оставшихся посетителей текущего узла. Передача сигнала :stop означает, что вся итерация должна прекратиться.
Листинг 16. Усовершенствованный посетитель дерева
(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))))))

Использование функций усовершенствованного посетителя

Так что же можно делать с нашим новым, усовершенствованным посетителем? В листинге Листинг 17 приведен пример коллектора, который ищет строки в нашем дереве. Функция string-visitor ищет узел с нужной строкой и возвращает обновленное состояние, которое принимает узел. Функция string-finder вызывает tree-visitor и string-visitor и возвращает конечное состояние.

Листинг 17. Функция поиска строки
(defn string-visitor
  [node state]
  (when (string? node)
    {:state (conj state node)}))

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

Функцию поиска строки тоже легко написать – пусть она ищет первый узел определенного типа, см. листинг Листинг 18. Соответствующая функция подобна нашим первым функциям посетителей, но в самом начале использует для поиска тип узла. Когда find-first вызывает посетителя, он частично применяет тип к функции matched, что дает функцию, которая просто принимает node и state, как и ожидалось. Обратите внимание, что функция matched возвращает stop=true, чтобы выйти из цикла.

Листинг 18. Поиск узла
(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)])))

Передача нескольких функций

До сих пор мы фактически не использовали возможность передачи нескольких функций. Ключевым моментом здесь является то, что мы хотим разложить функциональность наших посетителей на более мелкие части, а затем рекомбинировать их для создания сложной функциональности. Например, в листинге Листинг 18мы переписали анализатор concat, чтобы он искал узлы :concat (функция 1), содержащие все строки (функция 2), а затем вычислял значение concat (функция 3).

Первый посетитель-анализатор типа создается в родовой функции on. Эта функция возвращает анонимную функцию посетителя, который переходит к следующему узлу, если узел не того типа. Эта функция допускает многократное использование любой цепочкой посетителей, которым необходимо проанализировать оставшуюся часть цепочки по типам с возможностью выхода. Аналогичным образом вторая функция all-strings создает условного посетителя, который ищет узел concat, содержащий все строковые аргументы.

Наконец, мы создаем мультиметод для вычисления выражения, называемый eval-expr. В данном случае, по умолчанию мы вычисляем что-угодно, просто возвращая то же самое. Добавляем дополнительные реализации :concat и :compare-criteria. И этот мультиметод превращается в посетителя с функцией node-eval.

Такую цепочку посетителей легко собрать в составного посетителя chained-example, как показано в листинге Листинг 19.

Листинг 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])))

Разные части этой реализации (например, функции on и node-eval) можно повторно использовать в других цепочках посетителей. Понятие цепочки посетителей приводит к очень гибкой структуре с широкими возможностями структурирования и многократного применения посетителей к дереву.


Другие возможности, предоставляемые посетителями Clojure

Эта статья лишь затрагивает использование зипперов в модели Visitor, только чтобы возбудить аппетит к дальнейшему изучению. Например, вы могли заметить, что структуры on и all-strings в листинге Листинг 18 выглядят одинаково. Обе функции наделяют посетителя фильтром. Вместо цепочки функций, содержащей фильтры, можно наделить посетителя-фильтр с помощью условий, составленных с применением обычных соединителей Clojure. Добавление специального макроса для создания и комбинирования этих условий сделало бы код более компонуемым.

На самом деле, библиотеки функций поиска по шаблону (например, новая библиотека Clojure core.match, см. раздел Ресурсы) позволяют задавать модели с помощью метасимволов, соответствие которым следует искать в структуре данных. Такие библиотеки нетрудно объединить с посетителем дерева, чтобы посетители могли использовать целые модели деревьев. Этот мощный шаг приближает к разговору о проблеме в терминах самой проблемы, абстрагируясь от языка.

Другой аспект модели Visitor, который здесь внимательно не рассматривался, ― порядок итераций. В Revelytix мы всегда обходим узлы в порядке углубления анализа зиппера. В некоторых случаях узлы лучше обходить в обратном порядке, пропуская некоторые узлы или поддеревья, или в каком-то еще. Итерация, по существу состоит из трех операций: start (поиск start loc из корневого узла); next (если это loc, поиск следующего loc) и end? (является ли текущий loc концом итерации?). Легко абстрагировать эти функции в нашей текущей функции tree-visitor и обеспечить готовые и настраиваемые стратегии итераций.

В Clojure весь код ― это также и данные, которые обычно хранятся в виде деревьев s-выражений. Таким образом, все методы, описанные в этой статье, можно использовать не только для изменения данных, но и для изменения кода. Некоторые примеры можно найти в более сложных макросах-утилитах основного API Clojure.

Я надеюсь, что вы воспользуетесь высказанными здесь идеями для построения своих собственных посетителей на Clojure или другом языке и продолжите изучение способов структурирования и управления данными. В разделе Ресурсы приведены ссылки на весь код и примеры, используемые в этой статье, которые хранятся на сайте Github.

Ресурсы

Научиться

Получить продукты и технологии

  • Загрузить исходный код и примеры для этой статьи.

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Технология Java
ArticleID=808884
ArticleTitle=Посетители деревьев Clojure
publish-date=04062012