Тип системы

Концепция компьютерной науки

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

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

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

Основная цель системы типов в языке программирования — уменьшить вероятность возникновения ошибок в компьютерных программах из-за ошибок типов . ^[2] Данная рассматриваемая система типов определяет, что представляет собой ошибка типа, но в целом ее цель — предотвратить использование операций, ожидающих определенный вид значения, со значениями, для которых эта операция не имеет смысла (ошибки допустимости).

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

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

Обзор использования

Примером простой системы типов является язык C. Части программы на языке C являются определениями функций . Одна функция вызывается другой функцией.

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

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

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

Компилятор C проверяет типы аргументов, переданных функции при ее вызове, на соответствие типам параметров, объявленных в определении функции. Если типы не совпадают, компилятор выдает ошибку или предупреждение времени компиляции.

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

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

Основы

Формально, теория типов изучает системы типов. Язык программирования должен иметь возможность проверки типов с использованием системы типов , будь то во время компиляции или выполнения, вручную аннотированной или автоматически выведенной. Как кратко выразился Марк Манасс: ^[3]

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

Назначение типа данных, называемое типизацией , придает значение последовательности битов , такой как значение в памяти или некоторый объект , такой как переменная . Аппаратное обеспечение компьютера общего назначения не способно различать, например, адрес памяти и код инструкции или символ , целое число или число с плавающей точкой , поскольку оно не делает внутреннего различия между любыми возможными значениями, которые может означать последовательность битов . ^{[примечание 1]} Связывание последовательности битов с типом передает это значение программируемому оборудованию для формирования символической системы, состоящей из этого оборудования и некоторой программы.

Программа связывает каждое значение по крайней мере с одним определенным типом, но также может случиться, что одно значение связано со многими подтипами . Другие сущности, такие как объекты , модули , каналы связи и зависимости , могут стать связанными с типом. Даже тип может стать связанным с типом. Реализация системы типов теоретически может связывать идентификации, называемые типом данных (типом значения), классом (типом объекта) и видом ( типом типа или метатипом). Это абстракции, через которые может проходить типизация в иерархии уровней, содержащихся в системе.

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

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

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

• Абстракция (или модульность ) – типы позволяют программистам мыслить на более высоком уровне, чем бит или байт, не беспокоясь о низкоуровневой реализации. Например, программисты могут начать думать о строке как о наборе значений символов, а не как о простом массиве байтов. Еще выше, типы позволяют программистам думать об интерфейсах между двумя подсистемами любого размера и выражать их. Это обеспечивает больше уровней локализации, так что определения, необходимые для взаимодействия подсистем, остаются согласованными, когда эти две подсистемы взаимодействуют.
• Документация – В более выразительных системах типов типы могут служить формой документации, разъясняющей намерения программиста. Например, если программист объявляет функцию как возвращающую тип временной метки, это документирует функцию, когда тип временной метки может быть явно объявлен глубже в коде как целочисленный тип.

Преимущества, предоставляемые системами типов, определяемыми компилятором, включают в себя:

• Оптимизация – статическая проверка типов может предоставить полезную информацию во время компиляции . Например, если тип требует, чтобы значение было выровнено в памяти на кратном четырем байтам, компилятор может использовать более эффективные машинные инструкции.
• Безопасность – Система типов позволяет компилятору обнаруживать бессмысленный или недействительный код. Например, мы можем определить выражение 3 / "Hello, World"как недействительное, когда правила не определяют, как делить целое число на строку . Строгая типизация обеспечивает большую безопасность, но не может гарантировать полную безопасность типов .

Ошибки типа

Ошибка типа возникает, когда операция получает другой тип данных, чем ожидалось. ^[4] Например, ошибка типа может возникнуть, если строка кода делит два целых числа и вместо целого числа передается строка букв. ^[4] Это непреднамеренное состояние ^{[примечание 2],} которое может проявиться на нескольких этапах разработки программы. Таким образом, в системе типов необходимо средство для обнаружения ошибки. В некоторых языках, таких как Haskell , для которых вывод типа автоматизирован, lint может быть доступен его компилятору для помощи в обнаружении ошибки.

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

Проверка типа

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

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

Эти термины обычно не используются в строгом смысле.

Статическая проверка типов

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

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

Статическая проверка типов для языков, полных по Тьюрингу, по своей сути консервативна. То есть, если система типов является одновременно надежной (то есть она отклоняет все некорректные программы) и разрешимой (то есть можно написать алгоритм, который определяет, является ли программа хорошо типизированной), то она должна быть неполной (то есть существуют корректные программы, которые также отклоняются, хотя они и не сталкиваются с ошибками времени выполнения). ^[7] Например, рассмотрим программу, содержащую код:

if <complex test> then <do something> else <signal that there is a type error>

Даже если выражение <complex test>всегда оценивается как trueво время выполнения, большинство средств проверки типов отклонят программу как плохо типизированную, поскольку статическому анализатору сложно (если не невозможно) определить, что ветвь elseне будет взята. ^[8] Следовательно, средство проверки статических типов быстро обнаружит ошибки типов в редко используемых путях кода. Без статической проверки типов даже тесты покрытия кода со 100% покрытием могут не обнаружить такие ошибки типов. Тесты могут не обнаружить такие ошибки типов, поскольку необходимо учитывать комбинацию всех мест, где создаются значения, и всех мест, где используется определенное значение.

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

Многие языки со статической проверкой типов предоставляют способ обойти проверку типов. Некоторые языки позволяют программистам выбирать между статической и динамической безопасностью типов. Например, исторически C# объявляет переменные статически, ^{[9] : 77, Раздел 3.2,} но C# 4.0 вводит dynamicключевое слово, которое используется для объявления переменных, проверяемых динамически во время выполнения. ^{[9] : 117, Раздел 4.1} Другие языки позволяют писать код, который не является типобезопасным; например, в C программисты могут свободно приводить значение между любыми двумя типами, имеющими одинаковый размер, эффективно подрывая концепцию типа.

Список языков со статической проверкой типов см. в категории статически типизированные языки .

Динамическая проверка типов и информация о типах во время выполнения

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

Большинство языков с безопасной типизацией включают некоторую форму динамической проверки типов, даже если у них также есть статическая проверка типов. ^[10] Причина этого в том, что многие полезные функции или свойства трудно или невозможно проверить статически. Например, предположим, что программа определяет два типа, A и B, где B является подтипом A. Если программа пытается преобразовать значение типа A в тип B, что известно как приведение типов , то операция является допустимой только в том случае, если преобразуемое значение на самом деле является значением типа B. Таким образом, для проверки безопасности операции необходима динамическая проверка. Это требование является одним из критических замечаний по отношению к приведению типов.

По определению, динамическая проверка типов может привести к сбою программы во время выполнения. В некоторых языках программирования можно предвидеть и восстановиться после этих сбоев. В других ошибки проверки типов считаются фатальными.

Языки программирования, включающие динамическую проверку типов, но не статическую проверку типов, часто называют «динамически типизированными языками программирования». Список таких языков см. в категории динамически типизированные языки программирования .

Объединение статической и динамической проверки типов

Некоторые языки допускают как статическую, так и динамическую типизацию. Например, Java и некоторые другие якобы статически типизированные языки поддерживают приведение типов к их подтипам , запрашивая объект для обнаружения его динамического типа и других операций с типами, которые зависят от информации о типе времени выполнения. Другим примером является C++ RTTI . В более общем плане большинство языков программирования включают механизмы для диспетчеризации по различным «видам» данных, таким как непересекающиеся объединения , полиморфизм времени выполнения и варианты типов . Даже не взаимодействуя с аннотациями типов или проверкой типов, такие механизмы по сути аналогичны реализациям динамической типизации. См. язык программирования для более подробного обсуждения взаимодействия между статической и динамической типизацией.

Объекты в объектно-ориентированных языках обычно доступны по ссылке, статический целевой тип (или тип манифеста) которой равен либо типу времени выполнения объекта (его скрытому типу), либо его супертипу. Это соответствует принципу подстановки Лисков , который гласит, что все операции, выполняемые над экземпляром данного типа, могут также выполняться над экземпляром подтипа. Эта концепция также известна как полиморфизм подчинения или подтипа . В некоторых языках подтипы могут также обладать ковариантными или контравариантными возвращаемыми типами и типами аргументов соответственно.

Некоторые языки, например, Clojure , Common Lisp или Cython , по умолчанию динамически проверяют типы, но позволяют программам выбирать статическую проверку типов, предоставляя необязательные аннотации. Одной из причин использования таких подсказок может быть оптимизация производительности критических разделов программы. Это формализуется путем постепенной типизации. Среда программирования DrRacket , педагогическая среда на основе Lisp и предшественник языка Racket , также имеет мягкую типизацию. ^[11]

Наоборот, начиная с версии 4.0, язык C# предоставляет способ указать, что переменная не должна быть статически проверена на тип. Переменная, тип которой dynamicне будет подвергаться статической проверке типа. Вместо этого программа полагается на информацию о типе времени выполнения, чтобы определить, как переменная может быть использована. ^{[12] [9] : 113–119}

В Rust тип обеспечивает динамическую типизацию типов. ^[13]dyn std::any::Any'static

Статическая и динамическая проверка типов на практике

Выбор между статической и динамической типизацией требует определенных компромиссов .

Статическая типизация может надежно находить ошибки типов во время компиляции, что повышает надежность поставляемой программы. Однако программисты расходятся во мнениях относительно того, как часто возникают ошибки типов, что приводит к дальнейшим разногласиям относительно доли тех ошибок, которые закодированы, которые будут обнаружены при соответствующем представлении спроектированных типов в коде. ^{[14] [15]} Сторонники статической типизации ^{[ who? ]} считают, что программы более надежны, когда они хорошо проверены на тип, тогда как сторонники динамической типизации ^{[ who? ]} указывают на распределенный код, который доказал свою надежность, и на небольшие базы данных ошибок. ^{[ необходима цитата ]} Ценность статической типизации возрастает по мере увеличения прочности системы типов. Сторонники зависимой типизации [ ^{who ? ]} реализованной в таких языках, как Dependent ML и Epigram , предположили, что почти все ошибки можно считать ошибками типов, если типы, используемые в программе, правильно объявлены программистом или правильно выведены компилятором. ^[16]

Статическая типизация обычно приводит к скомпилированному коду, который выполняется быстрее. Когда компилятор знает точные типы данных, которые используются (что необходимо для статической проверки, либо через объявление, либо через вывод), он может создать оптимизированный машинный код. Некоторые динамически типизированные языки, такие как Common Lisp, допускают необязательные объявления типов для оптимизации по этой причине.

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

Статически типизированные языки, в которых отсутствует вывод типов (например, C и Java до версии 10 ), требуют, чтобы программисты объявляли типы, которые должен использовать метод или функция. Это может служить дополнительной документацией программы, которая является активной и динамической, а не статической. Это позволяет компилятору предотвратить ее отклонение от синхронности и игнорирование программистами. Однако язык может быть статически типизирован без необходимости объявления типов (примеры включают Haskell , Scala , OCaml , F# , Swift и в меньшей степени C# и C++ ), поэтому явное объявление типа не является необходимым требованием для статической типизации во всех языках.

Динамическая типизация позволяет использовать конструкции, которые некоторые (простые) статические проверки типов отвергли бы как незаконные. Например, функции eval , которые выполняют произвольные данные как код, становятся возможными. Функция eval возможна при статической типизации, но требует расширенного использования алгебраических типов данных . Кроме того, динамическая типизация лучше подходит для переходного кода и прототипирования, например, позволяя прозрачно использовать структуру данных-заполнителя ( фиктивный объект ) вместо полной структуры данных (обычно для целей экспериментирования и тестирования).

Динамическая типизация обычно допускает утиную типизацию (что позволяет упростить повторное использование кода ). Многие ^{[ указать ]} языки со статической типизацией также поддерживают утиную типизацию или другие механизмы, такие как обобщенное программирование , которые также позволяют упростить повторное использование кода.

Динамическая типизация обычно упрощает использование метапрограммирования . Например, шаблоны C++ обычно более громоздки для написания, чем эквивалентный код Ruby или Python , поскольку C++ имеет более строгие правила относительно определений типов (как для функций, так и для переменных). Это заставляет разработчика писать больше шаблонного кода для шаблона, чем это потребовалось бы разработчику Python. Более продвинутые конструкции времени выполнения, такие как метаклассы и интроспекция, часто сложнее использовать в статически типизированных языках. В некоторых языках такие функции также могут использоваться, например, для генерации новых типов и поведений на лету на основе данных времени выполнения. Такие продвинутые конструкции часто предоставляются динамическими языками программирования ; многие из них являются динамически типизированными, хотя динамическая типизация не обязательно связана с динамическими языками программирования .

Системы сильного и слабого типа

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

Безопасность типов и безопасность памяти

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

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

Рассмотрим следующую программу на языке, который является как типобезопасным, так и безопасным по отношению к памяти: ^[17]

вар х := 5; переменная y := "37";вар z := x + y;

В этом примере переменная zбудет иметь значение 42. Хотя это может быть не то, что ожидал программист, это хорошо определенный результат. Если бы yэто была другая строка, та, которую нельзя преобразовать в число (например, "Hello World"), результат также был бы хорошо определен. Обратите внимание, что программа может быть типобезопасной или безопасна для памяти и все равно давать сбой при недопустимой операции. Это касается языков, в которых система типов недостаточно развита, чтобы точно указать допустимость операций для всех возможных операндов. Но если программа сталкивается с операцией, которая не является типобезопасной, завершение программы часто является единственным вариантом.

Теперь рассмотрим аналогичный пример на языке C:

int x = 5 ; char y [] = "37" ; char * z = x + y ; printf ( "%c \n " , * z );            

В этом примере zбудет указывать на адрес памяти на пять символов дальше y, что эквивалентно трем символам после завершающего нулевого символа строки, на которую указывает y. Это память, к которой программа не должна иметь доступа. В терминах C это просто неопределенное поведение , и программа может делать что угодно; с простым компилятором она может фактически вывести любой байт, сохраненный после строки "37". Как показывает этот пример, C не является безопасным по отношению к памяти. Поскольку произвольные данные предполагались как символ, он также не является типобезопасным языком.

В общем, безопасность типов и безопасность памяти идут рука об руку. Например, язык, поддерживающий арифметику указателей и преобразования чисел в указатели (например, C), не является ни безопасным по памяти, ни безопасным по типам, поскольку он позволяет получать доступ к произвольной памяти, как если бы это была допустимая память любого типа.

Для получения дополнительной информации см. раздел Безопасность памяти .

Различные уровни проверки типов

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

• Директива use strictв JavaScript ^{[18] [19] [20]} и Perl применяет более строгую проверку.
• declare(strict_types=1)В PHP ^[21] для каждого файла допускается только переменная точного типа объявления типа, в противном случае будет выдано исключение .TypeError
• В Option Strict OnVB.NET компилятор может требовать преобразования между объектами.

Для достижения более высокого уровня строгости можно также использовать дополнительные инструменты, такие как lint и IBM Rational Purify .

Дополнительные типы систем

Было предложено, главным образом Гиладом Брахой , чтобы выбор системы типов был независимым от выбора языка; чтобы система типов была модулем, который может быть подключен к языку по мере необходимости. Он считает, что это выгодно, потому что то, что он называет обязательными системами типов, делает языки менее выразительными, а код более хрупким. ^[22] Требование, чтобы система типов не влияла на семантику языка, трудновыполнимо.

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

Полиморфизм и типы

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

Специализированные типы систем

Было создано много систем типов, которые специализированы для использования в определенных средах с определенными типами данных или для внеполосного статического анализа программ . Часто они основаны на идеях формальной теории типов и доступны только как часть прототипных исследовательских систем.

Следующая таблица дает обзор концепций теории типов, которые используются в специализированных системах типов. Имена M, N, O ранжируются по терминам, а имена ранжируются по типам. Будут использоваться следующие обозначения: ${\displaystyle \sigma ,\tau }$

• ${\displaystyle M:\sigma }$означает, что имеет тип ; ${\displaystyle M}$ ${\displaystyle \sigma }$
• ${\displaystyle M(N)}$является ли это приложением к ; ${\displaystyle M}$ ${\displaystyle N}$
• ${\displaystyle \tau [\alpha :=\sigma ]}$(соответственно ) описывает тип, который получается в результате замены всех вхождений переменной типа α (соответственно термина переменной x ) на тип σ (соответственно термина N ). ${\displaystyle \tau [x:=N]}$ ${\displaystyle \tau }$

1. Также называется зависимым типом продукта , поскольку . ${\textstyle (x:\sigma )\to \tau =\prod _{x:\sigma }\tau }$
2. Также называется типом зависимой суммы , поскольку . ${\textstyle (x:\sigma )\times \tau =\sum _{x:\sigma }\tau }$

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

Зависимые типы основаны на идее использования скаляров или значений для более точного описания типа некоторого другого значения. Например, это может быть тип матрицы . Затем мы можем определить правила типизации, например следующее правило для умножения матриц: ${\displaystyle \mathrm {matrix} (3,3)}$ ${\displaystyle 3\times 3}$

${\displaystyle \mathrm {matrix} _{\mathrm {multiply} }:\mathrm {matrix} (k,m)\times \mathrm {matrix} (m,n)\to \mathrm {matrix} (k,n)}$

где k , m , n — произвольные положительные целые значения. На основе этой системы типов был создан вариант ML , называемый Dependent ML , но поскольку проверка типов для обычных зависимых типов неразрешима , не все программы, использующие их, могут быть проверены на тип без каких-либо ограничений. Dependent ML ограничивает вид равенства, который он может решить, до арифметики Пресбургера .

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

Линейные типы

Линейные типы , основанные на теории линейной логики и тесно связанные с типами уникальности , являются типами, назначенными значениям, имеющим свойство иметь одну и только одну ссылку на них в любое время. Они ценны для описания больших неизменяемых значений, таких как файлы, строки и т. д., поскольку любая операция, которая одновременно уничтожает линейный объект и создает аналогичный объект (например, str = str + "a"), может быть оптимизирована «под капотом» в мутацию на месте. Обычно это невозможно, так как такие мутации могут вызывать побочные эффекты в частях программы, содержащих другие ссылки на объект, нарушая ссылочную прозрачность . Они также используются в прототипе операционной системы Singularity для межпроцессного взаимодействия, статически гарантируя, что процессы не смогут совместно использовать объекты в общей памяти, чтобы предотвратить состояния гонки. Язык Clean ( язык, похожий на Haskell ) использует эту систему типов, чтобы получить большую скорость (по сравнению с выполнением глубокого копирования), оставаясь при этом безопасным.

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

Типы пересечения — это типы, описывающие значения, которые принадлежат обоим из двух других заданных типов с перекрывающимися наборами значений. Например, в большинстве реализаций C знаковый символ имеет диапазон от -128 до 127, а беззнаковый символ — от 0 до 255, поэтому тип пересечения этих двух типов будет иметь диапазон от 0 до 127. Такой тип пересечения можно безопасно передавать в функции, ожидающие либо знаковые, либо беззнаковые символы, поскольку он совместим с обоими типами.

Типы пересечения полезны для описания перегруженных типов функций: например, если " int→ int" — это тип функций, принимающих целочисленный аргумент и возвращающих целое число, а " float→ float" — это тип функций, принимающих аргумент с плавающей точкой и возвращающих число с плавающей точкой, то пересечение этих двух типов можно использовать для описания функций, которые выполняют одно или другое действие в зависимости от типа входных данных, которые им предоставлены. Такую функцию можно было бы безопасно передать в другую функцию, ожидающую функцию " int→ int"; она просто не будет использовать функциональность " float→ float".

В иерархии подклассов пересечение типа и типа-предка (например, его родителя) является наиболее производным типом. Пересечение родственных типов пусто.

Язык Forsythe включает общую реализацию типов пересечения. Ограниченная форма — типы уточнения .

Типы союзов

Типы объединений — это типы, описывающие значения, которые принадлежат к одному из двух типов. Например, в языке C знаковый символ имеет диапазон от -128 до 127, а беззнаковый символ — от 0 до 255, поэтому объединение этих двух типов будет иметь общий «виртуальный» диапазон от -128 до 255, который может использоваться частично в зависимости от того, к какому члену объединения осуществляется доступ. Любая функция, обрабатывающая этот тип объединения, должна будет иметь дело с целыми числами в этом полном диапазоне. В более общем смысле, единственными допустимыми операциями для типа объединения являются операции, которые допустимы для обоих объединяемых типов. Концепция «объединения» в языке C похожа на типы объединений, но не является типобезопасной, поскольку допускает операции, которые допустимы для любого типа, а не для обоих . Типы объединений важны в анализе программ, где они используются для представления символических значений, точная природа которых (например, значение или тип) неизвестна.

В иерархии подклассов объединение типа и типа-предка (например, его родителя) является типом-предком. Объединение родственных типов является подтипом их общего предка (то есть все операции, разрешенные для их общего предка, разрешены для типа объединения, но они также могут иметь другие общие допустимые операции).

Экзистенциальные типы

Экзистенциальные типы часто используются в связи с типами записей для представления модулей и абстрактных типов данных из-за их способности разделять реализацию от интерфейса. Например, тип "T = ∃X { a: X; f: (X → int); }" описывает интерфейс модуля, который имеет член данных с именем a типа X и функцию с именем f , которая принимает параметр того же типа X и возвращает целое число. Это можно реализовать разными способами, например:

• intT = {а: int; е: (целое → целое); }
• floatT = { a: float; f: (float → int); }

Оба эти типа являются подтипами более общего экзистенциального типа T и соответствуют конкретным типам реализации, поэтому любое значение одного из этих типов является значением типа T. При наличии значения «t» типа «T» мы знаем, что «tf(ta)» является хорошо типизированным, независимо от того, каким является абстрактный тип X. Это обеспечивает гибкость при выборе типов, подходящих для конкретной реализации, в то время как клиенты, использующие только значения типа интерфейса — экзистенциального типа — изолированы от этого выбора.

В общем случае для средства проверки типов невозможно определить, к какому экзистенциальному типу принадлежит данный модуль. В приведенном выше примере intT { a: int; f: (int → int); } также может иметь тип ∃X { a: X; f: (int → int); }. Самое простое решение — аннотировать каждый модуль его предполагаемым типом, например:

• intT = {а: int; е: (целое → целое); } как ∃X { а: X; е: (X → целое); }

Хотя абстрактные типы данных и модули были реализованы в языках программирования уже довольно давно, только в 1988 году Джон К. Митчелл и Гордон Плоткин сформулировали формальную теорию под лозунгом: «Абстрактные типы [данных] имеют экзистенциальный тип». ^{[25] Теория представляет собой} типизированное лямбда-исчисление второго порядка, похожее на Систему F , но с экзистенциальной вместо универсальной квантификации.

Постепенный ввод текста

В системе типов с постепенной типизацией переменным может быть назначен тип либо во время компиляции (что является статической типизацией), либо во время выполнения (что является динамической типизацией). ^[26] Это позволяет разработчикам программного обеспечения выбирать любую парадигму типов по мере необходимости в пределах одного языка. ^[26] Постепенная типизация использует специальный тип, называемый dynamic , для представления статически неизвестных типов; постепенная типизация заменяет понятие равенства типов новым отношением, называемым согласованностью , которое связывает динамический тип с любым другим типом. Отношение согласованности является симметричным, но не транзитивным. ^[27]

Явное или неявное заявление и вывод

Многие статические системы типов, такие как C и Java, требуют деклараций типов : программист должен явно связать каждую переменную с определенным типом. Другие, такие как Haskell, выполняют вывод типов : компилятор делает выводы о типах переменных на основе того, как программисты используют эти переменные. Например, если задана функция , которая складывает и вместе, компилятор может сделать вывод, что и должны быть числами, поскольку сложение определено только для чисел. Таким образом, любой вызов в другом месте программы, который указывает нечисловой тип (такой как строка или список) в качестве аргумента, будет сигнализировать об ошибке.f(x, y)xyxyf

Числовые и строковые константы и выражения в коде могут и часто подразумевают тип в определенном контексте. Например, выражение 3.14может подразумевать тип с плавающей точкой , в то время как может подразумевать список целых чисел — обычно массив .[1, 2, 3]

Вывод типа в общем случае возможен, если он вычислим в рассматриваемой системе типов. Более того, даже если вывод невычислим в общем случае для данной системы типов, вывод часто возможен для большого подмножества реальных программ. Система типов Haskell, версия Hindley–Milner , является ограничением System Fω до так называемых полиморфных типов ранга 1, в которых вывод типа вычислим. Большинство компиляторов Haskell допускают полиморфизм произвольного ранга как расширение, но это делает вывод типа невычислимым. (Однако проверка типов разрешима , и программы ранга 1 все еще имеют вывод типа; полиморфные программы более высокого ранга отклоняются, если не даны явные аннотации типа.)

Проблемы с принятием решений

Система типов, которая назначает типы терминам в средах типов с использованием правил типизации , естественным образом связана с проблемами принятия решений по проверке типов , типизации и заполнению типов . ^[28]

• Учитывая тип environment , терм и тип , решите , можно ли присвоить терму тип в тип environment. ${\displaystyle \Gamma }$ ${\displaystyle e}$ ${\displaystyle \tau }$ ${\displaystyle e}$ ${\displaystyle \tau }$
• Для заданного терма определите, существует ли типовая среда и тип, такие, что терму может быть назначен тип в типовой среде . ${\displaystyle e}$ ${\displaystyle \Gamma }$ ${\displaystyle \tau }$ ${\displaystyle e}$ ${\displaystyle \tau }$ ${\displaystyle \Gamma }$
• Учитывая тип окружения и тип , решите, существует ли терм , которому может быть назначен тип в тип окружения. ${\displaystyle \Gamma }$ ${\displaystyle \tau }$ ${\displaystyle e}$ ${\displaystyle \tau }$

Единая система типов

Некоторые языки, такие как C# или Scala, имеют единую систему типов. ^[29] Это означает, что все типы C#, включая примитивные типы, наследуются от одного корневого объекта. Каждый тип в C# наследуется от класса Object. Некоторые языки, такие как Java и Raku , имеют корневой тип, но также имеют примитивные типы, которые не являются объектами. ^[30] Java предоставляет типы объектов-оболочек, которые существуют вместе с примитивными типами, поэтому разработчики могут использовать либо типы объектов-оболочек, либо более простые примитивные типы, не являющиеся объектами. Raku автоматически преобразует примитивные типы в объекты при доступе к их методам. ^[31]

Совместимость: эквивалентность и подтипирование

Проверка типов для статически типизированного языка должна проверять, что тип любого выражения соответствует типу, ожидаемому контекстом, в котором это выражение появляется. Например, в операторе присваивания формы выведенный тип выражения должен соответствовать объявленному или выведенному типу переменной . Это понятие согласованности, называемое совместимостью , специфично для каждого языка программирования.x := eex

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

В языках с подтипированием отношение совместимости более сложное: если Bявляется подтипом A, то значение типа Bможет использоваться в контексте, где Aожидается один из типа ( ковариант ), даже если обратное неверно. Как и эквивалентность, отношение подтипа определяется по-разному для каждого языка программирования, и возможны многие вариации. Наличие параметрического или специального полиморфизма в языке также может иметь последствия для совместимости типов.

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

• Портал компьютерного программирования

• Сравнение типов систем
• Ковариантность и контравариантность (информатика)
• Полиморфизм в объектно-ориентированном программировании
• Тип подписи
• Теория типов

Примечания

1. Линия компьютеров Burroughs ALGOL определяла содержимое ячейки памяти по ее флаговым битам. Флаговые биты определяют содержимое ячейки памяти. Инструкция, тип данных и функции определяются 3-битным кодом в дополнение к его 48-битному содержимому. Только MCP (главная программа управления) могла записывать в биты флагового кода.
2. Например, в ходе разработки может всплыть дырявая абстракция , которая может показать, что требуется дополнительная разработка типов. — «Вычисление хорошо типизированной программы всегда завершается». — Б. Нордстрём, К. Петерссон и Дж. М. Смит ^[5] Систематическое изменение переменных для предотвращения захвата свободной переменной может привести к ошибке в функциональном языке программирования, где функции являются гражданами первого класса. ^[6] — Из статьи о лямбда-исчислении .

Ссылки

1. Пирс 2002, стр. 1: «Система типов — это послушный синтаксический метод доказательства отсутствия определенных поведений программы путем классификации фраз в соответствии с типами значений, которые они вычисляют».
2. Карделли 2004, стр. 1: «Основная цель системы типов — предотвратить возникновение ошибок выполнения во время работы программы».
3. Пирс 2002, стр. 208.
4. Sethi, R. (1996). Языки программирования: Концепции и конструкции (2-е изд.). Addison-Wesley. стр. 142. ISBN 978-0-201-59065-4. OCLC  604732680.
5. Нордстрём, Б.; Петерссон, К.; Смит, Дж. М. (2001). "Теория типов Мартина-Лёфа". Алгебраические и логические структуры . Справочник по логике в информатике. Том 5. Oxford University Press. стр. 2. ISBN 978-0-19-154627-3.
6. Тернер, ДА (12 июня 2012 г.). "Немного истории функциональных языков программирования" (PDF) . приглашенная лекция на TFP12 в Университете Сент-Эндрюс . См. раздел об Algol 60.
7. "... любая здравая, разрешимая система типов должна быть неполной" — Д. Реми (2017). стр. 29, Реми, Дидье. "Системы типов для языков программирования" (PDF) . Архивировано из оригинала (PDF) 14 ноября 2017 г. . Получено 26 мая 2013 г. .
8. Пирс 2002.
9. Скит, Джон (2019). C# in Depth (4-е изд.). Мэннинг. ISBN 978-1617294532.
10. Miglani, Gaurav (2018). "Dynamic Method Dispatch or Runtime Polymorphism in Java". Архивировано из оригинала 2020-12-07 . Получено 2021-03-28 .
11. Райт, Эндрю К. (1995). Практическая мягкая типизация (PhD). Университет Райса. hdl :1911/16900.
12. "dynamic (C# Reference)". Библиотека MSDN . Microsoft . Получено 14 января 2014 г. .
13. "std::any — Rust". doc.rust-lang.org . Получено 2021-07-07 .
14. Мейер, Эрик; Дрейтон, Питер. «Статическая типизация там, где это возможно, динамическая типизация при необходимости: конец холодной войны между языками программирования» (PDF) . Корпорация Microsoft .
15. Лаучер, Аманда; Снивели, Пол (2012). «Типы против тестов». InfoQ.
16. Си, Хунвэй (1998). Зависимые типы в практическом программировании (PhD). Кафедра математических наук, Университет Карнеги-Меллона. CiteSeerX 10.1.1.41.548 . 
    Xi, Hongwei; Pfenning, Frank (1999). "Зависимые типы в практическом программировании". Труды 26-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования . ACM. С. 214–227. CiteSeerX  10.1.1.69.2042 . doi :10.1145/292540.292560. ISBN 1581130953. S2CID  245490.
17. Visual Basic — пример языка, который является как типобезопасным, так и безопасным по отношению к памяти.
18. "4.2.2 Строгий вариант ECMAScript". Спецификация языка ECMAScript® 2020 (11-е изд.). ECMA. Июнь 2020 г. ECMA-262.
19. "Строгий режим – JavaScript". MDN . Developer.mozilla.org. 2013-07-03 . Получено 2013-07-17 .
20. "Строгий режим (JavaScript)". MSDN . Microsoft . Получено 2013-07-17 .
21. "Строгая типизация". PHP Manual: Справочник языка: Функции .
22. Bracha, G. «Подключаемые типы» (PDF) .
23. "Конечно. Это называется "постепенная типизация", и я бы назвал это трендом. ..." Существует ли язык, который допускает как статическую, так и динамическую типизацию? . stackoverflow. 2012.
24. Копылов, Алексей (2003). «Зависимое пересечение: новый способ определения записей в теории типов». 18-й симпозиум IEEE по логике в компьютерных науках . LICS 2003. IEEE Computer Society. стр. 86–95. CiteSeerX 10.1.1.89.4223 . doi :10.1109/LICS.2003.1210048. 
25. Митчелл, Джон К.; Плоткин, Гордон Д. (июль 1988 г.). «Абстрактные типы имеют экзистенциальный тип» (PDF) . ACM Trans. Program. Lang. Syst . 10 (3): 470–502. doi :10.1145/44501.45065. S2CID  1222153.
26. Siek, Джереми (24 марта 2014 г.). «Что такое постепенная типизация?».
27. Сик, Джереми; Таха, Валид (сентябрь 2006 г.). Постепенная типизация для функциональных языков (PDF) . Scheme and Functional Programming 2006. Чикагский университет . стр. 81–92.
28. Барендрегт, Хенк; Деккерс, Уил; Статман, Ричард (20 июня 2013 г.). Лямбда-исчисление с типами. Издательство Кембриджского университета. п. 66. ИСБН 978-0-521-76614-2.
29. "8.2.4 Унификация системы типов". Спецификация языка C# (5-е изд.). ECMA. Декабрь 2017 г. ECMA-334.
30. "Собственные типы". Документация Perl 6 .
31. "Числа, § Автоупаковка". Документация Perl 6 .

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

• Карделли, Лука ; Вегнер, Питер (декабрь 1985 г.). «О понимании типов, абстракции данных и полиморфизма» (PDF) . ACM Computing Surveys . 17 (4): 471–523. CiteSeerX  10.1.1.117.695 . doi :10.1145/6041.6042. S2CID  2921816.
• Пирс, Бенджамин С. (2002). Типы и языки программирования . MIT Press. ISBN 978-0-262-16209-8.
• Cardelli, Luca (2004). "Системы типов" (PDF) . В Allen B. Tucker (ред.). CRC Handbook of Computer Science and Engineering (2-е изд.). CRC Press. ISBN 978-1584883609.
• Tratt, Laurence (июль 2009). "5. Динамически типизированные языки". Advances in Computers . Vol. 77. Elsevier. pp. 149–184. doi :10.1016/S0065-2458(09)01205-4. ISBN 978-0-12-374812-6.

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

• Медиафайлы по теме Системы типов на Wikimedia Commons
• Смит, Крис (2011). «Что нужно знать перед обсуждением систем типов».