SECD-машина — абстрактная машина , интерпретатор выражений λ-исчисления . Использует четыре стека: S ( англ. stack ) — стек объектов для вычисления рекурсивных выражений, E ( англ. environment ) — контекст (отображение идентификаторов в объекты), C ( англ. control list ) — управляющая строка (список управления), D ( англ. dump ) — дамп, хранилище предыдущих состояний, используемое для возврата из вызова функций.

Интерпретатор предложен в 1964 году (англ.) ( в статье «The Mechanical Evaluation of Expressions» (механическое вычисление выражений) . SECD-машина легла в основу многих практических реализаций функциональных языков программирования (как энергичных , так и ленивых вычислений ), хотя и требует оптимизации.

Неформальное описание

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

В самом начале контекст E, стек S и дамп D пусты, а подлежащее вычислению выражение загружается как единственный элемент C, который преобразуется в обратную польскую нотацию в процессе вычислений. Единственной используемой при этом операцией является аппликация , обозначаемая символом ap (от англ. apply — применить). Например, выражение f (g x) (единственный элемент списка) заменяется списком [x, g, ap, F, ap].

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

Если элементом С является ap (аппликация), из стека извлекаются два значения, и первое применяется ко второму. Если результатом аппликации является значение, оно помещается в стек S.

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

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

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

См. также

• (англ.) (

Примечания

Литература

• Филд А., Харрисон П. Функциональное программирование = Functional Programming. — М. : Мир, 1993. — С. 228—253. — 637 с. — ISBN 5-03-001870-0 .
• Хендерсон П. Функциональное программирование. Применение и реализация = Functional Programming. — М. : Мир, 1983. — С. 166—177. — 349 с.

Ссылки

• Georgi Georgiev (Skeleta). (англ.) . Дата обращения: 24 января 2021. 27 сентября 2007 года.