Решает ли система компиляции Glorious Glasgow Haskell наполовину проблему остановки?
title длинный, потому что SO не разрешил "Решает ли GHC наполовину проблему остановки?" по какой-то причине
Конечно, не сама проблема остановки, а подзадача конечной памяти.
Я играл с метапрограммированием а-ля Typing the Technical Interview и решил написать интерпретатор мозгового типа на уровне типов. Это было достаточно просто, и через полчаса я перешел от написания интерпретатора к попыткам написать программы, которые вешают компилятор.
+[+]выполнено столько же, сколько и ответы на тот вопрос, который я связал выше, переполнение стека сокращения. Я сдал GHC
-freduction-depth=0flag, снова скомпилирован и закончилась нехватка памяти. Неудивительно - это создало бы очень большой
S (S (S (...(S Z)...))) ячейка на ленте.
Я решил, что настоящая проблема - это повесить компилятор с ограниченным использованием памяти. Естественно,
+[] (или же
Cons Inc (Cons (Loop Nil) Nil)как тип) была моя первая попытка. Увеличивайте текущую ячейку, затем ничего не делайте, пока текущая ячейка не равна нулю. Я надеялся этим избежать создания постоянно больших значений, таких как большая ячейка или длинная лента. Но здесь GHC перехитрил меня:
λ> foo = undefined :: Eval NoHalt BlankTape t => t
λ> :t foo
foo :: t
Компиляция завершилась в мгновение ока, и было получено "значение"
forall t. t, что, как я полагаю, имеет смысл как ⊥ в мире, в котором типы являются значениями.
Поэтому я решил сделать петлю более сложной. Может быть, GHC может обнаруживать только особо простые петли? Но
+[+-] и
+[><]имел такое же поведение, поэтому мне пришлось поднять его на ступеньку выше с помощью очень сложного и дорогостоящего цикла без операций. Устанавливается при подсчете, вычислении логарифма каждого значения, сбросе счетчика и продолжении выполнения после достижения некоторой степени двойки.
Святая корова, GHC хорош. Максимум, на что хватило моих 8 ГБ памяти, - это подсчет до 64 на каждой итерации, и это завершилось примерно за 20 секунд с тем же результатом, что и раньше. Я смирился с поражением на этом этапе.
Оказывается, набор программ, не использующих хальтинг, которые используют конечную память, рекурсивно перечислим, поэтому GHC теоретически может обнаружить любую такую программу и остановиться. И единственные другие программы, не работающие с ошибкой, используют бесконечную память, поэтому они также не вешают GHC, как я надеялся.
GHC делает это? Даже с
UndecidableInstances, невосприимчив к ли он зависанию, не потребляя при этом еще больше памяти, как постулирует Луки?
Я перевел интерпретатор и программу на шаблоны C++ и наблюдал примерно такое же поведение из GCC, но с падением вместо нижнего значения.