Оптимизация вызова хвоста C

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

Кроме того, что было причиной отказа от оптимизации вызова хвоста из стандарта?

Ответ 1

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

Ответ 2

Чтобы ответить на последний вопрос: стандарт должен определенно не делать никаких утверждений об оптимизации. Там могут быть среды, где это более или менее сложно реализовать.

Ответ 3

Я думаю, что оптимизация хвостовых вызовов должна быть гарантирована только там, где ожидаются или требуются много рекурсии; то есть на языках, которые поощряют или применяют стиль функционального программирования. (С этими типами языков вы можете обнаружить, что циклы for или while либо сильно обескуражены, либо воспринимаются как неэлегантные, либо, возможно, даже полностью отсутствуют на этом языке, поэтому вы прибегаете к рекурсии по всем этим причинам и, возможно, больше.)

Язык программирования C (IMHO) явно не был разработан с учетом функционального программирования. Там все виды конструкций цикла, которые обычно используются в пользу рекурсии: for, do .. while, while. На таком языке было бы нецелесообразно предписывать оптимизацию хвостового вызова в стандарте, поскольку он не должен строго гарантировать рабочие программы.

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

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

Ответ 4

Несмотря на то, что современные компиляторы МОГУТ оптимизировать хвостовые вызовы, если вы включите оптимизацию, ваши сборки отладки, вероятно, будут работать без нее, чтобы вы могли получать трассировки стека и входить в/из кода и замечательные вещи. В этой ситуации оптимизация хвостового вызова не требуется.

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

Ответ 5

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