SECD-машина

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

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

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

В любой момент 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.

См. также

• Машина Кривина^[англ.]

Примечания

1. Landin, P. J. (January 1964). "The Mechanical Evaluation of Expressions". Comput. J. 6 (4): 308–320. doi:10.1093/comjnl/6.4.308.
2. Филд, Харрисон, 1993.

Литература

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

Ссылки

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