2.8. Парадигми теоретичного програмування

Разом з парадигмами прикладного програмування ПС продовжують розвиватися і теоретичне програмування, основано на фундаментальних дослідженнях, математичних теоріях і дисциплінах (логіка, алгебра, комбінаторика). Завдяки цьому забезпечується математичний аналіз й осмислення деяких завдань програмування, а також їх опису з використанням математичної символіки, відсутньої в прикладних МП. Правильність математичного аналізу треба доводити автоматизованими засобами, які розпізнають символи і забезпечують зіставлення з символікою базової мови для одержання необхідних результатів на комп'ютері.

Авторами української теоретичної школи програмування, створеної В.М. Глушковим, запропоновані нові парадигми, а саме:

– алгебраїчне та інсерційне програмування (А.А.Летичевський і ін.) [24–26];

– експлікативне та номінативне програмування (В.Н.Редько, М.С.Нікітченко), які використовують логічний і математичний апарат для абстрактного конструювання програм [27–29];

– алгебро-алгоритмічне програмування (Г.О. Цейтлін), що поєднує алгебраїчний апарат і теорію алгоритмів [30–31].

Розглянемо ці напрями детальніше.

2.8.1 Алгебраїчне та інсерційне програмування

Парадигма алгебраїчного програмування – АП [24, 25] ґрунтується на теорії переписування термів. У цій парадигмі терми представляють дані, а системи переписуючих правил, що подаються за допомогою системи рівностей, – алгоритми обчислень. Елементарний крок обчислення містить у собі включає зіставлення із зразком, перевірку умов і підстановку. Порядок вибору переписуючих правил і підтермів даного терму для зіставлення з лівими частинами рівності визначається стратегією переписування. По суті, стратегія визначає результат обчислень – терм з точністю до еквівалентності початковому терму. Власне стратегія переписування може бути описана в парадигмі більш низького рівня, наприклад, процедурній або функціональній, що зумовлює інтеграцію парадигм. На теперішній час ідея інтеграції парадигм (процедурної, функціональної, алгебраїчної і логічної) знайшла втілення в системі алгебраїчного програмування (APS) [25], в якій використовуються спеціалізовані структури даних – графові терми – для представлення даних і знань про предметні області.

Основою АП є математична модель, що вміщує такі поняття:

• агент як транзитивна система, наділена поведінкою;

• поведінка агентів задається мовою АL (Action Language) за допомогою операцій, констант, граничних умов і рекурсій;

• середовище, яке складається з множини агентів і функцій занурення в нього, що позначається env і має параметром стан середовища й агентні вирази;

• правила розгортання функціональних виразів у прості агентні вирази;

• транзитивна система, як композиція середовища й системи взаємодіючих агентів, занурених у це середовище.

Мова дій АL, як і будь-яка інша мова, має синтаксис і семантику. Синтаксис мови задає правила опису дій, семантика – функцій, які визначаються засобами й виразами мови й ставлять у відповідність заданим виразам значення в деякій семантичній області. Різні семантичні функції можуть давати рівні абстракції й властивості програм. Семантика може бути обчислювальна й інтерактивна. Кожна алгебра дій – це гомоморфний образ алгебри примітивних дій, коли всі складові різні, а їхнє подання однозначне з точністю до асоціативності й комутативності при детермінованому виборі.

Розширення поняття транзитивної системи – це множина заключних станів, що відповідають успішному завершенню функціонування системи і відсутності невизначених станів. Головний інваріант стану транзитивної системи – поведінка системи, що задається виразами алгебри поведінки F(A) на множині операцій алгебри дій – префікси a u, недетермінований вибір u + v з u і v поведінкою та властивостями асоціативності й комутативності. Скінченна поведінка системи задається константами , , 0, які позначають відповідно: стан успішного завершення, невизначеного й тупикового. Алгебра поведінки містить у собі відношення , елемент  як найменший, і операції поведінки, які монотонні.

Усяка транзитивна система має історію функціонування, яка зберігає зокрема один з таких станів: успішне завершення обчислень у середовищі транзитивної системи; «тупиковий» стан, коли кожна з паралельно виконаних частин системи перебуває у стані очікування; та невизначений стан, що виникає при виконанні алгоритму з нескінченними циклами.

Алгебраїчне програмування зосереджує увагу на проблемах інтелектуалізації і поведінки агентів у розподіленому середовищі, куди вони занурюються. Це програмування поступово перейшло в інсерційне програмування шляхом вставки, занурення агентів у різноманіття середовищ для перетворення поведінок агентів на основі відповідної моделі, що відповідає розміченій транзитивній системі й бісимуляційній еквівалентності [25]. Дане програмування узагальнює алгебраїчне перетворення множини станів інформаційного середовища на поведінку об'єктів.

Отож, інсерційне програмування узагальнює погляд на програму, як на алгебраїчно визначене перетворення множини станів інформаційного середовища, проте замість пасивного середовища (пам'яті) розглядається активне інформаційне середовище, що має спостережувану поведінку [26]. Зміна поведінки цього середовища відбувається внаслідок дії на його об'єкти взаємодіючих агентів. В основі інсерційного програмування – модель поведінки агентів в середовищах, що базується на поняттях транзиційної системи (основного стандарту в поведінковій теорії взаємодіючих процесів) і відношення бісимуляційної еквівалентності агентів щодо до середовища (стан агента ототожнюється з його поведінкою). На відміну від агентного програмування, що концентрує увагу, більшою мірою, на проблемах інтелектуалізації агентів, инсерційне програмування охоплює поведінкові аспекти агентів.

Термін «інерційне програмування» походить від англійського insert – вставляти, поміщати, занурювати. Програма в цій парадигмі розглядається як агент, наділений поведінкою, що, занурюючись в середовище, змінює його (середовища) поведінку і має зовнішнього спостерігача, а також інших агентів, що занурюються у це середовище надалі. Написати інсерційну програму – означає визначити функцію занурення (закон функціонування середовища із зануреними в нього агентами), а також початковий стан середовища і агента, зануреного в це середовище. Як базова система програмування для подання станів агентів і середовищ у вигляді структур даних, а також для програмування функції занурення використовується система алгебраїчного програмування АPS. Інерційна програма записується мовою AL за наступними рівнями [26]:

1. опис поведінки ініціалізованого багаторівневого середовища із зануреними в нього агентами;

2. задання функції, яка визначає відношення переходів агентів;

3. опис ядра функції занурення (функції розгортання занурень).

Інсерційними програмами моделюються реальні системи з недетермінованою поведінкою агентів і середовищ. Реалізація систем інерційного програмування вимагає застосування програм-симуляторів, а не інтерпретаторів, а також постановки цілей для отримання конкретних результатів.

Перший рівень виражається через паралельну композицію агентів з однією областю дій і відповідною комбінацією дій. Інші рівні виражаються через функцію занурення агента в деяке середовище, результат трансформації – нове середовище.

Головна діюча особа інсерційного програмування – агент, що наділений поведінкою, і занурюючись у середовище, змінює його. Характерною рисою є недетермінована поведінка агентів і середовищ, як це відбувається в реальних системах. При цьому програма агента вимагає не інтерпретації, а моделювання, оскільки вона зображаються транзитивною системою у вигляді композиції середовища й системи взаємодіючих агентів, занурених у це середовище.

Схема розробки об’єктів та середовища і опису функцій занурення включає: програму з набіру параметрів і початкових агентних виразів. Параметри можуть бути фіксовані й змінні, що змінюються при переході від одного середовища до іншого. Особливо це стосується параметрів розгортання.

Множина всіх переходів, заключних і «тупикових» станів – перелічувана, навіть якщо функція розгортання має нескінченну множину нетривіальних ітерацій.

Станом транзитивної системи є обмежені вирази, обумовлені операцією вибору +, співвідношенням x + 0 = a і відношенням переходу з одного стану в інший за правилом u → U(u).

Функція розгортання занурень задається на об'єктах середовища й агентів, тобто на агентних виразах. Для коректності функції занурення необхідно, щоб вона залежала тільки від поведінки агента й середовища і була неперервною функцією. Наступним кроком розроблення програм є її реалізація в МП, наприклад у С++, коли уточнюються типи даних і параметри. Потім проводиться верифікація отриманої програми для перевірки правильності її поведінки в заданій моделі.

Більш докладна про інсерційне програмування у [25].