3.4.1.1. Операции композиции

Пусть f – определяемая функция, f₁, f₂ – заданные функции определенных типов. Обозначаем значение функции  для аргумента x через (x); требуемое согласование типов для заданных функций при применении к ним операций композиции осуществляется путем их явного указания. В определении операции композиции сначала дается синтаксис ее представления, затем дается определение графика новой функции, определяемое через операцию композиции, и ее аппликативная форма, определяющая результат применения функции к аргументу.

Для упрощения график функции обозначается тем же символом, что и сама функция; , ,  – обозначение кортежей.

Все операции композиции являются бинарными, и их определение дается в инфиксной форме.

1. Последовательная композиция ()

; ;

2. Конкатенация ()

; ; f(x) = f₁(x)f₂(x)

3. Объединение ()

;

Для того чтобы сохранялось свойство функциональности для f операция  (отдавая дань предыстории, мы используем вместо общепринятого обозначения операции  теоретико-множественного объединения знак ) должна применяться только к совместным или ортогональным функциям.

Функции f₁ и f₂ совместны тогда и только тогда, когда

;

функции f₁ и f₂ ортогональны, если они совместны и не существует кортежей ₁ и ₂ таких, что (, ₁)f₁ и (, ₂)f₂ для всякого .

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

Аппликация функции f, определенной посредством операции , теперь имеет следующую семантику: f(x) = f₁(x) или f(x) = f₂(x), т.е. одному из значений f₁(x) или f₂(x), которое определено; если значение f₁(x) и f₂(x) оба не определены, f(x) также не определено.

4. Условие ()

; ;, если значение f₁(x) определено.

Заметим, что первые две операции композиции позволяют выразить известный оператор подстановки, используемый в языке рекурсивных функций и в обычной математической нотации:

,

где g – m-арная, а f₁, f₂, …, f_m – n-арные заданные функции; .

Через две другие операции композиции легко представляется условный оператор языков программирования или задание функции путем разбора случаев, используемое в обычной математической практике:

. Здесь ,, …,– попарно ортогональные пропозициональные функции, представляющие p₁, p₂, …, p_n. При этом значение «ложь» для p_i(x), i = 1, 2, …, n, можно трактовать как неопределенное значение для , причем это неопределенное значение является вычислимым и в описываемом далее языке представляется явно в виде обозначения. Значение «истина» для p_i(x) совпадает со значением .

Ясно, что значение функции может быть также не определено, если процесс его вычисления длится неограниченно. Мы различаем эти оба случая неопределенного значения, причем, если в результате вычисления значения функции получено неопределенное значение , мы можем существенно повысить эффективность при распараллеливании. Так в последнем примере при вычислении значения f(x) возможно одновременное вычисление всех значение p_i(x) и f_i(x), i = 1, 2, …, n, но получив в результате p_i(x) =  для некоторого i мы можем прервать начатое вычисление f_i(x), которое уже не может повлиять на результат.

Заметим, что операции композиции , ,  ассоциативны,  – ассоциативна и коммутативна. Введение следующего старшинства для операций композиции: , , ,  позволит в дальнейшем опускать некоторые скобки в задании функций.

С вычислительной точки зрения, только операция  является последовательной, остальные операции композиции параллельны.

5. Определение функций через систему функциональных уравнений.

Пусть F₁, F₂, …, F_n – символы типизированных функциональных переменных, ₁, ₂, …, _n – формы или термы, представляющие конечные композиции этих переменных и базисных функций f₁, f₂, …, f_m, m0, относительно введенных операций композиции функций.

Синтаксически оператор наименьшей фиксированной точки, как способ композиции функций f₁, f₂, …, f_m, определяется как система функциональных уравнений

() F_i = _i, i = 1, 2, …, n, где F_i – связанные в этом определении функциональные переменные.

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

, i = 1, 2, …, n.

Здесь – результат одновременной подстановки A_j вместо переменной X_j, j = 1, 2, …, k, в C.

Известно [7], что операции , ,  и  монотонны и, более того, непрерывны относительно своих аргументов и, как следствие, значения , i = 1, 2, …, n, всегда существуют и могут быть выражены явно:, i = 1, 2, …, n, где– нигде не определенная функция, а для k>0,.

Отметим, что в системе уравнений () во всех термах _i, i = 1, 2, …, n, должно быть выполнено согласование типов для используемых операций композиции, и тип каждой функциональной переменной F_i должен совпадать с типом _i, i = 1, 2, …, n.

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

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