Тип данных

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В информатике тип данных или просто тип представляет собой классификацию информационных сущностей (например, таких как значения[en] или выражения[en]), определяющую возможность их использования в рамках заданной формальной системы. Понятие имеет несколько определений, которые могут частично пересекаться или приводить к тождественному содержанию. Наиболее принципиально различимых, хотя и не противоречащих друг другу, определений два:

  • декларативное — тип есть множество допустимых значений[en], которые могут принимать данные, принадлежащие к этому типу;
  • процедурное — тип определяется поведением, т.е. набором действий, которые можно осуществлять над данными, принадлежащими к этому типу.

Декларативное определение чаще всего используется в императивном программировании, процедурное — в параметрическом полиморфизме. Объектно-ориентированное программирование использует процедурное определение при описании взаимодействия компонентов программы, и декларативное — при описании реализации этих компонентов на ЭВМ, соответственно, рассматривая «класс-как-поведение» и «класс-как-объект в памяти».

Операция назначения типа информационным сущностям называется типизацией. Назначение и проверка согласования типов может осуществляться заранее (статическая типизация), непосредственно при использовании (динамическая типизация) или совмещать оба метода. Типы могут назначаться «раз и навсегда» (сильная типизация) или позволять себя изменять (слабая типизация) — см. сильная и слабая типизация.

Теория типов формально изучает типы и результаты от их назначения. Неотъемлемой частью большинства языков программирования являются системы типов, использующие типы для обеспечения той или иной степени типобезопасности[en]. Лишь немногие языки могут считаться типизированными в полной мере, большинство языков предоставляет лишь некоторый уровень типизированности.

Понятие типобезопасности[en] опирается преимущественно на процедурное определение типа. Например, попытка деления «числа» на «строку» будет отвергнута большинством языков, так как для этих типов не определено соответствующее поведение. Слабо типизированные языки тяготеют к декларативному определению. Например, «число» и «запись» имеют различное поведение, но значение[en] адреса «записи» в памяти ЭВМ может иметь то же низкоуровневое представление, что и «число». Слабо типизированные языки предоставляют возможность нарушить[en] систему типов, назначив этому значению поведение «числа» посредством операции приведения типа. Подобные трюки могут использоваться для повышения эффективности программ, но несут в себе риск крахов[en], и поэтому не допускаются в безопасных[en] языках.

К не полным по Тьюрингу языкам описания данных (таким как SGML) процедурное определение не применимо.

Единообразная обработка данных разных типов называется полиморфизмом.

Классификация[править | править вики-текст]

Существуют различные классификации типов и правил их назначения.

Например, типы делятся на примитивные и агрегатные (последние также называются составными, композитными или структурными). Примерами примитивных типов служат вещественные, целое, логическое и др. Примерами агрегатных типов служат кортежи, массивы, списки и др. Нередко встречаются также предопределённые вспомогательные типы, полезные для промышленных разработок, такие так «время», «календарная дата» и пр.

Структурные (агрегатные) типы не следует отождествлять со структурами данных: одни структуры данных непосредственно воплощаются определёнными структурными типами, но другие строятся посредством их композиции, чаще всего рекурсивной. В последнем случае говорят о рекурсивных типах данных[en]. Примером структур данных, которые почти всегда строятся посредством композиции объектов рекурсивного типа, являются бинарные деревья.

По другой классификации типы делятся на самостоятельные и зависимые. Важными разновидностями последних являются ссылочные типы, частным случаем которых, в свою очередь, являются указатели. Ссылки (в том числе и указатели) представляют собой несоставной зависимый тип, значения которого являются адресом в памяти ЭВМ другого значения. Например, в языке Си тип «указатель на целое без знака» записывается как «unsigned *», в языке ML тип «ссылка на целое без знака» записывается как «word ref».

Также типы делятся на мономорфные и полиморфные (см. переменная типа).

Примеры[править | править вики-текст]

Самоприменение[править | править вики-текст]

Тип может быть параметризован другим типом, в соответствии с принципами абстракции[en] и параметричности[en]. Например, для реализации функции сортировки последовательностей нет необходимости знать все свойства составляющих её элементов — необходимо лишь, чтобы они допускали операцию сравнения — и тогда составной тип «последовательность» может быть определён как параметрически полиморфный. Это означает, что его компоненты определяются с использованием не конкретных типов (таких как «целое» или «массив целых»), а параметров-типов. Такие параметры называются переменными типа (англ. type variable) — они используются в определении полиморфного типа так же, как параметры-значения в определении функции. Подстановка конкретных типов в качестве фактических параметров для полиморфного типа порождает мономорфный тип. Таким образом, параметрически полиморфный тип представляет собой конструктор типов, то есть оператор над типами в арифметике типов.

Определение функции сортировки как параметрически полиморфной означает, что она сортирует абстрактную последовательность, то есть последовательность из элементов некоторого (неизвестного) типа. Для функции в этом случае требуется знать о своём параметре лишь два свойства — то, что он представляет собой последовательность, и что для её элементов определена операция сравнения. Рассмотрение параметров процедурным, а не декларативным, образом (т.е. их использование на основе поведения, а не значения) позволяет использовать одну функцию сортировки для любых последовательностей — для последовательностей целых чисел, для последовательностей строк, для последовательностей последовательностей булевых значений, и т. д. — и существенно повышает коэффициент повторного использования кода. Ту же гибкость обеспечивает и динамическая типизация, однако, в отличие от параметрического полиморфизма, первая приводит к накладным расходам. Параметрический полиморфизм наиболее развит в языках, типизированных по Хиндли — Милнеру, то есть потомках языка ML. В объектно-ориентированном программировании параметрический полиморфизм принято называть обобщённым программированием.

Несмотря на очевидные преимущества параметрического полиморфизма, порой возникает необходимость обеспечивать различное поведение для разных подтипов[en] одного общего типа, либо аналогичное поведение для несовместимых типов — т.е. в тех или иных формах ad hoc полиморфизма. Однако, ему не существует математического обоснования, так что требование типобезопасности[en] долгое время затрудняло его использование. Ad hoc полиморфизм реализовывался внутри параметрически полиморфной системы типов посредством различных трюков. Для этой цели использовались либо вариантные типы[en], либо параметрические модули (функторы), либо так называемые «значения, индексированные типами» (англ. type-indexed values), которые, в свою очередь, также имеют ряд реализаций[1]. Классы типов[en], появившиеся в языке Haskell, предоставили более изящное решение этой проблемы.

Если рассматриваемой информационной сущностью является тип, то назначение ей типа приведёт к понятию «тип типа», или «метатип». В теории типов это понятие носит название «род типов» (англ. kind of a type или type kind). Например, род «*» включает все типы, а род «* -> *» включает все унарные конструкторы типов. Рода явным образом применяются при полнотиповом программировании — например, в виде конструкторов типов в языках семейства ML.

Расширение безопасной[en] полиморфной системы типов классами[en] и родами типов сделало Haskell первым типизированным в полной мере языком. Полученная система типов оказала влияние на другие языки (например, Scala, Agda).

Ограниченная форма метатипов присутствует также в ряде объектно-ориентированных языков в форме метаклассов. В потомках языка Smalltalk (например, Python) всякая сущность в программе является объектом, имеющим тип, который сам также является объектом — таким образом, метатипы являются естественной частью языка. В языке C++ отдельно от основной системы типов языка реализована подсистема RTTI, также предоставляющая информацию о типе в виде специальной структуры.

Динамическое выяснение метатипов называется отражением (а также рефлексивностью или интроспекцией).

Представление на ЭВМ[править | править вики-текст]

Наиболее заметным отличием реального программирования от формальной теории информации является рассмотрение вопросов эффективности не только в терминах О-нотации, но и с позиций экономической целесообразности воплощения тех или иных требований в физически изготовляемой ЭВМ. И в первую очередь это сказывается на допустимой точности вычислений: понятие «число» на ЭВМ на практике не тождественно понятию числа в арифметике. Число на ЭВМ представляется ячейкой памяти, размер которой определяется архитектурой ЭВМ, и диапазон значений числа ограничивается размером этой ячейки. Например, процессоры архитектуры Intel x86 предоставляют ячейки, размер которых в байтах задаётся степенью двойки: 1, 2, 4, 8, 16 и т. д. Процессоры архитектуры Сетунь предоставляли ячейки, размер которых в трайтах задавался кратным тройке: 1, 3, 6, 9 и т. д.

Попытка записи в ячейку значения, превышающего максимально допустимый для неё предел (который известен) приводит к ошибке переполнения. При необходимости расчётов на более крупных числах используется специальная методика, называемая длинной арифметикой, которая в силу значительной ресурсоёмкости не может осуществляться в реальном времени. Для наиболее распространённых в настоящее время архитектур ЭВМ «родным» является размер ячеек в 32 и 64 бит (то есть 4 и 8 байт).

Кроме того, целые и вещественные числа имеют разное представление в этих ячейках: неотрицательные целые представляются непосредственно, отрицательные целые — в дополнительном коде, а вещественные кодируются особым образом. Из-за этих различий сложение чисел «1» и «0.1», которое в теории даёт значение «1.1», на ЭВМ непосредственно невозможно. Для его осуществления необходимо сперва выполнить преобразование типа, породив на основании значения целого типа «1» новое значение вещественного типа «1.0», и лишь затем сложить «1.0» и «0.1». В силу специфики реализации вещественных чисел на ЭВМ, такое преобразование осуществляется не абсолютно точно, а с некоторой долей приближения. По той же причине сильно типизированные языки (например, Standard ML) рассматривают вещественный тип как «не допускающий проверку на равенство[en]».

Важное значение также имеет понятие о выравнивании данных.


См.также[править | править вики-текст]

Примечания[править | править вики-текст]

Литература[править | править вики-текст]