Редукційні аспекти композиційної технології програмування

Композиційне програмування як уточнення поняття програмування базується на деяких загальних і спеціальних принципах. Відповідно до них процес конструювання програм здійснюється у декілька етапів.

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

· Конструювання програми на семантичному рівні (семантичне конструювання програми).

· Конструювання програми на синтаксичному рівні (синтаксичне оформлення програми).

Згідно з принципом функціональності як сама програма, пік і ті, взагалі кажучи, більш прості програми, з яких вона конструюється, у математико-семантичному плані являють собою функції. Як показують приклади, адекватне уточнення програм для однієї й тієї ж 1здзчі може привести до функцій різних типів. Звідси випливає, ЩО етап семантичного конструювання програми, у свою чергу, розбивається на два етапи. Перший із них зводиться до з'ясування питання про те, в якому класі функціональних структур припустиме синтезування програми. На цьому етапі має з'явитися іменна функція, що уточнює програму, а також базові функції,. що уточнюють ті більш прості програми, з яких конструюється потрібна програма. Діставши таку функцію, переходять до другого етапу семантично го конструювання програми. Цей етап відповідає принципу композиційності. Його результат - композиційна структура програми - являє собою зображення іменної функції, яка уточнює програму, у вигляді композицій базових функцій. Іншими словами, йдеться про діставання композиційної (семантичної) структури програми з базових функцій застосуванням до них так званих керуючих структур, які уточнюються як композиції.

Таким чином, конструювання програми на семантичному рівні виконується у два етапи:

· Розробка функціональної структури програми.

· Розробка композиційної (семантичної) структури програми.

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

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

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

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

1. постановка задачі;

2. аналіз задачі;

3. знаходження характеристичної властивості задачі, точніше, функції, до обчислення якої зводиться задача;

4. знаходження функціональної структури програми;

5. розробка композиuійної (семантичної) структури програми;

6. синтаксичне оформлення програми;

7. апробування програми.

Розглянемо застосування композиційної технології програмування до конструювання програм у сучасних мовах програмування на дуже простому прикладі.

Приклад. Написати програму обчислення суми

(1)

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

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

2. Аналіз задачі. Запишемо суму, яку необхідно обчислити, у розгорнутому вигляді

Як відомо, справедлива така рівність:

Тоді задача обчислення значення зводиться до задачі обчислення послідовності , де .

Ця послідовність може задаватись рекурентним співвідношенням:

,

де послідовність , у свою чергу, задається рекурентним співвідношенням

.

3. Характеристична властивість задачі. На цьому етапі виокремлюється така властивість задачі, точніше, функції, до обчислення якої зводиться задача, що "підказує" правильний вибір керуючих структур (композицій) у процесі конструювання програми, а саме при розробці композиційної структури програми.

Як випливає з аналізу задачі, функція f(n) має таку властивість: їїзначення для будь-якого натурального числа n збігається з членом першої з системи двох послідовностей

,
що визначається системою двох рекурентних співвідношень

(2)
та початковими значеннями . При цьому виконується умова

(3)

Цю властивість функції f(n) візьмемо за характеристичну для розробки програми обчислення її значень.

4. Функціональна структура програми. Згідно з композиційною технологією програмування, знайдемо функціональну структуру програми, для чого звернемося до характеристичної властивості функції f(n). Відповідно при обчисленні конкретного значення s цієї функції для деякого конкретного значення її аргументу n обчислюються члени послідовностей та . Відведемо для n комірку пам'яті з адресою N, а для членів вказаних послідовностей – відповідно комірки з адресами І та S. Тоді задачі обчислення значення s функції f(n) природно зіставити дію Р, яка одноелементну сукупність станів комірок пам'яті { (N,n) } перетворює в одноелементну сукупність станів комірок пам'яті { (S,s) }, де

,
таке, що дія типу умови (предикат) сукупності станів комірок пам'яті зіставляє значення false, якщо j=n, та значення true для всіх . Ця дія може бути уточнена як (D, W)-іменна функція яка іменніймножині {(N,n)} зіставляє іменну множину {(S,s)}.

Таким чином, функціональна структура програми задається (D,W)-іменною функцією

, де .

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

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

1. Аплікація (послідовне виконання), що позначається «;».

2. Розгалуження у повній та короткій формах відповідно: if_then_else та if_then.

3. Циклування двох видів – з попередньою та пост-умовами відповідно: while_do та repiat_until.

Для того, щоб розкласти іменну функцію F, яка зіставлена задачі обчислення на первинні або базові функції, використовуючи придатні керуючі структури (композиціі), звернемося до характеристичної властивості функції f(n). Її аналіз показує, що при розкладанні імейної функціі F має використовуватися одна з керуючих структур (композицій) типу циклування, наприклад, while_do.

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

while Р do (I:=I+ 1; S:=S+ ).

Легко зрозуміти, що за Р можна обрати іменний предикат . Це випливає з характеристичної властивості функції f(n), а саме з (3). Тоді, враховуючи ту частину характеристичної властивості функції f(n), яка пов'язана із початковими значеннями , можемо отримати семантичну (композиційну) структуру програми обчислення значень функції f(n):

F=

I:=1;

S:=l;

while do (I:=I+ 1; S:=S+ ).

6. Синтаксичне оформлення програми. Передбачає її запис у відповідній мові програмування. Один із можливих варіантів запису семантичної (композиційної) структури програми обчислення суми (1) у мові Паскаль матиме такий вигляд:

prograт SUM (inpиt, oиtpиt);

var І, N: integer;

S: rеаl;

begin

read (N);

I:=1; S:=l;

while do

begin

I:=I+ 1;

S:=S+

end;

writeln(S)

eпd.

7. Апробування програми. Програма призначена для розв'язання не однієї конкретної задачі. а цілого, як правило, нескінченного, класу однотипних задач і описує нескінченну множину обчислювальних процесів. Один від одного процеси відрізняються значеннями змінних, і зокрема початковими значеннями або аргументами. Однак виникає питання: яким чином можна переконатися, що у будь-якому з процесів, які можна виконати відповідно до заданої програми, будуть отримані правильні результати? Це питання правильності (коректності) програм є одним із самих основних, вирішальних і неминучих питань програмування.

Частіше за все правильність програми встановлюється методом тестування, або апробування програми. Він полягає у виконанні програми для деяких припустимих даних і порівнянні отриманих результатів із раніше відомими правильними результатами для цих вхідних даних. Останні можуть бути отримані різними способами: аналітично, з таблиць, підрахунком і т.д. Конкретний спосіб обирається залежно від задачі. Цей традиційний спосіб дорогий, обтяжливий і пов'язаний із великими витратами часу. Але, окрім цього, він незадовільний ще й тому, що розсіяти всі сумніви щодо коректності програми можна лише тоді, коли виконаються всі можливі асоційовані з програмою обчислювальні процеси, а не лише деякі відібрані варіанти. Однак таке вичерпне тестування програми принципово не можливе. Тому апробування програми може слугувати лише для доведення наявності помилок, але ніколи не гарантує їх відсутності. Іншими словами, апробування програми розв’язує питання лише часткової коректності програми. Таким чином, необхідно абстрагуватися від індивідуальних процесів та визначити деякі загальнозначимі умови, які можна вивести з характеру поведінки. Тут слово "загальнозначимий" слід розуміти як "припустимі для кожного процесу, що відповідає програмі". Цей аналітичний метод перевірки називається верифікацією програм. На відміну від тестування програм, де досліджуються властивості індивідуальних процесів, верифікація має справу з властивостями самої програми. Для доведення повної правильності програми (її коректності) застосовують відповідні математичні методи.

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

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

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

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

Оскільки процес композиційного програмування розділяється на етапи семантичного конструювання і синтаксичного оформлення програми, причому останній може здійснюватися автоматично (!), обмежимося далі конструюванням програм лише на семантичному рівні.

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