3. Модель асинхронного выполнения функциональных программ

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

1. листья дерева помечены символами элементов D{} (D – универсум данных,  - вычислимое неопределенное значение);

2. внутренние вершины дерева помечены либо символами операций , , , , либо функциональными термами.

Не ограничивая общности, допустим, что интересующая нас функция X₁ определяется системой рекурсивных функциональных уравнений:

() X_i = _i, i = 1, 2, …, n, где _i – функциональный терм, не содержащий вхождений функциональных переменных, отличных от X₁, X₂, …, X_n.

Вычисление значения функции , являющегося первой координатой наименьшего решения для X₁ системы (), для аргумента d представляется в виде последовательности состояний, начальным состоянием которой является дерево с двумя вершинами, корневая вершина которого помечена символом функциональной переменной X₁, а листовая – аргументом d, и которое содержит единственное (если процесс вычисления заканчивается успешно) конечное состояние. Если это состояние есть дерево, состоящее из одной вершины, помеченное некоторым данным d, то мы говорим о результативном окончании вычисления значения функции с результатом d. Если это конечное состояние есть , то мы говорим о безрезультатном окончании вычисления. Переходы из состояния в состояние при вычислении значения функции определяются правилами преобразования деревьев, разделенными на два подмножества: правила развертывания и правила свертывания деревьев.

Правила преобразования деревьев задаются в виде схем изменения состояний и обозначаются uu, где u и u – схемы состояния. Схема состояния отличается от конкретного состояния тем, что в ней для разметки вершин дерева состояния могут использоваться следующие метапеременные: t – произвольный функциональный терм (возможно с индексами), u – произвольное дерево-состояние, d – произвольный элемент D (возможно с индексами), f – базисная функция, X_i – функциональная переменная.

Результат применения правила uu к состоянию u есть дерево, полученное путем замены в дереве u некоторого его поддерева u на дерево u.

На рис. 1 показаны правила развертывания, на рис. 2 – правила свертывания деревьев.

Замечание: Символ неопределенного значения  в данной модели является вычислимым значением. Поэтому любая функция f в языке в общем случае рассматривается как однозначное соответствие из D в D, где D и D – множества, которым принадлежат область определения и область значений функции f соответственно. При этом полагается f()= для любой базисной функции f.

1.

{, , , }

2.

3.

Рис. 1. Правила развертывания деревьев

4.		5.		6.
7.		8.		9.
10.		11.	{, }	12.
13.	d  

Рис. 2. Правила свертывания деревьев

Данная модель является недетерминированной, поскольку в общем случае возможно применение нескольких правил к дереву-состоянию вычислений, и поэтому в зависимости от применяемого правила будут получаться различные последовательности вычислений. Также модель является параллельной, т.к. возможно одновременное применение нескольких правил к несвязным кустам дерева состояния. Источником параллелизма являются свойства операций , , .

Важно отметить, что не всякий порядок применения правил преобразования состояний приводит к корректному вычислению значения функции. Например, такой случай имеет место, если при вычислении значения (t₁t₂)(d) сначала делается попытка вычисления значения t₁(d), которое не определено и процесс вычислений продолжается бесконечно, а значение t₂(d) определено. Таким образом, условием корректности реализации модели является параллельное (или квазипараллельное) вычисление значений функций, соединяемых операцией .

Не менее важным является умение прерывать ненужные вычисления. Как видно из правил 6-11, при получении на одной из ветвей значения d, отличного от , или значения  вычисления, связанные с другой ветвью, необходимо прервать.

Кроме этого, модель предоставляет возможность повышения эффективности вычислений за счет вычислений с упреждением. Если имеется достаточное количество ресурсов, то при вычислении значения (t₁t₂)(d) можно значение t₁(d) вычислять одновременно с t₂(d), стремясь максимально распараллелить процесс вычислений.

Эти особенности модели вычислений являются принципиальными при ее реализации на вычислительных системах и пир разработке эффективных алгоритмов планирования параллельного выполнения функциональных программ.

*

1