Функциональное программирование

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

Контекст проще всего представить в виде двух списков: `n` – список имен и `v` – список значений. Например, пусть `n`=((X Y Z) (A X F)) и `v`=((1 (A B) –127) (C 3 ((lambda (X) (+ X 1)) . …))), тогда контекст имеет вид `{X\ ->\ 1,\ Y\ ->\ (A\ B),\ Z\ ->\ –127,\ A\ ->\ C,\ F\ ->\ [(lambda\ (X)\ (+\ X\ 1)),\ …]}`. Список `n` состоит из нескольких подсписков, которые являются наборами связей, добавляемых на разных этапах вычислений. В этом примере связь `X\ ->\ 3` временно вытеснена связью `X\ ->\ 1`. Функциональное замыкание будем представлять в виде S-выражения `(lambda\ .\ (n\ .\ v))`, где `lambda` – `lambda`-выражение, а `n` и `v` – состояние контекста в момент определения функции (значения свободных переменных также содержатся в этом контексте).

Для доступа к контексту используется функция `"ассоц"(x,n,v)`, которая по имени `x` из списка имен `n` выдает соответствующее значение из списка значений `v`. Если имени в списке `n` нет, то результат не определен.

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

Основной функцией программы является функция `"вычислить"(e,n,v)`, которая вычисляет S-выражение `e` в контексте `n` и `v`.

При выполнении рекурсивного блока (letrec `((x_1\ e_1)\ …\ (x_k\ e_k))\ e)` для создания контекста используется псевдофункция `"set"_"car"(x,y)`, которая разрушает уже существующую структуру данных, что запрещено в функциональном программировании. Действие этой функции заключается в замене первого элемента списка `x` на `y`. В языке Scheme эта функция имеет имя set–car!. С ее помощью можно построить циклические структуры, что и требуется для интерпретации рекурсивного блока. В принципе можно определить вычисление блока letrec без использования разрушающей псевдофункции, но для этого потребуется ленивая семантика языка. При вычислении значений выражений `e_1,\ …,\ e_k` значения для `x_1,\ …,\ x_k` еще недоступны, поэтому выражения `e_1,\ …,\ e_k` не должны требовать немедленного доступа к `x_1,\ …,\ x_k`, то есть должны быть функциями.

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

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

Таблица 2

Назначение регистров SECD-машины

Для ускорения доступа к значениям переменных вместо последовательного поиска в контексте используются индексные пары `(i\ .\ j)`, где `i` – номер списка, а `j` – номер элемента в списке. Определение индекса значения происходит во время компиляции.

Программа (cons (+ x 1) (cdr y)) может быть преобразована компилятором в следующий код: ((LOAD 0 . 0) (QUOTE . 1) + (LOAD 0 . 1) CDR CONS). Выполнение команд SECD-машины легко описать с помощью таблицы 3.

Таблица 3

Кроме S-выражений, функциональную программу можно представить также в виде графа (рис. 4), для обработки которого используется G-машина, и потокового графа (рис. 5), для обработки которого используется потоковая машина.

В функциональном языке программист не заботится явно о размещении новых объектов в памяти и удалении их после того, как объект перестанет быть необходимым. Поэтому очень важной является сборка мусора, которая запускается каждый раз при нехватке памяти для дальнейшей работы функциональной программы. Для SECD-машины сборка мусора состоит в том, что все ячейки памяти, к которым нет прямых или косвенных ссылок из регистров, переводятся в список свободных ячеек памяти. Основные классы сборщиков мусора описаны в главе 16 книги Филд А., Харрисон П. "Функциональное программирование".