Оптимизация вычислений в абстрактных машинах

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

Прежде всего, проанализированы недостатки рассмотренной выше базовой модификации категориальной абстрактной машины и сформулированы возможные направления оптимизации программ, представленных в терминах инструкций «классической» КАМ. В частности, предложено расширение системы инструкций КАМ с целью поддержки многоместных операций с параметрами функций, а также для реализации рекурсивных вычислений. Кроме того, представлена попытка классификации вычислительных стратегий, существующих в современных языках программирования. При этом существенное внимание уделено анализу вызова функций с передачей параметров по имени и по значению, а также рассмотрены и обсуждены формулировки теорем Черча — Россера о стратегиях вычислений.

Изложено введение в понятийный аппарат «ленивых» (г.е. выполняемых по мере необходимости) вычислений и рассмотрены возможные пути их реализации. Формальное исследование вычислительных стратегий категориальной абстрактной машины позволит провести сравнительный анализ возможностей по оптимизации кода КАМ и виртуальной машины, применяемой в технологической платформе .NET.

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

Как было показано в предыдущем параграфе, такая формализация вычислительной машины, как категориальная абстрактная машина, позволяет вполне удовлетворительно реализовать модель транслятора языка функционального программирования. Кроме того, как показывает практика, именно КАМ наиболее подходит для использования в качестве виртуальной машины при реализации современных профессиональных языков функционального программирования (в частности, языка CaML), в том числе и с объектными расширениями (в частности, языка Object CaML).

Тем не менее в том базовом варианте построения категориальной абстрактной машины, который мы исследовали выше, существует ряд объективных недостатков, не позволяющих реализовать передовые стратегии вычислений, необходимые современным системам программирования.

Перечислим наиболее существенные (с учетом целей и задач этой книги) из этих недостатков. Прежде всего, обращает на себя внимание некоторая громоздкость вычислений, которая, хотя и объяснима отчасти низкоуровневым характером категориальной абстрактной машины, но все же неоправданно велика. Оказывается, что причиной такой ситуации является ограничение на использование категориальной абстрактной машиной только одноместных операций. Другим существенным недостатком КАМ является отсутствие поддержки рекурсивных вычислений, которое, как мы увидим впоследствии, устраняется посредством модификации среды вычислений. Наконец, очевидно, что повторяющиеся фрагменты программы требуют многократных вычислений, поскольку порядок вычислений предопределен и заведомо не оптимален.

Выявив и оценив недостатки «классической» реализации категориальной абстрактной машины, наметим возможные направления оптимизации программ на языке инструкций КАМ.

Прежде всего, для решения проблемы громоздкости вычислений (которая, как отмечалось, вытекает из ограниченности системы команд КАМ только одноместными инструкциями) необходимо осуществить переход к многоместным операциям, изменив синтаксис и семантику языка программирования категориальной абстрактной машины. Кроме того, в целях оптимизации кода категориальной абстрактной машины целесообразно ввести ряд дополнительных функциональных инструкций, которые обеспечивали бы ускорение вычислений при одновременном сокращении и повышении удобочитаемости текстов программ для КАМ. Затем, чтобы устранить сложности, возникающие с поддержкой категориальной абстрактной машиной рекурсивных вычислений, необходимо не только модифицировать среду, но и расширить язык программирования КАМ дополнительными функциональными инструкциями. Наконец, следует рассмотреть вопрос о реализации на основе категориальной абстрактной машины поддержки вычислений по необходимости, иначе называемых «ленивыми» (lazy).

Приступим к реализации усовершенствований категориальной абстрактной машины с целью оптимизации стратегии вычислений. Прежде всего, для решения проблемы громоздкости вычислений, которая обусловлена ограниченностью системы команд КАМ только одноместными инструкциями, необходимо осуществить переход к многоместным операциям.

Заменим «встроенные» в систему команд категориальной абстрактной машины одноместные функции на двухместные. В частности, (в целях экономии времени, рассуждая без ограничения общности) приведем пример записи двухместной функции сложения:

+ =8 О .

С учетом характеристических равенств для категориальной абстрактной машины, выведенных выше, получим соотношение.

8 о =x о ,.

находящееся в полном соответствии с правилами редукции, принятыми в формальной системе категориальной комбинаторной логики, на основе которой построена К AM. Пересмотрим цикл работы (схему смены состояний) категориальной абстрактной машины, расширив пространство состояний КАМ дополнительными инструкциями, которые, по аналогии с основными командами КАМ, представим в форме табл. 4.4.

Таблица 4.4

Как видно из приведенной таблицы, пространство состояний категориальной абстрактной машины расширено посредством введения операций сравнения if, проверки условия eq, а также сложения add. Проиллюстрируем практическую эффективность программного кода усовершенствованной категориальной абстрактной машины следующим примером. Рассмотрим программу категориальной абстрактной машины, вычисляющую сумму целых чисел 2 и 3 в «классической» версии «языка программирования» КАМ:

push cur (push push edr swap quote 1 cons app swap push cur (edr) swap quote 2 cons app cons app) swap quote+cons app.

Запрограммируем ту же задачу в усовершенствованной версии КАМ: push quote 2 swap quote 3 cons add.

Очевидно, что объем программы сократился более чем втрое.

Рассмотрим, каким образом можно решить проблему с рекурсивными вычислениями в категориальной абстрактной машине, которая сводится к принципиальной цикличности и потенциальной бесконечности обрабатываемых инструкций.

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

Пересмотрим цикл работы (схему смены состояний) категориальной абстрактной машины, расширив пространство состояний КАМ дополнительными инструкциями, которые, по аналогии с основными командами абстрактной машины, представим в форме табл. 4.5.

Таблица 4.5

Как видно из приведенной таблицы, пространство состояний категориальной абстрактной машины расширено посредством введения операций wind и dum для обработки рекурсивных объектов.

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

При вычислении с вызовом по значению (call-by-value) все выражения должны быть означены до вычисления операции аппликации.

При вычислении с вызовом по имени (call-by-name) до вычисления операции аппликации необходима подстановка термов вместо всех вхождений формальных параметров до означивания. Именно эта стратегия лежит в основе «ленивых» (lazy), «отложенных» (delayed) или «замороженных» (frozen) вычислений, которые принципиально необходимы для обработки потенциально бесконечных структур данных.

Наконец, при вычислении с вызовом по необходимости (call-by-need) ранее вычисленные значения аргументов сохраняются в памяти компьютера только в том случае, если необходимо их повторное использование.

Чтобы устранить сложности с поддержкой категориальной абстрактной машиной «ленивых» вычислений, пересмотрим цикл работы КАМ, расширив пространство состояний дополнительными инструкциями для «замораживания» (freeze) и «размораживания» (unfreeze), которые представим в форме табл. 4.6.

Таблица 4.6

Сформулируем ряд теорем, известных по именам их авторов как теоремы Черча — Россера и позволяющих установить особенности различных вычислительных стратегий, а также взаимосвязей между ними. Заметим, что возможность «ленивого» связывания переменных с их значениями в языках функционального программирования вытекает из формулировки теорем Черча — Россера.

Поскольку доказательство теорем Черча — Россера выходит за рамки этой книги, ограничимся приведением формулировок теорем как таковых.

Теорема Черча — Россера. Пусть Е1 и Е2 — лямбда-выражения, причем справедливо соотношение: Е1=Е2. Тогда существует лямбда-выражение Е такое, что выполнены следующие условия: во-первых, Е1=Е; во-вторых, Е2=Е. Заметим, что символ «=» в формулировке теоремы понимается в смысле отношения конвертируемости. Если в языке вызовы по имени и, но значению приводят к определенному результату, то это один и тот же результат. Если вычисление значения выражения приводит к определенному результату, то к нему всегда приводит вызов по имени и не всегда — но значению.

После выяснения особенностей различных вычислительных стратегий, а также взаимосвязей между ними наметим возможные направления реализации стратегии «ленивых» вычислений.

Наиболее очевидным, исходя из специфики целей этой книги, представляется подход, при котором пересматривается цикл работы категориальной абстрактной машины, причем пространство состояний расширяется дополнительными инструкциями для «замораживания» (freeze) и «размораживания» (unfreeze), ранее представленными нами в виде табл. 4.6.

Напомним, что ни SECD-машина П. Лендина, ни категориальная абстрактная машина в «чистом», «классическом» представлении не обладают способностью поддержки реализации механизма отложенного означивания переменных.

Другим возможным подходом к реализации «ленивой» стратегии вычислений может служить использование механизма редукции графов для преобразования лямбда-выражений, который обеспечивает единственность означивания для каждого аргумента.

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

Подводя итоги сравнительного анализа стратегий вычисления и направлений их оптимизированной реализации на основе категориальной абстрактной машины, можно сделать следующие выводы (в сопоставлении КАМ с виртуальной машиной технологической платформы Microsoft .NET).

Во-первых, необходимо отметить, что в рамках рассматриваемой инструменталыю-технологической платформы Microsoft .NET используется виртуальная машина с универсальным высокоуровневым ассемблером (MSIL), принципиально подобная КАМ. Абстрактная машина .NET транслирует исходный текст на языке программирования в код MSIL, который в значительной степени является аналогичным КАМ-коду.

Во-вторых, виртуальная машина инструментально-технологической платформы Microsoft .NET является достаточно универсальным решением и предусматривает такие важнейшие механизмы поддержки проектирования и реализации языков программирования, как централизованная «сборка мусора», обработка ошибок и исключительных ситуаций. Кроме того, виртуальная машина .NET, как и категориальная абстрактная машина, отличается высокой аппаратной совместимостью, поскольку реализует целый ряд механизмов, обеспечивающих безопасную схему вычислений.

В-третьих, виртуальная машина .NET, в отличие от категориальной абстрактной машины, поддерживает широкую языковую интероперабельность, т. е. возможность одновременной разработки программных проектов на различных языках программирования в условиях одной и той же универсальной среды вычислений. Таким образом, представляется принципиально возможной и практически реализуемой разработка компонент проекта на наиболее целесообразных языках программирования.

В-четвертых, виртуальная машина .NET обеспечивает поддержку универсальной среды вычислений с широким спектром унифицированных предопределенных типов и структур данных.

Завершая первый раздел книги, посвященный исследованию современных языков программирования (на примере языка программирования F#) и поддерживающих их сред вычислений (па примере инструментальнотехнологической платформы .NET), кратко резюмируем содержание рассмотренных вопросов и проблем.

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

Далее посредством перечисленных теорий формализованы такие важнейшие аспекты языков программирования, как синтаксис и семантика. Кроме того, исследовано интуитивно ясное понятие типа, изучены основы теории типов и типизации в языках программирования.

Рассмотрены вопросы, связанные с представлением рекурсивных функций и множеств, а также с формализацией рекурсивных вычислений. Еще одним пунктом исследований стали важнейшие аспекты реализации языков программирования, включая схему трансляции в промежуточные коды виртуальных машин SECD и КАМ. Исследованы в сравнении различные стратегии вычислений и оптимизации кода.

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

• 1) математическое обоснование объектного подхода к программированию (на примере языка программирования С#);
• 2) компонентное проектирование интегрированных гетерогенных программных систем (на примере языков функционального программирования F# и объектно-ориентированного программирования С#);
• 3) теория и практика разработки событийно управляемых приложений;
• 4) сравнительное исследование функционального и объектно-ориентированного подходов к программированию.

Дальнейшие исследования, согласно практике, сложившейся на протяжении первого раздела книги, будут проводиться синтетически по направлениям теоретического обоснования программирования на основе современных формальных систем computer science и современной практики проектирования и реализации программного обеспечения на основе универсальной и прогрессивной программно-инструментальной платформы Microsoft .NET.

Контрольные вопросы

Вопрос 1.

Вариант 1: в чем состоит основное значение оптимизации кода?

• а) в повышении вычислительной эффективности (+);
• б) в повышении удобочитаемости программ;
• в) в повышении удобства использования программ.

Вариант 2: каковы основные стратегии вычислений?

• а) вызов по имени, по значению и по необходимости (+);
• б) вызов, но имени и по значению;
• в) вызов по имени и по необходимости.

Вариант 3: что из перечисленного является синонимом «ленивых» вычислений?

• а) вызов по имени;
• б) вызов по необходимости (+);
• в) вызов по значению.

Вопрос 2.

Вариант 1: каковы основные формализации ленивых вычислений?

• а) редукция графов и комбинаторная логика (+);
• б) редукция графов и теория вычислений;
• в) теория вычислений и комбинаторная логика.

Вариант 2: каков графический механизм формализации ленивых вычислений?

• а) такого механизма не существует;
• б) теория вычислений;
• в) редукция графов (+).

Вариант 3: каковы основные пути оптимизации КАМ-кода?

• а) введение многоместных операций (+);
• б) поддержка рекурсивных вычислений (+);
• в) устранение коллизий переменных.

Вопрос 3.

Вариант 1: что является недостатком «классической» версии КАМ?

• а) поддержка только одноместных операций (+);
• б) отсутствие поддержки рекурсивных вычислений (+);
• в) коллизии переменных.

Вариант 2: в чем состоит практическое значение теоремы Черча — Россера?

• а) в возможности «ленивых» вычислений (+);
• б) в возможности ликвидации коллизий переменных;
• в) в эквивалентности вызова по имени и вызова по значению.

Вариант 3: каковы возможные способы реализации «ленивых» вычислений?

• а) расширение абстрактных машин (+);
• б) редукция графов (+);
• в) категориальная комбинаторная логика.