К. М. Лавріщева програмна інженерія підручник Київ, 2008
 Скачать 5.23 Mb.
|
|
5.2.2. Експлікативне, номінативне програмування Разом з новими парадигмами програмування розробляється загальна теорія програмування, програмологія, яка об'єднує ідеї логіки, конструктивної математики і інформатики, уточнює поняття програми, самого програмування і на єдиній концептуальній основі надає загальний формальний апарат для конструювання програм [27-29]. Серед найважливіших програмних понять і принципів виділяються поняття композиції і принцип композиційності, який тлумачить програми як функції, що будуються з інших функцій за допомогою спеціальних операцій, названих Розділ 5 137 композиціями. Принцип композиційності став основним в композиційному програмуванні. З уразуванням композиційної експлікації (від explication-уточнення, роз'яснення) поняття програмування було розвинуто логіко-математичною композиційної системою побудови програм, що отримала надалі назву експлікативного програмування. Це програмування інтегрує в собі всі найбільш суттєві парадигми (стилі) програмування (структурне, функціональне, об'єктно- орієнтоване і ін.) в рамках концептуально єдиної експлікативної платформи, основу якої становлять три основні типи об'єктів: власне об'єкти, засоби побудови з одних об'єктів інших (функції) і програмологічні засоби застосування методів побудови (композиції). Експлікативне програмування містить у собі теорію дескриптивних і декларативних програмних формалізмів для розробки моделей структур даних, функцій і засобів конструювання з них програм [27–29]. Для цих структур вирішені проблеми існування, зєднання і ефективності. Теоретичну основу ЕП становлять логіка, конструктивна математика, інформатика, композиційне програмування і класична теорії алгоритмів. Для зображення алгоритмів програм використовуються алгоритмічні мови і методи програмування: функціональне, логічне, структурне, денотаційне і ін. Принципами експлікативного програмування є: – розвиток поняття програми в абстрактному розумінні і поступова його конкретизація за допомогою експлікацій; – дотримання принципу прагматичності або корисності визначення поняття програми введенням поняття проблеми, що ставиться для вирішення задач користувача; – принцип адекватності орієнтований на абстрактну побудову програм і реалізацію проблеми з урахуванням інформативності даних і їх аплікативності. Програма розглядається як функція, що виробляє вихідні дані на основі вхідних даних. Функція – це об'єкт, якому зіставляється денотат імені функції за допомогою відношення іменування (номінації); принцип дескриптивності дозволяє трактувати програму як складні дескрипції, побудовані з простих функцій і композицій відображення вхідних даних в результати на основі принципу обчислюваності. Розвиток поняття функції здійснюється за допомогою принципу композиційності, тобто складання програм (функцій) з простіших програм для створення нових програмних об'єктів зі складними дескрипціями функцій. Програми містять у собі номінативні (іменовані) дані, мовні вирази, терми і формули. Процес розвитку програми здійснюється у вигляді ланцюжка понять: дані – функція–ім'я функці–композиція–дескрипція. Тріада дані–функція–композиція задає семантичний аспект програми, а дані–ім'я функції–дескрипція – синтаксичний аспект. В експлікативному програмуванні головними є семантичний аспект, система композицій і номінативність, що орієнтована на системний опис номінативних відношень при побудові даних, функцій, композицій і дескрипцій [28]. На вищих рівнях подання абстракції програми використовуються композиційно-номінативні системи (КНС), що містять у собі трійку простих систем – композиційну, дескриптивну та денотаційну. Композиційна система визначає 138 Розділ 5 способи побудови функцій за деякою множиною даних. Дескриптивна система задає дескрипції (вирази, терми, формули), що застосовують для подання функцій. Денотаційна система задає денотати (значення, зміст) дескрипцій. У цілому КНС забезпечують уточнення абстракції поняття програми шляхом використання спеціальних мовних систем опису різноманітних класів функцій, які називаються композиційно-номінативними мовами функцій. Такі системи тісно пов'язані з алгеброю функцій і даних і побудовані в семантико-синтаксичному стилі. Вони відрізняються від традиційних систем (моделей програм) теоретико- функціональним підходом, використанням класів однозначних n-арних функцій, номінативними відображеннями і структурами даних. Для побудови математично простих і адекватних моделей програм параметричного типу використовується КНС і методи універсальної алгебри, математичної логіки і теорії алгоритмів. Дані в КНС розглядаються на трьох рівнях: абстрактному, булевому і номінативному. Клас номінативних даних забезпечує побудову іменованих даних, багатозначних номінативних даних або мультиіменованих даних, що задаються рекурсивно. У рамках даного програмування розроблені нові засоби для визначення систем даних, функцій і композицій номінативного типу, імена аргументів яких належать деякій множині імен Z. Композиція визначається на Z- номінативних наборах іменних функцій [29]. Номінативні дані дозволяють задавати структури даних, яким властиві неоднозначність іменування компонентів, типи множини, мультимножини, реляції і т.п. Функції мають властивість аплікативності, їх абстракції задають, відповідно, класи слабких і сильних аплікативних функцій. Слабкі функції дозволяють задавати обчислення значень на множині вхідних даних, а сильні – забезпечують обчислення функцій на заданих даних. Композиції класифікуються рівнями даних і функцій, а також типами аргументів. Експлікація композицій відповідає абстрактному розгляду функцій як слабоаплікативних функцій, а їх уточнення будується на основі поняття детермінанта композиції як відображення спеціального типу. Клас аплікативних композицій призначений для конструювання широкого класу програм. 5.2.3. Алгоритмічні алгебри Під час конструювання алгоритмів програмісти керуються в основному інтуїтивним підходом, не замислюючись над тим, чи утворюють певну систему виконувані ними операції, проте така система є, вона формально описана і називається алгоритмічною алгеброю. Наразі розроблено кілька алгоритмічних алгебр, найвідомішими з яких є алгебра Дейкстри, алгебра схем Янова та алгоритміка програм, досліджена у працях В.М. Глушкова і Г.О. Цейтліна. Дослідження і побудова алгебри алгоритмів або алгоритмічної алгебри почалося з проектування логічних структур ЕОМ під керівництвом академіка В.М.Глушкова. Як результат була створена теорія систем алгоритмічних алгебр (САА), що потім Г.О.Цейтліним була покладена в основу узагальненої теорії структурованих схем алгоритмів і програм, названою ним алгоритмікою [30]. Алгоритміка програм призначена для побудови послідовних і паралельних програм зі структурних схем з використанням апарату формальних алгебраїчних перетворень і канонічних форм опису логічних і операторних виразів. Її основу Розділ 5 139 становлять САА, розширені формалізмами для зображення логічних умов виконання паралельних програм, а також методами символьної мультиобробки [30, 31]. Основними поняттями алгебри алгоритмів є: – операції над множинами, булеві операції, предикати, функції й оператори; – бінарні і n-арні відношення, еквівалентність, частково і цілком упорядковані множини; – графи-схеми й операції над графовими структурами; – операції сигнатури САА, аксіоми і правила визначення властивостей програм на основі стратегії згортання, розгортання і їх комбінацій; – методи синтаксичного аналізу структурних програм і символьна обробка. Об'єкти алгоритміки – моделі алгоритмів і програм, що подаються у вигляді схем. Алгоритміка базується на комп'ютерній алгебрі, логіці і використовується для формального опису алгоритмів в МП. Схема реалізації програм засобами алгоритміки наведено на рис. 5.15. Рис. 5.15. Схема проектування програм в алгебрі алгоритміки У рамках алгоритміки розроблено спеціальні інструментальні засоби реалізації алгоритмів програм, що використовують сучасні об'єктно-орієнтовані засоби і метод моделювання UML. Цим забезпечується практичне застосування розробленої теорії алгоритміки у реалізації прикладних задач, починаючи з їхньої постановки, формування вимог і розробки алгоритмів і закінчуючи одержанням програм, що розв’язують ці задачі. Алгебра алгоритмів. Алгебра алгоритмів АА = {A, }, як і будь-яка алгебра, — це основа А і сигнатура операцій з елементами цієї основи. За допомогою операції сигнатури можна додати довільний елемент q AА. Це називається системоюутворювальної алгебри. Якщо з цієї системи не може бути виключений жоден елемент без порушення властивостей, то така система утворювальних алгебр називається базисом алгебри. 140 Розділ 5 Операції алгебри задовольняють наступні аксіоматичні закони: асоціативності, комутативності, ідемпотентності, закони виключення третього і суперечності. Алгебру, яку задовольняють перераховані операції, називають булевою. В алгебрі алгоритмів використовується алгебра множин, тобто елементи множини й операції над ними (об'єднання, перетину, доповнення і ін.). Вводиться також поняття універсуму – множини операцій постановки і розв’язання деякої задачі [30]. Основні об'єкти алгебри алгоритмів – схеми алгоритмів і їх суперпозиції, тобто підстановки одних схем в інші. З підстановкою зв'язані розгорнення, що відповідає спадному процесу проектування алгоритмів, і згортання, тобто перехід до більш високого рівня специфікації алгоритму. Схеми алгоритмів відповідають конструкціям структурного програмування. Послідовне виконання операторів А і В записується у вигляді композиції А*У; альтернативне виконання операторів А и В (u (А, У)) означає, якщо u – істинне, то виконується А, інакше В; цикл (u (А, У))виконується, поки не стане істинною умова u (u – логічна змінна). За допомогою цих елементарних конструкцій будується більш складна схема алгоритму: ::={ [u 1 ] А 1 }, А 1 ::= { [u 2 ] А 2 * D} , А 2 ::= А 3 * C, А 3 ::= { [u] А, B}, u ::= u 2 u 1 Здійснивши суперпозицію шляхом згортання даної схеми алгоритму , одержуємо таку схему: ::= {[ u 1 ]{ [u 2 ] ( [u 2 u 1 ] А, У ) * З }* D}. Важливим показником можливостей алгоритміки є проведений порівняльний аналіз алгебри алгоритміки з відомими алгебрами. Дамо короткі пояснення алгебри Дейкстри, Янова та ін. Алгебра Дейкстри АД = {АСС, L(2), СИГН} – двохосновна алгебра, елементами якої є множина САА операторів, зображених структурними блок- схемами, множина L(2) булевих функцій у сигнатурі СИГН, в яку входять операції диз’юнкції, кон’юнкції і суперечності, що набувають значення з L(2). За допомогою спеціально розроблених механізмів перетворення АД на алгебру алгоритміки встановлено зв'язок між альтернативою і циклом за формулою {[u] А} = ([u] Е, А * {[u] А}), що входить у СИГН. В АД використовуються похідні операції, які можуть бути отримані в наслідок суперпозиції основних операцій і констант. Операція фільтрації Ф (u) = {[u] Е, N}у АД зображена суперпозицією тотожного Е для невизначених N операторів і альтернативи в алгебрі алгоритміки, де N – фільтр дозволу виконання операцій обчислень. Оператор циклу while doтакож представлений суперпозицією операцій композиції і циклу в алгебрі алгоритміки. Алгебра схем Янова АЯ = {AHC, L(2)}; CИГН, де АНС – сукупність неструктурних схем, L(2) – сукупність різних булевих функцій, СИГН – сигнатура з композиції А*В і операція неструктурного переходу (u, F), а також операції Розділ 5 141 диз'юнкції, кон’юнкції і суперечності. АЯ містить у собі операції побудови неструктурних логічних схем програм. Схема Янова складається з предикатних символів множини P(p 1 , p 2 ,…,), операторних символів множини A{a 1 , a 2 ,…} і графа переходів. Оператор у даній алгебрі – це пари A{p}, що складається із символів множини А и предикатних символів p. Граф переходу – це орієнтований граф, у вершинах якого розміщуються перетворювачі, розпізнавачі й один оператор зупинки. Дуги графа задаються стрілками і позначаються знаками + і –. Дуги, що виходять з розпізнавача, розрізняються і називаються відповідно плюс-стрілка і мінус–стрілка. Перетворювач має одного нащадка, розпізнавач – двох. Одна вершина в графі переходу зветься вхідною і помічається вхідною стрілкою. Також є вершина зупинення, яка не має нащадків. Кожен розпізнавач містить у собі умови виконання схеми. Перетворювач обробляє оператори, що вміщають логічні змінні, що належать множині (p 1 , p 2 ,…) [31]. Кожна схема АЯ відзначається великою складністю, вимагає серйозного перетворення при переході до задання програми послідовністю дій, умов переходу і безумовного переходу. У праці [30] розроблена теорія інтерпретації схем Янова і доведено еквівалентність цих схем і операторних схем алгебри алгоритміки. Для зображення схеми Янова апаратом алгебри алгоритміки сигнатура операцій АЯ вводяться композиції А* В і операція умовного переходу, що залежно від умови u виконує перехід до наступних операторів або до оператора, позначеного міткою (типу goto). Умовний перехід трактується як бінарна операція (u, F), що залежить від умови u і розміток схеми F. Крім того, виконується заміна альтернативи і циклу типу while do. Внаслідок виконання бінарних операцій отримується нова схема F’, у якій встановлені бінарні операції (u) замість мітки і булевих операцій кон’юнкції і суперечності. Еквівалентність операцій перетворення доводить правильність переходу до неструктурного подання програм. Система алгебр Глушкова АГ= {ОП, УМ, СИГН}, де ОП – множина операторів, що входять у сигнатуру СИГН, і УМ – множина логічних умов, визначених на інформаційній множині ІМ. Сигнатура СИГН = {СИГНад Прогн.}, де СИГНад – сигнатура операцій Дейкстри, Прогн. – операція прогнозування. Сигнатура САА містить у собі операції алгебри АД, узагальнену тризначну булеву операцію і операцію прогнозування (ліве множення умови на оператор u = (А* u’) з породженням предиката u = УС такого, що u(m) = u’(м'), м' = А(m), А ОП). ИМ – множина оброблюваних даних за операціями з множин ОП і УС. Сутність операції прогнозування полягає в перевірці умови u у стані m оператора А і визначення умови u’, обчисленої в стані м' після виконання оператора А. Дана алгебра орієнтована на аналітичну форму подання алгоритмів і оптимізацію алгоритмів за вибраними критеріями. Алгебра алгоритміки і прикладні підалгебри. Алгебру алгоритміки розширено Г.О. Цейтліним дворівневою алгебраїчною системою і механізмами абстрактного опису даних (класами алгоритмів). Під багатоосновною алгоритмічною системою (БАС) розуміють систему S ={{D i i I }; СИГН 0 , СИГН n }, де D i – основи або сорти, СИГН 0 , СИГН n – сукупності операцій і предикатів, визначених на D i . Якщо вони порожні, то визначаються багатоосновні моделі – алгебри. Якщо сорти інтерпретуються як множина оброблюваних даних, то БАС є 142 Розділ 5 концепцію АТД у вигляді підалгебри, що широко використовується в об'єктному програмуванні. Тим самим установлено зв'язок із сучасними тенденціями розвитку програмування. Таким чином, можна зробити висновок, що проведене зіставлення механізмів алгебри Дейкстри, алгебри схем Янова та логічних операторів Глушкова проведено засобами алгоритміки Цейтліна. Це вказує на їх однакову алгоритмічну потужність при різних засобах подання алгоритмів програм. Практичним результатом досліджень алгебри алгоритміки є побудова оригінальних інструментальних систем проектування програм на основі сучасних засобів підтримки ООП (Rational Rose). Докладніше дана тема розглядається в [32]. Висновки. Проведений аналіз методів систематичного і теоретичного програмування свідчить про їх розвиток, удосконалювання, поповнення новими можливостям для застосування. Класичним прикладом є UML, завдяки якому ООП набув нових візуальних можливостей для проектування ПС. Теоретичні методи увібрали в себе не тільки можливості логічного, функціонального і процедурного програмування, а й алгебро-алгоритмічного апарата для абстрактного і формального представлення програм. Визначено сучасні тенденції розвитку мов опису DSL, інженерії ПС і предметних областей. Об’єднуючим ланцюгом у програмуванні є генерувальне програмування, що забезпечує генерацію членів сімейства предметної області з компонентів і ресурсів багаторазового використання, розроблених у різних середовищах за різними методами програмування (об’єктним, аспектним, компонентним і ін.). Дано загальну характеристику різних формальних теорій програмування, орієнтованих на абстрактне подання програм. Контрольні питання і завдання 1. Охарактеризуйте структурний метод програмування. 2. Наведіть основні особливості і можливості об’єктно-орієнтованого програмування. 3. Які діаграми є в мові UML для візуального проектування програм? 4. Наведіть основні типи компонентів і шляхи їхнього використання. 5. Назвіть базові поняття в компонентному програмуванні. 6. Визначте основні поняття й етапи життєвого циклу у компонентному програмуванні. 7. Визначте основні елементи аспектно-орієнтованого програмування. 8. Визначте основні елементи агентного програмування. 9. Визначте об'єкти генерувального програмування і наведить призначення. 10. Що таке простір проблем і простір рішень? 11. Наведіть теоретичні методи програмування. 12. Охарактеризуйте алгебраїчне програмування. 13. Що таке алгоритміка і її алгебра? 14. Покажіть сутність переходу до інших алгебр. |