Я изучаю методы реализации языков программирования и недавно натолкнулся на стеки спагетти, которые предположительно хорошо подходят для модели стиля передачи продолжения (учитывая их использование, например, в Scheme и SML / NJ ). Для упрощения, давайте рассмотрим только однопоточные процессы для этого вопроса.

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

Но мое понимание этой реализации довольно расплывчато, так что я, наверное, что-то упустил. Я надеюсь, что кто-то может рассказать мне о «стеках вызовов спагетти», под которыми я подразумеваю структуру данных, используемую в Scheme и / или SML / NJ для реализации процессов на основе CPS.

1. Учитывая следующий стек вызовов спагетти:

   [exit point] <-- ... <-- [frame A] <-- [frame B (active)]
                                   ^
                                    `---- [frame C]
   

   Насколько я понимаю, любое управление потоком из B либо раскручивает стек путем перехода к родителю (A становится активным, недостижимый B теперь мусором), либо заменяет активный фрейм подграфом, связанным только с использованием ссылок, содержащихся в B, или ссылок в новые кадры. Выполнение не может перейти к кадру C, что должно означать, что кадр C является мусором.

2. Вместо предыдущей ситуации я думаю, что может возникнуть следующая ситуация без мусора:

   [exit point] <-- ... <-- [frame W] <-- [frame X] <-- [frame Z (active)]
                                   ^                     |
                                    `---- [frame Y] <---´
   

   Например, я могу представить, что кадр Z принадлежит некоторой решающей функции, которая либо продолжается с кадра X, либо с кадра Y (любой из которых вернется к W). Это означает, что стеки вызовов спагетти не являются « деревьями родительских указателей ».

3. Тем не менее, я не могу представить себе ситуацию, когда цикл может быть построен. Возьмем следующую ситуацию, например:

   [exit point] <-- ... <-- [frame P] --> [frame Q (active)]
                                   ^             |
                                   |             v
                                    `---- [frame R]
   

   Я знаю, что рекурсивные привязки - вещь, но я очень сомневаюсь, что это разумно. Если Q вернется к R, кадр Q «израсходован». Если R должен был вернуться к P, а P не может просто вернуться к Q, так как он должен быть сначала инициализирован заново. Таким образом, петли могут привести к несовместимым состояниям. (Если, конечно, я неправильно понимаю назначение этой структуры данных, и вы будете использовать только узлы в ней в качестве шаблона для текущего кадра.)

Из этих наблюдений я должен сделать вывод, что стек вызовов спагетти (без мусора) на самом деле является DAG. Это правильно? Или я неправильно понимаю цель этой структуры данных?

Обновления:

• Я пролистал копию следующего документа:

  Е. А. Хаук и Б. А. Дент. 1968. Механизм стека Берроуза B6500 / B7500. В материалах 30 апреля - 2 мая 1968 г. весенняя совместная компьютерная конференция (AFIPS '68 (весна)). ACM, Нью-Йорк, Нью-Йорк, США, 245-251. DOI = http://dx.doi.org/10.1145/1468075.1468111

  Эта статья, кажется, определяет систему стека Suguaro. Как оказалось, эта система стека Suguaro является традиционным стеком вызовов, который позволяет нескольким «заданиям» проходить через кадры частично совместно используемого стека; это абсолютно не связано с продолжениями.

• Следующая статья (и сопутствующая статья 1996 г.), по-видимому, объясняет, что происходит в компиляторе SML / NJ:

  Чжун Шао и Эндрю У. Аппель. 2000. Эффективное и безопасное преобразование закрытия. ACM Trans. Программа. Lang. Сист. 22, 1 (январь 2000 г.), 129-161. DOI = http://dx.doi.org/10.1145/345099.345125

  Я думаю, что я должен прочитать эту статью ( копия на сайте автора ), прежде чем делать что-либо еще с этим вопросом. Концепция «Безопасно связанных замыканий» очень похожа на систему стеков Suguaro, поскольку она всегда очень поверхностна и предназначена только для совместного использования свободных переменных:

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

  В документе также явно упоминается, что он не использует «любой стек времени выполнения»:

  Вместо этого мы рассматриваем все записи активации как замыкания для функций продолжения и размещаем их в регистрах в куче.

  Я думаю, что неправильно понял и / или неправильно прочитал статью в Википедии, так как стеки спагетти не используются для управления потоком. Однако, после внимательного прочтения статей Аппеля и Шао, я, возможно, мог бы переформулировать вопрос со ссылкой на график зависимостей замыканий, а не на «стек вызовов спагетти» (который, очевидно, не является чем-то особенным).

Являются ли спагетти стеки родительскими указателями деревьев?

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

Каждый процесс в системе будет иметь один из этих списков, который представляет свой стек управления. Глава списка - это верхняя часть стека (т. Е. Активный кадр). Его nextуказатель ссылается на родительский фрейм.

На диаграмме вы видите структуру для нескольких процессов. Стек для «активного» процесса подсвечивается. Части дерева, которые не являются частью активного стека, выделены серым цветом. Они представляют стеки для других процессов.

Стеки спагетти образуют DAG?

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

Ваш пример функции принятия решения объединяет структуру стека управления с данными, хранящимися в стеке. Конечно, любая структура может быть сформирована, если мы начнем рассматривать данные. Но в качестве структуры данных каждый узел в стеке спагетти будет иметь ровно одного родителя.