Типы данных и их польза

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

Оставалось обсудить сложные типы, кототорые живут в высокоуровневых языках. Высокий уровень – это значит по максимуму cпрятать от нас всю работу с памятью и создать уютный мирок из красивых абстракций, где всё логично, просто и строго. Строго – значит мы будем ограничены почти во всём. За этим будет следить уже сам язык.

Объявили переменную char или String – извольте записывать в неё строго символы. Кроме того, если сложить две переменные символьного типа, то в языке С это будет эквивалентно сложению двух чисел и получится просто какое-то новое число (и какой-то новый символ). Да вот даже натурный эксперимент:

‘A’ + ‘B’ = 65+66 = 131 = ‘Г’

А в JavaScript или Python получится:

‘A’ + ‘B’ = ‘AB’

Тут своя логика: если складываются два символа или две строки, то значит их надо соединить. Это уже не числа, а именно строки. И нам, людям, так гораздо привычнее, конечно. И скорее всего, мы именно так и хотели складывать символы. Можно даже написать:

“Hello ” + “world”

На языке C такая операция просто не имеет смысла, а вот JavaScript и Python спокойно сложат строки и мы получим “Hello world”. Правда, чтобы это сделать, им придется выделить память под новую строку и по очереди скопировать в неё содержимое двух исходных строк, так как строки не являются простыми типами. Но это всё будет проделано скрытно от нас, и мы увидим только простой и понятный результат. На то она и высокоуровневость. А в языке C пришлось бы сделать то же самое, но руками и функцией strcpy(). От этого никуда не деться, просто вопрос, кто будет это делать – мы или язык.

Любые массивы, строки, классы и прочее – всё становится самостоятельными, отдельными типами с жестко назначенным для них поведением, которое вы не можете изменить. Менять его и не надо – всё сделано для вашего удобства. В конце концов, складывать строки руками – неудобно.

Массив становится целым классом Array, а что есть у класса? Свойства и методы. Например, возьмем массив в Javascript:

var a = new Array();

Мы создали объект класса Array, и помимо обычного массивного доступа он дает нам возможность пользоваться своими свойствами и методами:

a.length – длина массива
a.push() – добавить новый элемент в массив
a.pop() – удалить элемент из массива
a.fill() – заполнить массив чем-то

и многое другое.

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

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

Как завести число длиной 1 байт? Никак. Если в JavaScript вы написали:

var a = 5;

У вас нет никакого способа сказать, что это число должно быть байтом. Оно будет таким, каким решит язык.

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

Узнайте, какие вспомогательные функции есть в языке. Например, функция char() переводит число в символ. А функция ord() наоборот переводит символ в число. В языке PHP есть функция pack(), которая позволяет построить бинарную строку из данных любого формата.
Узнайте, что умеет сам тип (класс), с которым вы работаете. Если это класс String, то посмотрите, какие у него есть методы (например, charAt(), getBytes() и т.д.) и чем они могут помочь. Может быть и так, что вам надо записать строку задом наперед, а у неё уже есть готовый метод reverse().
Используйте битовые маски для получения нужных вам байт из числа. Например, выражение a & 255 вернёт вам младший байт, а (a >> 8) & 255 – старший.
В последнее время в некоторых языках озаботились производительностью и ввели дополнительные “простые” типы, которые ничем не перегружены. Скажем, в JavaScript это байтовый массив Uint8TypeArray. В Питоне тоже есть нечто подобное. Для повышения производительности по возможности используйте эти типы, а не стандартные.

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Некоторые распространённые типы данных[править | править код]

Логический тип[править | править код]

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

Целочисленные типы[править | править код]

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

Числа с плавающей запятой[править | править код]

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

Строковые типы[править | править код]

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

Указатели[править | править код]

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

Идентификационные типы[править | править код]

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

Абстрактные типы данных[править | править код]

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

Примеры[править | править код]

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

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

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

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

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

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

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

↑ IEEE Std 1320.2-1998 (R2004) IEEE Standard for Conceptual Modeling Language Syntax and Semantics for IDEF1X97:
a set of values and operations on those values
↑ ISO/IEC/IEEE 24765-2010 Systems and software engineering — Vocabulary:
a class of data, characterized by the members of the class and the operations that can be applied to them
↑ IEEE Std 1320.2-1998 (R2004) IEEE Standard for Conceptual Modeling Language Syntax and Semantics for IDEF1X97:
a categorization of an abstract set of possible values, characteristics, and set of operations for an attribute
↑ ISO/IEC 19500-2:2003, Information technology — Open Distributed Processing — Part 2: General Inter-ORB Protocol (GIOP)/Internet Inter-ORB Protocol (IIOP):
a categorization of values operation arguments, typically covering both behavior and representation
↑ С. J. Date. On The Logical Differences Between Types, Values, and Variables // Date on database: Writings 2000—2006, Apress, 2006, ISBN 978-1-59059-746-0
↑ Харрисон Дж. Введение в Функциональное Программирование = https://www.cl.cam.ac.uk/Teaching/Lectures/funprog-jrh-1996/. — 1997. Архивировано 11 января 2015 года.
↑ Strachey, 1967, 3.6.4. Polymorphism, p. 36—37.
↑ Cardelli, 1991, 2. Typeful languages, p. 5.
↑ Дейт К. Дж., 2005.
↑ Type-Indexed Values

Литература[править | править код]

Дейт К. Дж. Введение в системы баз данных = 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.
Лука Карделли[en]. 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.

Источник