Тип данных

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

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

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

Определение[править | править вики-текст]

Тип информационной сущности характеризует одновременно:

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

Первое свойство можно рассматривать как теоретико-множественное определение понятия типа; второе — как процедурное (или поведенческое) определение.

Кроме этого, в программировании используется низкоуровневое определение типа — как заданных размерных и структурных характеристик ячейки памяти, в которую можно поместить некое значение, соответствующее этим характеристикам. Такое определение является частным случаем теоретико-множественного. На практике, с ним связан ряд важных свойств, требующих отдельного рассмотрения[⇨].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Расширение безопасной полиморфной системы типов классами[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]».

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


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

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