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

Question

Согласно этому ответу

https://stackoverflow.com/questions/551950/what-stackless-programming-languages-are-available/671296#671296

все эти языки программирования не содержат стеков

• Питон без стека
• ПыПи
• Шепелявый
• Схема
• Tcl
• Lua
• Parrot виртуальная машина

Что на самом деле означает для них отсутствие стеков?Означает ли это, что они не используют стек вызовов?Если они не используют стек вызовов, то что они используют?

Answer 1

Что на самом деле означает для них отсутствие стеков?Означает ли это, что они не используют стек вызовов?

Да, это примерно так.

Если они не используют стек вызовов, то что они используют?

Точная реализация, конечно, будет варьироваться от языка к языку.В Stackless Python есть диспетчер, который запускает интерпретатор Python, используя самый верхний фрейм и его результаты.Интерпретатор обрабатывает коды операций по мере необходимости по одному за раз, пока не достигнет CALL_FUNCTION код операции, сигнал, который вы собираетесь ввести в функцию.Это заставляет диспетчер создавать новый фрейм с соответствующей информацией и возвращаться к диспетчеру с флагом разматывания.Оттуда диспетчер начинает заново, указывая переводчику на самый верхний кадр.

Языки без стеков избегают стеков вызовов по ряду причин, но во многих случаях это используется для того, чтобы определенные программные конструкции становились намного проще в реализации.Каноническим из них является продолжения.Продолжения - это очень мощные и очень простые управляющие структуры, которые могут представлять любую из обычных управляющих структур, с которыми вы, вероятно, уже знакомы (while, do, if, switch, et cetera).

Если это сбивает с толку, вы можете попробовать разобраться в статье Википедии, и в частности в cutesy продолжение аналогии с бутербродом:

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

Answer 2

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

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

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

1. блоки exception / finally / etc очень легко моделируются - если вы можете передать одно продолжение "return" в качестве аргумента, вы можете передать 2 (или более) так же легко.блоки "обработчика условий" lisp-y (которые могут возвращать или не возвращать управление вызывающей стороне) также просты - передайте продолжение для остальной части этой функции, которая может быть вызвана, а может и не быть.
2. Аналогичным образом упрощается использование нескольких возвращаемых значений - передайте несколько аргументов в продолжение.
3. Возвращаемые временные значения / копирование больше не отличаются от передачи аргумента функции.Это часто облегчает устранение временных ограничений.
4. Оптимизация хвостовой рекурсии тривиальна - вызывающий просто передает полученное им продолжение "return", а не записывает новое.