Хвостовые вызовы в архитектурах без стека вызовов

Question

Мой ответ на недавний вопрос о GOTO и хвостовой рекурсии был сформулирован в терминах стека вызовов.Я обеспокоен тем, что это было недостаточно общее, поэтому я спрашиваю вас:как понятие конечного вызова (или эквивалента) полезно в архитектурах без стека вызовов?

При передаче продолжения все вызываемые функции заменяют вызывающую функцию и, таким образом, являются хвостовыми вызовами, поэтому "хвостовой вызов" не кажется полезным различием.В архитектурах, основанных на обмене сообщениями и событиях, похоже, нет эквивалента, хотя, пожалуйста, поправьте меня, если я ошибаюсь.Последние две архитектуры являются интересными примерами, поскольку они связаны с ООП, а не с FP.А как насчет других архитектур?Были ли старые машины Lisp основаны на стеках вызовов?

Редактировать:Согласно "Что, черт возьми, такое:Стиль прохождения продолжения (CPS)" (и Алекс ниже), эквивалентом конечного вызова при передаче продолжения является не "вызываемая функция заменяет вызывающую функцию", а "вызывающая функция передает продолжение, которое ей было дано, вместо создания нового продолжения".Этот тип хвостового вызова полезен, в отличие от того, что я утверждал.

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

Answer 1

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

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

Перевести вызов tail в асинхронную обработку событий сложнее, поэтому вместо этого рассмотрим более общую версию.Если A подписан на событие на канале 1, B подписан на то же событие на канале 2, а обработчик B просто запускает событие на канале 1 (он транслирует событие по каналам), тогда A может быть подписан на событие на канале 2 вместо подписки B.Это более общее, потому что эквивалент конечного вызова требует, чтобы

• Подписка A на канал 1 будет отменена, когда A подпишется на канал 2
• обработчики самостоятельно отписываются (при вызове они отменяют подписку)

Теперь для двух систем, которые не выполняют дополнительных вычислений:лямбда-исчисление (или системы переписывания терминов в целом) и RPN.Для лямбда-исчисления конечные вызовы примерно соответствуют последовательности сокращений, где длина члена равна O(1) (см. Итерационные процессы в Раздел 1.2 SICP).Используйте RPN для использования стека данных и стека операций (в отличие от потока операций;операции - это те, которые еще предстоит обработать), и среда, которая сопоставляет символы с последовательностью операций.Конечные вызовы могут соответствовать процессам с ростом стека O(1).

Answer 2

"Архитектуры без стека вызовов" обычно "имитируют" его на некотором уровне - например, во времена IBM 360 мы использовали Соглашение о соединении S-Типа использование областей сохранения регистра и списков аргументов, обозначенных, по соглашению, определенными регистрами общего назначения.

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

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