Зубенко, Омельчук - Програмування. Поглиблений курс

Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ

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

Етап проектування полягає у:

•виборі згідно з вимогами вхідної специфікації системи структури

йелементної бази апаратної частини системи та її ПЗ;

•виборі функцiй кодування й декодування;

•розробці архітектури системи – декомпозиції її на підсистеми, уста- новлення взаємозв'язків між ними й визначення структури керування;

•деталізації семантичної структури підсистем, розбитті їх на моду- лі, окремі функції тощо.

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

На етапі кодування результати проектування трансформуються в конструкції мови (мов) програмування.

Обґрунтування правильності інформаційної системи (ОПС) поля-

гає в перевірці того, що, по-перше, отримана вихідна система є узгодже- ною (коректною), тобто дійсно реалізує запити вхідної системи згідно з аналізом задачі відносно вибраних функцій кодування й декодування і, по-друге, вона задовольняє всі прагматичні вимоги. Обґрунтування коре- ктностi може здійснюватись як інженерними, так і математичними ме- тодами. Інженерні методи базуються на тестуванні систем. Спочатку тестуються окремі функції й модулі, а потім здійснюється комплексне те- стування всієї системи. Тестування програми (функції) P полягає у про- веденнi контрольних обчислень за програмою на окремих спецiально підiбраних варiантах вхiдних даних (тестах) з метою виявлення можли- вих дефектів і помилок в її роботі. Пiсля кожного контрольного обчислен- ня результати порівнюють із тими, що мають відповідати запитам, тобто для кожного тесту a й кожного запиту Φ вхідної системи перевіряють

умову (*) узгодженості запиту та його реалізації в системі (див. підрозд. 2.1.3). Якщо знайдено невiдповiднiсть, то шукають помилку в програмі й

141

ПРОГРАМУВАННЯ

намагаються її усунути. Цей процес називається налагодженням (англ. – debugging) програми (рис. 2.2). Тестування й налагодження є своєрідним мистецтвом. Воно полягає в умiннi пiдiбрати тести так, щоб мiнiмiзувати наявні ресурси (матеріальні й часові) для виявлення й усунення можли- вих помилок ("ляпів") у програмi. На жаль, на практиці катастрофічний дефіцит ресурсів не дозволяє за допомогою тестування повністю розв'я- зати проблему обґрунтування коректності системи.

Аналіз задач

Проектування програмної моделі

Кодування

Обґрунтування

правильності

системи

Математичні методи

Інженерні методи

Верифікація програми

Тестування й налагодження

Трансформаційний підхід

Документація

Експлуатація

Рис. 2.2

142

Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ

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

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

Історично перший підхід виник у серединi 70-х рр. XX ст. і базува- вся на математичній верифiкацiї програм. За допомогою верифiкацiї намагалися математично довести коректнiсть програми в межах пев- ної математичної системи. Для цього було розроблено спеціальні ма- тематичні методи формального подання семантики програм і відпо- відні логічні засоби для роботи з ними. Отримані результати набули широкого розголосу в науковій спільноті та знайшли відображення в літературі, насамперед у роботах Т. Хоара, Е. Дейкстри, Д. Гріса та інших спеціалістів (див. літературу для СР). Експерименти з конкрет- ними програмами показали, що математичні доведення коректностi програм є реальними. Однак у бiльшостi випадкiв цi доведення до- сить складнi й самі потребують великих людських і матеріальних ре- сурсів. Текстуально вони займають (принаймні на сьогодні) набагато бiльший обсяг, нiж програми. У зв'язку із цим виникає нова проблема

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

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

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

143

ПРОГРАМУВАННЯ

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

них правил Tp1 будується її модель S1 . За S1 за допомогою спеціаль- них трансформацій Tp2 отримують її модель S2 тощо. Будується лан-

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

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

Чи задовольняє вихідна система прагматичні вимоги, з'ясовують під час атестації, а також шляхом аналізу її семантичної структури.

Етап документування полягає в підготовці внутрішньої програм- ної документації відповідно до вимог ТЗ. Існують певні міжнародні й національні стандарти на таку документацію. У сучасних технологіях програмування на цьому етапі використовують спеціальні системи –

генератори звітів.

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

144

Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ

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

У цілому, як видно з рис. 2.2, ЖЦ має циклічну природу. Для пове- рнення назад до одного або кількох попередніх етапів може бути ба- гато причин. Це і виявлені на етапах обґрунтування коректності або експлуатації помилки чи недоліки в роботі системи (найчастіше), і зміни Замовником вимог до системи тощо.

2.2.2. ДЕЯКІ МЕТОДОЛОГІЧНІ ПРИНЦИПИ ПРОГРАМУВАННЯ

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

ку розглянемо загальні принципи.

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

Прагматика Семантика Синтаксис

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

Принцип відокремлення. Фiксує вiдносну самостiйнiсть основних аспектiв програм, тобто синтаксису, семантики й прагматики. Оскiльки реальні програми як об'єкти дуже складнi, то на практицi кожен з аспектiв може розглядатися окремо із застосуванням своїх дескриптологічних засобів. Для прагматики використовують звичай- ну мову та ПЧП; для семантики – спецiальнi мови специфікацій, граф-схеми, різні діаграми тощо; для синтаксису – формальні грама-

145

ПРОГРАМУВАННЯ

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

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

Принцип декомпозиції, або "розділяй і володарюй". Оберне- ний до нього принцип "знизу-вгору". Згідно з принципом декомпо-

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

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

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

146

Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ

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

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

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

Спеціальних принципів може бути багато – вони визначають специфіку парадигм програмування й пов'язаних із ними технологій. Наведемо для прикладу тільки два таких принципи.

Принцип функціональності. Кожна мова програмування описує певний фіксований клас інформаційних об'єктів і множину запитів про них. Основні конструкції мов програмування – дані та програми. Дани- ми називаються конструкції, які подають у них інформаційні об'єкти, а програмами – конструкції, що подають запити. Запити можуть бути де- кларативними й процедурними. У першому випадку вони мають вигляд певних формул-декларацій, що описують зв'язок між вхідними й вихід- ними даними, у другому – алгоритмів, що описують процедуру пошуку результатів запиту. В обох випадках програма задає відповідність, яка пов'язує вхідні дані й результати обчислень за нею (графік програми). Принцип функціональності вказує на важливість графіків програм і ал- горитмів у процесі побудови програмних моделей систем та їхньої аксі- оматизації. Ці графіки можуть розглядатись окремо від програми й за- даватись довiльними прийнятними засобами, у тому числі й непроцеду- рними (табличними, аналітичними або алгебраїчними за допомогою рі- внянь). Цей принцип лежить в основі функціонального програмування, рівень абстракції якого – теоретико-множинний.

Принцип композиційності. Програма як певна функція ( X −Y -

оператор) має певну внутрiшню структуру, елементами якої є інтер-

147

ПРОГРАМУВАННЯ

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

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

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

Принцип композиційності лежить в основі композиційного програмування.

*Література для CР: ЖЦ і його основні етапи – [49, 67, 68, 72, 88, 120]; доказове програмування – [27, 31, 52]; верифікація програм – [4, 52, 76, 92, 138, 145]; трансформаційне програмування – [88, 139]; композиційне програмування – [108]; методологія програмування – [68, 91, 93, 109]

Контрольні запитання та вправи

1.З яких етапів складається ЖЦ?

2.Що таке технологія програмування?

3.У чому полягає суть етапу аналізу систем?

4.Що таке зовнішня специфікація й технiчне завдання системи?

5.Хто такі Замовник і Розробник?

6.У чому полягає етап проектування?

7.Що таке програмний код системи?

8.У чому полягає різниця між правильністю й коректністю ін- формаційної системи?

9.Що таке тестування й налагодження програм?

10.Що таке повна система тестів?

11.Що таке верифікація систем?

12.Що таке генератор звітів?

13.Що таке атестація системи?

14.У чому полягає експлуатація системи?

15.Яка причина циклічності ЖЦ інформаційних систем?

148

Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ

16.Що таке принцип підпорядкування? Пояснити на прикладах.

17.У чому полягає принцип відокремлення? Пояснити на при- кладах.

18.Що таке декомпозиція систем?

19.Сформулюйте принцип типізації. Проілюструйте його на прикладі будь-якої мови програмування.

20.У чому полягає принцип функціональності програм?

21.Сформулюйте принцип композиційності програм.

22.Проілюструйте на прикладах зі своєї практики програму- вання застосування принципів: а) підпорядкування; б) ві- докремлення; в) декомпозиції; г) типізації; д) функціональ- ності; е) композиційності; є) абстракції.

23.Дайте визначення типу змінної.

24.Що таке алгебра типу?

25.Що таке конструктор типу?

26.Що таке похідний тип?

27.Що таке вежа типів мови програмування?

28.Що таке композиція програм?

29.Що таке імперативна логіка програм?

2.3.Обчислювальні системи

¾Структура комп'ютера

¾Структура й функції операційних систем

¾Машинні типи даних

¾Навчальна машина

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

Розглянемо детальніше структуру й функції ОбС на прикладі пер- сонального комп'ютера та його програмного забезпечення.

149

ПРОГРАМУВАННЯ

2.3.1. СТРУКТУРА КОМП'ЮТЕРА

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

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

Найменша одиниця даних – біт – набуває одного з двох значень – 0 або 1. Елемент даних, що зберігається в комірці, називається байт і складається з восьми бітів. Ділянки ОП, в яких розміщуються машинні програми й дані, називаються полями. Поля – це неперервні ділянки пам'яті, тому для визначення поля достатньо вказати адресу його пер- шої комірки й довжину – загальну кількість комірок. Стандартним по- лем ОП є машинне слово – поле, в якому зберігається більшість ма- шинних команд. Зазвичай воно складається з двох байтів і адреса його кратна 2, але може бути й більшим, наприклад, довжиною 4.

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

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

150