Тип данных (Mnh ;guud])

Тип данных (тип) — множество значений и операций над этими значениями (IEEE Std 1320.2-1998).

Другие определения:

• Тип данных — класс данных, характеризуемый членами класса и операциями, которые могут быть к ним применены (ISO/IEC/IEEE 24765-2010).
• Тип данных — категоризация абстрактного множества возможных значений, характеристик и набор операций для некоторого атрибута (IEEE Std 1320.2-1998).
• Тип данных — категоризация аргументов операций над значениями, как правило, охватывающая как поведение, так и представление (ISO/IEC 19500-2:2003).
• Тип данных — множество допустимых значений (ISO/IEC 9075-1:2023).

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

Определение

Тип данных характеризует одновременно:

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

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

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

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

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

Типы позволяют избежать парадокса Рассела, в частности, Чёрч ввёл типы в лямбда-исчисление именно с этой целью.

В естественном языке за типизацию отвечают вопросительные местоимения.

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

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

Классификация

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

По аналогии с математикой, типы данных делят на скалярные (примитивные) и нескалярные (агрегатные). Значение нескалярного типа (нескалярное значение) имеет множество видимых пользователю компонентов, а значение скалярного типа (скалярное значение) не имеет такового. Примерами нескалярного типа являются массивы, списки и т. д.; примеры скалярного типа — «целое», «логическое» и т. д.

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

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

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

Некоторые распространённые типы данных

Логический тип

Основная статья: Логический тип

Логические, или булевы значения (по фамилии их изобретателя — Буля), могут иметь лишь одно из двух состояний — «истина» или «ложь». В разных языках обозначаются bool, BOOL, или boolean. «Истина» может обозначаться как true, TRUE или #T. «Ложь», соответственно, false, FALSE или #F. В языках C и C++ любое ненулевое число трактуется как «истина», а ноль — как «ложь». В Python некоторым единичным типам также назначается то или иное «логическое значение». В принципе, для реализации типа достаточно одного бита, однако из-за особенностей микропроцессоров, на практике размер булевых величин обычно равен размеру машинного слова.

Целочисленные типы

Основная статья: Целочисленный тип

Целочисленные типы содержат в себе значения, интерпретируемые как числа (знаковые и беззнаковые).

Числа с плавающей запятой

Основная статья: Числа с плавающей запятой

Используются для представления вещественных (не обязательно целых) чисел. В этом случае число записывается в виде x=a*10^b. Где 0<=a<1, а b — некоторое целое число из определённого диапазона. a называют мантиссой, b — порядком. У мантиссы хранятся несколько цифр после запятой, а b — хранится полностью.

Строковые типы

Основная статья: Строковый тип

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

Указатели

Основная статья: Указатель (тип данных)

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

Идентификационные типы

Идентификационные типы интерпретируются не как число, а как уникальный идентификатор объекта. Например, FourCC.

Абстрактные типы данных

Основная статья: Абстрактный тип данных

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

Примеры

• примитивные типы, в том числе:
  • логический тип
  • целые типы
  • вещественные типы
• ссылочные типы
• опциональные типы
  • обнуляемые типы
• Композитные типы, в том числе:
  • массивы
  • записи
  • кортежи
  • абстрактные типы (АТД, англ. ADT)
• алгебраические типы
  • вариантные типы
• подтипы
• унаследованные типы
• объектные типы, то есть объекты, значением которых являются типы — например, переменные типов
• частичные типы
• рекурсивные типы
• функциональные типы, например бинарные функции
• универсально квантифицированные типы, такие как параметрические типы
• экзистенциально квантифицированные, такие как модули
• зависимые типы — типы, зависящие от термов (значений)
• уточняющие типы — типы, идентифицирующие подмножества других типов
• Предопределённые типы (являющиеся фактически структурными, но предоставляемые на правах примитивных) для удобства промышленных разработок, такие как «дата», «время», «валюта» и др.

Самоприменение

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

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

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

Подробнее см. Класс типов

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

Подробнее см. Род (теория типов)

Расширение безопасной полиморфной системы типов классами и родами типов сделало 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) рассматривают вещественный тип как equality types (или identity types) (Equality type).

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

Литература

• Дейт К. Дж. Введение в системы баз данных = Introduction to Database Systems. — 8-е изд. — М.: Вильямс, 2005. — 1328 с. — ISBN 5-8459-0788-8 (рус.) 0-321-19784-4 (англ.).
• C. Strachey. Fundamental Concepts in Programming Languages. — 1967. Архивировано 12 августа 2017 года.
• Luca Cardelli, Peter Wegner. On Understanding Types, Data Abstraction, and Polymorphism. — ACM Computing Surveys, 1985. — С. 471—523. — ISSN 0360-0300.
• Лука Карделли. Typeful programming (англ.) // IFIP State-of-the-Art Reports. — Springer-Verlag, 1991. — Iss. Formal Description of Programming Concepts. — P. 431–507.
• Pierce, Benjamin C. Types and Programming Languages. — MIT Press, 2002. — ISBN 0-262-16209-1.
  • Перевод на русский язык: Пирс Б. Типы в языках программирования. — Добросвет, 2012. — 680 с. — ISBN 978-5-7913-0082-9.
• Luca Cardelli. CRC Handbook of Computer Science and Engineering. — 2nd. — CRC Press, 2004. — ISBN 158488360X.
• Zhe Yang. Encoding Types in ML-like Languages. — Department of Computer Science, New York University, (c) ACM, 1998.