[не ради срача] знатокам C# или Java

> > То есть, заменяем такой пример с рантаймом на рефлексию + использование компилятора через рефлексию + система типов.

Чего?

это уже про «Five compilations models» вольный пересказ пошёл.

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

Из императивной т.з.: ну, как сделать рефлексию CTFE на C++ шаблонах — понятно. Как сделать систему типов через рефлексию CTFE + семантику системы типов — тоже понятно. В чём проблема? (компилятор дёргать выборочно, но тут можно и boost::spirit заюзать). Хотя и тормозить это будет...

А логику C#-ного кода - понял?

ага.

Ну дык она такая же. Код-то почти текстуально совпадает.

я про хак вроде такого:

Я знаю, о чём речь. Я не понял, какое отношение это имеет к данной ситуации.

имеем: код, который должен компилироваться корректно, если длины векторов совпадают, или не компилироваться, если не совпадают.

Нет. Он должен не компилироваться, если нет статической гарантии, что длины векторов совпадают. Заранее эти длины неизвестны.

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

А так, из общих соображений: раз язык шаблонов тьюринг-полный, и эквивалентен лямбда-исчислению, введем типизированное лямбда-исчисление и поверх него Хиндли-Милнера с выводом типов.

Угу, угу. Вы ещё полёт на луну на шаблонах запрограммируйте.

Не нужно «раскрывать шаблон неизвестное заранее число раз». Нужно раскрыть его конечное число раз в код, вычисление которого неизвестное во время компиляции кол-во раз приводит к нужному результату. «Вычисление неизвестное число раз», но известной функции!

То есть, проблема в том, что можно (на примере факториала) раскрыть fac<C>, С= целая константа, но нельзя раскрыть fac<i> , int i ?

Это не проблема. На примере факториала:
1. Допустим, мы можем ограничить значение i разумным максимальным M, например, M=10. Тогда:
а) инстанцируем шаблон fac<M>, вычисление которого приведёт к заполнению какой-либо lookup-table, то есть, сгенерируется код вида LUT[1]=1; LUT[2]=2; LUT[3]=6;... LUT[10]=...
б) для случая переменной i<M, fac(i) можно вычислить за O(1) через LUT[i]
в) для случая переменной i>=M, fac(i)=fac( int(i/M)*M+ i%M) = fac(a+b), причём b<M
fac(a+b)=fac(a+b-1+1)=(a+b-1)*fac(a+b-1) по определению fac(a);
раскрываем далее это (a+b-1), пока оно не станет <=M.
Получим запись вида П(a+b-j)*fac(a+b-k), j=1..k, k<M. Причём a+b-k=M.
То есть, fac(a+b-k)=fac(M)=LUT[10].
Итого, свели вычисление переменной при раскрутке шаблона (что не можем сделать) к произведению неизвестного числа множителей и значения из таблицы.

Для факториала эти k, a,b можно прям вычислить (i-k=M,i-M=k) и подставить в формулу П(i-j)LUT[10] ; j=1..i-M

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

Раскрытие шаблона сгенерирует функцию, вычисление которой в рантайме и даст нужное значение. При этом будут использоваться значения из вычисленной LUT[M], которую мы тоже сгенерируем.

> Он должен не компилироваться, если нет статической гарантии, что длины векторов совпадают. Заранее эти длины неизвестны.

гуглим, к примеру «How Java's Floating-Point Hurts Everyone Everywhere» http://www.eecs.berkeley.edu/~wkahan/JAVAhurt.pdf и видим такую нотацию для скалярного произведения, через матрицы:

Matrix Notation for 3-Dimensional Euclidean Geometry
Lines, Planes and Cross–Products:
Let bold-faced lower-case letters p, q, r, ..., x, y, z stand for real 3-dimensional column-vectors.
Then row vector pT = [p1, p2, p3] is the transpose of column vector p , and pT·q is the scalar
product p•q of row pT and column q . Euclidean length ||p|| = √(pT·p) .
Do not confuse the scalar pT·q = qT·p with the 3–by–3 matrices (“dyads”) p·qT ≠ q·pT nor with
the vector cross-product p×q = –q×p .


Из такой нотации большинство «статических гарантий» само образуется.

>Он должен не компилироваться, если нет статической гарантии, что длины векторов совпадают. Заранее эти длины неизвестны.

Если бы знать длины векторов при компиляции, так никаких проблем бы не было.

«код должен не компилироваться» = «компилируется с прагмой #error»

dot a b:

dot a [] = 0
dot [] b = 0
dot (head_a:tail_a) (head_b:tail_b) = head_a*head_b + dot tail_a tail_b

dot0 a b n = dot a b, если длины a и b равны (между собой и равны n)
= error, если длины не равны


dot0 a b n = mac0 ( x y l) где l=длина x - длина y, x — самый длинный из (a,b), y - оставшийся

в итоге остаётся mac0 x y 0 = dot a b, если длины равны
или mac0 x y l, если не равны


То есть: раскрываем шаблон в вычисление разницы длин и скалярного произведения, и в ранайме делаем диспетчеризацию, l=0 — cчитаем произведение, l!=0 -> ругаемся с ошибкой. Код, который вычисляет и диспетчеризирует — сгенерирован.

Он должен не компилироваться, если нет статической гарантии, что длины векторов совпадают. Заранее эти длины неизвестны.

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

Если первое, тогда никак. Если второе, то можно сгенерировать код, уже удовлетворяющий ограничениям. А если не удовлетворяет — сгенерированный код вычисляется в NaN/выбрасывает исключение/обрабатывается ошибка в рантайме .

То есть, вопрос сводится к «как с заданными _main(n--,i++,a,b) гарантировать, что длины a и b одинаковы??? По определению, по построению a и b.

Надо бы как-то доказать, что такое _main не может раскрыться в error, да.
n-1 + i +1 = n+i = const. Доказано.

Можно предложить вариант: вводим n, пишем в файл const int n=...; #include „старая_программа“.cpp , натравливаем препроцессор и ловим ошибки. Первая программа генерирует исходник второй, во второй раскрываются шаблоны с конкретным n.

> Я не понял, какое отношение это имеет к данной ситуации.

Да такое же точно. Логика работы факториала шаблонами: В хвосте рекурсии возвращаем 1 из шаблона, в теле рекурсии — n* раскрытие след. шаблона.

Логика работы «компилятора» с проверкой на ошибки: в хвосте рекурсии, если ошибка, возвращаем 1 (длины разные), затем в охватывающем шаблоне из-за этой 1 возвращаем error и вываливаемся с ошибкой при раскрытии шаблона; если ошибки нет, возвращаем 0, затем возвращаемся в охватывающий и раскрываем шаблоны дальше.

ну, рейтрейсер на шаблонах C++ же написали: http://ompf.org/forum/viewtopic.php?f=8&t=1556&start=0&sid=adc9e6aab662360007... http://gitorious.org/metatrace http://savannah.nongnu.org/projects/metatrace http://git.savannah.gnu.org/cgit/metatrace.git/tree/ http://git.savannah.gnu.org/cgit/metatrace.git/tree/src/main.cc http://git.savannah.gnu.org/cgit/metatrace.git/tree/src/vector.hh

на шаблонах D, кстати, симпатичнее выглядит: http://h3.team0xf.com/ctrace/ . А то тут этот render.sh шороху наводит, «закат солнца вручную».

а почему симпатичнее: потому что в шаблонах D есть static if, который выполняется при раскрытии шаблона и в рантайме, и из-за отсутсвия которого приходится так извращаться

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

> и в ранайме делаем диспетчеризацию, l=0 — cчитаем произведение, l!=0 -> ругаемся с ошибкой

конечно, ради чего эта вся кодогенерация делается — диспетчеризация должна быть CTFE, во время компиляции и раскрытия шаблона. В D повезло с шаблонами, есть удобный static if. В C++ в общем случае будет раскрытие в рантайм, но для твоего конкретного примера где N=n с клавиатуры, потом в _main(n--, i++,a,b) нужно поставить шаблонами утверждения, что длина a = n-1, длина b=i+1. Потом накрутить вычисления по этим длинам, |a|-|b|=n-1-(i+1)=n-i . Ага, опаньки. С метрикой надо подумать.

кстати, интересный вопрос. Можно ли родить паттерн flyweight (приспособленец) шаблонами , эквивалентный твоей функциональной структуре, чтобы чего-то там автоматически рассуждать о свойствах алгоритма, раз знаем свойства паттерна?

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

Блин, вот что за стремление подменить мою задачу своей?

Допустим, мы можем ограничить значение i разумным максимальным M, например, M=10.

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

гуглим, к примеру «How Java's

Если кто не заметил, на жабе решение было. Моё же.

dot a [] = 0
dot [] b = 0
dot (head_a:tail_a) (head_b:tail_b) = head_a*head_b + dot tail_a tail_b

Шо за лэнгвич?

а длины вводятся с клавиатуры?

Равные длины векторов

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

Чего-чего?

вводим n, пишем в файл const int n=...; #include «старая_программа».cpp , натравливаем препроцессор и ловим ошибки. Первая программа генерирует исходник второй, во второй раскрываются шаблоны с конкретным n.

Накуя тогда шаблоны?

Я не понял, какое отношение это имеет к данной ситуации.

Да такое же точно.

Такое же точно как что?

Ещё раз: я знаю, что шаблоны умеют делать вычисления во время компиляции. Мне нужно не это.

Ничего не поделаешь, это плюсы и тупой компилятор

Ну, наконец-то.

Или так:

Он должен не компилироваться, если нет статической гарантии, что длины векторов совпадают. Заранее эти длины неизвестны.

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

Конкретные значения длин векторов (и тот факт, известны ли они в compile time или в runtime) нам не нужны. В терминах контрактного программирования, нужны инварианты «длины перемножаемых векторов совпадают»

Нам нужно обнести врапперами те места, где в C# происходит раскрытие шаблона несколько раз,
и налепить инвариантов на эти врапперы. Будет несколько вложенных друг в друга областей, начало области — раскрытие очередного шаблона в C# версии, конец — скалярное произведение.
Получается дерево, лист = скалярное произведение, узел=раскрытие _main(n--,i++,a,b), корень=раскрытие _main(n,0,a,b)

В самом листе дерева врапперов будет инвариант для скалярного произведения
(длины векторов равны). Из этого листа в корень дерева врапперов инвариант должен выполняться тоже везде.
На корне и на узлах инварианты выполняются (не зависимо от N, количество раскрытий Cons<A> равно количеству раскрытий Cons<B>) ==> значит, корень статически корректен с точки зрения типов. Nil<A>,Nil<B> не изменяют инвариант => значит, инвариант выполняется везде от корня до листа.

Независимо от N гарантируем выполнение инвариантов — от листа до корня,
от dot_product до _main(n,0,a,b).

Это идея, контракт-инвариант шаблонами, теперь про реализации:

1. boost: обмазавшись несвежим бустом, можно использовать type_traits или function_traits. Врапперы станут шаблоном класса или функции, инвариант — BOOST_STATIC_ASSERT на traits.


2. crazy1: см. реализацию машины Тьюринга со stackoverflow.com: #15 http://stackoverflow.com/questions/189172/c-templates-turing-complete/275295#...

Здесь нас интересуют 4 момента: Conditional, EnableIf, static_cast в instance Conditional (см.
   http://en.wikipedia.org/wiki/Curiously_Recurring_Template_Pattern
   http://en.wikipedia.org/wiki/Barton-Nackman_trick
   )
   
и собсно, static_assert по инвариантам.

а) когда я писал про вариант http://www.linux.org.ru/jump-message.jsp?msgid=4902040&cid=4912132 http://www.linux.org.ru/jump-message.jsp?msgid=4902040&cid=4912169 , имелось ввиду следущее: исчисление предикатов эквивалентно машине Тьюринга, обычным алгоритмам. Делаем такое «исчисление предикатов», где предикатом является l в mac0 x y l , то есть условие на корректность длин векторов. Затем реализуем собственно rule engine времени компиляции, на шаблонах, по этому предикату.
То есть, описанное выше в терминах инвариантов и контрактного программирования: предикат «инварианты выполняются» гарантирует корректность типов статически в compile time.

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

С врапперами это будет выглядеть окончательно мозголомно.   


3. crazy2:
http://matt.might.net/articles/c++-template-meta-programming-with-lambda-calc...
http://matt.might.net/articles/c++-template-meta-programming-with-lambda-calc...
лямбда-исчисление на шаблонах

Сделать типизированное лямбда-исчисление, и выводить зависимые типы.

4. Вариант на D кажется будет нагляднее из-за такой фичи: http://en.wikipedia.org/wiki/Generic_programming#Alias_parameters — она словно специально для этого предназначена. Впрочем, там и контракты есть.

5. Вариант «прагматичный» — взять тот же LLVM/Clang, и сделать что-то в духе literate programming: комментарий, начинающийся с //\\ + текст правила инварианта. Потом clang строит AST, наш парсер его парсит + правила, обходит AST и строит граф с инвариантами, и тут же проверяет на корректность.

То есть, а) генерировать такие врапперы автоматически б) облегчить синтаксис в) в конечном итоге может получиться точно такой же текст с шаблонами, автоматически сгенерированный.

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

Блин, вот что за стремление подменить мою задачу своей?

задача та же самая. Реализация разная.

Вот ты тупо перевёл построчно C# код в C++ и удивляешься, что шаблоны не работают. И не заработают — переводить надо по-разному.

Шаблоны в С++ работают так: нужно представлять сразу конечный результат, который должен получиться, то есть, в какой код раскрываются в конечном итоге и ограничения модели вычислений шаблонов. Тогда не будет непоняток вроде «а тут в плюсах квазицитирование отсутствует»

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

Правда, признаю : такая реализация не совсем корректная, код раскрывается в рантайм-код с ASSёRT-ами. Вариант с контрактами мне нравится больше.

> Ещё раз: я знаю, что шаблоны умеют делать вычисления во время компиляции. Мне нужно не это.

именно это и нужно. Нужен контракт-инвариант «длины векторов равны», который выполняется как предусловие и как постусловие для любой строчки от первого раскрытия шаблона, до той строчки, где происходит скалярное произведение. Как именно его реализовать на шаблонах — дело десятое: можно type_traits, можно СRTP и http://en.wikipedia.org/wiki/Barton-Nackman_trick , можно конечный автомат изобразить на шаблонах.

Суть в том, что твоё ограничение «длины не известны в compile time» или «шаблоны должны раскрываться заранее неизвестное число раз» — это несущественные особенности реализации на C#, которые надо переводить на C++ не «тупо в лоб», а подняться уровнем выше по абстракции, алгоритм и ограничения операций построенных типов => контрактное программирование и инварианты => вычисление логики предикатов во время компиляции, во время раскрытия шаблона.

> Допустим, нет.

тогда смотрим ветки i>=M, а не только i<M. Покрыты все случаи, то есть, любое i

я просто показал, как можно свести твою реализацию к эквивалентной, сгенерировавшей код, вычисление которого в рантайме с assert-ами совпадает с твоей реализацией. Да, мы так не узнаем статические свойства алгоритма, грубо говоря, не переберём все трассы.
Поэтому вариант с инвариантами лучше — он *доказывает* корректность статически.

> К тому же, подобное ограничение - ограничение используемого языка, а не задачи

в задаче вообще нет такого рода ограничений. Возьми, например функцию Аккермана вместо факториала или что-то ещё с большим множеством перебираемых значений — и такой трюк с look-up table уже не пройдёт.
Для твоего примера со скалярным произведением не нужно раскрывать шаблон неизвестное кол-во раз, исходя из требований задачи. Это уже особенности твоей частной реализации.
Так что пример не показателен, и раскрытие шаблонов как в С++ вполне подходит для задачи, если выбрать нужные концепции вроде инвариантов и статически вычисляемых предикатов.

Интересно всё-таки такой пример, где ограничение исходит от задачи.
Ну да, и наглядность решений разная. Я думаю, мало кто распарсит в голове решение на базе буста и type_traits

> надо переводить на C++ не «тупо в лоб», а подняться уровнем выше по абстракции, алгоритм и ограничения операций построенных типов => контрактное программирование и инварианты => вычисление логики предикатов во время компиляции, во время раскрытия шаблона.

конечно, сам этот алгоритм перехода надо бы запрограммировать. И показать на примере, что ограничения из-за зависимых типов порождают вот такие предикаты и вот такие инварианты контрактов. А чо, на LLVM + Clang это не очень сложно сделать. Кстати, в само LLVM шаблонами изображаются блоки кода, куски AST, и т. п.
Другое дело, что делать такое метапрограммирование в CTFE при раскрытии самой программы, а не отдельным макросредством вроде парсера + кодогенератора одной программы в другую — это уже явный перебор, вроде metatrace или K16 — вроде и работает, но отжирает при этом все ресурсы.

В терминах контрактного программирования, нужны инварианты «длины перемножаемых векторов совпадают»

Я так и выкрутился на Хаскеле.

Нам нужно обнести врапперами те места, где в C# происходит раскрытие шаблона несколько раз, и налепить инвариантов на эти врапперы.

????? Какие ещё в попу врапперы? На C# эта задача решена (почти так же, как и на Хаскеле), так как шарп умеет параметический полиморфизм. И какое, нафиг, раскрытие шаблона в шарпе? В нём нет шаблонов, в нём дженерики, они не раскрываются.

Получается дерево, лист = скалярное произведение, узел=раскрытие _main(n--,i++,a,b), корень=раскрытие _main(n,0,a,b)

Может, уже покажешь код?

Делаем такое «исчисление предикатов», где предикатом является l в mac0 x y l , то есть условие на корректность длин векторов. Затем реализуем собственно rule engine времени компиляции, на шаблонах, по этому предикату.

бла, бла, бла. Мне уже надоело лапшу с ушей снимать. По уму, ты должен был написать код пару дней назад.

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

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

Вот ты тупо перевёл построчно C# код в C++ и удивляешься, что шаблоны не работают. И не заработают — переводить надо по-разному.

Я не удивляюсь. Я знаю, что не заработают. И НИЧЕГО не заработает - в плюсах система типов слабенькая.

такая реализация не совсем корректная, код раскрывается в рантайм-код с ASSёRT-ами.

Это не «не совсем корректная», это просто некорректная.

Как именно его реализовать на шаблонах — дело десятое:

Нет, не десятое. Пойнт в том и состоит, что на шаблонах такие вещи НЕ реализуются.

надо ... подняться уровнем выше по абстракции

Опять бла-бла-бла. Код где?

Поэтому вариант с инвариантами лучше — он *доказывает* корректность статически.

Если бы он к тому же был приведён...

Возьми, например функцию Аккермана вместо факториала

У меня НЕТ факториала в задаче. Поэтому вместо чего я должен брать функцию Аккермана, я не понимаю.

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

Я пока не видел другой.

раскрытие шаблонов как в С++ вполне подходит для задачи

Нет, не подходит. Ибо все шаблоны раскрываются перед собственно компиляцией, а на чистом безшаблонном C++ такие вещи стопроцентно не делаются.

Интересно всё-таки такой пример, где ограничение исходит от задачи.

Интересен пример решения без подобных ограничений.

Я думаю, мало кто распарсит в голове решение на базе буста и type_traits

Учитывая, что его нет.