«Стек» в схеме. Что делает его особенным?

Question

Прочитав о Схеме, я наткнулся на это утверждение.

"Эквивалент схемы стека активации - это действительно цепочка частичных продолжений (записей приостановки)."

Я немного запутался в том, что это на самом деле означает. Что отличает стеки схем, скажем, от C?

Answer 1

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

Даниэль П. Фридман. «Приложения продолжений: приглашенный учебник». 1988 Основы языков программирования (POPL88). Январь 1988 г. http://www.cs.indiana.edu/hyplan/dfried/appcont.pdf

Если вы подсели на продолжения, вы найдете здесь много интересных статей: http://library.readscheme.org/page6.html

Answer 2

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

Answer 3

В C ваш стек будет немного больше, чем последовательность указателей памяти, сообщающих вам, где вы были, когда вы остановились.

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