Введение в теорию программирования. Функциональный подход


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


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

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

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

Приступим к реализации усовершенствований категориальной абстрактной машины с целью оптимизации стратегии вычислений.

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

Заменим "встроенные" в систему команд категориальной абстрактной машины одноместные функции на двухместные.

В частности, в целях экономии времени, рассуждая без ограничения общности, приведем пример записи двухместной функции сложения:

+<x,y> = ?o<?o<'+,x>,y>.

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

?o<?(x)oy,z> = xo<y,z>,

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

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

Таблица 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

<


Начало  Назад  Вперед



Книжный магазин