Императивная программа как функция

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

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

type Environment = [ (String, Expression)].

то начальное состояние среды при запуске программы вычисления факториала числа 5 может быть представлено в виде env_initial = [(«f», (Const 0)), («n», (Const 5))].

(предполагается, что начальное значение переменных, которые не задаются как исходные данные, в нашем примере — значение переменной f, равно нулю). После исполнения программы значение переменной п уменьшится до нуля, а значением переменной f окажется вычисленное значение факториала — 120. Таким образом, конечное состояние среды можно будет описать так:

env-final = [ («f», (Const 120)), (V, (Const 0))].

Исполнение программы может быть задано функцией, преобразующей начальное состояние среды env-initial в конечное состояние — envfinal. Таким образом, наша задача состоит в том, чтобы по заданной программе (выражению типа Statement) построить функцию, аргументом и результатом которой служит среда (выражение типа Environment). Мы, однако, начнем с более простой программы-интерпретатора, которая будет имитировать последовательное исполнение операторов программы. Такой интерпретатор получает в качестве аргументов программу и начальное состояние среды, а в результате работы выдает конечное состояние среды. Тип функции-интерпретатора можно задать с помощью следующего описания типа на языке Haskell:

interpret:: Statement -> Environment -> Environment.

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

evaluate:: Expression -> Environment -> Expression.

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

assoc:: String -> Environment -> Expression.

Определения функций assoc и evaluate следуют ниже:

assoc х ((у, е) :tail) | х == у = е.

| otherwise = assoc х tail evaluate (Variable x) env = assoc x env.

evaluate e@(Const n) _ = e.

evaluate (Unary op expr) env.

intrinsic op [evaluate expr env] evaluate (Binary el op e2) env =.

intrinsic op [evaluate el env, evaluate e2 env].

В приведенном определении предполагается, что функция intrinsic выполняет встроенные функции, заданные в унарной или бинарной операции, над константами. Например, если считать, что встроенными являются арифметические бинарные операции и % (последние две операции представляют целочисленное деление и операцию получения остатка от целочисленного деления), а также унарная операция арифметического отрицания neg, то уравнения, определяющие результат выполнения арифметических операций, будут выглядеть следующим образом: intrinsic «+» [ (Const а), (Const b) ] = Const (a + b).

intrinsic [ (Const a), (Const b) ] = Const (a — b).

intrinsic «*» [(Const a), (Const b) ] = Const (a * b).

intrinsic «/» [(Const a), (Const b) ] = Const (a 'div' b).

intrinsic «%» [(Const a), (Const b) ] = Const (a 'mod' b).

intrinsic «neg» [ (Const a) ] = Const (0 — a).

Поскольку требуется определить еще и операции с логическим результатом, то можно точно так же добавить несколько уравнений, определяющих результат применения функций сравнения и логических операций к константам:

intrinsic «>» [(Const а), (Const b) ] =.

Const (if a > b then 1 else 0) intrinsic «<» [(Const a), (Const b) ] =.

Const (if a < b then 1 else 0) intrinsic «==» [(Const a), (Const b) ] =.

Const (if a == b then 1 else 0) intrinsic «&&» [(Const a), (Const b) ] =.

Const (if a + b == 2 then 1 else 0) intrinsic «II» [(Const a), (Const b) ] =.

Const (if a + b >= 1 then 1 else 0) Разумеется, аналогичным образом можно определить и другие операции.

Теперь уже можно выписать и определяющие уравнения основной функции interpret. Эта функция просто следует правилам исполнения программы, заданным неформально для каждого из возможных типов операторов программы:

interpret Skip env = env interpret (Assignment x e) env =.

replace x (evaluate e env) env.

interpret (Sequence list) env = foldl (flip interpret) env list interpret (Select cond si s2) env = interpret selection env where selection = case evaluate cond env of.

Const 1 -> si Const 0 -> s2.

interpret oper@(Loop cond s) env = case (evaluate cond env) of Const 0 -> env.

Const 1 -> interpret oper (interpret s env).

Эти уравнения необходимо объяснить. Первое уравнение, впрочем, очевидно — оно отражает тот факт, что выполнение пустого оператора не изменяет среду. Второе уравнение использует функцию replace, которая заменяет в заданной среде значение одной переменной на заданное значение. Точнее, функция должна построить новую среду, отличающуюся от исходной значением только одной переменной. Вот как может выглядеть определение этой функции:

replace:: String -> Expression -> Environment -> Environment replace x v env = (x, v): filter ((/=x).fst) env.

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

Четвертое уравнение предписывает для исполнения условного оператора сначала вычислить значение условия и в зависимости от результата выбрать для последующей интерпретации первый или второй из внутренних операторов.

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

На несложном примере можно проверить, что наш интерпретатор действительно работает. Если вызвать функцию interpret с параметрами, задающими нашу исходную программу вычисления факториала и с начальной средой env_initial, то результатом вычисления будет новая среда env_final = [ («f», (Const 120)), («n», (Const 0))].

В данном случае, правда, важно не столько то, что мы можем с помощью функции interpret получать результаты исполнения программы, сколько то, что мы можем с ее помощью по любой программе получать эквивалентную этой программе функцию. Действительно, если задать для функции interpret только один аргумент — исходную программу, то по свойству карринга в результате получится функция типа Environment -> Environment, т. е. функция преобразования контекста из начального состояния в конечное. Это как раз и есть искомая функция, эквивалентная исходной программе.

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

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