Компиляция функциональных программ в SECD-машину

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

Чтобы проиллюстрировать этот подход, рассмотрим наш простой язык расширенного лямбда-исчисления и опишем процесс компиляции этого языка в последовательность команд SECD-машины, а также опишем процесс исполнения этих команд. Для этого прежде всего опишем процесс преобразования имен переменных в адресные пары.

В каждый момент времени при исполнении функциональной программы имеется контекст переменных, составленный из имен формальных аргументов исполняемых функций и переменных, полученных при их описании в letи letrec-блоках. Например, при вычислении значения выражения.

= 2,.

letrec x.

f = Xy.* x у.

in f 3.

в тот момент, когда вычисляется произведение двух чисел с помощью стандартной функции умножения целых, контекст переменных состоит из аргумента функции у (со значением 3) и двух переменных х и f, определенных в блоке letrec. Этот контекст состоит из двух «уровней» определения переменных — уровня описания переменных в блоке и вложенного в него уровня описания формального аргумента функции. Уровни принято нумеровать целыми числами, начиная от нуля, при этом самый внутренний блок получает номер ноль, а каждый из охватывающих его уровней — номер, на единицу больший него. Внутри каждого уровня переменные также нумеруются числами, начиная с нуля. Таким образом, в любой момент времени каждая переменная будет характеризоваться двумя числами — номером уровня и номером переменной внутри этого уровня. Эти два числа и образуют так называемую адресную пару переменной.

В приведенном выше примере в точке выполнения умножения переменная у имеет адресную пару (0,0), поскольку находится на нулевом уровне и является единственной переменной на этом уровне. Переменная х будет иметь адресную пару (1,0), поскольку это первая переменная на уровне 1, а переменная f будет однозначно характеризоваться своей адресной парой (1,1). Заметим, что адресная пара одной и той же переменной будет разной в зависимости от того места в программе, в котором осуществляется доступ к этой переменной. Так, в момент вызова функции f в том же примере переменная х будет характеризоваться адресной парой (0,0), а переменная у в этот момент вообще недоступна и, следовательно, в адресной паре не нуждается.

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

[[3], [2, f ' ] ].

где через f¹ обозначено замыкание, представляющее лямбда-выражение (Ху.* х у).

Несложно определить функцию, которая по заданной адресной паре (i, j) будет выдавать значение из так организованного контекста: getValue (level, number) context = context !! level ! ! number.

Если SECD-машина будет иметь в регистре контекста указанный выше список, то программа умножения будет выполнена с помощью последовательного исполнения нескольких команд, первые из которых загружают на вершину стека значения переменных х и у, а также операцию умножения (*) в виде сечения, а следующие две команды выполняют собственно умножение. Поскольку обращение к переменным происходит с помощью адресных пар, то выглядеть эти команды будут примерно следующим образом:

Load (0, 0);

Load (1, 0) ;

LoadFunc Apply;

Apply;

загрузка переменной у; загрузка переменной х; загрузка функции умножения;

— применение умножения к первому операнду; применение результата ко второму операнду.

Для того чтобы перевести (скомпилировать) программу на исходном языке расширенного лямбда-исчисления в эту последовательность команд, нужно в момент компиляции знать, каким переменным какие адресные пары будут соответствовать в каждый момент выполнения программы. Поэтому при компиляции необходимо иметь список, в котором хранятся переменные и соответствующие им адресные пары. Проще всего организовать этот список в точности так же, как и список адресных пар, тогда адресная пара будет просто вычисляться по положению переменной в списке. Например, в момент компиляции выражения (* х у) в вышеприведенном примере нужно, чтобы список активных переменных имел структуру [[" у" ], [" X", «f» ]].

Приведем определение функции addr, которая по заданному списку переменных и переменной из этого списка вычисляет адресную пару этой переменной. Заметим, что если мы компилируем корректную программу, то вычисление адресной пары обязательно закончится успешно — соответствующая переменная в списках, составляющих контекст переменных, обязательно найдется:

addr: Eq, а => а -> [[а]] -> (Int, Int).

addr var (varsrrest) = case findlndex (== var) vars of Nothing -> (lev + 1, num).

Just idx -> (0, idx).

where (lev, num) = addr var rest Теперь, когда мы умеем вычислять адресные пары переменных, можно приступить к процессу компиляции программы в последовательность команд нашей SECD-машины низкого уровня. Однако перед тем, как это делать, следует рассмотреть подробнее, как работает эта машина.

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

type Context = [ [WHNF] ].

type Stack = [WHNF] type Environment = Context type Control = [Command].

type Dump = [(Stack, Environment, Control)] type SECD = (Stack, Environment, Control, Dump).

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

Будем использовать составные команды для организации управления. Примерами составных команд могут служить такие команды, как команда выбора из альтернатив Select или команда образования замыкания для функции LoadFunc.

В список команд SECD-машины низкого уровня часто включают и команды для выполнения примитивных функций расширенного лямбдаисчисления, таких как сложение и другие арифметические операции, сравнения, логические операции, команды образования списков CONS и кортежей TUPLE-k и др. Мы не будем этого делать, считая, что примитивные операции, как и раньше, будут исполняться некоторой интерпретирующей системой, представленной функцией intrinsic, получающей в качестве аргументов идентификатор операции и список ее операндов. Для загрузки значений на стек будут также использоваться команды загрузки констант (LoadConst), имеющие в качестве аргумента простое значение загружаемой константы. Конечно, будут также применяться команда загрузки значения из контекста по адресной паре (Load), команда загрузки замыкания для функции (LoadFunc), операндом которой будет список команд, представляющих тело функции, команда загрузки знака примитивной операции (LoadSect). Кроме того, потребуются команды применения функции Apply и еще несколько вспомогательных команд, смысл которых будет разъяснен позже.

Программа, записанная на исходном языке расширенного лямбдаисчисления, сначала переводится (компилируется) в последовательность команд SECD-машины низкого уровня. Далее, если требуется исполнить эту программу, запускается интерпретатор команд SECD-машины. Компиляция исходного текста — это обычная функция, которая получает в качестве аргумента исходную программу и выдает в качестве результата список команд. Интерпретатор команд SECD-машины можно тоже описать в функциональном виде примерно так же, как мы это делали для SECDмашины высокого уровня, однако, как и раньше, такое описание будет недостаточным из-за того, что потребуется выполнять команды, которые невозможно описать в чисто функциональных терминах, так как они включают в себя изменение уже имеющихся значений (присваивание). Как и раньше, для энергичной SECD-машины это касается только вычисления значения рекурсивного блока, а для ленивой машины такое присваивание потребуется еще и для реализации повторных обращений к аргументам функции, вычисление которых было задержано до момента первого обращения к ним.

Мы не будем писать программу на языке Haskell для реализации компилятора и интерпретатора SECD-машины низкого уровня. Вместо этого сделаем следующее. Во-первых, определим типы данных для представления исходных программ, результатов работы (значения в виде СЗНФ) и команд SECD-машины. После этого опишем компиляцию в виде уравнений для функции компиляции comp. Уравнения будем записывать неформально, однако переписать их на языке Haskell большого труда не представляет. Наконец, опишем работу интерпретатора в терминах переходов из одного состояния SECD-машины в другое, имеющих вид (s, е, с, d) -" (s', е', с', d').

где (s_f е, с, d) представляет состояние SECD-машины до выполнения команды, a (s', е', c^f, d^?) — после ее выполнения. Конечно, правила такого перехода в основном зависят от первой из команд, лежащих в регистре управления, и могут быть переписаны в виде уравнений функции evaluate.

Начнем с описания выражений исходного языка программирования. Это описание практически полностью совпадает с описанием типа Ехрг, как оно появилось у нас в первый раз при описании интерпретатора. Добавим только конструкцию для представления пустого списка Nil и снова введем конструкцию для явного представления условного выражения, которое невозможно выразить в виде встроенной функции при чисто энергичных вычислениях. У пас получится следующее описание:

data Ехрг =.

Integral Integer I — целая константа.

Logical Bool I — логическая константа.

Nil I — константа — пустой список.

Function String I — встроенная функция.

Variable String I — переменная.

Lambda String Ехрг | — лямбда-выражение.

Application Expr Expr | — применение функции.

If Expr Expr Expr | — условное выражение.

Let String Expr Expr | — нерекурсивный блок.

Letrec [ (String, Expr)] Expr — рекурсивный блок Выражения в слабой заголовочной нормальной форме будут представлены значениями, которые можно описать в виде следующего описания типа и его конструкторов:

data WHNF =.

Numeric Integer I — целая константа.

Boolean Bool I — логическая константа.

List [WHNF] | — список (в том числе — пустой).

Closure [Command] Context | — замыкание для функции.

Section String Int [WHNF] — встроенная функция или.

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

Теперь опишем набор команд SECD-машины. В большинстве случаев смысл команд понятен интуитивно или ясен из предыдущих абзацев.

Смысл некоторых команд будет понятен при рассмотрении работы SECDмашины:

Command =.

Load (Int, Int).

LoadConst WHNF.

LoadFunc [Command].

LoadSect String.

Select [Command].

Apply.

Return.

LetApply.

Dummy.

RecApply.

Stop.

data

| — загрузка значения по адресной паре.

| — загрузка констант.

| — загрузка замыкания.

I — загрузка встроенной операции [Command] | — выбор альтернативы.

I — применение функции | — возврат из функции.

| — вход в нерекурсивный блок.

| — образование фиктивного контекста.

| — вход в рекурсивный блок.

— остановка работы Работу компилятора мы будем описывать в виде уравнений функции compile, аргументом которой является некоторая конструкция языка — выражение типа Ехрг, а результатом — последовательность команд, полученная компиляцией исходного выражения. Кроме исходного выражения аргументом функции compile является также контекст переменных, так что компиляция выражения всегда производится в некотором контексте переменных. Для упрощения записи будем считать, что функция compile представлена бинарной операцией (**), так что наши уравнения будут иметь вид ехрг ** context = [список команд].

Например, выражение (Integral п) компилируется в команду загрузки целой константы, так что соответствующее уравнение будет выглядеть следующим образом:

(Integral n) ** context = [LoadConst (Numeric n)].

Так же просто описываются уравнения для компиляции еще некоторых простых типов выражения:

• (Logical b) ** context = [LoadConst (Boolean b) ]
• (Nil) ** context = [LoadConst (List [])]
• (Function f) ** context = [LoadSect f]
• (Variable x) ** context = [Load $ addr x context]

Чтобы скомпилировать условное выражение, нужно сначала скомпилировать команды для вычисления условия, а также для вычисления обеих альтернатив условного выражения. После этого команды расставляются таким образом, чтобы сначала было вычислено условие, а потом исполнилась команда Select, которая уже и произведет выбор, какую из двух оставшихся последовательностей команд надо выполнять. Таким образом, соответствующее уравнение будет записано как.

(If cond eThen eElse) ** context = (cond ** context) ++.

[Select (eThen ** context) (eElse ** context)] Разумеется, компиляция всех подвыражений этого выражения производится в одном и том же контексте.

Немного сложнее выглядит команда компиляции лямбда-выражения. Сложность заключается в том, что команды, составляющие тело лямбдавыражения, должны компилироваться не в исходном контексте, а в контексте, в котором добавлен новый уровень переменных, содержащий единственную переменную — формальный аргумент лямбда-выражения. Поскольку контекст представляет собой список уровней, то добавление к нему нового уровня, содержащего переменную х, можно описать с помощью выражения [х]: context. Тогда все уравнение для представления результата компиляции лямбда-выражения можно записать так:

(Lambda х body) ** context.

[LoadFunc ((body ** ([x]: context)) ++ [Return])).

т.е. тело лямбда-выражения компилируется в расширенном контексте, к полученной последовательности команд добавляется еще команда возврата из функции Return, и вся эта скомпилированная последовательность команд является единственным операндом команды LoadFunc.

Компиляция выражения, представляющего собой применение функции к аргументу, выполняется совершенно естественным при энергичных вычислениях способом, а именно: сначала должны выполняться команды вычисления значения аргумента, затем команды, вычисляющие функцию (в простейшем случае это будет единственная команда загрузки функции), и, наконец, должна выполниться команда Apply, которая и применяет вычисленную функцию к вычисленному аргументу. Все это можно записать в виде следующего уравнения:

• (Application func arg) ** context =
• (arg ** context) ++ (func ** context) ++ [Apply] Осталось написать два самых сложных уравнения для компиляции блоков Let и Letrec. Для компиляции блока Let воспользуемся тем, что вычисление этого блока эквивалентно применению функции, у которой тело лямбда-выражения совпадает с телом блока, а аргументом является выражение, содержащееся в заголовке блока.

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

(Let х е body) ** context (е ** context) ++.

[LoadFunc ((body ** ([x]: context)) ++ [Return]), Apply].

При исполнении сгенерированной последовательности команд сначала в стек будет загружено значение, вычисленное выражением е, затем в стек загрузится функция, тело которой образовано телом блока, и, наконец, будет инициировано применение функции командой Apply.

Компиляция рекурсивного блока производится похожим образом. Однако имеются и существенные отличия. Во-первых, компиляция выражений, входящих в заголовок блока, производится в том же контексте, что и компиляция тела блока, поскольку в этих выражениях допустимо обращение к переменным заголовка. Для того чтобы впоследствии вычисления происходили в расширенном контексте, необходимо сформировать этот расширенный контекст еще до начала вычислений. Для этого будем использовать команду SECD-машины Dummy. Действительного обращения к значениям из этого контекста при вычислении выражений из заголовка блока происходить не будет. Напомним, что речь идет об энергичных вычислениях, гак что любое прямое обращение к переменным блока из выражений заголовка блока немедленно привело бы к зацикливанию программы. Обычно переменные содержатся в этих выражениях только внутри тел лямбда-выражений, так что действительно контекст пока можно сформировать фиктивный, не содержащий никаких значений. Вход в рекурсивный блок происходит в ситуации, когда текущим контекстом является фиктивный контекст, сформированный командой Dummy, поэтому при входе нужно заменить часть этого контекста списком вычисленных значений. Это будет делать команда входа в рекурсивный блок — RecApply.

Значения выражений, находящихся в заголовке блока, должны в результате работы SECD-машины попасть в список, поэтому необходимо к командам для вычисления выражений добавить еще и команды формирования такого списка. Начинается построение списка с команды загрузки в стек пустого списка командой LoadConst. Для присоединения к списку новых элементов можно воспользоваться стандартной функцией CONS, так что мы включим в скомпилированный код команды для загрузки и применения этой функции:

• (Letrec [(xl, el),…, (xn, en)] body) ** context [Dummy, LoadConst (List [])] ++
• (en ** ([xlxn]: context)) ++

[LoadSect «CONS», Apply, Apply] ++.

(el ** ([xlxn]: context)) ++.

[LoadSect «CONS», Apply, Apply] ++.

[LoadFunc ((body ** ([xlxn]: context) + + [Return])] ++.

[RecApply].

Программирование компилятора закончено. Заметим: несмотря на то что уравнения для компилятора были даны в неформальном виде, их несложно перевести в чисто функциональную программу. Для полноты изложения приведем эту программу в листинге 12.1 целиком.

Листинг 12.1. Компиляция выражений расширенного лямбда-исчисления import Data. List (findlndex).

— Основной тип данных для представления выражений — расширенного лямбда-исчисления и «команд» SECD-машины data Ехрг =.

Integral Integer I — целая константа.

Logical Bool I — логическая константа.

Nil | — константа — пустой список.

Function String I — встроенная функция.

Variable String I — переменная.

Lambda String Expr | — лямбда-выражение.

Application Expr Expr | — применение функции.

If Expr Expr Expr | — условное выражение.

Let String Expr Expr | — нерекурсивный блок.

Letrec [(String, Expr)] Expr — рекурсивный блок deriving (Show, Eq).

data Command =.

Load (Int, Int) | — загрузка значения по адресной паре.

LoadConst WHNF | — загрузка константы.

LoadFunc [Command] I — загрузка замыкания.

LoadSect String | — загрузка встроенной операции.

Select [Command] [Command] | — выбор альтернативы.

Apply I — применение функции.

Return I — возврат из функции.

LetApply I — вход в нерекурсивный блок.

Dummy | — образование фиктивного контекста.

RecApply | — вход в рекурсивный блок.

Stop — остановка работы.

deriving (Show, Eq).

— «результаты вычислений» data WHNF =.

Numeric Integer I.

Boolean Bool I.

List [WHNF] |.

Closure [Command] Context |.

Section String Int [WHNF].

deriving (Show, Eq).

• — Определения типов основных и вспомогательных функций type Context = [ [String]]
• —— Компилятор:

compile:: Expr -> [Command].

(***): Expr -> Context -> [Command].

comp:: [ [String] ] -> Expr -> [Command] -> [Command].

compile = (*** []).

e *** context = comp context e [Stop].

— Вычисление адресной пары переменной в заданном контексте имен addr: Eq, а => а -> [[а]] -> (Int, Int).

addr var (vars:rest) = case findlndex (== var) vars of Nothing -> (lev+1, num).

Just idx -> (0, idx).

where (lev, num) = addr var rest.

comp env (Integral n) lc = (LoadConst (Numeric n)) :1c.

comp env (Logical b) lc = (LoadConst (Boolean b)) :1c.

comp env Nil lc = (LoadConst (List [])): lc.

comp env (Function f) lc = (LoadSect f): lc.

comp env (Variable x) lc = (Load (addr x env)): lc.

comp env (Lambda var e) lc =.

• (LoadFunc (comp ([var]: env) e [Return])): lc comp env (Application func arg) lc =
• ((comp env arg). (comp env func)) (Apply:lc) comp env (If cond th el) lc = comp env cond
• ((Select (comp env th []) (comp env el [])):lc) comp env (Let x e body) lc = comp env e
• ((LoadFunc (comp ([x]: env) body [Return])): Apply: lc) comp env (Letrec pairs body) lc =

Dummy: (LoadConst (List [])) :

• (foldr (comp' env)
• ((LoadFunc (comp (names:env) body [Return])): RecApplyilc) (reverse values))

where (names, values) = unzip pairs comp' e ex lc =.

comp e ex ((LoadSect «cons»):Apply:Apply:lc).

В этой программе основная работа по компиляции выражения выполняется функцией comp, которая для повышения эффективности имеет дополнительный накапливающий параметр — уже сформированный список команд. Это позволяет полностью избавиться от неэффективного соединения списков команд с помощью операции (++), которую мы активно использовали в нашем неформальном описании компилятора.

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

let twice = Xf.Xx.f (f x) in twice (+ 1) 3.

Представление этого выражения в виде значения типа Ехрг будет выглядеть так: test: Ехрг test = Let «twice» .

• (Lambda «f» (Lambda «x»
• (Application (Variable «f»)
• (Application (Variable «f»)(Variable «x»)))))
• (Application
• (Application (Variable «twice»)
• (Application (Function «+»)(Integral 1))) (Integral 3))

Запустим наш компилятор, задав интерпретатору GIIC выражение compile test. Получим следующий результат (для повышения читабельности в представление результата добавлены переходы со строки на строку):

" compile test [LoadFunc.

[LoadFunc.

[Load (0,0), Load (1,0), Apply, Load (1,0), Apply, Return],.

Return],.

LoadFunc.

[LoadConst (Numeric 3), LoadConst (Numeric 1),.

LoadSect «+», Apply, Load (0,0), Apply, Apply, Return],.

Apply, Stop].

Проверьте, что сгенерированная последовательность команд действительно представляет исполняемый код для преобразования нашего выражения в СЗНФ.

Теперь перейдем к описанию работы SECD-машины низкого уровня. Ее работу мы также будем описывать неформально в терминах последовательного исполнения переходов, изменяющих состояние регистров машины. Каждый переход происходит под воздействием одной команды из регистра управления. Последней исполняемой командой будет команда остановки машины — Stop.

Практически всю работу SECD-машины низкого уровня тоже можно описать в виде чисто функциональной программы. Исключение составляет команда RecApply, которая производит присваивание в контексте — подмену фиктивного пустого списка значений на вычисленный список. Здесь снова существенно, что происходит именно замена значения, а не формирование нового списка, как это происходит в функциональных программах, поскольку этот фиктивный контекст уже мог быть запомнен в замыканиях для лямбда-выражений, встречающихся в заголовке блока. Замена значения должна привести к тому, что все ссылки на этот контекст будут теперь указывать на измененное значение. Фактически исполнение команды RecApply приведет к образованию циклического контекста, в котором некоторые элементы содержат ссылку на себя.

Сначала опишем, как исполняются простые команды, загружающие в стек результатов те или иные значения:

• (s, ctx, (LoadConst val):c, d) -" (val:s, ctx, c, d)
• (s, ctx, (Load addr):c, d) -" ((getValue addr ctx):s, ctx, c, d)
• (s, ctx, (LoadFunc corns) :c, d) —> ((Closure corns ctx): s, ctx, c, d)
• (s, ctx, (LoadSect f) :c, d) —" ((Section f (arity f)

[]): s, ctx, c, d).

Все эти переходы совершенно понятны — значение из команды или контекста просто переносится на стек результатов, возможно, несколько видоизменяясь. Так, при исполнении команды LoadFunc загрузки функции в стек помещается замыкание, образованное из команд, реализующих работу этой функции, и текущего контекста. При исполнении команды загрузки встроенной функции LoadSect формируется пустой список аргументов, и с помощью функции arity вычисляется количество требуемых аргументов для того, чтобы функция могла выполниться. Напомним, что функция getValue выбирает значение из двухуровневого списка значений по заданной адресной паре.

Команда Select тоже работает достаточно просто, однако результат ее работы зависит от значения, находящегося на вершине стека. Исполнение данной команды мы опишем с помощью двух переходов, соответствующих двум возможным значениям, которые будут находиться на вершине стека в момент ее исполнения:

((Boolean True) :s, ctx, (Select th el):c, d) -> (s, ctx, th ++ c, d) ((Boolean False) :s, ctx, (Select th el):c, d) —> (s, ctx, el ++ c, d).

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

• ((Closure corns env):arg:s, ctx, Apply: c, d) ->
• ([], [arg] :env, corns, (s, ctx, c) :d)

Работа команды Apply в ситуации, когда исполняемая функция представлена сечением, зависит от того, является ли аргумент функции последним требуемым аргументом. Если да, то результат вычисляется с помощью функции intrinsic, которая, как и раньше, выполняет действия по исполнению встроенной функции. Если нет, то очередной аргумент просто добавляется в список аргументов сечения. Таким образом, работа этой команды может быть описана с помощью следующих двух правил перехода (во втором из этих правил подразумевается, что значение п больше единицы):

• ((Section f 1 list):arg:s, ctx, Apply: c, d) -«
• ((intrinsic f (list ++ [arg])):s, ctx, c, d) ((Section f n list):arg:s, ctx, Apply: c, d) —>
• ((Section f (n-1) (list ++ [arg])):s, ctx, c, d) Команда выхода из функции просто восстанавливает сохраненное ранее состояние SECD-машины, перенося в стек вычисленное функцией значение:
• (val:s', ctx', Return: c', (s, ctx, c) :d) —> (val:s, ctx, c, d) Самой сложной является команда входа в рекурсивный блок. При вычислении рекурсивного блока, прежде всего, с помощью команды Dummy образуется фиктивный контекст. Он должен быть сохранен в отдельной области памяти, а в SECD-машине будет представлен «прозрачной» ссылкой на этот контекст. В нашем описании работы SECD-машины мы будем представлять эту ситуацию в виде «помеченного» значения link#context. При исполнении команды RecApply этот контекст является текущим, но он же мог быть сохранен во всех замыканиях, образованных при вычислении заголовка блока. Поэтому команда RecApply, работая с сохраненным в отдельной области памяти контекстом, фактически подменяет сразу во всех экземплярах этого контекста первый элемент на список вычисленных значений. Будем считать, что это проделывает специальная функция replace, так что в результате вызова (replace args link# ([] :ctx)) не просто образуется новый контекст link# (args: ctx), но фактически то же значение получают и все ранее сохраненные экземпляры этого контекста, имеющие ту же самую метку:
• (s, ctx, Dummy: c, d) —> (s, link# ([]: ctx), c, d)
• ((Closure commands link#([]: ctx)):(List args):s,

link#([]: ctx), RecApply: c, d) —> ([], (replace args link#([]: ctx)), commands, (s, ctx, c) :d).

Для полноты изложения осталось привести только правило для исполнения команды остановки Stop. Формально его можно записать следующим образом:

(s, ctx, Stop: c, d) —> (s, ctx, c, d).

Фактически состояние SECD-машины не меняется, и она просто останавливает свою работу.

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