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

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

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

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

  • Stackless Python
  • PyPy
  • шепелявость
  • Схема
  • Tcl
  • Lua
  • Попугай В.М.

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

Источник

2 ответа

Решение

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

Да, это правильно.

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

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

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

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

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

Источник

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

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

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

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