Войти
Машина SECD имеет большое влияние (см.: # Вклад Ландина) виртуальная машина и абстрактная машина, предназначенная для компиляторов функционального языка программирования. Буквы обозначают S tack, E nvironment, C ontrol, D ump - внутренние регистры машины. Регистры Stack, Control и Dump указывают на (некоторые реализации) stacks, а Environment указывают на (некоторую реализацию) ассоциативный массив .
. Машина была первой, которая была специально разработана для вычисления выражений лямбда-исчисления. Первоначально он был описан Питером Дж. Ландином в «Механической оценке выражений» в 1964 году. Описание, опубликованное Ландином, было довольно абстрактным и оставляло множество вариантов реализации открытыми (например, операционная семантика ). Следовательно, машина SECD часто представлена в более подробной форме, такой как компилятор Lispkit Lisp, который распространяется с 1980 года. С тех пор он использовался как цель для нескольких других экспериментальных компиляторов.
В 1989 году исследователи из Университета Калгари работали над аппаратной реализацией машины.
D. А. Тернер (2012) указывает, что в «Пересмотренном отчете по Алголу 60» (Naur, 1963) указывается вызов процедуры с помощью правила копирования, которое позволяет избежать захвата переменных с систематической сменой идентификаторов. Этот метод работает в реализации Algol 60, но в функциональном языке программирования, где функции являются первоклассными гражданами, свободная переменная в стеке вызовов может быть разыменована по ошибке.
Тернер отмечает, что Ландин решил эту проблему с помощью своей машины SECD, в которой функция представлена в куче закрытием .
Когда начинается оценка выражения, выражение загружается как единственный элемент управления C. Окружение E, стек Sи дамп Dначинаются пустыми.
Во время оценки Cон преобразуется в обратную польскую нотацию (RPN), где ap(для apply ) является единственным оператором. Например, выражение F (GX)(один элемент списка) заменяется на список 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 [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помещает указатель 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, построение списка, сложение целых чисел, ввод / вывод и т. д. Все они берут из стека необходимые параметры.
