Cтраница 2
С одной стороны, мы исследуем преобразование программ, при котором может быть модифицирована вся структура функциональной программы, а с другой стороны, можно управлять выполнением программы, используя аннотации, порождаемые абстрактной интерпретацией. Однако для имеющих точную математическую семантику функциональных языков и преобразование, и абстрактная интерпретация являются методами, способными обеспечить требуемый семантически корректный тип оптимизации. Что касается терминологии, то существует мнение, что преобразование означает любую семантически корректную оптимизацию, поэтому абстрактную интерпретацию можно было бы рассматривать только как часть инструментального набора преобразований. В то же время любой формальный статический анализ программ, включая преобразование, является абстрактной интерпретацией. Существует множество явных ограничений по производительности в неоптимизированых реализациях функциональных языков, разумеется, для последовательных архитектур фон-неймановского типа. Например, применение многих функций при вычислении обладает линейной зависимостью от размера аргумента ( формальные определения в гл. Мы уже увидели примеры этого в авторекурсии, которую, как показано в гл. Аналогично можно было бы ожидать, что при выполнении применения функции Фибоначчи используется число вызовов функции, зависящее экспоненциально от аргумента, тогда как два последовательно накапливающих счетчика дают тот же результат за линейное время и постоянное пространство в императивном цикле. Вопрос, будет ли это несущественно в специализированной, предположительно параллельной архитектуре, в значительной степени неуместен. С одной стороны, фон-неймановские машины останутся и в ближайшем, и в далеком будущем, а в любом случае параллельные машины - это набор последовательных процессоров, каждый из которых лучше всего используется при выполнении нетривиальных преобразований. [16]
Подобный анализ во время компиляции называют анализом строгости. Мы будем использовать его для иллюстрации более общего метода абстрактной интерпретации, который, говоря кратко; выводит определенные свойства выполнения программ, работая с абстрактным доменом, гораздо более простым, нежели ( стандартный) семантический домен анализируемых выражений. Другое применение абстрактной интерпретации возникает в системах вывода типов, образующих основу алгоритмов проверки типов, несмотря на то что термин абстрактная интерпретация еще не был введен в то время, когда были написаны первые программы проверки типов. Проверка типов во время компиляции, разумеется, имеет отношение к оптимизации, но уже рассмотрена в гл. [17]
Существует, однако, большое число иных возможностей ее использования при оптимизации функциональных программ путем семантически корректной аннотации. Мы уже встречались с одним примером, который может рассматриваться как абстрактная интерпретация в системе вывода типов, обсужденной в гл. Проверка типов является полностью статичным анализом, проводящимся на этапе компиляции и может быть сформулирована в терминах отображений между различными семантическими доменами, что является сутью абстрактной интерпретации. После этого могут быть установлены надежность и полнота. [18]
С одной стороны, мы исследуем преобразование программ, при котором может быть модифицирована вся структура функциональной программы, а с другой стороны, можно управлять выполнением программы, используя аннотации, порождаемые абстрактной интерпретацией. Однако для имеющих точную математическую семантику функциональных языков и преобразование, и абстрактная интерпретация являются методами, способными обеспечить требуемый семантически корректный тип оптимизации. Что касается терминологии, то существует мнение, что преобразование означает любую семантически корректную оптимизацию, поэтому абстрактную интерпретацию можно было бы рассматривать только как часть инструментального набора преобразований. В то же время любой формальный статический анализ программ, включая преобразование, является абстрактной интерпретацией. Существует множество явных ограничений по производительности в неоптимизированых реализациях функциональных языков, разумеется, для последовательных архитектур фон-неймановского типа. Например, применение многих функций при вычислении обладает линейной зависимостью от размера аргумента ( формальные определения в гл. Мы уже увидели примеры этого в авторекурсии, которую, как показано в гл. Аналогично можно было бы ожидать, что при выполнении применения функции Фибоначчи используется число вызовов функции, зависящее экспоненциально от аргумента, тогда как два последовательно накапливающих счетчика дают тот же результат за линейное время и постоянное пространство в императивном цикле. Вопрос, будет ли это несущественно в специализированной, предположительно параллельной архитектуре, в значительной степени неуместен. С одной стороны, фон-неймановские машины останутся и в ближайшем, и в далеком будущем, а в любом случае параллельные машины - это набор последовательных процессоров, каждый из которых лучше всего используется при выполнении нетривиальных преобразований. [19]
В частности, мы не сможем определить, что выражение 39 - 24 положительно. К сожалению, ситуация подобного рода неизбежно возникает почти во всех оптимизациях, основанных на абстрактной интерпретации; почти - так как правило о знаках для умножения способно дать исчерпывающую информацию, но это является исключением. Таким образом, при анализе строгости мы должны найти все случаи, в которых аргумент, который может быть передан по значению, не будет определен как строгий, но мы уверены, что любой аргумент, который должен быть передан по необходимости, конечно, не будет определен как строгий Разумеется, при достаточном расширении абстрактной области определения мы можем в полной мере представить любое свойство, делая возможным точное предсказание, но в конце концов мы можем и вернуться к стандартной области определения и проделать все вычисления полностью. [20]
В первой главе этой части мы сначала рассмотрим операционное представление преобразования программ и опишем методологию последовательного конвертирования определения функции в более эффективную версию, сохраняющую смысл, с использованием шести различных правил. В этом подходе осуществляется анализ свободных от переменных выражений, записанных ч стиле FP, описанном в гл. Подобный анализ так называемого функционального уровня основан на функциональной алгебре Бекуса, полезные результаты которой вводятся в начале гл. Неформально, с помощью простого численного примера вводится основная идея, затем в качестве типичного примера применения абстрактной интерпретации рассматривается анализ строгости. [21]
Другие приложения, которые различаются главным образом по времени, необходимом для их создания, включают в себя анализ высказываний и анализ сложности. Первый связан с определением того, какое из рекурсивных уравнений в описаниях функции потребуется при данном вызове этой функции. Это важно в компьютерах с параллельной архитектурой, в которых может быть необходим удаленный доступ к разделяемым кодам. Путем определения того, какие части этого кода необходимы ( высказывания), можно значительно сократить количество сообщений, которые эти высказывания пересылают. Анализ сложности также важен для параллельных машин, особенно для машин с улучшенными структурными элементами. Если выражение содержит подвыражение, которое может быть вычислено независимо, например аргументы применения функции или выражение, значением которого является функция и которое применяется к выражению аргумента, то независимые вычисления могут быть поручены ( разбросаны) различным процессорам для параллельного выполнения. Однако такое распределение приводит к дальнейшему росту обмена информацией, и если стоимость разделения вычислений преобладает над выигрышем по времени выполнения вычислений, то смысла увеличивать степень параллелизма таким образом нет. Задача, поэтому, заключается в том, чтобы заранее, на этапе компиляции, знать, как долго будет происходить вычисление подвыражений. Возможно, что на это будет указывать некая мера сложности, определенная для выражений, и если они были выражены в терминах некой нестандартной семантики и домена, то абстрактная интерпретация может стать формальной основой для подобного анализа. [22]
Фактологические, или, как их принято называть в социологии, эмпирические, исследования связаны с анализом того, как происходят события. Однако задача социологии состоит не только в сборе фактов, какими бы интересными и важными они ни были. Мы хотим также знать, почему эти события случаются, и для этого мы должны научиться ставить теоретические вопросы. Они помогут нам правильно интерпретировать факты при поиске причин процессов, находящихся в фокусе конкретного исследования. Мы знаем, что индустриализация оказала большое влияние на формирование современных обществ. Почему мы обнаруживаем различия между обществами, переживающими процессы индустриализации. Почему индустриализация влечет изменения в способах уголовного наказания или в системах семьи и брака. Чтобы ответить на подобные вопросы, необходимо подойти к ним теоретически. Теории предполагают конструирование абстрактных интерпретаций, которые можно использовать для объяснения разнообразных эмпирических ситуаций. Теория индустриализации, например, должна определять основные черты, присущие процессу индустриального развития, и показывать, какие из них наиболее важны для объяснения развития общества. Конечно, фактологические и теоретические вопросы не могут быть отделены друг от друга. Теоретические подходы обоснованы в том случае, когда мы способны проверить их средствами эмпирического исследования. [23]