Здравствуйте, vdimas, Вы писали:
V>Здравствуйте, samius, Вы писали:
DG>>>а разговоры о терминах — это всегда деструктивный разговор, не создающий нового знания. S>>Деструктивный разговор — это употребление общеизвестных терминов в недоступном для собеседника смысле. Я просто не пойму о чем ты разговариваешь. Слова знакомы, а суть противоречит тому что я знаю. Какого разговора ты хочешь без согласования терминов? О чем? Ты будешь говорить о своем, а я недоумевать, как такое возможно, думая о совершенно другом? S>>Если хочешь, что бы тебя понимали, нужно договориться с терминами.
V>Ну вообще, похоже ты давно понял, что речь идет о детерминированности.
Нет, до сих пор не понял. V>Однако я соглашусь с твоим оппонентом, что таки побочные эффекты зачастую нарушают детерминированность.
Зачастую — это не серьезно. Могут нарушать, а могут и не нарушать. V>Собственно, только в этом нарушении их и обвиняют, никаких других грехов им пока не приписывали. С другой стороны с этим "побочным эффектом" побочного эффекта (о как) успешно борются через локальность вычислений.
локальный побочный эффект не является побочным эффектом извне функции.
Вообще речь была об OrderBy и о том что нестабильность может сделать его нечистым. Я отвечал что что бы сделать его нечистым, или точнее недетерминированным, нужна не просто нестабильность, а нестабильность со случайным выбором порядка элементов с равным ключем.
Я могу согласиться с тем что OrderBy детерминирован лишь условно, с точностью не включая Object.ReferenceEquals, и возможность влиять на поведение результирующего перечислителя через исходную последовательность. Но если мы уж назвали OrderBy чистым, значит мы закрыли глаза на эти косяки.
Но причем же тут побочный эффект? Где побочный эффект у OrderBy? Где то, что соответствует определению побочного эффекта в OrderBy? Без согласования терминов ответить однозначно невозможно. Ведь DarkGray называет побочным эффектом просто отсутствие стабильности сортировки.
Здравствуйте, vdimas, Вы писали:
V>Угу, кто тебя спросит. Если несколько процессов или потоков от независимых либ делят одну консоль, то там получается занятная каша в любом случае, бо нам состояние консоли недоступно и мы даже не в состоянии организовать "атомарный" доступ к ней.
Вам — это кому? Вас занесло не в ту степь. По-вашему, выходит, что писать осмысленные программы на С вовсе нельзя — ведь даже положиться на то, что консоль выводит данные в определённом порядке невозможно. Однако, практика показывает, что программы такого рода вполне себе пишутся, и каким-то волшебным образом функция printf выводит данные в stdout строго в одном, нужном нам порядке. Каким же волшебным образом это происходит, не подскажете?
V>Ну это легко, если договориться о том, что есть "запрещает". Давай считать, что это означает потерю детерминированности для эквивалентного конечного автомата.
Какого конечного автомата? V>Если некий другой поток меняет состояние автомата в моменты работы ф-ии, то результат ее недетерминирован. Если ф-ия при повторном вхождении затирает предыдущее состояние собственного незавершенного вызова, то результат предыдущего вызова будет недетерминирован.
Как интересно. Давайте тогда уж условимся о том, что считать результатом функции. То, что она возвращает через return, или состояние некоего "вычислителя", разделяемого между всеми функциями? Если первое, то, конечно же, функция, хоть как-то работающая с разделяемым состоянием у нас сразу потеряет детерминистичность. Даже если у неё нет никаких побочных эффектов.
А если второе — то нам вопросы детерминированности результата отдельной функции становятся, в общем-то, малоинтересны. Вместо них мы введём понятие сериализуемости, через которое определим корректность. И сразу же окажется, что функции с побочными эффектами станут совершенно спокойно реентерабельны и потокобезопасны.
V>Я исхожу и того, что доказать на уровне компилятора не так-то сложно. Ведь работает как-то же линковщик, ресолвя абсолютно все до одной зависимости.
Линковщик резолвит не те зависимости.
V>Функциональная тоже опирается на некий контекст, который разный в разных точках вычисления.
Этот "контекст" в ФП не имеет никакого отношения к состоянию вычислителя. Это всего лишь правила связывания аргументов.
V>Доступный тебе из твоей программы из используемого языка.
Из программы на C доступно довольно много всего про состояние императивного вычислителя.
V>Сам Lazy<T> — это один сплошной побочный эффект. Всё преобразование заключается в запоминании состояния в точке вычисления.
Поэтому он императивен. Дальше что?
V>Один из них, Console, все время передается выше как результат предыдущей операции.
И тем не менее, порядок вычисления "вторых" узлов неважен, если вычисления не имеют побочных эффектов.
V>Нет, я имел ввиду показанный тобой случай.
Значит, вы чего-то не понимаете.
V>Она декларативна, угу, но лишь по отношению к уровню, который будет ее реализовывать. Это ты зашел на очередной круг.
Нет.
V>Это от того, что ты рассматриваешь лишь один join из 6-ти возможных, постоянно скипая зачем-то мой ответ тебе на один и тот же вопрос. Похоже на какое-то юление.
Это вы юлите. Вы мне тут только что утверждали, что equi-join будет стоить O(N*M) для случая, когда объём данных много больше объёма ОП, и ни один из результатов не отсортирован. Я вам показал что нет, ничего подобного. Теперь вы опять пишете мне, что имели в виду join по произвольному выражению (тогда причём тут сортировка?), а когда я напишу вам, что это — редкий случай, вы опять станете передергивать и делать вид, что речь идёт о соотношении объёма данных и памяти. Так что ли?
Ок, тогда давайте вернёмся к тому, с чего всё начиналось. Вы мне утверждали, что
если некая соединительная операция из 3-х (грубо) составляющий выполняется в 4 раза быстрее, что каждая в среднем стала выполняться быстрее в корень 3-й степени из 4.
Вы какие именно соединительные операции здесь имели в виду? Неужели в вашем проекте все соединения были по произвольной функции, и размер результата был примерно равен кросс-продукту? Как же вы тогда ускорили их путём применения индексов?
V>Вот это открытие... А как же так получилось?
Очень просто: логические чтения считают все обращения к кэшу страниц. Если происходит cache miss, то приходится реально выполнить физическое чтение.
V>Реальный IOPS, слава богу, от тебя мало зависит. Иначе бы у тебя было максимум 70 обработанных экстентов в секунду, а их, однако, многие тысячи. Спасибо кешу операционки.
Вы опять возвращаетесь к предположению о том, что СУБД пользуется кэшем операционки. Это далеко не всегда так — я вам об этом уже писал. Приличные СУБД не полагаются на тупой кэш операционки и отключают его, чтобы не мешал. Для выяснения этого факта даже исходники читать не надо.
V>Мой идиотизм — это в плане заблуждений относительно разметки страниц твоей любимой СУБД? Ты бы поосторожнее с такими вещами, бо они сами по себе тебя подставляют.
Вам полный список привести? Пожалуйста, мне нетрудно:
1.
фиксированные размеры страниц нужны исключительно для нужд кластерных индексов, которые принципиально живут только в контексте детерминированных размеров
Нет, кластерным индексам детерминированность размера данных совершенно неважна
2.
Кластерный индекс хорош лишь там, где seek по всем данным в процессе двоичного поиска относительно дешев. Т.е. когда размеры таблицы заведомо меньше размера ОП
Нет, кластерные индексы прекрасно работают и там, где размеры таблицы много больше размера ОП.
3.
линейка от 6-ки до MS SQL 2000 была в своё время изучена настолько подробно, насколько это вообще возможно, включая местами исходники.
Это вы просто соврали — потом, правда, поправились, что изо всей линейки читали исходники только 6го сервера. Хотя видно, что насчёт "насколько это вообще возможно" — мягко говоря, преувеличение.
4.
Если для некластерного у меня получалось получалось 1-2 страницы, для не самой большой таблицы, то для случае этого же индекса как кластерного — легко десяток-полтора сканированных страниц ради одного значения.
Вот ещё одно вранье. Сканирование полутора десятков страниц для одного значения, даже в случае самой широкой таблицы, требует примерно 10 в 36 степени записей. Мне лень считать, о каких объёмах собственно данных тут может идти речь.
5.
Для случая вставки в кластерный индекс всегда трудоемкость минимум O(n), помимо операции обновления дерева индекса
Нет, стоимость вставки в кластерный индекс без учёта стоимости обновления дерева — O(1), с учётом — O(log N).
6. Рассуждения о стоимости Join-ов — можете посмотреть выше.
Эти ошибки смотрелись бы нормально, если бы не подавались с таким апломбом и предположениями, что я вообще базы данных видел только на картинке, а вы якобы рассмотрели всё вплоть до исходников.
V> Находясь на твоей стороне спора, я бы это вычислил в одну итерацию, что и делаю регулярно с твоими заблуждениями, а тебе потребовался примерно десяток.
Чтобы находиться на моей стороне спора, нужно разбираться в вещах, о которых идёт спор
V>В том то и дело, что не будут такие же. Там тупая формула по статистике, а вид операции для оценки уже не важен, бо весовая ф-ия не оперирует видами аналитик, она оперирует абсолютными значениями на выходе весовых ф-ий. Вся аналитика остается на этапе составления весовых ф-ий и больше ее не будет.
Ок, напишите эту тупую формулу.
V>Мде? А мне показалось, что ты из всех операций join подразумеваешь только одну. И на основе этого хочешь поставить мне тройку.
Вы хотите и про другие виды join поговорить? Давайте сначала разберёмся с самым простым случаем. Потом можно будет перейти к остальным, если у вас ещё останется желание со мной поспорить.
V>Хороший бы вышел из тебя преподаватель, нечего сказать. Был у нас такой один, требовал чтобы отвечали как он давал иначе сразу трояк. А если дашь более общий вид формулы — вообще выгнать может.
Ну, если формула неверна, то правильно сделает.
V>Таки в том посте я давал не интерпретацию, а именно что наблюдения. Относительно ширины данных и их кол-ва. А предположение о фиксированности размера записей откуда взялось? Из dBase III?
V>Из твоих рекомендаций этого не видно вообще. Просто дело в том, очевидно, что слишком много всяких эффектов влияют на производительность. К тому же, хорошо известно, что не всякий алгоритм лучший в терминах O на бесконечно большом объеме данных даст лучшие показатели на малых объемах. Тут уже нужна оценка снизу. А оценка снизу обычно на многие порядки сложнее асимптотики предела сверху.
Ок, то есть вы хотите перейти обратно к примеру, когда данных мало и они целиком влезают в ОП? Ну давайте поговорим об этом.
V>Скажем так, я видел много разных кластерных индексов до MS SQL, и прекрасно понимал, в чем их цимус.
Я не знаю, что вы имеете в виду под словом "цимус", но судя по вашим репликам в этой ветке вы всё-таки смешали особенности конкретной реализации кластерных индексов с общим понятием "кластерный индекс". Отсюда смешные предположения про их характеристики в MS SQL.
V>Ну так согласно доке, сервер старается поддерживать равномерное заполнение кластерного индекса. Т.е. мало выделить +1 страницу, надо еще данные в ближайших таблицах распихать. Если ты не прочитал целиком в том месте, самое время вернуться и освежить. Боюсь, что вернуться и освежить придётся именно вам.
1. Сервер не старается поддерживать равномерное заполнение кластерного индекса. Это было бы глупо.
2. Что вы называете "распихать"? Никакого распихивания не происходит — просто страница сплитится на две. Половина данных попадает в одну, половина — в другую. Это позволяет снизить амортизированную стоимость вставки, т.к. последующие вставки в эти же страницы не будут приводить к сплиту.
V>Да, если можно. Хотя не надо, мне надоели бесконечные итерации, лучше я расскажу, чтобы не растягивать. Вот прямо здесь ты пропустил важный пункт — это выпрямление кванторов общности и кванторов существования в исходном запросе.
Это вы про замену Exists и All на join? Ну, это же не всё — такие же вещи происходят с in и вложенными запросами. V>В этом и заключается построение логического плана запроса.
V>MS SQL тормозит в сравнении с файловыми базами далеко не всегда. Он сливает им только на простых операциях, типа выборки из одной, максимум двух таблиц по натуральному join. Зато когда идут вложенные кванторы, да еще с разными перекрестными зависимостями/ограничениями на разных уровнях... то на движке JET приходится по десятку раз переформулировать один и тот же запрос, крутя его граф во все стороны, чтобы получить приемлемую эффективность, а MS SQL стабильно дает почти один и тот же план запроса, невзирая на формулировку. Ему даже join писать не надо, пиши таблицы через запятую, он сам разберет, а JET в этом месте просто уйдет в глубокий своп.
Верно.
V>Так вот, логических планов запросов тоже несколько, после выпрямления всех кванторов, т.е. после сведения их ко всяким пересечениям, произведениям и ограничениям.
И чем отличаются логические планы друг от друга?
Итого, идет как минимум два уровня перебора вариантов. А далее можно как в классике, например как в теории игр использовать оценочный аппарат с отсечением — ничего нового. Я потому и отбрасываю конкретный вид оценочной ф-ии, что она не принципиальна в после установления к какому классу сложности относится конкретное вычисление и какой аппарат использовать. Вряд ли ошибусь, если предположу использование такого раздела нечеткой логики как теория приближенных вычислений (бо статистика почти всегда врет, если не только что пересчитали, т.е. стоит задача выдавать решение в этих условиях).
S>>3. Начинается построение физического плана запроса: S>>3.1. Порождаются различные версии физического плана. Они похожи на выражения РА, вот только в аргументах у них немножко другие объекты, чем отношения, и операции немножко другие, чем в РА
V>Это атрибут физической модели и прямиком может топать как параметр в некую ф-ю оценки. РА здесь не при чем. По конкретной таблице есть требуемая операция в терминах РА — выборка / проекция / ограничение. Никаких других операций над конкретной таблицей НЕТ.
Куда делась сортировка?
S>>3.1.2. В отличие от РА, для операций важны применяемые алгоритмы — это влияет не только на оценку стоимости, но и на отсортированность результата V>Это опять ты оперируешь атрибутами физической модели. Атрибут для каждой конкретной структуры является константой, а для оценочной ф-ии — параметром.
Это не я, это сервер оперирует.
S>>Вы, пытаясь доказать свои заблуждения, выделяете фазу генерации вариантов планов запросов в отдельный этап. Ок, даже если бы это было так, всё равно РА было бы недостаточно.
V>Таки итерация планов запросов — это несомненно самый сложный и затратный этап.
Всё правильно. И уже на ней "просто РА" недостаточно. То, что вы продолжаете называть "атрибутами физической модели" является необходимым компонентом. Выбросьте эти атрибуты — и алгоритм перебора перестанет работать.
V>Тебе не нужен никакой sort на уровне PA, тебе нужно только обозначить вид соединения, а уже низлежащий слой пусть примет решение, исходя из прогноза по данным — будет он строить индекс, или и так пойдет.
Нет. Никакого "низлежащего слоя" нету — в физическом плане запроса указаны конкретные физические операции. Для их выбора нужно знать, что и как. Если в узле A мы выбрали merge join, то результат отсортирован по ключу, и в узле B, где мы джойним C с A, мы можем применять merge join или index nested loops join. И копать или нет дальше в эту сторону — принципиальный вопрос.
V>Я вижу, что включение в план запроса, наглядности ради, подробностей операций, просто сбивает тебя с толку. Понимаешь, породить sort из задачи join — не нужен вообще никакой специальный мат-аппарат, просто некое пороговое значение кол-ва элементов из оценки статистики, и решение да/нет — строим индекс или не строим.
Как интересно. То есть вы каким-то волшебным образом разделяете алгоритм построения физического плана на некоторые фрагменты, и произвольным образом называете одни из них "мат-аппаратом", а другие — нет? Это, несомненно, новое слово в построении запросов.
V>Если ты про ту, где отметился Ульман в соавторстве — то это не самая лучшая ссылка. И таки принято автором считать Ульмана, а остальную братию в соавторстве. И таки хотелось бы узнать, на что именно ты там пытался сослаться? На какой раздел?
На второй. Там, где про собственно реализацию.
V>Если ты опять и снова имеешь ввиду атрибуты физической модели, то они всегда представлены набором неких констант для целей оценки.
Да, я имею в виду "атрибуты физической модели". Благодаря которым оптимизатор знает, что индекс I1 по таблице T1 связан с этой таблицей. Именно благодаря этому оптимизатор вообще рассматривает варианты планов, включающие этот индекс, даже если вы ему явно об этом не сказали. А вот если вы построите свой "индекс" вручную — ну, например, как вы это называли "обыграете индекс при помощи отдельного отношения", оптимизатор не станет рассматривать его использование. Несмотря на наличие зависимостей, которые с точки зрения реляционной модели ничуть не хуже тех, что у "настоящего" индекса
S>>Как вы думаете, каково будет соотношение Thdd/Tram?
V>Если в затратах проца, то в первом случае когдаздо экономнее, чем во втором. Операции с файловой системой тривиальны алгоритмически, остальное делается само через DMA. К тому же, прокачка через DMA не портит кеш процессора, в отличие от операций копирования, да и на современном рейде суммарная буферная емкость даже в винчестерах уже ощутима. В общем, перелопачивать "вручную" данные весьма накладно. Ты так и не понял замечание про 1 всего измененный байт.
Я всё прекрасно понял. Напишите экспериментальную программу и мы легко убедимся, что я неправ.
V>Тем не менее, если низлежащая файловая система транзакционна, то можно было бы это учесть... тем более, в рамках одной конторы. Оракл не постеснялся специально под себя разработать файловую систему, а глядя на MS SQL такое ощущение, что правая рука не знает что делает левая в MS.
У MS была своя файловая система. Начиная с версии 7.0 они дропнули поддержку raw disks, потому что стоимость была высока, а выхлоп — никакой. Оракл просто многоплатформенный, у них не было возможности оптимизироваться под конкретную ФС (если не написать свою).
S>>"Мои екстенты" были, естественно, применены для оптимизации алгоритма поиска свободных страниц при размещении. Ну и для того, чтобы повысить шансы на последовательное чтение — мы это уже обсуждали.
V>Там вся оптимизация заключается в уменьшении кол-ва операций ввода-вывода, а ничего другого, кроме как укрупнять блоки, тут не придумаешь.
Если вы про оптимизацию выполнения запросов — кроме укрупнения блоков есть ещё много техник. Те же индексы разных видов. Тем более, что страница всё ещё 8к. V>А у этого подхода есть обратная сторона в избыточности копирований тем большей, чем крупнее блоки.
V>- Не было столько памяти, сколько сейчас; V>- не было таких технологий оптимизации ввода-вывода на уровне операционки, в условиях большей доступной памяти, как сейчас;
Это каких например? V>- ввод-вывод был узким звеном, а сейчас некоторые рейды способны выдавать и принимать быстрее, чем поспевают обрабатывать топовые процессоры.
Тем не менее в жизни мы наблюдаем отличны рост скорости процессоров и памяти, умеренный рост скорости линейного чтения с дисков, и очень слабый прогресс в IOPS. Только SSD несколько нарушают эту тенденцию. Однако вот, к примеру, команда Microsoft Exchange по-прежнему оптимизирует нагрузку на диск в терминах IO operations. То есть в ближайшие четыре года они не ожидают массового перехода на SSD.
V>Для сравнения, если раньше даже на более слабом проце при компиляции С++ у меня редко было более 50% загрузки проца, бо он "отдыхал" на ввод-выводе, то сейчас при куда как более мощном многоядерном проце у него заметно выше загрузка! Более 75% стабильно, а это уже ого разница.
Как интересно вы рассказываете. "Раньше" — это когда? Есть у меня подозрение, что просто с тех пор переписали компилятор, и он стал поддерживать многоядерность. Большинство старых компиляторов — однопоточные, так что на двухядернике больше 50% не получишь, даже если весь проект в кэше лежит.
V>Для MSVC V>http://msdn.microsoft.com/en-us/library/8wtf2dfz(VS.90).aspx
Осталось продемонстриовать, как эта опция поможет выкинуть исключение из вот такого кода:
int EpicFail(int a)
{
return a+1;
}
...
var a = EpicFail(MAX_INT);
V>Для GCC лучше поясню, а то из доки с непривычки будет непонятно: V>-ftrapv V>-fnon-call-exceptions V>Два этих параметра надо одновременно. Без второго первый не выбросит исключение.
Эти параметры помогут поймать багу в коде выше?
V>Дык, RSDN-тим или как? Я бы и сам подправил давно уже, там дел на несколько минут.
Я не занимаюсь веб-мордой. Те, кто занимается, эту ветку не читают. V>Я не отрицаю границ.
Ну и слава байту. Наконец-то договорились.
V>Кароч, примеров-то можно привести много... Но суть одна, если взять все знания из области IT, то ты получишь граф из довольно счетного кол-ва узлов, но огромного кол-ва связей м/у ними. Увидеть "четкую границу" можно лишь при невладении целыми кластерами таких узлов... в этом месте будет космический вакуум и несколько световых лет до следующего знакомого кластера узлов. Даже по обсуждаемому вопросу: пройдись по теории сложности, теории игр, линейному программированию, АИ, нечеткой логике и т.д. Потом попробуй "четко отделить" задачу оптимизации плана запросов от этих разделов. С удовольствием запасусь попкорном и понаблюдаю за этими попытками.
А чего тут пробовать? Нужно просто понимать, где в решениии что берётся откуда. И не путать божий дар с яичницей.
V>Ммм... да вроде поразрядную арифметику как раз в школе и изучают, если склероз не изменяет, где-то в 1-м классе... Оно уже в куче by design.
Нет. Первое упоминание чисел с ограниченной разрядностью в школе входило (в моё время) в учебник информатики за 11 класс. В первом-втором классах учат натуральным числам, которые могут быть бесконечной длины. И нигде в школе (кроме той же информатики мельком) не упоминается ничего похожего на целое переполнение. V>Кластерный индекс — он и в африке кластерный. Для меня явилось лишь неожиданностью нефиксированный размер строки. Это минимум вдвое проседание выборки из страницы из-за +1 к косвенности.
Если бы вы реально работали с настоящими базами данных, то вы бы знали, что CPU-cost на чтение данных из страницы пренебрежимо мал по сравнению со стоимостью дисковых операций.
S>>Из-за этого возникают предположения типа "вставка в кластерный индекс требует O(N) записей на диск", и принимаются неверные архитектурные решения. V>Именно так? А можно цитату целиком?
Я привёл выше. №5 в списке глупостей.
S>>И вот тут ключ к успеху — понимать, какие свойства относятся к чему. К примеру, "использование более одного индекса с низкой селективностью при поиске в одной таблице дороже, чем сочетание index seek с bookmark lookup и filter" как правило работает в случае хеш-индексов и btree-индексов. А вот для случая bitmap-индексов это полностью неверно.
V>А еще можно не плодить битмап-индексы и таки не бояться явной избыточности, зато организовать себе кластерный индекс по нужному полю/полям.
Можно. Но для принятия верного решения надо знать особенности конкретных архитектур, и не делать неверных предположений.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
S>Но причем же тут побочный эффект? Где побочный эффект у OrderBy? Где то, что соответствует определению побочного эффекта в OrderBy? Без согласования терминов ответить однозначно невозможно.
согласовывать необходимо сначала задачи, потом условия(границы) и только потом термины.
можно долго согласовывать термин "маленький", но без задачи и условий — это будет не о чем. и тоже самое с большинством других терминов.
S> Ведь DarkGray называет побочным эффектом просто отсутствие стабильности сортировки.
из эквивалентности кода следует, что и проблемы эквиваленты.
mutable-программу можно один в один переписать в immutable (в чисто функциональный подход), когда каждая функция заменяется на такую же (но чистую), берущую весь мир и возвращающую весь мир. при этом побочный эффект из mutable-программы в один в один перейдет в побочный эффект функций в immutable-программе
побочный эффект появляется при решении задачи:
возможность вызывать только тот код, который необходим,
или другими словами:
возможность переставлять функции в коде,
заменять функцию на ее значение и т.д.
и соответственно утверждается, что побочным эффектом называется один из видов херотени, которая мешает выполнять эти операции
возьмем код:
class C
{
public int X = new Random().Next();
public int Y = 0;
}
int F1(int y)
{
c.X++;
return y - c.X + c.Y;
}
int F2(int y)
{
c.Y--;
return y + c.X + c.Y;
}
int F0(int y1, int y2)
{
return y1 + y2 + (c.X < 0 ? -c.X : c.X);
}
static C c = new C();
void main()
{
var x1 = F1(F2(F1(F1(F1(7)))));
var x2 = F2(F1(F1(F2(F2(24)))));
Console.WriteLine(F0(x1, x2));
Console.WriteLine(x1);
Console.WriteLine(x2);
}
можно ли здесь переставить местами или заменить на значение, хоть одну функцию? нет почему? сплошные побочные эффекты по определению
заменим на эквивалентный чисто функциональный код:
class C
{
public C(int x, int y = 0){this.X = x;this.Y = y;}
public C(){this.X = new Random().Next();}
public readonly int X;
public readonly int Y;
}
class World
{
public int y;
public C c;
}
World F1(World w)
{
C c = new C(w.c.X + 1, w.c.Y);
return new World{c = c, y = w.y - c.X + c.Y};
}
World F2(World w)
{
C c = new C(w.c.X, w.c.Y - 1);
return new World{c = c, y = w.y + c.X + c.Y};
}
World F0(int y1, int y2, C c)
{
return new World{c = c, y = y1 + y2 + (c.X < 0 ? -c.X : c.X);};
}
void main()
{
C c = new C();
var w1 = F1(F2(F1(F1(F1(new World{c = c, y = 7})))));
var w2 = F2(F1(F1(F2(F2(new World{c = w1.c, y = 24})))));
var w3 = F0(w1.y, w2.y, w2.c);
PutLine(w3.y) >>= PutLine(w1.y) >>= PutLine(w2.y);
}
можно ли в этом в чистом функциональном коде переставить местами или заменить на значение, хотя бы одну функцию? нет. почему? потому что вся таже зависимость от побочного эффекта
единственная разница этого кода от предыдущего, что в предыдущем коде зависимость по побочному эффекту между x1 и x2 была неявной для ЯП и программиста (и ее необходимо было восстанавливать из кода), а здесь эта зависимость записана явна.
деление на декларивный и императивный код появилось на заре становления программирования при решении задачи: может ли меняться код исполнения при той или иной записи программы? и в какой степени?
пока не было оптимизирующих компиляторов деление было более-менее четкое:
пролог, sql — декларативные: исполнитель делает что хочет;
а асм, алгол, форт, паскаль, си — императивные: исполнитель делает то, что записано в коде, в том порядке в котором записано.
как появились оптимизирующие компиляторы — императивные языки перестали быть четко императивными, в них появилась декларативность: исполнитель в большинстве случаев стал выполнять другой код и в другом порядке, чем записано.
дело дошло даже до того, что маш. код перестал быть чисто императивным: современный процессор его выполняет в другом порядке, и другим способом чем записано
и наоборот, по мере стандартизации де факто реляционных баз — от большинства простого sql-кода стало ожидаться, как именно он будет исполняться (в каком порядке какие выборки будут делаться, какие индексы будут использоваться и т.д.)
и sql перестал был четко декларативным: от конкретной реализации СУБД (тем более конкретной версии) ожидается, что sql-запрос будет выполняться строго заданным способом, и никак иначе.
соответственно, сейчас дискуссия о том является ли конкретная запись декларативной или императивной — это дискуссия ни о чем:
сейчас многое зависит от исполнителя (мощности его анализатора кода и возможностей его выполнения) — и без фиксирования исполнителя нельзя утверждать — этот код декларативный или императивный. а если зафиксирован исполнитель, то прежде чем говорить чего больше: декларативности или императивности необходимо сначала зафиксировать метрику — в каких единицах и каким способом измеряется декларативность или императивность.
при этом можно говорить, что такая запись более декларативная/менее императивная без явной фиксации исполнителя, если при этом измеряется какую степень свободы для исполнения дает та или иная запись; или если сравнивается мощность анализатора исполнителя, чтобы исполнитель мог получить ту или иную свободу исполнения, для той или иной записи кода.
S>>Но причем же тут побочный эффект? Где побочный эффект у OrderBy? Где то, что соответствует определению побочного эффекта в OrderBy? Без согласования терминов ответить однозначно невозможно.
DG>согласовывать необходимо сначала задачи, потом условия(границы) и только потом термины.
Ты пришел и сказал что OrderBy имеет побочный эффект. К чему, по какому поводу — осталось загадкой.
DG>можно долго согласовывать термин "маленький", но без задачи и условий — это будет не о чем. и тоже самое с большинством других терминов.
S>> Ведь DarkGray называет побочным эффектом просто отсутствие стабильности сортировки.
DG>из эквивалентности кода следует, что и проблемы эквиваленты.
Вот это опять к чему?
DG>mutable-программу можно один в один переписать в immutable (в чисто функциональный подход), когда каждая функция заменяется на такую же (но чистую), берущую весь мир и возвращающую весь мир. при этом побочный эффект из mutable-программы в один в один перейдет в побочный эффект функций в immutable-программе
Я не понимаю, к чему это, потому комментирую содержимое. Один в один — это вряд ли. Перейдет в побочный эффект чистой функции — тут ты опять забыл посмотреть определения побочного эффекта и чистой функции.
DG>побочный эффект появляется при решении задачи: DG> возможность вызывать только тот код, который необходим, DG>или другими словами: DG> возможность переставлять функции в коде, DG> заменять функцию на ее значение и т.д.
Побочный эффект появляется как средство достижения целей при решении совершенно разнообразных задач. Я все еще не понимаю смысл, который ты вкладываешь в побочный эффект.
DG>и соответственно утверждается, что побочным эффектом называется один из видов херотени, которая мешает выполнять эти операции
Утверждается что этот вид хрени называешь побочным эффектом только ты.
DG>возьмем код:
DG>можно ли здесь переставить местами или заменить на значение, хоть одну функцию? нет почему? сплошные побочные эффекты по определению
Да, в нем много побочных эффектов по определению.
DG>заменим на эквивалентный чисто функциональный код: DG>
DG>class C
DG>{
DG> public C(){this.X = new Random().Next();}
DG> public readonly int X;
DG> public readonly int Y;
DG>}
DG> ...
DG>void main()
DG>{
DG> C c = new C();
DG> ...
DG>}
DG>
Этот код не является чисто функциональным, т.к. использует недетерминированные функции.
Ты молоток, написал кучу кода. Но совершенно зря. Твои выводы ничего не стоят, т.к. используют термины, смысл которых очевидно искажен. Чистота — еще один термин, который ты толкуешь как-то по-своему.
Здравствуйте, DarkGray, Вы писали:
DG>деление на декларивный и императивный код появилось на заре становления программирования при решении задачи: может ли меняться код исполнения при той или иной записи программы? и в какой степени?
Сам придумал? Если нет — дай ссылку.
DG>пока не было оптимизирующих компиляторов деление было более-менее четкое: DG>пролог, sql — декларативные: исполнитель делает что хочет;
Т.е. ты признаешь что sql когда-то был декларативным... Хорошо.
DG>а асм, алгол, форт, паскаль, си — императивные: исполнитель делает то, что записано в коде, в том порядке в котором записано.
DG>как появились оптимизирующие компиляторы — императивные языки перестали быть четко императивными, в них появилась декларативность: исполнитель в большинстве случаев стал выполнять другой код и в другом порядке, чем записано. DG>дело дошло даже до того, что маш. код перестал быть чисто императивным: современный процессор его выполняет в другом порядке, и другим способом чем записано
DG>и наоборот, по мере стандартизации де факто реляционных баз — от большинства простого sql-кода стало ожидаться, как именно он будет исполняться (в каком порядке какие выборки будут делаться, какие индексы будут использоваться и т.д.) DG>и sql перестал был четко декларативным: от конкретной реализации СУБД (тем более конкретной версии) ожидается, что sql-запрос будет выполняться строго заданным способом, и никак иначе.
Покажи мне способ строго задания sql запроса!
DG>соответственно, сейчас дискуссия о том является ли конкретная запись декларативной или императивной — это дискуссия ни о чем: DG>сейчас многое зависит от исполнителя (мощности его анализатора кода и возможностей его выполнения) — и без фиксирования исполнителя нельзя утверждать — этот код декларативный или императивный. а если зафиксирован исполнитель, то прежде чем говорить чего больше: декларативности или императивности необходимо сначала зафиксировать метрику — в каких единицах и каким способом измеряется декларативность или императивность.
А ты можешь назвать хоть один не императивный исполнитель sql? Хотя бы тот, который якобы был на заре становления программирования, когда sql еще был (по твоем рассуждениям) декларативен? Или тот, который (по рассуждениям vdimas-а) нельзя было бы выполнить на машине Тьюринга?
DG>при этом можно говорить, что такая запись более декларативная/менее императивная без явной фиксации исполнителя, если при этом измеряется какую степень свободы для исполнения дает та или иная запись; или если сравнивается мощность анализатора исполнителя, чтобы исполнитель мог получить ту или иную свободу исполнения, для той или иной записи кода.
Напомни, каким образом исполнитель связан с определением декларативности, если ты в него заглядывал?
Если ты о какой-то своей декларативности (как и о чистоте, побочных эффектах и т.п.), то я умываю руки.
S>Этот код не является чисто функциональным, т.к. использует недетерминированные функции.
если уж делаешь какие-то утверждения, то делай это правильно и четко.
твоя проблема, что ты умудряешься даже для железобетонных определений делать ужасные формулировки своих утверждений.
точная формулировка: функция конструирующая тип C не является чисто функциональной, т.к. использует недетерминированную функцию new Random().
остальные функции являются чисто функциональными и детерминированными.
и соответственно, как только ты бы сделал правильное и четкое утверждение, то скорее всего до тебя бы дошло, что тебе показывают и тебя просят подумать про ту часть кода, которая состоит из чисто функциональных детерминированных функциях.
вторая проблема, что ты считаешь собеседников заведомо глупыми. и любую неточность в формулировках ты трактуешь в пользу глупости собеседника, вместо того, чтобы самостоятельно устранить неточность и ответить по существу. при этом ты бы чему-то научился (и это был бы конструктивный подход), а так ты лишь чешешь свое самолюбие.
S>Этот код не является чисто функциональным, т.к. использует недетерминированные функции.
Это ты про Random()? А разве нет его в ФП языках? В примере была демонстрация того, о чем мы тут говорим по всей ветке, забей ты на этот на Random, это уже просто придирки...
Дело в том, что современные компиляторы давно способны устанавливать все зависимости, именно это и позволяет им заниматься оптимизацией и спекулятивным выполнением. И я пока не видел ни разу, чтобы компилятор ф-ого языка оптимизировал лучше, чем компилятор императивного, невзирая на все рассуждения о потенциальной мощи оптимизируемости чистого кода. Это все наши суеверия, честно говоря. Компилятор способен оперировать зависимостями на многие порядки превосходящими по сложности наши возможности, поэтому аргументы из разряда "вот здесь заввисимости идут явно, а тут неявно" — просто нелепы для современных компиляторов. показанный код — это лишь малюсенький пример эквивалентных преобразований кода, которые давно способны выполнять современные компиляторы.
S>Ты молоток, написал кучу кода. Но совершенно зря. Твои выводы ничего не стоят, т.к. используют термины, смысл которых очевидно искажен. Чистота — еще один термин, который ты толкуешь как-то по-своему.
Дык более половины встреченных определений "чистоты" неполны. Многие из них вообще говорят о каких-то глобальных переменных, о вводе-выводе и прочий бред... А если у нас нет в языке глобальных переменных? В общем, более нелепого определения чистоты ф-ий, чем в Вики, я еще не видел, так что не мечи тут молнии.
Чистота — это отсутствие неявных зависимостей и ничего более. Зачем она вообще нужна? Детерминированности ради. Чистота ведь не самоцель ни разу, а лишь ср-во обеспечения детерминированности. Вернее, одно из ср-в, хотя и самое дешевое из всех. Дешевое в разработке, ес-но... бо в исполнении чистые программы пока ничего дешевого не показывают, скорее наоборот. ИМХО, самое дешевое ср-во обеспечения детерминированности на сегодня по всем показателям суммарно — это локальность состояний. Оно, к тому же, хорошо ложится на современные многоядерные архитектуры.
Здравствуйте, samius, Вы писали:
V>>Зачем же от ленивости-то? Я сейчас с удовольствием почитал собственный аргумент, но в твоей озвучке. Итак... если нет возможности ощутить как-либо побочный эффект, он есть, или его нет? S>Смотри определение
Не в Вики случайно?
V>>Ну т.е. побочные эффекты таковы, что необнаруживаемы ср-вами языка программирования. Но они есть, бо язык тьюринг-полный. S>Да, Т-полнота для тебя означает вычислимость на МТ, это я уже понял. Хотя по определению Т-полноты это возможность реализовать любую функцию, вычислимую на МТ. S>Продемонстрируй все-таки побочный эффект от вычисления функции, описанной на хаскеле. Только без бэкдоров типа unsafePerformIO.
Да запусти любую программу на хаскеле, да посмотри.
V>>Просто уже раз 10 говорилось, что порядок выполнения ф-ий можно задать явно, прямо как список инструкций в императивном программировании. А твой "мир" протаскивать как монаду State, например. Получишь выражение одного базиса через другой с идентичным уровнем подробностей. ЧТД. Т.е. никакой базис ни над каким сверху не стоит в отношении "что"->"как", если брать выражение одного через другой. Фундаментально здесь то, что вот это вычисление вложенных ф-ий происходит не одномоментно, а упорядочено, т.е. начинает быть наблюдаемым точно такой же фактор времени, смены стадий вычислений, можно оперировать понятием "контекст вычисления" (см замыкания), что суть мгновенный снимок текущего состояния вычислителя и прочее и прочее. Там всей разницы, что в чистом ФП мы получаем копию вычислителя, а в императивном — оперируем тем же самым. Но! При таких строго последовательных вычислениях (например, без лямбд и продолжений, как в императивном программировании) у нас будет оставаться только копия вычислителя, а оригинал будет все время выкидываться... Вопрос на засыпку: как определить достоверно, что мы выкинули, копию или оригинал? А нельзя ли выкидывать сразу копию? S>Тебя увело куда-то в сторону. Еще раз. Должен ли результат применения чистых по определению функций зависеть от последовательности их применения?
Коль речь о программе целиком, то бишь о композиции ф-ий — ес-но. Именно об этом и речь. Но ты зря скипнул рассуждения и вернулся на самое начало разговора, так мы будем топтаться на месте бесконечно. Уже пора было посмотреть на ООП и другие техники обеспечения локальности побочных эффектов.
Мои рассуждения в пред. посте применимы к технике ООП, ведь если объект не имеет зависимостей от глобальных данных, то любые вызовы его методов в однопоточном апартаменте сводятся к эквивалентным чистым, по тем рассуждениям что я привел. Потому что все зависимости явные, состояние объекта подается методам на исполнения явно.
S>Теперь по поводу, нельзя ли выкидывать сразу копию... Копию выкидывать сразу можно при определенных условиях. Но это трюк вычислителя, а не языка программирования. Из того что копия может быть выкинута вычислителем, не следует ровно ничего в отношении императивности языка, описывающего порождение копии.
Нет, из этого следует детерминированность, а только она и является целью, а вовсе не абстрактная "чистота".
DG>>деление на декларивный и императивный код появилось на заре становления программирования при решении задачи: может ли меняться код исполнения при той или иной записи программы? и в какой степени? S>Сам придумал? Если нет — дай ссылку.
это же ты не можешь и шагу ступить без одобрения от авторитета, ты и ищи.
чтобы эту задачу сделать за тебя — ты обязан для начала выдать полный список авторитетов, которых ты считаешь верными априори, а также привести правила по которым можно от утверждений текущего контекста перейти к утверждениям авторитета и обратно от утверждений авторитетов к текущей ситуации.
DG>>пока не было оптимизирующих компиляторов деление было более-менее четкое: DG>>пролог, sql — декларативные: исполнитель делает что хочет; S>Т.е. ты признаешь что sql когда-то был декларативным... Хорошо.
я признаю, что когда-то была достаточно точная граница, отделяющая одну группу языков от другой. и соответственно, в те времена можно было на одну группу языков вешать ярлык "декларативные", а на другую группу — "императивные", потому что на основе этих ярлыков можно было делать те или иные выводы.
сейчас же когда выражение на языке sql: select name from users; ничем не отличается от выражения на языке C#: db.users.Select(_ => _.name) — такой четкой границы нету, и соответственно — навешивание ярлыков "язык декларативный/язык императивный" ничего не дает, потому что на основе этих ярлыков никаких выводов сделать нельзя
S>Покажи мне способ строго задания sql запроса!
The NO_INDEX hint instructs the optimizer not to use one or more indexes for the specified table. For example:
SELECT /*+ NO_INDEX(employees emp_empid) */ employee_id
FROM employees
WHERE employee_id > 200;
Each parameter serves the same purpose as in "INDEX Hint" with the following modifications:
•If this hint specifies a single available index, then the optimizer does not consider a scan on this index. Other indexes not specified are still considered.
•If this hint specifies a list of available indexes, then the optimizer does not consider a scan on any of the specified indexes. Other indexes not specified in the list are still considered.
•If this hint specifies no indexes, then the optimizer does not consider a scan on any index on the table. This behavior is the same as a NO_INDEX hint that specifies a list of all available indexes for the table.
The NO_INDEX hint applies to function-based, B-tree, bitmap, cluster, or domain indexes. If a NO_INDEX hint and an index hint (INDEX, INDEX_ASC, INDEX_DESC, INDEX_COMBINE, or INDEX_FFS) both specify the same indexes, then the database ignores both the NO_INDEX hint and the index hint for the specified indexes and considers those indexes for use during execution of the statement.
http://docs.oracle.com/cd/B19306_01/server.102/b14200/sql_elements006.htm#SQLRF50411
S>А ты можешь назвать хоть один не императивный исполнитель sql? Хотя бы тот, который якобы был на заре становления программирования, когда sql еще был (по твоем рассуждениям) декларативен? Или тот, который (по рассуждениям vdimas-а) нельзя было бы выполнить на машине Тьюринга?
на заре становления sql-я, большую часть запросов sql мог выполнить только человек, в частности, например, из-за ограниченности кол-ва вложенных запросов и их видов в имеющихся программных исполнителях.
даже сейчас большинство main-stream баз имеют ограничения на сложность sql, которые они могут выполнять, при этом в самом sql-е таких ограничений нет.
DG>>при этом можно говорить, что такая запись более декларативная/менее императивная без явной фиксации исполнителя, если при этом измеряется какую степень свободы для исполнения дает та или иная запись; или если сравнивается мощность анализатора исполнителя, чтобы исполнитель мог получить ту или иную свободу исполнения, для той или иной записи кода. S>Напомни, каким образом исполнитель связан с определением декларативности, если ты в него заглядывал?
In computer science, declarative programming is a programming paradigm that expresses the logic of a computation without describing its control flow.[1] Many languages applying this style attempt to minimize or eliminate side effects by describing what the program should accomplish, rather than describing how to go about accomplishing it
в данном определении, о control flow чего? и о how для кого идет речь?
если ты ссылаешь на это определение и при этом требуешь четкости, то ты обязан сначала преобразовать это определение в четкую математическую форму и записать это определение через first-order logic и явное введение всех термов(понятий) в этом определении
V>>Гы, поднимись в определениях на один уровень раньше и посмотри, что есть вычислимая ф-ия. V>>Своими словами — это та, для которой существует конечная программа в терминах пошаговых инструкций над идеальной машиной (с бесконечной памятью). G>МТ эквивалента лямбда-исчислению, блок схемам и ЧРФ.
Если игнорить проблему останова, которая некритична для императивного вычислителя, например MT, коль программа работает во времени, генерируя при этом пользу. Но сия проблема мешает любой энергичной реализации ЧРФ из-за потенциально бесконечного зацикливания (см определение ЧРФ). А неэнергичная реализация обязательно императивна.
G>Так что можно считать вычислимой функцией ту, которую можно записать в виде ЧРФ. G>Вычислимость — свойство самой функции, императивность — свойство записи алгоритма вычисления.
М/у ними фундаментальная доказанная с разных сторон связь (см теоремы Геделя). Я ведь именно с этим и спорю, что приписать некое св-во одной системе и не приписать эквивалентной другой — банально неграмотно.
V>>Ленивость — это изолированный мини-автомат, это та самая классическая ф-ия с памятью, которая и зовется автоматом. Именно ленивость позволяет Хаскелю упорядочить последовательность вычислений, делая их детерминированными, т.е. это именно инструмент детерминированной реализации программы по вышестоящему императивному ТЗ. G>Прямо немерянное количество заблуждений в одном предложении. G>1) С чего это ТЗ императивно? Как раз хорошее ТЗ максимально декларативно. То есть не описывает конкретных шагов для получения результата.
Дык, ес-но ТЗ декларативно. См. моё определение декларативности. Просто оно в общем случае описывает эквивалентный автомат, например в терминах use-case... или различные виды описаний каких-нить протоколов и т.д. Ес-но описывается не устройство автомата, а его наблюдаемое поведение. Теперь см. определение декларативности, данное оппонентом. Или ты пока не разобрался, кто здесь с чем спорит?
G>2) С чего это ленивость- "автомат"? Может у них какие-то общие свойства есть?
С того, что ф-ий преобразователь с памятью — это и есть автомат, см определение автомата.
V>>Т.е. таки ленивость не то, что означает императивность, она именно для возможности привнесения императивности и существует G>Опять какой-то бессвязный набор слов.
Ну уж извини, кто на что учился...
G>Императивный алгоритм — тот который задает последовательность шагов, изменяющих некоторое состояние для достижения результата. Любой императивный алгоритм можно представить в виде структурированой блок-схемы.
Ну ок, первую лекцию по программирование за 1-е сентября 1-го курса ты усвоил... Молоток!
G>Ленивость заключается в том что агрументы функции вычисляются не при вызове, а при обращении. Это как раз дает непостоянную последовательность вычисления. То есть как раз в виде блок-схемы записать не получится.
Если не знаешь как — спроси. Этот императивный алгоритм над состоянием ленивого преобразователя выражается через две простейшие подпрограммы:
1. init
var func = init_func
var args = init_args
var result = unknown
2. call
if result is unknown then result = func(args)
Откровенная печаль, что опустились до этого уровня обсуждения... лучше посмотри со стороны... в другой раз отвечать на подобного качества посты я не найду времени, сорри.
V>>Это такой комбинатор, для которого можно установить необходимый и достаточный порядок вычисления аргументов вместо произвольного. G>То есть ленивость таки не соответствует фиксированному порядку, а значит не является императивным.
Таки комбинатору I приписывается достаточный порядок вычисления аргументов, с тем, чтобы не вычислять часть из них, если уже не требуется. Я бы сказал, что это фундаментально для Хаскеля, см ф-ию ветвления.
V>>где требуется детерминированная последовательность операций G>Требуется она в одном случае — при общении программы с внешним миром.
Гы, программа без общения с внешним миром не требуется. Есть мнение, что полезный (целевой) эффект от любой программы — исключительно побочный. Поэтому декларативное ТЗ запросто может быть перечислением побочных эффектов.
V>>В общем, иначе было бы гораздо сложнее реализовать исходное императивное ТЗ на чистом ФП, если бы не ленивость. G>О чем ты? Бери F# и Haskell, покажи в чем леность помогает общаться с внешним миром.
Наворачивание ф-ий ввода-вывода на монаду IO в Хаскеле работает именно потому, что ф-ии не вычисляются энергично. Композиция ф-ий образует некий порядок вычислений, который затем пошагово интерпретируется во времени механизмом ленивости как показал выше.
G>И снова напомню что хорошее ТЗ максимально декларативно.
OMG... заберите его от меня...
Я ведь именно это и утверждаю, что суть декларативности — в отделении ТЗ от реализации, независимо от никаких техник реализации. Отвечай тогда уж не мне, а моим оппонентам.
V>>Пришлось бы бороться с комбинаторным взрывом при вычислении (в общем случае рекурсивном) всех аргументов всех операций. И не факт, что программа имела бы останов... G>Это ты о чем вообще? ЧРФ эквивалентны блок-схемам, причем без всякой ленивости
Это я о проблеме останова. О ней, родимой. Блок схемы и описываемая ими пошаговость вносят фактор времени в алгоритм, а ЧРФ никак не вносит. Не умеет... Именно поэтому проблема останова никакая не проблема для современного ПО, сидящего на модели, близкой к МТ. Ну работает себе некий сервис или основной цикл ОС в бесконечном цикле... дык, так и задумывалось.
S>Твои выводы ничего не стоят, т.к. используют термины, смысл которых очевидно искажен.
расскажи, пожалуйста, какой ярлык (декларативный/императивный) ты приклеиваешь к какому языку из списка: sql, c#, haskell. и какие выводы на основе приклеенного ярлыка делаешь?
Здравствуйте, vdimas, Вы писали:
V>Здравствуйте, gandjustas, Вы писали:
V>>>Гы, поднимись в определениях на один уровень раньше и посмотри, что есть вычислимая ф-ия. V>>>Своими словами — это та, для которой существует конечная программа в терминах пошаговых инструкций над идеальной машиной (с бесконечной памятью). G>>МТ эквивалента лямбда-исчислению, блок схемам и ЧРФ.
V>Если игнорить проблему останова, которая некритична для императивного вычислителя, например MT, коль программа работает во времени, генерируя при этом пользу
Что значит "некритична"? Что значит "программа работает во времени"? В реальном времени? Любая программа так работает, в языках программирования же никакого времени не существует.
V>Но сия проблема мешает любой энергичной реализации ЧРФ из-за потенциально бесконечного зацикливания (см определение ЧРФ).
Любая программа потенциально зацикливается. Любую незацикливающуюся программу на МТ можно переписать на любом языке и она тоже не будет зацикливаться.
V>А неэнергичная реализация обязательно императивна.
Слова ни о чем. Процессор выполняет последовательность инструкций. Тем не менее оперировать понятием последовательности действий при написании программы не обязательно. И понятие вычислимости функции тоже на "последовательность" не опираются.
G>>Так что можно считать вычислимой функцией ту, которую можно записать в виде ЧРФ. G>>Вычислимость — свойство самой функции, императивность — свойство записи алгоритма вычисления.
V>М/у ними фундаментальная доказанная с разных сторон связь (см теоремы Геделя).
Какая именно, приведи ссылку.
V> Я ведь именно с этим и спорю, что приписать некое св-во одной системе и не приписать эквивалентной другой — банально неграмотно.
Нет, ты пытаешься разные логические уровни объединить в один приписывая свойства объектов одного уровня объектам другого. Это неправильно. Кажется Синклер тебе это уже говорил.
V>>>Ленивость — это изолированный мини-автомат, это та самая классическая ф-ия с памятью, которая и зовется автоматом. Именно ленивость позволяет Хаскелю упорядочить последовательность вычислений, делая их детерминированными, т.е. это именно инструмент детерминированной реализации программы по вышестоящему императивному ТЗ. G>>Прямо немерянное количество заблуждений в одном предложении. G>>1) С чего это ТЗ императивно? Как раз хорошее ТЗ максимально декларативно. То есть не описывает конкретных шагов для получения результата.
V>Дык, ес-но ТЗ декларативно. См. моё определение декларативности.
Давай всетаки общеизвестным пользоваться. http://en.wikipedia.org/wiki/Declarative_programming
V>Просто оно в общем случае описывает эквивалентный автомат, например в терминах use-case... или различные виды описаний каких-нить протоколов и т.д.
Протокол и есть автомат Но это не ТЗ. Вот ТЗ: "стул должен стоять не ближе 5 метров от дивана". Переведи это в автомат.
G>>2) С чего это ленивость- "автомат"? Может у них какие-то общие свойства есть? V>С того, что ф-ий преобразователь с памятью — это и есть автомат, см определение автомата.
Опять ты склеиваешь разные логические уровни. Причем тут память и ленивость? Ты хочешь рассмотреть реализацию ленивости — так и пиши, но не надо после этого приписывать свойства реализации самой ленивости.
G>>Императивный алгоритм — тот который задает последовательность шагов, изменяющих некоторое состояние для достижения результата. Любой императивный алгоритм можно представить в виде структурированой блок-схемы.
V>Ну ок, первую лекцию по программирование за 1-е сентября 1-го курса ты усвоил... Молоток!
А ты?
G>>Ленивость заключается в том что агрументы функции вычисляются не при вызове, а при обращении. Это как раз дает непостоянную последовательность вычисления. То есть как раз в виде блок-схемы записать не получится.
V>Если не знаешь как — спроси. Этот императивный алгоритм над состоянием ленивого преобразователя выражается через две простейшие подпрограммы: V>1. init V>var func = init_func V>var args = init_args V>var result = unknown
V>2. call V>if result is unknown then result = func(args)
И когда будут вычислены args?
например есть программа z = f(x(), y()), вычисления ленивые, преобразуй в блок схемы, указывая последовательность вычислений.
V>Откровенная печаль, что опустились до этого уровня обсуждения... лучше посмотри со стороны... в другой раз отвечать на подобного качества посты я не найду времени, сорри.
Это ты как раз пониматься начал по лестице абстракции, подниись еще чуть выше и посмотри сверху на свою же писанину. Тогда совсем в депрессию впадешь.
V>>>Это такой комбинатор, для которого можно установить необходимый и достаточный порядок вычисления аргументов вместо произвольного. G>>То есть ленивость таки не соответствует фиксированному порядку, а значит не является императивным.
V>Таки комбинатору I приписывается достаточный порядок вычисления аргументов, с тем, чтобы не вычислять часть из них, если уже не требуется. Я бы сказал, что это фундаментально для Хаскеля, см ф-ию ветвления.
"достаточный" не означает фиксированный, это противоречит императивности.
V>>>где требуется детерминированная последовательность операций G>>Требуется она в одном случае — при общении программы с внешним миром.
V>Гы, программа без общения с внешним миром не требуется. Есть мнение, что полезный (целевой) эффект от любой программы — исключительно побочный. Поэтому декларативное ТЗ запросто может быть перечислением побочных эффектов.
И что? Теперь надо обязательно всю программу строить на побочных эффектах?
V>>>В общем, иначе было бы гораздо сложнее реализовать исходное императивное ТЗ на чистом ФП, если бы не ленивость. G>>О чем ты? Бери F# и Haskell, покажи в чем леность помогает общаться с внешним миром.
V>Наворачивание ф-ий ввода-вывода на монаду IO в Хаскеле работает именно потому, что ф-ии не вычисляются энергично.
Не поэтому, кури монады. Можешь в F# повторить state (IO там нет, но суть не отличается).
V>Композиция ф-ий образует некий порядок вычислений, который затем пошагово интерпретируется во времени механизмом ленивости как показал выше.
Тот "механизм" не является полным, потому что он как раз о порядке вычисления агрументов ничего не говорит.
G>>И снова напомню что хорошее ТЗ максимально декларативно. V>OMG... заберите его от меня... V>Я ведь именно это и утверждаю, что суть декларативности — в отделении ТЗ от реализации, независимо от никаких техник реализации. Отвечай тогда уж не мне, а моим оппонентам.
Ты его императивным назвал, а это слово противоречит декларативности.
V>>>Пришлось бы бороться с комбинаторным взрывом при вычислении (в общем случае рекурсивном) всех аргументов всех операций. И не факт, что программа имела бы останов... G>>Это ты о чем вообще? ЧРФ эквивалентны блок-схемам, причем без всякой ленивости
V>Это я о проблеме останова. О ней, родимой.
Она тоже не зависит от ленивости
V>Блок схемы и описываемая ими пошаговость вносят фактор времени в алгоритм, а ЧРФ никак не вносит. Не умеет... Именно поэтому проблема останова никакая не проблема для современного ПО, сидящего на модели, близкой к МТ. Ну работает себе некий сервис или основной цикл ОС в бесконечном цикле... дык, так и задумывалось.
А чем бесконечная рекурсия отличается от бесконечного цикла?
V>>Просто оно в общем случае описывает эквивалентный автомат, например в терминах use-case... или различные виды описаний каких-нить протоколов и т.д. G>Протокол и есть автомат Но это не ТЗ. Вот ТЗ: "стул должен стоять не ближе 5 метров от дивана". Переведи это в автомат.
автомат из одной императивной команды:
установить положение стула не ближе 5 метров от дивана.
Здравствуйте, DarkGray, Вы писали:
G>>Протокол и есть автомат Но это не ТЗ. Вот ТЗ: "стул должен стоять не ближе 5 метров от дивана". Переведи это в автомат.
DG>автомат из одной императивной команды: DG>установить положение стула не ближе 5 метров от дивана.
Здравствуйте, DarkGray, Вы писали:
S>>Этот код не является чисто функциональным, т.к. использует недетерминированные функции.
DG>если уж делаешь какие-то утверждения, то делай это правильно и четко. DG>твоя проблема, что ты умудряешься даже для железобетонных определений делать ужасные формулировки своих утверждений.
DG>точная формулировка: функция конструирующая тип C не является чисто функциональной, т.к. использует недетерминированную функцию new Random(). DG>остальные функции являются чисто функциональными и детерминированными.
Резульаты остальных функций ты воле заменить значениями.
DG>и соответственно, как только ты бы сделал правильное и четкое утверждение, то скорее всего до тебя бы дошло, что тебе показывают и тебя просят подумать про ту часть кода, которая состоит из чисто функциональных детерминированных функциях.
Ты же написал что заменил код на чисто функциональный. Там не было никаких оговорок.
DG>вторая проблема, что ты считаешь собеседников заведомо глупыми. и любую неточность в формулировках ты трактуешь в пользу глупости собеседника, вместо того, чтобы самостоятельно устранить неточность и ответить по существу. при этом ты бы чему-то научился (и это был бы конструктивный подход), а так ты лишь чешешь свое самолюбие.
Я не считаю собеседника глупым. Я считаю что он игнорирует определения. Причем это входит в тенденцию, а значит намеренно.
Здравствуйте, vdimas, Вы писали:
V>Здравствуйте, samius, Вы писали:
S>>Этот код не является чисто функциональным, т.к. использует недетерминированные функции.
V>Это ты про Random()? А разве нет его в ФП языках? В примере была демонстрация того, о чем мы тут говорим по всей ветке, забей ты на этот на Random, это уже просто придирки...
Раднома в ФП языках? Именно в таком виде — в чистых нет.
Если забить на рандом, то я не понимаю, в чем суть вопроса. Во втором фрагменте кода побочных эффектов нет
V>Дело в том, что современные компиляторы давно способны устанавливать все зависимости, именно это и позволяет им заниматься оптимизацией и спекулятивным выполнением.
Извиняюсь. Не по делу.
Я почему-то вообще чувствую себя первокурсником, которого пытаются завалить пара преподавателей. Причем особо циничным способом — доказать что я не втыкаю в два определения с первой лекции. И от усердия преподы скатываются черт знает в какие дебри философии. Вот, дело до оптимизации дошло. Но определения-то вот они, в конспекте. Есть другие — давай обсудим. Не вопрос.
S>>Ты молоток, написал кучу кода. Но совершенно зря. Твои выводы ничего не стоят, т.к. используют термины, смысл которых очевидно искажен. Чистота — еще один термин, который ты толкуешь как-то по-своему.
V>Дык более половины встреченных определений "чистоты" неполны. Многие из них вообще говорят о каких-то глобальных переменных, о вводе-выводе и прочий бред... А если у нас нет в языке глобальных переменных? В общем, более нелепого определения чистоты ф-ий, чем в Вики, я еще не видел, так что не мечи тут молнии.
Покажи менее нелепые.
V>Чистота — это отсутствие неявных зависимостей и ничего более. Зачем она вообще нужна? Детерминированности ради. Чистота ведь не самоцель ни разу, а лишь ср-во обеспечения детерминированности. Вернее, одно из ср-в, хотя и самое дешевое из всех. Дешевое в разработке, ес-но... бо в исполнении чистые программы пока ничего дешевого не показывают, скорее наоборот. ИМХО, самое дешевое ср-во обеспечения детерминированности на сегодня по всем показателям суммарно — это локальность состояний. Оно, к тому же, хорошо ложится на современные многоядерные архитектуры.
Какой кошмар.
Смотри: допустим что printf детерминирована. Даже не важно, детерминирована ли она на самом деле, но давай предположим, что да, если на самом деле нет. Пусть она возвращает всегда длину строки, которая могла бы быть выведена вне зависимости ни от чего.
Если ты утверждаешь что она чиста (детерминирована ведь), значит порядок вызова не важен. Верно ли это, ответь мне глядя в консоль на результат работы printf.
Может детерминированности таки мало для чистоты? Если мало, то почему твое определение чистоты лучше чем то что в вики?
Здравствуйте, vdimas, Вы писали:
V>Здравствуйте, samius, Вы писали:
V>>>Зачем же от ленивости-то? Я сейчас с удовольствием почитал собственный аргумент, но в твоей озвучке. Итак... если нет возможности ощутить как-либо побочный эффект, он есть, или его нет? S>>Смотри определение
V>Не в Вики случайно?
Да я там его смотрел. У тебя есть свое, лучше?
S>>Да, Т-полнота для тебя означает вычислимость на МТ, это я уже понял. Хотя по определению Т-полноты это возможность реализовать любую функцию, вычислимую на МТ. S>>Продемонстрируй все-таки побочный эффект от вычисления функции, описанной на хаскеле. Только без бэкдоров типа unsafePerformIO.
V>Да запусти любую программу на хаскеле, да посмотри.
Проблема в том, что результат выполнения main на хаскеле (без использования бэкдоров) является функцией, ну или его можно воспринимать как фукнцию. И увидеть побочный эффект от выполнения main я затрудняюсь. А с тем что эта функция (результат main) может иметь побочные эффекты, я не спорю.
V>>>Просто уже раз 10 говорилось, что порядок выполнения ф-ий можно задать явно, прямо как список инструкций в императивном программировании. А твой "мир" протаскивать как монаду State, например. Получишь выражение одного базиса через другой с идентичным уровнем подробностей. ЧТД. Т.е. никакой базис ни над каким сверху не стоит в отношении "что"->"как", если брать выражение одного через другой. Фундаментально здесь то, что вот это вычисление вложенных ф-ий происходит не одномоментно, а упорядочено, т.е. начинает быть наблюдаемым точно такой же фактор времени, смены стадий вычислений, можно оперировать понятием "контекст вычисления" (см замыкания), что суть мгновенный снимок текущего состояния вычислителя и прочее и прочее. Там всей разницы, что в чистом ФП мы получаем копию вычислителя, а в императивном — оперируем тем же самым. Но! При таких строго последовательных вычислениях (например, без лямбд и продолжений, как в императивном программировании) у нас будет оставаться только копия вычислителя, а оригинал будет все время выкидываться... Вопрос на засыпку: как определить достоверно, что мы выкинули, копию или оригинал? А нельзя ли выкидывать сразу копию? S>>Тебя увело куда-то в сторону. Еще раз. Должен ли результат применения чистых по определению функций зависеть от последовательности их применения?
V>Коль речь о программе целиком, то бишь о композиции ф-ий — ес-но. Именно об этом и речь. Но ты зря скипнул рассуждения и вернулся на самое начало разговора, так мы будем топтаться на месте бесконечно. Уже пора было посмотреть на ООП и другие техники обеспечения локальности побочных эффектов.
Я прочитал еще раз — не заметил в рассуждениях мысли, которая бы была связана с моим вопросом.
V>Мои рассуждения в пред. посте применимы к технике ООП, ведь если объект не имеет зависимостей от глобальных данных, то любые вызовы его методов в однопоточном апартаменте сводятся к эквивалентным чистым
Чушь! V>, по тем рассуждениям что я привел. Потому что все зависимости явные, состояние объекта подается методам на исполнения явно.
Возьмем пример DarkGray-а, где создается объект C, который не зависит ни от каких глобальных данных (напрямую). Но зависит от GetTickCount, который seed в rnd, что данными назвать затруднительно. Тем не менее, считать такой объект чистым — весьма наивно.
Да, пусть объект C имеет зависимость от rnd лишь в конструкторе. Но эта зависимость могла бы быть в методе. И эта зависимость не от данных. Имей в виду, когда будешь карежить определения в другой раз.
S>>Теперь по поводу, нельзя ли выкидывать сразу копию... Копию выкидывать сразу можно при определенных условиях. Но это трюк вычислителя, а не языка программирования. Из того что копия может быть выкинута вычислителем, не следует ровно ничего в отношении императивности языка, описывающего порождение копии.
V>Нет, из этого следует детерминированность, а только она и является целью, а вовсе не абстрактная "чистота".
Напоминаю о примере с якобы детерминированным printf-ом. Детерминированности недостаточно для изменения порядка.
G>>>Протокол и есть автомат Но это не ТЗ. Вот ТЗ: "стул должен стоять не ближе 5 метров от дивана". Переведи это в автомат.
DG>>автомат из одной императивной команды: DG>>установить положение стула не ближе 5 метров от дивана.
S>С понятием автомата ты тоже не знаком?
т.е. ты даже не понимаешь, что такое автомат из одной команды?
Абстра́ктный автома́т (в теории алгоритмов) — математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. На вход этому устройству поступают символы одного алфавита, на выходе оно выдаёт символы (в общем случае) другого алфавита.
входной алфавит: стул, для которого должно выполняться условие "стоять не ближе 5 метров от дивана"
выходной алфавит: стул, для которого выполняется условие "стоять не ближе 5 метров от дивана"
входная последовательность: последовательность из одного символа — стул, для которого должно выполняться условие "стоять не ближе 5 метров от дивана"
выходная последовательность: последовательность из одного символа — стул, для которого выполняется условие "стоять не ближе 5 метров от дивана"
автомат имеет три состояния:
инициальное,
рабочее,
терминальное.
стартует с инициального.
из инициального переходит в рабочее.
в рабочем читает один символ алфавита с потока (если символы кончились, то переходит в терминальное),
выполняет команду "установить положение стула не ближе 5 метров от дивана", выдает в поток символ "стул, для которого выполняется условие "стоять не ближе 5 метров от дивана"" и переходит в состояние "рабочее".
