Понимание STG

Конструкция GHC основана на чем-то, называемом STG, который обозначает "бесхребетную, безглазную G-машину".

Теперь G-машина, по-видимому, не подходит для "машины сокращения графа", в которой реализована ленивость. Неоцененные thunks хранятся в виде дерева выражений, а выполнение программы сводится к уменьшению их до нормальной формы. (Дерево - это ациклический граф, но повсеместная рекурсия Haskell означает, что выражения Haskell образуют общие графики, следовательно, сокращение графа, а не древообразование.)

Чем менее ясны термины "бесхребетность" и "безбрежность".

Я думаю, что "бесхребетность" относится к тому факту, что функциональные приложения не имеют "позвоночника" узлов приложений приложения. Вместо этого у вас есть объект, который называет вызываемую функцию и указывает на все ее аргументы. Это правильно?
Я думал, что "tagless" ссылается на то, что узлы-конструкторы не "помечены" идентификатором конструктора, и вместо этого case-выражения разрешаются с помощью команды перехода. Но теперь я не уверен, что это правильно. Вместо этого он, похоже, ссылается на то, что узлы не помечены своим состоянием оценки. Может ли кто-нибудь уточнить, какие (если таковые имеются) эти интерпретации верны?

Ответ 1

GHC wiki содержит вводную статью о STG, написанную Максом Болингброком:

Я знаю кунг-фу: изучение STG на примере

Машина STG является неотъемлемой частью GHC, ведущего в мире компилятора Haskell. Он определяет, как модель оценки Haskell должна быть эффективно реализована на стандартном оборудовании. Несмотря на эту ключевую роль, она обычно плохо понимается среди пользователей GHC. Этот документ призван предоставить обзор машины STG в ее современном воплощении с тегами-указателями на основе eval/apply с помощью серии простых примеров, показывающих, как компилируется исходный код Haskell.

Ответ 2

Вы правы в отношении "Без спины", то есть, если я прав. Это в основном описано в статье 1988 года Берна, Пейтона-Джонса и Робсона "The Spineless G-Machine". Я прочитал его, но это не так свежо в моем сознании. В принципе, на G-Machine все записи стека указывают на приложение node, кроме одного сверху, которое указывает на главу выражения. Эти узлы приложения предоставляют доступ к аргументам косвенным образом и в некоторых описаниях G-Machine перед применением функции стек перестраивается, так что последние n узлов в стеке указывают на аргумент вместо приложения node, Если я не ошибаюсь, часть "Без спины" заключается в том, чтобы избежать того, чтобы эти узлы приложения (которые называются позвоночником графа) в стеке вообще, тем самым избегая повторной компоновки перед каждой редукцией.

Что касается части "Без тегов", вы теперь более корректны, чем раньше, но... Использование тегов на узлах - очень, очень старая вещь. Можете ли вы подумать о том, как был реализован динамически типизированный язык, такой как LISP? Каждая ячейка должна иметь свою ценность и тег, который указывает тип. Если вы хотите что-то, вы должны изучить тег и действовать соответствующим образом. В случае Haskell состояние оценки более важно, чем тип, Haskell статически типизирован.

В машине STG теги не используются. Метки были заменены, возможно, благодаря вдохновению Oan lanaguages набором наборов функций. Если вы хотите, чтобы значение node не было вычислено, функция вычислит его. Когда он уже вычислен, функция возвращает его. Это позволяет много творчества в том, что может сделать эта функция, не делая более сложным клиентский код.

Эта часть "без тегов" да, описывается в статье "Применение функциональных языков на складе" от SPJ.

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

Ответ 3

Вы хотите прочитать книгу SPJ о функциональной реализации PL:

http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/index.htm

Ответ 4

Ответ от migle - это именно то, что означает бессмысленность и безбрежность STGM. Сегодня не стоит пытаться понять имена двух функций, потому что имена основаны на истории технологий сокращения графов: от G-машины, Spiceless G-machine и Spiceless и Tagless G-machine.

G-машина использует как позвоночник, так и теги. Позвоночник - это список ребер из корневого узла приложения функции в узел функции. Например, приложение-функция "f e1 e2... en" представляется как

root = AP left_n en
left_n = AP left_n-1 en-1 ...
left_2 = AP left_1 e1
left_1 = FUN f

в G-машине, и поэтому позвоночник представляет собой список ребер, состоящих из left_n → left_n-1 ->... → left_2 → left_1. Это буквально позвоночник функции!

В том же приложении функции есть теги AP и FUN.

В следующем продвинутом G-машине, так называемом Spineless G-machine, нет такого позвоночника, представляя такое приложение-функцию в смежном блоке, чей первый слот указывает на f, второй слот указывает на e1,... и n + 1-й слот точки en. В этом представлении нам не нужен позвоночник. Но блок запускает специальный тег, обозначающий количество слотов и так далее.

В самой продвинутой G-машине, так называемой Spineless Tagless G-machine, такой тег заменяется указателем на функцию. Чтобы оценить приложение функции, нужно перейти к коду с помощью указателя функции.

Очень жаль, что бумага Симона Пейтона Джонса STGM не дает правил компиляции/оценки на каком-то абстрактном уровне, и поэтому людям очень нелегко понять суть STGM.