K>Вот в том же компиляторе Nemerle применяются персистентные словари, реализованные как деревья применяются для излишней сложности? Планируете заменить на хэш-таблицы?
Там максимум можно заменить на дерево хеш-таблиц.
Т.е. максимум что можно сделать — это подчиненные узлы хранить у родителя не в списке, а в хеш-таблице. Но, учитывая небольшое кол-во объявлений в каждом конкретном scope, смысла большого нет.
K>Класс типа — это кортеж функций, который подставляет в неявный параметр функции компилятор.
Кортеж _обязательных_ для реализации ф-ий.
K>Что у них общего? K>С констрейнтами дженериков (к ООП не имеют никакого отношения) их еще можно сравнивать. Но с Явовскими интерфейсами?
Класс типов решает похожую задачу — определяет контракт на операции с типом. А разве явовские интерфейсы не для этого? Или ты имел ввиду, что в случае Явы мы имеем дело с динамическим полиморфизмом интерфейсов, в отличие от статического в случае классов типов Хаскеля? Ну дык, и Хаскель интерпретируемый бывает.
Здравствуйте, vdimas, Вы писали:
V>Там максимум можно заменить на дерево хеш-таблиц. V>Т.е. максимум что можно сделать — это подчиненные узлы хранить у родителя не в списке, а в хеш-таблице. Но, учитывая небольшое кол-во объявлений в каждом конкретном scope, смысла большого нет.
В компиляторе немерла таких извратов нет.
Сейчас там использовано вот это: http://rsdn.ru/forum/nemerle/3290129.flat.aspx
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, vdimas, Вы писали:
V>>Там максимум можно заменить на дерево хеш-таблиц. V>>Т.е. максимум что можно сделать — это подчиненные узлы хранить у родителя не в списке, а в хеш-таблице. Но, учитывая небольшое кол-во объявлений в каждом конкретном scope, смысла большого нет. WH>В компиляторе немерла таких извратов нет.
Дык про то и речь, что в подобных случаях хеш-таблицы не рулят. На небольших объемах (коими является список символов, вводимых в пределах одного ыscope) рулят просто упорядоченные массивы и разновидности быстрого поиска по ним.
WH>Сейчас там использовано вот это: http://rsdn.ru/forum/nemerle/3290129.flat.aspx
Я подозрительно отношусь к реализации алгебраических типов через сабклассы. Т.е. даже в отсутсвии рекурсии в определении типа невозможно будет представить его как value-type.
Здравствуйте, vdimas, Вы писали:
V>Дык про то и речь, что в подобных случаях хеш-таблицы не рулят. На небольших объемах (коими является список символов, вводимых в пределах одного ыscope) рулят просто упорядоченные массивы и разновидности быстрого поиска по ним.
А что делать с внешними? А ведь они могут быть весьма не маленькими.
Короче на данной задаче как ни крути все заруливает неизменяемое дерево поиска. Ибо мы можем очень дешево хранить много немного отличающихся версий этого дерева.
V>Я подозрительно отношусь к реализации алгебраических типов через сабклассы. Т.е. даже в отсутсвии рекурсии в определении типа невозможно будет представить его как value-type.
А это тут вообще при чем? В случае дерева узлы по любому не могут быть value типами.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
v> M>Не так уж и много приходится платить
v> Превращение многих задач из O(N) в O(N^2) из-за пересоздания структур данных при каждом вычислении — это на больших объемах пока что отсос полный на подобных задачах. Банальный кеш данных не сделаешь.
Значит, надо пользоваться другими алгоритмами Значит, надо кэшировать структуры Значит, надо делть что-то еще
«Не так уж и много» я имел в виду что-то вроде тут. Отставание в 2-3 раза от императивщины на многих задачах, имхо, часто не такая уж и высокая цена
Здравствуйте, WolfHound, Вы писали:
WH>А что делать с внешними? А ведь они могут быть весьма не маленькими. WH>Короче на данной задаче как ни крути все заруливает неизменяемое дерево поиска. Ибо мы можем очень дешево хранить много немного отличающихся версий этого дерева.
Дерево — да, но дерево лишь абстракция. Для своего интерпретатора Схемы я собирал environment именно как дерево из различных scope. Но в этой задаче узлом является не символ, а scope, соотвественно реализация различных scope может быть различной, у меня каждый локальный scope — это был упорядоченный массив, глобальный scope был хеш-таблицей. Очень удобно, ведь ты дерево при поиске символа рассматриваешь не с верху, а с конкретного листа, текущего scope, поэтому для тебя путь до корня — лишь линейный упорядоченный список этих вложенных scope (для случая импорта неймспейсов и прочих областей видимости вполне понятно как добавить разновидность некоего meta-scope).
С "версионностью" тоже было ну крайне просто, т.к. для Схемы вложенность этих scope всегда однонаправленная, то дерево достаточно образовать лишь отношением GetParent(), поэтому как таковая версионность не требовалась, ибо каждый путь от листа до корня суть своя "версия" этого environment.
V>>Я подозрительно отношусь к реализации алгебраических типов через сабклассы. Т.е. даже в отсутсвии рекурсии в определении типа невозможно будет представить его как value-type. WH>А это тут вообще при чем? В случае дерева узлы по любому не могут быть value типами.
Почему? У меня деревья поголовно примерно такие:
struct Node<T> {
T data;
Node<T>[] children;
}
T тоже в 99% случаев value-type.
Просто для твоего конкретного случая, когда ты подчиненные узлы размещаешь как поля типа (т.к. их известное кол-во в твоей задаче), это не суть важно, ибо получается тот же уровень коссвенности (ну еще +1, если быть точным, но не принципиально). А для общего случая показанное мной весьма даже руль, и там уровень коссвенности ровно вдвое ниже.
Здравствуйте, vdimas, Вы писали:
V>Дерево — да, но дерево лишь абстракция.
Блин! Ты опять как тетерев токуешь.
Тут разговор про 2-3 дерево которое является частным случаем B дерева. Раньше в компиляторе было красно-черное дерево но он несколько медленней.
И это конкретная структура данных, а никакая не абстракция.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, hattab, Вы писали:
H>Здравствуйте, gandjustas, Вы писали:
H>>>Очевидно презентация это единственный юзкейс для подобной хни
H>Не переживай за меня. Приведи примеры.
Зачем после выделенной фразы что-либо Вам приводить?
Здравствуйте, vdimas, Вы писали:
V>В тех же задачах обработки сигнала на серверной стороне высокоуровневый ЯП используется... ну как удобный инструмент для непосредственного управления низкоуровневыми ресурсами железа, которые по природе своей имеют адреса и состояния в них. Не споря с тем, что в функциональном плане одну и ту же задачу вполне можно решить разными подходами, эффективность полученных решений может слишком различаться.
Не нужно путать способ декомпозиции и особенности конкретной реализации.
... << RSDN@Home 1.2.0 alpha 4 rev. 1228>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, VladD2, Вы писали:
VD>Ну, в прочем хэш-таблица удобнее хотя бы тем, что применима к объектам которые не могут быть сравнены на больше-меньше.
Хэш-таблица применима к объектам, для которых можно вычислить хэш. Т.е. отобразить на множество целых чисел. Целые числа могут быть сравнены на больше-меньше.
VD>А объекты, значит, не годятся для представления любых, в том числе и этих, данных?
Ну конечно годятся. Только выраженного преимущества не имеют. И как раз они-то и могут оказаться теми самыми "ненужными абстракциями" о которых вы писали выше.
VD>Ну, какой бы ни был дизайн этого мира, но он таков каков он есть .
Мы говорим не о дизайне мира, а о дизайне программ. Важно почувствовать разницу.
VD>Понимание того как применять формулу "S = a * b" не дает ни капельки для понимания того как спроектировать, написать и отладить большую и сложную систему. ООП дает методологию для этого. ФП нет.
Для каждого инструмента построения "больших и сложных систем" из ООП есть аналогичное средство ФП, которое ничуть не хуже. Можете привести примеры чего-то такого, что есть в ООП, а в ФП — нет?
... << RSDN@Home 1.2.0 alpha 4 rev. 1228>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Ночной Смотрящий, Вы писали:
НС>Вообще, имхо, погоня за чистотой до добра не доведет.
Не понимаю, что подразумевается под "погоней за чистотой". Разделение кода на чистый и "нечистый" до добра не доведет? По-моему, как раз отсутствие такого разделения до добра и не доводит.
НС>Основная цель существования ЯВУ — обеспечение взаимодействия формальной логики машины и неформальных мозгов программиста. Можно конечно попытаться мозги перетачивать, только снижение трения внутри ЯВУ с минимизацией давления на мозги явно продуктивнее.
Основная цель существования ЯВУ — это сформулировать решаемую проблему более-менее формально. Для того, чтобы формализовать мышление самого программиста и для того, чтобы программисты решающие одну задачу могли обсуждать ее на одном языке. Т.е ЯВУ — это язык для программиста, взаимодействие с машиной обеспечивает компилятор этого ЯВУ, по большому счету, автоматически. И эволюция ЯВУ происходит в направлении отдаления ЯВУ от языка машины и приближении к языкам, которые придумывались для решения проблем человеком. Языки для человеческого мозга (например, матанализ или дифгеометрия) мозг, естественно, не перетачивают. Они дают мозгу инструментарий для решения проблем. И улучшение этих языков — единственный известный и продемонстрировавший свою эффективность на опыте способ улучшения человеческого мышления.
НС>Не только. Для некоторых деревьев требуется балансировка или fill factor, что может геморой свой внести. Генерация хешкода все таки менее проблемна обычно.
Несбалансированное дерево и плохая хешфункция приводят к одной и той же проблеме: ухудшению асимптотики. Вот только дерево можно автоматически балансировать, а автоматически получить хорошую хэш функцию можно только в том случае, когда мы создаем хеш-таблицу для некоторого набора данных и больше уже этот набор не изменяем.
НС>Ну и immutable деревья свои заморочки привносят, когда модификация неудобна для них.
Модифицировать их вообще нельзя, поэтому заморочки связанные с модификацией характерны для хештаблиц, но уж точно не для деревьев.
НС>Ну, с программистом дела похуже обстоят, иногда ему даже эти самые компиляторы писать приходится.
Обстоят дела точно так же. Создание инструментов требует одной квалификации — использование инструментов требует другой квалификации (не меньшей в общем случае, но другой). В этом и заключается смысл создания инструментов — чтобы у одних болела голова об одном, у других — о другом, а не у всех обо всем — это способ борьбы со сложностью.
... << RSDN@Home 1.2.0 alpha 4 rev. 1228>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, vdimas, Вы писали:
V>Там максимум можно заменить на дерево хеш-таблиц. V>Т.е. максимум что можно сделать — это подчиненные узлы хранить у родителя не в списке, а в хеш-таблице. Но, учитывая небольшое кол-во объявлений в каждом конкретном scope, смысла большого нет.
Замена персистентной структуры данных на неперсистентную в том случае, когда версионность использовалась, всегда будет связано с серьезными сложностями.
... << RSDN@Home 1.2.0 alpha 4 rev. 1228>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, vdimas, Вы писали:
V>Кортеж _обязательных_ для реализации ф-ий.
Вообще-то не все функции обязательны для реализации потому, что одни могут быть выражены через другие. Нет, например, необходимости реализовывать функции "равно" и "не равно" — достаточно реализовать одну из двух.
V>Класс типов решает похожую задачу — определяет контракт на операции с типом.
Определение сходства по решаемым задачам — путь, в данном случае, тупиковый. По той простой причине, что в рамках такого взгляда вся эта дискуссия не имеет никакого смысла. ФП и ООП решают не просто похожие, но две совершенно одинаковые задачи — абстрагирование и декомпозицию.
Все, что можно обсуждать в данном случае — это то, какими способами задачи решаются и эти способы, вообще говоря, серьезно различаются.
... << RSDN@Home 1.2.0 alpha 4 rev. 1228>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Farsight, Вы писали:
H>>>>Очевидно презентация это единственный юзкейс для подобной хни
H>>Не переживай за меня. Приведи примеры.
F>Зачем после выделенной фразы что-либо Вам приводить?
А что тебе не понравилось в выделенной фразе? Что я возможность пернуть подмышкой хней назвал?
Здравствуйте, Klapaucius, Вы писали:
K>Основная цель существования ЯВУ — это сформулировать решаемую проблему более-менее формально.
Это не проблема, это следствие.
K> Для того, чтобы формализовать мышление самого программиста
Во-во, об этом я и говорю: вместо того, чтобы делать язык максимально удобным для пользователя, мы начинаем формализовать мышление в угодду техническим аспектам. Это как, вместо того, чтобы сделать кресло по форме задницы, мы разрабатываем методику, как сидеть на таком кресле, которое проще изготовить.
Здравствуйте, Ночной Смотрящий, Вы писали:
K>>Основная цель существования ЯВУ — это сформулировать решаемую проблему более-менее формально. НС>Это не проблема, это следствие.
Не понял. Что не проблема?
K>> Для того, чтобы формализовать мышление самого программиста НС>Во-во, об этом я и говорю: вместо того, чтобы делать язык максимально удобным для пользователя, мы начинаем формализовать мышление в угодду техническим аспектам.
Нет, я говорю о том, что для того, чтобы язык был максимально пригодным для решения задач и минимально неудобным для пользователя он должен быть формализован "в угоду" решаемым проблемам, а не техническим аспектам. От технических аспектов — т.е. торчащих через дыры в абстракциях углов железа нужно избавлятся, по мере того, как прогресс железа и оптимизаторов это позволяет. Так вот, неизолированное изменяемое состояние я рассматриваю как порчу языка в угоду техническим аспектам.
НС>Это как, вместо того, чтобы сделать кресло по форме задницы, мы разрабатываем методику, как сидеть на таком кресле, которое проще изготовить.
Все дело в том, что для кресла удобство задницы — основная задача. В том случае, если основная задача другая — нужно прибегать к компромиссу и иметь дело с вышеуказанным минимаксом: решать основную задачу максимально эффективно, при минимальном ущербе для задницы. В любом случае, с моей точки зрения движение от машины к проблеме полезно и для решения проблем и для удобства задницы. В чем удобство для человека в близости к железу мне не понятно — я всегда считал, что близость к железу вынужденная. От бедности.
... << RSDN@Home 1.2.0 alpha 4 rev. 1228>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Farsight, Вы писали:
H>>А что тебе не понравилось в выделенной фразе? Что я возможность пернуть подмышкой хней назвал?
F>Суть в том, что выделенная фраза неадекватна. Ты же отметешь любые примеры и будешь стоять на том, что SL это хня. Так зачем тебе что-либо приводить?
Вообще-то речь шла не о SL, а всего лишь о:
Сделать приложегние на С++ чтобы в нем было тесктовое поле ввода, которое крутится вокруг своей оси и в него можно вбивать текст. А в фоне этого поля ввода крутился какой-нибудь видеоролик.
Если у тебя есть варианты других юзкейсов (кроме презентационной пыли в глаза пионерок) этой хни -- в студию.
Значит, надо кэшировать структуры 
