Здравствуйте, D. Mon, Вы писали:
DM>Если мы откуда-то пришли, значит мы там уже были и могли запомнить это место (.save), зачем туда опять пешком идти?
Дело не в месте, а в направление. Итерация назад в варианте BidirectionalRange возможна только с конца. В то время как у нормального двусвязного списка с любого элемента. Это явно бредово. Но меня не особо напрягает, т.к. я этот DList и вообще BidirectionalRange обхожу стороной. )))
Здравствуйте, D. Mon, Вы писали:
EP>>Или, например то, что по двусвязному списку нельзя пройтись в обратном направлении тому откуда мы пришли — это тоже вполне конкретная алгоритмическая инвалидность. DM>Если мы откуда-то пришли, значит мы там уже были и могли запомнить это место (.save), зачем туда опять пешком идти?
Запоминать каждое состояние range которое мы посетили? Машина Тьюринга как-то умеет обходится без этого:
DM>Достать итераторы — да, дело хорошее. Но я же про другое — про возможность слепить range из несвязанных итераторов. Это обратная операция, и она примерно настолько же ошибкоемкая как прямая работа с указателями: да, если соблюдать осторожность? написать корректный код можно, но шанс наступить на мину очень велик.
Она ошибкоёмкая только в плохом коде, в котором и так вообще всё ошибкоёмкое.
Например тут:
class Foo
{
// only internals:typedef std::list<Bar> List;
List something
vector<List::iterator> chunks;
public:
// ...
};
вообще никак нельзя смешать итераторы из разных range'ей — опасность сильно преувеличенна.
Единственное зачем нужно следить — это добавлять итераторы в вектор в возрастающем порядке, но инварианты-то везде есть.
EP>>С тем же успехом можно вообще запретить все range/view — так как они могут протухать — и ни какой GC тут не спасёт. DM>В иных языках так и сделали — зафорсили иммутабельность. Корректность еще возрасла. Однако если в каком-то одном месте мы допустили возможность ошибок, это еще не повод плодить такие места дальше. Вопрос того, насколько язык помогает или мешает писать корректный код, он не черно-белый, не 1 или 0, тут есть градации. D тут ближе к корректности, чем С++, некоторые другие языки еще ближе.
auto myfind(Range, T)(Range r, T t)
{
size_t n = 0;
auto left = r.save;
while(!r.empty && r.front != t) {
r.popFront();
n++;
}
return tuple(left.takeExactly(n), r);
}
// versustemplate<typename I, typename T>
I find(I first, I last, const T& x)
{
while(first != last && *first != x)
++first;
return first;
}
В первом варианте даже не весь код показан — нет реализации takeExactly, нет костыля для строк и массивов, а во втором случае — это полный код. И корректность какого из вариантов легче достигается? По-моему очевидно
Да, при использовании только диапазонов нельзя смешать что-то совсем несвязанное — но толку от этого, если код алгоритмов распухает в разы?
Код в котором нет каких-то ошибок свойственных только итераторам, но не выполняющий основную свою основную функцию — не достигает постусловия (которые намного труднее достичь когда этого кода в разы больше) — никому не нужен.
EP>>Вот правильные слова (~4 минуты, [16m00s, 19m42s) ): DM>Да, очень правильные — при его дизайне с итераторами действительно нет возможности проверить, что два итератора относятся к одному списку. А подход с range эту задачу успешно решает. И в этом их большое преимущество.
На RandomAccessRange вылезают те же проблемы, только даже ещё хуже.
Как ты проверишь что индекс принадлежит правильному диапазону? В случае итераторов ещё можно включать проверки в debug — а с индексами что делать?
DM>Что до МТ и while, то можно и без полноты по Тьюрингу прекрасно программы писать, которые делают все что нужно и гарантированно не виснут. См. тот же ATS, а также Idris, Agda.
Согласен — специальные языки действительно полезны.
DE>без "import std.array;" работать не будет. То есть мы всё равно вынуждены подключать библиотеку. DE>Насчёт иметь в языке — мне не понятно чем стандартная библиотека хуже. Вот то, что С++ довольно долго не имел хеш таблиц стандартных — это, конечно, не здорово. Но эти времена прошли.
std.array — это как раз обёртка вокруг стандартных массив, для поддержки диапазонов (std.range), которые являются именно библиотечной конструкцией. К самим массивам это отношения не имеет. У массивов всегда есть просто test.length.
Мелкие замечания: круглые скобки после empty не нужны, а квадратные принято ставить после типа, а не переменной (хотя тут вообще auto хватило бы).
Здравствуйте, DarkEld3r, Вы писали:
DM>>Что до специального синтаксиса, то опыт популярных "высокоуровневых" языков вроде перла/питона/руби/похапе и пр. показал, что они во многом так удобны именно из-за наличия подобных структур данных сразу в языке, без необходимости подключения дополнительных библиотек. Это достаточно базовые вещи, чтобы иметь их в приличном языке сразу.
DE>Тут я немного не понял. Даже вот такая фигня:
test.empty(); DE>без "import std.array;" работать не будет.
Будет работать "test.length==0". empty — уже второстепенная функция, ей можно и в библиотеке побыть.
DE>Насчёт иметь в языке — мне не понятно чем стандартная библиотека хуже. Вот то, что С++ довольно долго не имел хеш таблиц стандартных — это, конечно, не здорово. Но эти времена прошли.
Теоретически — если нечто реализуется чисто библиотечно, то вся его логика должна быть в библиотеке, а когда это нечто встроено в язык, то о нем знает компилятор и может применять свою особую компиляторную магию для большей эффективности. Тот же foreach делать без лишних лямбд.
Only truly useful thing is to decompose your program into clear subroutines, clear units, which you understand. That is the only thing I know which works.
ARK>А вечные циклы теоретически можно и запретить. И так неизбежно и будет, с ростом мощи компиляторов. ARK>(Ну, останется 0,001% программ, где будет присутствовать циклы, доказать завершимость которых не удастся, такие программы напишут на Ц )
Алан Тьюринг недавно сказал, что у тебя такого компилятора не было и быть не может, и я ему верю
Рост мощи никак не решит halting problem. Разве что можно закрепить на законодательном уровне: "Наговнокодил? 15 суток!"
Здравствуйте, alex_public, Вы писали:
DM>>Если мы откуда-то пришли, значит мы там уже были и могли запомнить это место (.save), зачем туда опять пешком идти? _>Дело не в месте, а в направление. Итерация назад в варианте BidirectionalRange возможна только с конца. В то время как у нормального двусвязного списка с любого элемента.
Ну так если мы работаем не с итераторами, а с рэнджами, то к этому любому элементу мы можем прийти только оперируя рэнджем, а значит этот "любой элемент" и будет концом некоторого рэнджа. Неудобно лишь туда-сюда ерзать, но это и не должно быть удобно, такое ерзание — либо редкое извращение (для которого можно и специальный код написать), либо просто плохой алгоритм, для которого есть правильное решение в один проход.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>[q] EP>Only truly useful thing is to decompose your program into clear subroutines, clear units, which you understand. That is the only thing I know which works.
Да, это тоже очень важно. Но что важнее, статически доказанная безошибочность (конечно, только в плане отсутствия исключений, но не в плане соответствия ТЗ) или ясность кода — затрудняюсь сказать. ИМХО, в равной степени важно.
EP>Алан Тьюринг недавно сказал, что у тебя такого компилятора не было и быть не может, и я ему верю
Почему не может-то, уже есть примеры типа ATS или Perfect Developer, правда очень уж многословные и с весьма корявым синтаксисом.
EP>Рост мощи никак не решит halting problem. Разве что можно закрепить на законодательном уровне: "Наговнокодил? 15 суток!"
Ну вы же пишете код, который завершается? И обычно не испытываете затруднений в определении, где есть завершимость, а где нет.
Halting problem вполне можно решить статически в большинстве случаев. А там, где не решается — выкинуть такие случаи. Или написать на С.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>>>Или, например то, что по двусвязному списку нельзя пройтись в обратном направлении тому откуда мы пришли — это тоже вполне конкретная алгоритмическая инвалидность. DM>>Если мы откуда-то пришли, значит мы там уже были и могли запомнить это место (.save), зачем туда опять пешком идти? EP>Запоминать каждое состояние range которое мы посетили?
Зачем каждое? Какую задачу мы решаем?
Рэнджи и итераторы применяются для работы с контейнерами и ленивыми потоками данных. 99,5325371% реального кода с ними сводятся к iterate/filter/map/reduce/find, которые все работают в один проход. Желание ерзать итератором взад-вперед и итерировать UTF-8 строки задом-наперед — это что-то очень странное. Да, для таких странностей стандартная библиотека D может быть не очень годится, их можно делать руками, если очень хочется.
EP>Корректность достигается правильной декомпозицией: EP>auto myfind(Range, T)(Range r, T t) EP>// versus EP>template<typename I, typename T> EP>I find(I first, I last, const T& x) EP>[/ccode] В первом варианте даже не весь код показан — нет реализации takeExactly, нет костыля для строк и массивов, а во втором случае — это полный код. И корректность какого из вариантов легче достигается? По-моему очевидно
Ты уже несколько раз этот код цитировал. И пытался из результата своего find строить "первую часть" диапазона для однопроходного итератора. Т.е. действительно очевидно, что твой вариант больше подвержен ошибкам. Мы это уже обсудили, зачем повторять?
EP>Да, при использовании только диапазонов нельзя смешать что-то совсем несвязанное — но толку от этого, если код алгоритмов распухает в разы?
Если содержимое стандартной библиотеки распухает — мне не страшно. Зато пользовательский код, ее использующий, получается коротким и корректным. А вот с STL'ными итераторами он практически всегда пухлый и уродливый.
DM>>Да, очень правильные — при его дизайне с итераторами действительно нет возможности проверить, что два итератора относятся к одному списку. А подход с range эту задачу успешно решает. И в этом их большое преимущество.
EP>На RandomAccessRange вылезают те же проблемы, только даже ещё хуже. EP>Как ты проверишь что индекс принадлежит правильному диапазону? В случае итераторов ещё можно включать проверки в debug — а с индексами что делать?
Опять повторяемся. Еще раз спрошу: как обращение по произвольному индексу в случае итераторов может быть безопаснее, чем в случае ренджей?
И какую конкретно проблему ты имел в виду по той ссылке?
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Кстати, насчёт "опасных" итераторов — в общем случае takeExactly не делает проверок на empty: EP>void popFront() { _input.popFront(); --_n; } EP> Спокойно можно выйти за границы.
Если делать несколько раз popFront, не проверяя на empty? Ну так в пользовательском коде такой низкоуровневой работы не будет, а будет либо foreach, либо передача в другую функцию, потребляющую range. А в библиотечном коде это был бы баг, да, но маловероятный.
Здравствуйте, AlexRK, Вы писали:
EP>>[q] EP>>Only truly useful thing is to decompose your program into clear subroutines, clear units, which you understand. That is the only thing I know which works. ARK>Да, это тоже очень важно. Но что важнее, статически доказанная безошибочность (конечно, только в плане отсутствия исключений, но не в плане соответствия ТЗ) или ясность кода — затрудняюсь сказать. ИМХО, в равной степени важно.
Там где система типов может отловить целый класс ошибок, и не мешает при этом разработке — то естественно, почему бы не использовать.
Но если она ловит одни ошибки(да и то в редких случаях, причём которые без неё ловятся assert'ами), но тем самым заставляет писать на порядок больше кода — то это сомнительная выгода
EP>>Алан Тьюринг недавно сказал, что у тебя такого компилятора не было и быть не может, и я ему верю ARK>Почему не может-то, уже есть примеры типа ATS или Perfect Developer, правда очень уж многословные и с весьма корявым синтаксисом.
Пока нам доступна вся мощь МТ — в общем случае определить зациклится программа на входных данных или нет, не получится.
Если от этой мощи отказываемся — то вполне возможно.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Как ты проверишь что индекс принадлежит правильному диапазону? В случае итераторов ещё можно включать проверки в debug — а с индексами что делать?
Вообще то проверка границ у массивов в D встроенная. Правда по умолчанию она выключена (@system). Но легко включается или флагами компилятора на весь проект или спец.атрибутом (@trusted или @safe) прямо в коде.
Здравствуйте, alex_public, Вы писали:
_>std.array — это как раз обёртка вокруг стандартных массив, для поддержки диапазонов (std.range), которые являются именно библиотечной конструкцией. К самим массивам это отношения не имеет. У массивов всегда есть просто test.length.
Ок, теперь понятно.
_>Мелкие замечания: круглые скобки после empty не нужны, а квадратные принято ставить после типа, а не переменной (хотя тут вообще auto хватило бы).
auto как раз попробовал использовать, но тупо заменил им тип не убрав скобки после переменной и получил ошибку.
Здравствуйте, D. Mon, Вы писали:
DM>Будет работать "test.length==0". empty — уже второстепенная функция, ей можно и в библиотеке побыть.
Ну вот именно это разделение мне и не кажется логичным...
DM>Теоретически — если нечто реализуется чисто библиотечно, то вся его логика должна быть в библиотеке, а когда это нечто встроено в язык, то о нем знает компилятор и может применять свою особую компиляторную магию для большей эффективности. Тот же foreach делать без лишних лямбд.
Согласен, просто не уверен, что хеш таблицам надо именно в языке быть. Впрочем, это совсем не важный недостаток, если недостаток вообше.
Пользуясь случаем, спрошу — в студии при использовании вижуал Д никакого интелисенса нет. С этим ничего нельзя поделать?
Здравствуйте, alex_public, Вы писали:
_>Здравствуйте, jazzer, Вы писали:
J>>А вот если у тебя такая задача, каким бы был идиоматичный код на D?
_>Эм, я не знаю какой был бы идиоматичный код на D. Я в нём пока что совсем не спец., а так присматриваюсь понемногу. )))
J>>Есть массив целых чисел, нужно найти искомое число, потом отсчитать вниз 2 четных числа, а потом наверх 5 нечетных. J>>Т.е. для массива 1,2,3,4,5,6,7,8,9,10,11,12 мы находим 5, потом отсчитываем 2 четных числа вниз (4,2), потом 5 нечетных вверх (3,5,7,9,11) — ответ 11.
J>>Мне вот не приходит в голову, как такую задачу решать на диапазонах. А на итераторах все естественно.
_>
Не, ну это неинтересно, я надеялся код на диапазонах увидеть, а массив и индексы...
_>А на C++ ты бы какой код взял? )
Ну что-нть вроде такого (пишу в браузере)
template<class It, class Val>
It f25(It begin, It end, Val val)
{
auto found = find( begin, end, val );
auto even2 = prev(make_filter_iterator( is_even, found ), 2);
auto odd5 = next(make_filter_iterator( is_odd, even2.base() ), 4);
return odd5.base();
}
код будет работать с любыми двунаправленными итераторами — хоть массив, хоть двусвязный список...
Можно и честно через обратный итератор, если смущает "-2":
template<class It, class Val>
It f25(It begin, It end, Val val)
{
auto found = find( begin, end, val );
auto back_even2 = next(make_filter_iterator( is_even, make_reverse_iterator(found) ), 1);
auto odd5 = next(make_filter_iterator( is_odd, back_even.base().base() ), 4);
return odd5.base();
}
(1 и 4 — потому что началом считается первый, удовлетворяющий условию)
Здравствуйте, alex_public, Вы писали:
_>Вообще то проверка границ у массивов в D встроенная. Правда по умолчанию она выключена (@system). Но легко включается или флагами компилятора на весь проект или спец.атрибутом (@trusted или @safe) прямо в коде.
По умолчанию включена. Выключается ключиком -noboundscheck. Но речь выше не только про массивы шла.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Там где система типов может отловить целый класс ошибок, и не мешает при этом разработке — то естественно, почему бы не использовать. EP>Но если она ловит одни ошибки(да и то в редких случаях, причём которые без неё ловятся assert'ами), но тем самым заставляет писать на порядок больше кода — то это сомнительная выгода
Пока что все, кто переписывал что-то с С++ на D, сообщают об уменьшении размеров кода.
EP>Пока нам доступна вся мощь МТ — в общем случае определить зациклится программа на входных данных или нет, не получится. EP>Если от этой мощи отказываемся — то вполне возможно.
Это не "мощь", это просто свойство, отказавшись от которого, мы ничуть не теряем в "мощи" (кроме как "мощи" совершать глупости). Осмысленные алгоритмы вполне себе записываются на тотальных языках с проверкой завершимости.
Здравствуйте, D. Mon, Вы писали:
DM>Ну так если мы работаем не с итераторами, а с рэнджами, то к этому любому элементу мы можем прийти только оперируя рэнджем, а значит этот "любой элемент" и будет концом некоторого рэнджа. Неудобно лишь туда-сюда ерзать, но это и не должно быть удобно, такое ерзание — либо редкое извращение (для которого можно и специальный код написать), либо просто плохой алгоритм, для которого есть правильное решение в один проход.
Нее, даже на уровне диапазонов BidirectionalRange предоставляет недостаточную функциональность. Правда я даже не представляю как безопасно её можно вставить туда, хотя при этом структуры (типа DList) реализующие BidirectionalRange очень легко могут эту функциональность реализовать.
Например. Есть у нас BidirectionalRange r1. Делаем r2=r1.save. Далее, делаем итерацию r1 вперёд до какого-то элемента. Т.е. r1 у нас теперь задаёт часть r2. А теперь хотим получить BidirectionalRange на разницу между r2 и r1. Логичная же математическая операция, не так ли? ) Но такой у нас нет и в этом вся проблема. Если бы была, то можно было бы делать всё как и с итераторами.
Кстати, если говорить например про DList, то такую функцию довольно просто реализовать — проверить что оба диапазона родные и вернуть новый, с внутренними указателями (DList.Range хранит в себе всего лишь два указателя) из этих двух. Но это конкретно DList, а нам то надо это как функцию работы с произвольным BidirectionalRange...
Здравствуйте, D. Mon, Вы писали:
DM>Да, для таких странностей стандартная библиотека D может быть не очень годится, их можно делать руками, если очень хочется.
Так о том и речь, что для этого не годится. Странности это или нет другой вопрос. Вообще — всё для чего они не годятся можно назвать странностями
DM>Ты уже несколько раз этот код цитировал. И пытался из результата своего find строить "первую часть" диапазона для однопроходного итератора.
Я не пытался, это бессмысленно. Для однопроходного я пытался получить вторую часть — а у тебя там был .save(), который есть только у forward.
DM>Т.е. действительно очевидно, что твой вариант больше подвержен ошибкам. Мы это уже обсудили, зачем повторять?
В полном варианте find для range будет реализация takeExactly и костылей для RandomAccess и isSomeString — в итоге займёт строк сто, а в моём варианте их 7. Разве не очевидно что более подвержено ошибкам?
EP>>Да, при использовании только диапазонов нельзя смешать что-то совсем несвязанное — но толку от этого, если код алгоритмов распухает в разы? DM>Если содержимое стандартной библиотеки распухает — мне не страшно. Зато пользовательский код, ее использующий, получается коротким и корректным. А вот с STL'ными итераторами он практически всегда пухлый и уродливый.
Опять 25 Итераторы элементарно апргейдятся до range'ей, и код получается корректным, и доступ к мощи остаётся
DM>Опять повторяемся. Еще раз спрошу: как обращение по произвольному индексу в случае итераторов может быть безопаснее, чем в случае ренджей?
Я уже показывал примеры — как минимум в случае итераторов будет меньше переменных, и это безопаснее.
DM>И какую конкретно проблему ты имел в виду по той ссылке?
Здравствуйте, DarkEld3r, Вы писали:
DE>Пользуясь случаем, спрошу — в студии при использовании вижуал Д никакого интелисенса нет. С этим ничего нельзя поделать?
Какой-то есть:
Стоит зайти в его настройки (через Tools/Options/Text Editor/D), а также из его меню вызвать Build Phobos Browse Info.