[design patterns] обход AST: visitor или виртуальные методы?

Visitor однозначно. Потому что обходящему потребуются наверняка дофига сопутствующей информации о которых АСТ знать незачем.

Ну и переиспользование опятьже. Добавлять каждый раз новый виртуальный метод - дурной тон.

Да, это так, но:

- при добавлении в язык новых фич - и добавлении новых типов узлов в AST - все равно придется патчить все визиторы, что по объему работы не сильно проще добавления новых виртуальных методов;

- визиторы, AFAIK, ориентированы на относительно редко меняющуюся библиотеку классов, для которой часто приходится писать новые, не предусмотренные ранее алгоритмы; в компиляторе же набор алгоритмов и структур данных более-менее известен заранее (а оптимизации, которые действительно могут добавляться в произвольном количестве по мере их изобретения, все равно по большей части делаются не над AST, а над трехадресным кодом);

- в случае визиторов входящие в AST объекты удобно делать максимально открытыми для чтения и модификации методами визитора (проще всего сделать все поля публичными) - не будет ли это, в свою очередь, дурным тоном?

> - при добавлении в язык новых фич - и добавлении новых типов узлов в AST - все равно придется патчить все визиторы, что по объему работы не сильно проще добавления новых виртуальных методов;

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

в случае визиторов входящие в AST объекты удобно делать максимально открытыми для чтения и модификации методами визитора (проще всего сделать все поля публичными) - не будет ли это, в свою очередь, дурным тоном?

Дурным тоном ИМХО является использование интерфейсов плохо подходящих задаче, но следующих какому-либо набору соглашений. Кстати, в небезынтерсной книжке Beautiful Code, приводится пример программы, которая красива как раз за счёт исопльзования структур с открытыми полями (Глава 6. Framework for Integrated Test: Beauty Through Fragility).

«Дурной тон» относительно открытости полей - это в тон «дурному тону» добавления новых виртуальных методов :).

Остальные визиторы при изменении AST могут сломаться, особенно если тип значения, возвращаемого методом visit(), не void.

И спасибо за ссылку на Beautiful Code. Давно стоит на полке, но все руки не доходили почитать. А статья действительно стоящая!

Что то я не пойму. Интерфейс это single dispatch. Визитор это double dispatch. Как между ними можно выбирать?

>Остальные визиторы при изменении AST могут сломаться, особенно если тип значения, возвращаемого методом visit(), не void.

Не понял. При изменении какого AST? Это же рантаймовая сущность.

Видимо, в данному случае одну и ту же задачу можно решить с помощью как single dispatch, так и double dispatch.

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

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

мне кажется, что *свои* классы (для внутреннего, скажем, внутрикомпиляторного пользования) можно (и нужно) писать без визиторов

( http://www.linux.org.ru/people/ien/profile это случаем не ты? )

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

Нет, не я.

Компилятор - для того, чтобы как следует разобраться, как они делаются, и заодно изучить, наконец, Яву :).

Я могу сказать почему я выбрал визетеры для этой задачи: нетривиальная интерпретация подразумевает кучу вспомогательной функциональности и ее удобнее использовать и реализовывать в классе-визитере. Плюс пихать все это в АСТ не хотелось.

мультиметоды

Я бы Visitor-ом сделал, хотя бы потому что код относящийся к одной функциональности не будет размазан по всем классам иерархии.

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

А The Right Thing - не использовать вообще для этого Java, потому что это глупо. Ведь есть же та же Scala, с ADT и pattern matching-ом, где все это делается намного кошернее.

А, да, если уж про совсем The Right Thing говорить, с большими буквами T и R, то это вообще будет очень далеко от Java: библиотека «Scrap your boilerplate» в Haskell.

http://www.haskell.org/haskellwiki/Scrap_your_boilerplate

Это же извращение, через жопу сделанный visitor на стероидах.
Вот нет чтобы сразу взять нормальный язык, с нормальной поддержкой мультиметодов - Common Lisp, например.

Вот нет чтобы сразу взять нормальный язык

именно это он и предложил :)

> А The Right Thing - не использовать вообще для этого Java, потому что это глупо. Ведь есть же та же Scala, с ADT и pattern matching-ом, где все это делается намного кошернее.

полностью одобряю — скала с паттерн матчингом вместо визитора

а яву изучать можно, если надо, чтобы вытошнило

>а яву изучать можно, если надо, чтобы вытошнило

в квотезы!

Таки да. Но в яве их нет :).

> А, да, если уж про совсем The Right Thing говорить, с большими буквами T и R, то это вообще будет очень далеко от Java: библиотека «Scrap your boilerplate» в Haskell.

С Haskell все как раз ясно и просто, там и вопроса такого не возникло бы :). Меня-то сейчас интересует именно канонический стиль решения подобных задач на Java.

> полностью одобряю — скала с паттерн матчингом вместо визитора

Если писать серьезно, то лучше сразу Haskell, как тут уже сказали :).

а яву изучать можно, если надо, чтобы вытошнило

Ну отчего же. Ява пока что мне кажется очень приятным языком, если с C++ сравнивать.

> Это же извращение, через жопу сделанный visitor на стероидах.

Это не извращение, ты не понял ни хрена. Это visitor, устойчивый к изменениям структуры AST. И код получается в разы понятнее и компактнее, чем любое ООП-говно.

Вот нет чтобы сразу взять нормальный язык, с нормальной поддержкой мультиметодов - Common Lisp, например.

Мультиметоды тут на хрен не нужны, как и вообще ООП. На CL то же самое прекрасно делается макрами.

> С Haskell все как раз ясно и просто, там и вопроса такого не возникло бы :)

Ясно и просто - это будет до фига boilerplate-кода, который надо переписывать каждый раз как меняется AST. Scrap your boilerplate - это нетривиальный хак. Но зато очень полезный и красивый хак.

Ну отчего же. Ява пока что мне кажется очень приятным языком, если с C++ сравнивать.

угу

class AbstractClassTest1
{
    static abstract class Parent {
        abstract public void say();
    };
    static class Child extends Parent {
        public void say() { System.out.println("Hello, Java World!"); };
    };
    static Parent innocent_function()
    {
        if( System.currentTimeMillis()%10 != 0 ) {
            return new Child();
        }else{
            Parent[] a = new Parent[1];
            return a[0]; /* Mu-ha-ha! */
        }
    }
    public static void main(String[] args)
    {
        Parent p = innocent_function();
        p.say();
    }
};

$ javac AbstractClassTest1.java 
$ java AbstractClassTest1 
Hello, Java World!
$ java AbstractClassTest1 
Hello, Java World!
$ java AbstractClassTest1 
Exception in thread "main" java.lang.NullPointerException
        at AbstractClassTest1.main(AbstractClassTest1.java:21)
$

>> С Haskell все как раз ясно и просто

Ясно и просто - это будет до фига boilerplate-кода, который надо переписывать каждый раз как меняется AST. Scrap your boilerplate - это нетривиальный хак. Но зато очень полезный и красивый хак.

Хак действительно нетривиальный и замечательный, но когда он уже реализован и Data.Generics есть под рукой, все становится несколько проще и яснее :).

Ну, около сарая лежат грабли, да. Но в плюсах (я все-таки с C++ яву сравнивал) граблей все-таки несравненно больше, и они заботливо разложены в самых посещаемых местах :).

> Parent[] a = new Parent[1];

return a[0]; /* Mu-ha-ha! */

И чего ты хотел этим сказать?

return new Parent[]{ new Child() }; было не написать?

Конечно нет. Ведь в джаве ВНЕЗАПНО можно обратиться к null !!11 А мировая общественность этого не знает, убаюканная сладкоречивыми маркетологами!!1

> И чего ты хотел этим сказать?

То что хотел сказать — сказать не получилось. Пример получился непоказательный, все свелось к неинициализированной переменной.

Чего там ещё неинициализировано? Всё там инициализировано прекрасно. null-ом. Тоже не понял, что ты хотел сказать этим примером.

Мог бы написать просто и понятно:

    static Parent innocent_function() 
    { 
        if( System.currentTimeMillis()%10 != 0 ) { 
            return new Child(); 
        }else{ 
            return null;
        } 
    }

Было бы то же самое :)

> return null; Было бы то же самое :)

Все иерархии классов, абстрактность, ... имеют смысл только до тех пор, пока значение не null. В яве (вроде?) нет формального определения NotNullable<T>, так что значение null для NotNullable<Parent>, которое *подразумевалось* вместо Parent, можно считать не иницилизированным значением.

Вот в плюсах я бы написал Parent& innocent_function() {....} и дырки этой не было бы.

> Вот в плюсах я бы написал Parent& innocent_function() {....} и дырки этой не было бы.

Т.е. в *настоящий момент* претензия «в яве можно создать массив из абстрактных объектов» действительно бессмыслена; надо было выдать притензию «нет типа NotNullable<T>; если он и есть, то невозможно создать массив из NotNullable<T>».

Parent& innocent_function() {
  Parent *p = null;
  return *p;
}

оно? :)

если на Яве, то скорее всего визитор. Хотя и у него есть свои ограничения, он не очень-то удобен. Проще руками обход написать. Либо, не совсем руками — например, ANTLR может сгенерировать Tree Walker по Tree Grammar.

> (а оптимизации, которые действительно могут добавляться в произвольном количестве по мере их изобретения, все равно по большей части делаются не над AST, а над трехадресным кодом);

не всегда так. Проще делать максимально простой кодогенератор, а оптимизации проверяют семантическую корректность, и следовательно, им нужен трансформированный AST (семантическое дерево)

> Интерфейс это single dispatch. Визитор это double dispatch. Как между ними можно выбирать?

визитор — это реализация double dispatch средствами single dispatch, через коллбеки. Оно будет не нужно с нормальными generic методами и нормальным мультидиспатчем. «Визитор может сломаться» и означает, что пытаются запихнуть более многомерную диспетчеризацию в одномерную.

NULL большими буквами, а так и правда оно :-)

g++ -Wall -Wextra молчит, даже варнингов не выдает... нда...

>В яве (вроде?) нет формального определения NotNullable<T>

http://robaustin.wikidot.com/annotations-and-notnull

>Вот в плюсах я бы написал Parent& innocent_function() {....}

И либо отказываться от указателей (о_О) либо просто переносить ошибку в другое место.

> http://robaustin.wikidot.com/annotations-and-notnull

This JSR (305) is currently Inactive. (зачахло в сентябре 2006)

This means that the JSR has not gone final and that its Spec Lead and Expert Group have not published a milestone draft for their JSR in more than 18 months. This may mean that the specification has reached a particularly difficult stage in its development, or that the community interest in the JSR has waned.

> И либо отказываться от указателей (о_О) либо просто переносить ошибку в другое место.

нет конечно

хотя бы:

давать как минимум варнинги на все случаи конвертации из указателя в ссылку; иметь одну (или несколько) написанных юзером (generic) функций для конвертации, в которых этот варнинг подавляется прагмой; эта функция будет выбрасывать исключение, которе можно ловить и ошибку обрабатывть