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

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

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

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

Оператор "goto &NAME" в Perl ближе к тому, о чем вы думаете, но не вполне, поскольку это отбрасывает местных жителей. Параметры для вновь вызванной функции сохраняются.

Еще одно простое отличие: хвостовой вызов может переходить только к точке входа функции, в то время как goto может переходить практически куда угодно (некоторые языки ограничивают цель goto, например C, где goto не может перейти за пределы функции).

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

Кроме того, он также может обнаруживать круговую хвостовую рекурсию, например

test() -> ..., test2().
test2() -> ..., test3().
test3() -> ..., test().

также будет оптимизирован.

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

У вас есть два вопроса.

Во-первых, нет, в этом случае вам не грозит переполнение стека, потому что оба этих вызова test () являются хвостовая рекурсия.

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

Я думаю, что разница здесь между «настоящим» goto и тем, что в некоторых случаях может показаться goto. В некоторых особых случаях компилятор может определить, что он может очистить стек текущей функции перед вызовом другой функции. Это когда вызов является последним вызовом функции. Разница, конечно же, в том, что, как и в любом другом вызове, вы можете передавать аргументы новой функции.

Как отмечали другие, эта оптимизация не ограничивается рекурсивными вызовами, а всеми последними вызовами. Это используется в «классическом» способе программирования конечных автоматов.

Это goto в том же смысле, почему if это goto, а while это goto. Он реализован с использованием (морального эквивалента) goto, но он не раскрывает весь потенциал goto, позволяющий стрелять себе в ногу, напрямую программисту.

По словам Гая Стила, эти рекурсивные функции являются окончательным GOTO.

Вот более общий ответ, который заменяет мой предыдущий ответ, основанный на стеках вызовов. Поскольку предыдущий ответ был принят, я не буду заменять текст.

Пролог

В некоторых архитектурах нет вещей, которые они называют «функциями», которые «вызываются», но у них есть нечто аналогичное (обмен сообщениями может называть их «методами» или «обработчиками сообщений»; архитектуры, основанные на событиях, имеют «обработчики событий» или просто «обработчики»). ). Я буду использовать термины «блок кода» и «вызов» для общего случая, хотя (строго говоря) «блок кода» может включать в себя вещи, которые не являются полностью функциональными. Вы можете заменить «invocation» или «invoke» соответствующей изменяемой формой «call», как я мог бы в некоторых местах. Характеристики архитектуры, описывающие вызов, иногда называют «стилями», например, «стилем передачи продолжения» (CPS), хотя ранее это не было официальным термином. Чтобы вещи не были слишком абстрактными, мы рассмотрим стек вызовов, передачу продолжения, обмен сообщениями (а-ля ООП) и стили вызова обработки событий. Я должен указать модели, которые я использую для этих стилей, но я опускаю их из соображений экономии места.

Особенности вызова

или, C для продолжения, координации и контекста, для меня этого достаточно

Hohpe идентифицирует три красиво аллитерационные функции вызова стиля стека вызовов: продолжение, координация, Контекст (все с заглавной буквы, чтобы отличить их от других употреблений слов).

• Продолжение решает, где будет продолжено выполнение после завершения блока кода. Функция «Продолжение» связана с «первоклассными продолжениями» (часто называемыми просто «продолжениями ", в том числе мной), поскольку продолжения делают функцию продолжения видимой и управляемой на программном уровне.
• Координация означает, что код не выполняется, пока не будут готовы необходимые данные. В пределах одного стека вызовов вы получаете координацию бесплатно, потому что счетчик программы не вернется к функции, пока вызываемая функция не завершится. Координация становится проблемой (например) при параллельном программировании и программировании, управляемом событиями: первое связано с тем, что производитель данных может отставать от потребителя данных, а второе - потому, что, когда обработчик запускает событие, обработчик немедленно продолжает работу, не дожидаясь ответа.
• Контекст относится к среде, которая используется для разрешения имен в блоке кода. Он включает выделение и инициализацию локальных переменных, параметров и возвращаемых значений. Передача параметров также регулируется соглашением о вызовах (соблюдение аллитерации); в общем случае вы можете разделить Context на функцию, которая охватывает локальных жителей, одну, которая охватывает параметры, а другая - для возвращаемых значений. Для CPS возвращаемые значения покрываются передачей параметров.

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

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

Задачи функции вызова

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

Хвостовые звонки

или Ответ

или остальное в принципе не нужно

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

Хвостовые вызовы в определенных стилях вызова

Различные стили упорядочивают цепочки вызовов в разных структурах, которые я назову «клубок», за неимением лучшего слова. Разве не приятно, что мы отказались от спагетти-кода?

• Со стеком вызовов в клубке есть только одна цепочка вызовов; удлинение цепочки означает нажатие счетчика программ. Хвостовой вызов означает, что счетчик программы не выдвигается.
• В CPS клубок состоит из существующих продолжений, которые образуют обратный arborescence (направленное дерево, каждое ребро которого указывает на центральный узел), где каждый путь возвращается к центру представляет собой цепочку вызовов (примечание: если точка входа в программу передается "нулевым" продолжением, клубок может быть целым лесом обратных ветвей). По умолчанию используется одна конкретная цепочка, в которую во время вызова добавляется ссылка на вызов. Хвостовые вызовы не добавляют ссылку на вызов в цепочку вызовов по умолчанию. Обратите внимание, что «цепочка вызовов» здесь в основном синонимична «продолжению» в смысле «продолжение первого класса».
• При передаче сообщений цепочка вызовов - это цепочка заблокированных методов, каждый из которых ожидает ответа от метода перед ним в цепочке. Метод, вызывающий другого, называется «клиентом»; вызываемый метод - это «поставщик» (я намеренно не использую «сервис», хотя «поставщик» не намного лучше). Связка сообщений - это набор несвязанных цепочек вызовов. Эта структура путаницы больше похожа на наличие нескольких стеков потоков или процессов. Когда метод просто повторяет ответ другого метода как свой собственный, метод может заставить своего клиента ждать своего поставщика, а не самого себя. Обратите внимание, что это дает немного более общую оптимизацию, которая включает оптимизацию координации, а также продолжения. Если последняя часть метода не зависит от ответа (и ответ не зависит от данных, обработанных в последней части), метод может продолжаться после того, как он будет передан поставщику в зависимости от ожидания клиента. Это аналогично запуску нового потока, где последняя часть метода становится основной функцией потока, за которой следует хвостовой вызов в стиле стека вызовов.

А как насчет стиля обработки событий?

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

1. Слушатель Алиса подписывается на событие «инаугурация» на BBC News, используя обработчик «party»
2. Алиса запускает мероприятие «Выборы» на канале BBC News
3. Боб ожидает "выборы" на BBC News, поэтому вызывается обработчик "openPolls" Боба.
4. Боб подписывается на событие «инаугурация» на канале CNN.
5. Боб запускает мероприятие «голосование» на канале CNN
6. Другие события запускаются и обрабатываются. В конце концов, один из них (например, «победа») запускает событие «инаугурация» на CNN.
7. Запрещенный куратор Боба объявил "инаугурацию" на BBC News
8. Вызывается обработчик инаугурации Алисы.

И оптимизированная версия:

1. Слушательница Алиса подписывается на событие «инаугурация» на BBC News.
2. Алиса запускает мероприятие «Выборы» на канале BBC News
3. Боб ожидает "выборы" на BBC News, поэтому вызывается обработчик "openPolls" Боба.
4. Боб подписывает всех, кто слушает «инаугурацию» на BBC News, на мероприятие инаугурации на CNN *.
5. Боб запускает мероприятие «голосование» на канале CNN
6. Другие события запускаются и обрабатываются. В конце концов, один из них запускает мероприятие «инаугурация» на CNN.
7. Обработчик инаугурации Алисы вызывается для инаугурации на CNN.

Обратите внимание, что хвостовые вызовы сложнее (несостоятельны?) При обработке событий, потому что они должны учитывать подписки. Если бы Алиса позже отказалась от подписки на «инаугурацию» на BBC News, подписку на инаугурацию на CNN также пришлось бы отменить. Кроме того, система должна гарантировать, что она не вызывает ненадлежащим образом обработчик несколько раз для слушателя. Что, если в приведенном выше оптимизированном примере есть другой обработчик «инаугурации» на CNN, который запускает «инаугурацию» на BBC News? Событие "вечеринки" Алисы будет запущено дважды, что может вызвать у нее проблемы на работе. Одно из решений состоит в том, чтобы * Боб отменил подписку всех слушателей на «инаугурацию» на BBC News на шаге 4, но затем вы вводите другую ошибку, при которой Алиса будет пропускать инаугурации, которые не поступают через CNN. Может быть, она хочет отпраздновать инаугурации в США и Великобритании. Эти проблемы возникают из-за того, что я не делаю различий в модели, возможно, на основе типов подписок. Например, возможно, существует особый вид одноразовой подписки (например, Обработчики сигналов System-V) или некоторые обработчики сами отписываются, и оптимизация хвостового вызова применяется только в этих случаях.

Что дальше?

Вы можете перейти к более полному определению задач функции вызова. Отсюда вы можете выяснить, какие оптимизации возможны и когда их можно использовать. Возможно, удастся идентифицировать другие функции вызова. Вы также можете придумать больше примеров стилей вызова. Вы также можете изучить зависимости между функциями вызова. Например, синхронный и асинхронный вызовы включают явное связывание или разъединение продолжения и координации. Это никогда не кончится.

Получите все это? Я все еще пытаюсь переварить это сам.

Использованная литература:

1. Хохпе, Грегор; "Event-Driven Architecture"
2. Сугальский, Дэн; "CPS и хвостовые вызовы - два отличных вкуса, которые прекрасно сочетаются друг с другом "

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

(на мой взгляд, goto - это вызов функции без возможности возврата туда, откуда вы пришли). Именно это и происходит в примере с erlang.

Это не то, что происходит в Erlang, вы МОЖЕТЕ вернуться туда, откуда пришли.

Вызовы хвостовой рекурсии, что означает, что это «своего рода» goto. Убедитесь, что вы понимаете, что такое хвостовая рекурсия, прежде чем пытаться понять или написать какой-либо код. Прочитать книгу Джо Армстронга, вероятно, неплохая идея, если вы новичок в Erlang.

По идее, в случае, когда вы вызываете себя с помощью test (), тогда выполняется вызов в начало функции с использованием любых параметров, которые вы передаете (в этом примере нет), но больше ничего не добавляется в стек. Таким образом, все ваши переменные выбрасываются, и функция запускается заново, но вы не помещали новый указатель возврата в стек. Так что это похоже на гибрид между goto и вызовом функции в традиционном императивном стиле языка, как в C или Java. Но есть еще одна запись в стеке с самого первого вызова из вызывающей функции. Поэтому, когда вы в конечном итоге выходите, возвращая значение, а не выполняя другой test (), это место возврата извлекается из стека, и выполнение возобновляется в вашей вызывающей функции.