Машина SECD - это очень влиятельная ( см .: § Вклад Ландина ) виртуальная машина и абстрактная машина, предназначенная как цель для компиляторов языков функционального программирования . Эти буквы обозначают S клейкости, E nvironment, C ontrol, D UMP-внутренние регистры машины. Регистры Stack, Control и Dump указывают на (некоторые реализации) стеки , а Environment указывает на (некоторую реализацию) ассоциативный массив .
Эта машина была первой, специально разработанной для вычисления выражений лямбда-исчисления . Первоначально он был описан Питером Дж. Ландином в «Механической оценке выражений» [1] в 1964 году. Описание, опубликованное Ландином, было довольно абстрактным и оставляло множество вариантов реализации открытыми (например, операционная семантика ). Следовательно , машина SECD часто представлена в более детальном виде, например, Питер Хендерсон «ы Lispkit лисповского компилятора, который был распространен с 1980 года С тех пор он был использован в качестве мишени для нескольких других экспериментальных составителей.
В 1989 году исследователи из Университета Калгари работали над аппаратной реализацией машины. [2]
Вклад Ландина [ править ]
Д. А. Тернер (2012) [3] указывает, что «Пересмотренный отчет по Алголу 60» ( Naur 1963) определяет вызов процедуры с помощью правила копирования, которое позволяет избежать захвата переменных с систематической сменой идентификаторов. Этот метод работает в реализации Algol 60, но в функциональном языке программирования, где функции являются первоклассными гражданами, свободная переменная в стеке вызовов может быть разыменована по ошибке.
Тернер отмечает, что Ландин решил эту проблему с помощью своей машины SECD, в которой функция вместо этого представлена закрытием в куче. [3]
Неофициальное описание [ править ]
Когда начинается оценка выражения, выражение загружается как единственный элемент управления C
. Окружение E
, стек S
и дамп D
начинаются пустыми.
Во время оценки C
он преобразуется в обратную польскую нотацию (RPN), где ap
(для применения ) является единственным оператором. Например, выражение 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 могут реализовать стек как каноническую структуру стека, таким образом повышая общую эффективность виртуальной машины при условии, что размер стека будет строго ограничен.
В C
пунктах регистра во главе списка кодов или команд , которые будут оценены. Как только инструкция там была выполнена, C
указывается на следующую инструкцию в списке - это похоже на указатель инструкций (или счетчик программ ) в обычных машинах, за исключением того, что последующие инструкции всегда указываются во время выполнения и по умолчанию не содержатся. в последующих ячейках памяти, как в обычных машинах.
Текущее окружение переменных управляется E
регистром, который указывает на список списков. Каждый отдельный список представляет один уровень среды: параметры текущей функции находятся в заголовке списка, переменные, которые свободны в текущей функции, но связаны окружающей функцией, находятся в других элементах E
.
Дамп, на вершину которого D
указывает регистр, используется как временное хранилище для значений других регистров, например, во время вызовов функций. Его можно сравнить со стеком возврата других машин.
Организация памяти машины SECD аналогична модели, используемой большинством интерпретаторов функционального языка : количество ячеек памяти, каждая из которых может содержать либо атом (простое значение, например 13 ), либо представлять пустое или непустое значение. пустой список. В последнем случае ячейка содержит два указателя на другие ячейки, одна из которых представляет первый элемент, а другая представляет список, за исключением первого элемента. Два указателя традиционно называются car и cdr соответственно, но вместо них часто используются более современные термины голова и хвост . Различные типы значений, которые может содержать ячейка, различаются тегом. Часто также различают разные типы атомов (целые числа, строки и т. Д.).
Итак, список, содержащий числа 1 , 2 и 3 , обычно записываемый как (1 2 3)
, может быть представлен следующим образом:
Содержимое адресного тега (значение для целых чисел, автомобиль и 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
. Эта инструкция находится в конце обоих вариантов asel
.ldf
принимает один аргумент списка, представляющий функцию. Он создает замыкание (пару, содержащую функцию и текущую среду) и помещает ее в стек.ap
выдает закрытие и список значений параметров из стека. Замыкание применяется к параметрам, устанавливая его среду как текущую, помещая перед ней список параметров, очищая стек и устанавливаяC
указатель функции замыкания. Предыдущие значенияS
,E
и следующее значениеC
сохраняются на свалке.ret
извлекает одно возвращаемое значение из стека, восстанавливаетS
,E
иC
из дампа, и помещает возвращаемое значение в текущий стек.dum
помещает «пустышку», пустой список, перед списком окружения.rap
работает как , только заменяет вхождение фиктивного окружения текущим, что делает возможными рекурсивные функции
Существует ряд дополнительных инструкций для основных функций, таких как car, cdr, построение списка, сложение целых чисел, ввод-вывод и т. Д. Все они берут из стека необходимые параметры.
См. Также [ править ]
Ссылки [ править ]
- Перейти ↑ Landin, PJ (январь 1964). «Механическая оценка выражений» . Comput. J. 6 (4): 308–320. DOI : 10.1093 / comjnl / 6.4.308 .
- ^ Доступнастатья о дизайне SECD: DESIGN ISSUES .
- ^ a b Д. А. Тернер «Некоторая история языков функционального программирования» в приглашенной лекции TFP12 , Университет Сент-Эндрюс, 12 июня 2012 г. См. раздел, посвященный Algol 60
Дальнейшее чтение [ править ]
- Данви, Оливье . Рациональная деконструкция машины SECD Ландина . Отчет об исследовании БРИКС RS-04-30, 2004. ISSN 0909-0878.
- Филд, Энтони Дж. Филд и Питер Г. Харрисон. 1988 Функциональное программирование . Эддисон-Уэсли. ISBN 0-201-19249-7
- Грэм, Брайан Т. 1992 "Микропроцессор SECD: пример проверки". Springer. ISBN 0-7923-9245-0
- Хендерсон, Питер. 1980 Функциональное программирование: применение и реализация . Прентис Холл. ISBN 0-13-331579-7
- Когге, Питер М. Архитектура символических компьютеров . ISBN 0-07-035596-7
- Ландин, П.Дж. (март 1966 г.). «Следующие 700 языков программирования» (PDF) . Comm. ACM . 9 (3): 157–166. DOI : 10.1145 / 365230.365257 .
Внешние ссылки [ править ]
- Коллекция SECD