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


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


/p>

Как видно из приведенной таблицы, пространство состояний категориальной абстрактной машины расширено посредством введения операций сравнения 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.

Таблица 12.2. Дополнительные инструкции КАМ для реализации рекурсивных вычислений

Старое состояние КАМНовое состояние КАМТермКодСтекТермКодСтек

T

dum c

sm

$Y

C

S

[a:b]

wind c

(t$Y)S

(t.[a:b])

C

S

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

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


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



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