Система типа Хиндли–Милнера

Система типов, используемая в программировании и математике

Система типов Хиндли–Милнера ( HM ) — это классическая система типов для лямбда-исчисления с параметрическим полиморфизмом . Она также известна как Дамас–Милнер или Дамас–Хиндли–Милнер . Впервые она была описана Дж. Роджером Хиндли ^[1] и позднее переоткрыта Робином Милнером ^[2] . Луис Дамас внес тесный формальный анализ и доказательство метода в своей докторской диссертации. ^{[3] [4]}

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

Введение

Как метод вывода типов, метод Хиндли–Милнера способен выводить типы переменных, выражений и функций из программ, написанных в совершенно нетипизированном стиле. Будучи чувствительным к области действия , он не ограничивается выводом типов только из небольшой части исходного кода, а скорее из полных программ или модулей. Способный также справляться с параметрическими типами , он является ядром систем типов многих функциональных языков программирования. Впервые он был применен таким образом в языке программирования ML .

Источником является алгоритм вывода типа для простого типизированного лямбда-исчисления , разработанный Хаскеллом Карри и Робертом Фейсом в 1958 году. ^{[ требуется ссылка ]} В 1969 году Дж. Роджер Хиндли расширил эту работу и доказал, что их алгоритм всегда выводит наиболее общий тип. В 1978 году Робин Милнер ^[5] независимо от работы Хиндли предоставил эквивалентный алгоритм, алгоритм W. В 1982 году Луис Дамас ^[4] наконец доказал, что алгоритм Милнера является полным, и расширил его для поддержки систем с полиморфными ссылками.

Мономорфизм против полиморфизма

В простом типизированном лямбда-исчислении типы T являются либо константами атомарного типа, либо типами функций формы . Такие типы являются мономорфными . Типичными примерами являются типы, используемые в арифметических значениях: ${\displaystyle T\rightarrow T}$

3 : Число сложить 3 4 : Число добавить : Номер -> Номер -> Номер

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

id ≡ λ x . x

который просто возвращает любое значение, к которому он применен. Менее тривиальные примеры включают параметрические типы, такие как списки .

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

минусы: forall a . a -> Список a -> Список a nil : forall a . Список a идентификатор : forall a . a -> a

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

id' : Строка -> Строкаnil' : Номер списка

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

В отличие от систем типов, используемых, например, в Pascal (1970) или C (1972), которые поддерживают только мономорфные типы, HM разработан с упором на параметрический полиморфизм. Последователи упомянутых языков, такие как C++ (1985), сосредоточились на различных типах полиморфизма, а именно на подтипировании в связи с объектно-ориентированным программированием и перегрузкой . Хотя подтипирование несовместимо с HM, вариант систематической перегрузки доступен в основанной на HM системе типов Haskell.

Let-полиморфизм

При расширении вывода типа для простого типизированного лямбда-исчисления в сторону полиморфизма необходимо решить, допустимо ли назначение полиморфного типа не только как типа выражения, но и как типа λ-связанной переменной. Это позволило бы назначить универсальный тип идентичности переменной 'id' в:

(λ id . ... (id 3) ... (id "текст") ... ) (λ x . x)

Разрешение этого приводит к полиморфному лямбда-исчислению ; однако, к сожалению, вывод типа в этой системе неразрешим. ^[6] Вместо этого HM отличает переменные, которые непосредственно связаны с выражением, от более общих λ-связанных переменных, называя бывшие let-связанные переменные, и позволяет назначать полиморфные типы только им. Это приводит к let-полиморфизму , где приведенный выше пример принимает форму

 пусть id = λ x . x в ... (id 3) ... (id "текст") ...

который может быть типизирован с полиморфным типом для 'id'. Как указано, синтаксис выражения расширен, чтобы сделать переменные, связанные с let, явными, и, ограничивая систему типов, чтобы разрешить только переменным, связанным с let, иметь полиморфные типы, в то время как параметры в лямбда-абстракциях должны получить мономорфный тип, вывод типа становится разрешимым.

Обзор

Оставшаяся часть статьи выглядит следующим образом:

• Определена система типов HM. Это делается путем описания системы вывода, которая точно определяет, какие выражения имеют какой тип, если таковой имеется.
• Оттуда он работает над реализацией метода вывода типа. После введения синтаксически-ориентированного варианта вышеуказанной дедуктивной системы он набрасывает эффективную реализацию (алгоритм J), апеллируя в основном к металогической интуиции читателя.
• Поскольку остается открытым вопрос о том, действительно ли алгоритм J реализует исходную систему вывода, вводится менее эффективная реализация (алгоритм W) и дается намек на ее использование в доказательстве.
• Наконец, обсуждаются дополнительные темы, связанные с алгоритмом.

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

Система типа Хиндли–Милнера

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

Синтаксис

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

Типы синтаксически делятся на две группы: монотипы и политипы. ^{[примечание 2]}

Монотипии

Монотипы всегда обозначают определенный тип. Монотипы синтаксически представлены как термины . ${\displaystyle \tau }$

Примерами монотипов являются константы типа, такие как или , и параметрические типы, такие как . Последние типы являются примерами приложений функций типа , например, из набора , где верхний индекс указывает количество параметров типа. Полный набор функций типа произволен в HM, ^{[примечание 3]} за исключением того, что он должен содержать по крайней мере , тип функций. Он часто записывается в инфиксной нотации для удобства. Например, функция, отображающая целые числа в строки, имеет тип . Опять же, скобки могут использоваться для устранения неоднозначности выражения типа. Приложение связывает сильнее, чем инфиксная стрелка, которая является правосвязывающей. ${\displaystyle {\mathtt {int}}}$ ${\displaystyle {\mathtt {string}}}$ ${\displaystyle {\mathtt {Map\ (Set\ string)\ int}}}$ ${\displaystyle \{{\mathtt {Map^{2},\ Set^{1},\ string^{0},\ int^{0}}},\ \rightarrow ^{2}\}}$ ${\displaystyle C}$ ${\displaystyle \rightarrow ^{2}}$ ${\displaystyle {\mathtt {int}}\rightarrow {\mathtt {string}}}$

Типовые переменные допускаются как монотипы. Монотипы не следует путать с мономорфными типами, которые исключают переменные и допускают только основные термины.

Два монотипа равны, если они имеют одинаковые термины.

Политипы

Политипы (или схемы типов ) — это типы, содержащие переменные, связанные нулем или более квантификаторами for-all, например . ${\displaystyle \forall \alpha .\alpha \rightarrow \alpha }$

Функция с политипом может сопоставить любое значение того же типа с собой, а функция тождества является значением для этого типа. ${\displaystyle \forall \alpha .\alpha \rightarrow \alpha }$

В качестве другого примера, это тип функции, отображающей все конечные множества в целые числа. Функция, которая возвращает мощность множества , будет значением этого типа. ${\displaystyle \forall \alpha .({\mathtt {Set}}\ \alpha )\rightarrow {\mathtt {int}}}$

Квантификаторы могут появляться только на верхнем уровне. Например, тип исключается синтаксисом типов. Также монотипы включены в политипы, таким образом, тип имеет общую форму , где и является монотипом. ${\displaystyle \forall \alpha .\alpha \rightarrow \forall \alpha .\alpha }$ ${\displaystyle \forall \alpha _{1}\dots \forall \alpha _{n}.\tau }$ ${\displaystyle n\geq 0}$ ${\displaystyle \tau }$

Равенство политипов зависит от переупорядочения квантификации и переименования квантифицированных переменных ( -конверсия). Кроме того, квантифицированные переменные, не встречающиеся в монотипе, могут быть отброшены. ${\displaystyle \alpha }$

Контекст и набор текста

Чтобы осмысленно объединить все еще разрозненные части (синтаксические выражения и типы), нужна третья часть: контекст. Синтаксически контекст — это список пар , называемых присваиваниями , предположениями или привязками , каждая пара утверждает, что переменная-значение имеет тип . Все три части, объединенные вместе, дают суждение о типе в форме , утверждающее, что при предположениях выражение имеет тип . ${\displaystyle x:\sigma }$ ${\displaystyle x_{i}}$ ${\displaystyle \sigma _{i}.}$ ${\displaystyle \Gamma \ \vdash \ e:\sigma }$ ${\displaystyle \Gamma }$ ${\displaystyle e}$ ${\displaystyle \sigma }$

Свободные переменные типа

В типе символ является квантификатором, связывающим переменные типа в монотипе . Переменные называются квантифицированными , и любое вхождение квантифицированной переменной типа в называется связанным , а все несвязанные переменные типа в называются свободными . Помимо квантификации в политипах, переменные типа также могут быть связаны, появляясь в контексте, но с обратным эффектом в правой части . Такие переменные затем ведут себя там как константы типа. Наконец, переменная типа может законно появляться несвязанной в типизации, и в этом случае они неявно все-квантифицированы. ${\displaystyle \forall \alpha _{1}\dots \forall \alpha _{n}.\tau }$ ${\displaystyle \forall }$ ${\displaystyle \alpha _{i}}$ ${\displaystyle \tau }$ ${\displaystyle \alpha _{i}}$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle \forall }$ ${\displaystyle \vdash }$

Наличие как связанных, так и несвязанных переменных типов немного необычно в языках программирования. Часто все переменные типов неявно обрабатываются как все-квантифицированные. Например, в Prolog нет предложений со свободными переменными . Аналогично в Haskell, ^{[примечание 4]} , где все переменные типов неявно встречаются квантифицированными, т. е. тип Haskell здесь a -> aозначает . Связанный и также очень необычный эффект связывания правой стороны присваиваний. ${\displaystyle \forall \alpha .\alpha \rightarrow \alpha }$ ${\displaystyle \sigma }$

Обычно смесь как связанных, так и несвязанных переменных типа возникает из-за использования свободных переменных в выражении. Константная функция K = дает пример. Она имеет монотип . Можно принудительно вызвать полиморфизм с помощью . При этом имеет тип . Свободная переменная монотипа происходит из типа переменной, связанной в окружающей области видимости. имеет тип . Можно представить, что свободная переменная типа в типе связана с типом в типе . Но такая область видимости не может быть выражена в HM. Скорее, связывание реализуется контекстом. ${\displaystyle \lambda x.\lambda y.x}$ ${\displaystyle \alpha \rightarrow \beta \rightarrow \alpha }$ ${\displaystyle \mathbf {let} \ k=\lambda x.(\mathbf {let} \ f=\lambda y.x\ \mathbf {in} \ f)\ \mathbf {in} \ k}$ ${\displaystyle f}$ ${\displaystyle \forall \gamma .\gamma \rightarrow \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle x}$ ${\displaystyle k}$ ${\displaystyle \forall \alpha \forall \beta .\alpha \rightarrow \beta \rightarrow \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle f}$ ${\displaystyle \forall \alpha }$ ${\displaystyle k}$

Тип заказа

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

Например, тождество может иметь своим типом как или и многие другие, но не . Наиболее общим типом для этой функции является , в то время как другие более конкретны и могут быть выведены из общего путем последовательной замены другого типа для параметра типа , т. е. квантифицированной переменной . Контрпример не работает, поскольку замена не является последовательной. ${\displaystyle \lambda x.x}$ ${\displaystyle \forall \alpha .\alpha \rightarrow \alpha }$ ${\displaystyle {\texttt {string}}\rightarrow {\texttt {string}}}$ ${\displaystyle {\texttt {int}}\rightarrow {\texttt {int}}}$ ${\displaystyle {\texttt {int}}\rightarrow {\texttt {string}}}$ ${\displaystyle \forall \alpha .\alpha \rightarrow \alpha }$ ${\displaystyle \alpha }$

Последовательную замену можно сделать формальной, применив замену к термину типа , записанному . Как показывает пример, замена не только тесно связана с порядком, который выражает, что тип является более или менее специальным, но и с всеквантификацией, которая позволяет применять замену. ${\displaystyle S=\left\{\ a_{i}\mapsto \tau _{i},\ \dots \ \right\}}$ ${\displaystyle \tau }$ ${\displaystyle S\tau }$

Формально, в HM, тип является более общим, чем , формально , ​​если некоторая квантифицированная переменная в последовательно подставляется так, что получается, как показано на боковой панели. Этот порядок является частью определения типа системы типов. ${\displaystyle \sigma '}$ ${\displaystyle \sigma }$ ${\displaystyle \sigma '\sqsubseteq \sigma }$ ${\displaystyle \sigma '}$ ${\displaystyle \sigma }$

В нашем предыдущем примере применение подстановки привело бы к результату . ${\displaystyle S=\left\{\alpha \mapsto {\texttt {string}}\right\}}$ ${\displaystyle \forall \alpha .\alpha \rightarrow \alpha \sqsubseteq {\texttt {string}}\rightarrow {\texttt {string}}}$

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

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

Отношение представляет собой частичный порядок и является его наименьшим элементом. ${\displaystyle \sqsubseteq }$ ${\displaystyle \forall \alpha .\alpha }$

Основной тип

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

Замена в типизациях

Определенный выше порядок типов может быть распространен на типизации, поскольку подразумеваемая всеквантификация типизаций обеспечивает последовательную замену:

${\displaystyle \Gamma \vdash e:\sigma \quad \Longrightarrow \quad S\Gamma \vdash e:S\sigma }$

В отличие от правила специализации, это не часть определения, а, как и неявная всеквантификация, скорее следствие правил типа, определенных далее. Свободные переменные типа в типизации служат в качестве заполнителей для возможного уточнения. Связывающий эффект окружения со свободными переменными типа справа от того, что запрещает их замену в правиле специализации, снова заключается в том, что замена должна быть последовательной и должна включать всю типизацию. ${\displaystyle \vdash }$

В этой статье будут рассмотрены четыре различных набора правил:

1. ${\displaystyle \vdash _{D}}$декларативная система
2. ${\displaystyle \vdash _{S}}$синтаксическая система
3. ${\displaystyle \vdash _{J}}$алгоритм J
4. ${\displaystyle \vdash _{W}}$алгоритм W

Дедуктивная система

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

Доказательство с использованием правил — это последовательность суждений, в которой все предпосылки перечислены перед заключением. Примеры ниже показывают возможный формат доказательств. Слева направо каждая строка показывает заключение, примененное правило и предпосылки, либо ссылаясь на более раннюю строку (номер), если предпосылка является суждением, либо делая предикат явным. ${\displaystyle [{\mathtt {Name}}]}$

Правила набора текста

См. также правила набора текста

В боковой рамке показаны правила вывода системы типа HM. Правила можно грубо разделить на две группы:

Первые четыре правила (доступ к переменной или функции), ( применение , т.е. вызов функции с одним параметром), ( абстракция , т.е. объявление функции) и (объявление переменной) сосредоточены вокруг синтаксиса, представляя одно правило для каждой формы выражения. Их значение очевидно с первого взгляда, поскольку они разлагают каждое выражение, доказывают их подвыражения и, наконец, объединяют отдельные типы, найденные в предпосылках, с типом в заключении. ${\displaystyle [{\mathtt {Var}}]}$ ${\displaystyle [{\mathtt {App}}]}$ ${\displaystyle [{\mathtt {Abs}}]}$ ${\displaystyle [{\mathtt {Let}}]}$

Вторая группа образована оставшимися двумя правилами и . Они обрабатывают специализацию и обобщение типов. Хотя правило должно быть ясно из раздела о специализации выше, оно дополняет первое, работая в противоположном направлении. Оно допускает обобщение, т. е. квантификацию монотипных переменных, не связанных в контексте. ${\displaystyle [{\mathtt {Inst}}]}$ ${\displaystyle [{\mathtt {Gen}}]}$ ${\displaystyle [{\mathtt {Inst}}]}$ ${\displaystyle [{\mathtt {Gen}}]}$

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

Пример : Доказательство того, где , можно записать ${\displaystyle \Gamma \vdash _{D}id(n):int}$ ${\displaystyle \Gamma =id:\forall \alpha .\alpha \rightarrow \alpha ,\ n:int}$

${\displaystyle {\begin{array}{llll}1:&\Gamma \vdash _{D}id:\forall \alpha .\alpha \rightarrow \alpha &[{\mathtt {Var}}]&(id:\forall \alpha .\alpha \rightarrow \alpha \in \Gamma )\\2:&\Gamma \vdash _{D}id:int\rightarrow int&[{\mathtt {Inst}}]&(1),\ (\forall \alpha .\alpha \rightarrow \alpha \sqsubseteq int\rightarrow int)\\3:&\Gamma \vdash _{D}n:int&[{\mathtt {Var}}]&(n:int\in \Gamma )\\4:&\Gamma \vdash _{D}id(n):int&[{\mathtt {App}}]&(2),\ (3)\\\end{array}}}$

Пример : Для демонстрации обобщения ниже показано: ${\displaystyle \vdash _{D}\ {\textbf {let}}\,id=\lambda x.x\ {\textbf {in}}\ id\,:\,\forall \alpha .\alpha \rightarrow \alpha }$

${\displaystyle {\begin{array}{llll}1:&x:\alpha \vdash _{D}x:\alpha &[{\mathtt {Var}}]&(x:\alpha \in \left\{x:\alpha \right\})\\2:&\vdash _{D}\lambda x.x:\alpha \rightarrow \alpha &[{\mathtt {Abs}}]&(1)\\3:&id:\alpha \rightarrow \alpha \vdash _{D}id:\alpha \rightarrow \alpha &[{\mathtt {Var}}]&(id:\alpha \rightarrow \alpha \in \left\{id:\alpha \rightarrow \alpha \right\})\\4:&\vdash _{D}{\textbf {let}}\,id=\lambda x.x\ {\textbf {in}}\ id\,:\,\alpha \rightarrow \alpha &[{\mathtt {Let}}]&(2),\ (3)\\5:&\vdash _{D}{\textbf {let}}\,id=\lambda x.x\ {\textbf {in}}\ id\,:\,\forall \alpha .\alpha \rightarrow \alpha &[{\mathtt {Gen}}]&(4),\ (\alpha \not \in free(\epsilon ))\\\end{array}}}$

Let-полиморфизм

Незаметный сразу, набор правил кодирует регулирование, при котором тип может быть обобщен или нет путем слегка варьирующегося использования моно- и политипов в правилах и . Помните, что и обозначают поли- и монотипы соответственно. ${\displaystyle [{\mathtt {Abs}}]}$ ${\displaystyle [{\mathtt {Let}}]}$ ${\displaystyle \sigma }$ ${\displaystyle \tau }$

В правиле переменная значения параметра функции добавляется в контекст с мономорфным типом через предпосылку , тогда как в правиле переменная входит в среду в полиморфной форме . Хотя в обоих случаях наличие в контексте препятствует использованию правила обобщения для любой свободной переменной в назначении, это регулирование заставляет тип параметра в -выражении оставаться мономорфным, тогда как в let-выражении переменная может быть введена полиморфной, делая возможными специализации. ${\displaystyle [{\mathtt {Abs}}]}$ ${\displaystyle \lambda x.e}$ ${\displaystyle \Gamma ,\ x:\tau \vdash _{D}e:\tau '}$ ${\displaystyle [{\mathtt {Let}}]}$ ${\displaystyle \Gamma ,\ x:\sigma \vdash _{D}e_{1}:\tau }$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle \lambda }$

Вследствие этого регулирования не может быть типизирован, так как параметр находится в мономорфной позиции, в то время как имеет тип , так как был введен в let-выражение и поэтому рассматривается как полиморфный. ${\displaystyle \lambda f.(f\,{\textrm {true}},f\,{\textrm {0}})}$ ${\displaystyle f}$ ${\displaystyle {\textbf {let}}\ f=\lambda x.x\,{\textbf {in}}\,(f\,{\textrm {true}},f\,{\textrm {0}})}$ ${\displaystyle (bool,int)}$ ${\displaystyle f}$

Правило обобщения

Правило обобщения также заслуживает более пристального внимания. Здесь все-квантификация, подразумеваемая в посылке, просто перемещается в правую сторону в заключении, связанная явным всеобщим квантификатором. Это возможно, поскольку не встречается свободно в контексте. Опять же, хотя это делает правило обобщения правдоподобным, оно на самом деле не является следствием. Напротив, правило обобщения является частью определения системы типов HM, а неявная все-квантификация — следствием. ${\displaystyle \Gamma \vdash _{D}e:\sigma }$ ${\displaystyle \vdash _{D}}$ ${\displaystyle \alpha }$

Алгоритм вывода

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

Степени свободы выбора правил

Выделяя точки в доказательстве, где вообще невозможно никакое решение, первая группа правил, сосредоточенная вокруг синтаксиса, не оставляет выбора, поскольку каждому синтаксическому правилу соответствует уникальное правило типизации, которое определяет часть доказательства, в то время как между заключением и посылками этих фиксированных частей могут возникать цепочки и . Такая цепочка может также существовать между заключением доказательства и правилом для самого верхнего выражения. Все доказательства должны иметь такую ​​набросанную форму. ${\displaystyle [{\mathtt {Inst}}]}$ ${\displaystyle [{\mathtt {Gen}}]}$

Поскольку единственный выбор в доказательстве в отношении выбора правил — это цепочки и , форма доказательства предполагает вопрос, можно ли сделать его более точным, где эти цепочки могут не понадобиться. Это на самом деле возможно и приводит к варианту системы правил без таких правил. ${\displaystyle [{\mathtt {Inst}}]}$ ${\displaystyle [{\mathtt {Gen}}]}$

Система правил, ориентированная на синтаксис

Современная трактовка HM использует чисто синтаксически-ориентированную систему правил, разработанную Клементом ^[7] в качестве промежуточного шага. В этой системе специализация располагается непосредственно после исходного правила и объединяется с ним, в то время как обобщение становится частью правила. Там также определяется, что обобщение всегда производит наиболее общий тип путем введения функции , которая квантифицирует все монотипные переменные, не связанные в . ${\displaystyle [{\mathtt {Var}}]}$ ${\displaystyle [{\mathtt {Let}}]}$ ${\displaystyle {\bar {\Gamma }}(\tau )}$ ${\displaystyle \Gamma }$

Формально, чтобы подтвердить, что эта новая система правил эквивалентна исходной , нужно показать, что , что распадается на два поддоказательства: ${\displaystyle \vdash _{S}}$ ${\displaystyle \vdash _{D}}$ ${\displaystyle \Gamma \vdash _{D}\ e:\sigma \Leftrightarrow \Gamma \vdash _{S}\ e:\sigma }$

• ${\displaystyle \Gamma \vdash _{D}\ e:\sigma \Leftarrow \Gamma \vdash _{S}\ e:\sigma }$( Последовательность )
• ${\displaystyle \Gamma \vdash _{D}\ e:\sigma \Rightarrow \Gamma \vdash _{S}\ e:\sigma }$( Полнота )

Хотя согласованность можно увидеть, разложив правила и на доказательства в , вероятно, видно, что является неполным, как нельзя показать в , например, но только . Однако лишь немного более слабая версия полноты доказуема ^[8] , а именно ${\displaystyle [{\mathtt {Let}}]}$ ${\displaystyle [{\mathtt {Var}}]}$ ${\displaystyle \vdash _{S}}$ ${\displaystyle \vdash _{D}}$ ${\displaystyle \vdash _{S}}$ ${\displaystyle \lambda \ x.x:\forall \alpha .\alpha \rightarrow \alpha }$ ${\displaystyle \vdash _{S}}$ ${\displaystyle \lambda \ x.x:\alpha \rightarrow \alpha }$

• ${\displaystyle \Gamma \vdash _{D}\ e:\sigma \Rightarrow \Gamma \vdash _{S}\ e:\tau \wedge {\bar {\Gamma }}(\tau )\sqsubseteq \sigma }$

подразумевая, что можно вывести основной тип выражения, что позволит нам в конечном итоге обобщить доказательство. ${\displaystyle \vdash _{S}}$

Сравнивая и , теперь в суждениях всех правил появляются только монотипы. Кроме того, форма любого возможного доказательства с системой вывода теперь идентична форме выражения (оба рассматриваются как деревья ). Таким образом, выражение полностью определяет форму доказательства. В форма, скорее всего, будет определена относительно всех правил, кроме и , которые позволяют строить произвольно длинные ветви (цепочки) между другими узлами. ${\displaystyle \vdash _{D}}$ ${\displaystyle \vdash _{S}}$ ${\displaystyle \vdash _{D}}$ ${\displaystyle [{\mathtt {Inst}}]}$ ${\displaystyle [{\mathtt {Gen}}]}$

Степени свободы, устанавливающие правила

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

Здесь в игру вступает порядок подстановки (специализации). Хотя на первый взгляд локально определить типы невозможно, есть надежда, что их можно уточнить с помощью порядка при обходе дерева доказательств, дополнительно предполагая, поскольку полученный алгоритм должен стать методом вывода, что тип в любой посылке будет определен как наилучший из возможных. И на самом деле, можно, как следует из правил : ${\displaystyle \vdash _{S}}$

• [ Abs ] : критический выбор — τ . На данный момент о τ ничего не известно , поэтому можно только предположить наиболее общий тип, которым является . План состоит в том, чтобы специализировать тип, если это станет необходимым. К сожалению, политип в этом месте не допускается, поэтому на данный момент придется ограничиться некоторым α . Чтобы избежать нежелательных захватов, переменная типа, еще не включенная в доказательство, является безопасным выбором. Кроме того, следует помнить, что этот монотип еще не зафиксирован, но может быть уточнен. ${\displaystyle \forall \alpha .\alpha }$
• [ Var ] : Выбор заключается в том, как уточнить σ . Поскольку любой выбор типа τ здесь зависит от использования переменной, которая локально не известна, наиболее безопасным вариантом будет наиболее общий. Используя тот же метод, что и выше, можно инстанцировать все квантифицированные переменные в σ с помощью новых монотипных переменных, снова оставляя их открытыми для дальнейшего уточнения.
• [ Let ] : Правило не оставляет выбора. Сделано.
• [ Приложение ] : Только правило приложения может потребовать уточнения переменных, «открытых» до сих пор, как того требуют обе предпосылки.
  1. Первая посылка обязывает результат вывода иметь форму . ${\displaystyle \tau \rightarrow \tau '}$
     • Если это так, то отлично. Позже можно будет выбрать его τ' для результата.
     • Если нет, то это может быть открытая переменная. Тогда это можно уточнить до требуемой формы с двумя новыми переменными, как и раньше.
     • В противном случае проверка типа не выполняется, поскольку первая предпосылка вывела тип, который не является и не может быть преобразован в тип функции.
  2. Вторая предпосылка требует, чтобы выведенный тип был равен τ первой предпосылки. Теперь есть два возможно разных типа, возможно, с переменными открытого типа, которые можно сравнить и сделать равными, если это возможно. Если это так, то находится уточнение, а если нет, то снова обнаруживается ошибка типа. Известен эффективный метод «сделать два термина равными» путем подстановки, объединение Робинсона в сочетании с так называемым алгоритмом Union-Find . ^{[ необходима цитата ]}

Если кратко суммировать алгоритм union-find, то, учитывая набор всех типов в доказательстве, он позволяет сгруппировать их в классы эквивалентности с помощью процедуры union и выбрать представителя для каждого такого класса с помощью процедуры find . Подчеркивая слово процедура в смысле побочного эффекта , мы явно выходим за рамки логики, чтобы подготовить эффективный алгоритм. Представитель a определяется таким образом, что если и a, и b являются переменными типа, то представитель произвольно является одним из них, но при объединении переменной и терма терм становится представителем. Предполагая реализацию union-find под рукой, можно сформулировать объединение двух монотипов следующим образом: ${\displaystyle {\mathtt {union}}(a,b)}$

объединить(ta, tb): та = найти(та) тб = найти(тб) если оба ta,tb являются членами формы D p1..pn с идентичными D,n , то унифицируйте (ta[i], tb[i]) для каждого соответствующего i- го параметра, иначе,  если хотя бы один из ta,tb является переменной типа , то союз(та, тб) еще ошибка «типы не совпадают»

Теперь, имея набросок алгоритма вывода под рукой, более формальное представление дается в следующем разделе. Он описан в Milner ^[2] P. 370 ff. как алгоритм J.

Алгоритм J

Представление алгоритма J является неправильным использованием нотации логических правил, поскольку оно включает побочные эффекты, но позволяет проводить прямое сравнение с , одновременно выражая эффективную реализацию. Теперь правила определяют процедуру с параметрами, дающими в заключении, где выполнение предпосылок происходит слева направо. ${\displaystyle \vdash _{S}}$ ${\displaystyle \Gamma ,e}$ ${\displaystyle \tau }$

Процедура специализируется на политипе путем копирования термина и замены связанных переменных типа последовательно новыми переменными монотипа. ' ' создает новую переменную монотипа. Вероятно, необходимо скопировать тип, вводя новые переменные для квантификации, чтобы избежать нежелательных захватов. В целом, алгоритм теперь действует, всегда делая наиболее общий выбор, оставляя специализацию унификации, которая сама по себе дает наиболее общий результат. Как отмечено выше, конечный результат должен быть обобщен до в конце, чтобы получить наиболее общий тип для данного выражения. ${\displaystyle inst(\sigma )}$ ${\displaystyle \sigma }$ ${\displaystyle newvar}$ ${\displaystyle {\bar {\Gamma }}(\tau )}$ ${\displaystyle \tau }$ ${\displaystyle {\bar {\Gamma }}(\tau )}$

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

Эффективность немного снижается, поскольку привязка переменных типа в контексте должна поддерживаться, чтобы разрешить вычисление и включить проверку наличия , чтобы предотвратить построение рекурсивных типов во время . Примером такого случая является , для которого ни один тип не может быть выведен с помощью HM. На практике типы являются лишь небольшими терминами и не создают расширяющихся структур. Таким образом, в анализе сложности можно рассматривать их сравнение как константу, сохраняя затраты O(1). ${\displaystyle {\bar {\Gamma }}(\tau )}$ ${\displaystyle {\mathit {unify}}(\alpha ,\tau )}$ ${\displaystyle \lambda \ x.(x\ x)}$

Доказательство алгоритма

В предыдущем разделе, при наброске алгоритма, его доказательство было намекнуто металогической аргументацией. Хотя это приводит к эффективному алгоритму J, неясно, отражает ли алгоритм должным образом системы вывода D или S, которые служат семантической базовой линией.

Наиболее критическим моментом в приведенной выше аргументации является уточнение монотипных переменных, связанных контекстом. Например, алгоритм смело меняет контекст при выводе eg , поскольку монотипная переменная, добавленная в контекст для параметра, позже должна быть уточнена при обработке приложения. Проблема в том, что правила вывода не допускают такого уточнения. Утверждение, что уточненный тип мог быть добавлен ранее вместо монотипной переменной, в лучшем случае является целесообразным. ${\displaystyle \lambda f.(f\ 1)}$ ${\displaystyle f}$ ${\displaystyle int\rightarrow \beta }$

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

${\displaystyle \Gamma \vdash _{S}e:\tau \quad \Longrightarrow \quad S\Gamma \vdash _{S}e:S\tau }$

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

Алгоритм W

Отсюда доказательство алгоритма J приводит к алгоритму W, который только делает побочные эффекты, налагаемые процедурой, явными, выражая ее последовательную композицию посредством подстановок . Представление алгоритма W на боковой панели по-прежнему использует побочные эффекты в операциях, выделенных курсивом, но теперь они ограничены генерацией новых символов. Форма суждения — , обозначающая функцию с контекстом и выражением в качестве параметра, производящую монотип вместе с подстановкой. — это версия без побочных эффектов производства подстановки, которая является наиболее общим унификатором . ${\displaystyle {\textit {union}}}$ ${\displaystyle S_{i}}$ ${\displaystyle \Gamma \vdash e:\tau ,S}$ ${\displaystyle {\textsf {mgu}}}$ ${\displaystyle {\textit {union}}}$

Хотя алгоритм W обычно считается алгоритмом HM и часто в литературе представляется непосредственно после системы правил, его цель описана Милнером ^[2] на стр. 369 следующим образом:

В его нынешнем виде W едва ли является эффективным алгоритмом; слишком часто применяются подстановки. Он был сформулирован для доказательства надежности. Теперь мы представляем более простой алгоритм J, который имитирует W в точном смысле.

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

Доказательство обязательств

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

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

Имея контекст , выражение не может быть напечатано ни в , ни в , но алгоритмы приходят с типом , где W дополнительно обеспечивает замену , что означает, что алгоритм не может обнаружить все ошибки типа. Это упущение можно легко исправить, более тщательно различая переменные доказательства и переменные монотипа. ${\displaystyle 1:int,\ f:\alpha }$ ${\displaystyle f\ 1}$ ${\displaystyle \vdash _{D}}$ ${\displaystyle \vdash _{S}}$ ${\displaystyle \beta }$ ${\displaystyle \left\{\alpha \mapsto int\rightarrow \beta \right\}}$

Авторы хорошо знали о проблеме, но решили не исправлять ее. Можно предположить, что за этим стоит прагматическая причина. Хотя более правильная реализация вывода типа позволила бы алгоритму работать с абстрактными монотипами, они не были нужны для предполагаемого применения, где ни один из элементов в уже существующем контексте не имеет свободных переменных. В этом свете ненужное усложнение было отброшено в пользу более простого алгоритма. Оставшимся недостатком является то, что доказательство алгоритма относительно системы правил менее общее и может быть сделано только для контекстов с в качестве побочного условия. ${\displaystyle free(\Gamma )=\emptyset }$

${\displaystyle {\begin{array}{lll}{\text{(Correctness)}}&\Gamma \vdash _{W}e:\tau ,S&\quad \Longrightarrow \quad \Gamma \vdash _{S}e:\tau \\{\text{(Completeness)}}&\Gamma \vdash _{S}e:\tau &\quad \Longrightarrow \quad \Gamma \vdash _{W}e:\tau ',S\quad \quad {\text{forall}}\ \tau \ {\text{where}}\ {\overline {\emptyset }}(\tau ')\sqsubseteq \tau \end{array}}}$

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

Чтобы должным образом доказать обязательства, необходимо сначала усилить их, чтобы позволить активировать лемму о подстановке, пронизывающую подстановку через и . Оттуда доказательства проводятся индукцией по выражению. ${\displaystyle S}$ ${\displaystyle \vdash _{S}}$ ${\displaystyle \vdash _{W}}$

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

Расширения

Рекурсивные определения

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

Правило набора текста

В оригинальной статье ^[4] показано, что рекурсия может быть реализована с помощью комбинатора . Таким образом, возможное рекурсивное определение можно сформулировать как . ${\displaystyle {\mathit {fix}}:\forall \alpha .(\alpha \rightarrow \alpha )\rightarrow \alpha }$ ${\displaystyle {\mathtt {rec}}\ v=e_{1}\ {\mathtt {in}}\ e_{2}\ ::={\mathtt {let}}\ v={\mathit {fix}}(\lambda v.e_{1})\ {\mathtt {in}}\ e_{2}}$

В качестве альтернативы возможно расширение синтаксиса выражения и дополнительное правило типизации:

${\displaystyle \displaystyle {\frac {\Gamma ,\Gamma '\vdash e_{1}:\tau _{1}\quad \dots \quad \Gamma ,\Gamma '\vdash e_{n}:\tau _{n}\quad \Gamma ,\Gamma ''\vdash e:\tau }{\Gamma \ \vdash \ {\mathtt {rec}}\ v_{1}=e_{1}\ {\mathtt {and}}\ \dots \ {\mathtt {and}}\ v_{n}=e_{n}\ {\mathtt {in}}\ e:\tau }}\quad [{\mathtt {Rec}}]}$

где

• ${\displaystyle \Gamma '=v_{1}:\tau _{1},\ \dots ,\ v_{n}:\tau _{n}}$
• ${\displaystyle \Gamma ''=v_{1}:{\bar {\Gamma }}(\ \tau _{1}\ ),\ \dots ,\ v_{n}:{\bar {\Gamma }}(\ \tau _{n}\ )}$

по сути, слияние и включение рекурсивно определенных переменных в монотипные позиции, где они встречаются слева от, но как политипы справа от него. ${\displaystyle [{\mathtt {Abs}}]}$ ${\displaystyle [{\mathtt {Let}}]}$ ${\displaystyle {\mathtt {in}}}$

Последствия

Хотя все вышесказанное очевидно, оно имеет свою цену.

Теория типов связывает лямбда-исчисление с вычислениями и логикой. Простая модификация выше влияет на оба:

• Свойство сильной нормализации становится недействительным, поскольку можно сформулировать нетерминированные термины.
• Логика рушится, потому что тип становится обитаемым . ${\displaystyle \forall a.a}$

Перегрузка

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

В то время как в функциональном программировании удалось избежать перегрузки ad hoc из-за вычислительных затрат как при проверке типов, так и при выводе ^{[ требуется ссылка ]} , было введено средство систематизации перегрузки, которое по форме и именованию напоминает объектно-ориентированное программирование, но работает на один уровень выше. «Экземпляры» в этой систематике не являются объектами (т. е. на уровне значений), а скорее типами. Пример быстрой сортировки, упомянутый во введении, использует перегрузку в порядках, имея следующую аннотацию типа в Haskell:

быстрая сортировка :: Порядок a => [ a ] ​​-> [ a ]       

Здесь тип aне только полиморфен, но и ограничен экземпляром некоторого класса типов Ord, который предоставляет предикаты порядка <и >=используется в теле функций. Затем соответствующие реализации этих предикатов передаются в быструю сортировку в качестве дополнительных параметров, как только быстрая сортировка используется на более конкретных типах, предоставляя единственную реализацию перегруженной функции quickSort.

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

Типы высшего порядка

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

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

Haskell вводит один более высокий уровень, называемый kind . В стандартном Haskell виды выводятся и используются лишь для описания арности конструкторов типов. Например, конструктор типа списка рассматривается как отображение типа (типа его элементов) в другой тип (тип списка, содержащего указанные элементы); в нотации это выражается как . Доступны расширения языка, которые расширяют виды для эмуляции функций зависимой системы типов . ^[9] ${\displaystyle *\to *}$

Подтипирование

Попытки объединить подтипирование и вывод типов вызвали некоторое разочарование. Накапливать и распространять ограничения подтипирования (в отличие от ограничений равенства типов) просто, делая полученные ограничения частью выведенных схем типизации, например , где — это ограничение на переменную типа . Однако, поскольку переменные типа больше не унифицируются с энтузиазмом в этом подходе, он имеет тенденцию генерировать большие и громоздкие схемы типизации, содержащие множество бесполезных переменных типа и ограничений, что делает их трудными для чтения и понимания. Поэтому были приложены значительные усилия для упрощения таких схем типизации и их ограничений с использованием методов, аналогичных методам упрощения недетерминированного конечного автомата (NFA) (полезных при наличии выведенных рекурсивных типов). ^[10] Совсем недавно Долан и Майкрофт ^[11] формализовали связь между упрощением схемы типизации и упрощением NFA и показали, что алгебраический подход к формализации подтипирования позволяет генерировать компактные основные схемы типизации для языка, похожего на ML (называемого MLsub). Примечательно, что предложенная ими схема типизации использовала ограниченную форму типов объединения и пересечения вместо явных ограничений. Позднее Парро утверждал ^[12], что эта алгебраическая формулировка эквивалентна относительно простому алгоритму, напоминающему алгоритм W, и что использование типов объединения и пересечения не является существенным. ${\displaystyle \forall \alpha .\ (\alpha \leq T)\Rightarrow \alpha \rightarrow \alpha }$ ${\displaystyle \alpha \leq T}$ ${\displaystyle \alpha }$

С другой стороны, вывод типа оказался более сложным в контексте объектно-ориентированных языков программирования, поскольку объектные методы, как правило, требуют полиморфизма первого класса в стиле System F (где вывод типа неразрешим) и из-за таких особенностей, как полиморфизм с ограничением F. Следовательно, системы типов с подтипированием, обеспечивающие объектно-ориентированное программирование, такие как система Карделли ^[13] , не поддерживают вывод типа в стиле HM. ${\displaystyle F_{<:}}$

Полиморфизм строк может использоваться как альтернатива подтипированию для поддержки таких языковых функций, как структурные записи. ^[14] Хотя этот стиль полиморфизма в некоторых отношениях менее гибок, чем подтипирование, в частности, требуя большего полиморфизма, чем строго необходимо, чтобы справиться с отсутствием направленности в ограничениях типов, его преимущество заключается в том, что его можно довольно легко интегрировать со стандартными алгоритмами HM.

Примечания

1. Вывод типа Хиндли–Милнера является DEXPTIME -полным. Фактически, простое решение о том, является ли программа ML типизируемой (без необходимости выводить тип), само по себе является DEXPTIME -полным. Нелинейное поведение проявляется, но в основном на патологических входных данных. Таким образом, доказательства теории сложности, полученные Mairson (1990) и Kfoury, Tiuryn ​​& Urzyczyn (1990), стали неожиданностью для исследовательского сообщества. ^{[ необходима цитата ]}
2. В оригинальной статье политипы называются «схемами типов».
3. Параметрические типы не присутствовали в исходной статье о HM и не нужны для представления метода. Ни одно из правил вывода ниже не будет заботиться о них или даже отмечать их. То же самое относится к непараметрическим «примитивным типам» в указанной статье. Все механизмы для вывода полиморфных типов могут быть определены без них. Они были включены сюда ради примеров, а также потому, что природа HM полностью посвящена параметрическим типам. Это происходит из типа функции , жестко зашитого в правилах вывода ниже, который уже имеет два параметра и был представлен здесь только как частный случай. ${\displaystyle C\ \tau \dots \tau }$ ${\displaystyle \tau \rightarrow \tau }$
4. Haskell предоставляет расширение языка ScopedTypeVariables, позволяющее включать в область видимости переменные всех квантифицированных типов.

Ссылки

1. Hindley, J. Roger (1969). «Принципиальная схема типа объекта в комбинаторной логике». Transactions of the American Mathematical Society . 146 : 29–60. doi :10.2307/1995158. JSTOR  1995158.
2. Милнер, Робин (1978). «Теория полиморфизма типов в программировании». Журнал компьютерных и системных наук . 17 (3): 348–374. CiteSeerX 10.1.1.67.5276 . doi :10.1016/0022-0000(78)90014-4. S2CID  388583. 
3. Дамас, Луис (1985). Назначение типов в языках программирования (диссертация доктора философии). Эдинбургский университет. hdl :1842/13555. CST-33-85.
4. Damas, Luis; Milner, Robin (1982). Основные схемы типов для функциональных программ (PDF) . 9-й симпозиум по принципам языков программирования (POPL'82). ACM. стр. 207–212. doi :10.1145/582153.582176. ISBN 978-0-89791-065-1.
5. Милнер, Робин (1978), «Теория полиморфизма типов в программировании», Журнал компьютерных и системных наук , 17 (3): 348–375, doi : 10.1016/0022-0000(78)90014-4 , hdl : 20.500.11820/d16745d7-f113-44f0-a7a3-687c2b709f66
6. Уэллс, Дж. Б. (1994). «Типичность и проверка типов в лямбда-исчислении второго порядка эквивалентны и неразрешимы». Труды 9-го ежегодного симпозиума IEEE по логике в компьютерных науках (LICS) . стр. 176–185. doi :10.1109/LICS.1994.316068. ISBN 0-8186-6310-3. S2CID  15078292.
7. Клемент (1986). Простой аппликативный язык: Mini-ML (PDF) . LFP'86. ACM. doi :10.1145/319838.319847. ISBN 978-0-89791-200-6.
8. Vaughan, Jeff (23 июля 2008 г.) [5 мая 2005 г.]. "Доказательство корректности алгоритма вывода типа Хиндли–Милнера" ​​(PDF) . Архивировано из оригинала (PDF) 2012-03-24. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
9. Yorgey; Brent; Weirich; Stephanie; Cretin; Julien; Peyton Jones; Simin; Vytiniotis; Dmitryos; Magalhaes; José Pedro (январь 2012 г.). «Giving Haskell a promotion». Труды 8-го семинара ACM SIGPLAN по типам в проектировании и реализации языков . стр. 53–66. doi :10.1145/2103786.2103795. ISBN 978-1-4503-1120-5.
10. Потье, Франсуа (1998). Вывод типа при наличии подтипирования: от теории к практике (диссертация) . Получено 10 августа 2021 г.
11. Долан, Стивен; Майкрофт, Алан (2017). «Полиморфизм, подтипирование и вывод типов в MLsub» (PDF) . POPL 2017: Труды 44-го симпозиума ACM SIGPLAN по принципам языков программирования . doi : 10.1145/3009837.3009882.
12. Парро, Лионель (2020). «Простая сущность алгебраического подтипирования: вывод главного типа с упрощением подтипирования». 25-я Международная конференция ACM SIGPLAN по функциональному программированию — ICFP 2020, [Онлайн-мероприятие], 24–26 августа 2020 г. doi : 10.1145 /3409006 .
13. Карделли, Лука; Мартини, Симоне; Митчелл, Джон К.; Скедров, Андре (1994). «Расширение системы F с подтипированием». Информация и вычисления, т. 9. Северная Голландия, Амстердам. стр. 4–56. doi : 10.1006/inco.1994.1013 .
14. Даан Лейен, Расширяемые записи с метками области действия , Институт информационных и вычислительных наук, Утрехтский университет, Проект, Редакция: 76, 23 июля 2005 г.

• Mairson, Harry G. (1990). "Определение типизации ML является полным для детерминированного экспоненциального времени". Труды 17-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования - POPL '90 . ACM. стр. 382–401. doi :10.1145/96709.96748. ISBN 978-0-89791-343-0. S2CID  75336.
• Kfoury, AJ; Tiuryn, J.; Urzyczyn, P. (1990). "ML-типируемость является dexptime-полной". Caap '90 . Lecture Notes in Computer Science. Vol. 431. pp. 206–220. doi :10.1007/3-540-52590-4_50. ISBN 978-3-540-52590-5.

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

• Грамотная реализация алгоритма W на языке Haskell вместе с его исходным кодом на GitHub.
• Простая реализация алгоритма Хиндли-Милнера на Python.