Comments 32
Детерминированность алгоритма гарантирована только на детерминированной машине. Как только появляются сайд-эффекты (ввод-вывод), поведение системы не детерминированно. Любой язык программирования, который умеет излагать это на типоязыке, точно это показывает:
- Rust: любое IO unsafe. Любой вызов в ОС unsafe. В общем случае, любой unsafe code — undefined behavior.
- Haskell: Монада IO, которая в себя собирает "всё плохое".
… Но тут есть чуть больше. Время исполнения кода — это side effect. Если мы начинаем закладываться на время, то любая функция перестаёт быть чистой. Острее всего это становится в момент появления параллельного кода, когда относительный порядок выполнения недетерминирован.
Но, на самом деле, любой правильный язык программирования (и правильная методология разработки) должна стремиться к сохранению инварианта — т.е. написанию такого кода, который сохраняет типоповедение вне зависимости от происходящего на входе/сайд-эффектах.
На самом деле, любой девопс должен стремиться к этому же. Идемпотентные плейбуки ансибла, воспроизводимые деплои в кубе, reproducible builds при сборке пакетов, декларативный процесс воссоздания любого артефакта (и отсутствие golden artifacts).
Как только появляются сайд-эффекты (ввод-вывод), поведение системы не детерминированно
Но ведь это не так. Чисто функциональные ФП языка потому так и называются, что они детерминированны. Естественно, никто не застрахован от событий из разряда пролета высокоэнергетической частицы через память именно в момент когда там производятся вычисления или аппаратного бага, но обычный IO в нормальных условиях — это совсем иная вещь.
Цитата из хорошей книги на тему:
Nowhere is it better illustrated than in the Functional Reactive Programming (frp) approach to user interaction. Instead of writing separate handlers for every possible user action, all having access to some shared mutable state, frp treats external events as an infinite list, and applies a series of transformations to it. Conceptually, the list of all our future actions is there, available as the input data to our program. From a program’s perspective there’s no difference between the list of digits of π, a list of pseudo-random numbers, or a list of mouse positions coming through computer hardware. In each case, if you want to get the nth item, you have to first go through the first n − 1 items. When applied to temporal events, we call this property causality
Но тут есть чуть больше. Время исполнения кода — это side effect. Если мы начинаем закладываться на время, то любая функция перестаёт быть чистой. Острее всего это становится в момент появления параллельного кода, когда относительный порядок выполнения недетерминирован.
Почитайте мою последнюю статью, я там про это говорил. Сайд эффект — это все явления, которые мы должны были бы выразить в типах, но не стали этого делать. В ФП они запрещены. В ФП есть просто "эффекты", которые не сайд, потому что они явно являются частью результата функции.
Если вам нужен порядок вычислений — вот вам ио монада. Если вам нужен стейт — вот вам стейт монада. Если вам нужно аллокации контролировать — вот вам какая-нибудь аллок монада. Нужно проверять что мы не слишком перегрели процессор — температур монада. Хотим писать логи — райтер монада.
В любом случае у нас не будет сайд эффекта, если нам важно что-то контролировать мы вынесем это в типы.
Время выполнения — это действительно сайд эффект. Иначе не были бы возможны временные атаки на информационные системы. Так медленно бит за битом можно получать информацию о внутреннем устройстве и создавать канал утечки по этому сайд каналу.
Время выполнения — это действительно сайд эффект.
Зависит от того — важно вам время выполнения или нет. Если нет — то и сайдэффекта нет (по определению).
Если вам важно учитывать этот эффект — то вы сделаете MeasureTimeMonad и снова будете в дамках.
И речь вроде шла не про криптографию в любом случае.
Язык программирования без IO смысла не имеет, мы не узнаем результат вычисления. Если же есть IO, то это всегда undefined behavior, потому что никакая модель вычислений не может ответить, что будет, если на pin42 подать +5. Может быть, лампочка загорится. Может быть, байтик в принтер уедет. А, может, это сигнал "выключите меня, пожалуйста". И не существует никакой type safety для защиты от этого.
Насчёт времени, как сайд-эффекта. Представьте себе, что у вас алгоритм, который вычисляет два числа (чистые фунции) в двух тредах. Ответ записывается в список в "родительском" треде, который ждёт все треды на завершение и записывает результат в порядке их завершения.
Алгоритм, допустим, o(1), и, даже, допустим, с одинаковым числом операций. Какое число будет вычислено первым?
Я хочу заметить, что в этом примере нет "порядка" вычисления как IO, но результат выполнения двух чистых функций является настолько произвольным, что его используют как генератор рандома в современных компьютерах (haveged).
Т.е. запуск треда — это IO. Ожидание треда — IO. Раздумие про то, сколько времени прошло (в тиках ли, или wallclock time) — это IO.
Таким образом, любое параллельное программирование — это та самая недетерминированность, которую невозможно убрать из языка программирования. С ней можно работать как с любыми другими эффектами, но "убрать" её нельзя.
Язык программирования без IO смысла не имеет, мы не узнаем результат вычисления. Если же есть IO, то это всегда undefined behavior, потому что никакая модель вычислений не может ответить, что будет, если на pin42 подать +5.
Можно пойти в спеку процессора и посмотреть что происходит когда на пин42 подается +5. Это и будет ответ на вопрос. Если в какой-то момент спека нарушена — ну, это нарушение спеки и аппаратный баг, да. Несите новый камень.
Алгоритм, допустим, o(1), и, даже, допустим, с одинаковым числом операций. Какое число будет вычислено первым?
Параллельность — это явный отказ от последовательности. Определение последовательности выполнения параллельного кода — оксюморон.
Я хочу заметить, что в этом примере нет "порядка" вычисления как IO, но результат выполнения двух чистых функций является настолько произвольным, что его используют как генератор рандома в современных компьютерах (haveged).
Композицию чистых функций нельзя использовать для рандома просто по определению. Ну или если вас устроит рандом который всегда выдает 4
Таким образом, любое параллельное программирование — это та самая недетерминированность, которую невозможно убрать из языка программирования. С ней можно работать как с любыми другими эффектами, но "убрать" её нельзя.
Чистота — это свойства программы, а не результата который она производит. Создание параллельного IO — чистая операция, всегда возвращает одно и то же. Его интерпретация — очевидно нет, можно происходить всё, что угодно.
Я немного не понял вас. Если мы выполнили в двух тредах две функции и джём их результата ( await_any()) — это ещё чистая фукнция или уже нет?
Так мы ничего не ждем. Мы только создали футуру (или таск, или промиз, как удобно), который нужно выполнить. Создание такой футуры это чистая функция. Интерпретация (выполнение соответствующих запросов) — нет. Сама программа не может дождаться выполнения футуры. Иными словами, вы не можете написать функцию Promise<T> -> T
x = await new Promise<T>(...) это просто сахар для new Promise<T>(...).then(x => ...)
Ну, с тредами почти так же. Код (замыкание) для треда — чистая функция, его запуск и ожидание — IO.
Я про это и говорю — многопточное программирование закрывает вопрос детерминированности программы полностью.
Вопрос в том что считать под детерминированностью. Возьмем например вывод текста параллельно на экран.
Если под Д подразумевать то что надписи в принципе буду выведены, то они будут.
Если под Д подразумевать что надписи всегда выводятся в одном порядке, то для этого нужно прилагать дополнительные усилия.
Свести к Д можно всегда (не считая аппаратного сбоя), вопрос что мы под этим понимаем.
Если мы делаем математику/логику между параллельными тредами, то мы можем получить чистый jitter, достойный haveged. Например, если мы из первого полученного числа вычитаем второе и выводим результат на экран. Цифра — одно из множества возможных значений, а не фиксированная величина.
На самом деле вывод на экран — это уже IO, которое совершенно не определено и является UB.
Как по вашему в ФП языках живут если они и на экран выводят, и в многопоток умеют? У них "Нечестная" чистота? Или нечисто, но все старательно делают вид, что всё нормально?
На экран выводят в монадках или их заменителях. Делают UB, который чаще всего то, что им обещали, но обещали не создатели языка, а посторонние люди (у которых в доках 100500 нюансов, а финальная документация на Си с вставками на ассемблере, ссылающимся на architectural guide, в котором есть инструкции процессора, которые делают UB тоже).
Как-то раз я месяц фулл-тайм ловил (как оказалось) баг в ядре Linux (про фриз при нескольких очередях в veth), вызванный изменением, вызванным другим багом в ядре Linux (про iptables и MSS adjust), вызванным другим изменением, вызванным желанием сэкономить PPS за полтора года до начала проявления бага с фризом. PPS, что характерно, в итоге так и не экономился.
И вот с одной стороны я молодец, что разобрался (в ядро до этого сильно не лазил, падало оно очень мерзко, это всё), а со второй — целый месяц убитого времени из-за вот этого вот желания сэкономить и нежелания хотя бы проверить, что экономия есть.
неужели не было потом приятно "я же понял как эта чёртова система работает"?
Лучше бы, чтобы некоторого опыта не было ) с одной стороны — да, круто, разобрались, повысили квалификацию, а, с другой стороны — сколько полезного (на самом деле нет) мы могли сделать за время расследования причин проблем, которые сами же и придумали.
Вот коллеги тоже, например, постреляли себе по ногам с обеих рук: https://m.habr.com/ru/company/timeweb/blog/428954/
И причиной может быть интерференция событий, а не суперпозиция…
А вот уже способность идентифицировать все эти причины — вопрос квалификации, опыта, ну и личных качеств, если угодно. При этом польза от разводящего руками девопса, говорящего «ну, шит хэппенс» — как-то сомнительна.
Конечно, я не говорю, что разработчики наивны, глупы или неспособны понять, как линейность может быть обманчива
если кто-то обладает квалификацией и упорством добраться до первопричин, а не махнуть рукой "а хез, оно само" — по-вашему он наивен, глуп и неспособен что-то понять. мда...
А если каждый второй отчет в бухгалтерии падает с непонятной ошибкой, в 1с ничего не понятно, в БД ничего не понятно, RAID-контроллер, как пионер, говорит готов. То придется искать первопричину, которая будет в одном битом секторе на одном жестком диске в массиве.
Потому что это на самом деле очень философский вопрос. У нас есть чистые фунции, которые должны вычислять волновую функцию для частиц, квадрат которой — вероятность, причём вычислять её детерминированно, на устройстве, состоящем из объектов, подчиняющимся этим самым волновым функциям с вероятностями.
Если бы какой-то части обстоятельств не было (даже одного) — инцидента могло бы вообще не быть.
Похожая тема — в разборах причин автокатастроф, см википедию, там тоже так же, например: не сделали что-то здесь во время обслуживания, сломалось что-то там, совпали погодные условия, ошибка в документации на самолет (и как следствие конкретная ошибка пилота) — в результате авария. Не было бы хотя бы чего-то одного из этого — самолет нормально долетел бы резервных мощностях.
У тебя угнали пароли пользователей через форму входа, в чем корневая и единственная причина этого инцидента?
Ответ программиста — постараться локализовать причину, а в идеале найти причину и пофиксить. Бывает, что проблема воспроизводится с трудом, случается нечасто, тогда, может быть и не стоит дальше копать. Но какие-то решения пользователям нужно предложить.
Что-то я не понимаю, какие тут могут быть альтернативы от инженеров или кто-там не такой как программист?
Программисты, девопсы и коты Шрёдингера