Сумісність і перетворення типів даних
Курсовий проект з програмування
Склала: Ірина Комарова IT2V
Таллінн 2004
Вступ
Мова
програмування Pascal був розроблений в 1968-1971 рр.. Ніклаус Віртом в
Цюріхському Інституті інформатики (Швейцарія), і названий вчесть Блеза Паскаля --
видатного математика, філософа і фізика 17-го століття. Початкова мета
розробки мови диктувалася необхідністю створення інструменту "для
навчання програмуванню як систематичній дисципліні ". Однак дуже
скоро виявилася надзвичайна ефективність мови Pascal в самих
різноманітних програмах, від вирішення невеликих задач чисельного характеру до
розробки складних програмних систем - компіляторів, баз даних, операційних
систем і т.п. До теперішнього часу Pascal належить до групи найбільш
поширених і популярних у світі мов програмування:
•
існують численні реалізації мови практично для всіх машинних
архітектур;
•
розроблено десятки діалектів і проблемно-орієнтованих розширень
Pascal;
•
навчання програмуванню та науково-технічні публікації в значній
мірою базуються на цій мові.
Опис типів даних
Гідністю
мови Паскаль є можливість використання широкого набору різних типів
даних. Тип даних визначає можливі значення констант, змінних, функцій,
виразів і операцій, які можуть працювати над ними.
Типи
даних підрозділяються на прості і складні. Прості типи поділяються на стандартні
(зумовлені) типи і типи визначаються користувачами (для користувача
типи).
Імена
стандартних типів є ідентифікаторами і діють у будь-якій точці
програми. Вони описані в стандартному модулі System. Так само, як і інші
ідентифікатори, імена стандартних типів можуть бути перевизначені в програмі.
Однак
залишається можливість звернення до їх первісного глузду за допомогою
кваліфікується ідентифікатора із зазначенням імені модуля System. Наприклад:
System.Integer, System.Real.
До
стандартним типам відносяться:
•
група цілих типів (Shortint, Integer, Longint, Byte, Word);
• група речових типів (Single,
Real, Double, Extended, Comp);
• група логічних (Булевського) типів (Boolean, ByteBool, WordBool, LongBool);
•
символьний тип (Char);
•
рядковий тип (String, Pchar);
•
вказівний тип (Pointer);
•
текстовий тип (Text).
символьний
тип, цілі і Булевського типи відносять до, так званих, порядковим типами.
Порядкові
типи характеризуються наступними властивостями:
1.
Безліч допустимих значень будь-якого порядкового типу являє собою
упорядковану послідовність, кожен елемент якої має свій порядковий
номер. Порядковий номер є цілим числом. Перше значення будь-якого
порядкового типу має номер 0, наступний номер 1 і т.д. Виняток становлять
порядкові типи Integer, Shortint, Longint, де порядковим номером значень
цих типів є саме значення.
2.
До будь-якого значення порядкового типу можна застосовувати функції повертають номер,
попереднє чи наступне значення даного типу.
Користувальницькі
типи - додаткові абстрактні типи, характеристики яких програміст
може визначати самостійно.
До
користувальницьким типами відносяться:
•
перераховуються тип;
•
інтервальний тип;
•
вказівні типи (крім стандартного типу Pointer);
•
структуровані типи;
•
процедурний тип.
перераховуються
та інтервальний типи є порядковими.
Структура
підрозділу опису типів виглядає наступним чином:
Форма
запису:
type
=;
Приклад:
type
vec
= Integer;
bool
= Boolean;
Стандартні
функції мови Паскаль
Для
виконання часто зустрічаються операцій і перетворень даних, що відносяться до
різних типів, існують заздалегідь певні функції, які називаються
За умовчанням. Для звернення до функції необхідно задати її ім'я і в дужках
список аргументів (параметрів).
Перш
ніж перейдемо до стандартних функцій, спочатку ознайомимося з правилами їх
використання:
1.
Ім'я функції записується прописними літерами латинського алфавіту.
2.
Аргумент функції записується в круглих дужках після імені функції.
3.
Аргументом функції може бути константа, змінна, або арифметичне
вираз того ж типу
Тепер
розглянемо деякі стандартні функції:
Функція
Дія Тип Х Тип значення, що повертається
SQRT (X)
обчислює квадратний корінь з аргументу Х дійсний дійсний
SQR (X)
обчислює квадрат аргументу Х цілий дії-них цілий дії-них
RANDOM (X)
повертає випадкове число, перед викликом функції бажано використовувати в
програмі оператор RANDOMIZE включає випадкову ініціалізацію генератора
випадкових чисел цілий, позитивний відповідає типу змінної приймаючої
значення
SIN (X)
обчислює синус аргументу Х дійсний дійсний
COS (X)
обчислює косинус аргументу Х дійсний дійсний
ABS (X)
обчислює абсолютне значення (модуль) аргументу Х цілий дії-них цілий
дії-них
ODD (X)
перевіряє Х на парність довге ціле логічний
ORD (X)
визначає порядковий номер символу Х будь-який тип крім дійсного довге
ціле
CHR (X)
визначає символ стоїть за порядковим номером Х byte символьний
PRED (X)
визначає попереднє значення по відношенню до Х будь-який тип крім дійсного
той же тип
SUCC (X)
визначає подальше значення по відношенню до Х будь-який тип крім
дійсного той же тип
ARCTAN (X)
обчислює арктангенс аргументу Х дійсний дійсний
EXP (X)
обчислює експоненту від аргументу Х дійсний дійсний
LN (X)
обчислює натуральний логарифм від Х дійсний дійсний
TRUNC (X)
знаходить цілу частину від Х дійсний довге ціле
ROUND (X)
округлює Х в бік найближчого цілого дійсний довге ціле
INT (X)
повертає цілу частину аргументу Х дійсний дійсний
FRAC (X)
повертає дробову частина аргументу Х дійсний дійсний
DEC (X, N)
зменшує значення змінної Х на задане число N будь-який тип крім
дійсного той же тип
INC (X, N)
збільшує значення змінної Х на задане число N будь-який тип крім
дійсного той же тип
PI
повертає значення числа - дійсний
Приклади:
1.
ORD ( 'R') = 82; ORD (5) = 5;
2.
CHR (68) = 'D'; можна викликати цю функцію через # ", якщо аргумент функції
константа (# 68 = 'D');
3. PRED ( 'N') = 'M'; PRED (87) = 86;
4. SUCC ( 'S') = 'T'; SUCC (87) = 88;
5. PI = 3.141592653897932385;
6. ROUND (3.1415) = 3;
7. LN (1) = 0.000;
8. SQRT (36) = 6.000;
9. SIN (90 * pi/180) = 1.000.
Зауваження:
В
тригонометричних функціях аргумент повинен бути заданий тільки в радіани мірою
кута.
Працює
і перетворення типів даних.
Турбо-Паскаль
- Універсальна мова, отже, всі застосовувані операції визначені
тільки над операндами сумісних типів.
Два
типу вважаються сумісними, якщо
•
обидва вони є один і той самий тип.
•
один тип є тип-діапазон другого типу.
•
обидва вони є типами-діапазонами одного й того самого базового типу.
•
один тип є рядок, а інший - рядок або символ.
•
обидва вони є процедурні типи з однаковим типом результату (для типу-функції),
однаковою кількістю параметрів і однаковим типом взаємно відповідних
параметрів.
Коли
в тих чи інших операціях або операторах присутні дані, що відносяться до
різних типів, виникає питання про сумісність типів. У зв'язку з цим говорять
про ідентичність типів, сумісності типів і сумісності типів для
привласнення. Коли виникають проблеми з відповідністю типів даних, можна
здійснити перетворення тих чи інших типів.
Ідентичність
типів.
Ідентичність
типів потрібно від формальних параметрів процедур і функцій та відповідних
їм фактичних параметрів під час дзвінка.
Два
типу Т1 і Т2 ідентичні в наступних випадках:
T1
і Т2 - один і той же ідентифікатор типу (integer; real і т.д. і т.п.);
Один
тип оголошується еквівалентним іншому.
type
T1 = boolean;
T2 = T1;
T3 = boolean;
M1 = array [1 .. 5] of integer;
M2 = array [1 .. 5] of integer;
var
V1, V2 = array [1 .. 10] of integer;
Так,
типи Т1, Т2, Т3 і boolean - ідентичні, а М1 і М2 - не ідентичні типи, але тим
не менше, змінні V1 і V2 - змінні ідентичних типів.
Працює
типів.
Працює
типів потрібно в виразах (у тому числі й в операціях відносини).
Два
типу Т1 і Т2 ідентичні в наступних випадках:
Т1
і Т2 - один і той же тип або вони ідентичні;
Т1
і Т2 - речові типи;
Т1
і Т2 - цілі типи;
Один
тип - матеріальний, а другий - цілий;
Один
тип являє собою тип - діапазон іншого;
Обидва
типу є типами - діапазонами якогось одного типу;
Обидва
типу є типами - множинами з сумісними базовими типами;
Один
тип є рядком, а інший - символом або рядком.
Працює
для присвоєння.
Ця
сумісність необхідна, коли значення якогось вираження присвоюється
змінної, типізований константі або функції. Якщо значення об'єкта типу Т2
визначається об'єкту типу Т1, то це можливо в наступних випадках:
Т1
і Т2 - ідентичні типи і не є файловими типами або структурованими
типами, що містять компоненти файлового типу на будь-якому рівні
структурованості;
Т1
і Т2 - сумісні порядкові типи і значення типу Т2 знаходиться в межах
можливих значень об'єкту типу Т1;
Т1
і Т2 - дійсні типи та значення типу Т2 знаходиться в межах можливих
значень об'єкту типу Т1;
Т1
- Дійсний тип, а Т2 - цілий;
Т1
і Т2 - рядки;
Т1
- Рядок, а Т2 - символ;
Т1
і Т2 - сумісні типи - множини і всі компоненти значення типу Т2 знаходяться
в безлічі Т1.
Перетворення
типів у Паскалі може бути явним і неявним. При явному перетворення типів
використовуються виклики спеціальних функцій Ord, Trunc, Round, Chr, Ptr
(перетворює четирехбайтний цілочисельний аргумент до типу-вказівником), аргументи
яких належать одному типу, а результат іншому.
Перетворення
може досягатися застосуванням ідентифікатора (імені) стандартного типу, або
певного користувачем типу, в якості ідентифікатора функції
перетворення до вираження перетворюється типу (так зване автовизначення
перетворення типів). Наприклад, припустимі наступні виклики функцій:
Type
Mytype = (A, B, C, D);
. . . . . . . . . . . . . . . . .
Mytype (2);
Integer (D);
Pointer (Longint (A) + $ FF);
Char (127 Mod C);
Byte (K);
При
автовизначення перетворення типу виразу може відбутися зміна довжини
його внутрішнього подання (зменшення або збільшення).
В
Турбо-Паскалі є ще один явний спосіб: в ту область пам'яті, яку займає
мінлива деякого типу, можна помістити значення виразу іншого типу,
якщо тільки довжина внутрішнього представленні розташовуваного значення в
точності дорівнює довжині внутрішнього подання змінної. З цією метою знову
використовується автовизначення функція перетворення типів, але вже у лівій
частині оператора присвоєння:
Type
Byt = Array [1 .. 2] Of Byte;
Int = Array [1 .. 2] Of Integer;
Rec = Record
X: Integer;
Y: Integer;
End;
Var
VByt: Byt;
VInt: Int;
VRec: Rec;
Begin
Byt (VInt [1]) [2]: = 0;
Int
(VRec) [1]: = 256;
End.
Дані
одного типу можуть автоматично (неявно) перетворюватися в дані іншого
типу перед виконанням операцій виразів.
Неявно
перетворення типів можливо тільки в двох випадках:
•
вираз з цілих і речових приводиться до речових
•
одна й та ж область пам'яті трактується поперемінно як що містить дані то
одного, то іншого типу.
Поєднання
даних може статися при використанні записів з варіантами, типізованих
покажчиків, що містять однакову адресу, а також при явному розміщенні даних
різного типу в одній області пам'яті (використовується Absolute - за ним поміщається
або абсолютний адресу, або ідентифікатор раніше певної змінної).
Абсолютний
адреса - пара чисел, розділених двокрапкою - перше - сегмент, другий --
зсув.
Приклад:
B: Byte Absolute $ 0000: $ 0055;
W: Longint Absolute 128:0;
Якщо
за Absolute вказано ідентифікатор змінної, то відбувається поєднання в пам'яті
даних різного типу, причому перші байти внутрішнього представлення даних будуть
розташовуватися з одного й того ж абсолютному адресою:
Var
X: Real;
Y: Array [1 .. 3] Of Integer Absolute
X;
Еквівалентність
типів
Щодо
поняття еквівалентності типів існує кілька точок зору. Розглянемо три
з них. Всі вони виходять з того, що еквівалентні типи повинні допускати однакові
послідовності операцій.
Структурна
еквівалентність
Два
атрибуту типу T1 і T2 називаються (структурно) еквівалентними, якщо
•
їх базові типи BT1 і BT2, відповідно, збігаються або
•
BT1 = arr (M, N, T1 '), BT2 = arr (M, N, T2') і T1 'еквівалентний T2', або
•
BT1 = rec ([F1: T11 ,..., Fn: T1n]), BT2 = rec ([F1: T21 ,..., Fn: T2n]) і T1i еквівалентний
T2i для кожного i, або
•
BT1 = ref (T1 '), BT2 = ref (T2') і T1 'еквівалентний T2' і
•
припущення про еквівалентність T1 і T2 не суперечить умовам 1-4.
Кілька
дивне умова 5 пов'язане з рекурсивного типів. Воно робить ставлення
структурної еквівалентності найбільшим серед відносин, що задовольняють
умовами 1-4.
П
р и м е р:
Хай
T1 = rec ([info: int, next: T1])
T2 = rec ([info: int, next: T2])
Застосовуючи
тільки правила 1-4, отримаємо, що T1 і T2 еквівалентні, якщо T1 і T2
еквівалентні. Правило 5 змушує зробити висновок, що T1 і T2 дійсно
еквівалентні (на підставі тільки правил 1-4 можна зробити і зворотний висновок).
Якщо
б не було посилальних і, отже, рекурсивних типів (як у Фортране або
Алгол 60), то визначення структурної еквівалентності зводилося б до умови
1, тобто до рівності базових типів.
При
допущення ж рекурсивних посилальних типів для перевірки структурної
еквівалентності двох типів використовується алгоритм знаходження всіх пар
еквівалентних станів деякого кінцевого автомата. Можна використовувати
наступний метод побудови цього автомата.
Спочатку
будується праволінейная граматика:
1.
Для кожного опису ідентифікатора типу, змінної або параметра
declared (I, B, Inf), де Inf одно type (T), var (T) або par (T), типу T ставиться в
відповідність новий нетермінал t.
2.
Якщо нетерміналу t відповідає базовий тип arr (m, n, T1), то типу T1 ставиться в
відповідність новий нетермінал t1 і вводиться правило t -> arr mn t1.
3.
Якщо нетерміналу t відповідає базовий тип rec ([f1: T1 ,..., fn: Tn]), то типу Ti
ставиться у відповідність новий нетермінал ti для кожного i і вводяться правила t
-> Ref i fi ti.
4.
Якщо нетерміналу t відповідає базовий тип ref (T1), де T1 = int або T1 = real,
то вводиться правило t -> T1.
5.
Якщо нетерміналу t відповідає базовий тип ref (tid (I, B)), а типу tid (I, B) вже
сопоставлен нетермінал t1, то вводиться правило t -> ^ t1.
Нетермінали
цієї граматики еквівалентні, якщо і тільки якщо відповідні типи
структурно еквівалентні.
Залишається
перетворити цю граматику до автоматною увазі і застосувати алгоритм знаходження
всіх пар еквівалентних станів.
Ставлення
структурної еквівалентності дійсно є еквівалентними, тому що воно
рефлексивно, транзитивній і симетрично. Крім того, два типи структурно
еквівалентні тоді і тільки тоді, коли вони допускають одні й ті ж
послідовності операцій. Це робить таку еквівалентність простий і
зрозумілою програмістам. Її основним і досить істотним недоліком є
складний і громіздкий алгоритм перевірки еквівалентності. Наскільки відомо
автору, структурна еквівалентність була прийнята тільки у мові Алгол 68.
Предикат
consist в цьому випадку визначимо наступним чином:
consist (T1, T2): base_type (T1, BT1), base_type (T2, BT2),
(BT1 = int, BT2 = real;%, що приводиться,
equiv (BT1, BT2);% еквівалентність
error ( "Несумісні
типи ")).
Іменна
еквівалентність
При
стандартизації мови Паскаль була прийнята іменна еквівалентність. Відповідно до її
визначення еквівалентними можуть бути тільки іменовані типи, тобто типи з
атрибутами int, real або tid (_,_):
1.
Іменований тип еквівалентний сам собі.
2.
Якщо тип T = tid (I, B) має опис declared (I, B, T1), де T1 - іменований тип,
то типи T і T1 еквівалентні.
Це
дуже обмежувальне визначення. Навіть у Паскалі допустимо присвоювання
U: = V,
якщо
змінні U і V описані як
var U, V: array [1 .. 10] of real,
хоча
мають неіменованний тип "масив". Але в тому ж Паскалі цей оператор
неприпустима через нееквівалентності типів змінних, якщо вони описані як
var U: array [1 .. 10] of real;
var V: array [1 .. 10] of real;
Щоб
охопити всі ці випадки, компілятор для кожного входження вирази типу,
що починається з array, record або ^ (т. е. що не є ідентифікатором типу),
вводить унікальне ім'я типу - псевдонім, завдяки чому різні входження одного
і того ж вирази типу виявляються нееквівалентним в сенсі іменний
еквівалентності.
В
відповідності зі сказаним слід внести зміни в правила DC-граматики для
нетермінала type, що визначають атрибут типу. У них включається тепер породження
і опис псевдонімів типу. Для створення нових "імен" можна
використовувати самі різні методи; ми тут скористаємося предикатом recorda,
генерує як псевдонім унікальну посилання на порожній терм,
записуваний по ключу alias. опис цього псевдоніма типу включається у вигляді
предиката declared.
type (B, tid (A, B)) -->
[array, `[, n (M ),`:, n (N ),`], of], type (B, T),
(recorda (alias, _, A),
assert (declared (A, B, type (arr (M, N, T )))}.
type (B, tid (A, B)) -->
[record], field (B, F), fields (B, LF),
(correct (F, LF),
recorda (alias, _, A),
assert (declared (A, B, type (rec ([F | LF ])))},
[end].
type (B, tid (A, B)) -->
[ `^, id (I )],
((type_id2 (I, B, B1, type (_));
assert (declared (I, B, type (referred ))),
B1 = B),
recorda (alias, _, A),
assert (declared (A, B, type (ref (I, B1 )))}.
Предикат
consist в цьому випадку визначається наступним чином:
consist (T1, T2): T1 = int, T2 = real;%, що приводиться,
equiv (T1, T2)
;% Еквівалентність
error ( "Несумісні
типи ").
equiv (T, T).
equiv (tid (I, B), tid (I1, B1)): declared (I, B, type (tid (I1, B1 )));
declared (I1, B1, type (tid (I, B ))).
Іменна
еквівалентність порівняно просто реалізується. Але це - відношення
(рефлексивне і симетричне) не транзитивній, і тому не є
еквівалентність ні в математичному, ні в звичному, повсякденному розумінні. Поняття
псевдонім типу звичайно не дається програмістам, Тому початківці програмісти
на Паскалі часто роблять помилки, на зразок зазначених у прикладі. Мотивацією для
введення іменний еквівалентності в 1970-і роки стало бажання уникнути помилок
програмування, на зразок присвоювання "яблук" "крабів",
коли і ті, й інші описані як цілі. З розвитком об'єктно-орієнтованого
програмування подібні хитрощі стали зайвими, а іменна еквівалентність
залишилася в деяких мовах як анахронізм.
Структурно-іменна
еквівалентність
Цей
тип еквівалентності найпростіший: еквівалентними вважаються типи, що мають
однаковий базовий тип. Предикат consist в цьому випадку визначається наступним
так:
consist (T1, T2): base_type (T1, BT1), base_type (T2, BT2),
(BT1 = int, BT2 = real
;%, Що приводиться,
BT1 = BT2
;% Еквівалентність
error ( "Несумісні
типи ")).
При
цьому немає необхідності вводити псевдоніми типу, як у випадку іменний
еквівалентності. Замість предиката acc_type при аналізі доступу можна застосовувати
предикат base_type.
Ставлення
структурно-іменний еквівалентності рефлексивно, симетрично і транзитивній. За
вкладення воно лежить строго між структурним та іменний еквівалентності. Їм
легко користуватися на практиці.
Приклади
1.
З
допомогою нескладної програми ми зможемо дізнатися внутрішній код довільного
символу.
Program
Code_pf_Char;
(Програма
читає символ з клавіатури і виводить на екран
цей
символ і відповідний йому внутрішній код)
var
ch:
Char; (В цю змінну читається символ)
begin
Write ( 'Введіть
будь-який символ: ');
ReadLn (ch);
(Читаємо один символ)
WriteLn (ch,
'=', Ord (ch)); (Перетворимо його до цілого і виводимо на екран)
END.
Звертаємо
увагу: при виклику
WriteLntch, '
= ', Ord (ch));
третій
параметром звернення зазначений виклик функції ORD (СН), що з точки зору мови
є виразом; в багатьох випадках при виклику процедур і функцій як
параметрів виклику можна вказувати не тільки змінні або константи, а й
вислову з їх участю.
2.
Давайте
подивимося, як можна реалізувати на універсальною мовою програмування
найпростіші інструкції лінгвіста (навіть не іспользуюшая цих понять), що стосуються
етапу перетворення орфографічного тексту в фонетичну транскрипцію. Далі
наведено приклад задачі і її рішення на мові Паскаль.
невимовною
голосні:
Сполучення
"вств" і "СТН" транскрибуються як [ств] і [сн]
відповідно, тобто:
1)
/ вств/-> [ств]
2)
/ СТН/-> [лнц]
Реалізація
двох цих правил на мові Паскаль:
program transcription;
var
Word: String;
I, J, K: Integer;
begin
Write ( 'Введіть слово:'); ReadLn (Word);
K: = Pos ( 'вств', word);
while (K 0) do
begin
delete (Word, K, 1);
K: = Pos ( 'вств', Word);
end;
K: = Pos ( 'СТН', Word);
while (K 0) do
begin
delete (Word, K 1, 1);
K: = Pos ( 'СТН', Word);
end;
WriteLn ( 'Транскрипція:', Word);
end.
Як
видно з прикладу, два правила, викладені в лінгвістичному описі,
реалізуються програмою в двадцять з гаком рядків. Неважко помітити, що а)
такий запис дуже громіздка, б) вона важка для сприйняття, в) вона абсолютно
не має нічого спільного з записом, природною для лінгвіста і тому погано
відображає суть перетворень, що відбуваються. А якщо б ми трохи ускладнили
правила, ввівши декілька слів-винятків, вимагаючи перевірити, чи не є
транскрібіруемое слово похідним від одного з них, програма збільшилася б у
два рази або більше.
Список літератури
Для
підготовки даної роботи були використані матеріали з сайту http://2balla.ru
