Какие бывают преобразования фрагмента кода?

Открыл для себя лисп или компилятор решил написать?

Можно CSE, можно loop-unrolling, грабить корованы и выносить constant expression за его пределы, много всего.

ни то ни другое. меня интересует не какие задачи можно решать, a КАК их можно решать

Ты же вроде питонист? Если да, посмотри rope, там как и с чем и почему много и до кучи.

Можно здесь посмотреть (да-да, я опять со своим Groovy): AST Transformations.

не какие задачи можно решать, a КАК их можно решать

А AST у тебя небось в xml? Тогда добавь к своему КАК ещё и технические трансформации.

Правильно товарищ тебе подсказал - у лиспа самое простое AST. Ибо он сам по себе дерево. Исчезает промежуточный (и трудоёмкий) слой реализации. Если я тебя правильно понял, то это самое КАК исчезает.

не какие задачи можно решать, a КАК их можно решать

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

ну, тривиальное, например - расчёт константных выражений...

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

Другая крайность - причесываем AST рекурсивно какой нибудь функцией, функция принимает узел AST, и возвращает eго замену. Так можно делать что угодно, но слишком брутально иногда выходит.

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

Как еще можно извращаться?:-)

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

Упаси Боже, ненавижу XML! Реализация неважна.

Такая аналогия. Я спрашиваю"есть вектор, что с ним можно делать?" Ожидаемый ответ - вектора можно складывать, умножать скалярно и на число. A мне начинают рассказывать как с их помощью моделировать космические корабли на просторах большОГО театра...

см. выше:-)

Вопрос, a рекурсия хвостовая Или обычная? T. e. функция получает уже обновленный узел, или исходный?

Насчет под классов преобразований я ж понятия не имею какие они есть...:-(

Как еще можно извращаться?

Ещё можно просто стрить новое AST с нуля на основании семантики (с точки зрения преобразователя) полученного AST.

Например, на входе

res = for (i in seq, j in 1..100) { collect tuple(i, j) }

на выходе

{
   res = new Collection;
   for(var i = seq.Iterator(); i.hasNext(); i.Next())
      for(int i = 1; i<=100; j++)
         res.add(tuple(i, j));
}

у лиспа самое простое AST

У лиспа AST ничуть не проще AST в более других языках.

Спасибо, но это же фактически вариант 2? Да еще и в особо изощренной форме:-)

Ну.... да, спасибо. Задачи несколько другие, но это тоже пригодится:.)

Самый удобный способ - паттерн-матчинг. Посмотри, как сделаны макросы в Scheme, например.

Офигеть, я не знал что такое есть в существующих ЯП. В C++ точно такой фичи нет.

Хо-хо! Да до кучи. destructuring-bind в CL, кацкель, рефал

Читай про http://en.wikipedia.org/wiki/Rewriting#Term_rewriting_systems

Смотри на http://www.cs.indiana.edu/~dyb/pubs/nano-jfp.pdf

КАК их можно решать

Как? Ну, например, переписать AST в виде плоской последовательности уравнений (утверждений Пролога), и задавать относительно этой базы данных вопросы на Прологе.

В некоторых простых случаях Пролог можно кастрировать до Datalog-а, и тогда реализация будет очень эффективной: http://people.csail.mit.edu/mcarbin/papers/aplas05.pdf

С разморозкой!

Насчёт C++: http://www.linux.org.ru/forum/development/9525806, ссылка на статью.

В плохих языках такая функциональность есть сразу, из коробки. В хороших языках она реализуется средствами самого языка. Пример такой реализации: http://llvm.org/docs/doxygen/html/namespacellvm_1_1PatternMatch.html

Толстовато же, нет?

C++ не силен в метапрограммировании. Все-таки возможности по рефлексии у языка C++ откровенно слабые. Что и видно по реализации наколенной «Mach7». Особенно забавная ситуация выходит при попытке интеграции с другим ЯП (как красиво присобачить скриптовый язык в game-движок?).

C++ не силен в метапрограммировании. Все-таки возможности по рефлексии у языка C++ откровенно слабые.

С этим согласен. Обычно pattern-matching реализуется как языковая фича, а не в виде библиотеки (единственное исключение, которое я знаю, — это Racket/Scheme/CL, ну на то он и лисп).

А библиотека эта на самом деле реализует не pattern-matching (полноценный), а всего-лишь «switch по типам», причём шаблонные типы она, судя по всему, не поддерживает. Это значит, что ни вложенных паттернов, ни сопоставления с параметризованными типами (e.g., Option/Maybe) она не поддерживает.

единственное исключение, которое я знаю, — это Racket/Scheme/CL

Forth, Tcl, ...

Ok.

Ты не понял сути

Чего именно я не понял?

Зачем pattern matching в языке, когда его можно в библиотеку добавить? Даже в таком убожестве, как Racket, это возможно, а в C++ и вовсе делается элементарно.

Чем плох приведенный пример pattern matching?

Все-таки возможности по рефлексии у языка C++ откровенно слабые

Очень забавное заявление. Рефлексия подразумевает динамику, что очень медленно по сравнению с классами в C++. Разные профи пишут, что dynamic_cast следует всячески избегать, а вы рефлексию хотите... Но ведь никто же вам руки не связывает, запилите себе динамические классы с рефлексией поверх классов в C++, делов то. Динамическое ООП на прототипах пишется за вечер. Да это будет тормозить как питон, а вы чего ждете, волшебной рефлексии без оверхеда?

Чем плох приведенный пример pattern matching?

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

Рефлексия подразумевает динамику

Рефлексия подразумевает дескрипторы типов. И всё.

вы чего ждете, волшебной рефлексии без оверхеда?

Да хотя бы как в Яве.

Делать можно всё, что можно делать с деревьями, не?

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

Этот подход работает с любыми тагированными структурами. Во всяких ML-ях тоже tagged unions.

Рефлексия подразумевает динамику,

Чушь.

а вы чего ждете, волшебной рефлексии без оверхеда?

Мало же ты знаешь про рефлексию.

Рефлексия подразумевает дескрипторы типов. И всё.

Дык, typeid в крестах есть.

Да хотя бы как в Яве.

А что на яве? getClass и компания? Честно говоря не в курсе, как там оно тормозит, но думаю, что поиск по имени, да ещё с учетом наследования, не самая быстрая операция. На сколько медленнее получается вызов метода с поиском через рефлексию, по сравнению с прямым вызовом? Думаю что раз так в 50. Т.е. со скоростью питона и других динамических языков.

Этот подход работает с любыми тагированными структурами.

Во всяких ML-ях тоже tagged unions.

Заявления уровня «у нас Тьюринг-полный язык, и мы можем реализовать любой алгоритм».

Рефлексия подразумевает дескрипторы типов. И всё.

Дык, typeid в крестах есть.

Это можно назвать идентификатором, но не дескриптором. Полезной информации в нем практически нет. Само близкое к дескрипторам типа в Си/Си++ - DWARF-информация, но до нее трудно добраться.

getClass и компания? Честно говоря не в курсе, как там оно тормозит, но думаю, что поиск по имени, да ещё с учетом наследования, не самая быстрая операция.

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

Заявления уровня «у нас Тьюринг-полный язык, и мы можем реализовать любой алгоритм».

Не тупи. Это вполне конкретная реализация pattern matching, работающая с любыми структурами, для которых возможно определение типа в рантайме (то есть, с тупым tag-ом или rtti). Чем она хуже ML?

Не тупи.

Не умничай.

Это вполне конкретная реализация pattern matching

Такую «конкретную реализацию» можно написать на любом языке, следовательно, в любом языке есть pattern matching. На этом дискуссию можно заканчивать за ее бессмысленностью.

Такое впечатление

Т.е. я прав на счет «в 50 раз медленнее»?

что ты собираешься в критичном цикле вызывать методы через рефлексию.

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

Т.е. я прав на счет «в 50 раз медленнее»?

Но в любом случае, рефлексия - это медленная штука,

Возможно, я не мерял. Но для задач, в которых важна рефлексия, скорость обычно не играет роли.

и лично мне понятно, почему в крестах её нет из коробки.

Если ты думаешь, что ее нет из-за скорости, ты сильно ошибаешься.

следовательно, в любом языке есть pattern matching

А я о чем? Мой поинт в том и заключается, что гнило включать такую функциональность в язык, потому как она элементарно делается средствами любого языка.

в любом случае, рефлексия - это медленная штука

Зачем лжешь? Оверхед на compile time рефлексию ровно ноль.

А я о чем?

О том, что приведенный пример pattern matching не хуже того, что встроен в язык.

Оверхед на compile time рефлексию ровно ноль.

Про compile time тут и бубен не звенел, только это не называется рефлексией.

Но для задач, в которых важна рефлексия, скорость обычно не играет роли.

Ну и что тогда мешает взять, да и унаследоваться от QObject? Это если самому сделать лень.

Если ты думаешь, что ее нет из-за скорости, ты сильно ошибаешься.

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

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

Про compile time тут и бубен не звенел, только это не называется рефлексией.

Тебе уже намекнули, что ты некомпетентен, а ты не понял. Зря.

Ну так чем же он «хуже»?