Трудновыявляемые ошибки в алгоритмах

[Anton_Peplov]

epros в сообщении #1647084 писал(а):

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

Так делается в том случае, если результат проверки не важен. Если это необязательный бантик. То есть это не баг, а фича: сознательное решение программиста не тратить вычислительные ресурсы на фигню. Повязали бантик быстро - хорошо, нет - подарим торт без бантика. Главное-то торт. Как пишет счетчик читателей на "стихи.ру", "мы не гарантируем узнавание и учет всех читателей, эта функция работает лишь с определенной вероятностью". Ну и действительно плевать мне, по большому счету, 20 человек меня прочитало за неделю или на самом деле 18, просто счетчик два повторных захода не опознал.

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

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

[Geen]

Anton_Peplov в сообщении #1647086 писал(а):

Любой ли баг можно найти?

А что есть баг?

[worm2]

epros, кажется, это намёк на искусственные нейронные сети.
Разработчики которых часто не заморачиваются с воспроизводимостью результатов, не воюют с race conditions и прочими подобными вещами.
Хотя могли бы, но ради производительности плюют на не очень сильные отклонения результата от ожидаемого (и даже вопросом "а что в точности мы должны получить?" не задаются).
Но могли бы. Никто не запрещает.

[Anton_Peplov]

Geen в сообщении #1647087 писал(а):

А что есть баг?

Баг - это когда программа работает неправильно, потому что программист записал не тот алгоритм, который имел в виду. Например, проверяет не то условие, которое хотел проверить, и программа зацикливается. Или не учел какой-то особенности входных данных и допустил, скажем, деление на ноль. Как говорится, отладка - это долгий и болезненный процесс осознания того, что твоя программа делает именно то, что ты написал.

(Случай из жизни)

Как-то лет десять назад я писал большую программу, один кусочек которой должен был считывать подходящую строку в текстовом файле. Файл был большой и отсортированный по возрастанию, скажем, лохматости. Ну я на эту сортировку и положился: мол, если лохматость уже вышла за пределы искомого диапазона, то строка не найдена. Оптимизация, прст. А потом полдня голову ломал, почему программа не находит одну конкретную запись. Вот другие находит, а эту нет. После долгой мучительной отладки оказалось, что список в файле был не отсортирован как целое, а сшит из нескольких отсортированных кусков. Ну как если бы за списком жильцов дома № 1 в алфавитном порядке шел список жильцов дома № 2 в алфавитном порядке. И вот ты смотришь в любое место длиннющего списка и видишь сортировку по алфавиту, а в чем подлость, ты поймешь, только если с отчаяния просмотришь список полностью и увидишь, что за Ячменевыми снова начались Абрамовы. С тех пор я никогда не полагался на предварительную сортировку, сделанную неизвестно кем.

[epros]

Anton_Peplov в сообщении #1647086 писал(а):

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

В общем, я уже не понимаю, о чем мы спорим.

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

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

[Anton_Peplov]

epros в сообщении #1647091 писал(а):

Вы вот ратуете за повторяемость и прослеживаемость результатов работы алгоритмов, а её по факту нет.

Она есть там, где она достаточно важна, чтобы о ней заботится.

В 1996 г. ракета "Ариан-5" взорвалась через 40 секунд после старта с Куру. Как показало расследование, взрыв произошел из-за ошибки в программном обеспечении. А именно, выражающее горизонтальную составляющую скорости ракеты относительно платформы 64-битовое число с плавающей точкой конвертировалось в 16-битовое целое со знаком. Эта конвертация привела к вычислительной ошибке. Ракета и груз стоили $500 млн. Неожиданный трудноуловимый баг? Да. Нашли, когда очень захотели найти? Да. Больше ракеты по этой причине не падают. Падают по другим.

epros в сообщении #1647091 писал(а):

если даже точные ответы нам супер как важны, не факт, что мы их все получим при имеющихся ресурсах

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

epros в сообщении #1647091 писал(а):

Я говорю: "Алиса, перестрой маршрут без платных дорог". И что Вы думаете? Она мне построила маршрут до офиса компании "Без платных дорог".

Вот только нейросети не надо сюда вмешивать. Конечно, обученная нейросеть работает по алгоритму (ух ты, я говорю как Webpack!), но этот алгоритм она вырабатывает сама в процессе обучения. Алгоритм работы большой нейросети слишком велик для понимания человеком и (почти) не дробится на осмысленные для человека блоки. Так что если воспроизводимость еще какая-никакая есть (на баги там плюют в рамках, указанных уважаемым worm2), то прослеживаемости вообще никакой нет. Я потому с самого начала и сделал оговорку про алгоритмы обозримого размера.

[Geen]

Anton_Peplov в сообщении #1647090 писал(а):

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

Тогда, очевидно, не любой баг можно найти.

[Anton_Peplov]

Geen в сообщении #1647096 писал(а):

Тогда, очевидно, не любой баг можно найти.

Программируя машину с неограниченными регистрами - да, поскольку множество всех возможных входных данных бесконечно. Можно, скажем, исхитриться написать алгоритм умножения целых чисел так, чтобы он правильно вычислял все произведения кроме $937897 \cdot 10^{66} \times 7 \cdot 10^{133}$. И если никто никогда не протестирует именно эту пару, то баг останется невыявленным.

Разнообразие входных данных для реальных машин ограничено (хотя бы памятью), поэтому чисто теоретически можно перебрать и проверить все варианты. На практике, конечно, их астрономическое число. Можно представить себе баг, на поиск которого нужно больше усилий, чем было потрачено на разработку программы. Вот только встречается ли такое в реальной жизни?

[Geen]

Anton_Peplov в сообщении #1647097 писал(а):

Программируя машину с неограниченными регистрами

Это не при чём.
Важнее то, что установить что "программист имел в виду" почти всегда невозможно (даже если программа работает "правильно").

[epros]

Anton_Peplov в сообщении #1647092 писал(а):

Она есть там, где она достаточно важна, чтобы о ней заботится.

В 1996 г. ракета "Ариан-5" взорвалась через 40 секунд после старта с Куру. Как показало расследование, взрыв произошел из-за ошибки в программном обеспечении. А именно, выражающее горизонтальную составляющую скорости ракеты относительно платформы 64-битовое число с плавающей точкой конвертировалось в 16-битовое целое со знаком. Эта конвертация привела к вычислительной ошибке. Ракета и груз стоили $500 млн. Неожиданный трудноуловимый баг? Да. Нашли, когда очень захотели найти? Да. Больше ракеты по этой причине не падают. Падают по другим.

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

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

Anton_Peplov в сообщении #1647092 писал(а):

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

Для многих задач ресурсов хватает, но на некоторые задачи неожиданно может не хватить даже огромного количества ресурсов. И что в таком случае должен сделать качественно написанный алгоритм? Вовремя обнаружить проблему и пойти по обходному пути. А тупо написанный алгоритм просто повиснет. Но именно наличие в алгоритме таких обходных путей делает его поведение слабо предсказуемым.

Anton_Peplov в сообщении #1647092 писал(а):

Вот только нейросети не надо сюда вмешивать. Конечно, обученная нейросеть работает по алгоритму (ух ты, я говорю как Webpack!), но этот алгоритм она вырабатывает сама в процессе обучения.

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

[Anton_Peplov]

Geen в сообщении #1647098 писал(а):

Важнее то, что установить что "программист имел в виду" почти всегда невозможно

Даже для него самого? Или проблема в том, что программистов и тестировщиков больше одного?

[Sender]

epros в сообщении #1647102 писал(а):

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

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

[EminentVictorians]

epros в сообщении #1647102 писал(а):

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

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

[Anton_Peplov]

epros в сообщении #1647102 писал(а):

Так что за калькулятором никто не проверяет, а просто верят ему.

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

epros в сообщении #1647102 писал(а):

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

"Алгоритм доступен для понимания человеком" и "данные могут быть обработаны человеком" - это разные вещи. Потому что важна не только длина алгоритма, но и объем данных. Возьмем прибор, считывающий данные каждую миллисекунду и работающий сутки. Мы хотим сгладить шумовую дорожку и поэтому усредняем данные по секундным интервалам скользящим средним. Очень простая для понимания процедура. Алгоритм на десять строк. А теперь сделайте это сами, раз программа "в общем-то, и не нужна". У меня таких приборов было 128, и работали они ежедневно в течение лет.

epros в сообщении #1647102 писал(а):

Ну вот Ваш же пример про то, что прослеживаемости по факту нет, а есть только некая иллюзия прослеживаемости.

Похоже, мы понимаем под прослеживаемостью разные вещи. Ну и ладно, я уже устал от этого разговора.

[Martynov_M]

EminentVictorians в сообщении #1647071 писал(а):

Интересно, а существуют ситуации, где код написан по всем нормам и стандартам, а программа работает не так, как от неё ожидается?
Я имею в виду, что код по спецификации написан корректно и должен делать $X$, а в действительности делает $Y$.

Есть такой класс программ как видеодрайверы. Странная вещь.
Скачиваешь видеодрайвер с официального сайта. Проходит 1 год. Скачиваешь новую игру. И обнаруживаешь артефакты на экране. Идешь к разработчику. Он говорит:

– А что ты хотел? Это ведь новая игра! Она использует графическую функцию «Xi451» таким хитрым образом, что иногда она работает корректно, а иногда нет. У кого-то есть артефакты, у кого-то нет. Жди. Сейчас выпустим обновления.