к оглавлению к алгоритмизации СУБД ЯиМП 3GL 4GL 5GL технологии прогр.

Объектно-ориентированное программирование

Типы данных

Современное понятие типа в языках программирования.
Базовые типы.
Основные конструкторы типов.

Современное понятие типа

Прежде чем приступать к изучению объектно-ориентированного программирования (ООП) вспомним ряд положений, без понимания которых невозможно понять парадигму ООП. Одной из основных посылок для понимания такого метода программирования является четкое представление о типах данных, которые Вы собираетесь использовать в своей программе.

А начнем мы разговор с вещей, которые большинство из Вас считает простыми и давно известными. Мы поговорим о базовых типах данных и о конструкторах новых типов, используемых в языке С. Для нас стало уже привычным в начале каждой программы, функции описывать переменные, c которыми мы собираемся оперировать. При этом Вы иногда обоснованно, иногда нет, присваиваете каждой переменной один из доступных в данном языке программирования типов. А почему нам доступны именно эти типы? Насколько адекватно они позволяют описывать моделируемый в программе мир? Можно ли использовать другие, более подходящие типы? На эти и множество других, еще не заданных вопросов, мы и попытаемся сегодня найти ответы.

Каждая используемая нами в программе переменная только тогда имеет смысл, когда может принимать какие-либо значения. Множество значений, которые может принимать переменная, играет столь важную роль для характеристики переменной, что оно называется типом переменной.

Понятие типа программного объекта образовалось постепенно из понятия типа, вошедшего в употребление для описания типов данных, над которыми выполняются операции в программе. На заре программирования типы данных определялись тем, какой машинный формат применялся для отображения данных. Программисты раньше говорили не о типе процессора и его частотных характеристиках, они говорили "Я работаю на машине с длиной слова 64 разряда". (Такой длиной слова обладали отечественные ЭВМ БЭСМ-6, в отличие от распространенных тогда копий с машин IBM/360, имеющих длину слова 32 разряда). Вскоре данные с плавающей точкой стали называть данными вещественного типа. Данным логического типа стали приписывать значения "истина" или "ложь", хотя они представлялись единицей или нулем в одном единичном разряде.

Современное понятие типа базируется на множестве значений, которые могут принимать переменные данного типа, и наборе операций, которые можно к ним применять.

Теперь перед нами встает вопрос: как правильно задать тип данных в программе, и каким образом типы данных можно представить в памяти машины? Прежде всего, следует различать классы типов данных. Самой важной отличительной чертой является структурность значений того или иного типа. Если значение не структурное, т.е. не распадается на компоненты, то оно называется скаляром. Остановимся вначале на таких типах.

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

Итак, хорошо знакомые нам типы char, integer, float…..

Базовые типы

Целый (integer). Представляет множество целых чисел. В системе программирования должны быть определены следующие операторы:

+ сложение,
- вычитание,
* умножение,
/ деление,
% остаток от целочисленного деления.

В каждой ВМ определено некоторое подмножество целых чисел, лежащих в некоторых пределах. С этим подмножеством компьютер может оперировать прямо и эффективно.

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

Например, если для некоторой вычислительной системы тип int определен как множество целых чисел, по абсолютной величине не превосходящих max (|x| <= max), и если сложение, выполняемое машиной, обозначить как add, то

x add y = x + y

только тогда, когда |x + y| <= max. Следовательно, обычный ассоциативный закон, вообще говоря, для машины не выполняется.

Соотношение

(x add y) add z = x add (y add z)

верно тогда, когда |x add y| <= max и |y add z| <= max.

Например, положим max = 100 и подставим значения x = 60, y = 50 и z = -40. Тогда

60 add (50 add (-40)) = 70

а результат (60 add 50) add (-40) не определен.

Количество элементов памяти, необходимое для хранения значений переменной в машине, зависит от диапазона значений, которые эта переменная может принимать. Например, если переменная должна принимать n различных значений, то для ее хранения потребуется log₂(n) битов. Я напоминаю Вам этот, конечно же, известный факт по той только причине, что мы привыкли исходить из обратного - то есть, от машинного представления данного типа. Чаще мы рассуждаем так: для хранения переменной целого типа отводится 16 бит. Следовательно, самое большое целое число (то есть граница интервала) есть 65535 (2¹⁶ - 1). Хотя надо оценивать интервал значений, необходимый нам для моделирования, и под него выбирать тип переменной.

Литерный (char). Этот тип обозначает конечное упорядоченное множество литер. Помимо диапазонов чисел, следует определять набор литер, с помощью которых компьютер общается с внешним миром. Литерами из этого набора снабжаются все периферийные устройства (читающие и печатающие). Существует несколько общепринятых стандартов наборов литер:

Международной организации стандартов ISO - International Standards Organisation;
Американский стандартный код для обмена информацией ASCII - American Standard Code for Information Interchange
8-ми и 7-ми битовые коды обмена информацией КОИ-8 и КОИ-7

Наиболее популярный ASCII код поддерживает 26 букв латинского алфавита, 10 десятичных арабских цифр, некоторое количество специальных литер, таких, как знаки пунктуации. Стандарт определяет 128 литер, подразделяющихся на печатаемые и управляющие. Управляющие литеры играют большую роль при передаче данных. Например, литеры Carriage Return и Line Feed обрабатываются всеми построчно печатающими устройствами. Оставшиеся 128 кодов от 128 до 255 могут определять коды национального языка. Существуют четыре варианта кодировки символов кириллицы. Стандартом de facto стал так называемый альтернативный вариант кодировки. Сейчас, когда отечественная промышленность перестала производить ЭВМ, проблемы нескольких стандартов стали не такими острыми. Хотя еще попадаются файлы с документацией, набранные в основном варианте кодировки. Тогда мы видим по преимуществу, не буквы, а символы псевдографики. А всего лишь несколько лет назад выпускаемые различными министерствами ПЭВМ (скопированные с одного и того же образца IBM PC XT) имели различные кодировки.

Отображение битов на множество литер называется кодом. Следовательно, каждой литере соответствует целое неотрицательной число. Таким образом, тип char можно интерпретировать как множество неотрицательных целых чисел в интервале от 0 до 255, или множество целых чисел в интервале от -128 до +127. Некоторые языки имеют функции преобразования из целого числа в литерное и наоборот (например, BASIC).

Лирическое отступление UNICODE.

Хорошо, когда национальная письменность соотносится с набором литер латинского алфавита. Например, на 26 латинских литер - 33 литеры кириллицы. А каково арабам, китайцам, японцам? Клинопись, иероглифы и языки, в которых столько букв, что одного байта для кодировки не хватает. Для поддержки подобных языков были созданы двухбайтовые наборы символов. Как всегда, было предложено несколько вариантов, и после непродолжительных мучений был выработан стандарт Unicode. Его первоначально разработали фирмы Apple и Xerox в 1988 году. В 1991г был создан консорциум, в который вошли основные производители Hardware и Software. Строки в Unicode просты и логичны. Все символы в них состоят из 16-битовых кодов. Следовательно. Можно закодировать 65536 символов. Этого достаточно даже для японской каны. В настоящее время кодовые позиции определены для нескольких языков и задействовано около 34000 кодов. Так что место для расширения есть. Кодовые позиции разбиты на группы:

0000 - 007F ASCII
0080 - 00FF Расширение ASCII (Latin 1)
0100 - 017F Европейские латинские
0180 - 01FF Расширенные латинские
0250 - 02AF Стандартные фонетические
02B0 - 02FF Модифицированные литеры
0300 - 03FF Общие диакритические знаки
0370 - 03FF Греческий
0400 - 04FF Кириллица
0530 - 058F Армянский
0590 - 05FF Еврейский
0600 - 06FF Арабский
0900 - 097F Деванагари

Около 29000 кодовых позиций пока не занято, но зарезервировано для будущего использования. Приблизительно 6000 позиций оставлено специально для программистов.

Вещественный (real, float, double …) Особое значение имеет тот факт, что в машине можно представить только значения из конечного диапазона. В случае целых чисел можно утверждать, что при любых обстоятельствах, кроме переполнения, в результате выполнения арифметических операций получались точные значения. Но применительно к арифметике с вещественными числами это утверждение неверно.

Причина заключается в том, что на сколь угодно малом интервале оси вещественных чисел содержится бесконечно много значений. Ось вещественных чисел образует так называемый континуум.

В программировании, тип real не представляет бесконечное, несчетное множество вещественных чисел; ему соответствует конечное множество представителей интервалов континуума вещественных чисел.

Результаты вычислений, в которых участвуют приближенные, а не точные значения, в значительной степени зависят от решаемой задачи и от выбранного алгоритма. В лучшем случае полученные результаты будут приближениями с неизбежными погрешностями. Оценка этих погрешностей, которые являются результатом подмены вещественного континуума конечным множеством представителей, является очень трудной задачей и служит объектом изучения вычислительной математики.

Естественно, что производить вычисления, ничего не зная о природе и степени ожидаемой погрешности, бессмысленно. Чтобы понимать и даже проводить такие измерения, необходимо знать, какого вида представления используются для вещественных чисел с конечным числом цифр. В современных компьютерах обычно используют так называемое представление с плавающей точкой (отсюда и пошло название типа float)

Вещественное число x изображается с помощью двух целых чисел e и m, каждое из которых содержит конечное число цифр, так что

x = m * Be, -E < e < E, -M < m < M

Здесь m называется мантиссой, e - порядком, а B, E и M являются константами, характеризующими представление. Число B называется основанием представления с плавающей точкой. Обычно B не равно 10 (как мы привыкли в школьном курсе математики), а является малой степенью 2.

Для любого заданного значения x можно найти много различных пар (m, e). Каноническая или нормализованная форма определяется дополнительным соотношением

(M/B)<=|m|<M

При использовании только нормализованной формы плотность представителей интервалов на оси вещественных чисел экспоненциально уменьшается с увеличением |x|. Например, интервал [0.1: 1] содержит приблизительно столько же представителей, сколько интервал [10000 : 100000]. (Для основания представления 10 это точно столько).

Эта неравномерность накладывает ряд ограничений. Очевидно, что нельзя точно описать элементарные операции над аргументами типа float. Поэтому они определяются в виде аксиом:

Тип float является конечным подмножеством множества вещественных чисел
Каждому числу x принадлежащему множеству вещественных чисел ставится в соответствие число типа float, которое называется его представителем.
Каждое число типа float представляет множество вещественных чисел, но это множество значений является связным интервалом на вещественной числовой оси.
Существует максимальное значение max, такое, что для всех |x| > max представители не определены.
Множество чисел типа float симметрично относительно 0.

Следующие аксиомы постулируют совокупность требований, которые безоговорочно должны выполняться в любой машинной арифметике.

Коммутативность сложения и умножения
x + y = y + x, x * y = y * x
x >= y >= 0 (x - y) + y = x
Симметричность основных операций относительно 0

x - y = x + (-y) = - (y - x)

( -x ) * y = x * ( -y ) = - (x * y )

( -x ) / y = x / ( -y ) = - (x / y )
Монотонность основных операций

если 0 <= x <= a и 0 <= y <= b

то x + y <= a + b, x - b <= a - y,

x * y <= a * b/ x / b <= a / y

Обратите внимание, что обычные для арифметики законы ассоциативности и дистрибутивности отсутствуют в рассмотренных аксиомах. Это не случайно. Использование конечного числа представителей может нарушить исполнение этих законов. Например, если наше представление позволяет хранить только 4 цифры (порядок будем задавать положением десятичной точки) то

x = 9.900 y = 1.000 z = -0.999 1. (x + y) + z = 10.90 + (-0.999) = 9.910 2. x + (y + z) = 9.900 + 0.001 = 9.901

Вы можете сами представить подобный пример нарушения дистрибутивного закона.

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

Деление также представляет потенциальную опасность. В случае малых делителей результат легко может оказаться в области переполнения. Поэтому следует избегать деления на числа, близкие к нулю. Например, не следует в программе пользоваться отношением вида abs (t/x) <= eps, его лучше заменить отношением вида abs(t) <= eps * abs(x). Оно не содержит деления.

Мне кажется, что рассмотренные положения несколько поколебали Ваши представление о типах как о чем-то простом и понятном. А ведь мы пока говорили только об основных типах. Пора переходить к составным и производным типам.

Основные конструкторы типов

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

Типы строятся, исходя из конечного набора базисных типов (называемых также простыми, примитивными, элементарными), с помощью операций - конструкторов типов.

Большинство конструкторов типов имеют прямые аналоги в математике. Итак, базисные типы - это множества целых чисел, конечных приближений вещественных чисел, литерных значений и, возможно, булевских величин.

Одним из самых простых и понятных конструкторов можно назвать объявление перечисляемого типа. Этот скалярный тип описывается простым перечислением его компонент. Хотя с теоретической точки зрения скалярные типы данных могут полностью удовлетворить потребности программиста, все же желательно иметь практическую возможность определять свои неструктурные типы, и их помощью можно более четко описать предполагаемую потенциальную область значений переменной и обеспечить возможность эффективного представления переменной. Объявление переменной перечисляемого типа определяет список именованных констант, называемый списком перечисления. Каждому элементу списка перечисления ставится в соответствие целое число. Поэтому переменной перечисляемого типа выделяется столько же памяти, сколько и для переменной типа int. Над объектами перечисляемого типа определены те же операции, что и над объектами целого типа.

enum {компонента1,...,компонентаn}; enum TColor {WHITE, YELLOW, RED, GREEN, BLUE, BLACK}; … Tcolor color1 = WHITE, color2; color2 = color1;

Теперь поговорим немного о другом классе типов. Это так называемые структурные типы данных. Структурные типы предоставляют возможность давать коллективное имя некоторому множеству элементов. Существует несколько способов структурирования, каждый из которых отличается способом доступа к индивидуальным компонентам. Для определения типа структурной переменной необходимо задать:

1. способ структурирования,

2. типы компонент.

Важнейшие конструкторы таких типов - это массивы и записи (структуры).

Массив позволяет хранить как единое целое последовательность переменных одного типа. Переменная, имеющая структуру массива, является совокупностью компонент-переменных одного и того же типа. У массива, однако, есть характерные особенности:

1. Каждая отдельная компонента массива может быть явно обозначена и к ней имеется прямой доступ.

2. Число компонент массива определяется при его описании и в дальнейшем не меняется.

Для обозначения компонент используется имя переменной-массива и индекс, который однозначно указывает на желаемый элемент. Тот факт, что индекс может быть вычисляемым объектом, выделяет массив среди других структур данных.

Элементы массива могут быть не только скалярами, но также и структурными компонентами. Если они сами являются массивами, то первоначальный массив называется многомерным.

С абстрактной точки зрения массив можно определить как отображение области одного типа (множество индексов) на множество значений некоторого другого типа (тип элементов). Отображение по-другому называется "функцией". Так что, массивы - это функции с конечной областью определения, то есть функции, определяемые конечной таблицей значений.

Типовой конструктор массивов в языке Си обозначается как [ ].

Тип идентификатор [размер];

В отличие от массива структура позволяет объединить в одном программном объекте совокупность значений, которые могут иметь различные типы. Список объявлений элементов представляет собой последовательность из одного и более переменных. Каждая переменная, объявленная в этом списке, называется элементом структуры. Элементы структуры могут иметь базовый тип, либо быть указателем, структурой. Элемент структуры не может быть того же типа, в которой он содержится, однако им может указатель на тип структуры, в которую он входит.

Типовое выражение, соответствующее конструктору записи

struct { тип1 идентификатор1; … типn идентификаторn; };

Структура как конструкция аналогична декартову произведению множеств. Простым примером такого произведения является дата. Для спецификации даты достаточно трех значений: год, месяц, число месяца. Так что вполне логично для описания переменной типа TDate использовать следующую конструкцию:

enum TMonth {Jan, Feb, Mar, ..., Dec}; struct Tdate { int Year; TMonth Month; int Day; }; … TDate BirthDay[10]; BirthDay[3].Year = 1256; BirthDay[3].Month = Jan; BirthDay[3].Day = 22;

Пришедшее в язык Си из Алгола 68 понятие объединения union представляет собой размеченное объединение, где элемент множества слагаемого входит во множество с пометкой, указывающей это слагаемое. Объединение позволяет в различные моменты времени хранить в одном объекте значения различного типа. В процессе объявления объединения с ним ассоциируется набор типов значений, которые могут храниться в данном объединении. В каждый момент времени объединение может хранить значение только одного типа из набора.

Память, которая выделяется переменной типа объединение, определяется размером наиболее длинного из элементов объединения. Все элементы размещаются в одной и той же области памяти и с одного и того же адреса. Значение текущего элемента теряется, когда другому элементу объединения присваивается значение. Синтаксически объединение union записывается аналогично struct.

union { тип1 идентификатор1; … типn идентификаторn; };

В некоторых языках имеются такие конструкторы типов, как отрезок, множество set (Паскаль), граф.

Особый интерес представляет такой конструктор типов, как указатель pointer. Указатели являются средством построения и обработки структур данных, являющихся, по существу, ориентированными графами с узлами, которые сами могут иметь сложную структуру. Указатель - это переменная, предназначенная для хранения адреса некоторого объекта. Объявление указателя специфицирует имя переменной и тип объекта, на который может указывать эта переменная. Указатель может указывать на значение базового, перечисляемого типа, структуры, объединения, массивы, функции и указатели. В языке Си указатель состоит из адреса, указывающего на объект определенного типа, то есть это типизированный указатель. Приведение указателей к определенному типу позволяет ввести аксиоматику арифметики указателей. Однако, кроме типизированных указателей, существует указатель на пустой тип (void). Указатель на void может указывать на значение любого типа. Однако для выполнения операций над указуемым объектом, необходимо привести тип указателя к типу этого объекта.

Несколько особняком стоят функции. В математике функциям уделяется большое внимание, они являются базовыми объектами. Как мы только что отметили, табличные функции виде массивов входят в систему типов. А как обстоит дело с другими функциями, теми, что представляются в виде подпрограмм (процедур), возвращающих значения?

Тут надо задать вопрос - А что такое данные? Согласно распространенной точке зрения, высказанной Никлаусом Виртом в книге "Алгоритмы + структуры данных = программа", данные - это пассивная, обрабатываемая часть программы. Но функции относятся к активной части программы, и значит, это не данные.

С другой стороны, все, что может быть аргументом ("фактическим параметром") функции, следует считать данными. Но функция, возвращающая значение, может быть использована в качестве аргумента. Какой-то порочный круг.

Выход здесь такой: функции - это данные, но данные особого рода в виду их двойной роли (активной и пассивной) в вычислениях. В языке Си, как и в Алголе 68 функции включаются в систему типов, и тип функции определяется типом возвращаемого значения.

В заключение я хочу привести Вам цитату из книги Хоара [1] по поводу структурной организации типов.

Тип определяет класс значений, которые могут принимать переменная или выражение
Каждое значение принадлежит одному и только одному типу.
Тип значения константы, переменной или выражения можно вывести либо из контекста, либо из вида самого операнда, не обращаясь к значениям, вычисляемым во время работы программы.
Каждой операции соответствует некоторый фиксированный тип ее операндов и некоторый фиксированный тип результата
Для каждого типа свойства значений и элементарных операций над значениями задаются с помощью аксиом.
При работе с языками высокого уровня знание типа позволяет обнаруживать в программе бессмысленные конструкции и решать вопрос о методе представления данных и преобразования их в вычислительной машине.
Интересующие нас типы - это типы, хорошо известные математикам: прямые произведения, размеченные объединения, множества, функции, последовательности…

Обсуждая то или иное понятие, человек стремится различить в нем три стороны: идею, формулировку и мотивировку. Идея - это содержательная, интуитивная сторона, суть дела. Формулировка - это математически точное, однозначное выражение идеи. Мотивировка - это подоплека понятия: что за ним стоит, какова его цель, в каком контексте и на каком "фоне" оно возникает.

Рассматривая с этих точек зрения определение Хоара, можно отметить, что идеи, в основном, понятны; формулировки требуют уточнения; желательна более полная мотивировка.

Пытаясь понять, что стоит за идеями и решениями, мы можем увидеть направления дальнейшего движения и факторы, которые оказывают на него влияние.

к оглавлению к алгоритмизации СУБД ЯиМП 3GL 4GL 5GL технологии прогр.

Знаете ли Вы, что процедурная абстракция, процедура - это наиболее известный в программировании тип абстракции. Всякий, кто применял для выполнения функции подпрограмму, реализовывал тем самым процедурную абстракцию. Процедуры объединяют в себе методы абстракции через параметризацию и спецификацию, позволяя абстрагировать отдельную операцию или событие.

НОВОСТИ ФОРУМА

Рыцари теории эфира