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

Question

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

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

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

• Stackless Python
• PyPy
• Лисп
• Схема
• Tcl
• Lua
• Попугай В.М.

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

Answer 1

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

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

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

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

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

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

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

Answer 2

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

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

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

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