Машина SECD — это очень влиятельная ( см.: § Вклад Ландина ) виртуальная машина и абстрактная машина, предназначенная в качестве цели для компиляторов функционального языка программирования . Буквы обозначают S tack, Environment , Control , D ump — внутренние регистры машины. Регистры Stack, Control и Dump указывают на (некоторые реализации) стеков , а Environment указывает на (некоторые реализации) ассоциативного массива .
Машина была первой, специально разработанной для оценки выражений лямбда-исчисления . Первоначально она была описана Питером Дж. Ландином в "Механической оценке выражений" [1] в 1964 году. Описание, опубликованное Ландином, было довольно абстрактным и оставляло открытыми многие варианты реализации (например, операционную семантику ).
Lispkit Lisp был влиятельным компилятором, основанным на машине SECD, [2] а машина SECD использовалась в качестве цели для других систем, таких как Lisp/370. [3] В 1989 году исследователи из Университета Калгари работали над аппаратной реализацией машины. [4]
DA Turner (2012) [5] указывает, что язык программирования ALGOL 60 не может возвращать функции из других функций (что делает функции больше не первоклассными). Функция, вложенная в другую функцию, может ссылаться на переменную, находящуюся в стеке внешней функции. Если бы вложенная функция была возвращена из внешней функции, то она ссылалась бы на переменную в стековом фрейме, который больше не присутствует. Turner отмечает, что машина SECD Ландина решает эту проблему (тем самым позволяя функциям возвращать функции), поскольку значение функции теперь представлено замыканием в куче, которое может хранить окружение переменных, которые оно должно использовать независимо от того, что происходит в стеке. [5]
Когда начинается оценка выражения, выражение загружается как единственный элемент управления C. Окружение E, стек Sи дамп Dначинаются пустыми.
Во время оценки Cон преобразуется в обратную польскую нотацию (RPN) с ap(for 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 могут реализовать стек как каноническую структуру стека, тем самым повышая общую эффективность виртуальной машины, при условии, что на размер стека будет наложено строгое ограничение.
Регистр Cуказывает на заголовок кода или списка инструкций, которые будут оценены. После того, как инструкция там выполнена, Cуказывает на следующую инструкцию в списке — он похож на указатель инструкций (или счетчик программ ) в обычных машинах, за исключением того, что последующие инструкции всегда указываются во время выполнения и по умолчанию не содержатся в последующих ячейках памяти, как в случае с обычными машинами.
Текущая переменная среда управляется регистром E, который указывает на список списков. Каждый отдельный список представляет один уровень среды: параметры текущей функции находятся в заголовке списка, переменные, которые свободны в текущей функции, но связаны окружающей функцией, находятся в других элементах E.
Дамп, на голову которого Dуказывает регистр, используется как временное хранилище значений других регистров, например, во время вызовов функций. Его можно сравнить со стеком возвратов других машин.
Организация памяти машины SECD похожа на модель, используемую большинством функциональных языковых интерпретаторов : ряд ячеек памяти, каждая из которых может содержать либо атом ( простое значение, например 13 ), либо представлять пустой или непустой список. В последнем случае ячейка содержит два указателя на другие ячейки, один из которых представляет первый элемент, а другой представляет список, за исключением первого элемента. Два указателя традиционно называются car и cdr соответственно, но вместо них часто используются более современные термины head и tail . Различные типы значений, которые может содержать ячейка, различаются тегом . Часто различаются также различные типы атомов (целые числа, строки и т. д.).
Итак, список, содержащий числа 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помещает значение переменной в стек. Переменная указывается аргументом, парой. Пара car указывает уровень, cdr — позицию. Таким образом, (1 . 3)выдает третий параметр текущей функции (уровень 1).selожидает два аргумента списка и выталкивает значение из стека. Первый список выполняется, если выталкиваемое значение не равно нулю, второй список — в противном случае. Перед тем, как один из этих указателей списка будет сделан новым C, указатель на следующую инструкцию сохраняется в дампе.
joinизвлекает ссылку на список из дампа и делает ее новым значением C. Эта инструкция находится в конце обеих альтернатив sel.ldfпринимает один аргумент списка, представляющий функцию. Он создает замыкание (пару, содержащую функцию и текущую среду) и помещает его в стек.apвыталкивает замыкание и список значений параметров из стека. Замыкание применяется к параметрам путем установки его окружения как текущего, помещения списка параметров перед ним, очистки стека и установки Cуказателя функции замыкания. Предыдущие значения S, Eи следующее значение Cсохраняются в дампе.retизвлекает одно возвращаемое значение из стека, восстанавливает S, Eи Cиз дампа и помещает возвращаемое значение в текущий стек.dumпомещает «фиктивный» пустой список перед списком окружения.rapработает как , только заменяет вхождение фиктивной среды на текущую, тем самым делая возможными рекурсивные функцииСуществует ряд дополнительных инструкций для базовых функций, таких как car, cdr, построение списков, сложение целых чисел, ввод-вывод и т. д. Все они берут необходимые параметры из стека.
{{cite journal}}: Цитировать журнал требует |journal=( помощь )