5.4. Аппаратное
обеспечение функциональных программ

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

Можно было бы начать с
вопроса о том, почему не могут быть обращены правила преобразования, изложенные
в разд. 5.3. Это происходит потому, что функциональные программы,
которые по этим правилам могут быть выведены из императивных, имеют очень
специальную форму. Если рассматривать процесс преобразования блок-схемы, где
разрывается каждый цикл и вводится новое имя функции, то множество полученных
функциональных определений обладает тем свойством, что каждый вызов
определенной функции является самым внешним. Говорят, что вызов функции f является самым внешним в
выражении, если это выражение имеет вид f(ely e2l. . ., ek) или является условным
выражением если е то е' иначе е\ где вызов f является самым внешним в е' или в е", т. е. в
одной из ветвей условия. Функциональная программа, состоящая из множества
определений функций, в которой все вызовы определяемых функций являются самыми
внешними, называется итеративной и имеет итеративную
форму.
Такие функциональные программы могут быть преобразованы в императивные просто
применением обращенных правил разд. 5.3.