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

T>Ты, видимо, с алгебраическими типами не знаком?

В других системах оно называется "discriminated union" и обладает теми же характеристиками. В boost для С++ есть типобезопасная реализация unions, например.


T>А вот обработка EPlus наверху может быть специализирована (типы классов и тп). Но это не наша забота.

Дык я и высказывался относительно последующей обработки EPlus, и там, где в Хаскеле нужен будет паттерн-матчинг по реальному подтипу, в С++, например, возможен статический вариант "визитора", т.е. на этапе компиляции. Но опять же, это всё верно для "ручного" конструирования разборщиков, автоматически же можно заведомо нагенерить узлы для всех допустимых сочетаний операндов "+" заранее и обойтись вообще без диспетчеризации для поиска обработчиков (т.е. использовать соответствие 1:1). Ведь в конечном коде и так должна быть обработка всех допустимых вариантов, так зачем сначала сливать в бутылочное горлышко, а затем разливать из него? Вопрос не праздный, просматривая исходники я иногда замечаю, что народ увлекается паттерн матчингом и алгебраическими типами "на ровном месте", а разве для реализации абстракции "классификация" нет статических ср-в?


T>Вот функция: zip(i,j). Она берёт последовательность i3i2i1i0 и j3j2j1j0 и создаёт последовательность i3j3i2j2i1j1i0j0.

T>Возьмём индексы реального цикла i и j. Сдвинем их вправо на два разряда и пропустим через наш zip.

T>Мы получили индекс устройства (АП+ИУ), в котором будут выполняться 16 близко лежащих вычислений. Пересылки соседним вычислениям, что не поместились в наш индекс, будут иметь адресатом индекс АП+ИУ с небольшим расстоянием по манхеттенской метрике (max (abs (x-x') (abs (y-y'))). Половина всех пересылок будет проходить через всего один уровень иерархии (сортирующую псевдо-АП).

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

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

T>В комбинаторах я пишу максимально декларативно, единственное, за чем мне надо следить — отсутствие левой рекурсии. Списки разбираются many1 p = pure ( <*> p <*> many p в отличии от LR, где many1 p = pure (flip ( <*> many p <*> p (many p = many1 p <|> return []). Нужна контекстно-зависимая грамматика — будет. Не нужна — не будет.

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

T>>Ты, видимо, с алгебраическими типами не знаком?
V>В других системах оно называется "discriminated union" и обладает теми же характеристиками. В boost для С++ есть типобезопасная реализация unions, например.

Похожими. Не "теми же".

T>>А вот обработка EPlus наверху может быть специализирована (типы классов и тп). Но это не наша забота.
V>Дык я и высказывался относительно последующей обработки EPlus, и там, где в Хаскеле нужен будет паттерн-матчинг по реальному подтипу, в С++, например, возможен статический вариант "визитора", т.е. на этапе компиляции.

В Хаскеле, значит, не на этапе компиляции.

Ох. Ну, да ладно.

V>Но опять же, это всё верно для "ручного" конструирования разборщиков, автоматически же можно заведомо нагенерить узлы для всех допустимых сочетаний операндов "+" заранее и обойтись вообще без диспетчеризации для поиска обработчиков (т.е. использовать соответствие 1:1).

К разборщикам это имеет мало отношения. Семантика при их построении влияет только насколько она в них может быть выражена.

V>Ведь в конечном коде и так должна быть обработка всех допустимых вариантов, так зачем сначала сливать в бутылочное горлышко, а затем разливать из него? Вопрос не праздный, просматривая исходники я иногда замечаю, что народ увлекается паттерн матчингом и алгебраическими типами "на ровном месте", а разве для реализации абстракции "классификация" нет статических ср-в?

Сравнение с образцом, например.

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

Поэтому разбирай динамически. Что визитором, что сравнением с образцом.

T>>Мы получили индекс устройства (АП+ИУ), в котором будут выполняться 16 близко лежащих вычислений. Пересылки соседним вычислениям, что не поместились в наш индекс, будут иметь адресатом индекс АП+ИУ с небольшим расстоянием по манхеттенской метрике (max (abs (x-x') (abs (y-y'))). Половина всех пересылок будет проходить через всего один уровень иерархии (сортирующую псевдо-АП).
V>Это всё зависит от семантики i и j, при простой адресации матрицы так и есть, я упоминал о сложности поиска хорошей хеш ф-ии для общего случая, когда семантика не очевидна для компилятора.

Ты сперва простые случаи разбери.

В случае "неочевидности семантики" (что это означает, вообще? мы не смогли восстановить dataflow граф?) можно скатываться к последовательному коду.

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

T>К тебе приходит только что созданный объект, про структуру которого ты, в общем случае, не всё знаешь. Статически отклассифицировать его будет невозможно.
T>Поэтому разбирай динамически. Что визитором, что сравнением с образцом.

Вот здесь не понимаю логики. Что значит "приходит"? Из "ниоткуда", что-ли? Для рассматриваемого случая объект формируется парсером, т.е. на момент формирования точный тип объекта уже известен, а значит прямо в процессе формирования к нему можно привязать обработчик. Ты, похоже, не понял вопроса: зачем сливать в бутылочное горлышко, если потом надо будет разливать. Ключевая фраза: "зачем сливать"?

T>>К тебе приходит только что созданный объект, про структуру которого ты, в общем случае, не всё знаешь. Статически отклассифицировать его будет невозможно.
T>>Поэтому разбирай динамически. Что визитором, что сравнением с образцом.

V>Вот здесь не понимаю логики. Что значит "приходит"? Из "ниоткуда", что-ли? Для рассматриваемого случая объект формируется парсером, т.е. на момент формирования точный тип объекта уже известен, а значит прямо в процессе формирования к нему можно привязать обработчик. Ты, похоже, не понял вопроса: зачем сливать в бутылочное горлышко, если потом надо будет разливать. Ключевая фраза: "зачем сливать"?

Это можно fusion сделать. {-# RULES #-} в Хаскеле.

А может и компилятор догадаться.

Сливать надо потому, что так удобней писать код. Так лучше структурировать программу.

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


T>Сливать надо потому, что так удобней писать код. Так лучше структурировать программу.

Может надо использовать "правильные языки" (С)?
А то ты про алгебраические типы говорил, а в compile-time template<typename Left, typename Right> AstNode — такой же алгебраический тип с т.з. компилятора, не находишь? И того же уровня классификация из разряда "чтобы удобнее было" сохраняется.
Это я про то, что мы можем для нашего случая специализировать всего 1 метод этого класса для различных сочетаний и избежать диспечеризации в ран-тайм. А если использовать частичную специализацию, то можно описывать обработчики для целого класса за раз.

T>>Сливать надо потому, что так удобней писать код. Так лучше структурировать программу.
V>Может надо использовать "правильные языки" (С)?

Неужто C++, судя по typename? 8-O

V>А то ты про алгебраические типы говорил, а в compile-time template<typename Left, typename Right> AstNode — такой же алгебраический тип с т.з. компилятора, не находишь?

Нет, не нахожу.

V> И того же уровня классификация из разряда "чтобы удобнее было" сохраняется.

Нет, не сохраняется.

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

То же можно сделать с помощью rewrite rules, когда упрёмся в производительность.

Не надо выполнять преждевременной оптимизации.

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

V>>А то ты про алгебраические типы говорил, а в compile-time template<typename Left, typename Right> AstNode — такой же алгебраический тип с т.з. компилятора, не находишь?

T>Нет, не нахожу.

Поищи внимательней еще раз.
Хинт: в С++ порой значительная часть программы выполняется в compile-time при использовании шаблонов.


V>> И того же уровня классификация из разряда "чтобы удобнее было" сохраняется.

T>Нет, не сохраняется.

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


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

T>То же можно сделать с помощью rewrite rules, когда упрёмся в производительность.
T>Не надо выполнять преждевременной оптимизации.

Ха-ха, это для хаскеля такой финт — преждевременная оптимизация, а для шаблонов С++ — стандартное использование, которое экономит многие строки кода.

И вообще, не стоит бездумно разбрасываться шаблонными фразами, удешевляя смысл сокрытой в них мудрости.

V>>>А то ты про алгебраические типы говорил, а в compile-time template<typename Left, typename Right> AstNode — такой же алгебраический тип с т.з. компилятора, не находишь?
T>>Нет, не нахожу.
V>Поищи внимательней еще раз.
V>Хинт: в С++ порой значительная часть программы выполняется в compile-time при использовании шаблонов.

Что это означает?

V>>> И того же уровня классификация из разряда "чтобы удобнее было" сохраняется.
T>>Нет, не сохраняется.
V>Тогда поясни в чём же твоё "чтобы удобней было" состояло, если не в искуственной классификации. Потому как в этом смысле сохраняется полностью, да еще в самом типобезопасном варианте.

{-$ OPTIONS -fwarn-incomplete-patterns -fwarn-overlapping-patetrns #-}

V>>>Это я про то, что мы можем для нашего случая специализировать всего 1 метод этого класса для различных сочетаний и избежать диспечеризации в ран-тайм. А если использовать частичную специализацию, то можно описывать обработчики для целого класса за раз.
T>>То же можно сделать с помощью rewrite rules, когда упрёмся в производительность.
T>>Не надо выполнять преждевременной оптимизации.
V>Ха-ха, это для хаскеля такой финт — преждевременная оптимизация, а для шаблонов С++ — стандартное использование, которое экономит многие строки кода.

Я потерял твою мысль.

Приведи пример кода на Хаскеле и на C++.

V>И вообще, не стоит бездумно разбрасываться шаблонными фразами, удешевляя смысл сокрытой в них мудрости.

Действительно.

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

V>>>>А то ты про алгебраические типы говорил, а в compile-time template<typename Left, typename Right> AstNode — такой же алгебраический тип с т.з. компилятора, не находишь?
T>>>Нет, не нахожу.
V>>Поищи внимательней еще раз.
V>>Хинт: в С++ порой значительная часть программы выполняется в compile-time при использовании шаблонов.

T>Что это означает?

В данном примере диспечеризация у нас выполняется в compile-time, и в течении этого процесса семейство конкретных инстациирований приведенного шаблонного типа AstNode — такой же точно алгебраический тип, как для тебя алгебраические типы Хаскеля в run-time.

T>{-$ OPTIONS -fwarn-incomplete-patterns -fwarn-overlapping-patetrns #-}

И что? Для статической диспетчеризации в моём случае опций никаких задавать не надо, компилятор или линковщик и так знать дадут, если что-то забуду.
Например, для этого подхода ругнется линковщик при отсутствии обработчика нужной комбинации:

// H - файл
template<typename Left, typename Right> 
class AstNode : public AstNodeBase {
   Left left; Right right;
public:
  // пусть это будет переопределение виртуального метода
  virtual void Process();
};

...
// CPP-файл
// обработчик для конкретного типа
void AstNode<int, int>::Process() { ... }

А в этом случае компилятор даст знать при отсутствии нужной пары:

// объявление
template<typename Node>
struct Processor;

// определение для конкретной пары типов
template
struct Processor<AstNode<int, int> > {
  static void Process(AstNode<int, int> node) { ... }  
};

Букв много, но теми же макрами их режут как-то так:

DEF_PROC(int, int, { ... } );

T>>>Не надо выполнять преждевременной оптимизации.
V>>Ха-ха, это для хаскеля такой финт — преждевременная оптимизация, а для шаблонов С++ — стандартное использование, которое экономит многие строки кода.
T>Я потерял твою мысль.
T>Приведи пример кода на Хаскеле и на C++.

Для С++ привёл, для Хаскеля ты уже приводил. Скопировать еще раз? Логичней будет, чтобы ты объяснил, куда бы приспособить твой лозунг насчёт преждевременной оптимизации.

T>>Что это означает?
V>В данном примере диспечеризация у нас выполняется в compile-time, и в течении этого процесса семейство конкретных инстациирований приведенного шаблонного типа AstNode — такой же точно алгебраический тип, как для тебя алгебраические типы Хаскеля в run-time.

Нет глубокого анализа.

    ors (Or a b)        = ors a >> hPutStr h " " >> ors b
    ors (Var a)         = hPutStr h (show (varIds Map.! a))
    ors (Not (Var a))   = hPutStr h ("-" ++ show (varIds Map.! a))
    ors (Label a)       = hPutStr h (show (labIds Map.! a))
    ors (Not (Label a)) = hPutStr h ("-" ++ show (labIds Map.! a))
    ors _               = error $ "Formula is not in CNF."

(HDL Atom, предшественник Bluespec, модуль SAT.hs)

T>>{-$ OPTIONS -fwarn-incomplete-patterns -fwarn-overlapping-patetrns #-}
V>И что? Для статической диспетчеризации в моём случае опций никаких задавать не надо, компилятор или линковщик и так знать дадут, если что-то забуду.
V>Например, для этого подхода ругнется линковщик при отсутствии обработчика нужной комбинации:
V>

V>// H - файл
V>template<typename Left, typename Right> 
V>class AstNode : public AstNodeBase {
V>   Left left; Right right;
V>public:
V>  // пусть это будет переопределение виртуального метода
V>  virtual void Process();
V>};

V>...
V>// CPP-файл
V>// обработчик для конкретного типа
V>void AstNode<int, int>::Process() { ... }
V>

У тебя очень, очень простой анализ. Неглубокий.

V>Букв много, но теми же макрами их режут как-то так:
V>

V>DEF_PROC(int, int, { ... } );
V>

Да-да. Макрами режут.

T>>>>Не надо выполнять преждевременной оптимизации.
V>>>Ха-ха, это для хаскеля такой финт — преждевременная оптимизация, а для шаблонов С++ — стандартное использование, которое экономит многие строки кода.
T>>Я потерял твою мысль.
T>>Приведи пример кода на Хаскеле и на C++.

V>Для С++ привёл, для Хаскеля ты уже приводил. Скопировать еще раз? Логичней будет, чтобы ты объяснил, куда бы приспособить твой лозунг насчёт преждевременной оптимизации.

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

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

Всё то же, что в C++ и более того, но медленней. Быстро можно сделать с помощью правил переписывания. Выполнить оптимизацию.

Твои соображения насчёт compile time dispatch заботятся только о скорости, об удобстве использования во вторую (хорошо, если так) очередь.

Здравствуйте, vdimas, Вы писали:
V>Потому что, "может быть распараллелено" и принципиально требует паралельного расчёта — это разные вещи. Матрица принципиально не требует, а ты лишь параллелишь до определённого уровня, подсчитывая и иерархически складывая частичные суммы. Ну блин, прямо Америку открыл, посмотри на БПФ и алгоритм "бабочки", и заодно станет понятно, почему он требует кол-во отсчётов, равное степени двойки — та же фигня.
оффтоп: БПФ (т.е. Кули-Тьюки) не требует степени двойки. Это популярный миф.

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

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

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

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

S>оффтоп: БПФ (т.е. Кули-Тьюки) не требует степени двойки. Это популярный миф.

Какой миф? Алгоритм-то простейший. Посмотри сам, что происходит в случае подачи кол-ва отсчётов, отличное от степени двойки. Там всего два варианта: прореживание по частоте, или прореживание по времени, известные алгоритмы являются вариациями на эти темы. Но суть тут одна — каждый из вариантов использует БПФ на основе степени 2-ки как "подпрограмму", и отличаются они только способами формирования подпоследовательностей.

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

Здравствуйте, vdimas, Вы писали:
V>Какой миф?
Обычный, городской
V>Алгоритм-то простейший. Посмотри сам, что происходит в случае подачи кол-ва отсчётов, отличное от степени двойки. Там всего два варианта: прореживание по частоте, или прореживание по времени, известные алгоритмы являются вариациями на эти темы. Но суть тут одна — каждый из вариантов использует БПФ на основе степени 2-ки как "подпрограмму", и отличаются они только способами формирования подпоследовательностей.
Вообще-то в алгоритме используется разложение количества отсчетов на простые делители. Вычислительная сложность линейно зависит от произведения количества делителей на их "размер". В случае N = 2^K получается ровно К=log2(N) делителей, само разложение выполняется тривиально, и делитель равен двум. "Подпрограмма" получается ровно одна. В случае, когда N простое, всё получается как можно хуже: сложность алгортма возвращается к O(N^2) для обычного ДПФ. Сравни, к примеру, заголовки 4.1. и 4.2 здесь. Так что алгоритм К-Т по основанию два — всего лишь популярный частный случай.
Существует библиотека, построенная на темплейтах C++ и бусте с локи, где БПФ преобразование выполняется для любого непростого N.

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

Да, к примеру, если у тебя есть 1000 отсчетов, ты можешь дополнить его до 1024 и воспользоваться "тупым К-Т алгоритмом". А можешь разложить 1000 на 2*2*2*5*5*5 и получить временные характеристики, близкие к 2*2*2*2*2*2*2*2, безо всяких искажений спектра.

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

S>Существует библиотека, построенная на темплейтах C++ и бусте с локи, где БПФ преобразование выполняется для любого непростого N.
Доклад про это решение был представлен на конференции PSI'03 (http://psi.nsc.ru/psi03/list_e.shtml) "Marcin Zalewski and Sibylle Schupp. Polymorphic Algorithms FFT-Implementations That Share". Доклад в ПостСкрипте здесь.

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


S>Да, к примеру, если у тебя есть 1000 отсчетов, ты можешь дополнить его до 1024 и воспользоваться "тупым К-Т алгоритмом". А можешь разложить 1000 на 2*2*2*5*5*5 и получить временные характеристики, близкие к 2*2*2*2*2*2*2*2, безо всяких искажений спектра.

Не совсем, низкая степень повторного использования слагаемых получится, тут у тебя в 2 раза примерно больше времени на вычисление. И еще есть тот факт, что в двоичном виде парная позиция — это перестановка бит в обратном порядке, и вообще много операций простым сдвигом выполняются, а для множителя 5 надо будет умножениями заниматься. Для всяких однокристаллических ЭВМ без умножителя это критично.

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

V>Не совсем, низкая степень повторного использования слагаемых получится, тут у тебя в 2 раза примерно больше времени на вычисление.
Кстати, перечитал статью — что-то с памятью. У меня отложилась значительно более оптимистичная оценка результатов.
На практике, парни наблюдали странные эффекты с разбросом времен в 1000 раз, и на момент публикации не имели понятия, где там порыта собака.

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

V>>Не совсем, низкая степень повторного использования слагаемых получится, тут у тебя в 2 раза примерно больше времени на вычисление.
S>Кстати, перечитал статью — что-то с памятью. У меня отложилась значительно более оптимистичная оценка результатов.
S>На практике, парни наблюдали странные эффекты с разбросом времен в 1000 раз, и на момент публикации не имели понятия, где там порыта собака.

Некоторые умудряются память динамически выделять во время расчётов БПФ (в одной из верхних ссылок по гуглю есть нехороший исходник), да мало ли что еще.
Принципиально больше всего повторений для множителя 2. Если какой-то из множителей встречается лишь однажды, то для него никаких повторений. Каждый множитель, отличный от 2-х, это суть классическое прореживание по частоте или времени (не принципиально) над БПФ, со всеми вытекающими. Например разложение 5*3*2^N эквивалентно 15*2^N, прореживание = 15, а это полный Вася, собирать потом 15 независимых БПФ.

--------------
На самом деле, классический БПФ экономит хоть и много, но на практике недостаточно — слишком много умножений всё-равно. Так вот еще один способ свести кол-во вычислений практически к K*Log(N), где К-константа, — это ограничение разрядности таблицы синусов. В принципе, 3-х разрядов достаточно для очень многих применений (особенно в случае непрерывной фильтрации результатов — ошибки сглаживаются). При таком раскладе вместо log(N) умножений имеем максимум К=7 различающихся вариантов умножения, и если таблица синусов захардкожена в умножениях на константу в развёрнутом цикле (6 различных значений синуса S всего, т.к. 0 пропускается при кодогенерации), то известно сколько раз встречается каждый из вариантов (M), т.е. захардкожено умножение на известную константу S*M, да и среди этих констант бывают повторения (с точностью до знака). В общем, на однокристалках без умножителей можно довольно приличные последовательности в реалтайм обсчитывать.

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

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

V>Технология generics в .Net позволит при надобности построить полностью типизированные узлы в рантайм, но у меня оччень большие сомнения в необходимости этого (обрати внимание на вывод типа узлов верхнего уровня — мрак).

А можно о выделенном чуть поподробнее?