Ещё не все с этим знакомы, а надо бы, "Чтобы все".

An Applicative Control-Flow Graph Based on Huet’s Zipper.

Цитаты:

To support
optimizations in classic imperative style, we built a control-flow graph using mutable
pointers and other mutable state in the nodes. This decision proved unfortunate:
the mutable flow graph was big and complex, and it led to many bugs. We have
replaced it by a smaller, simpler, applicative flow graph based on Huet’s (1997)
zipper. The new flow graph is a success; this paper presents its design and shows
how it leads to a gratifyingly simple implementation of the dataflow framework
developed by Lerner, Grove, and Chambers (2002)...

The measurements in Table 1 reflect costs with optimization turned off.
With optimization turned on, it is hard to make an apples-to-apples comparison:
the old optimizer uses a dataflow framework that does not compose
analyses and transformations; some of the older optimizations are more conservative
than the newer ones; and some of the older optimizations run once
instead of being iterated to a fixed point. Still, when we compensate for these
differences as best we can, the results are similar: the applicative flow graph
performs about 10% better than its imperative counterpart...

Sapienti sat?

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

T>Ещё не все с этим знакомы, а надо бы, "Чтобы все".

T>An Applicative Control-Flow Graph Based on Huet’s Zipper.

Знакомы уже много лет.
Вполне рабочая модель для определённой стадии компиляции (низкоуровневой оптимизации локального кода в бэкэнде).

T>>Ещё не все с этим знакомы, а надо бы, "Чтобы все".
T>>An Applicative Control-Flow Graph Based on Huet’s Zipper.

M>Знакомы уже много лет.
M>Вполне рабочая модель для определённой стадии компиляции (низкоуровневой оптимизации локального кода в бэкэнде).

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

Ведь намекаешь, так?

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

T>>>Ещё не все с этим знакомы, а надо бы, "Чтобы все".
T>>>An Applicative Control-Flow Graph Based on Huet’s Zipper.

M>>Знакомы уже много лет.
M>>Вполне рабочая модель для определённой стадии компиляции (низкоуровневой оптимизации локального кода в бэкэнде).

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

T>Ведь намекаешь, так?

Конечно.
Ziper и есть дерево, хранящее все ссылки на родителей и потомков, а в самих узлах остаются только примитивные атрибуты.
Если ты в коде увидел, что тебе надо добавить поле или метод в класс, то ты зипером идёшь в класс (перемещаешь фокус), добавляешь новый член класса, и возвращаешься обратно. Очень удобно, наверное.
Поскольку он и есть дерево всех ссылок, то ты не можешь иметь два экземпляра зипера, иначе ты получишь два некогерентных дерева (даже просто перемещая фокус).
Ты не можешь иметь ссылки на узлы дерева, они просто не имеют смысла, так как ничего с этим узлом ты сделать уже не сможешь, не имея зипера с фокусом на этом узле. А его ты иметь не можешь, поскольку ты можешь иметь только один зипер, иначе ты получишь некогерентные деревья.
Когда ты уже насоздавал все узлы в своём дереве, и тебе надо провести просто локальную оптимизацию кода — на здоровье, экспортируй код метода в зипер, оптимизируй, генерируй из оптимизированного результата нэйтивный код. А пока ты хочешь что-то менять в глобальном дереве программы — зипер идёт лесом.

Здравствуйте, thesz, Вы писали:
T>Вот мне моя паранойя говорит, что ты здесь намекаешь на слабую применимость в других стадиях.
T>Ведь намекаешь, так?
Если я всё правильно понял, он говорит об этом в контексте своего symade — а это такой типа напрочь продвинутый редактор + рефакторер (если совсем грубо).
Поэтому ему дерево постоянно приходится перестраивать. Вот он и боится, что из за неизменяемости дерева память будет пухнуть при любых операциях.
А в ленивость — не верит, как та бабушка с электричеством.

T>>>>Ещё не все с этим знакомы, а надо бы, "Чтобы все".
T>>>>An Applicative Control-Flow Graph Based on Huet’s Zipper.
M>>>Знакомы уже много лет.
M>>>Вполне рабочая модель для определённой стадии компиляции (низкоуровневой оптимизации локального кода в бэкэнде).
T>>Вот мне моя паранойя говорит, что ты здесь намекаешь на слабую применимость в других стадиях.
T>>Ведь намекаешь, так?
M>Конечно.
M>Ziper и есть дерево, хранящее все ссылки на родителей и потомков, а в самих узлах остаются только примитивные атрибуты.
M>Если ты в коде увидел, что тебе надо добавить поле или метод в класс, то ты зипером идёшь в класс (перемещаешь фокус), добавляешь новый член класса, и возвращаешься обратно. Очень удобно, наверное.
M>Поскольку он и есть дерево всех ссылок, то ты не можешь иметь два экземпляра зипера, иначе ты получишь два некогерентных дерева (даже просто перемещая фокус).
M>Ты не можешь иметь ссылки на узлы дерева, они просто не имеют смысла, так как ничего с этим узлом ты сделать уже не сможешь, не имея зипера с фокусом на этом узле. А его ты иметь не можешь, поскольку ты можешь иметь только один зипер, иначе ты получишь некогерентные деревья.
M>Когда ты уже насоздавал все узлы в своём дереве, и тебе надо провести просто локальную оптимизацию кода — на здоровье, экспортируй код метода в зипер, оптимизируй, генерируй из оптимизированного результата нэйтивный код. А пока ты хочешь что-то менять в глобальном дереве программы — зипер идёт лесом.

Зипер — Zipper, — это способ описания "пути" до элемента в какой-то структуре.

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

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

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

А то и просто перестраиваю дерево с помощью tying the knot, если удобней.

Если надо, повторяю действия до фиксированной точки.

Откуда ты взял всё вот это отквоченное выше, я не знаю.

T>>Вот мне моя паранойя говорит, что ты здесь намекаешь на слабую применимость в других стадиях.
T>>Ведь намекаешь, так?
T>Если я всё правильно понял, он говорит об этом в контексте своего symade — а это такой типа напрочь продвинутый редактор + рефакторер (если совсем грубо).
T>Поэтому ему дерево постоянно приходится перестраивать. Вот он и боится, что из за неизменяемости дерева память будет пухнуть при любых операциях.
T>А в ленивость — не верит, как та бабушка с электричеством.

Это всё необходимо разъяснить.

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

M>А пока ты хочешь что-то менять в глобальном дереве программы — зипер идёт лесом.

Почему? Изменение, вставка и удаление в зиппере имеют сложность O(1).

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

M>>А пока ты хочешь что-то менять в глобальном дереве программы — зипер идёт лесом.

L>Почему? Изменение, вставка и удаление в зиппере имеют сложность O(1).

Ну как "почему"? Я же там всё написал. Какое имеет отношение сложность вставки к невозможности хранить ссылки на узлы дерева?

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

T>Зипер — Zipper, — это способ описания "пути" до элемента в какой-то структуре.

Нет, зипер это и есть список/дерево.
http://en.wikipedia.org/wiki/Zipper_(data_structure)
А если ты используешь его как путь к элементу, то ты не можешь менять этот элемент без изменения всего дерева (при наличии ссылок на родителя) или всей верхушки дерева (всего начала списка, если это зипер списка).

T>Я не понимаю двух вещей:
T>1) как можно экспортировать что-то в пути до элементов и какой в этом смысл и

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

T>2) чем описание путей до элемента в структуре глобального дерева программы концептуально отличается от описания путей в структуре описания локального графа низкоуровневого представления.

Если ты не собираешься менять это дерево — то ничем.
Если ты его собираешься менять, то изменения в локальном коде (внутри метода) никому не интересны, так как с методом общаются через его декларацию, а его внутренний код не важен. А вот глобальные изменения (добавление типов, методов и пр.) затрагивают всю программу. Тем и отличаются.

T>Ты это из своих каких-то внутренних представлений вывел, по-моему. С реальной жизнью они имеют мало общего.

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

Всё это хорошо, пока делается внутри метода. А если ты это делаешь на глобальном уровне всей программы, то все ссылки на данные внутри старого дерева уже не будут иметь отношения к новому дереву. Ты можешь полностью переписать старое дерево на совершенно новое. Но ты не сможешь вставить новый элемент в старое дерево. То есть у тебя не может быть независимых друг от друга мета-программ, меняющих дерево.

Вот в яве (языке) можно получить доступ к приватным полям и методам outer класса из inner класса, а в JVM этого нельзя. Для реализации такого доступа компилятор генерирует специальные getter/setter-ы для полей или прокси методы для вызова приватных методов другого класса. Если у ты модифицируешь дерево, то ты проходишь этой мета-программкой, когда находишь в локальном коде обращение к private полю outer класса — генерируешь outer классу getter/setter методы "на лету" и подменяешь обращение к полю на эти методы.
Можно сделать в два прохода — проанализировать, какие hidden/proxy методы нужно добавить за первый проход, потом добавить их, и вторым проходом сгенерировать новое дерево. Первый минус — может тебе надо изменить всего один класс, а менять прийдётся всё дерево.
Второй минус заключается в том, что у тебя может быть ещё одна мета-программка, которая тоже хочет проанализировать и чего-то сделать с деревом. Если ты не знаешь заранее всех этих кодо-переписывателей, то ты должен предположить, что после изменения дерева одним плагином, надо прогнать по этому дереву все остальные плагины. Скажем, ты переписал обращения к private полям при помощи первого анализатора/генератора, а потом запустил второй, который сгенерировал новое приватное поле в outer методе и обращение к нему из inner класса. Может сгенерировал, а может и нет. Если у тебя они независимы — то ты не знаешь. И при любом изменении кода должен запускать весь анализ и переписывание кода с нуля. И каждый раз создавая новое дерево.
Из-за этой проблемы семантика компиляторов так фиксирована и правила языка захардкодены в компилятор. Потому они ниразу не расширяемые. Потому никакого мета-программирования в мэйнстриме сейчас нет. Потому что никто не хочет запускать компиляцию по новой, каждый раз, как какая-то пользовательская мета-программа поменяла/сгенерировала кусок кода.
И если для мутабельного дерева эти проблемы так велики, то для иммутабельного дерева, с его сверх-накладными расходами по созданию дерева на сотни мегабайт на каждый чих, это вообще неподъёмная задача.

T>А то и просто перестраиваю дерево с помощью tying the knot, если удобней.

Это кто такой? А то прямой перевод с аглицкого наводит на мысли о мутабельном дереве

T>>Зипер — Zipper, — это способ описания "пути" до элемента в какой-то структуре.
M>Нет, зипер это и есть список/дерево.
M>http://en.wikipedia.org/wiki/Zipper_(data_structure)

Zipper is a purely functional data structure used in functional programming to solve some problems in a way that uses notions like “context” and “hole”.

"hole" и есть участок рассматриваемой структуры данных.

Вот ещё (!!!):

Wikibooks' Haskell has more about this subject

Так что, во-первых, наши ссылки совпадают по смыслу, во-вторых, если хочешь знать больше про Zipper, читай про Хаскель.

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

Почему "всего дерева"-то?

T>>Я не понимаю двух вещей:
T>>1) как можно экспортировать что-то в пути до элементов и какой в этом смысл и
M>Ты хоть читал статью, которую так упорно подсовываешь? Там очень популярно написано, как заносятся данные в их зипер.

Они заносятся в дерево через zipper. Одним только zipper ты можешь построить неправильное дерево.

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

Внутренний код метода может быть сколь угодно сложным. Метод одного человека — программа другого.

Прошу попытаться ещё раз.

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

Вершина дерева и все элементы на пути к вставленному будут другими. Но не у всех элементов дерева поменяются ссылки.

Как ты думаешь, почему сложность вставки в чисто функциональное отображение Map на основе сбалансированного дерева имеет сложность O(log(N)), а не O(N) или O(Nlog(N))? Именно потому, что не всё дерево надо пересоздавать.

M>Вот в яве (языке) можно получить доступ к приватным полям и методам outer класса из inner класса, а в JVM этого нельзя. Для реализации такого доступа компилятор генерирует специальные getter/setter-ы для полей или прокси методы для вызова приватных методов другого класса. Если у ты модифицируешь дерево, то ты проходишь этой мета-программкой, когда находишь в локальном коде обращение к private полю outer класса — генерируешь outer классу getter/setter методы "на лету" и подменяешь обращение к полю на эти методы.
M>Можно сделать в два прохода — проанализировать, какие hidden/proxy методы нужно добавить за первый проход, потом добавить их, и вторым проходом сгенерировать новое дерево. Первый минус — может тебе надо изменить всего один класс, а менять прийдётся всё дерево.

Не всё. Только относящиеся к делу элементы. Давай заново.

M>Второй минус заключается в том, что у тебя может быть ещё одна мета-программка, которая тоже хочет проанализировать и чего-то сделать с деревом. Если ты не знаешь заранее всех этих кодо-переписывателей, то ты должен предположить, что после изменения дерева одним плагином, надо прогнать по этому дереву все остальные плагины. Скажем, ты переписал обращения к private полям при помощи первого анализатора/генератора, а потом запустил второй, который сгенерировал новое приватное поле в outer методе и обращение к нему из inner класса. Может сгенерировал, а может и нет. Если у тебя они независимы — то ты не знаешь. И при любом изменении кода должен запускать весь анализ и переписывание кода с нуля. И каждый раз создавая новое дерево.

Это задача посложней, но тоже решается путём мемоизации (запоминания или кэширования) результатов анализа.

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

Метапрограммирование усложняет анализ программы. Который проводит каждый человек в начале поддержки. Именно поэтому, а не по какой-либо другой причине, оно запрещено в крупных конторах.

Поэтому оно запрещено в Java, как и синонимы типов. Поэтому его нет и в C#. Что будет дальше — посмотрим.

Мнение, что метапрограммирования в мейнстриме нет потому, что оно затрудняет построение IDE, ошибочно. Его опровергает boost с вычислениями на макросах, как минимум, да и вообще существование множества IDE для языка с макросами — C++.

Что самое интересное, boost можно, а самостоятельное метапрограммирование практически нельзя.

M>И если для мутабельного дерева эти проблемы так велики, то для иммутабельного дерева, с его сверх-накладными расходами по созданию дерева на сотни мегабайт на каждый чих, это вообще неподъёмная задача.

Ты отталкиваешься от неправильной посылки "необходимость пересоздания всего дерева на каждый чих".

Вот у тебя и выводы хромают.

T>>А то и просто перестраиваю дерево с помощью tying the knot, если удобней.
M>Это кто такой? А то прямой перевод с аглицкого наводит на мысли о мутабельном дереве

Tying the knot.

Результаты анализа дерева я могу использовать при создании дерева. Более того, я могу воспользоваться результатами анализа строящегося в данный момент дерева.

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

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

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

T>Это всё необходимо разъяснить.

Ну дык эта, просим объяснений. Да на таком уровне чтобы как бабушке про электричество

T>>>Поэтому ему дерево постоянно приходится перестраивать. Вот он и боится, что из за неизменяемости дерева память будет пухнуть при любых операциях.
T>>>А в ленивость — не верит, как та бабушка с электричеством.
T>>Это всё необходимо разъяснить.
M>Ну дык эта, просим объяснений. Да на таком уровне чтобы как бабушке про электричество

Наливай!