Архитектура компьютеров и ВС, принципы параллельного программирования (Файлы для подготовки к экзамену), страница 5

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

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

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

; ;

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

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

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

;

Для того чтобы сохранялось свойство функциональности для 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) также не определено.

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

; ; , если значение 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), которое уже не может повлиять на результат.

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

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

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

Пусть 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.

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

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

3.4.1.2. Задание данных и базисных функций

Данные в общем случае представляют собой множества кортежей одинаковой длины. С теоретической точки зрения, данные в языке представляются как (0, m)-арные, m0, d-отношения. Определение данных осуществляется путем замыкания операций композиции , , ,  и оператора наименьшей фиксированной точки над непустым множеством конструкторов. Каждое определяемое множество данных относится к определенному типу данных, который характеризуется в некотором смысле и общей структурой построения этого множества и используемыми при этом конструкторами. Идентификация типа данных осуществляется путем однозначного сопоставления ему имени.

Отметим, что операция  на данных (при определении абстрактных типов данных, которые представляются как (0, m)-арные d-отношения), равносильна операции декартова произведения; операция  по-прежнему имеет интерпретацию теоретико-множественного объединения.

Пусть – множество символов конструкторов и – множество символов парных им деструкторов. С каждым конструктором с_i и деструктором связана их арность: (n_i, 1) и (1, n_i) соответственно.

Конструкторы и деструкторы интерпретируются как функциональные d-отношения на эрбрановском универсуме – индуктивном классе D_C:

1. если арность c_i есть (0, 1), то c_iD_C;

2. если c_i имеет арность (n_i, 1), n_i>0, то c_i₁₂…_nD_C¹ для любых _iD_C, i = 1, 2, …, n_i;

3. других элементов, кроме определенных в п. 1 и 2 в D_C нет.

Введем интерпретацию конструкторов:

и

.

Легко видеть, что конструкторы – всюду определенные функции на D_C, а деструкторы в общем случае – частичные функции, обратные функциям, сопоставляемым конструкторам.

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

.

Более того, можно расширить сигнатуру операций композиции d-отношений путем добавления к ней унарной операции взятия обратного отношения:

.

Рассмотрим множество базисных функций , где INT – натуральный ряд чисел, m>0, 1im, .

Можно показать, что на D_C теперь выразима любая вычислимая функция при условии, что C содержит хотя бы один (0, 1)-арный конструктор и хотя бы один (m, 1)-арный конструктор для m>0.

В частности, в языке с этой сигнатурой операций и этим множеством базисных функций выразимы все комбинаторные d-отношения из [7]. В качестве примера приведем здесь некоторые из них:

> (функция-нуллификатор): , где (n_i, 1) – арность конструктора c_i;

 (тождественная функция): ;

> (функция равенства или на D_C – тождества кортежей длины n):

(первое уравнение говорит о том, что кортежи равны, если равны их соответствующие элементы; второе уравнение утверждает, что два элемента множества D_C равны, если они тождественны);

>/– (функция неравенства кортежей длины n):

.

Эти функции имеют интерпретацию:

> ,

 ,

> ,

>– /– , где n>0;

для n = 0 график первых трех функций есть {((, ()}, у последней он пуст.

Аналогично можно определить комбинаторное функциональное d-отношение:

< , n>0 и для n=0 < .

Определимость в языке функции > позволяет исключить операцию композиции функций  (условие), как зависящую операцию:  =   >.

Кроме того, операция взятия обратного отношения становится конструктивной и для всякого определения d-отношения может быть «опущена» на уровень базисных функций путем использования следующих правил [7]:

1. ;

(> ), где ₁ и ₂ имеют арности (n, n₁) и (n, n₂) соответственно.

1. Пусть X_i = _i, i = 1, 2, …, k; обратным для X₁ (не нарушая общности, положим, что в этой системе уравнений нас интересует X₁) является наименьшее решение для системы уравнений , i = 1, 2, …, k, где .

Введение понятия конструктора и деструктора служит основой для построения ортогональных функций на абстрактных типах данных.