190
newCtx = ("x1", e1'):("x2":e2'):...:("xn", en'):ctx
Таким образом, функция makepairs должна преобразовать
аргументы ["x1", "x2",... "xn"] и (e1':e2':...:en':tail) в
необходимые списки [("x1", e1'), ("x2":e2'),...
("xn", en')] и остаток второго аргумента tail. Тогда
соответствующее уравнение будет действительно работать так, как
описано. Уравнения для функции makepairs можно теперь описать
следующим образом:
makepairs [] s = ([], s)
makepairs (x:names) (e:exprs) = ((x, e):head, tail)
where (head, tail) = makepairs names exprs
Итак, мы описали поведение SECD-машины практически для всех
команд, кроме рекурсивного блока Letrec. К сожалению, для
рекурсивного блока поведение SECD-машины описать в терминах
функционального программирования не удается без использования
специальных функций, нарушающих основные принципы
функционального программирования. Дело в том, что, несмотря на
внешнюю схожесть нерекурсивного и рекурсивного блоков, их реализация
имеет
одно существенное отличие: контекст для вычисления выражений
e1, e2,... en должен быть тем же самым, что и новый, пополненный
контекст, используемый для вычисления тела блока e. Есть, правда, одна
существенная разница: при энергичной схеме вычислений контекст при
вычислении выражений e1, e2,... en впрямую не используется (то есть,
значения переменных x1,
x2,... xn не выбираются при вычислениях), так
что первоначально, до начала вычисления тела блока можно в этом
контексте связать с переменными x1, x2,... xn произвольные значения.
Однако, после того, как значения выражений e1', e2',... en' будут
вычислены, их надо «вставить» в уже сформированный контекст вместо
начальных значений, то есть совершить что
-то вроде разрушающего
присваивания. Если допустить, что такая функция, выполняющая
присваивание, есть, то исполнение рекурсивного блока можно будет
описать с помощью следующих уравнений.
evaluate (s, e, (Letrec pairs body):c, d) =
evaluate (s, (map (\(x,y) -> (x,(Numeric 0))) pairs) <++> e,
(reverse values) ++ ((LetrecApply names body):c), d)
where (names, values) = unzip pairs
evaluate (s, e, (LetrecApply names body):c, d) =
evaluate ([], newCtx, [body],
(tail, (drop (length names) e), c):d)
where (newCtx, tail) = replaceAll names s e
Здесь в первом уравнении контекст модифицируется для вычисления
значений выражений e1, e2,... en. Для этого берутся все имена x1, x2,...
xn из заголовка блока и связываются с произвольно выбранным значением