Category: дизайн

Category was added automatically. Read all entries about "дизайн".

with Cat The Cat

Ещё одно разочарование.

Для Хаскеля нет простых веб-фреймворков.

Вообще нет, совсем, никаких.

Это связано с тем, что все (ВСЕ!) веб-фреймворки используют WAI. WAI, Web Application Interface, представляет из себя библиотеку в 18 (примерно) каталогов, каждый из которых содержит по несколько исходных файлов.

WAI это результат работы Сноймана, автора Есода, самого сложного веб-фреймворка, что я видел. Про Есод я могу сказать только одно - я не представлял, что программирование приложения можно сделать настолько сложным. По-моему, Снойману удалось возвести программирование на Хаскеле на высоту промышленной Явы. Поэтому я не удивлён, что WAI настолько сложна и объёмна.

Наличие объёмной прослойки между сервером и кодом самого приложения не упрощает ни первого, ни второго. Именно поэтому все (ВСЕ!) веб-фреймворки на Хаскеле настолько сложны.

Сложность я мерил по себе, конечно же. После того, как мне пришлось прыгать по документации и исходному коду ТРЁХ РАЗНЫХ ПАКЕТОВ И ПАРЫ ПРИМЕРОВ для получения понимания, как же добавить формочку в страничку в фреймворке Spock (а до этого я не смог вообще ничего сделать в течении часа, изучая Snap), я счёл, что надо посмотреть, есть ли простые варианты. Самый простой вариант это Simple, но и он излишне сложен.

Может быть, что дело во мне - я неразумно считаю, что веб-программирование простая вещь, а она сложна и сложность WAI оправдана. Вполне может быть. Это не означает, что веб-программирование должно оставаться сложным.
with Cat The Cat

Возвращаясь к LevelDB.

Делая хранилище, реализовал Crit-Bit trees (близкий аналог, на самом деле - у меня C#, а дизайн по ссылке для C) и на их основе приоритетную очередь, где приоритет - лексикографический порядок ключей (как у memcmp).

Получил ускорение, как и ожидал. Пока измерил для небольшого объема, 120000 вставок. Скорость возросла на 40% (458 супротив 771 миллисекунды). Это хорошо объяснимо - при вставке в очередь проход по ключу осуществляется всего один раз.

Я понял смысл выбора дизайна LevelDB - они позволяют сравнивать записи, не конвертируя их в подходящее для memcmp представление. Это нормально, может быть, даже ускоряет работу. Но будучи совмещенным с другим выбором - список с пропусками для структуры быстрого поиска, - делает невозможной алгоритмическую оптимизацию, которая доступна для memcmp-совместимого ключа и crit-bit trees.
with Cat The Cat

Про "дизайн" встроенных малых языков на C#.

(ниже я буду использовать квадратные скобки для параметров шаблонов)

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

На работе я сделал прототип вот такого подъязыка для запросов к нашей БД:
string name = "b1";
var query = IPRQuery
    .From(ClassA.Description) // Создаём выборку.
    .Where( a => a.Index < 10) // прореживаем выборку.
    .RelatedTo(ClassB.Description) // Создаём ещё одну выборку -
                                   // экземпляров класса ClassB, состоящих
                                   // хоть в каком-то отношении с экземплярами выше.
                                   // Это ограничивает и первую выборку, кстати.
    .Where ( b => b.Name == name)  // Прореживаем и...
                                   // проецируем:
    .Select( (a,b) => new { Name = b.Name, Index = a.Index, A = a});
foreach (var e in query) { // создание запроса и обращение к БД.
    Console.WriteLine("Name "+e.Name+", Index "+e.Index+", ClassA object index "+a.Index);
}
Вся эта штука создана на основе статических методов и методов расширения.

Один из From, например, сделан как статический метод IPRQuery:
class IPRQuery {
    static public IPRQuery[T] From[T](IPRClassDescription[T] source) where T : IPRObject
}
Он создаёт выборку. Однако мы можем добавить ещё одну выборку, и тут нам нужны методы расширения:
class IPRQueryExt {
    static public IPRQuery[Pair[X,T]]
        From[X,T](this IPRQuery[X],IPRClassDescription[T] source) where T : IPRObject
}
Это позволяет сделать сколь угодно много From через точку.

RelatedTo сделана ровно таким же способом, только вместо простого добавления ещё одного источника мы добавляем ещё один источник с операцией связи. Она тоже требует параметр источника производный от IPRObject, также создаёт IPRQuery от пары.

From и RelatedTo можно перегрузить для разных источников: это описание класса (выше), IPRQuery[T] для подзапросов и конкретный объект, производный от IPRObject, например, экземпляр ClassA выше (From(classAObject)). Получается удобно, можно, например, выбрать все объекты, связанные с данным.

Where и Select также сделаны на основе перегрузки, и тоже, по большей части, методы расширения.
class IPRQueryExt {
    static public IPRQuery[T]
        Where[T](this IPRQuery[T],Func[T,Bool])
    static public IPRQuery[Pair[X,T]]
        Where[X,T](this IPRQuery[X,T],Func[T,Bool])
    static public IPRQuery[Pair[X,T]]
        Where[X,T](this IPRQuery[X,T],Func[X,T,Bool])
    static public IPRQuery[Pair[Pair[X1,X2],T]]
        Where[X1,X2,T](this IPRQuery[Pair[Pair[X1,X2],T]],Func[X1,X2,T,Bool])
}
И тд. Мы делаем вложенную структуру типов IPRQuery плоской для простого вызова функции.

Select завершает выборку, создавая проекцию данных из БД в данные C#. Сделан он по образу и подобию Where.

Отдельно надо сказать про преобразование кода функций.

Я не стал особо заморачиваться, а сделал практически как на ФЯ, сравнением с образцом. Преобразование кода сводится к перебору всех типов, что могут придти в каком-то месте:
internal string WhereExpr(Expression expr) {
    if (expr is BinaryExpression) { ...}
    else if (expr is UnaryExpression) { ...}
    else if (expr is ...) { ...}
    throw new Exception("Unknown expression "+expr.ToString());
}
А чего мучиться? ;)

Для получения значений параметров из окружения (выше это видно где мы прореживаем с b => b.Name == name) я, не мудрствуя лукаво, создаю лямбда-выражение типа Func[object] и вычисляю его, получая object, который я преобразую в строку (и для строк (typeof(string).IsAssignable(object.GetType())) я ещё делаю замену символов - кавычки, спецсимволы, тому подобное).

Вуаля!

Я ещё не задумывался над GroupBy, SortBy и т.п. Посмотрим. ;)

В общем, мой прототип получил одобрение у всех заинтересованных сторон и я надеюсь довести его до полноценной библиотеки. Когда руки дойдут. ;)
with Cat The Cat

Пост про дизайн.

Большое спасибо archimag, откликнувшегося на мою предложение написать пост.

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

Хочется, однако, поднять тему сравнения дизайнов программ. Особенно, ещё не написанных программ. А потом я про типы в дизайне расскажу, куда ж без них. ;)

Насколько я понял, позиция archimag (как же адресовать blogspot?) такова: в самом начале мы не можем сказать, насколько хорош дизайн, мы это можем сказать только апостериори.

Если программа может быть написана двумя или более способами, то необходимо произвести выбор одного из них. Archimag предлагает выбрать дизайн наугад и потом оценить, подошёл ли он. Желательно бы делать лучше, например, уметь сравнивать дизайны между собой.

В том самом обсуждении я предложил следующий вариант: сперва сравниваем дизайны по тому, как много сценариев программы они покрывают, потом сравниваем по количеству кода, потребному для реализации дизайна. Такая несложная иерархия.

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

Теперь надо немного добавить про типы.

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

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

Приведу пример.

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

Для ограничения действий dup и over мы введём парочку классов:
-- у класса FAIL не должно быть реализаций. Сейчас покажу, почему.
class FAIL e

-- класс StackSlot указывает, что тип может быть сохранён в ячейке стека.
class StackSlot a
-- и реализации, который просто сигнализируют, что можно использовать
-- как элемент стека.
instance StackSlot Int
instance StackSlot Char
instance StackSlot (Pointer a)

-- А вот для Maybe потребуется FAIL, реализации которого быть не может.
instance FAIL (Maybe a) => StackSlot (Maybe a)

-- Наши новые типы для dup и over:
dup :: StackSlot a => StackOp (Stack1 stk a) (Stack2 stk a a)
over :: (StackSlot a, StackSlot b) =>
        StackOp (Stack2 stk b a) (Stack3 stk b a b)
Теперь наши примитивы более безопасны и почти так же удобны.

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

Хотя идея приблизительно понятна. Это уже проходили в "Зависимых типах для распределённых массивов" - надо задать типами контракты на содержимое каждого узла системы, тогда будет понятно, что куда как идёт.

Пожалуй, это всё, что я хотел сказать. ;)

PS
Вспомнил.

Ещё типы позволяют лучше управлять повторным использованием кода. Вот.

Проще отыскать что с чем и как работает.

Что должно положительно сказываться на скорости внесения изменений.
with Cat The Cat

Про ленивость и энергичность, программерское.

У нас есть два вида "ленивости" - с запоминанием, как в Haskell/Miranda/Clean и без оного, как в ОКамл (прошу учесть, что когда я интересовался OCaml, там ленивых вычислений толко и не было, все предпочитали пользоваться функциями от (), unit). Последняя проще в реализации, но толку от неё чуть.

Взять те же числа Фибоначчи:
fibs = 1:1:zipWith (+) fibs (tail fibs)
Без запоминания результатов каждое число Фибоначчи будет вычислять все предыдущие. Получаем экспоненциальную сложность алгоритма, как в наивной реализации.

Большой смысл имеет только реализация на основе упрощения графов.

Одна из методик компиляции под названием GRIN (Graph Reduction Intermediate Notation) подходит и для трансляции энергичных языков тоже. Я описывал то, что из этого понял вот тут.

Итак, используя GRIN, мы можем транслировать смесь энергичного и ленивого кода.

С её помощью можно оценить количество необходимых аннотаций ленивости.

Возьмем для примера map.

map :: (a -> b) -> [a] -> [b]
map f (x:xs) = f x:map f xs
map f []     = []
Итак, map по умолчанию энергичен, причем энергичен и при вычислении аргументов конструктора (:) и при вычислении конструктора списка ([] или (:)).

Можно ли сделать map ленивым не меняя его код? И до какой степени?

Вот интересные случаи:
  1. snd (map id (error "aaa"),10) -- map может не форсировать вычисление входного списка вообще
  2. drop 1 $ map id (error "aaa":1:[]) -- map может не форсировать вычисление элементов списка
  3. take 1 $ drop 1 $ map id (error "aaa":1:error "bbb") -- map может не форсировать вычисление хвоста списка
Если наш map по умолчанию энергичный, мы не можем реализовать первый пункт. То же самое с третьим пунктом. Они открыты только при модификации кода.

А вот второй пункт для нас открыт: мы передадим функцию, которая возвращает отложенное вычисление вместо значения.

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

Это всё из-за того, что в качестве аргумента к нам может придти как значение, так и отложенное вычисление, а значит, аргумент надо форсировать и запоминать вычисленное значение.

Можно не запоминать - OCaml. Но тогда будет похуже.

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

Ленивые вычисления сложны при их пристальном рассмотрении. Даже на таком простом примере.

Теперь надо рассмотреть обратный случай: можно ли сделать ленивый map сколь угодно энергичным?

Первый вариант я решать не берусь (нужна энергичная пара, tuple), а для второго и третьего у меня готовы решения.

Для того, чтобы вычисление map стало не ленивым по хвосту, надо сделать так:
strictTail [] = []
strictTail (x:xs) = (x:) $! strictTail xs
И применить strictTail к результату map f list.

Вот strictHead:
strictHead [] = []
strictHead (x:xs) = ((:) $! x) (strictHead xs)
Вот.

Модифицировать map мне не надо, а значит, выше модульность.

На этом, пожалуй, всё. ;)
with Cat The Cat

Еще замечание.

Не так давно я давал ссылочку на страницу на LtU со ссылкой на статью про информационно-ориентированный дизайн.

При всех ее достоинствах, сверстана она так, что я с моим увеличенным шрифтом (у меня слабое зрение) читать ее не могу вовсе. А от оглавления остается всего 2/3.

Что из этого следует, не знаю. ;)