Когда вы когда-нибудь сталкивались с проблемой проблемы с остановкой? Это может быть, когда сотрудник/босс предложил решение, которое нарушило бы фундаментальные пределы вычислений, или когда вы поняли, что проблема, которую вы пытались решить, на самом деле решить невозможно.
В последнее время я придумал это, когда изучал контролеры типов. Наш класс понял, что было бы невозможно написать идеальный контролер типов (тот, который будет принимать все программы, которые будут выполняться без ошибок типа, и отклонять все программы, которые будут выполняться с ошибками типа), потому что это фактически решит проблему остановки, Другое дело, когда мы поняли, в том же классе, что невозможно определить, будет ли деление когда-либо происходить на ноль, на этапе проверки типов, поскольку проверка того, является ли число во время выполнения равным нулю, также версия проблемы с остановкой.
Я буквально получил задание на остановку, как в "написать плагин монитора, чтобы определить, постоянно ли остановлен хост". Шутки в сторону? Хорошо, так что я просто дам ему порог. "Нет, потому что после этого он может вернуться".
Появилась много теоретического изложения.
Несколько лет назад я помню, как читал обзор (в журнале Byte, я считаю) продукта под названием Basic Infinite Loop Finder или BILF. BILF должен был сканировать исходный код Microsoft Basic и найти любые петли, которые не завершались. Он утверждал, что сможет найти любые бесконечные петли в коде.
Рецензент был достаточно сообразителен, чтобы указать, что для того, чтобы эта программа работала во всех случаях, она должна была решить проблему остановки и дошла до того, чтобы предоставить математическое доказательство того, почему она не может работать во всех случаях.
В следующем выпуске они опубликовали письмо представителя компании, объяснив, что проблема будет исправлена в следующей версии.
Обновление: Я просмотрел изображение статьи на imgur. Я вспомнил неправильный журнал. Это был Creative Computing, а не Byte. В противном случае, это в значительной степени, как я его помнил.
Вы можете увидеть его версию приветствия на imgur.
Проект, над которым я сейчас работаю, имеет неразрешимые проблемы. Это генератор unit test, поэтому в целом то, что он пытается выполнить, - это ответить на вопрос "что делает эта программа". Что является примером проблемы с остановкой. Другая проблема, которая возникла во время разработки, - "даны две (тестовые) функции одинаковые"? Или даже "имеет значение порядок этих двух вызовов (утверждений)"?
Что интересно в этом проекте, так это то, что, хотя вы не можете отвечать на эти вопросы в всех ситуациях, вы можете находить интеллектуальные решения, которые решают проблему. 90% время, которое для этого домена действительно очень хорошее.
Другие инструменты, которые пытаются рассуждать о другом коде, такие как оптимизация компиляторов/интерпретаторов, инструменты для анализа статического кода, даже инструменты рефакторинга, скорее всего, ударят (таким образом, придется искать обходные пути) проблемы с остановкой.
Пример 1. Сколько страниц в моем отчете?
Когда я учился программировать, я играл с созданием инструмента для распечатки хороших отчетов из данных. Очевидно, я хотел, чтобы он был действительно гибким и мощным, поэтому генератор отчетов должен был завершить работу всех генераторов отчетов.
Определение отчета оказалось настолько гибким, что оно было полным. Он может смотреть на переменные, выбирать между альтернативами, использовать циклы для повторения вещей.
Я определил встроенную переменную N, количество страниц в экземпляре отчета, чтобы вы могли поместить строку, на которой указана "страница n из N" на каждой странице. Я сделал два прохода, первый - для подсчета страниц (в течение которых N был установлен на ноль), а второй - для их генерации, используя N, полученный с первого прохода.
Иногда первый проход будет вычислять N, а затем второй проход будет генерировать другое количество страниц (потому что теперь ненулевой N изменит то, что сделал отчет). Я пробовал делать итеративные действия до тех пор, пока N не успокоился. Тогда я понял, что это безнадежно, потому что, если он не успокоится?
Затем это приводит к вопросу: "Могу ли я, по крайней мере, обнаружить и предупредить пользователя, если итерация никогда не решится на стабильное значение для количества страниц, которые создает их отчет?" К счастью, к этому времени я заинтересовался чтением о Тьюринге, Годеле, вычислимости и т.д. И установил связь.
Через несколько лет я заметил, что MS Access иногда печатает "Страница 6 из 5", что поистине замечательно.
Пример 2: компиляторы С++
Процесс компиляции включает в себя расширение шаблонов. Определения шаблонов могут быть выбраны из нескольких специализаций (достаточно хороших, чтобы служить "cond" ), и они также могут быть рекурсивными. Таким образом, это полная мета-система Тьюринга (чисто функциональная), в которой определения шаблона являются языком, типы - это значения, а компилятор - действительно интерпретатор. Это был несчастный случай.
Следовательно, невозможно рассмотреть любую данную С++-программу и сказать, может ли компилятор в принципе завершиться успешной компиляцией программы.
Поставщики компилятора обходятся, ограничивая глубину стека рекурсивного шаблона. Вы можете настроить глубину в g++.
Многие много лет назад я помогал консультанту нашей компании, который внедрял очень сложную систему железных дорог, чтобы перемещать корзины из металлических деталей в доменную печь мощностью 1500 градусов. Сама трасса представляла собой довольно сложный "мини-рейлайдер" на цехе, который пересекался в нескольких местах. Несколько моторизованных поддонов будут перемещать корзины частей вокруг в соответствии с графиком. Очень важно, чтобы двери печи были открыты как можно короче.
Поскольку завод был в полном объеме, консультант не смог запустить свое программное обеспечение в режиме реального времени, чтобы проверить его алгоритмы планирования. Вместо этого он написал симпатичный графический симулятор. Когда мы смотрели, как виртуальные поддоны перемещаются по его схеме на экране, я спросил: "Как вы узнаете, есть ли у вас конфликты планирования?"
Его быстрый ответ: "Легко - симуляция никогда не прекратится".
Сложный статический анализ кода может столкнуться с проблемой остановки.
Например, если виртуальная машина Java может доказать, что кусок кода никогда не получит доступ к индексу массива вне пределов, он может опустить эту проверку и запустить быстрее. Для некоторого кода это возможно; поскольку он становится более сложным, он становится проблемой остановки.
Это все еще проблема для шейдеров в приложениях GPU. Если шейдер имеет бесконечный цикл (или очень длинный расчет), должен ли драйвер (после некоторого ограничения времени) остановить его, убить фрагмент или просто запустить его? Для игр и других коммерческих вещей первое, вероятно, то, что вы хотите, но для научных/графических вычислений последнее - это то, что вы хотите. Хуже того, некоторые версии окон предполагают, что, поскольку графический драйвер не реагирует на некоторое время, он убивает его, что искусственно ограничивает вычислительную мощность при выполнении вычислений на графическом процессоре.
Там нет API для приложения, чтобы контролировать, как должен себя вести драйвер, или установить тайм-аут или что-то еще, и, конечно, нет способа, чтобы драйвер мог сказать, будет ли ваш шейдер завершен или нет.
Я не знаю, улучшилась ли эта ситуация в последнее время, но я хотел бы знать.
Другой распространенной версией этого является "нам нужно устранить любые взаимоблокировки в нашем многопоточном коде". Совершенно разумный запрос, с точки зрения управления, но для предотвращения взаимоблокировок в общем случае вам необходимо проанализировать все возможные состояния блокировки, в которые может попасть программное обеспечение, что не удивительно, равнозначно проблеме остановки.
Есть способы частично "разрешить" взаимоблокировки в сложной системе, наложив еще один слой поверх блокировки (например, определенный порядок получения), но эти методы не всегда применимы.
Почему это эквивалентно проблеме остановки:
Представьте, что у вас есть две блокировки: A и B и два потока, X и Y. Если поток X имеет блокировку A и хочет также блокировать B, а поток Y имеет блокировку B и хочет A тоже, тогда у вас есть тупик,
Если оба X и Y имеют доступ как к A, так и B, то единственный способ гарантировать, что вы никогда не попадаете в плохое состояние, - это определить все возможные пути, которые каждый поток может взять через код, и порядок в котором они могут приобретать и удерживать блокировки во всех этих случаях. Затем вы определяете, могут ли два потока когда-либо приобретать более одного замка в другом порядке.
Но определение всех возможных путей, которые может выполнять каждый поток через код, (в общем случае) эквивалентно задаче остановки.
Система тестирования Perl поддерживает тестовый счетчик. Вы либо ставите количество тестов, которые вы собираетесь запускать в верхней части программы, либо заявляете, что не собираетесь отслеживать их. Этот защитник против вашего теста выходит преждевременно, но есть и другие охранники, поэтому это не все, что важно.
Время от времени кто-то пытается написать программу, чтобы подсчитать количество тестов для вас. Это, конечно, побеждает простой цикл. Они все равно пахают вперед, делая все больше и больше сложных приемов, чтобы попытаться обнаружить петли и угадать, сколько итераций будет и решить проблему остановки. Обычно они заявляют, что это просто должно быть "достаточно хорошим".
Я когда-то работал над проектом интеграции в банкомате (банкоматах). Клиент попросил меня создать отчет из моей системы для транзакций, отправленных переключателем страны, которые не были получены моей системой!
Я нашел бумагу Беркли: Looper: легкое обнаружение бесконечных циклов в Runtime http://www.eecs.berkeley.edu/~jburnim/pubs/BurnimJalbertStergiouSen-ASE09.pdf
LOOPER может быть полезен, поскольку большинство бесконечных циклов являются тривиальными ошибками. Однако в этой статье даже не упоминается проблема остановки!
Что они говорят об их ограничениях?
[LOOPER] обычно не может рассуждать о циклах, где не прекращается зависит от особенностей кучи мутации в каждой итерации цикла. Это потому, что наше символическое исполнение является консервативным в конкретизирующие указатели, и наши символические рассуждения недостаточно мощный. Мы считаем, что объединение наших методов с анализом формы и более мощное создание и доказательство инварианта было бы ценным будущая работа.
Другими словами, "проблема будет исправлена в следующей версии".
Из Функциональный обзор (Eclipse) Visual Editor:
Визуальный редактор Eclipse (VE) может быть используется для открытия любого.java файла. Тогда анализирует исходный код Java для визуального beans....
Некоторые инструменты визуального редактирования будут предоставить визуальную модель кода, которая сам этот визуальный инструмент генерироваться. Последующее прямое редактирование исходного кода может визуальный инструмент от анализа кода и построение модели.
Eclipse VE, однако, может либо быть используется для редактирования GUI с нуля или из файлов Java, которые были "hardcoded" или встроенный в другой визуальный инструмент. Исходный файл может либо обновляться с использованием графического Просмотр, дерево JavaBeans или свойства или можно редактировать напрямуюРедактор исходного кода.
Возможно, теперь я должен придерживаться Матисса.
Не связанный, здесь кто-то запрашивает проблему с остановкой в Eclipse.
Чтобы быть справедливым, домен VE довольно ограничен, и, вероятно, он не сходит с ума из-за сложных вещей, таких как отражение. Тем не менее, претензия на создание GUI из любого java файла кажется halt-ish.
"Как вы можете заверить меня, что ваш код на 100% свободен от ошибок?"