====== SECD - виртуальная функциональная машина ====== * [[http://en.wikipedia.org/wiki/SECD_machine | Статья]] в Википедии * {{secd:secd-delphi.zip | Реализация для Windows}}, с текстами (Delphi) * {{secd:secd-kylix.tgz | Реализация для Linux}}, с текстами (Kylix) ===== Деревья и их запись ===== Рассмотрим бинарные деревья, состоящие из узлов и листьев. Каждый узел имеет два подчиненных дерева: правое и левое. Листья содержат слова, состоящие из букв и символа подчеркивания. Например: {{secd:images:image001.gif}} У некоторых узлов листья могут отсутствовать. Будем обозначать их специальным значением NIL. Для записи дерева “в строку” будем использовать такой способ: ( левое_поддерево . правое_поддерево ) Дерево из предыдущего примера будет выглядеть так: ( мама . ( мыла . раму ) ) Для сокращения записи длинных деревьев “с правым уклоном” будем применять следующие правила: - ( x . ( y ) ) == ( x y ) - ( x . NIL ) == ( x ) Тогда дерево из предыдущего примера можно переписать так: ( мама мыла . раму ) ---- ===== Регистры машины ===== Наша вычислительная машина будет оперировать деревьями. Обрабатываемые деревья хранятся в пяти регистрах с именами “стек”, “аргументы”, “команды”, “история” и “словарь”. Стек предназначен для обрабатываемых данных. Большинство команд так или иначе преобразуют содержимое стека. Левое поддерево стека будем называть верхним, или первым элементом. В регистре команд находится список команд, которые надо выполнить. Машина циклически извлекает первую команду из списка и выполняет ее, т.е. преобразует содержимое всех регистров в соответствии со смыслом команды. Регистр аргументов содержит значения аргументов текущей выполняемой функции. Их значения доступны посредством команды _arg. Регистр истории заполняется при вызове функции и хранит необходимые данные для возврата к вызывающей функции. Команда _if также выполняется аналогично вызову функции и использует регистр истории. Регистр словаря содержит информацию обо всех функциях, определенных командой _define и доступных для вызова командой _call. ---- ===== Выполнение ===== Если в качестве команды выступает слово, начинающееся с символа подчеркивания, оно выполняется по специальному алгоритму. Иначе команда заносится в регистр стека в качестве левого поддерева: ^ Стек ^ Аргументы ^ Команды ^ История | %% %% ^ Стек ^ Аргументы ^ Команды ^ История ^ | {{secd:images:image002.gif}} | {{secd:images:image003.gif}} | {{secd:images:image004.gif}} | {{secd:images:image005.gif}} | => | {{secd:images:image019.gif}} | {{secd:images/image003.gif}} | {{secd:images:image013.gif}} | {{secd:images:image014.gif}} | Это также можно отобразить в следующем виде: | s | | ( x . s ) | | e | => | e | | ( x . c ) | | c | | h | | h | ---- ===== Возврат ===== Если регистр команд оказался пустым, это означает, что выполнение текущей функции закончено, и следует вернуться к вызывающей функции. Если регистр истории непустой, производится следующее действие: | ( x . os ) | | ( x . s ) | | oe | => | e | | NIL | | c | | ( s e c . h ) | | h | Если же и регистр команд, и регистр истории пусты, машина завершает работу, и результатом выполнения программы считается значение на вершине стека. ^ Стек ^ Аргументы ^ Команды ^ История | %% %% ^ Стек ^ Аргументы ^ Команды ^ История ^ | {{secd:images/image015.gif}} | {{secd:images/image016.gif}} | {{secd:images/image017.gif}} | {{secd:images/image018.gif}} | => | {{secd:images/image019.gif}} | {{secd:images/image003.gif}} | {{secd:images/image022.gif}} | {{secd:images/image023.gif}} | ---- ====== Специальные команды ====== ===== _head – выделение левого поддерева ===== Команда _head извлекает из стека верхний элемент и заменяет его на левое поддерево этого элемента. | ( ( a . b ) s ) | | ( a . s ) | | e | => | e | | ( _head . c ) | | c | | h | | h | ^ Стек ^ Команды | %% %% ^ Стек ^ Команды ^ | {{secd:images/image025.gif}} | {{secd:images/image024.gif}} | => | {{secd:images/image026.gif}} | {{secd:images/image013.gif}} | ---- ===== _tail – выделение правого поддерева ===== Команда _head извлекает из стека верхний элемент и заменяет его на правое поддерево этого элемента. | ( ( a . b ) s ) | | ( b . s ) | | e | => | e | | ( _tail . c ) | | c | | h | | h | ^ Стек ^ Команды | %% %% ^ Стек ^ Команды ^ | {{secd:images/image028.gif}} | {{secd:images/image027.gif}} | => | {{secd:images/image029.gif}} | {{secd:images/image022.gif}} | ---- ===== _cons – создание дерева ===== Команда _cons извлекает из стека два верхних элемента, объединяет их в дерево и помещает результат в первый элемент стека. | ( a b . s ) | | ( ( a . b ) . s ) | | e | => | e | | ( _cons . c ) | | c | | h | | h | ^ Стек ^ Команды | %% %% ^ Стек ^ Команды ^ | {{secd:images/image030.gif}} | {{secd:images/image031.gif}}{{secd:images/image032.gif}} | => | {{secd:images/image036.gif}} | {{secd:images/image022.gif}} | ---- ===== _sym – проверка слова ===== Команда _sym проверяет, является ли верхний элемент стека простым словом. Она замещает верхний элемент словом TRUE в случае простого слова, или FALSE в случае дерева или значения NIL. | ( a . s ) | | ( t . s ) | | e | => | e | | ( _sym . c ) | | c | | h | | h | Здесь t равно TRUE или FALSE. ^ Стек ^ Команды | %% %% ^ Стек ^ Команды ^ | {{secd:images/image038.gif}} | {{secd:images/image037.gif}} | => | {{secd:images/image039.gif}} | {{secd:images/image022.gif}} | ---- ===== _eq – сравнение деревьев ===== Команда _cons извлекает из стека два верхних элемента, проверяет их на равенство и помещает результат TRUE или FALSE в первый элемент стека. Два дерева считаются равными, если они “выглядят” одинаково. | ( a b . s ) | | ( t . s ) | | e | => | e | | ( _eq . c ) | | c | | h | | h | Здесь t равно TRUE или FALSE. ^ Стек ^ Команды | %% %% ^ Стек ^ Команды ^ | {{secd:images/image040.gif}} | {{secd:images/image041.gif}} | => | {{secd:images/image039.gif}} | {{secd:images/image022.gif}} | ---- ===== _if – условный оператор ===== Команда _if извлекает из стека верхний элемент и выбирает один из потоков команд, в зависимости от истинности значения. Если остаток регистра команд непуст, состояние регистров сохраняется в истории, как при команде _call. | ( x . s ) | | s | | e | => | e | | ( _if a b . c ) | | y | | h | | ( s e c . h ) | Здесь y равно a если x равно TRUE, иначе y равно b. ^ Стек ^ Команды ^ История | %% %% ^ Стек ^ Команды ^ История ^ | {{secd:images/image042.gif}} | {{secd:images/image043.gif}} | {{secd:images/image044.gif}} | => | {{secd:images/image045.gif}} | {{secd:images/image047.gif}} | {{secd:images/image046.gif}} | Если остаток регистра команд `c’ пустой, то команда выполняется более оптимальным образом (конечная рекурсия): | ( x . s ) | | s | | e | => | e | | ( _if a b ) | | y | | h | | h | ^ Стек ^ Команды | %% %% ^ Стек ^ Команды ^ | {{secd:images/image048.gif}} | {{secd:images/image049.gif}} | => | {{secd:images/image050.gif}} | {{secd:images/image051.gif}} | ---- ===== _arg – извлечение аргумента функции ===== Команда _arg помещает на стек копию списка аргументов текущей функции из регистра аргументов. Конкретные аргументы затем можно вычислить комбинацией команд _head и _tail. | s | | ( e . s ) | | e | => | e | | ( _arg . c ) | | c | | h | | h | ^ Стек ^ Команды | %% %% ^ Стек ^ Команды ^ | {{secd:images/image052.gif}} | {{secd:images/image053.gif}}{{secd:images/image054.gif}} | => | {{secd:images/image058.gif}} | {{secd:images/image059.gif}} | ---- ===== _def – определение новой функции ===== Команда _define извлекает из стека имя и тело новой функции, и добавляет их в начало регистра словаря. При поиске функции словарь просматривается от начала к концу, поэтому новое определение может “затенять” старое определение функции с тем же именем. | ( (name . body) . s ) | | s | | e | | e | | (_def . c) | => | c | | h | | h | | v | | ( (name . body) . v ) | ^ Стек ^ Команды ^ Словарь | %% %% ^ Стек ^ Команды ^ Словарь ^ | {{secd:images/image060.gif}} | {{secd:images/image061.gif}} | {{secd:images/image062.gif}} | => | {{secd:images/image063.gif}} | {{secd:images/image064.gif}} | {{secd:images/image065.gif}} | ---- ===== _call – вызов функции ===== Команда _call: * извлекает из стека имя функции и список аргументов * сохраняет значения регистров стека, аргументов, команд и истории в регистре истории * находит в регистре словаря и помещает в регистр команд тело функции * заносит в регистр аргументов список аргументов функции * опустошает стек | ( (name . args) . s ) | | NIL | | e | => | args | | ( _call . с ) | | body | | h | | ( s e c . h ) | ^ Стек ^ Аргументы ^ Команды ^ История | %% %% ^ Стек ^ Аргументы ^ Команды ^ История ^ | {{secd:images/image066.gif}} | {{secd:images/image067.gif}} | {{secd:images/image068.gif}} | {{secd:images/image069.gif}} | => | {{secd:images/image070.gif}} | {{secd:images/image071.gif}} | {{secd:images/image072.gif}} | {{secd:images/image073.gif}} | Если остаток регистра команд `c’ пустой, то команда выполняется более оптимальным образом (конечная рекурсия): | ( (name . args) . s ) | | s | | e | => | args | | ( _call ) | | body | | h | | h | ^ Стек ^ Аргументы ^ Команды | %% %% ^ Стек ^ Аргументы ^ Команды ^ | {{secd:images/image074.gif}} | {{secd:images/image076.gif}} | {{secd:images/image075.gif}} | => | {{secd:images/image081.gif}} | {{secd:images/image082.gif}} | {{secd:images/image083.gif}} | ---- Copyright (C) 2001-2005 Сергей Вакуленко