Может ли среда выполнения обнаруживать бесконечный цикл?

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

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

(Портировано с /programming//q/16250472/1858225 )

Это может быть теоретически возможно для среды выполнения для проверки таких петель , используя следующую процедуру:

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

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

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

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

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

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

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

Итак, давайте сделаем это. Мы запустим его один раз во время выполнения Tortoise, и в то же время мы запустим его во время выполнения Hare. Однако мы организуем, чтобы среда выполнения Hare работала ровно в два раза быстрее; каждый раз, когда среда выполнения Turtoise делает один шаг, среда выполнения Hare делает два шага.

$n$$p$$kn$$k$$kn\ge p$

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

Как следует из используемых мной терминов, это всего лишь известный алгоритм обнаружения циклов Черепахи и Зайца Роберта Флойда .

Так же, как я собирался предложить алгоритм определения цикла Флойда, пост Ричи побил меня до этого. Тем не менее, все это можно сделать более практичным путем ускорения сравнения полных состояний.

Узким местом предлагаемого алгоритма было бы сравнение полного состояния. Эти сравнения обычно не заканчиваются, а заканчиваются рано - при первом различии. Одна оптимизация заключается в том, чтобы вспомнить, где произошли прошлые различия, и сначала проверить эти части состояния. Например, ведите список местоположений и просмотрите этот список, прежде чем проводить полное сравнение. Когда местоположение из этого списка показывает разницу, остановите сравнение (с ошибкой) и переместите местоположение в начало списка.

Другой (и потенциально более масштабируемый) подход заключается в использовании добавочного хеширования. Выберите функцию полного состояния так, чтобы значения хеш-функции легко настраивались в O (1) при изменении какой-либо части состояния. Например, возьмите взвешенную сумму слов состояния mod для некоторого большого простого числа и объедините с невзвешенной суммой mod для некоторого другого большого простого числа (можно также добавить модульную взвешенную сумму квадратов слов с различным весом и модулем). Таким образом, обновления хеша будут занимать O (1) времени на каждом шаге выполнения, а сравнение будет занимать O (1) времени, пока вы не получите попадание. Вероятность ложного положительного результата (т. Е. Совпадения хэшей, в то время как состояния различаются) очень мала, и даже если это когда-либо произойдет, амортизируется большое количество истинных отрицаний (ложные отрицания невозможны).

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

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

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

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