2. Процедурне програмування

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

Для представлення даних викори­стовуються стани пам’яті. Змінні або імена можуть бути типізова­ними або ніі, а їх значення беруться з областей даних, які визнача­ються як абстрактні або конкретні типи.

Алгоритми в процедурних мовах програмування представляю­ться як композиції операторів присвоювання, що змінюють стани пам’яті. В процесі розвитку процедурної парадигми ще в 60-70-х роках з’ясувалось, що всі різновиди композицій зрештою зводяться до чотирьох основних: присвоювання, послідовної композиції, умов­ного оператора та умовного циклу. Це призвело до відкриття Глушковим В. М. алгебри алгоритмів, яка лягла в основу структурно­го програмування. Кожна процедурна програма визначає деяке часткове перетворення на множині станів пам’яті.

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

Розглянемо коротко семантичні проблеми для процедурних (імперативних) програм.

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

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

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

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

• (х := у) - присвоювання,

• (Р; 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.

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

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

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