Проектирую типы для представления синтаксического дерева. Хочется, чтобы у узла, представляющего класс, можно было запросить список его членов, а у члена класса можно было запросить его родительский узел. В обычном ООП я бы сделал это с помощью mutable коллекций. А как быть, если я хочу написать это в функциональном стиле, без mutable? Как это обычно делается?

Здравствуйте, nikov, Вы писали:

N>Проектирую типы для представления синтаксического дерева. Хочется, чтобы у узла, представляющего класс, можно было запросить список его членов, а у члена класса можно было запросить его родительский узел. В обычном ООП я бы сделал это с помощью mutable коллекций. А как быть, если я хочу написать это в функциональном стиле, без mutable? Как это обычно делается?
Создать словарь (элемент, родитель)?

N>Проектирую типы для представления синтаксического дерева. Хочется, чтобы у узла, представляющего класс, можно было запросить список его членов, а у члена класса можно было запросить его родительский узел.

А вот это конкретно зачем?

M>В обычном ООП я бы сделал это с помощью mutable коллекций. А как быть, если я хочу написать это в функциональном стиле, без mutable? Как это обычно делается?

Tying the knot

data SomeParent = SomeP [Child]

data Child = Child SomeParent Information

mkChild parent info = Child parent info
mkParent childInfo = self
    where
        self = SomeParent (child self childInfo)

Однако, если у нас появляется SomeParent2, то всё сразу усложняется (появляется класс ChildParent и forall в варианте Child).

При изменении AST Child надо перестраивать.

Нехорошее решение, в общем.

И я не вижу, зачем оно необходимо.

Если в процессе обработки Child надо обращаться к информации, вычислимой из предка, то лучше эту информацию вычислить и передать явно. Так будет безопасней.

Здравствуйте, nikov, Вы писали:

N>Проектирую типы для представления синтаксического дерева. Хочется, чтобы у узла, представляющего класс, можно было запросить список его членов, а у члена класса можно было запросить его родительский узел. В обычном ООП я бы сделал это с помощью mutable коллекций. А как быть, если я хочу написать это в функциональном стиле, без mutable? Как это обычно делается?

Cергей дело говорит. Подумай, может быть, что-нибудь типа зиппера подойдёт больше?

Здравствуйте, nikov, Вы писали:
N>Проектирую типы для представления синтаксического дерева. Хочется, чтобы у узла, представляющего класс, можно было запросить список его членов, а у члена класса можно было запросить его родительский узел. В обычном ООП я бы сделал это с помощью mutable коллекций. А как быть, если я хочу написать это в функциональном стиле, без mutable? Как это обычно делается?

С точки зрения scheme:
Технически: список можно закольцевать (с помощью set-cdr! или как-то хитро обернувшись вокруг circular-list).
Идеологически: в принципе, страшного в этом с точки зрения scheme нет. Например, библиотечными функциями поддерживаются кольцевые списки. Правда, в данном случае получается не просто кольцевой список — а граф (т.е. возможно, что придется писать свои обертки для функций работы со списками), но сути это не меняет.

Кстати, если у Вас граф — может быть его и реализовывать нужно как граф, а не как дерево с "обратными" ссылками?

Здравствуйте, nikov, Вы писали:

N>Проектирую типы для представления синтаксического дерева. Хочется, чтобы у узла, представляющего класс, можно было запросить список его членов, а у члена класса можно было запросить его родительский узел. В обычном ООП я бы сделал это с помощью mutable коллекций. А как быть, если я хочу написать это в функциональном стиле, без mutable? Как это обычно делается?

не понятно, причём тут мутабельность?? речь о том, что ты его переподчинять будешь в уже построенном дереве?

а так-то какие проблемы:

data Tree a = Tree {node::a, parent::Maybe (Tree a), childs::[Tree a]}

Здравствуйте, nikov, Вы писали:

N>Проектирую типы для представления синтаксического дерева. Хочется, чтобы у узла, представляющего класс, можно было запросить список его членов, а у члена класса можно было запросить его родительский узел. В обычном ООП я бы сделал это с помощью mutable коллекций. А как быть, если я хочу написать это в функциональном стиле, без mutable? Как это обычно делается?

Без mutable это делается ровно одним способом — построением нового дерева. Целиком нового, а не только верхушки.
Если у тебя есть родитель и у него два под-узла, то при изменении одного под-узла тебе надо будет создать нового родителя, и создать новый второй под-узел, чтоб он указывал на нового родителя.
Я тебе больше скажу — установка любого атрибута у узла, при immutable данных, потребует от тебя создать полностью новое дерево.
Ты всё ещё хочешь работать с immutable AST?
Тогда что-то умное по этому поводу можно поискать в Clean-е.

N>Проектирую типы для представления синтаксического дерева. Хочется, чтобы у узла, представляющего класс, можно было запросить список его членов, а у члена класса можно было запросить его родительский узел. В обычном ООП я бы сделал это с помощью mutable коллекций. А как быть, если я хочу написать это в функциональном стиле, без mutable? Как это обычно делается?

Вдогонку.

STRef/IORef тоже есть, но это не функциональный стиль.

Здравствуйте, mkizub, Вы писали:

M>Ты всё ещё хочешь работать с immutable AST?
Это единственно разумное представление AST.
Если конечно сделаеть его правильно.
А ссылки на парента если очень хочется сделать можно через таблицу parentId -> parent.
Только оно очень не часто нужно если работать в функциональном стиле.

Здравствуйте, WolfHound, Вы писали:

WH>Если конечно сделаеть его правильно.

Вот и расскажи как правильно.

WH>А ссылки на парента если очень хочется сделать можно через таблицу parentId -> parent.

Таблица, разумеется, immutable? И всю таблицу пересоздавать, когда меняется какой-либо узел. Мало было тормозов, добавим ещё табличный double dispatching.

WH>Только оно очень не часто нужно если работать в функциональном стиле.

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

Здравствуйте, mkizub, Вы писали:

M>Вот и расскажи как правильно.
http://en.wikipedia.org/wiki/Zipper_(data_structure)
И дальше по ссылкам.

M>Таблица, разумеется, immutable?
Разумеется.

M>И всю таблицу пересоздавать, когда меняется какой-либо узел.
Ух... как все запущено...
http://rsdn.ru/forum/message/3290129.flat.aspx

Автор: WolfHound
Дата: 13.02.09

Можешь сам посчитать сколько пересоздается...

M>Мало было тормозов, добавим ещё табличный double dispatching.
Оперция редкая.
Ибо в большинстве случаев нафиг не нужная.

M>Ну, типа, пробежаться по всему дереву/графу и найти этого родителя.
Зачем по всему?

M>Вот и расскажи как правильно.
WH>>А ссылки на парента если очень хочется сделать можно через таблицу parentId -> parent.
M>Таблица, разумеется, immutable? И всю таблицу пересоздавать, когда меняется какой-либо узел. Мало было тормозов, добавим ещё табличный double dispatching.

Узлы не меняются в процессе анализа, поэтому ничего делать не надо.

Структуру всё равно надо пересоздавать в процессе синтеза структуры по результатам анализа. Я уж находился в своё время по изменяемым структурам. Чихнул разок, и перестраивай инварианты. Не дай бог, что забудешь.

WH>>Только оно очень не часто нужно если работать в функциональном стиле.
M>Ну, типа, пробежаться по всему дереву/графу и найти этого родителя. Расходы мизерные, с учётом того, что для изменения узла теперь надо будет пересоздавать только верхушку дерева, а не всё дерево.

Ты объясни, зачем нужно родителя искать.

Типовой пример приведи, пожалуйста.

А то писал-писал транслятор, да так ни разу родителя и не пришлось искать. Может, я что упускаю?

Здравствуйте, thesz, Вы писали:

T>Узлы не меняются в процессе анализа, поэтому ничего делать не надо.

Вот я Java все методы интерфейса public, но писать этот public не нужно, он автоматически вставляется.
Ты анализируешь AST, обнаруживаешь, что метод интерфейса не имеет флага public и этот флаг ему вставляешь.
Или ты вставляешь всем типам супер-тип Object. И так далее.
Нет?
Ты вставил методу интерфейса флаг public ещё в процессе парсинга?
Ты автоматом вставил супер-тип, если он не указан?
Отлично. Так можно. Но это hardcoded семантика. Подобный компилятор очень трудно модифицировать, даже под новую версию языка.

T>Структуру всё равно надо пересоздавать в процессе синтеза структуры по результатам анализа. Я уж находился в своё время по изменяемым структурам. Чихнул разок, и перестраивай инварианты. Не дай бог, что забудешь.

Нужно. В один pass компилятора можно уместить кучу анализа, и пересоздать дерево один раз за pass.
Тогда у тебя весь анализ смешан в кучу. Ты уже не сможешь разделить анализ супер-типа и флагов методов, если они делаются в один проход.
Зато, если всё свалить в кучу и минимизировать количетво проходов — получается быстро.
Но нерасширяемо.

T>Ты объясни, зачем нужно родителя искать.
T>Типовой пример приведи, пожалуйста.

Ну, переписать одну семантическую конструкцию на другую. Заменить один узел на другой. Такскать за собой список родителей не интересно, так как в общем случае у нас граф, а не дерево.
Или просто найти узел по имени (резолвинг символов). Надо пройти по дереву с листика до корешка. Делать этот резолвинг один раз, обходя дерево от корня к листикам — не получится, подставил макрос, и тебе надо делать резолвинг по новой.

T>А то писал-писал транслятор, да так ни разу родителя и не пришлось искать. Может, я что упускаю?

Расширяемость арихитектуры.
Можно без родителя, можно без расширяемости и независимости отдельных частей компилятора. Это даже в 100 раз быстрее будет работать (если не ставить себе целью испльзовать только immutable данные). Но модифицируемость и расширяемость компилятора будет на нуле.

Здравствуйте, mkizub, Вы писали:

M>Ну, переписать одну семантическую конструкцию на другую. Заменить один узел на другой. Такскать за собой список родителей не интересно, так как в общем случае у нас граф, а не дерево.
M>Или просто найти узел по имени (резолвинг символов). Надо пройти по дереву с листика до корешка. Делать этот резолвинг один раз, обходя дерево от корня к листикам — не получится, подставил макрос, и тебе надо делать резолвинг по новой.

И когда нужен родитель-то?

T>>Узлы не меняются в процессе анализа, поэтому ничего делать не надо.
M>Вот я Java все методы интерфейса public, но писать этот public не нужно, он автоматически вставляется.
M>Ты анализируешь AST, обнаруживаешь, что метод интерфейса не имеет флага public и этот флаг ему вставляешь.
M>Или ты вставляешь всем типам супер-тип Object. И так далее.
M>Нет?
M>Ты вставил методу интерфейса флаг public ещё в процессе парсинга?
M>Ты автоматом вставил супер-тип, если он не указан?
M>Отлично. Так можно. Но это hardcoded семантика. Подобный компилятор очень трудно модифицировать, даже под новую версию языка.

Это вам трудно, нам как два байта переслать.

T>>Структуру всё равно надо пересоздавать в процессе синтеза структуры по результатам анализа. Я уж находился в своё время по изменяемым структурам. Чихнул разок, и перестраивай инварианты. Не дай бог, что забудешь.
M>Нужно. В один pass компилятора можно уместить кучу анализа, и пересоздать дерево один раз за pass.
M>Тогда у тебя весь анализ смешан в кучу. Ты уже не сможешь разделить анализ супер-типа и флагов методов, если они делаются в один проход.
M>Зато, если всё свалить в кучу и минимизировать количетво проходов — получается быстро.
M>Но нерасширяемо.

Объясни. Не понял.

Это противоречит или подтверждает мои слова?

T>>Ты объясни, зачем нужно родителя искать.
T>>Типовой пример приведи, пожалуйста.
M>Ну, переписать одну семантическую конструкцию на другую. Заменить один узел на другой. Такскать за собой список родителей не интересно, так как в общем случае у нас граф, а не дерево.
M>Или просто найти узел по имени (резолвинг символов). Надо пройти по дереву с листика до корешка. Делать этот резолвинг один раз, обходя дерево от корня к листикам — не получится, подставил макрос, и тебе надо делать резолвинг по новой.

Это я опять не понимаю.

У нас есть отдельный этап анализа окружения, чтобы все имена были определены. Его, наверное, надо делать после макросов, нат?

T>>А то писал-писал транслятор, да так ни разу родителя и не пришлось искать. Может, я что упускаю?
M>Расширяемость арихитектуры.
M>Можно без родителя, можно без расширяемости и независимости отдельных частей компилятора. Это даже в 100 раз быстрее будет работать (если не ставить себе целью испльзовать только immutable данные). Но модифицируемость и расширяемость компилятора будет на нуле.

Как в компиляторе заменили изменяемое представление графа на чисто функциональное, и как от этого случилось сокращение кода втрое, исчезло большинство ошибок, стало возможным написать многие дополнительные оптимизации и (барабанная дробь!)

СКОРОСТЬ УВЕЛИЧИЛАСЬ НА 10%

Я эту ссылку постил всюду, но она того стоит.

Короче говоря, опыт опровергает твои слова.

Здравствуйте, Mr.Cat, Вы писали:

MC>Кстати, если у Вас граф — может быть его и реализовывать нужно как граф, а не как дерево с "обратными" ссылками?

А что если структуру данных обозвать "граф", то проблема исчезает?

Тут основной вопро в том, что неизменяемые объекты не могут иметь взаимных ссылок. Стало быть нужно или использовать изменяемые переменные или какие-то третьи структуры данных которые нужны только для того, чтобы связать два объекта обратной ссылкой.

Упомянутый зипер из той же оперы.

Здравствуйте, nikov, Вы писали:

N>Проектирую типы для представления синтаксического дерева. Хочется, чтобы у узла, представляющего класс, можно было запросить список его членов, а у члена класса можно было запросить его родительский узел. В обычном ООП я бы сделал это с помощью mutable коллекций. А как быть, если я хочу написать это в функциональном стиле, без mutable? Как это обычно делается?

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

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

Вместо такой вот структуры

class Parent
{
    List<Child> childs = new ArrayList<Child>();
}

class Child
{
    Parent parent;
    
    public String getChildInfoString()
    {
        return child.getName() + "; parent:" + parent.getName();
    }
}

нужно использовать что-то вроде

class Parent
{
    List<Child> childs = new ArrayList<Child>();
}

class Child
{
    public String getChildInfoString()
    {
        return child.getName();
    }
}

class ChildHelper
{
public static String getChildInfoString(Child child, Parent parent)
{
    return child.getChildInfoString() + "; parent:" + parent.getName();
}

Если для данного child нужно получить его parent, то делается это например с помощью хэштаблицы childId->parent. В этом случае разумно ввести объект-контейнер, который бы разруливал обратные зависимости.

class Tree
{
Map<Integer, Parent> map = new HashMap<Integer, Parent> ();

public Parent getParent(Child child)
{
return map.get(child.getId());
}
}

Здравствуйте, LaPerouse, Вы писали:

LP>Если для данного child нужно получить его parent, то делается это например с помощью хэштаблицы childId->parent. В этом случае разумно ввести объект-контейнер, который бы разруливал обратные зависимости.

Этот контейнер ничем не лучше обратных ссылок, даже хуже. Он
а) дублирует дерево
б) занимает намного больше места
в) намного тормознутей по сравнению с прямой ссылкой
и при этом не решает никаких проблем, так как при обновлении дерева тебе надо синхронно менять этот контейнер, что ничем не лучше синхронного изменения двух ссылок (родителя на под-узел и под-узла на родителя).

С остальными мыслями по поводу вредности ссылок на родителя совершенно согласен.

Кстати, если уж держать ссылки на родителя, то имеет смысл и держать поле, которым родитель ссылается на под-узел.
Если, конечно, в родителе под-узлы структурированы, а не свалены в один список.
То есть, если у нас

class IfStat {
  Expr condition;
  Expr then;
  Expr else;
}

то для Expr неплохо бы знать и где он находится, в comdition, then или else поле у родителя.
Кроме скорости удаления, вставки и проверки целостности дерева, это ещё и даёт возможность держать мета-информацию о поле родителя.
Скажем, про поле else можно написать, что оно optional, а про condition, что требует boolen выражения, что это скалярный или векторный слот (поле) родителя и пр.
Эта-же мета-информация о полях родителя прекрасно подходит для обхода дерева.

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

Здравствуйте, VladD2, Вы писали:

VD>Тут основной вопро в том, что неизменяемые объекты не могут иметь взаимных ссылок.

Почему не могут? Обычные рекурсивно описанные объекты (точнее значения). Ленивые бесконечные списки, деревья с циклами, графы, наконец...

Здравствуйте, geniepro, Вы писали:

G>Здравствуйте, VladD2, Вы писали:

VD>>Тут основной вопро в том, что неизменяемые объекты не могут иметь взаимных ссылок.

G>Почему не могут? Обычные рекурсивно описанные объекты (точнее значения). Ленивые бесконечные списки, деревья с циклами, графы, наконец...

Бесконечные списки — совершенно из другой серии, если они односвязные.

Давай рассмотрим простейший случай: A ссылается на B, B ссылается на A.
В случае ИП все легко и понятно — поле, которым объект класса A (назовем его a) ссылается на объект класса B (пусть будет b) есть просто ссылка, то есть альтернативное наименование все той же сущности.
Что же будет в случае ФП? Получим, что b должен содержаться в a, a дожен содержаться в b, получается этакая бесконечная рекурсия, которую без ленивости не разрулить. Но стоп, ленивость — это ведь не есть неотъемлимая составляющая ФП? Безусловно, это так, и все с этим вроде как согласны. Тогда отсюда следует простой вывод: функциональное программирование как парадигма не расчитана на подобное применение. Иными словами, это есть ограничение функциональное парадигмы.