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

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

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

Edit: согласно "What the heck is: Continuation Passing Style (CPS) "(и Алекс ниже), эквивалент хвостового вызова при передаче продолжения - это не "вызываемая функция заменяет вызывающую функцию", а " вызывающая функция передает продолжение, которое ему было дано, а не создает новое продолжение". Этот тип хвостового вызова полезен, в отличие от того, что я утверждал.

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

2 2
functional-programming tail-call-optimization callstack

2 ответа:

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

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

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

4

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

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

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

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

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

2