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

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

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

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

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

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

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

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

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

  1. ( x . ( y ) ) == ( x y )
  2. ( 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 )

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

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

( (name . args) . s ) s
e args
( _call ) body
h h

Стек Аргументы Команды Стек Аргументы Команды


Copyright (C) 2001-2005 Сергей Вакуленко

 
proj/secd/secd.txt · Последние изменения: 2007/05/19 04:34 vak
 
Copyright (C) 1996-2013 Serge Vakulenko
serge@vak.ru