SECD - виртуальная функциональная машина

Статья в Википедии
Реализация для Windows, с текстами (Delphi)
Реализация для Linux, с текстами (Kylix)

Деревья и их запись

Рассмотрим бинарные деревья, состоящие из узлов и листьев. Каждый узел имеет два подчиненных дерева: правое и левое. Листья содержат слова, состоящие из букв и символа подчеркивания. Например:

У некоторых узлов листья могут отсутствовать. Будем обозначать их специальным значением NIL.

Для записи дерева “в строку” будем использовать такой способ:

( левое_поддерево . правое_поддерево )

Дерево из предыдущего примера будет выглядеть так:

( мама . ( мыла . раму ) )

Для сокращения записи длинных деревьев “с правым уклоном” будем применять следующие правила:

( x . ( y ) ) == ( x y )
( x . NIL ) == ( x )

Тогда дерево из предыдущего примера можно переписать так:

( мама мыла . раму )

Регистры машины

Наша вычислительная машина будет оперировать деревьями. Обрабатываемые деревья хранятся в пяти регистрах с именами “стек”, “аргументы”, “команды”, “история” и “словарь”.

Стек предназначен для обрабатываемых данных. Большинство команд так или иначе преобразуют содержимое стека. Левое поддерево стека будем называть верхним, или первым элементом.

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

Регистр аргументов содержит значения аргументов текущей выполняемой функции. Их значения доступны посредством команды _arg.

Регистр истории заполняется при вызове функции и хранит необходимые данные для возврата к вызывающей функции. Команда _if также выполняется аналогично вызову функции и использует регистр истории.

Регистр словаря содержит информацию обо всех функциях, определенных командой _define и доступных для вызова командой _call.

Выполнение

Если в качестве команды выступает слово, начинающееся с символа подчеркивания, оно выполняется по специальному алгоритму. Иначе команда заносится в регистр стека в качестве левого поддерева:

Стек	Аргументы	Команды	История		Стек	Аргументы	Команды	История
				⇒

Это также можно отобразить в следующем виде:

s		( x . s )
e	⇒	e
( x . c )		c
h		h

Возврат

Если регистр команд оказался пустым, это означает, что выполнение текущей функции закончено, и следует вернуться к вызывающей функции. Если регистр истории непустой, производится следующее действие:

( x . os )		( x . s )
oe	⇒	e
NIL		c
( s e c . h )		h

Если же и регистр команд, и регистр истории пусты, машина завершает работу, и результатом выполнения программы считается значение на вершине стека.

Стек	Аргументы	Команды	История		Стек	Аргументы	Команды	История
				⇒

Специальные команды

_head – выделение левого поддерева

Команда _head извлекает из стека верхний элемент и заменяет его на левое поддерево этого элемента.

( ( a . b ) s )		( a . s )
e	⇒	e
( _head . c )		c
h		h

Стек	Команды		Стек	Команды
		⇒

_tail – выделение правого поддерева

Команда _head извлекает из стека верхний элемент и заменяет его на правое поддерево этого элемента.

( ( a . b ) s )		( b . s )
e	⇒	e
( _tail . c )		c
h		h

Стек	Команды		Стек	Команды
		⇒

_cons – создание дерева

Команда _cons извлекает из стека два верхних элемента, объединяет их в дерево и помещает результат в первый элемент стека.

( a b . s )		( ( a . b ) . s )
e	⇒	e
( _cons . c )		c
h		h

Стек	Команды		Стек	Команды
		⇒

_sym – проверка слова

Команда _sym проверяет, является ли верхний элемент стека простым словом. Она замещает верхний элемент словом TRUE в случае простого слова, или FALSE в случае дерева или значения NIL.

( a . s )		( t . s )
e	⇒	e
( _sym . c )		c
h		h

Здесь t равно TRUE или FALSE.

Стек	Команды		Стек	Команды
		⇒

_eq – сравнение деревьев

Команда _cons извлекает из стека два верхних элемента, проверяет их на равенство и помещает результат TRUE или FALSE в первый элемент стека. Два дерева считаются равными, если они “выглядят” одинаково.

( a b . s )		( t . s )
e	⇒	e
( _eq . c )		c
h		h

Здесь t равно TRUE или FALSE.

Стек	Команды		Стек	Команды
		⇒

_if – условный оператор

Команда _if извлекает из стека верхний элемент и выбирает один из потоков команд, в зависимости от истинности значения. Если остаток регистра команд непуст, состояние регистров сохраняется в истории, как при команде _call.

( x . s )		s
e	⇒	e
( _if a b . c )		y
h		( s e c . h )

Здесь y равно a если x равно TRUE, иначе y равно b.

Стек	Команды	История		Стек	Команды	История
			⇒

Если остаток регистра команд `c’ пустой, то команда выполняется более оптимальным образом (конечная рекурсия):

( x . s )		s
e	⇒	e
( _if a b )		y
h		h

Стек	Команды		Стек	Команды
		⇒

_arg – извлечение аргумента функции

Команда _arg помещает на стек копию списка аргументов текущей функции из регистра аргументов. Конкретные аргументы затем можно вычислить комбинацией команд _head и _tail.

s		( e . s )
e	⇒	e
( _arg . c )		c
h		h

Стек	Команды		Стек	Команды
		⇒

_def – определение новой функции

Команда _define извлекает из стека имя и тело новой функции, и добавляет их в начало регистра словаря. При поиске функции словарь просматривается от начала к концу, поэтому новое определение может “затенять” старое определение функции с тем же именем.

( (name . body) . s )		s
e		e
(_def . c)	⇒	c
h		h
v		( (name . body) . v )

Стек	Команды	Словарь		Стек	Команды	Словарь
			⇒

_call – вызов функции

Команда _call:

извлекает из стека имя функции и список аргументов
сохраняет значения регистров стека, аргументов, команд и истории в регистре истории
находит в регистре словаря и помещает в регистр команд тело функции
заносит в регистр аргументов список аргументов функции
опустошает стек

( (name . args) . s )		NIL
e	⇒	args
( _call . с )		body
h		( s e c . h )

Стек	Аргументы	Команды	История		Стек	Аргументы	Команды	История
				⇒