Ациклічність та замкненість макрокомпозицій
Задачу експлікації проектування програмних систем розглянуто з точки зору сутнісної платформи. Обґрунтовано адекватність вибору ациклічних композицій як базовий засіб експлікації логіки будови проектів. Для ациклічних композицій встановлено замкненість відносно суперпозиції. Показано, що встановлена...
Saved in:
| Date: | 2012 |
|---|---|
| Main Authors: | , |
| Language: | Ukrainian |
| Published: |
Інститут програмних систем НАН України
2012
|
| Series: | Проблеми програмування |
| Subjects: | |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/86582 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Ациклічність та замкненість макрокомпозицій / В.Ю. Вінник, Т.С. Парфірова // Проблеми програмування. — 2012. — № 2-3. — С. 18-24. — Бібліогр.: 10 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-86582 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-865822015-09-24T03:01:56Z Ациклічність та замкненість макрокомпозицій Вінник, В.Ю. Парфірова, Т.С. Теоретичні та методологічні основи програмування Задачу експлікації проектування програмних систем розглянуто з точки зору сутнісної платформи. Обґрунтовано адекватність вибору ациклічних композицій як базовий засіб експлікації логіки будови проектів. Для ациклічних композицій встановлено замкненість відносно суперпозиції. Показано, що встановлена в попередніх роботах замкненість відносно множення та накладання є наслідком замкненості відносно суперпозиції. The problem of explication of software design is treated from the perspective of entity platform. It is established that acyclic compositions are adequate basic means for explication of design structures and logics. For acyclic compositions, closure against superopsition is proved. It is shown that closure against multiplication and overlapping is a corollary of that against superposition. 2012 Ациклічність та замкненість макрокомпозицій / В.Ю. Вінник, Т.С. Парфірова // Проблеми програмування. — 2012. — № 2-3. — С. 18-24. — Бібліогр.: 10 назв. — укр. 1727-4907 http://dspace.nbuv.gov.ua/handle/123456789/86582 004.415.2 uk Проблеми програмування Інститут програмних систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Теоретичні та методологічні основи програмування Теоретичні та методологічні основи програмування |
| spellingShingle |
Теоретичні та методологічні основи програмування Теоретичні та методологічні основи програмування Вінник, В.Ю. Парфірова, Т.С. Ациклічність та замкненість макрокомпозицій Проблеми програмування |
| description |
Задачу експлікації проектування програмних систем розглянуто з точки зору сутнісної платформи. Обґрунтовано адекватність вибору ациклічних композицій як базовий засіб експлікації логіки будови проектів. Для ациклічних композицій встановлено замкненість відносно суперпозиції. Показано, що встановлена в попередніх роботах замкненість відносно множення та накладання є наслідком замкненості відносно суперпозиції. |
| author |
Вінник, В.Ю. Парфірова, Т.С. |
| author_facet |
Вінник, В.Ю. Парфірова, Т.С. |
| author_sort |
Вінник, В.Ю. |
| title |
Ациклічність та замкненість макрокомпозицій |
| title_short |
Ациклічність та замкненість макрокомпозицій |
| title_full |
Ациклічність та замкненість макрокомпозицій |
| title_fullStr |
Ациклічність та замкненість макрокомпозицій |
| title_full_unstemmed |
Ациклічність та замкненість макрокомпозицій |
| title_sort |
ациклічність та замкненість макрокомпозицій |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2012 |
| topic_facet |
Теоретичні та методологічні основи програмування |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/86582 |
| citation_txt |
Ациклічність та замкненість макрокомпозицій / В.Ю. Вінник, Т.С. Парфірова // Проблеми програмування. — 2012. — № 2-3. — С. 18-24. — Бібліогр.: 10 назв. — укр. |
| series |
Проблеми програмування |
| work_keys_str_mv |
AT vínnikvû aciklíčnístʹtazamknenístʹmakrokompozicíj AT parfírovats aciklíčnístʹtazamknenístʹmakrokompozicíj |
| first_indexed |
2025-07-06T14:04:24Z |
| last_indexed |
2025-07-06T14:04:24Z |
| _version_ |
1836906620390473728 |
| fulltext |
Теоретичні та методологічні основи програмування
18
УДК 004.415.2
АЦИКЛІЧНІСТЬ ТА ЗАМКНЕНІСТЬ МАКРОКОМПОЗИЦІЙ
В.Ю. Вінник, Т.С. Парфірова
Київський національний університет імені Тараса Шевченка,
01601 Київ, вул. Володимирська, 60,
тел.: (+38044) 521 3345
E-mail: vadim.vinnik@gmail.com, tetiana.parfirova@gmail.com
Задачу експлікації проектування програмних систем розглянуто з точки зору сутнісної платформи. Обґрунтовано адекватність
вибору ациклічних композицій як базовий засіб експлікації логіки будови проектів. Для ациклічних композицій встановлено
замкненість відносно суперпозиції. Показано, що встановлена в попередніх роботах замкненість відносно множення та
накладання є наслідком замкненості відносно суперпозиції.
The problem of explication of software design is treated from the perspective of entity platform. It is established that acyclic compositions
are adequate basic means for explication of design structures and logics. For acyclic compositions, closure against superopsition is proved.
It is shown that closure against multiplication and overlapping is a corollary of that against superposition.
Вступ
Загальна задача експлікації програмування [1−3], яка вирішується шляхом покрокового прагматико-
обумовленого розгортання концептуально єдиного сутнісного ядра, включає в себе низку більш вузьких задач
експлікації тих чи інших часткових випадків програмування а також метазадачу підтримки системної єдності
через встановлення зв’язків між ними, тобто відповідно задач аналізу та синтезу. Зосередимося на перших.
Декомпозиція програмування може здійснюватись „по горизонталі” – відповідно до предметних областей та
індукованих ними відгалужень прикладного програмування, або „по вертикалі” – відповідно до ступеню
абстракції чи конеретизації у розгляді предмету. Що стосується конкретних мов програмування, цілих
парадигм (імперативної, об’єктно-орієнтованої, функціональної тощо), а також різноманітних відгалужень
(бази даних, задачі символьної обробки та ін.), відповідні семантичні структури та логіка побудови програм
добре вивчені завдяки численним роботам [4−7]. Разом з тим, якщо розглядати програмуваня більш абстрактно,
відволікаючись від специфіки мов, середовищ та технологій, як структуровану та цілеспрямовану діяльність з
побудови програмних систем, в якій центральне місце займає проектування, наявні моделі виглядають
недостатньо переконливими і повними. Це і не дивно: якщо у першому випадку предмет розгляду – програма,
що виконується на реальній чи ідеальній машині, – безпосередньо допускає строгий опис математичними
засобами, то у другому випадку предмет надто обтяжений залежністю від психологічних, ринкових,
соціокультурних та інших мінливих факторів, що важко піддаються моделюванню.
Для експлікації проектування програмних систем у першому наближенні потрібно почати з того єдиного
принципу, що може вважатися безсумнівним: будь-які артефакти людської діяльності (твори мистецтва, наукові
теорії, політичні доктрини, в тому числі й проекти програмних систем) мають композиційну природу. По-
перше (так би мовити, у просторовому вимірі) композиційна платформа дозволяє розглядати сутність як певне
поєднання інших сутностей, по-друге, що більш важливо, в часовому вимірі дозволяє бачити процес її
становлення як покрокове введення та виключення композицій, а по-третє – власну роль та призначення
сутності дозволяє розглядати з точки зору її включеності в ту чи іншу композицію.
Відповідно до загальних принципів композиційного, експлікативного програмування та сутнісної
платформи, експлікувати певний клас сутностей – значить описати характерний для нього клас композицій,
тобто виділити ті композиції, що визначають прагматико-обумовлену суть цих сутностей, задають їх
сутесутнісні відношення. Домовимося композиції проектного рівня, щоб відрізняти їх від композицій рівня
програмної реалізації, називати макрокомпозиціями.
Не намагаючись охопити всі визначальні властивості макрокомпозицій, зосередимо увагу на одній з них,
а саме ациклічності. Дійсно, цикли в програмуванні хоча й відіграють надзвичайно важливу роль, але
зосереджені переважно на мікрорівні (на рівні конкретних алгоритмів) і тим самим інкапсульовані з точки зору
проектного рівня. Проект як абстраговане відображення складових програмної системи та зв’язків між ними
має вигляд або ієрархічної моделі (відношення надоб’єкт-підоб’єкт, надклас-підклас тощо), або
однонаправленого, без зворотних ланок, потоку передачі даних між підсистемами (наприклад, діаграма
послідовностей в мові UML).
Зазначимо: беручи за основу розгляду ациклічність проектів, ми не відкидаємо і не ігноруємо цикли як
такі, а замість цього вказуємо їх місце. З великого досвіду формалізації семантики програм [4, 6] відомо, що
будь-яка циклічна (чи хоча б потенційно циклічна) сутність має незрівнянно складніші властивості, ніж
ациклічна. Проекти, за самим своїм призначенням, мають бути фундаментом для створення системи, яка сама
© В.Ю. Вінник, Т.С. Парфірова, 2011
ISSN 1727-4907. Проблеми програмування. 2012. № 2-3. Спеціальний
Теоретичні та методологічні основи програмування
19
має високий рівень складності. Але ж немає сенсу в якості фундаменту для цілого класу складних систем брати
сутності, які через власну складність в свою чергу потребували б фундаменту.
Оскільки для самих по собі проектів важно запропонувати просту та водночас точну логіко-математичну
модель, для поточної задачі дослідження властивостей ациклічних композицій залучимо допоміжні сутності –
програми, що не містять циклів. Це дозволить застосувати добре розроблений формальний апарат
композиційного програмування (КП). Виходячи з наведених міркувань введено поняття ациклічної функції,
обґрунтовано його адекватність для відображення передач керування та даних між підсистемами великої
системи, розглянуто близькі за сенсом поняття послідовно-паралельних та ланцюгових функцій, вирішено
питання про взаємну звідність цих трьох класів функцій. Також показано, що клас ациклічних функцій
замкнений відносно операцій множення і накладання, які становлять в КП моделі послідовного та паралельного
виконання програм.
У даній роботі покажемо, що клас ациклічних функцій замкнений також відносно суперпозиції, та
виявимо зв’язки цієї властивості з властивостями, дослідженими раніше.
Основні поняття і означення композиційного програмування
Тотожне відображення множини X позначатимемо ( ){ }XxxxX ∈= |,id , область визначення та область
значень функції – та відповідно. f fdom frang YX позначаємо множину всіх відображень множини Y в
множину X . U|α позначено обмеження бінарного відношення α на множину U . Проекцію відношення ρ
по -й компоненті позначаємо k ρkpr .
Відповідно до композиційного програмування (КП) [1, 2] і розробленої на його основі сутнісної
платформи [3], дані моделюються іменними множинами (ІМ), а програми – іменними функціями (ІФ).
Позначимо і множину всіх імен і денотатів відповідно. -іменною множиною називають скінченне
функціональне бінарне відношення , . Клас всіх іменних множин позначимо .
V D V
VD∈α V⊆V N
Операція накладання ІМ визначається так:
( ) ( ) ( ){ }βαββα 1pr,,|, ∉∈∪=∇ ududu .
Можна довести асоціативність накладання.
За означенням, ІФ – це унарна часткова функція вигляду ΝΝ→~:f . ІФ називається -арною, якщо
, і -арною, якщо до того ж , . Не кожна іменна функція має
визначену арність. Функція, яка має деяку арність, називається поліарною. Всюди далі розглядаються лише
поліарні іменні функції.
f V
Vf Ddom ⊆ ( WV , ) Wf Drang ⊆ V⊆WV ,
Говорячи про еквівалентність ІФ, всюди маємо на увазі еквівалентність за поведінкою, яка полягає у
тому, що на однакових аргументах дві ІФ або мають однаковий результат, або разом невизначені:
( ) ( )ααα gf −∈∀ ~N .
Операції над ІФ називають композиціями. Змістовно, композиції моделюють збирання складної
програми з більш простих програм (підпрограм). Для подальшого розгляду потрібні дві композиції: множення
ІФ (відповідає послідовному виконанню) та накладання ІФ (відповідає паралельному виконанню), означених
наступним чином:
( )( ) ( )( )αα fggf −~o ,
( )( ) ( ) ( )ααα gfgf ∇−∇ ~ .
Слід звернути увагу на те, що в останній формулі знаком ∇ позначено операцію над ІФ у лівій частині й
операцію над ІМ у правій; це не повинно призводити до непорозумінь, оскільки з контексту завжди ясно, який з
двох сенсів мається на увазі.
Нехай ІФ та f g – відповідно - та ( )11,VU ( )22 ,VU -арні. Тоді ІФ є gf o ( )21,VU -арною, якщо 21 UV = ,
та всюди невизначеною в іншому випадку. ІФ gf ∇ є ( )21, VVU ∪ -арною, якщо , інакше – всюди
невизначеною.
UUU == 21
З останнього видно, що для застосування тих чи інших композицій до наперед заданих ІФ потрібно
узгодити їх арності. Для цього існують описані далі допоміжні функції.
Обмеженням назвемо параметричну ( )VUV ∩, -арну ІФ (де ), таку, що, при , V
U↑ V⊆VU , VD∈α
( ) ( ) ( ){ }UududuUV
U ∈∧∈==↑ ααα ,|,| .
Теоретичні та методологічні основи програмування
20
Перейменуванням назвемо параметричну ( )UV , -арну ІФ , де ; ξb V⊆VU , VU →:ξ , таку, що, при
, VD∈α
( ) ( )( )( ){ }Uuuu ∈= |, ξααξb .
Змістовно, ця операція заміняє в ІМ α імена Vv∈ на нові імена Uu∈ , такі, що ( ) vu =ξ . Відзначимо,
що взаємна однозначність відображення ξ не вимагається, тобто одне ім’я з α може після перейменування
перейти в декілька нових імен. Безпосередньо з означення слідує, що якщо WV =⊇= ξα 21 prpr , то
( )( ) αξαξ obo =↑V
W , де позначено множення унарних функцій (слід мати на увазі, що ІМ o α саме є функцією,
що іменам ставить у відповідність денотати).
Ациклічні функції та їх властивості
Нагадаємо означення. Нехай програма складається з підпрограм (n if ni ,,1K= ). Вхід програми в
цілому розглядається як вихід її уявної 0-ї підпрограми; дуальним чином, вихід ациклічної програми
розглядається як вхід її уявної -ї підпрограми. Характеристична особливість ациклічних програм полягає
у тому, що відношення „діяти після”, або „використовувати дані від” є частковим порядком на множині
підпрограм. Цей порядок можна доповнити до лінійного: для всіх i , , де
( 1+n )
j 10 +≤<≤ nji , канал передачі
даних з виходу -ї підпрограми на вхід -ї існує тоді й тільки тоді, коли i j ji < .
Припустимо, функції мають арність if ( )ii VU , при ni ,,1K= . Нехай дана множина імен V , яку також
будемо позначати , та множина імен U , яку також позначимо . Нехай для всіх i , , де 0V 1+nU j 10 <≤ i ≤ +nj ,
дано відображення ijξ .
Сукупність цих відображень можна розглядати як трикутну матрицю Ξ , що має рядок і стільки ж
стовпчиків, причому нумерація рядків починається з 0, а стовпчиків – з 1. Накладаються обмеження:
1+n
, ( )ij
n
ij
iV ξ2
1
1
prU
+
+=
⊇ ni ,0= ,
, ( )U
1
0
1pr
−
=
=
j
i
ijjU ξ 1,1 += nj .
Тоді, за означенням, ациклічна ІФ в базисі Φ – це ( )UV , -арна ІФ , така, що
, та для будь-якої -іменної множини
( nUV fff K,1,
ΞΤ= )
Φ∈nff ,,1 K V α значення ( )αβ f= визначається за наступними
рекурентними співвідношеннями, де αα =0 , 1+= nββ :
, при ( )iik
k
i
k αξβ o∇
−
=
=
1
0
1,1 += nk ,
( )kkk f βα = , при nk ,1= .
Зазначимо, що iα при є значенням функції (змістовно, результатом роботи i -ї підпрограми),
а
ni ≤≤0 if
iβ при є аргументом функції . 11 +≤≤ ni if
У попередніх роботах встановлено низку властивостей ациклічних функцій.
Твердження 1. Скінченний добуток, тобто ІФ вигляду nfff oKo1= можна представити як ациклічну
ІФ в базисі . Справді, нехай ІФ має арність { nff ,,1 K } if ( )ii VU , для всіх ni ,,1K= . Перепозначимо
через . Тоді за умови узгоджених арностей
1U
0V ( )nVV fff
n
,,T 1,0
KΞ= при
Теоретичні та методологічні основи програмування
21
.
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎣
⎡
∅
∅∅
=Ξ
nV
V
V
id
id
id
1
0
MO
K
K
Твердження 2. Скінченне накладання, тобто ІФ вигляду nfff ∇∇= K1 можна представити як
ациклічну ІФ в базисі . Справді, нехай ІФ має арність { nff ,,1 K } if ( )iVU , для всіх . Позначимо
. Тоді при
ni ,,1K=
i
n
i
VV
1=
= U ( )nVU fff ,,T 1, KΞ=
.
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
∅
∅∅
∅
=Ξ
−
n
n
V
V
V
UUU
id
id
id
ididid
1
1
MMO
K
K
Твердження 3. Добуток довільних ациклічних функцій gf o ( )mUV fff ,,1, KΞΤ= та ( )nWU ggg ,,1, KΨΤ=
може бути перетворений на еквівалентну ациклічну функцію в базисі { }nm ggff ,,,,, 11 KK .
Твердження 4. Накладання довільних ациклічних ІФ gf ∇ ( )mVU fff ,,1, KΞΤ= та ( )nWU ggg ,,1, KΨΤ=
може бути перетворене на еквівалентну ациклічну функцію в базисі { }nm ggff ,,,,, 11 KK .
Ациклічність суперпозиції ациклічних функцій
Основна задача даної роботи полягає у доведенні наступної властивості.
Теорема. Нехай дано дві ациклічні ІФ, ( )mVU fff ,,1, KΞΤ= та ( )nYX ggg ,,1, KΨΤ= , дано таке число , що
, причому функція є -арною. Тоді функція , отримана підстановкою функції
k
mk ≤≤1 kf ( YX , ) h g замість
базисної функції , тобто функція kf
( )( )mknYXkVU ffggffh ,,,,,,, 11,11, KKK +
Ψ
−
Ξ ΤΤ= ,
може бути представлена у вигляді
( )mknkVU ffggffh ,,,,,,, 1111, KKK +−
ΖΤ=
при деякій матриці перейменувань . Ζ
Позначимо кількість базисних функцій функції : ih h 1−+= nmr . Тепер перепишемо співвідношення з
означень ациклічної функції для кожної з функцій , f g , : h
( ) 10 += mf βα , (1)
при ( )jji
i
j
i αξβ o∇
−
=
=
1
0
11 +≤≤ mi , (2)
( )iii f βα = при mi ≤≤1 , (3)
( ) 10 += ng δγ , (4)
при ( )jji
i
j
i γψδ o∇
−
=
=
1
0
11 +≤≤ ni , (5)
( )iii g δγ = при ni ≤≤1 , (6)
( ) 10 += rh νμ , (7)
при ( )jji
i
j
i μζν o∇
−
=
=
1
0
11 +≤≤ ri , (8)
Теоретичні та методологічні основи програмування
22
( )iii h νμ = при ri ≤≤1 . (9)
Аргумент і значення функції ототожнимо з аргументом і значенням функції : f h
00 μα = , (10)
11 ++ = rm νβ . (11)
Крім того, випишемо умову, що аргумент та значення функції ототожнюються з аргументом та
значенням функції
kf
g :
kβγ =0 , (12)
kn αδ =+1 . (13)
Тоді для базисних функцій , їх аргументів та значень маємо такі означення: ih
(14)
⎪
⎩
⎪
⎨
⎧
−+≤≤+
−+≤≤
−≤≤
=
+−
+−
.1,
,1,
,11,
1
1
nminkf
nkikg
kif
h
ni
ki
i
i
(15)
⎪
⎩
⎪
⎨
⎧
−+≤≤+
−+≤≤
−≤≤
=
+−
+−
,1,
,1,
,10,
1
1
nmink
nkik
ki
ni
ki
i
i
α
γ
α
μ
(16)
⎪
⎩
⎪
⎨
⎧
+≤≤+
−+≤≤
−≤≤
=
+−
+−
.,
,1,
,11,
1
1
nmink
nkik
ki
ni
ki
i
i
β
δ
β
ν
Тепер розглянемо аргументи та значення функцій . Можливі три випадки. ih
Випадок 1. . Оскільки, згідно (14, 15, 16), 11 −≤≤ ki ii fh = , ii αμ = та, ii βν = , з огляду на (10, 11),
єдино можливим значенням jiζ при 10 −≤≤ ij є
jiji ξζ = . (17)
Випадок 2. . Згідно (16), аргументом 1−+≤≤ nkik iν функції є ih
, jkij
ki
j
kii γψδν o1,
0
1 +−
−
=
+− ∇==
тобто
. ( ) ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
∇= +−
−
=
+− ∇ jkij
ki
j
kii γψγψν oo 1,
1
01,0
Маючи на увазі (12), підставимо вираз (9) для kβ у перший член накладання, а в другому, згідно (15), виразимо
jγ ( ) через kij −≤≤1 jμ ( ): 1−≤≤ ijk
. ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
∇⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
= +−+−
−
=
−
=
+− ∇∇ jkikj
i
kj
jjk
k
j
kii μψαξψν ooo 1,1
11
0
1,0
Тепер в першому члені замінимо jα на jμ згідно (15), а спільний множник внесемо до оператора накладання:
. ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
∇⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
= +−+−
−
=
+−
−
=
∇∇ jkikj
i
kj
jjkki
k
j
i μψμξψν ooo 1,1
1
1,0
1
0
Порівнявши отриманий вираз з (8), робимо висновок:
Теоретичні та методологічні основи програмування
23
(18)
⎩
⎨
⎧
−≤≤
−≤≤
=
+−+−
+−
.1,
,10,
1,1
1,0
ijk
kj
kikj
jkki
ji ψ
ξψ
ζ
o
Випадок 3. . Згідно (16), аргумент nmink +≤≤+ iν функції є ih
. ( ) ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
∇∇⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
= +−
−
+=
+−+−
−
=
∇∇ jnij
ni
kj
knikjnij
k
j
i αξαξαξν ooo 1,
1
1,1,
1
0
У першому члені накладання можна замінити jα на jμ за (15), у другому члені, згідно (13), підставимо 1+nδ
замість kα , а в третьому члені jα ( nijk −≤≤+1 ) можна замінити на jμ ( 1−≤≤+ ijnk ):
. (19) ( ) ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
∇∇⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
= +−+−
−
+=
++−+−
−
=
∇∇ jninj
i
nkj
nnikjnij
k
j
i μξδξμξν ooo 1,1
1
11,1,
1
0
Розглянемо окремо множник 1+nδ з другого члена цього виразу. Застосувавши його означення (9), винесемо
перший доданок з оператора накладання:
. ( ) ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
∇== +
=
++
=
+ ∇∇ jnj
n
j
njnj
n
j
n γψγψγψδ ooo 1,
1
01,01,
0
1
З 0γ тут можна обійтися таким же чином, як і у випадку 2, тобто замінити на означення kβ (2), після чого
всі jα та jγ замінити на відповідні jμ згідно (15):
, ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
∇⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
= +
=
−
=
++ ∇∇ jnj
n
j
jjk
k
j
nn γψαξψδ ooo 1,
1
1
0
1,01
тобто
, ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
∇⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
= ++−
−+
=
+
−
=
+ ∇∇ jnkj
nk
kj
jjkn
k
j
n μψμξψδ ooo 1,1
1
1,0
1
0
1
Підставивши це у (19), отримуємо:
. ( )( ) ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
∇⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
∇⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
∇= +−+−
−
+=
++−+−
−+
=
++−+−
−
=
∇∇∇ jninj
i
nkj
jnkjnik
nk
kj
jjknniknij
k
j
i μξμψξμξψξξν oooooo 1,1
1
1,11,
1
1,01,1,
1
0
Порівнюючи цей вираз з (8), доходимо висновку, що при nmink +≤≤+
(20)
⎪
⎩
⎪
⎨
⎧
−≤≤+
−+≤≤
−≤≤∇
=
+−+−
++−+−
++−+−
.1,
,1,
,10,
1,1
1,11,
1,01,1,
ijnk
nkjk
kj
ninj
nkjnik
jknniknij
ji
ξ
ψξ
ξψξξ
ζ o
oo
Таким чином, вирази (17, 18, 20) повністю визначають елементи матриці Ζ .
Зазначимо, що представити суперпозицію функції g замість функції у вигляді ациклічної функції
можна й іншим способом, з простішим виглядом матриці перейменувань, але ціною неістотного розширення
базису двома допоміжними функціями, а саме:
kf
( )mknkVU ffggffh YX ,,,id,,,,id,, 1111, KKK +−
ΖΤ=
DD
,
де елементи матриці Ζ визначаються за такими правилами:
• jiji ξζ = при ; kij ≤<≤0
• kikjji −−= ,ψζ при 1++≤<≤ nkijk ;
• 1,1 −−−−= ninjji ξζ при 21 ++≤<≤++ nmijnk ;
• 1, −−= nijji ξζ при та 10 −≤≤ kj 22 ++≤≤++ nmink .
Теоретичні та методологічні основи програмування
24
• В усіх інших випадках ∅=jiζ .
Іншими словами, якщо матрицю представити в блочній формі Ξ
, ⎥
⎦
⎤
⎢
⎣
⎡
Ξ
ΞΞ
=Ξ
12
0201
де матриці та верхньо-трикутні, а 01Ξ 12Ξ 02Ξ – прямокутна, причому 01Ξ містить рядків і стовпчиків, то
матриця має вигляд
k
Ζ
.
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
Ξ
∅Ψ
Ξ∅Ξ
=Ζ
12
0201
Таким чином, клас ациклічних функцій замкнений відносно суперпозиції. Варто уваги, що встановлені
раніше властивості замкненості цього класу відносно множення та накладання (твердження 3 та 4) виявляються
наслідками даної властивості.
Справді, нехай дано ациклічні функції та f g . Згідно твердження 1, ациклічною у базисі { }21,hh є
функція . За теоремою, ациклічною буде функція, отримана з неї підстановкою замість та 21 hhh o= f 1h g
замість . Такі ж міркування справедливі для накладання. 2h
Висновок
У контексті основної проблематики – експлікації проектів програмних систем – зазначені властивості
підтверджують адекватність обраних засобів розкриття логіки та структури проектів. Дійсно, якщо до
ациклічної композиції підставити ті чи інші аргументи – підпрограми (if ni ,,1K= ), буде отримано деяку
конкретну програму; якщо ж в якості аргументів підставити інші проекти, результатом підстановки буде знову
проект. Іншими словами, подібно до того, як чиста логіка предикатів першого порядку є спільною основою для
необмеженого класу прикладних логік, параметризація запропонованої нами моделі базисними функціями дає
деякі прикладні програмування, тоді як без параметризації вона являє собою „чисту”, абстраговану від змісту,
форму, спільну для цих програмувань.
1. Редько В.Н. Композиции программ и композиционное программирование // Программирование. – 1978. – № 5. – С. 3-24.
2. Редько В.Н. Композиционная структура программологии // Кибернетика и системный анализ. – 1998. – № 4. – С. 47-66.
3. Редько В.Н., Редько И.В., Гришко Н.В. Программологические основания сущностной платформы // Проблеми програмування. –
2008. – № 2-3 (Спец. випуск). – С. 75-83.
4. Hoare, C.A.R., Jifeng, He. Unifying Theories of Programming. − Prentice Hall Europe. − 1998 − 298 p.
5. Кауфман В.Ш. Языки программирования. Концепции и принципы. − М.: Радио и связь, 1993. − 430 с.
6. Дейкстра Э. Дисциплина программирования. − М.: Мир, 1978. − 280 с.
7. Басараб И.А., Никитченко Н.С., Редько В.Н. Композиционные базы данных. − К.: Либідь, 1992. − 192 с.
8. Parfirova T., Vinnyk V Compositional Model of Acyclic Programs // CSE'2010 International Scientific Conference on Computer Science and
Engineering, September 20-22, 2010, Košice - Stará Ľubovňa, Slovakia.
9. Parfirova T., Vinnyk V Some properties of acyclic compositional programs // Information Models of Knowledge. – ITHEA № 19. – P. 460-464.
10. Парфірова Т.С., Вінник В.Ю. Семантичні структури програм без циклів // Матеріали 7-ї Міжнародної конференції «Теоретичні та
прикладні аспекти побудови програмних систем» – TAAPSD’2010, Київ, Україна, 4-8 жовтня 2010 р. – C. 378-384.
АЦИКЛІЧНІСТЬ ТА ЗАМКНЕНІСТЬ МАКРОКОМПОЗИЦІЙ
Вступ
Основні поняття і означення композиційного програмування
Ациклічні функції та їх властивості
Ациклічність суперпозиції ациклічних функцій
Висновок
|