РОЗДІЛ 2
ОСНОВНІ МЕТОДОЛОГІЧНІ ПОЛОЖЕННЯ КОМПОЗИЦІЙНО-НОМІНАТИВНОГО МЕТОДУ
2.1. Принципи композиційно-номінативного методу
Композиційне програмування (КП) як теоретичне підґрунтя і основа програмології - науки про програми - було започатковане В. Н. Редьком [23, 24] в 1960-х роках як розвиток структурологічного підходу Г.Фреге [25], який був перенесений на програмування А. А. Ляпуновим [26-28] та розвинений Ю. І. Яновим [29, 30], А. П. Єршовим [31-36], Л. А. Калужніним [37, 38], В. М. Глушковим [39, 40] та іншими.
Композиційно-номінативний метод формалізації поняття програми базується на наступних принципах, які досить детально обґрунтовані в роботах [18, 23, 42] та низці інших. Ці фундаментальні принципи визначають напрямок досліджень композиційних методів, які є основою КП. Головні принципи носять філософсько-методологічне навантаження.
Принцип розвитку (від абстрактного до конкретного). Поняття програми уточнюється в процесі його розвитку. Цей процес починається з найбільш абстрактних представлень, які відображають загальні істотні властивості програм, потім переходить до більш конкретних представлень, що відображають специфічні властивості програм, і таким чином поступово розкривається поняття програми в його багатстві.
Принцип апплікативності (функціональності). На гранично високому рівні абстракції програми можуть розглядатися як функції, які при застосуванні до вхідних даних, можуть виробляти вихідні дані.
Принцип номінативності програм. Програми можна представляти як імена, які позначають функції, що відображають вхідні дані в результати.
Принцип композиційності [23]. Програми (функції) будуються з більш простих програм за допомогою композицій.
Принцип дескриптивності. Програми можна представляти у вигляді складних дескрипцій, побудованих із використанням дескрипцій більш простих програм і композицій, які описують функції, що відображають вхідні дані в результати.
Принцип номінативності даних. Структури даних програм можна розглядати як похідні від номінативних структур.
Принцип обчислюваності. Програми і композиції є обчислюваними відображеннями.
Зазначені принципи визначають як основні наступні поняття: дані, функції, імена функцій, композиції, дескрипції. Ці поняття утворять пентаду основних програмних понять. Формалізація понять пентади здійснюється відповідно до теоретико-функціонального підходу, при якому базовим поняттям виступає поняття функції, а не множини.
Принцип теоретико-функціональної формалізації. Формалізація програмних понять здійснюється в рамках теоретико-функціонального підходу, в основі якого лежить поняття функції (відображення), розглянуте на різних рівнях абстракції.
Поняття функції трактується дуже широко як часткової багатозначної функції (відношень). Цей клас функцій застосовується для представлення семантики недетермінованих програм. Оскільки теорія таких функцій розроблена слабко, введемо для них основні використовувані поняття і позначення.
На сьогодні КП активно розвивається і широко застосовується на практиці [19, 62, 79-84]. На основі КП розвивається інша теорія - теорія інституцій [85]. Принципи КП знаходять відображення і використовуються в працях вітчизняних та зарубіжних науковців [86-91].
2.2. Часткові багатозначні функції
Нехай A і R - довільні множини. Неформально, часткове багатозначне відображення f із A у R трактується як об'єкт, який при застосуванні до елемента a із A, може (неоднозначним способом) виробити в якості результату деякий елемент r із R (позначаємо f(a)?=r) або ж не виробити ніякого результату (тобто бути не визначеним на a - позначаємо f(a)?). Цей опис можна зробити більш строгим, якщо сказати, що f можна однозначно охарактеризувати його розширеним графіком gru(f ) ? A?(R?{u}), де u?(A?R). Тоді застосування f до a можна описати таким чином: вибирається довільний елемент (a,ru)?gru(f ) і якщо ru=r (r?R), тo r є результат застосування f до a, якщо ж ru=u, тo результат не визначений. Клас усіх часткових багатозначних відображень із A у R позначаємо AR. Для задання функції f?AR будемо часто використовувати індексний конструктор функцій вигляду [ (i) ( (i) | i ? I ], де :I A, :IR - індексні часткові однозначні відображення з деякої множини індексів I у множини A і R відповідно. Такий конструктор задає функцію f у такий спосіб. На a?A значення f може дорівнювати значенню на такому i?I, для якого (i)?=a. Якщо ж таке (i) не визначено або ж необхідного i не існує, то значення f на a буде не визначено. Якщо відображення і будуть тотальними відображеннями, то в конструкторі будемо використовувати традиційні позначення ai і ri для елементів індексованих множин, одержуючи конструктори [ai (ri | i?I], [ai ((i) | i?I] і [(i)(ri | i?I].
Для характеризації багатозначної функції (відношення) f поряд із розширеним графіком будемо також використовувати наступні поняття:
* графік (реляційна складова) - gr(f) = { (a,r) | f(a)?=r, a?A, r?R},
* множина визначеності - def(f)={a | f(a) ?, a?A},
* множина невизначеності - und(f)={a | f(a)?, a?A},
* множина результатів - res(f)={r | ? a?A ( f(a)?=r)}.
Приклад. Нехай A=R={a,b,c,d}. Розглянемо функцію f =[a ( a, a (b, a (, b ( a, b (b, c ( a, d (]. Ця функція
* на елементі a може приймати значення a або b або бути не визначеною,
* на елементі b завжди визначена і може приймати значення a або b,
* на елементі c завжди визначена і може приймати тільки одне значення a,
* на елементі d завжди не визначена.
Множини функції, які характеризують f:
* gru(f )={(a,a), (a,b), (a,u), (b,a), (b,b), (c,a), (d,u)},
* gr(f )={(a,a), (a,b), (b,a), (b,b), (c,a)},
* def(f )={a,b,c},
* und(f )={a,d},
* res(f)={a,b}.
Введемо позначення для наступних класів відображень:
* часткових багатозначних - A R,
* часткових однозначних - A R,
* тотальних однозначних - A R,
* реляційних (def(f ) ? und(f )=?) - A R,
* скінчених (gr(f ) скінченне) - A R,
* скінченнях реляцій