НОУ ІНТУЇТ | лекція | Прикладні та теоретичні методи програмування

1. 5.2. теоретичне програмування Теоретичне програмування включає в себе формальні методи, засновані...

5.2. теоретичне програмування

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

Так, напрямок, пов'язаний з використанням математичного апарату для опису дій над об'єктами як алгебраїчні операції базових основ алгебри, отримало назву алгебраїчного програмування, алгоритміки і ін. Українські вчені розробили теоретичні напрямки програмування, зокрема:

• алгебраїчне, инсерционно програмування (Летичівський А.А. та ін.) [ 5.24 , 5.25 ];
• експлікатівное програмування (Редько В.Н.) і наука про програми (програмології), яка об'єднує логічний і математичний апарат для конструювання програм [ 5.26 - 5.28 ];
• алгебро-алгоритмічне програмування (Цейтлін Г.Є.), що об'єднує алгебраїчний апарат, теорію алгоритмів і операції над множинами [ 5.29 - 5.30 ]. Зупинимося на їхній короткій характеристиці.

5.2.1. Алгебраїчне, инсерционно програмування

Алгебраїчне програмування (АП) - це конструювання програм з алгебраїчними перетвореннями і функціями інтелектуальних агентів. В основі математичного апарату АП лежить алгебра мови дій АL (Action Language) і поняття транзитивної системи [ 5.24 , 5.25 ], В якості механізму визначення поведінки систем і механізмів її еквівалентності. Як понять в загальному випадку можуть бути компоненти, програми і їх специфікації, об'єкти, які взаємодіють один з одним і з середовищем їх існування.

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

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

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

Транзитивні системи називають бісімуляційно еквівалентними, якщо кожне стан еквівалентно станом іншої системи. На безлічі поводжень визначаються нові операції, які використовуються для побудови програм агентів. До них належать такі операції: послідовна композиція ( ) І паралельна композиція .

Середа Е, де знаходиться об'єкт, визначається як агент в алгебрі дій АL і функції занурення від двох аргументів . Перший аргумент - це поведінка середовища, другий - поведінка агента, який занурюється в цю середу з заданим станом. Значення функцій занурення - це новий стан однієї і тієї ж середовища. Базовим поняттям є "дія", яке трансформує стан агентів, поведінка яких, врешті-решт, змінюється.

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

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

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

Агенти розглядаються як значення транзитивних систем з точністю до бісіміляціонной еквівалентності, яка характеризується безперервною алгеброю з апроксимацією і двома операціями: недетермінованим вибором і префіксінгом. Середа вводиться як агент, в неї занурюється функція, яка має поведінка (агент і середа). Довільні безперервні функції можуть бути використані як функції занурення в ці функції. Трансформації поведінки середовища, які визначаються функціями занурення, складають новий тип еквівалентності - еквівалентність занурення.

Створення нових методів програмування з введенням агентів і середовищ дозволяє інтерпретувати елементи складних програм як самостійно взаємодіючі об'єкти.

В АП інтегрується процедурне, функціональне і логічне програмування, використовуються спеціальні структури даних - граф термів, який дозволяє використовувати різні засоби представлення даних і знань про ПрО у вигляді виразів багатоосновної алгебри даних.

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

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

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

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

Технологічна схема в АП

На наступному рівні опису програми знаходяться функції, які перетворять будь-Агентне вираз в AL-програму дій. Наприклад, функція розгортання функціональних виразів може бути представлена ​​у вигляді простих агентних виразів:

де - параметри агентних виразів.

Функція розгортання агентних функціональних виразів задає семантику AL-програми у вигляді програми функціонування агента в будь-якому середовищі. Якщо функція розгортання обробляється за кінцеве число кроків, то вона містить кінцеве вираз. Безліч всіх переходів, заключних і тупикових станів - перелічуваних, навіть якщо функція розгортання має безліч нетривіальних ітерацій. Станом транзитивної системи є обмежені вираження, що визначаються операцією вибору , співвідношенням і ставленням переходу з правилом .

Третій рівень програми - це функція розгортання занурень, що задаються в алгебрі дій. Ці функції визначаються на об'єктах середовища і агентів, тобто агентних виразах. Для коректності функцій занурення необхідно, щоб вона залежала тільки від поведінки агента і середовища і була безперервною функцією. Наступним кроком розробки програм є її реалізація в ЯП, наприклад в С ++, коли уточнюються типи даних і параметри. Потім проводиться верифікація отриманої програми для перевірки правильності виконання її поведінки в заданій моделі. Більш докладно про инсерционно програмуванні та засобах його автоматизації в [ 5.25 ].