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

[EminentVictorians]

Ende
Выделено из темы «Философия»

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

Алгоритмы (обозримого размера) хороши как раз тем, что каждый шаг можно проследить и, при необходимости, вспомнить о его смысле.

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

[Anton_Peplov]

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

Но как это все компилируется Вы же все равно не знаете.

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

[epros]

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

Алгоритмы (обозримого размера) хороши как раз тем, что каждый шаг можно проследить и, при необходимости, вспомнить о его смысле.

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

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

[Anton_Peplov]

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

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

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

[EminentVictorians]

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

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

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

[Anton_Peplov]

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

Интересно, а существуют ситуации, где код написан по всем нормам и стандартам, а программа работает не так, как от неё ожидается?

Что значит "по всем нормам и стандартам"? Норма и стандарт не гарантируют от ошибок, а лишь уменьшают их частотность до коммерчески приемлемого уровня. В производстве микроэлектроники, например, существует стандарт "шесть сигм". Какие нормы и стандарты действуют в богоспасаемой компании "Мелкософт", видно по недавним событиям.

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

[EminentVictorians]

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

Что значит "по всем нормам и стандартам"?

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

Давайте даже не будем брать сторонние эффекты. Пусть есть достаточно чистая программа, которая ни с чем лишним не взаимодействует (в идеале, чтобы даже I/O не было, но я пока не очень представляю, как это может выглядеть).

Я тут скорее имею в виду, можно ли "сломать" язык его же синтаксисом. Т.е. написать такой код, который обманет свой собственный компилятор.

-- 22.07.2024, 14:16 --

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

[mihaild]

(Оффтоп)

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

Какие нормы и стандарты действуют в богоспасаемой компании "Мелкософт", видно по недавним событиям

Имеющим такое же отношение к майкрософту, как отравление метиловым спиртом к производяшему его заводу.

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

Т.е. написать такой код, который обманет свой собственный компилятор

Баги в компиляторах бывают.

[Anton_Peplov]

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

Я тут скорее имею в виду, можно ли "сломать" язык его же синтаксисом. Т.е. написать такой код, который обманет свой собственный компилятор.

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

-- 22.07.2024, 14:40 --

(Оффтоп)

mihaild в сообщении #1647074 писал(а):

Имеющим такое же отношение к майкрософту, как отравление метиловым спиртом к производяшему его заводу.

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

[mihaild]

(Оффтоп)

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

Я не понял из прочитанного, кто покупал услугу у CrowdStrike: майкрософт или пользователи?

Пользователи. С точки зрения M$ ситуация ничем формально не отличается от того, что все решили массово скачать очередной "оптимизатор реестра".

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

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

Не в ОС, а в популярное приложение для нее. Сути не меняет, да.
Вопрос, почему товарищи в CrowdStrike не знают вещей, которые изучают на 2м курсе соответствующих специальностей в любом университете - что обновления не раскатываются сразу на всю клиентскую базу - остается открытым.

[epros]

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

Позволяет-то позволяет, только кому это надо - писать такой код?

Он может написаться вполне непреднамеренно. Захотели проверить какое-то условие, а проверка всё никак не завершается.

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

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

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

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

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

Может быть и так, что Вы никак не изолируете кусок, на котором программа сбоит, да и вообще не поймёте, что это сбой. Приведу свой любимый пример: Человеку объяснили, что такое совершенное число и привели примеры - 6 и 28, а на вопрос: "Бывают ли нечётные совершенные числа?" - сказали, что не знают. И он, вместо того, чтобы посмотреть википедию, решил написать простую программу поиска нечётных совершенных чисел. Каков будет результат, если программа написана достаточно грамотно для того, чтобы сразу не вылетать по переполнению регистра? Результат известен: Она за разумное время не закончится. Это "сбой"? Но ведь никто не доказал, что нечётных совершенных чисел не существует, может быть просто компьютер нужен помощнее (чем использовались до сих пор) и подождать подольше.

[Anton_Peplov]

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

Может быть и так, что Вы никак не изолируете кусок, на котором программа сбоит, да и вообще не поймёте, что это сбой. Приведу свой любимый пример: Человеку объяснили, что такое совершенное число и привели примеры - 6 и 28, а на вопрос: "Бывают ли нечётные совершенные числа?" - сказали, что не знают. И он, вместо того, чтобы посмотреть википедию, решил написать простую программу поиска нечётных совершенных чисел. Каков будет результат, если программа написана достаточно грамотно для того, чтобы сразу не вылетать по переполнению регистра? Результат известен: Она за разумное время не закончится. Это "сбой"? Но ведь никто не доказал, что нечётных совершенных чисел не существует, может быть просто компьютер нужен помощнее (чем использовались до сих пор) и подождать подольше.

Было бы очень глупым решением написать такую программу без вывода промежуточных результатов. Моя программа писала бы на экране: "Проверены числа до 1 000 000. Нечётных совершенных чисел не найдено. Проверены числа до 2 000 000. Нечётных совершенных чисел не найдено" и так далее через каждый миллион. Если отчет об $n$-ном миллионе не появляется слишком долго - либо программа зависла, либо компьютер уже слабоват для таких чисел. У нас должна быть предварительная оценка, какие числа может осилить компьютер, хотя бы с точностью до порядка. Если проверено явно меньше, прерываем исполнение и требуем, начиная с $n-1$-го миллиона, выводить разбивку по сто тысяч, и т.д. Так локализуем последнее число $m$, для которого проверка была завершена. Запускаем программу пошагово с числом $m+2$ и ищем лажу.

-- 22.07.2024, 15:31 --

(Оффтоп)

mihaild в сообщении #1647078 писал(а):

Пользователи

А, ну тогда мои извинения Microsoft.

[mihaild]

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

Если проверено явно меньше, прерываем исполнение и требуем, начиная с $n-1$-го миллиона

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

[Anton_Peplov]

mihaild в сообщении #1647081 писал(а):

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

Это неоспоримо указывает на наличие бага в алгоритме. То есть решает проблему, поставленную уважаемым epros: отличает сбой от от нормальной работы.

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

Как делал я в те годы, когда еще что-то программировал. Пусть мы выяснили, что при запуске с нуля последнее сообщение, которое мы видимо, про пятый миллион. Значит, и запускаем ее всегда с нуля. Раскидываем по коду точки останова "останавливаем, если счетчик достиг $k$" и запускаем отладку в режиме "выполнять до точки останова". Поскольку новые точки останова можно добавлять прямо в ходе отладки, продолжаем столько, сколько там нужно, чтобы найти проблемное число в миллионе бинарным поиском. Добравшись до проблемного числа, выполняем пошагово и проверяем, где лажа. Благо отладчик показывает состояние всех переменных.

[epros]

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

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

Может быть и так, что Вы никак не изолируете кусок, на котором программа сбоит, да и вообще не поймёте, что это сбой. Приведу свой любимый пример: Человеку объяснили, что такое совершенное число и привели примеры - 6 и 28, а на вопрос: "Бывают ли нечётные совершенные числа?" - сказали, что не знают. И он, вместо того, чтобы посмотреть википедию, решил написать простую программу поиска нечётных совершенных чисел. Каков будет результат, если программа написана достаточно грамотно для того, чтобы сразу не вылетать по переполнению регистра? Результат известен: Она за разумное время не закончится. Это "сбой"? Но ведь никто не доказал, что нечётных совершенных чисел не существует, может быть просто компьютер нужен помощнее (чем использовались до сих пор) и подождать подольше.

Было бы очень глупым решением написать такую программу без вывода промежуточных результатов. Моя программа писала бы на экране: "Проверены числа до 1 000 000. Нечётных совершенных чисел не найдено. Проверены числа до 2 000 000. Нечётных совершенных чисел не найдено" и так далее через каждый миллион.

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

Вот так Вы и получите то самое "детище, непонятное своим создателям", потому что создатель программы уже не будет знать почему ответ не был получен: то ли мощности процессора не хватило, то ли его просто нет. А при более мощном процессоре ответ внезапно и непредсказуемо для создателя программы будет получен и программа пойдёт по совсем другому пути.