Immutable object - Философия программирования

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

V>>Второе предложение можно по-русски?
S>Ссылаясь на определение декларативного программирования, я утверждаю что printf не описывает что нужно получить, т.к. void, ее результат есть ничто. Вместо этого printf воспроизводит побочный эффект. Т.е. вместо описания мы имеем инструкцию.

А что, сигнатура ф-ии уже является полноценной декларацией? Вовсе нет, сигнатура в ФЯ лишь объявляет контракт, и то, лишь с самыми зачатками программирования в ограничениях. (Пролог в этом плане всяко мощнее.) И ввиду слабости и зачаточности этой техники нифига непонятно, что же надо получить в ф-ии int -> int*int, например... Т.е. аннотация типов есть, а какая м/у аргументами и результатами связь — непонятно...

V>>На уровне твоего кода его нет. Я не зря привел ф-ый язык как пример.
S>Извини, ты привел в пример чистый ФЯ, при этом упоминаешь haskell. Что мне намекает на то, что ты не понимаешь природу вывода в хаскеле.

Ну поясни "природу", как ты понимаешь. Я понимаю как оно определено в этом языке и какие ограничения накладывает, что-то еще? Я как-то делал замечания, что ф-ый подход хорош там где нам надо данные вычислять и не очень хорош когда эти вычисленные данные потом надо куда-то девать. А девать их куда-то рано или поздно придется. Т.е. абсолютно любой ф-ий язык должен иметь связь с внешним миром, чтобы быть хоть немного полезен именно как язык программирования.

V>>Т.е. ты никак не можешь достоверно узнать, есть он или нет, бо на твои собственные программные примитивы это никак не влияет.
S>В случае haskell я достоверно знаю что побочного эффекта нет. Описание main не производит побочный эффект.

Достоверно знать можно разными путями, начнем с того что. Аннотация типов и ф-ой чистоты — лишь один из способов. Компилятор всяко больше может знать, выведя все зависимости.

S>>>В случае хаскеля, например, ввод-вывод не делают (не выполняют). Вместо этого результатом функции main является комбинация императивных действий и вычислений. Такая комбинация получается с помощью декларативного описания, именно она является целью декларативных вычислений. Выполнение ввода-вывода остается таким образом за бортом ФЯ.

V>>Э нет, за бортом ничего не остается, есть монады, задачи которых — именно образовать цепочку вычислений. Императив. И пусть это делается "чисто функциональными ср-вами" — ничего по-сути не меняется, коль нам гарантируется последовательность вычислений.
S>Не вижу связи между цепочкой вычислений и императивом. Композиция функций для тебя тоже императив?

Банально инструмент для оного. Этим инструментом явно описывается такая фундаментальная вещь, как детерминированный поток исполнения, что и требовалось. Не всё ли равно, какой инструмент? Аргументы насчет "явных" зависимостей — немного слабоваты. Мы же вполне можем писать без глобальных переменных в том же ООП. Ведь состояние вполне может быть локально, типа переменных стека или переменных объекта. В этих случаях замыкание или void-методы можно рассматривать как принимающие и возвращающие локальный контекст, в котором объявлены (оно так и есть технически с разной степенью подробности).

S>>>В сравнении с таким подходом, результатом выполнения main у C-подобных языков является int или void. И printf для вычисления этого значения не нужен.

V>>При чем тут вообще main? В Хаскеле есть ввод-вывод куда угодно, в файл, сокет и т.д., вызываемые из произвольной IO ф-ии.
S>Ты что-то путаешь в отношении ввода-вывода хаскеля. Ввод-вывод не вызывается из произвольной функции. Или ты уже про бэкдоры типа unsafePerformIO ?

Нет, я про любые IO ф-ии. То, что main организует IO — непринципиально, ведь может же быть возможность, интероперабельности кода на Хаскеле с другими языками (подрбно не копал, но вроде есть проекты для хаскеля генерации то в байткоды, то код на других языках), т.е. какая разница, кто именно запускает IO — main или другая "точка входа"? Хаскель был приведен лишь как пример языка, считающегося чистым функциональным для демонстрации неизбежности императивности в любой программе, целью которой является чуть больше, чем собственная компиллируемость (это я на всякий случай откидываю класс языков, используемых для док-ва теорем).

V>>Я пока не увидел, чем IO монада в Хаскеле отличается от тела ф-ии printf.
S>Монада IO в хаскеле не производит побочный эффект, как это делает printf.
V>>Про State вообще молчу... эмуляция императива как оно есть.
S>Эмуляция императива != императив.

Дудки! Иначе эмуляцию ФП на современных императивных выч. машинах, близких по принципу работы к машине Тьюринга, нельзя было считать за ФП.

Но тут же все утверждают что "ФП существует!", и вполне согласен, хоть оно и эмулируется на самом деле. Какая фиг разница, с помощью какого инструмента воспроизводится требуемая механика, если в результате можно получить все точно такие же эффекты (например, побочные эффекты в случае State)? Простоты ради предположи, что любой метод объекта в ООП не изменяет состояние объекта, а порождает новое измененное состояние, прямо как в State. И найди после этого отличия.

S>Хаскель описывает что нужно получить на выходе main. C описывает как нужно выводить в консоль, притом что на выходе этого описания return 0 в лучшем случае.

Сорри, но это уже классика в стиле "тут смотрим, тут не смотрим". Описание в виде ограничений типов — это еще нифига не описание. Это так, легкое ограничение на то, что можно подставить внутрь этого описания. Учитывая вывод типов и прочие плюшки, т.е. даже зачастую отсутствие нотации типов в описании я могу так же прдеположить что "тип" любого локального контекста в императивной программе компилятор "выводит" вполне успешно.

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

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

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

Да нет никакого трюка. Это ты описал принцип работы ф-ого преобразователя с памятью. Он состоит из памяти и собсно ф-ии вычисления следующего состояния. Рассуждая таким же образом, императивная программа ведет себя точно так же, получает World на входе, и что-то с ним делает с помощью "сконструированной" компилятором программы. Степень декларативности тут одинаковая.

S>>Внутри Main могут быть всякие ветвления, рекурсия, и прочее. Каждая из функций может чего-то записывать в консоль (скажем, отладочный вывод).
S>да, ветвления, рекурсия и прочее. Но каждая из функций, к которым обращается main, не пишет и не читает. Они возвращают функции, которые при выполнении будут писать и читать.

Да какая разница? На ф-ом языке операции над ФПВ и есть львиная доля программы.

Тем более, что в ленивом языке любая ф-ия по определению возвращает ф-ию, а не результат, которая будет работать лишь при "выполнении" (С).

S>На этапе построения результата main побочных эффектов нет.

Вообще-то есть — это сама технология ленивости. Но тебе эта "побочность" явным образом недоступна, хоть она декларируется в семантике и на нее надо полагаться.

S>Но порядок их выполнения при выполнении результирующей функции нам важен. Этот порядок обеспечивается композицией функций, из которых строится main. Они представляют собой конвейер по надругательствам над миром. Тут уже не важно, считать ли мир изменяемым, или считать что каждая функция при выполнении создает новую копию мира и где-то есть указатель на текущий мир. Важно что конвейер обеспечивает точный порядок приложения функций к миру.

О чем и речь. Используется имеющийся механизм для создания потока вычисления.

S>А в хаскеле так: к окончанию декларативной программы на хаскеле у нас появляется программа для вычислителя. Программа для вычислителя императивна и может работать с изменяющимся миром/консолью.

Все это с таким ворохом допущений... Для сравнения, программу на С++ в шаблонах тоже можно считать декларативной, порождающей целевой "вычислитель".

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

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

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

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

V>>Это только у нас в голове так, согласно доке по консоли.
S>Т.е. если доку не читать, то побочных эффектов в printf не будет?

Неизвестно,зависит того, null там или другой девайс.

V>>Дык, тело сишной printf тоже не имеет никаких побочных эффектов, является полностью реентерабельной. Если бы были побочные эффекты именно внутри кода printf, она не была бы реентерабельной и многопоточной. И да, в printf таки подается FILE (просто в той перегрузке, в которой не подается, используется глобальная переменная). И отличие в Хаскеля лишь в том, что IO-тип Console не надо возвращать обратно как результат ф-ии, бо это лишь частное требование для механики монады IO, которая не нужна в C++.
S>printf консоль портит? Портит. А значит побочный эффект присутствует. putChar консоль портит? Нет. Вот в этом и отличие от Хаскеля.

Это ты слишком поверхностно рассматриваешь. Давай мы распишем механику ленивости, для начала. А потом модель императивного вычислителя. И только потом будем искать разницу, а не вот так, с высоты птичьего полета да еще под удобным углом.

V>>Вооот... мы дошли до цепочек вычислений в ф-ом программировании, через механизм вложенных вызовов ф-ий, мне даже не пришлось 10-й раз намекать, как для случая РА. Чем не императив? ИМХО, только точкой зрения на происходящее.
S>f(g(x)) тоже императив?

Во избежание спекуляций, без контекста и рассмотрения подробностей отвечать на это не буду. Бо я именно согласен или обсуждать вглубь, или никак вообще. Любой Тьюринг-полный язык императивен по своему определению, например Хаскель. То, что в нем есть ФВП, ленивость и иммутабельность — это лишь приятные плюшки, но не более. Неимперативным в принципе может быть только Тьюринг-неполный язык и никакой другой.

V>>Это ес-но, речь шла о том, где заканчивается декларативное и начинается императивное. Твои побочные эффекты могут быть нам недоступны, т.е. не влиять на элементы нашей программы, примерно как в монаде IO. В чем тогда отличие якобы декларативного Хаскеля в случае этой монады, и императивной программы, которая использует только "чистые" ф-ии и процедуры, не изменяющие неявно состояния нашей программы?
S>В том что программа на Хаскеле описывает результат. А императивная программа описывает последовательность действий.

Нет, это тебя опять несет на высоту птичьего полета. Программа на Хаскеле для IO всегда описывает именно действия, которые будет совершать эта ф-ия. То, что любая ф-ия на самом деле возвращает ф-ию — это св-во ленивости, а не чистой ф-сти. Тут ты пытаешься всё свалить в кучу. Я видел твою "расшифровку" монады IO, но даже этого не требуется, коль IO ф-ия ленива.

V>>Первое предложение ты написал поторопимшись. У нас уже есть низлежащая аппаратура, которая близка по принципу работы машине Тьюринга, поэтому последовательность инструкций мы имеем как вычислительный базис. Отличие ф-ых языков от императивных в том, что ф-ые скрывают от программиста внутреннюю работу с состоянием, т.е. на уровне пользовательской программы побочных эффектов НЕТ. Я же привел printf не случайно, показав точно такой же случай, что на уровне пользовательской программы нет никаких побочных эффектов. Я понимаю, что тебе сразу захотелось полезть куда-то внутрь, чуть ли не до самой машины Тьюринга и показать мне, что таки состояние есть у консоли "где-то там унутрях"... но это очень толсто, коль этот случай сравнивался с точно таким же аналогичным из ФЯ...
S>И зачем по-твоему вызывать из C++ printf если побочных эффектов у него нет и он ничего не возвращает/вычисляет? Почему бы его просто не выкинуть из пользовательской программы?

А почему из Хаскеля не выкидываешь? Еще раз, ТВОЯ программа не имеет доступа к этим побочным эффектам, прямо как в Хаскеле.

V>>В общем, я еще с самого начала предупредил, что тема иммутабельности и границ императивности — скользкая. Много холивара и условностей, а львиная доля любой императивной программы — абсолютно чиста с т.з. побочных эффектов над доступными примитивами программы. Сказать, что я заведомо определился с какой-то точкой зрения не могу. В разных спорах участвую с разных сторон.

Интересны сугубо аргументы. Бо сдается мне, что прямо на сегодня в этих понятиях слишком много религиозного и зависимости от точки зрения и глубины рассмотрения происходящего. А раз так, то использовать их в кач-ве аргументов следует осторожно или не использовать вообще, предпочитая обсуждать конкретику вместо приема спора, когда вопрос пытаются отнести к некоему "классу" и выстроеному последующему док-ву на принадлежности проблемы к сему классу.
S>Конечно, если считать printf декларативным и не имеющим побочных эффектов, а монады императивными, то тема очень скользкая.
S>Давай по-маленьку. Как printf влияет на результат функции, в теле которой вызывается? Как влияет putChar из Хаскеля?

Про зависимости я ответил даже не помаленьку, а сразу с заделом тут: http://www.rsdn.ru/forum/philosophy/4570092.1.aspx
Давай уже там.

И кстате, можно не только Хаскель. Вон Эрланг торчит в разделе декларативных языков на этом сайте, можно посмотреть ввод-вывод у него — классика ф-ой композиции для целей императивности.

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

DG>>при появлении буферизации, параллельного выполнения, сложных вариантов output file-а и т.д. все эффекты могут выполняться нечетко
S>По-моему у тебя нечеткое понимание побочного эффекта. Глобальное изменение состояния оно есть или нет. Четко или нечетко — это уже к качеству выполнения изменения, что мы не обсуждаем.

Во-первых, необязательно глобальное состояние (это слишком упрощено), а во-вторых — четкость изменения состояния — это архиважно (С) важно для соответствия императивной программы автоматной модели.

DG>>если же исполнитель — это понимает как "выполни как хочешь, но дай правильный результат этой конструкции", то это уже декларация.
S>Ну так можно дойти до того что вычислений без побочных эффектов не бывает, т.к. при вычислениях меняются содержимые регистров процессора.

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

S>Только какое отношение исполнитель имеет к определению императивного программирования? Покажи связь между программой "1 + 2 * 3" и "оттранслируй, выполни".

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

DG>>отчасти это лучше видно на конструкции (1, 4, 2).sort(desc) — с одной стороны, исполнитель это может понимать как: создай массив, заполни его (1, 4, 2), вызови для массива функцию sort с параметром desc — и это императивный подход,
DG>>с другой стороны — исполнитель это может понимать как: необходимо переставить элементы (1, 4, 2) так, чтобы каждый следующий был меньше предыдущего — а это уже чисто декларативный подход.
S>Я предлагаю ограничить осбуждение конструкциями в рамках конкретных, наперед заданных исполнителей, а не в рамках того что существует абстрактный исполнитель, который конкретную конструкцию воспринимает не так как другой.

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

DG>>если вернуться к sql там все тоже самое:
DG>>конструкция select name from users order by name может считаться императивной: найди таблицу users, выбери записи по индексу по полю name (или отсортируй), и верни только значения поля name.
S>Ты имеешь в виду что select отсортирует таблицу по-месту, изменив тем самым содержимое таблицы? Если нет, то в чем здесь императив?

В алгоритме в терминах инструкций, очевидно:
— найди таблицу
— выбери проекцию
— отсортируй результат

И откуда ты решил, что по-месту?

DG>>а может в декларативной: дай в отсортированном виде значения поля name из таблицы users.

Хороший пример, показывающий эквивалентность декларативного определения и определения в терминах инструкций. На самом деле, на любом выбранном уровне подробностей эти определения будут эквивалентны. Они будут неэквивалентны лишь тогда, когда попытаемся приписать для любого выбранного примера разный уровень подробностей декларативному и императивному.

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

S>>>По-моему у тебя нечеткое понимание побочного эффекта. Глобальное изменение состояния оно есть или нет.

DG>>опять ты хочешь поделить мир лишь на два полюса: глобально или локально. в реальном мире нет таких полюсов: есть лишь менее/более локально (более/менее глобально).
DG>>например, функция IEnumerable OrderBy(IEnumerable, Func) несмотря на то, что она с одной стороны чисто функциональая, имеет побочный эффект — если она меняет состояние порядка одинаковых элементов внутри результирующей последовательности.
S>Внутри результирующей последовательности OrderBy может менять что угодно. Внутри исходной — нет.
S>Между делом, у тебя опять что-то с определениями. Определение чистой функции не допускает побочные эффекты. Т.е. чистая функция не может обладать побочными эффектами по определению. У тебя же она и чистая с одной стороны, и с побочным эффектом с другой.

Ну да, например ленивость... Самый что ни на есть побочный эффект, "выпрямляющий" вычисления. Тут уже как-то обсуждалось похожая тема. Кароч, с понятием "побочный эффект" надо быть аккуратней, бо речь всегда может идти только о доступном для осязания/измерения/использования побочном эффекте, иначе можно считать что его нет. Именно так эмулируется ФП императивном вычислительном базисе, через допущения относительно видимости побочных эффектов.

DG>>и соответственно, не смотря на то, что функция чисто функциональная по определению — результат выражения зависит от истории применения orderby-ев к последовательности
S>А разве кто-то утверждал что результат применения чистых по определению функций не должен зависить от последовательности их применения?

А это уже заворот на 10-й круг в этом обсуждении. Можно смело завязывать, стороны выдохлись.

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

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

S>>Ссылаясь на определение декларативного программирования, я утверждаю что printf не описывает что нужно получить, т.к. void, ее результат есть ничто. Вместо этого printf воспроизводит побочный эффект. Т.е. вместо описания мы имеем инструкцию.

V>А что, сигнатура ф-ии уже является полноценной декларацией? Вовсе нет, сигнатура в ФЯ лишь объявляет контракт, и то, лишь с самыми зачатками программирования в ограничениях. (Пролог в этом плане всяко мощнее.) И ввиду слабости и зачаточности этой техники нифига непонятно, что же надо получить в ф-ии int -> int*int, например... Т.е. аннотация типов есть, а какая м/у аргументами и результатами связь — непонятно...

Видишь ли, когда ты вызываешь функцию не ради ее результата, ты тем самым говоришь что она тебе не для вычисления нужна, а для побочного эффекта. Хоть printf все-таки не void, а int. И зовут ее ради побочного эффекта, тем самым попадая под определение императива.

S>>Извини, ты привел в пример чистый ФЯ, при этом упоминаешь haskell. Что мне намекает на то, что ты не понимаешь природу вывода в хаскеле.

V>Ну поясни "природу", как ты понимаешь. Я понимаю как оно определено в этом языке и какие ограничения накладывает, что-то еще? Я как-то делал замечания, что ф-ый подход хорош там где нам надо данные вычислять и не очень хорош когда эти вычисленные данные потом надо куда-то девать. А девать их куда-то рано или поздно придется. Т.е. абсолютно любой ф-ий язык должен иметь связь с внешним миром, чтобы быть хоть немного полезен именно как язык программирования.
Я объяснял природу как я ее понимаю. В двух словах — программа на хаскеле декларативно объявляет комбинацию функций (в том числе императивных). Но я уже повторяюсь. А ты мне пишешь про императивные монады. Продемонстрируй мне императивность монад в коде, покажи побочный эффект!

S>>В случае haskell я достоверно знаю что побочного эффекта нет. Описание main не производит побочный эффект.

V>Достоверно знать можно разными путями, начнем с того что. Аннотация типов и ф-ой чистоты — лишь один из способов. Компилятор всяко больше может знать, выведя все зависимости.
Ты можешь показать обнаруживаемый побочный эффект от main хаскеля? От именно самой main, а не от запуска результата, который возвращает main.

S>>Не вижу связи между цепочкой вычислений и императивом. Композиция функций для тебя тоже императив?

V>Банально инструмент для оного. Этим инструментом явно описывается такая фундаментальная вещь, как детерминированный поток исполнения, что и требовалось. Не всё ли равно, какой инструмент? Аргументы насчет "явных" зависимостей — немного слабоваты. Мы же вполне можем писать без глобальных переменных в том же ООП.
Продемонстрируй побочный эффект от композиции чистых функций.

V>Ведь состояние вполне может быть локально, типа переменных стека или переменных объекта. В этих случаях замыкание или void-методы можно рассматривать как принимающие и возвращающие локальный контекст, в котором объявлены (оно так и есть технически с разной степенью подробности).
А кто говорит о локальном состоянии? Каким образом локальное состояние может быть интерпретировано как побочный эффект вычислений?

S>>Ты что-то путаешь в отношении ввода-вывода хаскеля. Ввод-вывод не вызывается из произвольной функции. Или ты уже про бэкдоры типа unsafePerformIO ?

V>Нет, я про любые IO ф-ии. То, что main организует IO — непринципиально, ведь может же быть возможность, интероперабельности кода на Хаскеле с другими языками (подрбно не копал, но вроде есть проекты для хаскеля генерации то в байткоды, то код на других языках), т.е. какая разница, кто именно запускает IO — main или другая "точка входа"? Хаскель был приведен лишь как пример языка, считающегося чистым функциональным для демонстрации неизбежности императивности в любой программе, целью которой является чуть больше, чем собственная компиллируемость (это я на всякий случай откидываю класс языков, используемых для док-ва теорем).
Ну так продемонстрируй мне императивность функции main хаскеля. А то твоя демонстрация пока не удалась.

V>>>Я пока не увидел, чем IO монада в Хаскеле отличается от тела ф-ии printf.
S>>Монада IO в хаскеле не производит побочный эффект, как это делает printf.
V>>>Про State вообще молчу... эмуляция императива как оно есть.
S>>Эмуляция императива != императив.

V>Дудки! Иначе эмуляцию ФП на современных императивных выч. машинах, близких по принципу работы к машине Тьюринга, нельзя было считать за ФП.

Ты видел в определении императивного программирования ссылку на изменяемость состояния вычислителя? Я нет. Речь о программе, а не о способе ее выполнения.

V>Но тут же все утверждают что "ФП существует!", и вполне согласен, хоть оно и эмулируется на самом деле. Какая фиг разница, с помощью какого инструмента воспроизводится требуемая механика, если в результате можно получить все точно такие же эффекты (например, побочные эффекты в случае State)? Простоты ради предположи, что любой метод объекта в ООП не изменяет состояние объекта, а порождает новое измененное состояние, прямо как в State. И найди после этого отличия.
Если любой метод объекта в ООП не будет изменять состояние объекта (и не только объекта, а вообще обозримого состояния), то по определению императива императива в этом объекте не будет.

S>>Хаскель описывает что нужно получить на выходе main. C описывает как нужно выводить в консоль, притом что на выходе этого описания return 0 в лучшем случае.

V>Сорри, но это уже классика в стиле "тут смотрим, тут не смотрим". Описание в виде ограничений типов — это еще нифига не описание. Это так, легкое ограничение на то, что можно подставить внутрь этого описания. Учитывая вывод типов и прочие плюшки, т.е. даже зачастую отсутствие нотации типов в описании я могу так же прдеположить что "тип" любого локального контекста в императивной программе компилятор "выводит" вполне успешно.
Причем тут ограничения типов? Покажи лучше побочный эффект от main-а хаскеля.

V>На самом деле для док-ва корректности и даже вывода результата "на кончике пера" требуется вовсе не чистота, не иммутабельность (как тут считают некоторые), а гарантия локальности контекста. Т.е. гарантии того, что "кто-то" извне что-то не испортит. Мы когда-то с thesz проходились по этой теме в философии, таки сошлись на том, что в случае иммутабельности всего-навсего чуть проще любые реализации таких "доказывающих" аппаратов. Т.е. отсутствие побочных эффектов — это не обязательное требование для док-ва корретности и прочего из этой области, но достаточное. А коль так, коль есть возможность в императивном виде породить столь же корректную программу (например, с гарантией однопоточности для любого локального контекста), со всеми автовыводимыми зависимостями, то любая императивная запись программы ничем не будет отличаться от чистой ф-ой кроме как в плане требований к сложности компилятора и прочего инструментария.
Проще, не проще — это не предмет обсуждения. Любая императивная запись ничем не будет отличаться от чистой фунциональной? Ну вот тебе printf("\n"). Покажи неотличимую чистую функциональную

V>Кароч, одинаковая будет степень декларативности. И это даже можно будет доказать на примере модели эквивалентного ф-го преобразователя с памятью.
Степень декларативности определяется по соответствию определению декларативности. Модели преобразования памяти не интересуют в контексте обсуждения декларативности. Мы обсжудаем декларативность программы, а не преобразований памяти.

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

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

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

V>Да нет никакого трюка. Это ты описал принцип работы ф-ого преобразователя с памятью. Он состоит из памяти и собсно ф-ии вычисления следующего состояния. Рассуждая таким же образом, императивная программа ведет себя точно так же, получает World на входе, и что-то с ним делает с помощью "сконструированной" компилятором программы. Степень декларативности тут одинаковая.
Извини, но мы обсуждаем декларативность исходной программы а не сконструипрованной компилятором программы.

S>>да, ветвления, рекурсия и прочее. Но каждая из функций, к которым обращается main, не пишет и не читает. Они возвращают функции, которые при выполнении будут писать и читать.

V>Да какая разница? На ф-ом языке операции над ФПВ и есть львиная доля программы.

V>Тем более, что в ленивом языке любая ф-ия по определению возвращает ф-ию, а не результат, которая будет работать лишь при "выполнении" (С).
Отлично.

S>>На этапе построения результата main побочных эффектов нет.

V>Вообще-то есть — это сама технология ленивости. Но тебе эта "побочность" явным образом недоступна, хоть она декларируется в семантике и на нее надо полагаться.
Побочность явным образом недоступна => побочного эффекта нет. См. определение побочного эффекта.

S>>Но порядок их выполнения при выполнении результирующей функции нам важен. Этот порядок обеспечивается композицией функций, из которых строится main. Они представляют собой конвейер по надругательствам над миром. Тут уже не важно, считать ли мир изменяемым, или считать что каждая функция при выполнении создает новую копию мира и где-то есть указатель на текущий мир. Важно что конвейер обеспечивает точный порядок приложения функций к миру.

V>О чем и речь. Используется имеющийся механизм для создания потока вычисления.
О чем и речь.

S>>А в хаскеле так: к окончанию декларативной программы на хаскеле у нас появляется программа для вычислителя. Программа для вычислителя императивна и может работать с изменяющимся миром/консолью.

V>Все это с таким ворохом допущений... Для сравнения, программу на С++ в шаблонах тоже можно считать декларативной, порождающей целевой "вычислитель".

Программа на шаблонах возвращает(вычисляет) вычислитель? Нет?

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

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

S>>Т.е. если доку не читать, то побочных эффектов в printf не будет?

V>Неизвестно,зависит того, null там или другой девайс.
Если неизвестно, то считать что их нет наивно.

V>>>Дык, тело сишной printf тоже не имеет никаких побочных эффектов, является полностью реентерабельной. Если бы были побочные эффекты именно внутри кода printf, она не была бы реентерабельной и многопоточной. И да, в printf таки подается FILE (просто в той перегрузке, в которой не подается, используется глобальная переменная). И отличие в Хаскеля лишь в том, что IO-тип Console не надо возвращать обратно как результат ф-ии, бо это лишь частное требование для механики монады IO, которая не нужна в C++.
S>>printf консоль портит? Портит. А значит побочный эффект присутствует. putChar консоль портит? Нет. Вот в этом и отличие от Хаскеля.

V>Это ты слишком поверхностно рассматриваешь. Давай мы распишем механику ленивости, для начала. А потом модель императивного вычислителя. И только потом будем искать разницу, а не вот так, с высоты птичьего полета да еще под удобным углом.
Ну т.е. как в случае с существованием переменной (понятия ЯВУ) ты ищешь переменную в исполняющемся коде, так и декларативность языка ты определяешь не по конструкциям языка, а по вычислителю?
Ну что мне сказать?

Скажу что я не разделяю такую позицию.

V>>>Вооот... мы дошли до цепочек вычислений в ф-ом программировании, через механизм вложенных вызовов ф-ий, мне даже не пришлось 10-й раз намекать, как для случая РА. Чем не императив? ИМХО, только точкой зрения на происходящее.
S>>f(g(x)) тоже императив?

V>Во избежание спекуляций, без контекста и рассмотрения подробностей отвечать на это не буду. Бо я именно согласен или обсуждать вглубь, или никак вообще. Любой Тьюринг-полный язык императивен по своему определению, например Хаскель.
По какому определению, позволь? не по этому?

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

Раскрой, пожалуйста, как из такой полноты вытекает императивность? Может она вытекает из возможности эмуляции функциональной машины на МТ? Мне не очевидно.

V>То, что в нем есть ФВП, ленивость и иммутабельность — это лишь приятные плюшки, но не более. Неимперативным в принципе может быть только Тьюринг-неполный язык и никакой другой.

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

S>>В том что программа на Хаскеле описывает результат. А императивная программа описывает последовательность действий.

V>Нет, это тебя опять несет на высоту птичьего полета. Программа на Хаскеле для IO всегда описывает именно действия, которые будет совершать эта ф-ия. То, что любая ф-ия на самом деле возвращает ф-ию — это св-во ленивости, а не чистой ф-сти. Тут ты пытаешься всё свалить в кучу. Я видел твою "расшифровку" монады IO, но даже этого не требуется, коль IO ф-ия ленива.
Ленивость не означает императивность, не так ли?

V>А почему из Хаскеля не выкидываешь? Еще раз, ТВОЯ программа не имеет доступа к этим побочным эффектам, прямо как в Хаскеле.

Из хаскеля я вывод не выкидываю потому как он составляющая часть результата main.

S>>Конечно, если считать printf декларативным и не имеющим побочных эффектов, а монады императивными, то тема очень скользкая.
S>>Давай по-маленьку. Как printf влияет на результат функции, в теле которой вызывается? Как влияет putChar из Хаскеля?

V>Про зависимости я ответил даже не помаленьку, а сразу с заделом тут: http://www.rsdn.ru/forum/philosophy/4570092.1.aspx
V>Давай уже там.
Давай. Только я там не увидел ответа.

V>И кстате, можно не только Хаскель. Вон Эрланг торчит в разделе декларативных языков на этом сайте, можно посмотреть ввод-вывод у него — классика ф-ой композиции для целей императивности.

F# тоже торчит в разделе декларативных, так он еще и ООП, никто же не говорит что ООП стало декларативным.

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

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

DG>>>при появлении буферизации, параллельного выполнения, сложных вариантов output file-а и т.д. все эффекты могут выполняться нечетко
S>>По-моему у тебя нечеткое понимание побочного эффекта. Глобальное изменение состояния оно есть или нет. Четко или нечетко — это уже к качеству выполнения изменения, что мы не обсуждаем.

V>Во-первых, необязательно глобальное состояние (это слишком упрощено), а во-вторых — четкость изменения состояния — это архиважно (С) важно для соответствия императивной программы автоматной модели.
сложно не сложно, четко не четко — это незначительные детали в контексте проверки определения.

S>>Ну так можно дойти до того что вычислений без побочных эффектов не бывает, т.к. при вычислениях меняются содержимые регистров процессора.

V>Можно ограничиться машиной Тьюринга. И да, это так, даже для любого сколь-угодно чистого ФЯ. Императивная программа является декларацией для низлежащей вычислительной модели, ничем не худшей декларацией, чем любая ф-ая программа, это можно доказать на примере эквивалентных автоматов. Собсно, именно это я изначально и постулировал.
Мы обсуждаем императивность/декларативность программы на ЯВУ, а не низлежащего вычислителя.

S>>Только какое отношение исполнитель имеет к определению императивного программирования? Покажи связь между программой "1 + 2 * 3" и "оттранслируй, выполни".

V>Эта связь подразумевается и она присутствует by design, коль речь идет о программе, а не о некоем текстовом файле для отсылки его содержимого по почте. Известно несколько техник исполнения программ, выбирай любую: компиляция, интерпретация или всякие их новомодные управляемые гибриды... выбирай не стесняйся.

Можешь показать где в определении императивности/декларативности рассматриваются подразумеваемые связи?

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

V>Фишка в том, что оба этих исполнителя на уровне машины Тьюринга будут эквивалентны.
Допустим
V>Поэтому т.з. на абстрактного "исполнителя" вообще не важна.
Никак не вытекает. "Поэтому" тут нет.

S>>Ты имеешь в виду что select отсортирует таблицу по-месту, изменив тем самым содержимое таблицы? Если нет, то в чем здесь императив?

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

V>И откуда ты решил, что по-месту?
Я предположил что присутстсвует побочный эффект. Если он присутствует, то где бы ему еще быть? Может в "найди таблицу"?

DG>>>а может в декларативной: дай в отсортированном виде значения поля name из таблицы users.

V>Хороший пример, показывающий эквивалентность декларативного определения и определения в терминах инструкций.
Так которая из инструкций императивна?

V>На самом деле, на любом выбранном уровне подробностей эти определения будут эквивалентны. Они будут неэквивалентны лишь тогда, когда попытаемся приписать для любого выбранного примера разный уровень подробностей декларативному и императивному.
На самом деле императивность селекта не показана пока.

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

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

S>>Внутри результирующей последовательности OrderBy может менять что угодно. Внутри исходной — нет.
S>>Между делом, у тебя опять что-то с определениями. Определение чистой функции не допускает побочные эффекты. Т.е. чистая функция не может обладать побочными эффектами по определению. У тебя же она и чистая с одной стороны, и с побочным эффектом с другой.

V>Ну да, например ленивость... Самый что ни на есть побочный эффект, "выпрямляющий" вычисления.
Ленивость (грамотно выполненная) не является побочным эффектом. Грамотно выполненная — это значит что нет никакого способа узнать, были ли выполнены вычисления или нет. Ленивый список в хаскеле — хороший пример. Lazy<T> в дотнете — плохой, т.к. у него есть свойство, по которому можно определить факт вычисления. Возьми, пожалуйста какой-нибудь хороший пример и продемонстрируй побочный эффект от ленивости.

V>Тут уже как-то обсуждалось похожая тема. Кароч, с понятием "побочный эффект" надо быть аккуратней, бо речь всегда может идти только о доступном для осязания/измерения/использования побочном эффекте, иначе можно считать что его нет.
Речь именно о доступных для осязания побочных эффектах. См. определение. Если осязаемого нет — считай что его нет. Например, грамотная ленивость.

V>Именно так эмулируется ФП императивном вычислительном базисе, через допущения относительно видимости побочных эффектов.
Я не понял, о чем речь.

DG>>>и соответственно, не смотря на то, что функция чисто функциональная по определению — результат выражения зависит от истории применения orderby-ев к последовательности
S>>А разве кто-то утверждал что результат применения чистых по определению функций не должен зависить от последовательности их применения?

V>А это уже заворот на 10-й круг в этом обсуждении. Можно смело завязывать, стороны выдохлись.

А чем закончились 9 кругов в конкретно этом аспекте? Таки не должен зависеть?

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

S>Ну т.е. как в случае с существованием переменной (понятия ЯВУ) ты ищешь переменную в исполняющемся коде, так и декларативность языка ты определяешь не по конструкциям языка, а по вычислителю?

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

S>Ну что мне сказать?

Скажу что я не разделяю такую позицию.

Вижу, и некоторые другие не разделяют. Причем, именно последние буквально несколько лет... когда ФП стало популярным, хотя ему столько же, сколько Лиспу.

ИМХО, с некоей непонятной мне легкостью стали пытаться обзывать традиционно рассматриваемый ранее уровень "как" уровнем "что". Т.е. зачем-то для ФП некоторые предпочитают ОПУСКАТЬСЯ в рассмотрении происходящего на один уровень, на уровень неких подробностей алгоритма, называя эти подробности уровнем "что" для низлежащей ф-ой модели исполнения. Ничего более смешного не видел, т.к. этот трюк требует слишком много допущений и натяжек... и к тому же, фактически не имеет аргументов против, когда аналогичное начинаешь совершать с императивным программированием. Бо нет в реальной программе никакого "мира" (как ты приводил пример), а есть вполне конечное мн-во состояний. И высокоуровневая императивная программа — несомненно декларативное описание автомата над этим состоянием. Так же, как и идентичная функциональная. Речь идет лишь об инструменте описания, но оба рассматриваемых инструмента равномощны по-определению, коль позволяют порождать идентичные программы с т.з. низлежащей вычислительной модели. Вглядись в происходящее: не может быть описание алгоритма в стиле control flow быть более декларативным, чем блок-схема алгоритма, бо оба описывают один и тот же граф вычислений с очень близким уровнем подробностей. Единственно что, в некоторых местах control flow не задает явно порядок вычисления, дык уже звучал аргумент, что тот же С++ тоже не задает явно порядок вычисления аргументов ф-ий, т.е. однозначно интерпретируемый исходный код, не содержащий UB, будет обладать теми же характеристиками, что аналогичный ф-ий код, для которого не важен порядок вычисления аргументов. Понимаешь что происходит? Вот эту миниатюрную с т.з. низлежащей вычислительной модели разницу в уровнях описания (возможное местами абстрагирование от порядка исполнения веток... но лишь местами) пытаются выдать за водораздел м/у декларативным и недекларативным. Это искажение самого термина "декларация".

V>>Во избежание спекуляций, без контекста и рассмотрения подробностей отвечать на это не буду. Бо я именно согласен или обсуждать вглубь, или никак вообще. Любой Тьюринг-полный язык императивен по своему определению, например Хаскель.
S>По какому определению, позволь? не по этому?
S>

S>В теории вычислимости исполнитель (множество вычисляющих элементов) называется тьюринг-полным, если на нём можно реализовать любую вычислимую функцию.

Гы, поднимись в определениях на один уровень раньше и посмотри, что есть вычислимая ф-ия.
Своими словами — это та, для которой существует конечная программа в терминах пошаговых инструкций над идеальной машиной (с бесконечной памятью).

S>Раскрой, пожалуйста, как из такой полноты вытекает императивность?

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

Еще не ощутил всю иронию происходящего?
Уровень "что" для любой полноценной программы, пусть даже на функциональном языке, т.е. любое ТЗ для нее — это описание поведения эквивалентного автомата. Вот прямо отсюда можно начинать сворачивать все обсуждения относительно попыток приписать уровень "что" любым другим уровням, кроме относительных ТЗ в иерархии программных единиц... потому что иной подход потребует неких натяжек и обязательного условия не рассматривать ничего уровнем выше и ни дай бог ничего уровнем ниже. А я на это пойти не могу.

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

V>>То, что в нем есть ФВП, ленивость и иммутабельность — это лишь приятные плюшки, но не более. Неимперативным в принципе может быть только Тьюринг-неполный язык и никакой другой.

S>Пруф? Или хотя бы направление рассуждений доказательства? Пока ты не доказал что хаскель императивен, я считаю его существование опровержением твоего тезиса.

Пруф по ссылке выше, а так же курить эквивалентность автоматов. И на всякий случай (заранее) можно покурить эквивалентность структурных автоматов и абстрактных, но можно поверить и на слово.

S>>>В том что программа на Хаскеле описывает результат. А императивная программа описывает последовательность действий.

V>>Нет, это тебя опять несет на высоту птичьего полета. Программа на Хаскеле для IO всегда описывает именно действия, которые будет совершать эта ф-ия. То, что любая ф-ия на самом деле возвращает ф-ию — это св-во ленивости, а не чистой ф-сти. Тут ты пытаешься всё свалить в кучу. Я видел твою "расшифровку" монады IO, но даже этого не требуется, коль IO ф-ия ленива.
S>Ленивость не означает императивность, не так ли?

Ленивость — это изолированный мини-автомат, это та самая классическая ф-ия с памятью, которая и зовется автоматом. Именно ленивость позволяет Хаскелю упорядочить последовательность вычислений, делая их детерминированными, т.е. это именно инструмент детерминированной реализации программы по вышестоящему императивному ТЗ. Т.е. таки ленивость не то, что означает императивность, она именно для возможности привнесения императивности и существует, см поведение I-комбинатора в ленивой среде. Это такой комбинатор, для которого можно установить необходимый и достаточный порядок вычисления аргументов вместо произвольного. Теперь срослось, где именно идет переход из потенциально "параллельного" в "последовательное"? Фишка ленивости в том, что позволяет безболезненно переносить наработки лямбда-исчисления для использования в программу, где требуется детерминированная последовательность операций. В общем, иначе было бы гораздо сложнее реализовать исходное императивное ТЗ на чистом ФП, если бы не ленивость. Пришлось бы бороться с комбинаторным взрывом при вычислении (в общем случае рекурсивном) всех аргументов всех операций. И не факт, что программа имела бы останов...

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

V>>Ну да, например ленивость... Самый что ни на есть побочный эффект, "выпрямляющий" вычисления.
S>Ленивость (грамотно выполненная) не является побочным эффектом. Грамотно выполненная — это значит что нет никакого способа узнать, были ли выполнены вычисления или нет. Ленивый список в хаскеле — хороший пример. Lazy<T> в дотнете — плохой, т.к. у него есть свойство, по которому можно определить факт вычисления. Возьми, пожалуйста какой-нибудь хороший пример и продемонстрируй побочный эффект от ленивости.

Зачем же от ленивости-то? Я сейчас с удовольствием почитал собственный аргумент, но в твоей озвучке. Итак... если нет возможности ощутить как-либо побочный эффект, он есть, или его нет?

V>>Тут уже как-то обсуждалось похожая тема. Кароч, с понятием "побочный эффект" надо быть аккуратней, бо речь всегда может идти только о доступном для осязания/измерения/использования побочном эффекте, иначе можно считать что его нет.
S>Речь именно о доступных для осязания побочных эффектах. См. определение. Если осязаемого нет — считай что его нет. Например, грамотная ленивость.

V>>Именно так эмулируется ФП императивном вычислительном базисе, через допущения относительно видимости побочных эффектов.
S>Я не понял, о чем речь.

Ну т.е. побочные эффекты таковы, что необнаруживаемы ср-вами языка программирования. Но они есть, бо язык тьюринг-полный.

DG>>>>и соответственно, не смотря на то, что функция чисто функциональная по определению — результат выражения зависит от истории применения orderby-ев к последовательности
S>>>А разве кто-то утверждал что результат применения чистых по определению функций не должен зависить от последовательности их применения?

V>>А это уже заворот на 10-й круг в этом обсуждении. Можно смело завязывать, стороны выдохлись.

S>А чем закончились 9 кругов в конкретно этом аспекте? Таки не должен зависеть?

Не закончились, судя по всему.

Просто уже раз 10 говорилось, что порядок выполнения ф-ий можно задать явно, прямо как список инструкций в императивном программировании. А твой "мир" протаскивать как монаду State, например. Получишь выражение одного базиса через другой с идентичным уровнем подробностей. ЧТД. Т.е. никакой базис ни над каким сверху не стоит в отношении "что"->"как", если брать выражение одного через другой. Фундаментально здесь то, что вот это вычисление вложенных ф-ий происходит не одномоментно, а упорядочено, т.е. начинает быть наблюдаемым точно такой же фактор времени, смены стадий вычислений, можно оперировать понятием "контекст вычисления" (см замыкания), что суть мгновенный снимок текущего состояния вычислителя и прочее и прочее. Там всей разницы, что в чистом ФП мы получаем копию вычислителя, а в императивном — оперируем тем же самым. Но! При таких строго последовательных вычислениях (например, без лямбд и продолжений, как в императивном программировании) у нас будет оставаться только копия вычислителя, а оригинал будет все время выкидываться... Вопрос на засыпку: как определить достоверно, что мы выкинули, копию или оригинал? А нельзя ли выкидывать сразу копию?

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

DG>>а разговоры о терминах — это всегда деструктивный разговор, не создающий нового знания.
S>Деструктивный разговор — это употребление общеизвестных терминов в недоступном для собеседника смысле. Я просто не пойму о чем ты разговариваешь. Слова знакомы, а суть противоречит тому что я знаю. Какого разговора ты хочешь без согласования терминов? О чем? Ты будешь говорить о своем, а я недоумевать, как такое возможно, думая о совершенно другом?

S>Если хочешь, что бы тебя понимали, нужно договориться с терминами.

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

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

V>Гы, поднимись в определениях на один уровень раньше и посмотри, что есть вычислимая ф-ия.
V>Своими словами — это та, для которой существует конечная программа в терминах пошаговых инструкций над идеальной машиной (с бесконечной памятью).
МТ эквивалента лямбда-исчислению, блок схемам и ЧРФ.
Так что можно считать вычислимой функцией ту, которую можно записать в виде ЧРФ.
Вычислимость — свойство самой функции, императивность — свойство записи алгоритма вычисления.

V>Ленивость — это изолированный мини-автомат, это та самая классическая ф-ия с памятью, которая и зовется автоматом. Именно ленивость позволяет Хаскелю упорядочить последовательность вычислений, делая их детерминированными, т.е. это именно инструмент детерминированной реализации программы по вышестоящему императивному ТЗ.
Прямо немерянное количество заблуждений в одном предложении.
1) С чего это ТЗ императивно? Как раз хорошее ТЗ максимально декларативно. То есть не описывает конкретных шагов для получения результата.
2) С чего это ленивость- "автомат"? Может у них какие-то общие свойства есть?

V>Т.е. таки ленивость не то, что означает императивность, она именно для возможности привнесения императивности и существует
Опять какой-то бессвязный набор слов.
Императивный алгоритм — тот который задает последовательность шагов, изменяющих некоторое состояние для достижения результата. Любой императивный алгоритм можно представить в виде структурированой блок-схемы.

Ленивость заключается в том что агрументы функции вычисляются не при вызове, а при обращении. Это как раз дает непостоянную последовательность вычисления. То есть как раз в виде блок-схемы записать не получится.

V>Это такой комбинатор, для которого можно установить необходимый и достаточный порядок вычисления аргументов вместо произвольного.
То есть ленивость таки не соответствует фиксированному порядку, а значит не является императивным.

V>где требуется детерминированная последовательность операций
Требуется она в одном случае — при общении программы с внешним миром.

V>В общем, иначе было бы гораздо сложнее реализовать исходное императивное ТЗ на чистом ФП, если бы не ленивость.
О чем ты? Бери F# и Haskell, покажи в чем леность помогает общаться с внешним миром.
И снова напомню что хорошее ТЗ максимально декларативно.

V>Пришлось бы бороться с комбинаторным взрывом при вычислении (в общем случае рекурсивном) всех аргументов всех операций. И не факт, что программа имела бы останов...
Это ты о чем вообще? ЧРФ эквивалентны блок-схемам, причем без всякой ленивости

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

V>>Для состояния твоей программы — несомненно одинаковы. Я ведь не зря привел пример ввода-вывода в ф-х языках.
S>А с каких это пор stdout перестал быть состоянием моей программы?
S>Вот я бы, скажем, отказался принимать у вас программу с перепутанным порядком вывода в консоль — она нарушает ТЗ.

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

V>>Дык, тело сишной printf тоже не имеет никаких побочных эффектов, является полностью реентерабельной. Если бы были побочные эффекты именно внутри кода printf, она не была бы реентерабельной и многопоточной.
S>

Совершенно необязательно. Вы опять делаете неявные предположения, которые очевидно неверны. Попробуйте формально доказать, что наличие побочных эффектов запрещает функции быть реентерабельной и многопоточной.

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

V>>Вооот... мы дошли до цепочек вычислений в ф-ом программировании, через механизм вложенных вызовов ф-ий, мне даже не пришлось 10-й раз намекать, как для случая РА. Чем не императив? ИМХО, только точкой зрения на происходящее.
S>Тем, что в императиве все вычисления зависимые, если нам не удаётся доказать обратное (что в общем случае крайне трудно). А в декларативном программировании у нас есть только те зависимости, которые мы описали явно.

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

V>>Это ес-но, речь шла о том, где заканчивается декларативное и начинается императивное. Твои побочные эффекты могут быть нам недоступны, т.е. не влиять на элементы нашей программы, примерно как в монаде IO. В чем тогда отличие якобы декларативного Хаскеля в случае этой монады, и императивной программы, которая использует только "чистые" ф-ии и процедуры, не изменяющие неявно состояния нашей программы?
S>Императивная программа в любом случае опирается на состояние некоторого "вычислителя". Скажем, в дотнете и яве вся семантика описана в терминах виртуальной машины и последовательности её состояний.

Функциональная тоже опирается на некий контекст, который разный в разных точках вычисления.

V>>Первое предложение ты написал поторопимшись. У нас уже есть низлежащая аппаратура, которая близка по принципу работы машине Тьюринга, поэтому последовательность инструкций мы имеем как вычислительный базис. Отличие ф-ых языков от императивных в том, что ф-ые скрывают от программиста внутреннюю работу с состоянием, т.е. на уровне пользовательской программы побочных эффектов НЕТ. Я же привел printf не случайно, показав точно такой же случай, что на уровне пользовательской программы нет никаких побочных эффектов.
S>Что такое "уровень пользовательской программы"?

Доступный тебе из твоей программы из используемого языка.

S>>>В частности, можно вычислить первые N чисел Фибоначчи не за N^2, а за N, несмотря на явно рекурсивное определение этой функции.

V>>Это св-во ленивости, а не ф-сти. Точно такой же эффект достижим и в императиве аж бегом, если навертишь свой некий тип Lazy<T>. Не смущает, что сам механизм ленивости основан на запоминании состояния в точке вычисления?

S>Это не свойство ленивости. Это возможность выполнять преобразования программы, опираясь на гарантии соответствия. Тот самый Lazy<T> применим только там, где порядок вычислений неважен. Если используемые в вычислении функции пользуются побочными эффектами, применение Lazy<> приведёт к нарушениям логики.

Сам Lazy<T> — это один сплошной побочный эффект. Всё преобразование заключается в запоминании состояния в точке вычисления.

V>>Дык, если ширина каждого слоя узлов ровно 1, то порядок будет ровно 1. Я же не зря этот пример привел, подводя к нужной мысли... но ты и сам его показал на примере цепочки printf.
S>Ну как можно быть таким невнимательным? В примере с printf ширина каждого слоя узлов, очевидно, 2.

Один из них, Console, все время передается выше как результат предыдущей операции.

S>И ваша мысль, к которой вы так тонко подводили, малоинтересна: да, есть такой частный случай, когда выражение представлено в виде последовательности унарных операций. Вот в нём декларативная программа однозначно сведётся к императивной. Увы, в природе такие случаи встречаются исчезающе редко.

Нет, я имел ввиду показанный тобой случай.

S>Да пожалуйста. Мне эта тема вообще неинтересна. Вы упорно отказываетесь понимать одну простую вещь: вся могучесть РА как раз в том, что она насквозь декларативна, и позволяет выполнять широкий класс оптимизаций.

Она декларативна, угу, но лишь по отношению к уровню, который будет ее реализовывать. Это ты зашел на очередной круг.

V>>Ага, вот где путаница, только не у меня. Для случая join мы имеем те же N, а не M (по крайней мере одна из сторон соединения просматривается целиком для любого из join).
S>У вас.

V>>Я словесно имел ввиду, что полная формула в пределе такая:
V>>K1 * O(N * log N) + K2 * O(N), где K2 обычно гораздо гораздо хуже K1.
S>1. И куда у вас делась кардинальность второго отношения? У нас отношения с кардинальностями N и M. При этом M итерируется полностью, а среди N мы выполняем поиск.
S>2. Ну и где же обещанные O(N*M)? Внезапно оказалось, что никаких умножений в стоимости join уже нет.

Это от того, что ты рассматриваешь лишь один join из 6-ти возможных, постоянно скипая зачем-то мой ответ тебе на один и тот же вопрос. Похоже на какое-то юление.

V>>Очередной бред. При чем тут "пессимистика" и логические чтения?
S>При том, что логические чтения превращаются в физические с вероятностью, отличной от 1.

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

S>Реальный запрос никогде не будет выполнять больше физических чтений, чем логических.

Вот это открытие... А как же так получилось?

S>Поэтому если я вижу оценку в 8000 логических чтений, это не означает, что время выполнения запроса будет равно 8000 поделить на IOPS моего диска.

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

S>Cache Hit Ratio может быть достаточно высоким для того, чтобы сократить эту оценку на порядок.

V>>обычно бывает ровно наоборот, зависимости для малого кол-ва данных обычно гораздо похуже, чем для асимптотики сверху. Ты этого не знаешь, поэтому порешь ерунду насчет "пессимистичности"... Ровно наоборот, оценка сверху зачастую — самая оптимистичная, т.к. для нее отбрасываются незначащие компоненты для бесконечно большого N. И эта оценка именно для логических чтений, независимо ни от какого cache hit ratio для твоих "больших размеров". Характерно, что для малого кол-ва данных тоже может случиться низкий cache hit ratio, например, если каждая страница в некоей выборке будет нужна лишь однажды, и не случится к ней того самого повторного обращения...
S>Я рекомендую прекратить делать предположения о том, чего я знаю, а чего нет.

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

V>>Оба предела асимптотики, выраженной в логических чтениях, что нижний, что верхний, никак не зависят от cache hit ratio.
S>Правильно. Я говорю о переходе от логических чтений к физическим.

Угу... Сдается мне, что мои замечания в предыдущих постах просто не воспринимались...

V>>Ты сейчас подставляешься по самое нихочу, заканчивай умничать, где не ходил еще ни разу...
S>Прекратите паясничать. Я вас уже столько раз ткнул носом в фактические идиотизмы, а вы по-прежнему пытаетесь понтоваться. Зачем?

Мой идиотизм — это в плане заблуждений относительно разметки страниц твоей любимой СУБД? Ты бы поосторожнее с такими вещами, бо они сами по себе тебя подставляют. Находясь на твоей стороне спора, я бы это вычислил в одну итерацию, что и делаю регулярно с твоими заблуждениями, а тебе потребовался примерно десяток.

V>>Есть асимптотика в логических чтениях — я с ней и не спорю.
S>Более того, логические чтения можно рассчитать точно, а не в терминах асимптотики. И формулы будут практически такие, как мы с вами обсуждали.

В том то и дело, что не будут такие же. Там тупая формула по статистике, а вид операции для оценки уже не важен, бо весовая ф-ия не оперирует видами аналитик, она оперирует абсолютными значениями на выходе весовых ф-ий. Вся аналитика остается на этапе составления весовых ф-ий и больше ее не будет.

S>Забавно вы юлите. Ваши наблюдения про N*M для сложности join — тоже насчёт "вполне осязаемых соотношений"?

Ты дважды скипнул мои пояснения насчет джоин и теперь строишь мину при плохой игре. В предыдущем посте я на это уже отвечал.

V>>Фишка в том, что O(M*logN) не зависит от cache hit ratio даже для физических чтений, бо O — это ограничение асимптотики сверху. Но оценок может быть много, не обязательно оценка сверху. Ты же сам давал ссылку на что-то там по оценке сложности (хоть я и не ходил по ним, бо теорию, в отличии от, знаю неплохо, а оценка сложностей конкретных алгоритмов не интересует пока не столкнусь с ними).
S>Теорию вы, простите, знаете на три с минусом. Если вы стоимость join прикидываете на глаз с такими ошибками, то игнорировать шанс почитать учебники не стоит.

Мде? А мне показалось, что ты из всех операций join подразумеваешь только одну. И на основе этого хочешь поставить мне тройку.

Хороший бы вышел из тебя преподаватель, нечего сказать. Был у нас такой один, требовал чтобы отвечали как он давал иначе сразу трояк. А если дашь более общий вид формулы — вообще выгнать может.

V>>Наблюдения — это объективная реальность.
S>Зато их интерпретация у вас не лучше, чем в анекдоте про Василия Ивановича, Петьку, и таракана.

Таки в том посте я давал не интерпретацию, а именно что наблюдения. Относительно ширины данных и их кол-ва.

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

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

V>>Да ладно тебе, своими "идите почитайте" ты нарываешься везде и всюду, где бы я не встречал твои посты. Заслужено получаешь в ответ. А здесь опять попытался сумничать не по теме обсуждения.
S>Так что ж я могу сделать, если вы не идёте и не читаете?

Делиться информацией очевидно, чтобы все ходы были записаны...

V>>Я вижу крайне узкоспециализированный опыт и весьма оригинальные эффекты из-за этого, см начало обсуждение. Например о ненужности реляционной модели, и о прочих вредительских советах.
S>Где вы нашли "о ненужности реляционной модели"? Процитируйте.
V>>Так всегда бывает, когда сложную и объемную область изучают на примере конкретного продукта, непонимая, где и откуда растут ноги, и почему именно так.
S>Удивительное дело. У меня вот как раз полностью обратное впечатление.
S>Скажем, идея о том, что кластерный индекс требует фиксированного размера записи сама по себе может появиться только от непонимания, откуда растут ноги, и почему именно так.

Скажем так, я видел много разных кластерных индексов до MS SQL, и прекрасно понимал, в чем их цимус.

S>У меня такой идеи никогда даже не появлялось. Наверное, это оттого, что я плохо понимаю дизайн СУБД и причины, по которым принимаются те или иные решения в них. К сожалению, суровая практика показала, что мои некомпетентные идеи ближе к истине, чем ваши.

В обсуждении конкретной СУБД? Возможно... В принципе, учитывая заложенную дороговизну операций ввода-вывода в MS SQL действительно, возможно будет эффективней использовать неэффективную структуру данных с лишним уровнем индирекции.

V>>Дать тебе ссылку на устройство связанного списка?

S>Ну, как только я перестану его понимать, или скажу глупость типа "стоимость вставки в связный список — это O(N)" — сразу давайте ссылку.

Ну так согласно доке, сервер старается поддерживать равномерное заполнение кластерного индекса. Т.е. мало выделить +1 страницу, надо еще данные в ближайших таблицах распихать. Если ты не прочитал целиком в том месте, самое время вернуться и освежить.

V>>Еще раз, как именно происходит преобразование структурных формул SQL к вариантам планов запросов, которые ЗАТЕМ оцениваются оценочной ф-ей.
S>1. Выполняется парсинг запроса в AST
S>2. Выполняется преобразование AST в дерево логического плана исполнения запроса (про то, как применяется паттерн Visitor, надо рассказывать?)

Да, если можно. Хотя не надо, мне надоели бесконечные итерации, лучше я расскажу, чтобы не растягивать. Вот прямо здесь ты пропустил важный пункт — это выпрямление кванторов общности и кванторов существования в исходном запросе. В этом и заключается построение логического плана запроса. MS SQL тормозит в сравнении с файловыми базами далеко не всегда. Он сливает им только на простых операциях, типа выборки из одной, максимум двух таблиц по натуральному join. Зато когда идут вложенные кванторы, да еще с разными перекрестными зависимостями/ограничениями на разных уровнях... то на движке JET приходится по десятку раз переформулировать один и тот же запрос, крутя его граф во все стороны, чтобы получить приемлемую эффективность, а MS SQL стабильно дает почти один и тот же план запроса, невзирая на формулировку. Ему даже join писать не надо, пиши таблицы через запятую, он сам разберет, а JET в этом месте просто уйдет в глубокий своп. Так вот, логических планов запросов тоже несколько, после выпрямления всех кванторов, т.е. после сведения их ко всяким пересечениям, произведениям и ограничениям. Итого, идет как минимум два уровня перебора вариантов. А далее можно как в классике, например как в теории игр использовать оценочный аппарат с отсечением — ничего нового. Я потому и отбрасываю конкретный вид оценочной ф-ии, что она не принципиальна в после установления к какому классу сложности относится конкретное вычисление и какой аппарат использовать. Вряд ли ошибусь, если предположу использование такого раздела нечеткой логики как теория приближенных вычислений (бо статистика почти всегда врет, если не только что пересчитали, т.е. стоит задача выдавать решение в этих условиях).

S>3. Начинается построение физического плана запроса:
S>3.1. Порождаются различные версии физического плана. Они похожи на выражения РА, вот только в аргументах у них немножко другие объекты, чем отношения, и операции немножко другие, чем в РА

А вот тут уже и есть та самая скука. Механика.

S>3.1.1. В частности, в отличие от РА, для аргументов очень важен порядок сортировки кортежей — от него зависит применимость операций

Это атрибут физической модели и прямиком может топать как параметр в некую ф-ю оценки. РА здесь не при чем. По конкретной таблице есть требуемая операция в терминах РА — выборка / проекция / ограничение. Никаких других операций над конкретной таблицей НЕТ. (переименование оставлю за бортом). Теперь эти операции требуется расписать в индексах, при том что зависимостями исходной таблицы и индексов СУБД полностью владеет. Вот тебе тот самый второй уровень вложенности итерации перебора планов запросов.

S>3.1.2. В отличие от РА, для операций важны применяемые алгоритмы — это влияет не только на оценку стоимости, но и на отсортированность результата

Это опять ты оперируешь атрибутами физической модели. Атрибут для каждой конкретной структуры является константой, а для оценочной ф-ии — параметром.

S>3.2. Процесс порождения не пытается построить все возможные планы. Это бы привело к слишком большим затратам на оптимизацию. Применяются как эвристические методы отсечения, так и основанные на оценках стоимости планов.
S>3.3. Как только оптимизатор найдёт приемлемый физический план выполнения (по оценкам), он передаёт план на исполнение.

Для решений на основе векторного спуска или отсечений в задачах оптимизации — как только пройдет экстремум. Для простых случаев экстремум находится через обычное решение задачи (матрицы) линейного программирования, ХЗ используется ли это в MS SQL.

S>Вы, пытаясь доказать свои заблуждения, выделяете фазу генерации вариантов планов запросов в отдельный этап. Ок, даже если бы это было так, всё равно РА было бы недостаточно.

Таки итерация планов запросов — это несомненно самый сложный и затратный этап. По этой теме, очевидно, тебя можно пинать с самых первых постов. Неужели query rewriting является таким уж незначащим шагом? Да именно здесь запросы из стоимости в часы превращаются в запросы стоимостью доли секунд... Процедура затратная, однако, бо перебор по большому итоговому дереву обычно... Построение AST в сравнении с этим этапом не видно и под микроскопом, и это подтверждают файловые базы, не располагающие оптимизаторами — они начинают выдавать данные фактически мгновенно. Немудрено, SQL крайне прост в парсинге, и сложность его выражений обычно смехотворна с т.з. формальных грамматик.

S>Я вам с самого начала говорил — то, что там применяется, только похоже на РА. Основы, несомненно, те же.
S>Однако, используются расширения РА, что вы упорно отказываетесь признать. Если bookmark lookup и можно заменить на операцию join, если добавить к таблице и к индексу "невидимый" атрибут RID, то для операции sort никакого аналога в РА найти не удастся.

А почему бы не пройтись предварительно по предложенным Коддом расширениям? Чтобы составить представление, чем же именно и куда расширяют? Расширения-то предлагались и они есть де-факто, только совсем с другой стороны, не на этом уровне. Предлагались расширения как ср-во описания более высокоуровневых операций и далее итеративно. Короче, абсолютно все предлагаемые расширения по-определению являлись "синтаксическим сахаром" и были выразимы в базисе.

Тебе не нужен никакой sort на уровне PA, тебе нужно только обозначить вид соединения, а уже низлежащий слой пусть примет решение, исходя из прогноза по данным — будет он строить индекс, или и так пойдет. Я вижу, что включение в план запроса, наглядности ради, подробностей операций, просто сбивает тебя с толку. Понимаешь, породить sort из задачи join — не нужен вообще никакой специальный мат-аппарат, просто некое пороговое значение кол-ва элементов из оценки статистики, и решение да/нет — строим индекс или не строим. В сравнении с перебором вариантов плоского представления кванторов — это полное тьфу. Если сервер умудряется составлять на десятки вариантов формулировок одного и того же запроса один и тот же план — то он перебирает никак не меньше десятка вариантов, правильно? А я бы предположил цифру еще на порядок менее скромную.

V>>Действительно, при переборе планов запросов некоторые ветки перебора могут отсекаться довольно рано, но это было бы известно тебе и так, если бы ты понимал, как именно эти планы строятся по выражениям SQL. И да, в твоей ссылке такой информации нет.
S>Это потому, что вы проигнорировали ссылку на Гарсиа-Молина.

Если ты про ту, где отметился Ульман в соавторстве — то это не самая лучшая ссылка. И таки принято автором считать Ульмана, а остальную братию в соавторстве. И таки хотелось бы узнать, на что именно ты там пытался сослаться? На какой раздел?

S>Угу. Вот только в реляционной модели зависимости — это некоторые факты, которые можно вычислить. А не свойства отношений, хранимые в некоторой форме.

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

V>>Давай прежде посмотрим, как работает memory mapped file, а потом будем делать выводы.
S>Куда именно вы предлагаете посмотреть?

На принципы виртуального ввода-вывода для популярной архитектуры. Memory-mapped файл — это фактически "родная" технология ввода-вывода для аппаратуры.

V>>Не все-равно в затратах копирования данных во внутренний кеш операционки.
S>Вы опять ту же песню на новый лад. Ок, давайте сравним затраты времени на копирование 64кб данных в памяти и запись 64кб на диск.
S>Как вы думаете, каково будет соотношение Thdd/Tram?

Если в затратах проца, то в первом случае когдаздо экономнее, чем во втором. Операции с файловой системой тривиальны алгоритмически, остальное делается само через DMA. К тому же, прокачка через DMA не портит кеш процессора, в отличие от операций копирования, да и на современном рейде суммарная буферная емкость даже в винчестерах уже ощутима. В общем, перелопачивать "вручную" данные весьма накладно. Ты так и не понял замечание про 1 всего измененный байт.

V>>К тому же, в случае memory mapped file мы даем операционной системе решать, как ей лучше сбрасывать данные, а лучше драйвера ввода-вывода все-равно никто не знает.
S>Ну, если, конечно, нас не интересует целостность данных — то да, таки драйвер ввода-вывода рулит.
S>У MS Access всю жизнь была, скажем так, весьма примитивная recovery model. Поэтому можно, наверное, было некоторые решения отдать на откуп драйверу ввода-вывода.

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

V>>В принципе, там суть не в IOPS, разумеется, а в том, что сервер, в отличие от ОС, знает, когда у него конец транзакции, поэтому использует копии страниц кеша, а не пользует память кеша страниц ОС напрямую, как в случае memory mapped file. Твои экстенты — они сугубо для уменьшения кол-ва дорогостоящих операций ввода/вывода, чтобы копировать за раз больше страниц... Но не на диск, разумеется, бо это не серверу решать (вот почему Oracle давно уже разраобтал свою файловую систему, чтобы держать всё под конторлем), а для того лишь, чтобы уменьшить кол-во системных вызовов, каждый из которых относительно дорогой (даже холостой вызов этого последовательного АПИ ввода-вывода стоит единицы микросекунд).
S>О да. Действительно. Единицы микросекунд мы экономим там, где сам вызов стоит миллисекунды. Кто бы мог подумать.

Смотря что происходит в эти миллисекунды. Если поток ожидает или вызов асинхронный — это одно, а если активно работает — совсем другое. Для многозадачной ОС и СУБД сверху — разница большая. К тому же,
про буферы рейдов уже напоминал. Как раз размеров буферов сейчас хватает, чтобы сектор диска к головке подъехал, но IO при этом не ждал завершения операции.

S>"Мои екстенты" были, естественно, применены для оптимизации алгоритма поиска свободных страниц при размещении. Ну и для того, чтобы повысить шансы на последовательное чтение — мы это уже обсуждали.

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

V>>И кстати, IOPS на SSD-массивах скоро будет уже под миллионы и выше, при том, что пропускная способность DMA ограничена, так что тебе стоит пересмотреть свои представления.
V>>http://www.ixbt.com/news/hard/index.shtml?15/38/75
S>Ок, интересные новости. Это, несомненно, повлияет на дизайн СУБД в ближайшие лет 10. Тем не менее, общие соображения останутся прежними. И мои представления легко пересмотреть — потому что они хорошо структурированы

Я заменю в них маленький кусочек, и всё будет в порядке. А вот вам придётся ставить заново все эксперименты — или выбросить накопленный опыт на помойку.

Ес-но, будут заново все эксперименты. Так и только так и никак иначе.

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

V>>Основная фишка memory-mapped file в том, что в этом случае мы имеем меньше слоев IO, чем при последовательном способе, т.е. банально меньше копируется данных м/у дисковым кешем операционной системы и нашими буферами (страницами). Я уверен, что в MS SQL будет пересмотрен способ работы со страницами в ближайших версиях, бо сейчас их способ уже малость архаика.
S>Можно подумать, memory mapped files были придуманы недавно.

— Не было столько памяти, сколько сейчас;
— не было таких технологий оптимизации ввода-вывода на уровне операционки, в условиях большей доступной памяти, как сейчас;
— ввод-вывод был узким звеном, а сейчас некоторые рейды способны выдавать и принимать быстрее, чем поспевают обрабатывать топовые процессоры.

Для сравнения, если раньше даже на более слабом проце при компиляции С++ у меня редко было более 50% загрузки проца, бо он "отдыхал" на ввод-выводе, то сейчас при куда как более мощном многоядерном проце у него заметно выше загрузка! Более 75% стабильно, а это уже ого разница.

Ну и экономия таблиц маппинга повышает эффективность: http://msdn.microsoft.com/en-us/library/windows/desktop/aa366720(v=vs.85).aspx согласно принципа работы виртуальной памяти.
А с эффективностью сейчас малость траблы. Все устойчиво имеют некое проседание эффективности после перекомпиляции на x64.

V>>Пффф, по кругу... Тебе осталось показать, что запись результата мощности O(N*M) будет дешевле сортировки одной из компонент.
S>Ну откуда же у нас взялось N*M в результате, если мы выполняем join по равенству атрибута?

А как же остальные виды join?
(нравится мне эта ненавязчивая тема

)

V>>В рантайм warning-ов не бывает, зато бывают исключения. А компиляторы? — все популярные.
S>Вас не затруднит привести опции компилятора, которые заставляют его выбрасывать исключения при целом переполнении для gcc и msvc?

Для MSVC
http://msdn.microsoft.com/en-us/library/8wtf2dfz(VS.90).aspx

Для GCC лучше поясню, а то из доки с непривычки будет непонятно:
-ftrapv
-fnon-call-exceptions
Два этих параметра надо одновременно. Без второго первый не выбросит исключение.

V>>А если по-делу: предпросмотром на этом сайте кто-нить займется или теперь уже никогда?
S>Вы зачем это у меня спрашиваете?

Дык, RSDN-тим или как? Я бы и сам подправил давно уже, там дел на несколько минут.
Просто раздражает читать собственные очепятки...

S>Совершенно верно. Зачем же вы продолжаете спорить? Одной рукой вы признаёте наличие двух (и более) моделей; одновременно с этим другой рукой упорно отрицаете наличие границы между ними. Получается, даже простейшие вещи на современных ЯП нельзя писать, основываясь на предположениях школьной арифметики относительно поведения целых чисел.

Я не отрицаю границ. Я говорю о том, что кол-во связей различных разделов IT очень велико. Повторное использование знаний тоже крайне велико, и это объективная реальность. Что я пальцы оловом обжигал в студенчестве — примочку гитарную проектировал, что потом чисто-программный джиттер-буффер многоконтурный отлаживал в VoIP — занимался одним и тем же из САУ. Все эти осциллографы и умение зачистить контакт с одной стороны и знание конкретного ЯП с другой — шелуха это всё... инструментарий и не более того. А в плане границ ПО и железа всё еще печальнее. Одних только способов реализации конечных автоматов я знаю около десятка, каждый из который все дальше от железа и все ближе к микропрограммам и потом к обычному ПО. Четкой границы нет вообще. По крайней мере в своем стаже я как раз по всему градиенту тщательно прошелся. Одна и та же модель абсолютно на любом уровне. Автомат он и в Африке автомат, что на регистрах, что в ООП-парадигме.

Кароч, примеров-то можно привести много... Но суть одна, если взять все знания из области IT, то ты получишь граф из довольно счетного кол-ва узлов, но огромного кол-ва связей м/у ними. Увидеть "четкую границу" можно лишь при невладении целыми кластерами таких узлов... в этом месте будет космический вакуум и несколько световых лет до следующего знакомого кластера узлов. Даже по обсуждаемому вопросу: пройдись по теории сложности, теории игр, линейному программированию, АИ, нечеткой логике и т.д. Потом попробуй "четко отделить" задачу оптимизации плана запросов от этих разделов. С удовольствием запасусь попкорном и понаблюдаю за этими попытками.

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

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

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

Ммм... да вроде поразрядную арифметику как раз в школе и изучают, если склероз не изменяет, где-то в 1-м классе... Оно уже в куче by design.

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

S>Ошибки случаются оттого, что свойства одной модели слепо переносятся на другую модель. Ну, примерно как оценки свойств ISAM-модели переносятся на модель кластерных индексов.

Кластерный индекс — он и в африке кластерный. Для меня явилось лишь неожиданностью нефиксированный размер строки. Это минимум вдвое проседание выборки из страницы из-за +1 к косвенности.

S>Из-за этого возникают предположения типа "вставка в кластерный индекс требует O(N) записей на диск", и принимаются неверные архитектурные решения.

Именно так? А можно цитату целиком?

S>И вот тут ключ к успеху — понимать, какие свойства относятся к чему. К примеру, "использование более одного индекса с низкой селективностью при поиске в одной таблице дороже, чем сочетание index seek с bookmark lookup и filter" как правило работает в случае хеш-индексов и btree-индексов. А вот для случая bitmap-индексов это полностью неверно.

А еще можно не плодить битмап-индексы и таки не бояться явной избыточности, зато организовать себе кластерный индекс по нужному полю/полям. Избыточность не запрещена даже в реляционной модели, бояться тут нечего. Все-равно, ориентироваться надо лишь на результаты замеров в конкретных сценариях и ни на что более.

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

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

S>>Ну т.е. как в случае с существованием переменной (понятия ЯВУ) ты ищешь переменную в исполняющемся коде, так и декларативность языка ты определяешь не по конструкциям языка, а по вычислителю?

V>По вычислительной модели. Это принципиально. См. для сравнения движки языков программирования в ограничениях: ты задаешь цель ("что"), и они ее находят ("как" — перебором или векторным спуском, но нас это не касается).
Движки языков программирования в ограничениях не могут быть выполнены на МТ? Или они тоже императивны по твоей логике?

V>И да, любой современный высокоуровневый язык предоставляет ср-ва деклараций НАД обязательно подразумеваемой вычислительной моделью. Для того, чтобы признать кусок кода без побочных эффектов декларативным в сравнении с императивным, порождающим идентичную программу, это надо совсем уж тщательно выбрать обсуждаемый уровень и точку зрения на него, бо с т.з. вычислительного базиса обе программы одинаково декларативны.
С точки зрения вычислимости на МТ ничто не декларативно. Вообще не пойму, что ты тут обсуждаешь с такой позицией?

S>>Ну что мне сказать?

Скажу что я не разделяю такую позицию.

V>Вижу, и некоторые другие не разделяют. Причем, именно последние буквально несколько лет... когда ФП стало популярным, хотя ему столько же, сколько Лиспу.

V>ИМХО, с некоей непонятной мне легкостью стали пытаться обзывать традиционно рассматриваемый ранее уровень "как" уровнем "что". Т.е. зачем-то для ФП некоторые предпочитают ОПУСКАТЬСЯ в рассмотрении происходящего на один уровень, на уровень неких подробностей алгоритма, называя эти подробности уровнем "что" для низлежащей ф-ой модели исполнения. Ничего более смешного не видел, т.к. этот трюк требует слишком много допущений и натяжек...
Не видел ничего более смешного чем судить о декларативности по вычислительной модели и возможности выполнить ее на МТ.

V>и к тому же, фактически не имеет аргументов против, когда аналогичное начинаешь совершать с императивным программированием. Бо нет в реальной программе никакого "мира" (как ты приводил пример), а есть вполне конечное мн-во состояний. И высокоуровневая императивная программа — несомненно декларативное описание автомата над этим состоянием. Так же, как и идентичная функциональная. Речь идет лишь об инструменте описания, но оба рассматриваемых инструмента равномощны по-определению, коль позволяют порождать идентичные программы с т.з. низлежащей вычислительной модели. Вглядись в происходящее: не может быть описание алгоритма в стиле control flow быть более декларативным, чем блок-схема алгоритма, бо оба описывают один и тот же граф вычислений с очень близким уровнем подробностей. Единственно что, в некоторых местах control flow не задает явно порядок вычисления, дык уже звучал аргумент, что тот же С++ тоже не задает явно порядок вычисления аргументов ф-ий, т.е. однозначно интерпретируемый исходный код, не содержащий UB, будет обладать теми же характеристиками, что аналогичный ф-ий код, для которого не важен порядок вычисления аргументов. Понимаешь что происходит? Вот эту миниатюрную с т.з. низлежащей вычислительной модели разницу в уровнях описания (возможное местами абстрагирование от порядка исполнения веток... но лишь местами) пытаются выдать за водораздел м/у декларативным и недекларативным. Это искажение самого термина "декларация".
Давай вообще начнем с того, откуда в определении декларативности программы взялась вычислительная модель?

V>>>Любой Тьюринг-полный язык императивен по своему определению, например Хаскель.
S>>По какому определению, позволь? не по этому?
S>>

S>>В теории вычислимости исполнитель (множество вычисляющих элементов) называется тьюринг-полным, если на нём можно реализовать любую вычислимую функцию.

V>Гы, поднимись в определениях на один уровень раньше и посмотри, что есть вычислимая ф-ия.
V>Своими словами — это та, для которой существует конечная программа в терминах пошаговых инструкций над идеальной машиной (с бесконечной памятью).
У меня нет слов. Ты из возможности вычислить в МТ делаешь вывод о императивности! Хорошо, покажи мне декларативную по-твоему функцию, такую, что для нее не существует программы МТ.
Вернемся к императивности по Тьюринг-полноте. Если (допустим, хоть это и не так) любой Т-полный язык императивен, то может быть существуют не Т-полные языки(программирования), которые невычислимы на МТ и которые все-таки декларативны?

S>>Раскрой, пожалуйста, как из такой полноты вытекает императивность?

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

V>Еще не ощутил всю иронию происходящего?
V>Уровень "что" для любой полноценной программы, пусть даже на функциональном языке, т.е. любое ТЗ для нее — это описание поведения эквивалентного автомата. Вот прямо отсюда можно начинать сворачивать все обсуждения относительно попыток приписать уровень "что" любым другим уровням, кроме относительных ТЗ в иерархии программных единиц... потому что иной подход потребует неких натяжек и обязательного условия не рассматривать ничего уровнем выше и ни дай бог ничего уровнем ниже. А я на это пойти не могу.

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

V>Вернее могу, но только в обсуждении других вычислительных моделей, ведь есть же еще модели, помимо машины Тьюринга и тоже с разными интересными св-вами.
Я верю, что можешь. Из других вычислительных моделей ты наверняка сделаешь другие не менее интересные выводы, чем императивность всего, вычислимого на МТ.

V>>>То, что в нем есть ФВП, ленивость и иммутабельность — это лишь приятные плюшки, но не более. Неимперативным в принципе может быть только Тьюринг-неполный язык и никакой другой.

S>>Пруф? Или хотя бы направление рассуждений доказательства? Пока ты не доказал что хаскель императивен, я считаю его существование опровержением твоего тезиса.

V>Пруф по ссылке выше, а так же курить эквивалентность автоматов. И на всякий случай (заранее) можно покурить эквивалентность структурных автоматов и абстрактных, но можно поверить и на слово.
Ты сначала докажи причастность автоматов к определению императивности.
Вообще не понятно, как ты трактуешь Тьюринг-полноту. Походу у тебя Т-неполным языком является язык, который нельзя выразить в МТ

V>>>Нет, это тебя опять несет на высоту птичьего полета. Программа на Хаскеле для IO всегда описывает именно действия, которые будет совершать эта ф-ия. То, что любая ф-ия на самом деле возвращает ф-ию — это св-во ленивости, а не чистой ф-сти. Тут ты пытаешься всё свалить в кучу. Я видел твою "расшифровку" монады IO, но даже этого не требуется, коль IO ф-ия ленива.
S>>Ленивость не означает императивность, не так ли?

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

От:	samius	http://sams-tricks.blogspot.com
Дата:	09.01.12 11:19
Оценка:	+1

От:	DarkGray	http://blog.metatech.ru/post/ogni-razrabotki.aspx
Дата:	09.01.12 14:02
Оценка:	+2

От:	samius	http://sams-tricks.blogspot.com
Дата:	09.01.12 14:28
Оценка:

	От:	vdimas
	Дата:	10.01.12 01:06
	Оценка:

	От:	vdimas
	Дата:	10.01.12 01:40
	Оценка:

От:	gandjustas	http://blog.gandjustas.ru/
Дата:	11.01.12 04:10
Оценка:	+2