SECD-машина
Машина SECD — это очень влиятельная ( см. § Вклад Ландина ) виртуальная машина и абстрактная машина , предназначенная для использования в качестве цели для языков функционального программирования компиляторов . Буквы обозначают Stack , Environment , Control , Dump — внутренние регистры машины. Регистры Stack, Control и Dump указывают на (некоторые реализации) стеков , а Environment указывает на (некоторую реализацию) ассоциативного массива .
Эта машина была первой, специально разработанной для оценки выражений лямбда-исчисления . Первоначально он был описан Питером Дж. Ландином в «Механической оценке выражений». [1] в 1964 году. Описание, опубликованное Ландином, было довольно абстрактным и оставляло открытыми многие варианты реализации (например, операционную семантику ).
Lispkit Lisp был влиятельным компилятором, основанным на машине SECD. [2] а машина SECD использовалась в качестве цели для других систем, таких как Lisp/370. [3] В 1989 году исследователи из Университета Калгари работали над аппаратной реализацией машины. [4]
Вклад Ландина [ править ]
Д.А. Тернер (2012) [5] указывает, что язык программирования АЛГОЛ 60 не мог возвращать функции из других функций (функции рендеринга больше не являются первоклассными). Функция, вложенная в другую функцию, может ссылаться на переменную, находящуюся в стеке внешней функции. Если бы вложенная функция была возвращена из внешней функции, она бы ссылалась на переменную в кадре стека, которой больше нет. Тернер отмечает, что машина SECD Лэндина решает эту проблему (таким образом позволяя функциям возвращать функции), поскольку значение функции теперь представлено замыканием в куче, которое может хранить среду переменных, которые она должна использовать независимо от того, что происходит в стеке. [5]
Неофициальное описание [ править ]
Когда начинается вычисление выражения, выражение загружается как единственный элемент управления. 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), можно представить следующим образом:
Содержимое адресного тега (значение для целых чисел, car и cdr для списков)
9 [ целое число | 2 ]
8 [ целое число | 3 ]
7 [ список | 8 | 0 ]
6 [ список | 9 | 7 ]
...
2 [ список | 1 | 6 ]
1 [ целое число | 1 ]
0 [ ноль ]
В наш список не входят ячейки памяти с 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, указатель на следующую инструкцию сохраняется в дампе.joinизвлекает ссылку на список из дампа и делает ее новым значениемC. Эта инструкция встречается в конце обеих альтернативsel.ldfпринимает один аргумент списка, представляющий функцию. Он создает замыкание (пару, содержащую функцию и текущую среду) и помещает его в стек.apизвлекает замыкание и список значений параметров из стека. Замыкание применяется к параметрам путем установки его среды в качестве текущей, помещения списка параметров перед ним, очистки стека и установкиCк указателю функции замыкания. Предыдущие значенияS,E, и следующее значениеCсохраняются в дампе.retизвлекает одно возвращаемое значение из стека, восстанавливаетS,E, иCиз дампа и помещает возвращаемое значение в текущий стек.dumпомещает «пустой список» перед списком окружения.rapработает как , только то, что оно заменяет появление фиктивной среды на текущую, что делает возможным использование рекурсивных функций.
Существует ряд дополнительных инструкций для основных функций, таких как car, cdr, построение списка, сложение целых чисел, ввод-вывод и т. д. Все они берут любые необходимые параметры из стека.
См. также [ править ]
Ссылки [ править ]
- ^ Ландин, П.Дж. (январь 1964 г.). «Механическая оценка выражений» . Вычислить. Дж. 6 (4): 308–320. дои : 10.1093/comjnl/6.4.308 .
- ^ Хендерсон, Питер (1980). Функциональное программирование: применение и реализация . Энглвуд Клиффс, Нью-Джерси: Prentice-Hall International. ISBN 0-13-331579-7 .
- ^ Пэджет, Джулиан. «Три необычных Лиспа». CiteSeerX 10.1.1.99.1028 .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ документ о дизайне SECD: ПРОБЛЕМЫ ДИЗАЙНА . Доступен
- ^ Перейти обратно: а б «Д. А. Тернер «Некоторые истории языков функционального программирования» в приглашенной лекции TFP12 , Университет Сент-Эндрюс, 12 июня 2012 г. См. раздел «Алгол 60» (PDF) .
Дальнейшее чтение [ править ]
- Дэнви, Оливье . Рациональная деконструкция машины 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 г.