Существуют ли полностью оптимизирующие компиляторы для завершающих программ?

20

В книге Эндрю У. Аппеля « Реализация современного компилятора в ML» он говорит в главе 17, что теория вычислимости показывает, что всегда можно изобрести новые оптимизирующие преобразования, и продолжает доказывать, что полностью оптимизирующий компилятор решит проблему остановки: Программа Q, который не производит никакого вывода и никогда не останавливается, может быть легко заменен его оптимальным представлением, Opt (Q) , являющимся "L: goto L". Таким образом, полностью оптимизирующий компилятор может решить проблему остановки.

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

Кроме того, каковы последствия ограничения нас на прекращение программ?

Симон 'Восстанови Монику' Блеск
источник
2
Трудно даже найти оптимальную последовательность команд для одного блока кода без какого-либо потока управления. Superoptimization статья в Википедии дает хорошее введение (с цитатами.)
блуждающих Logic
В статье Википедии упоминается, что супероптимизация рассматривает последовательности инструкций без петель. Полагаю, отсутствие петель - это еще один способ сказать, что оно заканчивается. Если коротко взглянуть на доступные ссылки, то это представляется возможным, но чрезвычайно дорогим.
Саймон 'Восстанови Монику' Сияние
2
Что означает «оптимизировать» здесь? Меньшее время выполнения? Если да, то какие: наихудший случай, средний случай, каждый случай, какой-то случай, ...?
Рафаэль

Ответы:

16

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

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

Напомним, что следующая проблема не вычислима:

Учитывая неконтекстную грамматику с терминальным алфавитом Σ , решите, будет ли L ( G ) = Σ .GΣL(G)=Σ

Кроме того, обратите внимание, что с учетом неконтекстной грамматики мы можем жестко закодировать, скажем, алгоритм CYK для этой одной грамматики; Обозначим этот алгоритм на C Y K G . Заметим, что C Y K G заканчивается для всех входов (из Σ ).GCYKGCYKGΣ

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

Opt(CYKG)='return true;'L(G)=Σ

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

Рафаэль
источник
ΣL(G)G
3
ΣMPM(i)MiOPT(PM)'return false;'M
sdcvvc