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. ;

2. 

3. 

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

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

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

Очевидно, что любая пара деструкторов ипри ij представляет пару ортогональных функций. Полагая, что арности c_i и c_j одинаковы, отношение будет функциональным. Также, если₁ и ₂ – ортогональные функции, а ₃ и ₄ – произвольные функциональные композиции, то ₁₃ и ₂₄, ₁₃ и ₂₄, ₁₃ и ₂₄ являются парами ортогональных функций. Очевидно, что если в представлении ₁₂…_k, k>1, функциональные композиции _i и _j, ij, попарно ортогональны или совместны, то отношение  является функциональным.

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

Пример.

Определим в языке натуральный ряд чисел следующим образом:

, где o и succ (0, 1)-арный и (1, 1)-арный конструкторы с графиками: ,, где C = {o, succ}.

Обратным для NAT является разрешимый предикат принадлежности D_C:

.

Если определить аппликацию для функций-деструкторов o^-1 и succ^-1 в форме:

,

и рассматривать  как вычислимое неопределенное значение, то

, где – наименьшее решение для P_NAT в его определении выше.

Пример.

Для иллюстрации задания функций рассмотрим определение в языке функции умножения на NAT:

Для ясности здесь указаны арности определяемых функций F_ум и F_сл; очевидно их тип принадлежит множеству отображений NATNATNAT.

Как только указаны типы базисных функций (в данном примере это функции o: {}NAT, succ: NATNAT, : ‘t‘t‘t, i = 1, 2, где ‘t – произвольный тип, тип определяемых функций F_ум и F_сл может быть выведен путем реконструкции типов правых частей их определений в уравнениях выше согласно согласованию типов для операций композиции и решению типовых уравнений, вытекающих из этих уравнений. Таким образом построен алгоритм типового контроля в разработанном языке функционального параллельного программирования

В рассматриваемом языке функционального программирования в качестве базисных включены реализованные и эффективно вычисляемые компьютером арифметические, логические и другие функции вместе с множеством базисных типов (real, int и др.) на которых они определены.

По аналогичным соображениям эффективности реализации в язык включены механизмы импортирования функций из других, в том числе, последовательных языков программирования (C, C++, Java и др.), что естественно, существенно расширяет возможности задания «базисных» функций, а сам языке превращается в некотором смысле в полиязычную систему программирования.