SECD-машина

Машина SECD — это очень влиятельная ( см. § Вклад Ландина ) виртуальная машина и абстрактная машина, предназначенная для использования в качестве цели для языков функционального программирования компиляторов . Буквы обозначают Stack , Environment , Control , Dump — внутренние регистры машины. Регистры Stack, Control и Dump указывают на (некоторые реализации) стеков , а Environment указывает на (некоторую реализацию) ассоциативного массива .

Эта машина была первой, специально разработанной для оценки выражений лямбда-исчисления . Первоначально он был описан Питером Дж. Ландином в «Механической оценке выражений». в 1964 году. Описание, опубликованное Ландином, было довольно абстрактным и оставляло открытыми многие варианты реализации (например, операционную семантику ).

Lispkit Lisp был влиятельным компилятором, основанным на машине SECD. а машина SECD использовалась в качестве цели для других систем, таких как Lisp/370. В 1989 году исследователи из Университета Калгари работали над аппаратной реализацией машины.

Вклад Ландина

Д.А. Тернер (2012) указывает, что язык программирования АЛГОЛ 60 не может возвращать функции из других функций (функции рендеринга больше не являются первоклассными). Функция, вложенная в другую функцию, может ссылаться на переменную, находящуюся в стеке внешней функции. Если бы вложенная функция была возвращена из внешней функции, она бы ссылалась на переменную в кадре стека, которой больше нет. Тернер отмечает, что машина SECD Ландина решает эту проблему (таким образом позволяя функциям возвращать функции), поскольку значение функции теперь представлено замыканием в куче, которое может хранить среду переменных, которые она должна использовать независимо от того, что происходит в стеке.

Неофициальное описание

Когда начинается вычисление выражения, оно загружается как единственный элемент управления. C. Окружающая среда E, куча S и свалить D начать пусто.

Во время оценки C он преобразуется в обратную польскую запись (RPN) с помощью ap (для apply ) является единственным оператором. Например, выражение F (G X) (один элемент списка) заменяется на список X:G:ap:F:ap.

Оценка C действует аналогично другим выражениям RPN. Если первый элемент в C это значение, оно помещается в стек S. Точнее, если элемент является идентификатором, значение, помещенное в стек, будет привязкой для этого идентификатора в текущей среде. E. Если элемент является абстракцией, замыкание создается для сохранения привязок его свободных переменных (которые находятся в E), и именно это замыкание помещается в стек.

Если предмет ap, два значения извлекаются из стека, и приложение завершает работу (первое применяется ко второму). Если результатом приложения является значение, оно помещается в стек.

Однако если приложение представляет собой абстракцию значения, в результате получится выражение лямбда-исчисления, которое само может быть приложением (а не значением), и поэтому не может быть помещено в стек. В этом случае текущее содержимое S, E, и C выбрасываются на свалку D (который представляет собой стопку этих троек), S повторно инициализируется до пустого состояния, и C повторно инициализируется для результата приложения с помощью E содержащий среду для свободных переменных этого выражения, дополненную привязкой, полученной в результате применения приложения. Затем оценка продолжается, как указано выше.

Завершенная оценка обозначается значком C быть пустым, и в этом случае результат будет в стеке S. Последнее сохраненное состояние оценки на D затем извлекается, и результат завершенной оценки помещается в содержимое стека, восстановленное из D. Затем оценка восстановленного состояния продолжается, как указано выше.

Если C и D оба пусты, общая оценка завершена, и результат помещен в стек S.

Регистры и память

Машина SECD основана на стеке . Функции берут свои аргументы из стека. Аргументы встроенных инструкций кодируются сразу после них в потоке команд.

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

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

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

Свалка, во главе которой D Точки регистра используются как временное хранилище для значений других регистров, например, во время вызовов функций. Его можно сравнить со стеком возврата других машин.

Организация памяти SECD-машины аналогична модели, используемой большинством интерпретаторов функциональных языков : ряд ячеек памяти, каждая из которых может содержать либо атом (простое значение, например 13 ), либо представлять собой пустое или не-значение. пустой список. В последнем случае ячейка содержит два указателя на другие ячейки: один представляет первый элемент, а другой представляет список, за исключением первого элемента. Два указателя традиционно называются car и cdr более современные термины «голова» и «хвост» соответственно, но вместо них часто используются . Различные типы значений, которые может содержать ячейка, различаются тегом . Часто выделяют также разные типы атомов (целые числа, строки и т. д.).

Итак, список, содержащий числа 1 , 2 и 3 , обычно записывается как (1 2 3), можно представить следующим образом:

Address   Tag       Content (value for integers, car & cdr for lists)

      9 [ integer |     2 ]
      8 [ integer |     3 ]
      7 [ list    | 8 | 0 ]
      6 [ list    | 9 | 7 ]
      ...
      2 [ list    | 1 | 6 ]
      1 [ integer |     1 ]
      0 [ nil             ]

В наш список не входят ячейки памяти с 3 по 5, ячейки которых могут быть распределены по памяти случайным образом. Ячейка 2 является главой списка, она указывает на ячейку 1, содержащую значение первого элемента, и на список, содержащий только 2 и 3 (начиная с ячейки 6). Ячейка 6 указывает на ячейку, содержащую 2, и на ячейку 7, которая представляет список, содержащий только 3 . Для этого он указывает на ячейку 8, содержащую значение 3 , и указывает на пустой список ( nil ) как cdr. В машине SECD ячейка 0 всегда неявно представляет пустой список, поэтому для обозначения пустого списка не требуется никакого специального значения тега (все, что необходимо, может просто указывать на ячейку 0).

Принцип, согласно которому cdr в ячейке списка должен указывать на другой список, является всего лишь соглашением. Если и car, и cdr указывают на атомы, это даст пару, обычно записываемую как (1 . 2)

Инструкция

• nil помещает нулевой указатель в стек
• ldc помещает постоянный аргумент в стек
• ld помещает значение переменной в стек. Переменная обозначается аргументом, парой. Автомобиль пары определяет уровень, CDR – позицию. Так (1 . 3) дает третий параметр текущей функции (уровень 1).
• sel ожидает два аргумента списка и извлекает значение из стека. Первый список выполняется, если полученное значение не равно нулю, второй список — в противном случае. Прежде чем один из этих указателей списка будет создан, будет создан новый C, указатель на следующую инструкцию $sel$ сохраняется в дампе.
• join извлекает ссылку на список из дампа и делает ее новым значением C. Эта инструкция встречается в конце обеих альтернатив sel.
• ldf принимает один аргумент списка, представляющий функцию. Он создает замыкание (пару, содержащую функцию и текущую среду) и помещает его в стек.
• ap извлекает замыкание и список значений параметров из стека. Замыкание применяется к параметрам путем установки его среды в качестве текущей, помещения списка параметров перед ним, очистки стека и установки C к указателю функции замыкания. Предыдущие значения S, E, и следующее значение C сохраняются в дампе.
• ret извлекает одно возвращаемое значение из стека, восстанавливает S, E, и C из дампа и помещает возвращаемое значение в текущий стек.
• dum помещает «пустой список» перед списком окружения.
• rap работает как $ap$, только то, что оно заменяет вхождение фиктивной среды на текущую, что делает возможными рекурсивные функции.

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

См. также

• ПРОВЕРИТЬ машину
• Кривые машины

Дальнейшее чтение

• Дэнви, Оливье . Рациональная деконструкция машины SECD Ландина . Отчет об исследовании БРИКС RS-04-30, 2004 г. ISSN 0909-0878
• Филд, Энтони Дж. Филд и Питер Г. Харрисон. 1988 Функциональное программирование . Аддисон-Уэсли. ISBN   0-201-19249-7
• Грэм, Брайан Т. 1992 «Микропроцессор SECD: пример проверки». Спрингер. ISBN   0-7923-9245-0
• Когге, Питер М. Архитектура символических компьютеров . ISBN   0-07-035596-7
• Ландин, П.Дж. (март 1966 г.). «Следующие 700 языков программирования» (PDF) . Комм. АКМ . 9 (3): 157–166. дои : 10.1145/365230.365257 . S2CID   13409665 . Архивировано из оригинала (PDF) 20 июня 2010 г. Проверено 28 августа 2015 г.

Внешние ссылки

• SECD коллекция