Оптимизация вычислений и абстрактные машины
Проиллюстрируем особенности реализации наиболее существенных стратегий вычислений на примере КАМ.
Как было показано в ходе предыдущей лекции, такая формализация вычислительной машины как категориальная абстрактная машина позволяет вполне удовлетворительно реализовать модель транслятора языка функционального программирования.
Кроме того, как показывает практика, именно КАМ больше всего подходит для использования в качестве виртуальной машины при реализации современных языков функционального программирования (в частности, языка CaML), в том числе с объектными расширениями (в частности, языка Object CaML).
Тем не менее, в базовом варианте построения категориальной абстрактной машины, который мы исследовали в ходе предыдущих лекций, существует ряд объективных недостатков, не позволяющих реализовать передовые стратегии вычислений, необходимые современным системам программирования.
Перечислим наиболее существенные (с учетом целей и задач нашего курса) из этих недостатков.
Прежде всего, обращает на себя внимание некоторая громоздкость вычислений, хотя это и объясняется отчасти низкоуровневым характером категориальной абстрактной машины. Оказывается, что причиной такой ситуации является ограничение на использование категориальной абстрактной машиной только одноместных операций.
Другим существенным недостатком КАМ является отсутствие поддержки рекурсивных вычислений, которое, как мы увидим впоследствии, устраняется посредством модификации среды вычислений.
Наконец, очевидно, что повторяющиеся фрагменты программы требуют многократных вычислений, поскольку порядок вычислений предопределен и заведомо не оптимален.
Выявив и оценив недостатки "классической" реализации категориальной абстрактной машины, наметим возможные направления оптимизации программ на языке инструкций КАМ.
Прежде всего, для решения проблемы громоздкости вычислений (которая, как отмечалось, вытекает из ограниченности системы команд КАМ только одноместными инструкциями), необходимо осуществить переход к многоместным операциям, изменив синтаксис и семантику языка программирования категориальной абстрактной машины.
Кроме того, в целях оптимизации кода категориальной абстрактной машины целесообразно ввести ряд дополнительных функциональных инструкций, которые обеспечивали бы ускорение вычислений при одновременном сокращении и повышении удобочитаемости текстов программ для КАМ.
Затем, чтобы устранить сложности, связанные с поддержкой категориальной абстрактной машиной рекурсивных вычислений, необходимо не только модифицировать среду, но и расширить язык программирования КАМ дополнительными функциональными инструкциями.
Наконец, следует рассмотреть вопрос о реализации на основе категориальной абстрактной машины поддержки вычислений по необходимости, иначе называемых "ленивыми" (lazy).
Приступим к реализации усовершенствований категориальной абстрактной машины с целью оптимизации стратегии вычислений.
Прежде всего, для решения проблемы громоздкости вычислений, которая обусловлена ограниченностью системы команд КАМ только одноместными инструкциями, необходимо осуществить переход к многоместным операциям.
Заменим "встроенные" в систему команд категориальной абстрактной машины одноместные функции на двухместные.
В частности, в целях экономии времени, рассуждая без ограничения общности, приведем пример записи двухместной функции сложения:
+<x,y> = ?o<?o<'+,x>,y>.
C учетом характеристических равенств для категориальной абстрактной машины , выведенных в ходе предыдущих лекций, получим соотношение
?o<?(x)oy,z> = xo<y,z>,
которое находится в полном соответствии с правилами редукции, принятыми в формальной системе категориальной комбинаторной логики, на основе которой построена КАМ.
Продолжим обсуждение перехода к многоместным операциям в языке программирования категориальной абстрактной машины. Пересмотрим цикл работы (схему смены состояний) категориальной абстрактной машины, расширив пространство состояний КАМ дополнительными инструкциями, которые, по аналогии с основными командами КАМ, представим в форме таблицы 12.1.
true | if abc | sm | S | a c | m |
false | if abc | sm | S | b c | m |
(a,b) | add c | S | {a+b} | C | S |
(a,b) | eq c | S | true/false | C | S |
Как видно из приведенной таблицы, пространство состояний категориальной абстрактной машины расширено посредством введения операций сравнения if, проверки условия eq, а также сложения add. Проиллюстрируем практическую эффективность программного кода усовершенствованной категориальной абстрактной машины следующим примером. Рассмотрим программу категориальной абстрактной машины, вычисляющую сумму целых чисел 2 и 3 в "классической" версии "языка программирования" КАМ:
push cur (push push cdr swap quote 2 cons app swap push cur (cdr) swap quote 3 cons app cons app) swap quote + cons app.
"Запрограммируем" ту же задачу в усовершенствованной версии КАМ:
push quote 2 swap quote 3 cons add.
Как видно, объем программы сократился более чем втрое.
Рассмотрим, каким образом можно решить проблему с рекурсивными вычислениями в категориальной абстрактной машине. Проблема рекурсии сводится к принципиальной цикличности и потенциальной бесконечности обрабатываемых инструкций.
Чтобы устранить сложности, связанные с поддержкой категориальной абстрактной машиной рекурсивных вычислений, необходимо расширить язык программирования КАМ дополнительными функциональными инструкциями.
Пересмотрим цикл работы (схему смены состояний) категориальной абстрактной машины, расширив пространство состояний КАМ дополнительными инструкциями, которые, по аналогии с основными командами абстрактной машины, представим в форме таблицы 12.2.
T | dum c | sm | $Y | C | S |
[a:b] | wind c | (t$Y)S | (t.[a:b]) | C | S |
До сих пор рассматривались варианты абстрактных машин, реализующих механизм означивания переменных, известный под названием вызова по значению.
Однако существуют и другие стратегии вычислений. Рассмотрим более подробно возможные подходы к означиванию переменных.
При вычислении с вызовом по значению (call-by-value) все выражения должны быть означены до вычисления операции аппликации.
При вычислении с вызовом по имени (call-by-name) до вычисления операции аппликации необходима подстановка термов вместо всех вхождений формальных параметров перед означиванием. Именно эта стратегия лежит в основе "ленивых" (lazy), "отложенных" (delayed) или "замороженных" (frozen) вычислений, которые принципиально необходимы для обработки потенциально бесконечных структур данных.
Наконец, при вычислении с вызовом по необходимости (call-by-need) ранее вычисленные значения аргументов сохраняются в памяти компьютера только в том случае, если необходимо их повторное использование.
Чтобы устранить сложности с поддержкой категориальной абстрактной машиной "ленивых" вычислений, пересмотрим цикл работы КАМ, расширив пространство состояний дополнительными инструкциями для "замораживания" (freeze) и "размораживания" (unfreeze), которые представим в форме таблицы 12.3.
s | {freeze c}.C1 | S | C.s | C1 | S |
C.s | unfreeze.C | S | s | C | S |
s | unfreeze.C | S | s | C | S |
