Язык(среду/код) можно представить в виде направленного графа, узлы которого это набор определённых термов(единиц языка) который использует программист для написания программы и/или новых термов. Наверху графа находятся самые сложные термы состоящие из множества других, внизу примитивные(например операторы и т.п. целевой платформы). Дуги графа это ссылки указывающие на используемые термы.
(Так можно представить практически любой язык, в Си например узлами будут функции/структуры и операторы/примитивные типы(нижний уровень).)
Каждый терм в мета языке фактически представляет собой правило описывающие конструкцию(из термов на которые ссылается данный) на которую будет заменён терм после "вызова". Компилирование мета кода это преобразование всех термов в примитивные.
Например программист написал код:
a1 b2 b4 с3 d2 c2
Правила для использованных не примитивных термов:
a1 => b2 b1
b2 => c1
b4 => c4 d3
с3 => d2 d3
c2 => d2 d1
b1 => c1
c1 => d1
c4 => d3
В результате получится:
d1 d1 d1 d3 d3 d2 d3 d2 d2 d1
Представление компилирования в виде графа:
Абстрактно можно представить что граф, во время компиляции, как бы "разрастается" сверху вниз.
Скажите я правильно понял концепцию?
Спасибо.
Между тем,что я думаю,тем,что я хочу сказать,тем,что я,как мне кажется,говорю,и тем,что вы хотите услышать,тем,что как вам кажется,вы слышите,тем,что вы понимаете,стоит десять вариантов возникновения непонимания.Но всё-таки давайте попробуем...(Э.Уэллс)
Здравствуйте, hardcase, Вы писали: H>О какой концепции речь?
О совмещении функционального и метапрограммирования.
Между тем,что я думаю,тем,что я хочу сказать,тем,что я,как мне кажется,говорю,и тем,что вы хотите услышать,тем,что как вам кажется,вы слышите,тем,что вы понимаете,стоит десять вариантов возникновения непонимания.Но всё-таки давайте попробуем...(Э.Уэллс)
но такие преобразования не умеют напрямую(то, что через ad-hoc полиморфизм описывается одним правилом, при таком описании может потребовать увеличение кол-ва уже имещихся правил в k-раз) описывать ad-hoc полиморфизм (оно же контекстно-зависимые термы)
Здравствуйте, AlexCab, Вы писали:
H>>О какой концепции речь? AC>О совмещении функционального и метапрограммирования.
Ничего не понял, как вы собираетесь совмещать и зачем так абстрактно? Все же гораздо интереснее говорить о конкретных вещах, встречающихся в реальном программировании, а не об абстрактных "a1", "b2" etc.
Могу сказать, что метапрограммирование проще всего воспринимать так. Есть несколько этапов компиляции. На первом этапе программа из исходного текста превращается в список токенов (лексический анализ), на втором — в синтаксическое дерево (AST). Это дерево ближе всего к тому, как программист представляет программу. Если у вас есть класс, в нем метод, в методе блок (например if), в блоке аргумент условия, то это и есть дерево, где корень — сама программа, дальше — пространства имен, классы, функции, блоки, выражения, части выражений и в конце концов листья дерева — переменные, константы.
Можно предположить, что на разных этапах с представлением программы можно что-то делать Некие "действия, определенные пользователем". Так, препроцессор Си обрабатывает программу как последовательность токенов, а более продвинутые системы метапрограммирования — на этапе AST. Соответственно, метапрограммирование — это написание кода, реализующего эти действия.
В простейшем случае такими действиями будет просто подстановка фрагмента представления программы вместо некоторого аргумента. Например, в некоторой системе метапрограммирования есть "шаблоны" — по сути специальные параметризированные заготовки кода.
В С++ система шаблонов построена чисто на подстановках, потому она такая монструозная. Если придумать другую систему метапрограммирования, в которой кроме подстановок будут разрешены другие — "активные" действия, определенные пользователем — то получим полноценные "плагины к компилятору", пользовательский код, который будет выполняться прямо внутри компилятора на различных этапах компиляции.
Ну а этот код может быть написан в любой парадигме — на ассемблере, в процедурном стиле, в фуникцональном или объектно-ориентированном, или на смеси всех стилей вместе взятых, или еще каким-то образом, неизвестным науке. Это вопрос того, какой интерфейс предоставляет компилятор для доступа к самому себе. Это может быть какой-нибудь скриптовый язык типа javascript, или тот же самый язык, на котором написана основная программа — не важно, главное что если такая возможность есть, то парадигма метапрограммирования реализована полностью.
Здравствуйте, DarkGray, Вы писали:
AC>>Скажите я правильно понял концепцию? DG>в первом приближении — да.
DG>но такие преобразования не умеют напрямую(то, что через ad-hoc полиморфизм описывается одним правилом, при таком описании может потребовать увеличение кол-ва уже имещихся правил в k-раз) описывать ad-hoc полиморфизм (оно же контекстно-зависимые термы)
Расскажите что такое ad-hoc полиморфизм (и в чем разница с параметрическим) и контекстно-зависимые термы? На википедии скомканная пара абзацев, да к тому же про haskell которого я не знаю
Здравствуйте, AlexCab, Вы писали:
AC>Язык(среду/код) можно представить в виде направленного графа, узлы которого это набор определённых термов(единиц языка) который использует программист для написания программы и/или новых термов. Наверху графа находятся самые сложные термы состоящие из множества других, внизу примитивные(например операторы и т.п. целевой платформы). Дуги графа это ссылки указывающие на используемые термы. AC> AC>(Так можно представить практически любой язык, в Си например узлами будут функции/структуры и операторы/примитивные типы(нижний уровень).)
Представить можно в виде графа, в виде сети петри, в виде пятерки.. Дело ж не в том.. Ради чего такое представление и какие выводы из этого можно сделать.. Т.е. какой смысл в таком представлении. Что это нам дает?
XC> Ничего не понял, как вы собираетесь совмещать и зачем так абстрактно?
формулировка, используемая AlexCab ближе к декларативному описанию, потому что она фокусируется на том, что происходит, что изменяется.
формулировка, используемая тобой ближе к императивному описанию, потому что она фокусируется на том, как это делается, а не что при этом происходит.
желательно в голове иметь оба представление: как это делается, и что при этом происходит. Формулировка AlexCab чуть более ценная, потому что меньшее кол-во людей умеет её формулировать и оперировать ей.
XC>Могу сказать, что метапрограммирование проще всего воспринимать так.
тогда проще сказать, что метапрограммирование — это функция, которая берет на входе код и выдает на выходе другое код F:код -> код.
вид представления кода: текст, бинарник, ast и т.д. — это уже больше задача удобства.
XC> Расскажите что такое ad-hoc полиморфизм (и в чем разница с параметрическим) и контекстно-зависимые термы?
ad-hoc полиморфизм — чаще всего реализуется через перегрузку функций. и отличается от параметрического полиморфизма тем, что для разных типов используется разный код.
вот это параметрический полиморфизм (Add определен через + с помощью одного варианта кода)
T Add<T>(T x1, T x2)
{
return x1 + x2;
}
а вот это ad-hoc полиморфизм (Add определен разными способами в зависимости от типа)
int Add(int x1, int x2)
{
return x1 + x2;
}
int[] Add(int[] x1, int[] x2)
{
return x1.Concat(x2).ToArray();
}
контекстно-зависимые термы:
var x = 5;
int var = 1;
в первом случае, var преобразуется в объявление переменной, во втором в название переменной.
Console.WriteLine(x * 3);
var x = 5;
Console.WriteLine(x * 3);
первая строка "Console.WriteLine(x * 3)" преобразуется в ошибку компиляции, что переменная x не используется,
ровно такая же третья строка преобразуется в несколько инструкций byte-кода
B> Т.е. какой смысл в таком представлении. Что это нам дает?
если преобразование удалось представить в виде приведенного графа, то это дает возможность построить автомат, который будет транслировать код линейно за O(длина исходного кода) (или если есть ограничения по памяти, то почти линейно O(длина исходного кода * log длина исходного кода))
если такой граф построить не удалось, то стоимость транслирующего алгоритма будет выше линейной (и скорее всего выше, чем O(nlogn)).
Если бы компилилось на С#, было бы типичным образчиком ad-hoc полиморфизма. Здесь фактически задается имя Add для оператора сложения, который полиморфен именно в ad-hoc смысле, т.к. невозможно складывать значения обобщенным образом, не имея специальной информации о типе. Класть их в кортеж — можно. Складывать — увы. Об этом тебе должен был сказать компилятор.
S>Если бы компилилось на С#, было бы типичным образчиком ad-hoc полиморфизма. Здесь фактически задается имя Add для оператора сложения, который полиморфен именно в ad-hoc смысле, т.к. невозможно складывать значения обобщенным образом, не имея специальной информации о типе. Класть их в кортеж — можно. Складывать — увы. Об этом тебе должен был сказать компилятор.
Ну то есть параметрический полиморфизм — это когда нам действительно пофиг, что там за типы — как на этапе компиляции, так и на этапе выполнения. Например, вызываем метод базового типа, который никак не переопределен в дочерних типах.
А ad-hoc — когда на этапе компиляции нам пофиг, а на этапе выполнения — уже нет. Например — вызываем метод, который переопределен в каждом дочернем типе как-то по своему.
Я прав?
S>Если бы компилилось на С#, было бы типичным образчиком ad-hoc полиморфизма. Здесь фактически задается имя Add для оператора сложения, который полиморфен именно в ad-hoc смысле, т.к. невозможно складывать значения обобщенным образом, не имея специальной информации о типе. Класть их в кортеж — можно. Складывать — увы. Об этом тебе должен был сказать компилятор.
про C# говорить сложно, потому что он не умеет использовать ad-hoc полиморфизм из параметрического полиморфизма
в следующем коде: Sum — параметрический полиморфизм, Add — ad-hoc полиморфизм, Add2 — можно трактовать и так, и так, в зависимости от того как делается деление по входу или по выходу.
template<typename T>
T Sum(typename std::vector<T>::iterator begin, typename std::vector<T>::iterator end)
{
T t;
for (typename std::vector<T>::const_iterator it = begin; it != end; ++it)
{
Add2(t, *it);
}
return t;
};
template<typename T>
void Add2(T& x, T value)
{
x = Add(x, value);
}
bool Add(int x, int value)
{
return x + value;
}
bool Add(bool x, bool value)
{
return x || value;
}
S> т.к. невозможно складывать значения обобщенным образом, не имея специальной информации о типе. Класть их в кортеж — можно.
по такому определению даже вектор не является параметрическим полиморфизмом, потому что при хранении типа в векторе требуется специальная информация от типа, как именно данный тип копируется, и соответственно компилятор должен был бы сказать "бла-бла, то что ты там утверждаешь".
Здравствуйте, x-code, Вы писали:
XC>Здравствуйте, samius, Вы писали:
DG>>>вот это параметрический полиморфизм (Add определен через + с помощью одного варианта кода) DG>>>
S>>Если бы компилилось на С#, было бы типичным образчиком ad-hoc полиморфизма. Здесь фактически задается имя Add для оператора сложения, который полиморфен именно в ad-hoc смысле, т.к. невозможно складывать значения обобщенным образом, не имея специальной информации о типе. Класть их в кортеж — можно. Складывать — увы. Об этом тебе должен был сказать компилятор.
XC>Ну то есть параметрический полиморфизм — это когда нам действительно пофиг, что там за типы — как на этапе компиляции, так и на этапе выполнения. Например, вызываем метод базового типа, который никак не переопределен в дочерних типах.
Время компиляции/выполнения не имеет значения. Параметрический полиморфизм не требует специальных знаний о типе и позволяет писать код, который будет работать для всех типов. Как правило это обобщенные контейнеры (но не требующие сравнения, hashcode и т.п.), кортежи, в том числе старые необобщенные контейнеры типа ArrayList, методы по работе с ними. И вообще все, что можно сделать для заранее неизвестного типа.
XC>А ad-hoc — когда на этапе компиляции нам пофиг, а на этапе выполнения — уже нет. Например — вызываем метод, который переопределен в каждом дочернем типе как-то по своему. XC>Я прав?
Ad-hoc — это все, что связано со специальными знаниями о типе. Прежде всего — операторы, которые определены для множества типов. Например, складывать можем целые, плавающие, строки. Для каждого случая ищется специальный способ сложения. Вывод в консоль значения требует специального знания о том, как это значение преобразовать в строку. Перегрузка (overload) методов, операторов — типичный пример ad-hoc полиморфизма.
Отдельной категорией идет subtype полиморфизм. Прежде всего он родственен с параметрическим, потому как позволяет вызывать код единым образом для всех подтипов (но не позволяет для неродственных типов). Отдельный смысл у subtype полиморфизма в ООП программировании подразумевается в возможности переопределять (override) методы для подтипов. Это роднит его с ad-hoc полиморфизмом, т.к. позволяет указывать специальные методы для отдельных ветвей подтипов.
В жизни это все здорово перемешивается. Например, Dictionary<K,V> — вроде как пример параметрически полиморфного контейнера. Пока мы параметризуем его создание специальным объектом, который учит контейнер считать хэшкод и сравнивать элементы, — все впорядке. Однако, сам компарер — образец subtype полиморфизма. Если мы его не подадим, будет подан EqualityComparer<K>.Default, который зная о типе K может подсунуть специальный компарер для K. Это уже ad-hoc (причем времени выполнения, а не компиляции).
Здравствуйте, DarkGray, Вы писали:
B>> Т.е. какой смысл в таком представлении. Что это нам дает?
DG>если преобразование удалось представить в виде приведенного графа, то это дает возможность построить автомат, который будет транслировать код линейно за O(длина исходного кода) (или если есть ограничения по памяти, то почти линейно O(длина исходного кода * log длина исходного кода)) DG>если такой граф построить не удалось, то стоимость транслирующего алгоритма будет выше линейной (и скорее всего выше, чем O(nlogn)).
Во первых какой такой "приведенный граф"? .
Во-вторых речь шла цитирую "Язык(среду/код) можно представить в виде направленного графа, узлы которого это набор определённых термов(единиц языка) который использует программист для написания программы и/или новых термов. Наверху графа находятся самые сложные термы состоящие из множества других, внизу примитивные(например операторы и т.п. целевой платформы). Дуги графа это ссылки указывающие на используемые термы". Вам не кажется что "представить преобразование" и "представить язык" это разные вещи?
В-третьих, совсем не очевидно если можно представить (и что представить язык или преобразования) в (я так и не понял какие такие особые свойства у данного графа) таком виде то компиляция будет линейна.
В-четвертых, я не усмотрел там рекурсии. И в языке и в преобразовании она обычно присутствует. Собственно, это именна та фишка которая позволяет генерировать довольно мощные языки из грамматики. Без рекурсивности в определения грамматик нам пришлось бы сложновато. Отсюда следует любопытная штука.. Что преобразование выглядит вроде простым, а реально там будет рекурсия в разборе.. а вместе с рекурсией возникает не линейность в разборе.. не со всякой рекурсией, конечно, но в общем случае возникает..
И в пятых. Язык сам по себе являющимся линейным.. в том смысле, что там одна буква следует за другой, может иметь иерархическое содержание которое влечет за собой рекурсию. Классический пример: "У попа была собака он ее любил, потом убил и закопал и надпись написал "у попа бывла собака он ее любил...". Или вызов рекурсивной функции..
И... хотя этого достаточно.. не хочется сюда вопросы философии лепить..
S>>Если бы компилилось на С#, было бы типичным образчиком ad-hoc полиморфизма. Здесь фактически задается имя Add для оператора сложения, который полиморфен именно в ad-hoc смысле, т.к. невозможно складывать значения обобщенным образом, не имея специальной информации о типе. Класть их в кортеж — можно. Складывать — увы. Об этом тебе должен был сказать компилятор.
DG>про C# говорить сложно, потому что он не умеет использовать ad-hoc полиморфизм из параметрического полиморфизма
Вот пример EqualityComparer<T>.Default
DG>в следующем коде: Sum — параметрический полиморфизм, Add — ad-hoc полиморфизм, Add2 — можно трактовать и так, и так, в зависимости от того как делается деление по входу или по выходу. DG>
Не соглашусь. Методы Sum и Add2 не могут работать для любого типа без специального кода.
S>> т.к. невозможно складывать значения обобщенным образом, не имея специальной информации о типе. Класть их в кортеж — можно.
DG>по такому определению даже вектор не является параметрическим полиморфизмом, потому что при хранении типа в векторе требуется специальная информация от типа, как именно данный тип копируется, и соответственно компилятор должен был бы сказать "бла-бла, то что ты там утверждаешь".
Как бы эта информация берется из типа элемента, потому сам вектор ни в каких дописываниях для элементов некоторого типа не нуждается. Можем смело считать вектор образцом параметрического полиморфизма, задвинув под ковер его специализацию для bool-ов.
B>В-четвертых, я не усмотрел там рекурсии. И в языке и в преобразовании она обычно присутствует.
в большинстве случаев от рекурсии лучше переходить к итерированию по дереву.
для такого итерирования достаточно тривиально доказывается конечность алгоритма, в отличии от рекурсии.
Здравствуйте, DarkGray, Вы писали:
S>>Как бы эта информация берется из типа элемента, потому сам вектор ни в каких дописываниях для элементов некоторого типа не нуждается.
DG>ню-ню DG>расскажи, пожалуйста, с каких пор ссылка на тип перестала быть типом? и с каких пор можно определить вектор для типа int& (std::vector<int&>)?
Хорошо, не будем считать вектор образцом параметрического полиморфизма. Но вместе с ним и List<T>, И Tuple<T> и т.п.
S>Хорошо, не будем считать вектор образцом параметрического полиморфизма. Но вместе с ним и List<T>, И Tuple<T> и т.п.
поэтому я и утверждаю, что твоя трактовка параметрического полиморфизма мало используемая, и не несет никакой полезной информации для практического использования.
