Абстрактна семантика процедурних програм.

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

Побудова синтаксису мови програмування і синтаксично пра­вильного слова (програми Р) в цій мові на сьогодні не складає ве­ликої проблеми. А от побудова семантично правильної програми - це одна з основних (якщо не основна) проблема при проектуванні програмної системи. Складність цієї проблеми полягає в тому, що обґрунтування семантики тієї чи іншої мови програмування - це, як правило, вимагає розв’язання не однієї, а декількох складних ма­тематичних задач, в зв’язку з можливими інтеграціями парадигм. Дослідження самих парадигм програмування і їх об’єктів дає мо­жливість описати для деяких з них абстрактну семантику, тобто описати семантику незалежно від конкретної мови програмування.

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

• (х:= у) - присвоювання,
• (Р; Q) - послідовна композиція,
• if(u, Р, Q) - умовна композиція,
• while(u, Р) - умовний цикл або ітерація.

Виходячи з цього, абстрактний синтаксис процедурної програ­ми можна записати в нормальній формі Бекуса так:

 

< program >::=< operational-expression >;

< operational-expression >::= < operator > | < operational-expression >;

< operator >::= < assign > | < sequentional-composition > |

< conditional-composition > | < iteration >;

< assign >::= < variable >:= < expression >;

< variable >::= < element-from-setvariables R >;

< expression >::= < term-of-algebra TD(R) >;

< sequential-composition >::= (< operator >; < operational-expression >);

< conditional-composition >::= if(< condition >,< operational-expression >,

< operational-expression >);

< iteration >::= while(< condition >, < operational-expression >);

< condition >::= < propositional-boolean-function-on (R) >.

 

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

Семантика програм, незалежно від їх парадигм, має два різновиди: денотаційна семантика і операційна семантика. Як ми вже зазначали цей поділ ґрунтується на тому, що при виконанні будь-якої програ­ми необхідно вміти відповідати на такі два питання:

а) що обчислювати? і б) як обчислювати?

Відповідь на перше питання повинна давати денотаційна семантика, а відповідь на друге - операційна.

Денотаційна семантика.

Нехай задані

• область даних D, де визначені операції сигнатури Ω і елементарні предикати сигнатури П;
• множина імен R.

 

Множину всіх відображень В з множини R в область даних В позначимо через B= і будемо називати множиною станів пам’яті або інформаційним середовищем.

З даною програмою Р зв’яжемо часткову функцію : В → B, яка повинна обчислюватись цією програмою. Значення функції (b) на стані пам’яті b Є В будемо позначати через (b).

Визначимо:

а) семантику виразів:: : В → D, де у - вираз;

б) семантику імен виразів:: : В → R, де х - змінна;

в) семантику умов:: : В → {0,1}, де и - умова.

Виходячи з цього означення і абстрактного синтаксису, денотаційну семантику процедурних програм можна визначити так:

1) P = (x:= y) (b)(r) = (b,r) = (if( (b) = r,

2) P = ( )) (b) = ( ;

3) P = if(u, (b) = (if( );

4) P = while(u,Q) (b) = (b)),

де n - найменше натуральне число такe, що для всіх 0 ≤ т < n мають місце умови Більш лаконічно цe можна записати у вигляді рекурсивного означення:

(b) = if( = 0, b, ).

 

Операційна семантика

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

Пару (Р,b), де Р - програма, a b - стан пам’яті, називатимемо станом обчислень. Серед станів обчислень виділимо стан (succ, b) для фіксації успішного завершення обчислень програмою, тобто стан (succ,b) є заключним станом обчислень.

Бінарне відношення переходів → на станах обчислень позначається через (P, b) → (Р', b') і знаходиться за такими правилами:

а ) (x:=y,b) →(succ, );

;

в ) , де

г ) ;

д ) ;

e ) ;

є ) .

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

(P,b) () () …

Ця історія може бути як скінченна, так і нескінченна. Якщо історія скінченна, то її останнім етапом є стан (sucс, b), а стан пам’яті b Є В називається результатом виконання програми Р.

Нехай відношення * означає рефлексивно-транзитивне замикання відношення переходів , тобто s * s' ⇔ 1)s = s' або 2)s s' або 3)s s" * s'.

При цьому кожний стан обчислень породжує єдину історію обчислень.

Тепер виникає питання, як пов’язані між собою денотаційна і операційна семантики? Відповідь на це питання дає таке твердження.

Теорема 3.1. (b) = b' ⇔ (P,b) * (succ, b').

 

Доведення виконується методом математичної індукції з розглядом можливих варіантів обчислення функції (b) (пункти 1) - 4)) і відношення * (пункти а) - g)).

Розглянемо приклад процедурної програми.

Програма обчислення найбільшого спільного дільника двох
натуральних чисел (НСД).

Процедурна програма, як і функціональна, алгебраїчна і логічна програми обчислення НСД(х, у), де х, у - цілі натуральні числа, ґрунтується па таких властивостях цієї функції.

1. НСД(х,х) = х;

2. х>у ⇒НСД(х, у) =НСД(х -у,у);

3. х < у ⇒ НСД(х, у) =НСД(х, у - х).

 

Імперативна програма має такий вигляд:

 

НСД(х ,у).

Вхід: х, у Є N.

Вихід: d Є N.

begin

а:= х;

b:= у;

while а ≠ b do

if а > b then а:= а - b else b:= b - a; fi;

od;

d:= а;

End

 

Структурність і модульність

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

C КВАДРАТНИЙ КОРІНЬ З ДІЙСНОГО ЧИСЛА

REAL FUCTION ROOT (A)

S=A

IF (A.EQ.0) GO TO 20

10 T=(S+A/S)*.5

IF (ABS((T-S)/T).LE.1.Е-6) GO TO 20

S=T

GO TO 10

20 ROOT=S

END

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

function

root(a:real,eps:real): real;

var s, t: real;

begin

s:=a*0.5;

repeat

t:=s;

s:=(s+a/s)*O.5;

until abs(s-t)/s<eps do

root:=s;

end

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

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

Модульне програмування

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

Поняття модуля як абстракції даних було вперше запропоноване Парнасом у 1972 році, правда на той час уже існувала мова програмування Симула 67, в якій використовувалася парадигма об’єктів. У найбільш повному виді поняття абстракції даних було реалізоване в мові програмування Модула-2.

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

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

Цей же квадратний корінь можна знайти у відповідному рядку чотиризначних математичних таблиць Брадіса. У першому випадку вся складність зосереджена в алгоритмі, який необхідно було придумати і запрограмувати (що ми й зробили у наведеному вище прикладі програми на Паскалі). У другому — в структурах даних, тобто в таблицях, які професор В.М.Брадіс повинен був попередньо розрахувати.

Ось приклад тексту в Модулі 2, який дає певне уявлення про поділ модуля на дві частини — визначення і реалізацію:

definition module Months;

type Month=

(jan, feb, mch, apr, may, jun,

jul, aug, sep, oct, nov, dec);

 

procedure length(m: Month): Cardinal;

end Month;

 

implementation module Month;

var

len: array Month of Cardinal;

procedure length(m: Month): Cardinal;

begin

return len[m];

end length;

 

begin

len[jan]:=31; len[feb]:=28;

len[mch]:=31; len[apr]:=30;

len[may]:=31; len[jun]:=30;

len[jul]:=31; len[aug]:=31;

len[sep]:=30; len[oct]:=31;

len[nov]:=30; len[dec]:=31;

end Month.