Тип данных

В информатике и программировании тип данных (или просто тип ) — это набор или группировка значений данных, обычно определяемых набором возможных значений, набором разрешенных операций над этими значениями и/или представлением этих значений в виде машинных типов. ^[1] Спецификация типа данных в программе ограничивает возможные значения, которые может принимать выражение , например переменная или вызов функции. В случае литеральных данных она сообщает компилятору или интерпретатору , как программист намерен использовать данные. Большинство языков программирования поддерживают базовые типы данных: целые числа (различных размеров), числа с плавающей точкой (которые аппроксимируют действительные числа ), символы и логические значения . ^[2]^[3]

Концепция

Тип данных может быть указан по многим причинам: сходство, удобство или для привлечения внимания. Часто это вопрос хорошей организации, которая помогает пониманию сложных определений. Почти все языки программирования явно включают понятие типа данных, хотя возможные типы данных часто ограничены соображениями простоты, вычислимости или регулярности. Явное объявление типа данных обычно позволяет компилятору выбрать эффективное машинное представление, но концептуальную организацию, предлагаемую типами данных, не следует сбрасывать со счетов. ^[4]

Различные языки могут использовать различные типы данных или похожие типы с различной семантикой. Например, в языке программирования Pythonint представляет собой целое число произвольной точности , которое имеет традиционные числовые операции, такие как сложение, вычитание и умножение. Однако в языке программирования Java тип intпредставляет собой набор 32-битных целых чисел в диапазоне значений от −2 147 483 648 до 2 147 483 647 с арифметическими операциями, которые переходят при переполнении . В Rust этот 32-битный целочисленный тип обозначается i32и вызывает панику при переполнении в режиме отладки. ^[5]

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

Типы данных используются в системах типов , которые предлагают различные способы их определения, реализации и использования. В системе типов тип данных представляет собой ограничение, накладываемое на интерпретацию данных, описывающее представление, интерпретацию и структуру значений или объектов, хранящихся в памяти компьютера. Система типов использует информацию о типе данных для проверки корректности компьютерных программ , которые обращаются к данным или манипулируют ими. Компилятор может использовать статический тип значения для оптимизации необходимого ему хранилища и выбора алгоритмов для операций над значением. Во многих компиляторах Cfloat тип данных, например, представлен в 32 битах в соответствии со спецификацией IEEE для чисел с плавающей точкой одинарной точности . Таким образом, они будут использовать операции микропроцессора , специфичные для чисел с плавающей точкой, над этими значениями (сложение с плавающей точкой, умножение и т. д.).

Большинство типов данных в статистике имеют сопоставимые типы в компьютерном программировании, и наоборот, как показано в следующей таблице:

Определение

Парнас, Шор и Вайс (1976) выделили пять определений «типа», которые использовались — иногда неявно — в литературе:

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

Определение в терминах представления часто делалось в императивных языках, таких как ALGOL и Pascal , в то время как определение в терминах пространства значений и поведения использовалось в языках более высокого уровня, таких как Simula и CLU . Типы, включающие поведение, более тесно связаны с объектно-ориентированными моделями, тогда как структурированная модель программирования, как правило, не включает код и называется простыми старыми структурами данных .

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

Типы данных можно классифицировать по нескольким факторам:

Примитивные типы данных или встроенные типы данных — это типы, встроенные в реализацию языка. Пользовательские типы данных — это непримитивные типы. Например, числовые типы Java являются примитивными, а классы — определяемыми пользователем.
Значение атомарного типа — это отдельный элемент данных, который нельзя разбить на составные части. Значение составного типа или агрегатного типа — это набор элементов данных, к которым можно получить доступ по отдельности. ^[6] Например, целое число обычно считается атомарным, хотя оно состоит из последовательности битов, в то время как массив целых чисел, безусловно, является составным.
Базовые типы данных или фундаментальные типы данных определяются аксиоматически из фундаментальных понятий или перечислением их элементов. Сгенерированные типы данных или производные типы данных указываются и частично определяются в терминах других типов данных. Все базовые типы являются атомарными. ^[7] Например, целые числа являются базовым типом, определенным в математике, в то время как массив целых чисел является результатом применения генератора типа массива к целочисленному типу.

Терминология варьируется — в литературе взаимозаменяемо могут использоваться термины «примитивный», «встроенный», «базовый», «атомарный» и «фундаментальный». ^[8]

Примеры

Типы машинных данных

Все данные в компьютерах на основе цифровой электроники представлены в виде битов (варианты 0 и 1) на самом низком уровне. Наименьшая адресуемая единица данных обычно представляет собой группу битов, называемых байтом (обычно октет , который составляет 8 бит). Единица, обрабатываемая инструкциями машинного кода , называется словом (по состоянию на 2011 год ^{[обновлять]}[ ^{нужно обновить ]} обычно 32 или 64 бита).

Типы машинных данных раскрывают или делают доступным мелкозернистый контроль над оборудованием, но это также может раскрыть детали реализации, которые делают код менее переносимым. Следовательно, типы машин в основном используются в системном программировании или языках программирования низкого уровня . В языках более высокого уровня большинство типов данных абстрагированы в том смысле, что они не имеют машинного представления, определяемого языком. Например, язык программирования C предоставляет такие типы, как булевы значения, целые числа, числа с плавающей точкой и т. д., но точные битовые представления этих типов определяются реализацией. Единственный тип C с точным машинным представлением — это charтип, представляющий байт. ^[9]

Булев тип

Тип Boolean представляет значения true и false . Хотя возможны только два значения, они чаще представляются как слово, а не как один бит, поскольку для хранения и извлечения отдельного бита требуется больше машинных инструкций. Во многих языках программирования нет явного типа Boolean, вместо этого используется целочисленный тип и интерпретируется (например) 0 как false, а другие значения как true. Булевы данные относятся к логической структуре того, как язык интерпретируется в машинном языке. В этом случае Boolean 0 относится к логике False. True всегда не равен нулю, особенно тот, который известен как Boolean 1.

Числовые типы

Почти все языки программирования предоставляют один или несколько целочисленных типов данных. Они могут либо предоставлять небольшое количество предопределенных подтипов, ограниченных определенными диапазонами (например, shortи longи их соответствующие unsignedварианты в C/C++); или позволять пользователям свободно определять поддиапазоны, такие как 1..12 (например, Pascal / Ada ). Если соответствующий собственный тип не существует на целевой платформе, компилятор разобьет их на код, используя типы, которые существуют. Например, если 32-битное целое число запрашивается на 16-битной платформе, компилятор будет молчаливо рассматривать его как массив из двух 16-битных целых чисел.

Типы данных с плавающей точкой представляют собой определенные дробные значения ( рациональные числа , математически). Хотя они имеют предопределенные ограничения как на максимальные значения, так и на точность, их иногда ошибочно называют вещественными (вызывая ассоциации с математическими вещественными числами ). Обычно они хранятся внутри в виде $a \times 2 b$ (где $a$ и $b$ — целые числа), но отображаются в привычной десятичной форме.

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

Для независимости от деталей архитектуры может быть предоставлен тип Bignum или произвольной точности numeric . Он представляет целое или рациональное число с точностью, ограниченной только доступной памятью и вычислительными ресурсами системы. Реализации Bignum арифметических операций над значениями машинного размера значительно медленнее соответствующих машинных операций. ^[10]

Перечисления

Перечислимый тип имеет различные значения, которые можно сравнивать и назначать, но которые не обязательно имеют какое-либо конкретное представление в памяти компьютера; компиляторы и интерпретаторы могут представлять их произвольно. Например, четыре масти в колоде игральных карт могут быть четырьмя перечислителями с именами CLUB , DIAMOND , HEART , SPADE , принадлежащими перечислимому типу с именем suit . Если переменная V объявлена с типом данных suit , ей можно присвоить любое из этих четырех значений. Некоторые реализации позволяют программистам присваивать целочисленные значения значениям перечисления или даже рассматривать их как эквивалентные по типу целым числам.

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

Строки — это последовательность символов , используемая для хранения слов или обычного текста , чаще всего текстовых языков разметки, представляющих форматированный текст . Символы могут быть буквой некоторого алфавита , цифрой, пробелом, знаком препинания и т. д. Символы берутся из набора символов, такого как ASCII . Типы символов и строк могут иметь различные подтипы в зависимости от кодировки символов. Первоначальный 7-битный ASCII оказался ограниченным и был заменен 8-, 16- и 32-битными наборами, которые могут кодировать широкий спектр нелатинских алфавитов (например, иврит и китайский ) и других символов. Строки могут иметь как переменную, так и фиксированную длину, и некоторые языки программирования имеют оба типа. Они также могут быть подтипированы по их максимальному размеру.

Поскольку большинство наборов символов включают цифры , возможно наличие числовой строки, например "1234". Эти числовые строки обычно считаются отличными от числовых значений, например 1234, хотя некоторые языки автоматически преобразуют их.

Типы союзов

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

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

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

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

Если есть только один конструктор, то ADT соответствует типу продукта, похожему на кортеж или запись. Конструктор без полей соответствует пустому продукту (тип единицы). Если все конструкторы не имеют полей, то ADT соответствует перечислимому типу .

Одним из распространенных АТД является тип опции , определенный в Haskell как . ^[11]data Maybe a = Nothing | Just a

Структуры данных

Некоторые типы очень полезны для хранения и извлечения данных и называются структурами данных . Общие структуры данных включают:

Массив (также называемый вектором, списком или последовательностью) хранит ряд элементов и обеспечивает произвольный доступ к отдельным элементам. Элементы массива обычно (но не во всех контекстах) должны быть одного типа. Массивы могут быть фиксированной длины или расширяемыми. Индексы в массиве обычно должны быть целыми числами (если нет, можно подчеркнуть это ослабление, говоря об ассоциативном массиве ) из определенного диапазона (если не все индексы в этом диапазоне соответствуют элементам, это может быть разреженный массив ).
Запись (также называемая кортежем или структурой) Записи являются одними из самых простых структур данных . Запись — это значение, которое содержит другие значения, обычно в фиксированном количестве и последовательности и обычно индексируется по именам. Элементы записей обычно называются полями или членами .
Объект содержит ряд полей данных, как и запись, а также предлагает ряд подпрограмм для доступа к ним или их изменения, называемых методами .
односвязный список , который может быть использован для реализации очереди и определен в Haskell как ADT , иdata List a = Nil | Cons a (List a)
двоичное дерево , которое обеспечивает быстрый поиск и может быть определено в Haskell как ADT ^[12]data BTree a = Nil | Node (BTree a) a (BTree a)

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

Абстрактный тип данных — это тип данных, который не определяет конкретное представление данных. Вместо этого для его описания используется формальная спецификация, основанная на операциях типа данных. Любая реализация спецификации должна соответствовать заданным правилам. Например, стек имеет операции push/pop, которые следуют правилу Last-In-First-Out, и может быть конкретно реализован с использованием списка или массива. Абстрактные типы данных используются в формальной семантике и проверке программ и, менее строго, в проектировании .

Указатели и ссылки

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

Типы функций

Функциональные языки программирования рассматривают функции как отдельный тип данных и позволяют хранить значения этого типа в переменных и передавать их функциям. Некоторые многопарадигмальные языки, такие как JavaScript, также имеют механизмы для рассмотрения функций как данных. ^[13] Большинство современных систем типов выходят за рамки простого типа JavaScript «объект функции» и имеют семейство типов функций, различающихся по типам аргументов и возвращаемых значений, например, тип, Int -> Boolобозначающий функции, принимающие целое число и возвращающие логическое значение. В языке C функция не является типом данных первого класса, но указатели функций могут манипулироваться программой. Java и C++ изначально не имели значений функций, но добавили их в C++11 и Java 8.

Конструкторы типов

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

Количественные типы

Универсально-квантифицированные и экзистенциально-квантифицированные типы основаны на логике предикатов . Универсальная квантификация записывается как или и является пересечением по всем типам тела , т.е. значение имеет тип для каждого . Экзистенциальная квантификация записывается как или и является объединением по всем типам тела , т.е. значение имеет тип для некоторого . $\forall xf(x)$ forall x. f xxf xf xx $\exists xf(x)$ exists x. f xxf xf xx

В Haskell обычно используется универсальная квантификация, но экзистенциальные типы должны быть закодированы путем преобразования exists a. f aв forall r. (forall a. f a -> r) -> rили аналогичный тип.

Типы уточнений

Тип уточнения — это тип, наделенный предикатом, который предполагается верным для любого элемента уточненного типа. Например, тип натуральных чисел больше 5 может быть записан как $\{n\in \mathbb {N} \,|\,n>5\}$

Зависимые типы

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

Типы пересечений

Тип пересечения — это тип, содержащий те значения, которые являются членами двух указанных типов. Например, в Java класс Booleanреализует как интерфейсы , так Serializableи Comparableинтерфейсы . Следовательно, объект типа Booleanявляется членом типа Serializable & Comparable. Рассматривая типы как множества значений, тип пересечения является теоретико- множественным пересечением и . Также возможно определить зависимый тип пересечения, обозначаемый , где тип может зависеть от переменной терма . ^[14] $\sigma \cap \tau$ $\sigma$ $\tau$ $(x:\sigma )\cap \tau$ $\tau$ $x$

Мета-типы

Некоторые языки программирования представляют информацию о типе как данные, что позволяет проводить интроспекцию и рефлексию типов . Напротив, системы типов более высокого порядка , хотя и позволяют создавать типы из других типов и передавать их в функции как значения, обычно избегают основывать на них вычислительные решения. ^[^{необходима цитата}^]

Типы удобств

Для удобства высокоуровневые языки и базы данных могут предоставлять готовые типы данных «реального мира», например, время, даты и денежные значения (валюта). ^[15]^[16] Они могут быть встроены в язык или реализованы как составные типы в библиотеке. ^[17]

Смотрите также

Типы данных C
Словарь данных
Добрый
Тип (теория модели)
Теория типов для математических моделей типов
Преобразование типов
ISO/IEC 11404 , Типы данных общего назначения

Ссылки

^ Парнас, Шор и Вайс 1976.
^ наберите в бесплатном онлайн-словаре по вычислительной технике
^ Шаффер, Калифорния (2011). Структуры данных и анализ алгоритмов в C++ (3-е изд.). Минеола, Нью-Йорк: Довер. 1.2. ISBN 978-0-486-48582-9.
^ Скотт, Дана (сентябрь 1976 г.). «Типы данных как решетки». Журнал SIAM по вычислениям . 5 (3): 540–541. doi :10.1137/0205037.
^ "Rust RFCs - Integer Overflow". Язык программирования Rust. 12 августа 2022 г.
^ Дейл, Нелл Б.; Вимс, Чип; Хедингтон, Марк Р. (1998). Программирование на C++. Jones & Bartlett Learning. стр. 349. ISBN 978-0-7637-0537-4.
^ ИСО/МЭК 11404 , 6.4
^ БХАТНАГАР, СИМА (19 августа 2008 г.). УЧЕБНИК ИНФОРМАТИКИ ДЛЯ XI КЛАССА. PHI Learning Pvt. Ltd. стр. 182. ISBN 978-81-203-2993-5.
^ "SC22/WG14 N2176" (PDF) . Wayback Machine. Раздел 6.2.6.2. Архивировано из оригинала (PDF) 30 декабря 2018 г. Какой из [знак и величина, дополнение до двух, дополнение до единицы] применяется, определяется реализацией
^ "Целочисленные тесты — документация mp++ 0.27". bluescarni.github.io .
^ "6 предопределенных типов и классов". www.haskell.org . Получено 2022-06-15 .
^ Суреш, С. П. "Программирование на языке Haskell: Лекция 22" (PDF) . Математический институт Ченнаи . Получено 10 августа 2022 г. .
^ Фланаган, Дэвид (1997). "6.2 Функции как типы данных". JavaScript: полное руководство (2-е изд.). Кембридж: O'Reilly & Associates. ISBN 9781565922341.
^ Копылов, Алексей (2003). «Зависимое пересечение: новый способ определения записей в теории типов». 18-й симпозиум IEEE по логике в компьютерных науках . LICS 2003. IEEE Computer Society. стр. 86–95. CiteSeerX 10.1.1.89.4223 . doi :10.1109/LICS.2003.1210048.
^ Уэст, Рэндольф (27 мая 2020 г.). «Как SQL Server хранит типы данных: деньги». Родился SQL . Получено 28 января 2022 г. Некоторое время назад я описал MONEY как «удобный» тип данных, который по сути то же самое, что и DECIMAL(19,4), [...]
^ "Введение в типы данных и свойства полей". support.microsoft.com . Получено 28 января 2022 г. .
^ Уикхэм, Хэдли (2017). «16 дат и времени». R для науки о данных: импорт, очистка, преобразование, визуализация и моделирование данных . Севастополь, Калифорния. ISBN 978-1491910399. Получено 28 января 2022 г. .{{cite book}}: CS1 maint: location missing publisher (link)

Дальнейшее чтение

Парнас, Дэвид Л .; Шор, Джон Э.; Вайс, Дэвид (1976). «Абстрактные типы, определяемые как классы переменных». Труды конференции 1976 года по данным: абстракция, определение и структура - . стр. 149–154. doi : 10.1145/800237.807133 . S2CID 14448258.
Cardelli, Luca ; Wegner, Peter (декабрь 1985 г.). «On Understanding Types, Data Abstraction, and Polymorphism» (PDF) . ACM Computing Surveys . 17 (4): 471–523. CiteSeerX 10.1.1.117.695 . doi :10.1145/6041.6042. ISSN 0360-0300. S2CID 2921816. Архивировано (PDF) из оригинала 2008-12-03.
Кливленд, Дж. Крейг (1986). Введение в типы данных . Addison-Wesley. ISBN 978-0201119404.

Внешние ссылки

Медиа, связанные с типами данных на Wikimedia Commons