Cтраница 2
Материал первой части этой книги позволяет читателю понять концепции функционального языка и дает представление о математических основах этих концепций. Описаны некоторые свойства, необходимые для системы, вычисляющей функциональные выражения, например сохранение прозрачности ссылок и корректная реализация порядка вычислений, выбранного для данного языка. В предыдущей главе мы рассмотрели интерпретацию функциональных языков и описали интерпретаторы, которые сами написаны на функциональном языке. Это позволяет понять, как взяться за конструирование и реализацию функционального языка, чтобы обеспечить строгую спецификацию высокого уровня Однако операционные характеристики таких интерпретаторов основываются на возможностях того языка, на котором написан сам интерпретатор, - вспомните обсуждение энергичности или ленивости интерпретатора, написанного на энергичном или ленивом языке. В этой главе мы начинаем обсуждение удобных абстрактных машин для выполнения функциональных языков, использующих модель вычислений, основанных на контексте. [16]
Лэндина использует для вычисления К-вы-ражений четыре стека. Ее работу очень легко описать неформально Строгое описание работы SECD-машины основано на представлении ее состояния в зависимости от содержимого ее четырех стеков и заключается в описании переходов машины из одного состояния в другое. Важность SECD-машины состоит в том, что она лежит в основе многих методов практической реализации. Ясно, однако, что без оптимизации SECD-машина является далеко не самым эффективным средством реализации функционального языка. [17]
Ограничением при использовании F является в этом случае запрет частичного применения F. Если мы применяем F частично, то не имеем механизма, с помощью которого можно ссылаться на результирующую функцию, и не имеем механизма применения такой функции. Тем не менее именно таким путем реализуется применение функций во многих традиционных потоковых машинах. Невозможность поддерживать ( по крайней мере, простым способом) функции высшего порядка делает эти машины очень неудобными для реализации функциональных языков. [18]
С одной стороны, мы исследуем преобразование программ, при котором может быть модифицирована вся структура функциональной программы, а с другой стороны, можно управлять выполнением программы, используя аннотации, порождаемые абстрактной интерпретацией. Однако для имеющих точную математическую семантику функциональных языков и преобразование, и абстрактная интерпретация являются методами, способными обеспечить требуемый семантически корректный тип оптимизации. Что касается терминологии, то существует мнение, что преобразование означает любую семантически корректную оптимизацию, поэтому абстрактную интерпретацию можно было бы рассматривать только как часть инструментального набора преобразований. В то же время любой формальный статический анализ программ, включая преобразование, является абстрактной интерпретацией. Существует множество явных ограничений по производительности в неоптимизированых реализациях функциональных языков, разумеется, для последовательных архитектур фон-неймановского типа. Например, применение многих функций при вычислении обладает линейной зависимостью от размера аргумента ( формальные определения в гл. Мы уже увидели примеры этого в авторекурсии, которую, как показано в гл. Аналогично можно было бы ожидать, что при выполнении применения функции Фибоначчи используется число вызовов функции, зависящее экспоненциально от аргумента, тогда как два последовательно накапливающих счетчика дают тот же результат за линейное время и постоянное пространство в императивном цикле. Вопрос, будет ли это несущественно в специализированной, предположительно параллельной архитектуре, в значительной степени неуместен. С одной стороны, фон-неймановские машины останутся и в ближайшем, и в далеком будущем, а в любом случае параллельные машины - это набор последовательных процессоров, каждый из которых лучше всего используется при выполнении нетривиальных преобразований. [19]
Аналогия между МФП - и SECD-машинами, изложенная в гл. МФП соответствуют управляющему стеку в SECD-машине. Однако в нашем случае программа хранится в виде компилированного кода, а не в виде лямбда-выражений. Стек вызовов служит для запоминания состояния вычислений в точке вызова функции и восстановления этого состояния по завершении работы вызванной функции. В этом плане он играет роль, аналогичную работе дампа в SECD-машине. Стек вычислений в МФП в точности соответствует совокупности стека и контекста в SECD-машине. В ней параметры функций сохраняют свои имена, связи между именами и величинами хранятся в контексте. В МФП, однако, все ссылки на параметры функций при компиляции переходят к номера элементов стека, и поэтому возникает необходимость в списке связей имя - величина. И наконец, куча в МФП является лишь местом хранения структур и замыканий. SECD-машине возможно непосредственное размещение замыканий в S-стеке, то в МФП они хранятся в куче, а в стек помещается лишь указатель на место хранения соответствующего замыкания, что, по существу, то же самое. На самом же деле более близкое сходство можно увидеть при рассмотрении ленивой SECD-машины, в которой задержки рассматриваются как объекты кучи с косвенной адресацией через указатель. В заключение добавим, что, хотя SECD-машина может оказаться довольно неэффективной для практических целей, ее значимость заключается в том, что она хорошо описывает общую схему реализации функциональных языков, которая может быть осуществлена различными путями. МФП является лишь одной из возможных реализаций, основанных на SECD-машине. [20]