1. Природа динамічних об'єктів і способи їх реалізації.
Всі об'єкти, що представляють дані в програмі і які розглядали дотепер, були статичні в тому сенсі, що всі їхні параметри, розміри були відомі до виконання програми. Отже, ресурси для них можна було заздалегідь спланувати і виділити.
Існують задачі, для яких характерна наявність даних: - фактичне поява яких можливе, але не обов'язково; - час життя цих об'єктів менше часу виконання програми. Такі об'єкти називають динамічними об'єктами.
Наприклад, якщо нам треба вибрати з вхідного потоку даних, сукупності даних, що володіють певними властивостями. Зустрінемо чи ні ми такі сукупності це питання. Тому виділення ресурсів для їх зберігання заздалегідь навряд чи розумно. Більш того ми не знаємо як велика буде така сукупність. Потім, якщо зібрану сукупність ми повинні передати по лініях зв'язку, наприклад, на іншу машину, то в нашій програмі логічно було б ресурси, займані переданої сукупністю, звільнити для інших потреб. (Ресурсів не вистачає завжди - це закон.)
Для роботи зі статичними об'єктами в мовах програмування використовується добре відомий механізм імен. Pascal тут не виняток. Однак, цей механізм навряд чи нам підходить для подання та маніпуляції динамічними об'єктами. Справа в тому, що ім'я повинно побут відомо до виконання програми - це по-перше. По друге, породження всякого іменованого об'єкта пов'язано з виділенням пам'яті. Раз об'єкти виникають динамічно, то заздалегідь ми не знаємо скільки їх буде. Отже не можемо заздалегідь виділити (породити, написати, придумати) потрібну кількість імен. Далі, не ясно чому відповідає в пам'яті ім'я не існуючого об'єкта. Коли об'єкт став не потрібен ми не можемо знищити ім'я. Немає таких коштів у мові. З іншого боку, вже при написанні програми нам треба якось описувати дії над динамічними об'єктами.
Для вирішення цієї проблеми в програмуванні був запропонований механізм посилань. Ідея його полягає в тому, що динамічні об'єкти представлені не явно, а через деяку статичну змінну, яка вказує на місце розташування динамічного об'єкта, якщо він існує, або містить спеціальне значення - об'єкт відсутня. Що значить вказує? Це значить що її значення - "ім'я" динамічного об'єкта. Це спеціальне ім'я, зване посиланням (саму змінну, при цьому, часто називають покажчиком) і яке вказує де розміщується, як знайти об'єкт і отримати доступ до значення.
У разі Pascal такими ім'ям є адресу в пам'яті де розміщується динамічний об'єкт. Кожен раз, коли породжується динамічний об'єкт йому виділяється місце в пам'яті. Адреса початку виділеної області пам'яті покладається в якості значення посилальної змінної, представляє динамічний об'єкт. При знищенні динамічного об'єкта займана ним пам'ять вважається вільною, а відповідна посилальна змінна приймає спеціальне значення - немає об'єкта. Всі дії над динамічними об'єктами в програмі описуються як дії над значеннями посилальних змінних. Кожна посилальна змінна вказує, являє завжди тільки один динамічний об'єкт.
До недоліків такого рішення можна віднести наступне. Якщо значення посилальної змінної (посилання на динамічний об'єкт) буде загублено - цей об'єкт буде безповоротно загублений. Адже його "Імені" ми явно не знаємо. Воно є значення посилальної змінної. Якщо кілька посилальних змінних вказують на один і той же об'єкт і цей об'єкт буде знищений за допомогою однієї з них, то всі маніпуляції з іншими посилальними змінними стануть некоректними.
2. Опис посилальних змінних і їх семантика
Синтаксис завдання посилального типу:
<завдання посилального типу> :: = ^ <Ім'я типу>
^ - ознака посилального типу; <ім'я типу> - ім'я стандартного або описаного раніше типу. Це тип динамічних об'єктів, які може представляти змінна посилального типу. Треба підкреслити, що тут може бути тільки ім'я типу.
Самі змінні посилального типу вводяться звичайним чином.
type
масив = array [1 .. 100] of integer;
массівссилок = array [1 .. 100] of ^ integer;
var
q, p: ^ integer;
c: ^ char;
матриця: ^ масив;
чудо: массівссилок;
Зв'язок покажчика (посилальної змінної) з об'єктом графічно можна проілюструвати так:
Значення посилальної змінної, відповідне відсутності динамічного об'єкта - nil (зарезервоване слово).
Слід усвідомити, що опис виду
var v: ^ T;
лише вводить статичну змінну (під яку відводиться пам'ять). Проте, ніякого об'єкта типу Т при цьому не з'являється. Для породження об'єкта служить стандартна процедура new. Ця процедура має один фактичний параметр - посилальну змінну. В результаті виконання оператора процедури new породжується динамічний об'єкт належного типу, а посилальної змінної-параметру привласнюється посилання на цей тільки що породжений об'єкт.
При цьому створеному динамічному об'єкту ніякого значення не присвоюється. Тому конструкція new (v) рівносильна опису статичної змінної типу Т.
Для роботи з динамічними об'єктами використовується змінна з покажчиком:
<змінна з покажчиком> :: = <посилальна змінна> ^
тут посилальна змінна - це та посилальна змінна, яка представляє в програмі відповідний динамічний об'єкт. Стрілка після імені посилальної змінної свідчить про тому, що мова йде про значення динамічного об'єкта, який ця змінна представляє, а не про саму змінної.
Наприклад:
r ^: = 35; p ^: = r ^ + p ^ div3; матриця ^ [p ^ +3]: = 25; диво [p ^ +3] ^: = 3
У прикладі матриця ^ [p ^ +3]: = 25; відбувається разіменованіе посилальної змінної матриця (вираз виду матриця ^ часто називають разіменованіем, а операцію ^ - операцією разіменованія; ця операція є в багатьох мовах програмування). У разі диво [p ^ +3] ^: = 3 відбувається разіменованія не повної посилальної змінної чудо, а лише частковою змінної диво [p ^ +3]. Операція разіменованіе застосовна лише до простих змінним посилального типу.
3. Дії над посиланнями
Над значеннями посилального типу немає операцій, які б давали значення посилального типу. Над значеннями посилального типу визначені тільки операції присвоювання і порівняння на рівність і не рівність. В операторі присвоювання виду p: = e посилальним виразом може бути: - Порожнє посилання nil;-посилальна змінна;-посилальна функція (тобто функція чиє значення - посилання). Значення лівої і правої частин повинні засилати на об'єкти одного і того ж типу.
Нехай var p, g: ^ integer. Наприклад, p: = q; призводить до того що і p і q вказують на один і той самий об'єкт, але якщо при цьому об'єкт, на який вказувала посилальна змінна p, буде втрачено, то дії з q стануть некоректними!
Неправильно було б написати p: = q ^ тому зліва змінна посилального типу, а праворуч значення цілого типу; p ^: = 3.0 - знову невідповідність типів (integer та real); p ^: = nil - зліва змінна цілого типу, праворуч - посилальне значення.
Відмінності використання динамічних змінних:
динамічні змінний представлені через статичні змінні посилального типу;
динамічна змінна повинна породжуватися явно за допомогою процедури new;
для доступу до значень динамічної змінної використовується змінна з покажчиком.
4. Приклад.
Розглянемо наступну задачу. Є зовнішній файл, який представляє установа, що складається із записів про службовців установи. Про кожного службовця відомо ПІБ, стать, рік народження, посада (Лаборант, технік, інженер, науковий співробітник, адміністратор, начвідділу, заступник директора, директор), спеціальність (математик, програміст, механік, електронік, економіст, юрист, фізик, хімік), номер відділу (1 .. 32), де працює службовець, характеристика. Потрібно визначити відділ, де працює найбільше наукових співробітників. У відділі не більше 50 співробітників.
Структура п...
