Теория типов

Понятие математической логики

В математике и теоретической информатике теория типов представляет собой формальное представление определенной системы типов . ^[a] Теория типов — это академическое исследование систем типов.

Некоторые теории типов служат альтернативой теории множеств как основе математики . Две влиятельные теории типов, которые были предложены в качестве основы, — это типизированное λ-исчисление Алонсо Чёрча и интуиционистская теория типов Пера Мартина-Лёфа .

Большинство компьютеризированных систем корректуры используют в своей основе теорию типов . Распространенным из них является «Исчисление индуктивных конструкций» Тьерри Коканда .

История

Теория типов была создана, чтобы избежать парадокса в математическом уравнении, основанном на наивной теории множеств и формальной логике . Парадокс Рассела (впервые описанный в книге Готлоба Фреге « Основы арифметики ») заключается в том, что без надлежащих аксиом можно определить множество всех множеств, которые не являются членами самих себя; это множество одновременно содержит себя и не содержит себя. Между 1902 и 1908 годами Бертран Рассел предлагал различные решения этой проблемы.

К 1908 году Рассел пришел к разветвленной теории типов вместе с аксиомой сводимости , обе из которых появились в «Принципах математики» Уайтхеда и Рассела , опубликованных в 1910, 1912 и 1913 годах. Эта система позволила избежать противоречий, предложенных в парадоксе Рассела, путем создания иерархию типов с последующим присвоением каждой конкретной математической сущности определенному типу. Сущности данного типа были построены исключительно из подтипов этого типа, ^[b] что предотвращало определение сущности с использованием самой себя. Это разрешение парадокса Рассела похоже на подходы, используемые в других формальных системах, таких как теория множеств Цермело-Фаенкеля . ^[3]

Теория типов особенно популярна в сочетании с лямбда-исчислением Алонзо Чёрча . Одним из примечательных ранних примеров теории типов является просто типизированное лямбда-исчисление Чёрча . Теория типов Чёрча ^[4] помогла формальной системе избежать парадокса Клини-Россера , который затронул исходное нетипизированное лямбда-исчисление. Чёрч продемонстрировал ^[c] , что она может служить основой математики , и ее назвали логикой высшего порядка .

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

Приложения

Математические основы

Первый помощник по компьютерному доказательству, названный Automath , использовал теорию типов для кодирования математических вычислений на компьютере. Мартин-Лёф специально разработал интуиционистскую теорию типов , чтобы закодировать всю математику и послужить новой основой математики. Продолжаются исследования математических основ с использованием теории гомотопических типов .

Математики, работающие над теорией категорий, уже сталкивались с трудностями при работе с широко признанной основой теории множеств Цермело-Френкеля . Это привело к появлению таких предложений, как «Элементарная теория категории множеств» Ловера (ETCS). ^[6] Гомотопическая теория типов продолжает эту линию, используя теорию типов. Исследователи изучают связи между зависимыми типами (особенно тождественным типом) и алгебраической топологией (в частности, гомотопией ).

Помощники по доказательствам

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

• LF используется Twelf часто для определения других теорий типов;
• многие теории типов, подпадающие под логику высшего порядка, используются семейством доказывающих устройств HOL и PVS ;
• теория вычислительных типов используется NuPRL ;
• исчисление конструкций и его производные используются Коком , Матитой и Лином ;
• UTT (Единая теория зависимых типов Ло) используется Agda , которая является одновременно языком программирования и помощником по доказательству.

Многие теории типов поддерживаются LEGO и Изабель . Помимо теорий типов, Изабель также поддерживает другие фонды, такие как ZFC . Мицар — пример системы доказательств, которая поддерживает только теорию множеств.

Языки программирования

Любой статический анализ программы , например алгоритмы проверки типов на этапе семантического анализа компилятора , связан с теорией типов. Ярким примером является Agda , язык программирования, который использует UTT (унифицированную теорию зависимых типов Луо) в качестве системы типов.

Язык программирования ML был разработан для манипулирования теориями типов (см. LCF ), и его собственная система типов находилась под их сильным влиянием.

Лингвистика

Теория типов также широко используется в формальных теориях семантики естественных языков , ^{[7] [8],} особенно в грамматике Монтегю ^[9] и ее потомках. В частности, категориальные грамматики и грамматики предгрупп широко используют конструкторы типов для определения типов ( существительное , глагол и т. д.) слов.

Наиболее распространенная конструкция принимает базовые типы и для индивидуумов и истинностные значения соответственно и рекурсивно определяет набор типов следующим образом: ${\displaystyle e}$ ${\displaystyle t}$

• если и являются типами, то и ; ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \langle a,b\rangle }$
• ничего, кроме базовых типов, и то, что из них можно сконструировать с помощью предыдущего предложения, является типами.

Сложный тип — это тип функций от сущностей типа к сущностям типа . Таким образом, существуют типы, подобные которым интерпретируются как элементы множества функций от сущностей к истинностным значениям, т.е. индикаторные функции множеств сущностей. Выражение типа — это функция от наборов сущностей к истинностным значениям, т. е. (индикаторная функция a) набора множеств. Этот последний тип обычно считается типом кванторов естественного языка , например, «все или никто» ( Montague 1973, Barwise and Cooper 1981). ^[10] ${\displaystyle \langle a,b\rangle }$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \langle e,t\rangle }$ ${\displaystyle \langle \langle e,t\rangle ,t\rangle }$

Теория типов с записями — это формальная структура представления семантики , использующая записи для выражения типов теории типов . Он использовался в обработке естественного языка , главным образом в вычислительной семантике и диалоговых системах . ^{[11] [12]}

Социальные науки

Грегори Бейтсон ввел в социальные науки теорию логических типов; его представления о двойной связке и логических уровнях основаны на теории типов Рассела.

Теория типов как логика

Теория типов — это математическая логика , то есть совокупность правил вывода , которые приводят к суждениям . В большинстве логик есть суждения, утверждающие: « Предложение истинно» или « Формула представляет собой правильно составленную формулу ». ^[13] В теории типов есть суждения, которые определяют типы и присваивают их набору формальных объектов, известных как термины. Термин и его тип часто записываются вместе как . ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle \mathrm {term} :{\mathsf {type}}}$

Условия

Термин в логике рекурсивно определяется как постоянный символ , переменная или приложение-функция , где термин применяется к другому термину. Постоянные символы могут включать натуральное число , логическое значение и такие функции, как функция-преемник и условный оператор . Таким образом, некоторые термины могут быть , , , и . ${\displaystyle 0}$ ${\displaystyle \mathrm {true} }$ ${\displaystyle \mathrm {S} }$ ${\displaystyle \mathrm {if} }$ ${\displaystyle 0}$ ${\displaystyle (\mathrm {S} \,0)}$ ${\displaystyle (\mathrm {S} \,(\mathrm {S} \,0))}$ ${\displaystyle (\mathrm {if} \,\mathrm {true} \,0\,(\mathrm {S} \,0))}$

Суждения

Большинство теорий типов имеют четыре суждения:

• " это тип" ${\displaystyle T}$
• " это термин типа " ${\displaystyle t}$ ${\displaystyle T}$
• «Тип равен типу » ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$
• «Условия и оба типа равны» ${\displaystyle t_{1}}$ ${\displaystyle t_{2}}$ ${\displaystyle T}$

Суждения могут следовать из предположений. Например, можно сказать: «Если предположить , что это термин типа и является термином типа , из этого следует, что это термин типа ». Такие решения формально обозначаются символом турникета . ${\displaystyle x}$ ${\displaystyle {\mathsf {bool}}}$ ${\displaystyle y}$ ${\displaystyle {\mathsf {nat}}}$ ${\displaystyle (\mathrm {if} \,x\,y\,y)}$ ${\displaystyle {\mathsf {nat}}}$ ${\displaystyle \vdash }$

${\displaystyle x:{\mathsf {bool}},y:{\mathsf {nat}}\vdash ({\textrm {if}}\,x\,y\,y):{\mathsf {nat}}}$

Если нет предположений, то слева от турникета ничего не будет.

${\displaystyle \vdash \mathrm {S} :{\mathsf {nat}}\to {\mathsf {nat}}}$

Список предположений слева представляет собой контекст решения. Заглавные греческие буквы, такие как и , часто используются для обозначения некоторых или всех предположений. Таким образом, четыре различных решения обычно записываются следующим образом. ${\displaystyle \Gamma }$ ${\displaystyle \Delta }$

В некоторых учебниках тройной знак равенства используется, чтобы подчеркнуть, что это равенство в суждениях и, следовательно , внешнее понятие равенства. ^[14] Решения предусматривают, что каждый термин имеет тип. Тип будет ограничивать правила, которые можно применять к термину. ${\displaystyle \equiv }$

Правила вывода

Правила вывода теории типов говорят, какие суждения могут быть сделаны на основе существования других суждений. Правила выражаются в виде вывода в стиле Генцена с использованием горизонтальной линии, где необходимые входные суждения находятся над линией, а результирующие суждения — под линией. ^[15] Например, следующее правило вывода устанавливает правило замены для равенства суждений.

$${\displaystyle {\begin{array}{c}\Gamma \vdash t:T_{1}\qquad \Delta \vdash T_{1}=T_{2}\\\hline \Gamma ,\Delta \vdash t:T_{2}\end{array}}}$$

переписыванияна ${\displaystyle \Gamma }$ ${\displaystyle \Delta }$ ${\displaystyle t}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

Чтобы сформулировать конкретное суждение в теории типов, должно существовать правило для его генерации, а также правила для генерации всех необходимых входных данных этого правила и так далее. Применяемые правила образуют дерево доказательства , где самые верхние правила не требуют допущений. Одним из примеров правила, не требующего каких-либо входных данных, является правило, определяющее тип постоянного термина. Например, чтобы утверждать, что существует термин типа , можно было бы написать следующее. ${\displaystyle 0}$ ${\displaystyle {\mathsf {nat}}}$

$${\displaystyle {\begin{array}{c}\hline \vdash 0:nat\\\end{array}}}$$

Тип проживания

Обычно желаемый вывод доказательства в теории типов — это вывод о обитаемости типов . ^[16] Проблема решения типового жилья (сокращенно ): ${\displaystyle \exists t.\Gamma \vdash t:\tau ?}$

Учитывая контекст и тип , решите, существует ли термин , которому можно присвоить тип в среде типов . ${\displaystyle \Gamma }$ ${\displaystyle \tau }$ ${\displaystyle t}$ ${\displaystyle \tau }$ ${\displaystyle \Gamma }$

Парадокс Жирара показывает, что обитаемость типов тесно связана с согласованностью системы типов с соответствием Карри-Ховарда. Чтобы быть здоровой, такая система должна иметь необитаемые типы.

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

• создать суждение ( в данном случае известное как контекст )
• добавить предположение в контекст ( ослабление контекста )
• переставить предположения
• использовать предположение для создания переменной
• определить рефлексивность , симметрию и транзитивность для равенства суждений
• определить замену для применения лямбда-членов
• перечислить все взаимодействия равенства, такие как замена
• определить иерархию юниверсов типов
• утверждать существование новых типов

Кроме того, для каждого типа «по правилам» существует 4 разных типа правил.

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

В качестве примеров правил заинтересованный читатель может воспользоваться Приложением A.2 книги «Гомотопическая теория типов» ^[14] или прочитать «Интуиционистскую теорию типов» Мартина-Лёфа. ^[17]

Соединения с фундаментами

Логическая структура теории типов имеет сходство с интуиционистской или конструктивной логикой. Формально теорию типов часто называют реализацией интерпретации интуиционистской логики Брауэра-Хейтинга-Колмогорова . ^[17] Кроме того, можно установить связь с теорией категорий и компьютерными программами .

Интуиционистская логика

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

Согласно этой интуиционистской интерпретации, существуют общие типы, которые действуют как логические операторы:

Поскольку закон исключенного третьего не выполняется, не существует понятия типа . Аналогично, двойное отрицание не выполняется, поэтому не существует термина type . ${\displaystyle \Pi a.A+(A\to \bot )}$ ${\displaystyle \Pi A.((A\to \bot )\to \bot )\to A}$

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

Конструктивная математика

Пер Мартин-Лёф предложил свою интуиционистскую теорию типов в качестве основы конструктивной математики . ^[13] Конструктивная математика требует, чтобы при доказательстве того, что «существует свойство, обладающее свойством », необходимо построить частное явление и доказать, что оно обладает свойством . В теории типов существование осуществляется с использованием зависимого типа продукта, и его доказательство требует термина этого типа. ${\displaystyle x}$ ${\displaystyle P(x)}$ ${\displaystyle x}$ ${\displaystyle P}$

Примером неконструктивного доказательства является доказательство от противного . Первый шаг — предположить, что этого не существует, и опровергнуть это от противного. Вывод из этого шага таков: «Это не тот случай, которого не существует». Последний шаг — путем двойного отрицания сделать вывод о том, что существует. Конструктивная математика не позволяет на последнем этапе устранения двойного отрицания прийти к выводу о существовании. ^[18] ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$

Большинство теорий типов, предлагаемых в качестве основы, конструктивны, включая большинство теорий, используемых помощниками по доказательству. ^{[ нужна цитата ]} В теорию типов можно добавить неконструктивные особенности по правилу или предположению. К ним относятся операторы продолжений, такие как вызов с текущим продолжением . Однако эти операторы имеют тенденцию нарушать такие желательные свойства, как каноничность и параметричность .

Переписка Карри-Ховарда

Соответствие Карри -Ховарда — это наблюдаемое сходство между логикой и языками программирования. Импликация в логике «А Б» напоминает функцию от типа «А» к типу «Б». Для различных логик правила аналогичны выражениям в типах языка программирования. Сходство простирается еще дальше: применение правил напоминает программы на языках программирования. Таким образом, переписку часто резюмируют как «доказательства как программы». ${\displaystyle \to }$

Оппозицию терминов и типов можно также рассматривать как оппозицию реализации и спецификации . При синтезе программ (вычислительный аналог) обитаемость типов может использоваться для построения программ (всех или частей) на основе спецификации, заданной в форме информации о типе. ^[19]

Вывод типа

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

Области исследований

Теория категорий

Хотя первоначальная мотивация теории категорий была далека от фундаментализма, оказалось, что эти две области имеют глубокие связи. Как пишет Джон Лейн Белл : «Фактически категории сами по себе могут рассматриваться как теории типов определенного типа; уже один этот факт указывает на то, что теория типов гораздо более тесно связана с теорией категорий, чем с теорией множеств». Короче говоря, категорию можно рассматривать как теорию типов, рассматривая ее объекты как типы (или сорта), т.е. «Грубо говоря, категорию можно рассматривать как теорию типов, лишенную ее синтаксиса». Таким образом, следует ряд важных результатов: ^[20]

• декартовы замкнутые категории соответствуют типизированному λ-исчислению ( Ламбек , 1970);
• C-моноиды (категории с произведениями и экспонентами и одним нетерминальным объектом) соответствуют нетипизированному λ-исчислению (наблюденному независимо Ламбеком и Даной Скотт примерно в 1980 году);
• локально декартовы замкнутые категории соответствуют теориям типа Мартина-Лёфа (Seely, 1984).

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

Теория гомотопических типов

Гомотопическая теория типов пытается объединить теорию типов и теорию категорий. Основное внимание уделяется равенствам, особенно равенствам между типами. Теория гомотопических типов отличается от интуиционистской теории типов главным образом тем, что в ней рассматривается тип равенства. В 2016 году была предложена теория кубического типа, представляющая собой теорию гомотопического типа с нормализацией. ^{[21] [22]}

Определения

Термины и виды

Атомарные термины

Самые основные типы называются атомами, а термин, тип которого является атомом, известен как атомарный терм. Обычными атомарными терминами, включенными в теории типов, являются натуральные числа , часто обозначаемые типом , значения логической логики ( / ), обозначаемые типом , и формальные переменные , тип которых может различаться. ^[16] Например, следующее может быть атомарными терминами. ${\displaystyle {\mathsf {nat}}}$ ${\displaystyle \mathrm {true} }$ ${\displaystyle \mathrm {false} }$ ${\displaystyle {\mathsf {bool}}}$

• ${\displaystyle 42:{\mathsf {nat}}}$
• ${\displaystyle \mathrm {true} :{\mathsf {bool}}}$
• ${\displaystyle x:{\mathsf {nat}}}$
• ${\displaystyle y:{\mathsf {bool}}}$

Функциональные термины

Помимо атомарных терминов, большинство современных теорий типов также допускают функции . Типы функций обозначаются символом стрелки и определяются индуктивно : если и являются типами, то обозначение представляет собой тип функции, которая принимает параметр типа и возвращает термин типа . Типы этой формы известны как простые типы . ^[16] ${\displaystyle \sigma }$ ${\displaystyle \tau }$ ${\displaystyle \sigma \to \tau }$ ${\displaystyle \sigma }$ ${\displaystyle \tau }$

Некоторые термины могут быть объявлены напрямую как имеющие простой тип, например следующий термин, который принимает два последовательных натуральных числа и возвращает одно натуральное число. ${\displaystyle \mathrm {add} }$

${\displaystyle \mathrm {add} :{\mathsf {nat}}\to ({\mathsf {nat}}\to {\mathsf {nat}})}$

Строго говоря, простой тип допускает только один вход и один выход, поэтому более точным прочтением вышеуказанного типа является функция, которая принимает натуральное число и возвращает функцию вида . Круглые скобки поясняют, что у него нет типа , который был бы функцией, которая принимает функцию натуральных чисел и возвращает натуральное число. Соглашение заключается в том, что стрелка ассоциативна вправо , поэтому круглые скобки из типа можно опустить . ^[16] ${\displaystyle \mathrm {add} }$ ${\displaystyle {\mathsf {nat}}\to {\mathsf {nat}}}$ ${\displaystyle \mathrm {add} }$ ${\displaystyle ({\mathsf {nat}}\to {\mathsf {nat}})\to {\mathsf {nat}}}$ ${\displaystyle \mathrm {add} }$

Лямбда-термины

Новые функциональные термины могут быть созданы с использованием лямбда-выражений и называются лямбда-термами. Эти термины также определяются индуктивно: лямбда-терм имеет форму , где – формальная переменная и – терм, а его тип обозначается , где – тип , а – тип . ^[16] Следующий лямбда-терм представляет собой функцию, которая удваивает входное натуральное число. ${\displaystyle (\lambda v.t)}$ ${\displaystyle v}$ ${\displaystyle t}$ ${\displaystyle \sigma \to \tau }$ ${\displaystyle \sigma }$ ${\displaystyle v}$ ${\displaystyle \tau }$ ${\displaystyle t}$

${\displaystyle (\lambda x.\mathrm {add} \,x\,x):{\mathsf {nat}}\to {\mathsf {nat}}}$

Переменная и (неявно вытекающая из типа лямбда-терма) должна иметь тип . Термин имеет тип , что можно увидеть, дважды применив правило вывода приложения-функции. Таким образом, лямбда-терм имеет тип , что означает, что это функция, принимающая натуральное число в качестве аргумента и возвращающая натуральное число. ${\displaystyle x}$ ${\displaystyle {\mathsf {nat}}}$ ${\displaystyle \mathrm {add} \,x\,x}$ ${\displaystyle {\mathsf {nat}}}$ ${\displaystyle {\mathsf {nat}}\to {\mathsf {nat}}}$

Лямбда-терм часто называют ^[d] анонимной функцией , поскольку у него нет имени. Концепция анонимных функций встречается во многих языках программирования.

Правила вывода

Применение функции

Сила теорий типов заключается в определении того, как термины могут быть объединены посредством правил вывода . ^[4] Теории типов, которые имеют функции, также имеют правило вывода применения функции : если это термин типа и является термином типа , то применение to , часто записываемое , имеет тип . Например, если известны обозначения типов , и , то из применения функции можно вывести следующие обозначения типов . ^[16] ${\displaystyle t}$ ${\displaystyle \sigma \to \tau }$ ${\displaystyle s}$ ${\displaystyle \sigma }$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle (t\,s)}$ ${\displaystyle \tau }$ ${\displaystyle 0:{\textsf {nat}}}$ ${\displaystyle 1:{\textsf {nat}}}$ ${\displaystyle 2:{\textsf {nat}}}$

• ${\displaystyle (\mathrm {add} \,1):{\textsf {nat}}\to {\textsf {nat}}}$
• ${\displaystyle ((\mathrm {add} \,2)\,0):{\textsf {nat}}}$
• ${\displaystyle ((\mathrm {add} \,1)((\mathrm {add} \,2)\,0)):{\textsf {nat}}}$

Круглые скобки указывают порядок действий ; однако по соглашению приложение функции остается ассоциативным , поэтому при необходимости круглые скобки можно опустить. ^[16] В случае трех приведенных выше примеров все круглые скобки в первых двух можно опустить, а третий можно упростить до . ${\displaystyle \mathrm {add} \,1\,(\mathrm {add} \,2\,0):{\textsf {nat}}}$

Скидки

Теории типов, допускающие использование лямбда-членов, также включают правила вывода, известные как -редукция и -редукция. Они обобщают понятие применения функции на лямбда-термины. Символически они пишутся ${\displaystyle \beta }$ ${\displaystyle \eta }$

• ${\displaystyle (\lambda v.t)\,s\rightarrow t[v\colon =s]}$( -снижение). ${\displaystyle \beta }$
• ${\displaystyle (\lambda v.t\,v)\rightarrow t}$, if не является свободной переменной в ( -reduction). ${\displaystyle v}$ ${\displaystyle t}$ ${\displaystyle \eta }$

Первое сокращение описывает, как вычислить лямбда-терм: если к терму применяется лямбда-выражение , каждое вхождение in заменяется на . Второе сокращение делает явной связь между лямбда-выражениями и типами функций: если это лямбда-термин, то это должно быть функциональный термин, поскольку он применяется к . Следовательно, лямбда-выражение эквивалентно просто , поскольку оба принимают один аргумент и применяются к нему. ^[4] ${\displaystyle (\lambda v.t)}$ ${\displaystyle s}$ ${\displaystyle v}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle (\lambda v.t\,v)}$ ${\displaystyle t}$ ${\displaystyle v}$ ${\displaystyle t}$ ${\displaystyle t}$

Например, следующий термин может быть сокращен. ${\displaystyle \beta }$

${\displaystyle (\lambda x.\mathrm {add} \,x\,x)\,2\rightarrow \mathrm {add} \,2\,2}$

В теориях типов, которые также устанавливают понятия равенства для типов и терминов, существуют соответствующие правила вывода -равенства и -равенства. ^[16] ${\displaystyle \beta }$ ${\displaystyle \eta }$

Общие термины и типы

Пустой тип

Пустой тип не имеет терминов. Тип обычно пишется или . Одно из применений пустого типа — доказательство существования типа . Если для типа последовательно вывести функцию типа , то он необитаем , то есть не имеет термов. ${\displaystyle \bot }$ ${\displaystyle \mathbb {0} }$ ${\displaystyle a}$ ${\displaystyle a\to \bot }$ ${\displaystyle a}$

Тип устройства

Тип единицы имеет ровно 1 канонический термин. Пишется тип или и пишется единственный канонический терм . Тип объекта также используется в доказательствах типа проживания. Если для типа последовательно вывести функцию типа , то он является обитаемым , то есть должен иметь один или несколько термов. ${\displaystyle \top }$ ${\displaystyle \mathbb {1} }$ ${\displaystyle \ast }$ ${\displaystyle a}$ ${\displaystyle \top \to a}$ ${\displaystyle a}$

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

Булев тип имеет ровно два канонических термина. Тип обычно пишется или или . Каноническими терминами обычно являются и . ${\displaystyle {\textsf {bool}}}$ ${\displaystyle \mathbb {B} }$ ${\displaystyle \mathbb {2} }$ ${\displaystyle \mathrm {true} }$ ${\displaystyle \mathrm {false} }$

Натуральные числа

Натуральные числа обычно реализуются в стиле арифметики Пеано . Существует канонический термин для нуля. Канонические значения больше нуля используют повторяющиеся применения функции-преемника . ${\displaystyle 0:{\mathsf {nat}}}$ ${\displaystyle \mathrm {S} :{\mathsf {nat}}\to {\mathsf {nat}}}$

Зависимая типизация

Некоторые теории типов допускают, что типы сложных терминов, таких как функции или списки, зависят от типов их аргументов. Например, теория типов может иметь зависимый тип , который должен соответствовать спискам терминов, где каждый термин должен иметь тип . В данном случае имеет тип , где обозначает вселенную всех типов в теории. ${\displaystyle {\mathsf {list}}\,a}$ ${\displaystyle a}$ ${\displaystyle {\mathsf {list}}}$ ${\displaystyle U\to U}$ ${\displaystyle U}$

Некоторые теории также допускают, что типы зависят от терминов, а не от типов. Например, теория может иметь тип , где — термин типа, кодирующий длину вектора . Это обеспечивает большую специфичность и безопасность типов : функции с ограничениями длины вектора или требованиями соответствия длины, такие как скалярное произведение , могут кодировать это требование как часть типа. ^[24] ${\displaystyle {\mathsf {vector}}\,n}$ ${\displaystyle n}$ ${\displaystyle {\mathsf {nat}}}$

Существуют фундаментальные проблемы, которые могут возникнуть из-за зависимых типов, если теория не уделяет должного внимания тому, какие зависимости разрешены, например, парадокс Жирара . Логик Хенк Барендегт представил лямбда-куб как основу для изучения различных ограничений и уровней зависимой типизации. ^[25]

Тип продукта

Тип продукта зависит от двух типов, и его термины обычно записываются в виде упорядоченных пар или с помощью символа . Пара имеет тип продукта , где — тип , а — тип . Тип продукта обычно определяется с помощью функций-элиминаторов и . ${\displaystyle (s,t)}$ ${\displaystyle \times }$ ${\displaystyle (s,t)}$ ${\displaystyle \sigma \times \tau }$ ${\displaystyle \sigma }$ ${\displaystyle s}$ ${\displaystyle \tau }$ ${\displaystyle t}$ ${\displaystyle \mathrm {first} :(\Pi \,\sigma \,\tau .\sigma \times \tau \to \sigma )}$ ${\displaystyle \mathrm {second} :(\Pi \,\sigma \,\tau .\sigma \times \tau \to \tau )}$

• ${\displaystyle \mathrm {first} \,(s,t)}$возвращается , и ${\displaystyle s}$
• ${\displaystyle \mathrm {second} \,(s,t)}$возвращается . ${\displaystyle t}$

Помимо упорядоченных пар, этот тип используется для понятий логического соединения и пересечения .

Тип суммы

Тип суммы зависит от двух типов и обычно записывается с помощью символа или . В языках программирования типы сумм могут называться тегированными объединениями . Тип обычно определяется с помощью конструкторов и , которые являются инъективными , и функции исключения, такой что ${\displaystyle +}$ ${\displaystyle \sqcup }$ ${\displaystyle \sigma \sqcup \tau }$ ${\displaystyle \mathrm {left} :\sigma \to (\sigma \sqcup \tau )}$ ${\displaystyle \mathrm {right} :\tau \to (\sigma \sqcup \tau )}$ ${\displaystyle \mathrm {match} :(\Pi \,\rho .(\sigma \to \rho )\to (\tau \to \rho )\to (\sigma \sqcup \tau )\to \rho )}$

• ${\displaystyle \mathrm {match} \,f\,g\,(\mathrm {left} \,x)}$возвращается , и ${\displaystyle f\,x}$
• ${\displaystyle \mathrm {match} \,f\,g\,(\mathrm {right} \,y)}$возвращается . ${\displaystyle g\,y}$

Тип суммы используется для понятий логической дизъюнкции и объединения .

Зависимые произведения и суммы

Два общих типа зависимостей , зависимый продукт и зависимый тип суммы, позволяют теории кодировать интуиционистскую логику БХК , действуя как эквиваленты универсальной и экзистенциальной количественной оценки ; это формализовано перепиской Карри-Говарда . ^[24] Поскольку они также связаны с произведениями и суммами в теории множеств , их часто пишут символами и соответственно. ^[17] Зависимые типы произведения и суммы обычно встречаются в типах функций и часто включаются в языки программирования. ^[26] ${\displaystyle \Pi }$ ${\displaystyle \Sigma }$

Например, рассмотрим функцию , которая принимает a и термин типа и возвращает список с элементом в конце. Аннотацией типа такой функции будет , что можно прочитать как «для любого типа передать a и an и вернуть a ». ${\displaystyle \mathrm {append} }$ ${\displaystyle {\mathsf {list}}\,a}$ ${\displaystyle a}$ ${\displaystyle \mathrm {append} :(\Pi \,a.{\mathsf {list}}\,a\to a\to {\mathsf {list}}\,a)}$ ${\displaystyle a}$ ${\displaystyle {\mathsf {list}}\,a}$ ${\displaystyle a}$ ${\displaystyle {\mathsf {list}}\,a}$

Типы сумм рассматриваются в виде зависимых пар , где второй тип зависит от значения первого члена. Это естественным образом возникает в информатике, где функции могут возвращать различные типы выходных данных на основе входных данных. Например, логический тип обычно определяется с помощью функции-элиминатора , которая принимает три аргумента и ведет себя следующим образом. ${\displaystyle \mathrm {if} }$

• ${\displaystyle \mathrm {if} \,\mathrm {true} \,x\,y}$возвращается , и ${\displaystyle x}$
• ${\displaystyle \mathrm {if} \,\mathrm {false} \,x\,y}$возвращается . ${\displaystyle y}$

Тип возвращаемого значения этой функции зависит от ее входных данных. Если теория типов допускает зависимые типы, то можно определить функцию такую, что ${\displaystyle {\mathsf {bool}}}$ ${\displaystyle \mathrm {TF} \colon {\mathsf {bool}}\to U\to U\to U}$

• ${\displaystyle \mathrm {TF} \,\mathrm {true} \,\sigma \,\tau }$возвращается , и ${\displaystyle \sigma }$
• ${\displaystyle \mathrm {TF} \,\mathrm {false} \,\sigma \,\tau }$возвращается . ${\displaystyle \tau }$

Тогда тип может быть записан как . ${\displaystyle \mathrm {if} }$ ${\displaystyle (\Pi \,\sigma \,\tau .{\mathsf {bool}}\to \sigma \to \tau \to (\Sigma \,x:{\textsf {bool}}.\mathrm {TF} \,x\,\sigma \,\tau ))}$

Тип идентификации

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

Тип идентичности требует двух терминов одного типа и обозначается символом . Например, если и являются терминами, то это возможный тип. Канонические термины создаются с помощью функции рефлексивности . Для термина вызов возвращает канонический термин, принадлежащий данному типу . ${\displaystyle =}$ ${\displaystyle x+1}$ ${\displaystyle 1+x}$ ${\displaystyle x+1=1+x}$ ${\displaystyle \mathrm {refl} }$ ${\displaystyle t}$ ${\displaystyle \mathrm {refl} \,t}$ ${\displaystyle t=t}$

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

Индуктивные типы

Индуктивные типы — это общий шаблон для создания большого количества типов. Фактически, все описанные выше типы и многие другие можно определить с помощью правил индуктивных типов. Двумя методами генерации индуктивных типов являются индукция-рекурсия и индукция-индукция . Метод, который использует только лямбда-термины, — это кодирование Скотта .

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

Отличия от теории множеств

Наиболее общепринятой основой математики является логика первого порядка с языком и аксиомами теории множеств Цермело-Френкеля с аксиомой выбора , сокращенно ZFC. Теории типов, обладающие достаточной выразимостью , могут также выступать в качестве основы математики. Между этими двумя подходами существует ряд различий.

• В теории множеств есть и правила , и аксиомы , тогда как в теориях типов есть только правила. Теории типов, как правило, не имеют аксиом и определяются своими правилами вывода. ^[14]
• В классической теории множеств и логике действует закон исключенного третьего . Когда теория типов кодирует понятия «и» и «или» как типы, это приводит к интуиционистской логике и не обязательно имеет закон исключенного третьего. ^[17]
• В теории множеств элемент не ограничивается одним множеством. Элемент может появляться в подмножествах и объединениях с другими множествами. В теории типов термины (вообще) принадлежат только одному типу. Там, где будет использоваться подмножество, теория типов может использовать функцию предиката или использовать тип продукта с зависимой типизацией, где каждый элемент сочетается с доказательством того, что свойство подмножества справедливо для . Там, где используется объединение, теория типов использует тип суммы, который содержит новые канонические термины. ${\displaystyle x}$ ${\displaystyle x}$
• Теория типов имеет встроенное понятие вычислений. Таким образом, «1+1» и «2» — это разные термины в теории типов, но они вычисляют одно и то же значение. Более того, функции определяются вычислительно как лямбда-термы. В теории множеств «1+1=2» означает, что «1+1» — это просто еще один способ обозначения значения «2». Вычисления теории типов действительно требуют сложной концепции равенства.
• Теория множеств кодирует числа как множества . Теория типов может кодировать числа как функции, используя кодировку Чёрча , или, что более естественно, как индуктивные типы , и эта конструкция очень напоминает аксиомы Пеано .
• В теории типов доказательства являются типами, тогда как в теории множеств доказательства являются частью базовой логики первого порядка. ^[14]

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

Свойства теорий типов

Термины обычно относятся к одному типу. Однако существуют теории множеств, которые определяют «подтипирование».

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

Некоторые комбинации типов эквивалентны другим комбинациям типов. Когда функции считаются «возведением в степень», комбинации типов можно записать аналогично алгебраическим тождествам. ^[26] Таким образом, , , , , . ${\displaystyle {\mathbb {0} }+A\cong A}$ ${\displaystyle {\mathbb {1} }\times A\cong A}$ ${\displaystyle {\mathbb {1} }+{\mathbb {1} }\cong {\mathbb {2} }}$ ${\displaystyle A^{B+C}\cong A^{B}\times A^{C}}$ ${\displaystyle A^{B\times C}\cong (A^{B})^{C}}$

Аксиомы

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

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

Аксиомы могут вызвать проблемы, если они вводят термины без возможности вычисления этих терминов. То есть аксиомы могут мешать нормализующему свойству теории типов. ^[27]

Некоторые часто встречающиеся аксиомы:

• «Аксиома К» обеспечивает «единственность доказательств идентичности». То есть каждый термин тождественного типа равен рефлексивности. ^[28]
• «Аксиома универсальности» гласит, что эквивалентность типов — это равенство типов. Исследование этого свойства привело к созданию теории кубического типа, в которой это свойство справедливо без аксиомы. ^[22]
• «Закон исключенного третьего» часто добавляется, чтобы удовлетворить пользователей, которым нужна классическая логика , а не интуиционистская логика.

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

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

Главный

• Просто типизированное лямбда-исчисление , которое представляет собой логику более высокого порядка.
• интуиционистская теория типов
• система F
• LF часто используется для определения других теорий типов.
• исчисление конструкций и его производные

Незначительный

• Автомат
• Теория типа ST
• UTT (Единая теория зависимых типов Ло)
• некоторые формы комбинаторной логики
• другие определены в лямбда-кубе (также известном как системы чистого типа )
• другие под именем набрали лямбда-исчисление

Активные исследования

• Теория гомотопических типов исследует равенство типов.
• Кубическая теория типов - это реализация теории гомотопических типов.

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

• Основы математики
• Логика

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

• Аартс, К.; Бэкхаус, Р.; Хугендейк, П.; Верманс, Э.; ван дер Вауде, Дж. (декабрь 1992 г.). «Реляционная теория типов данных». Технический университет Эйндховена.
• Эндрюс Б., Питер (2002). Введение в математическую логику и теорию типов: к истине через доказательство (2-е изд.). Клювер. ISBN 978-1-4020-0763-7.
• Джейкобс, Барт (1999). Категориальная логика и теория типов. Исследования по логике и основам математики. Том. 141. Эльзевир. ISBN 978-0-444-50170-7. Архивировано из оригинала 10 августа 2023 г. Проверено 19 июля 2020 г.Подробно освещает теорию типов, включая полиморфные и зависимые расширения типов. Дает категориальную семантику .
• Карделли, Лука (1996). «Типовые системы». В Такере, Аллен Б. (ред.). Справочник по информатике и инженерии . ЦРК Пресс. стр. 2208–36. ISBN 9780849329098. Архивировано из оригинала 10 апреля 2008 г. Проверено 26 июня 2004 г.
• Коллинз, Джордан Э. (2012). История теории типов: развитие после второго издания «Principia Mathematica». Академическое издательство Ламберта. hdl : 11375/12315. ISBN 978-3-8473-2963-3.Содержит исторический обзор развития теории типов с акцентом на упадок теории как основы математики за четыре десятилетия после публикации второго издания «Principia Mathematica».
• Констебль, Роберт Л. (2012) [2002]. «Наивная вычислительная теория типов» (PDF) . В Швихтенберге, Х.; Штайнбрюгген, Р. (ред.). Доказательство и надежность системы . Наука НАТО, серия II. Том. 62. Спрингер. стр. 213–259. ISBN 9789401004138. Архивировано (PDF) из оригинала 9 октября 2022 г.Задуман как аналог теории типов Наивной теории множеств Пола Халмоша (1960).
• Коканд, Тьерри (2018) [2006]. «Теория типов». Стэнфордская энциклопедия философии .
• Томпсон, Саймон (1991). Теория типов и функциональное программирование. Аддисон-Уэсли. ISBN 0-201-41667-0. Архивировано из оригинала 23 марта 2021 г. Проверено 3 апреля 2006 г.
• Хиндли, Дж. Роджер (2008) [1995]. Базовая теория простых типов . Издательство Кембриджского университета. ISBN 978-0-521-05422-5.Хорошее введение в простую теорию типов для специалистов по информатике; Однако описанная система не совсем STT Черча. Рецензия на книгу. Архивировано 7 июня 2011 г. в Wayback Machine.
• Камареддин, Файруз Д.; Лаан, Тван; Недерпельт, Роб П. (2004). Современный взгляд на теорию типов: от ее истоков до сегодняшнего дня . Спрингер. ISBN 1-4020-2334-0.
• Феррейрос, Хосе; Домингес, Хосе Феррейрос (2007). «X. Логика и теория типов в межвоенный период». Лабиринт мысли: история теории множеств и ее роль в современной математике (2-е изд.). Спрингер. ISBN 978-3-7643-8349-7.
• Лаан, ТДЛ (1997). Эволюция теории типов в логике и математике (PDF) (доктор философии). Эйндховенский технологический университет. дои : 10.6100/IR498552. ISBN 90-386-0531-5. Архивировано (PDF) из оригинала 9 октября 2022 г.
• Монтегю, Р. (1973) «Правильное обращение с количественной оценкой в ​​обычном английском языке». В KJJ Hintikka, JME Moravcsik и P. Suppes (ред.), «Подходы к естественному языку» (Synthese Library, 49), Dordrecht: Reidel, 221–242; перепечатано в Portner and Partee (ред.), 2002 г., стр. 17–35. См.: Семантика Монтегю, Стэнфордская энциклопедия философии.

Примечания

1. См. § Термины и типы.
2. Например, в системе типов Джулии абстрактные типы не имеют экземпляров, но могут иметь подтип, ^{[1] : 110} , тогда как конкретные типы не имеют подтипов, но могут иметь экземпляры для « документации, оптимизации и отправки ». ^[2]
3. Чёрч продемонстрировал свой логистический метод с помощью своей простой теории типов ^[4] и объяснил свой метод в 1956 году, ^[5], страницы 47–68.
4. Например, в Julia функция без имени, но с двумя параметрами в некотором кортеже (x,y) может быть обозначена, скажем, (x,y) -> x^5+yкак анонимная функция. ^[23]

Рекомендации

1. Бальберт, Иво (2015) Начало работы с ISBN программирования Джулии 978-1-78328-479-5
2. docs.julialang.org v.1 Типы, заархивированные 24 марта 2022 г. в Wayback Machine.
3. Стэнфордская энциклопедия философии (редакция: понедельник, 12 октября 2020 г.) Парадокс Рассела. Архивировано 18 декабря 2021 г. в Wayback Machine 3. Ранние ответы на парадокс.
4. Черч, Алонсо (1940). «Формулировка простой теории типов». Журнал символической логики . 5 (2): 56–68. дои : 10.2307/2266170. JSTOR  2266170. S2CID  15889861.
5. Алонзо Черч (1956) Введение в математическую логику, том 1
6. ETCS в n Lab
7. Хацикириакидис, Стергиос; Ло, Чжаохуэй (07 февраля 2017 г.). Современные перспективы теоретико-типовой семантики. Спрингер. ISBN 978-3-319-50422-3. Архивировано из оригинала 10 августа 2023 г. Проверено 29 июля 2022 г.
8. Зима, Йоад (8 апреля 2016 г.). Элементы формальной семантики: введение в математическую теорию значения естественного языка. Издательство Эдинбургского университета. ISBN 978-0-7486-7777-1. Архивировано из оригинала 10 августа 2023 г. Проверено 29 июля 2022 г.
9. Купер, Робин. «Теория типов и семантика в движении. Архивировано 10 мая 2022 г. в Wayback Machine ». Справочник по философии науки 14 (2012): 271–323.
10. Барвайз, Джон; Купер, Робин (1981) Обобщенные кванторы и лингвистика и философия естественного языка 4 (2): 159–219 (1981)
11. Купер, Робин (2005). «Записи и типы записей в семантической теории». Журнал логики и вычислений . 15 (2): 99–112. doi : 10.1093/logcom/exi004.
12. Купер, Робин (2010). Теория типов и семантика в движении . Справочник по философии науки. Том 14: Философия лингвистики . Эльзевир.
13. Мартин-Лёф, Пер (1 декабря 1987). «Истинность предложения, очевидность суждения, достоверность доказательства». Синтезируйте . 73 (3): 407–420. дои : 10.1007/BF00484985. ISSN  1573-0964.
14. Программа Uniвалентных фондов (2013). Гомотопическая теория типов: одновалентные основы математики. Гомотопическая теория типов.
15. Смит, Питер. «Типы системы доказательств» (PDF) . Logicmatters.net . Архивировано (PDF) из оригинала 9 октября 2022 г. Проверено 29 декабря 2021 г.
16. Хенк Барендрегт; Уил Деккерс; Ричард Стэтман (20 июня 2013 г.). Лямбда-исчисление с типами. Издательство Кембриджского университета. стр. 1–66. ISBN 978-0-521-76614-2.
17. «Правила интуиционистской теории типов Мартина-Лёфа» (PDF) . Архивировано (PDF) из оригинала 21 октября 2021 г. Проверено 22 января 2022 г.
18. «Доказательство от противного». нлаб . Архивировано из оригинала 13 августа 2023 года . Проверено 29 декабря 2021 г.
19. Хайнеман, Джордж Т.; Бессай, Ян; Дюддер, Борис; Рехоф, Якоб (2016). «Долгий и извилистый путь к модульному синтезу». Использование формальных методов, верификация и валидация: фундаментальные методы . ISoLA 2016. Конспекты лекций по информатике. Том. 9952. Спрингер. стр. 303–317. дои : 10.1007/978-3-319-47166-2_21. ISBN 978-3-319-47165-5.
20. Белл, Джон Л. (2012). «Типы, наборы и категории» (PDF) . В Канамори, Акихиро (ред.). Наборы и расширения в двадцатом веке . Справочник по истории логики. Том. 6. Эльзевир. ISBN 978-0-08-093066-4. Архивировано (PDF) из оригинала 17 апреля 2018 г. Проверено 3 ноября 2012 г.
21. Стерлинг, Джонатан; Ангиули, Карло (29 июня 2021 г.). «Нормализация для теории кубических типов». 2021 36-й ежегодный симпозиум ACM/IEEE по логике в информатике (LICS) . Рим, Италия: IEEE. стр. 1–15. arXiv : 2101.11479 . doi : 10.1109/LICS52264.2021.9470719. ISBN 978-1-6654-4895-6. S2CID  231719089. Архивировано из оригинала 13 августа 2023 г. Проверено 21 июня 2022 г.
22. Коэн, Сирил; Коканд, Тьерри; Хубер, Саймон; Мёртберг, Андерс (2016). «Теория кубических типов: конструктивная интерпретация аксиомы однолистности» (PDF) . 21-я Международная конференция по типам доказательств и программ (TYPES 2015) . arXiv : 1611.02108 . doi :10.4230/LIPIcs.CVIT.2016.23 (неактивен 31 января 2024 г.). Архивировано (PDF) из оригинала 9 октября 2022 г.{{cite journal}}: CS1 maint: DOI inactive as of January 2024 (link)
23. Бальберт, Иво (2015) Начало работы с Джулией
24. Бове, Ана; Дюбьер, Питер (2009), Бове, Ана; Барбоса, Луис Соарес; Пардо, Альберто; Пинто, Хорхе Соуза (ред.), «Зависимые типы на работе», Языковая инженерия и тщательная разработка программного обеспечения: Международная летняя школа LerNet ALFA 2008, Пириаполис, Уругвай, 24 февраля - 1 марта 2008 г., Пересмотренные учебные лекции , Конспекты лекций на компьютере Наука, Берлин, Гейдельберг: Springer, стр. 57–99, номер документа : 10.1007/978-3-642-03153-3_2, ISBN. 978-3-642-03153-3, получено 18 января 2024 г.
25. Барендегт, Хенк (апрель 1991 г.). «Введение в системы обобщенных типов». Журнал функционального программирования . 1 (2): 125–154. дои : 10.1017/S0956796800020025. hdl : 2066/17240 – через Cambridge Core.
26. Милевский, Бартош. «Математическое программирование (изучение теории типов)». YouTube . Архивировано из оригинала 22 января 2022 г. Проверено 22 января 2022 г.
27. «Аксиомы и вычисления». Доказательство теорем в Lean . Архивировано из оригинала 22 декабря 2021 года . Проверено 21 января 2022 г.
28. «Аксиома К». нЛаб . Архивировано из оригинала 19 января 2022 г. Проверено 21 января 2022 г.

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

Вводный материал

• Теория типов в nLab, где есть статьи на многие темы.
• Статья об интуиционистской теории типов в Стэнфордской энциклопедии философии
• Книга Хенка Барендрегта «Лямбда-исчисление с типами»
• Строительное исчисление / Бумага в стиле учебника по типизированному лямбда-исчислению от Хельмута Брандла
• Заметки Пера Мартина-Лёфа по интуиционистской теории типов
• Программирование в книге Мартина-Лёфа «Теория типов»
• Книга «Теория гомотопических типов», в которой теория гомотопических типов предлагается в качестве математической основы.

Расширенный материал

• Роберт Л. Констебль (ред.). «Теория вычислительных типов». Схоларпедия .
• Форум TYPES — модерируемый форум электронной почты, посвященный теории типов в информатике, работающий с 1987 года.
• Книга Nuprl: «Введение в теорию типов».
• Типы Проектные конспекты лекций летних школ 2005–2008 гг.
  • В летней школе 2005 года проводятся вводные лекции.
• Летняя школа языков программирования штата Орегон, множество лекций и несколько заметок.
  • Лекции лета 2013 г., включая выступления Роберта Харпера на YouTube.
  • Лето 2015 г. Типы, логика, семантика и проверка
• Блог Андрея Бауэра