Вывод типа с типами продукта

15

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

Термин - это литерал, композиция терминов, цитата из термина или примитив.

e::=x|ee|[e]|

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

Термины, отличные от состава, имеют основные правила типа:

x:ι[Lit]Γe:σΓ[e]:α.ασ×α[Quot],α not free in Γ

Заметно отсутствуют правила для применения, поскольку в конкатенативных языках их нет.

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

τ::=ι|α|ρρρ::=()|τ×ρσ::=τ|α.σ

Это первое, что кажется подозрительным, но я не знаю точно, что с ним не так.

Чтобы улучшить читаемость и сократить скобки, я предполагаю, что в схемах типов. Я также буду использовать заглавную букву для переменной, обозначающей стек, а не одно значение.ab=b×(a)

Есть шесть примитивов. Первые пять довольно безобидны. dupпринимает верхнее значение и производит две его копии. swapизменяет порядок двух верхних значений. popотбрасывает верхнее значение. quoteпринимает значение и создает цитату (функцию), которая его возвращает. applyприменяет цитату к стеку.

dup::Ab.AbAbbswap::Abc.AbcAcbpop::Ab.AbAquote::Ab.AbA(C.CCb)apply::AB.A(AB)B

Последний комбинатор composeдолжен взять две кавычки и вернуть тип их конкатенации, то есть . В статически типизированном конкатенативном языке Cat этот тип очень прост.[e1][e2]compose=[e1e2]compose

compose::ABCD.A(BC)(CD)A(BD)

Однако этот тип слишком ограничен: он требует, чтобы производство первой функции точно совпадало с потреблением второй. В действительности вы должны принимать разные типы, а затем объединять их. Но как бы вы написали этот тип?

compose::ABCDE.A(BC)(DE)A

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

compose::ABCDE.A(BC)(DE)A((DC)B((CD)E))

Это по - прежнему относительно просто: composeпринимает функцию и один . Его результат потребляет поверх потребления не произведенного , и производит поверх производства не потребленного . Это дает правило для обычного состава.f1:BCf2:DEBf2f1Df1f2

Γe1:AB.ABΓe2:CD.CDΓe1e2:((CB)A((BC)D))[Comp]

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

A.()A=()A.A()=AABCD.ABCD=BD iff A=Cotherwise=undefined

Есть ли что-то ужасно сломанное в этом, чего я не вижу, или я нахожусь на чем-то вроде правильного пути? (Я, вероятно, ошибочно определил некоторые из этих вещей, и был бы признателен за исправления в этой области).

Джон Перди
источник
Как вы используете переменные в вашей грамматике? Этот вопрос должен помочь вам разобраться с «подтипом», который вам нужен.
Джмад
1
@jmad: Я не уверен, что понимаю вопрос. Переменные типа существуют только для формального определения схем типов, а сам язык вообще не имеет переменных, только определения, которые могут быть [взаимно] рекурсивными.
Джон Перди
Справедливо. Можете ли вы сказать, почему (возможно, с примером) правило для composeслишком ограничено? У меня сложилось впечатление, что это хорошо, как это. (например, ограничение может быть обработано объединением, как для применения, как в λ-исчислении)C=D
jmad
@jmad: конечно. Рассмотрим twiceопределение как dup compose apply, которое берет цитату и применяет ее дважды. [1 +] twiceвсе в порядке: вы составляете две функции типа . Но это не так: если , проблема в том, что , поэтому выражение запрещено, хотя оно должно быть допустимым и иметь типа . Конечно, решение состоит в том, чтобы поместить классификатор в нужное место, но я в основном задаюсь вопросом, как на самом деле написать тип без некоторого циклического определения. A b .ιι[pop] twiceA AAb.f1,f2:AbAA b .AAbAb.AbbAcompose
Джон Пурди

Ответы:

9

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

compose:ABCδ.δ (α.α AαB) (β.β BβC)δ (γ.γ AγC)

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

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

Я считаю, что проверка типов типа ранга 2 в общем неразрешима, хотя была проделана некоторая работа, которая дает хорошие результаты на практике (для Haskell):

  • Саймон Л. Пейтон Джонс, Димитриос Витиниотис, Стефани Вейрих, Марк Шилдс: Практический вывод типов для типов произвольного ранга. J. Funct. Программа. 17 (1): 1-82 (2007)

Правило типа для композиции просто:

Γe1:α.α Aα BΓe1:α.α Bα CΓe1 e2:α.α Aα C

Чтобы система типов работала в целом, вам нужно следующее правило специализации:

Γe:α.α Aα BΓe:α.C Aα C B
Дэйв Кларк
источник
Спасибо, это было очень полезно. Этот тип подходит для функций с одним аргументом, но он не поддерживает несколько аргументов. Например, dup +должен иметь тип потому что имеет тип . Но вывод типа при отсутствии аннотаций является абсолютным требованием, поэтому ясно, что мне нужно вернуться к чертежной доске. У меня есть идея для другого подхода, и я буду писать об этом, если это сработает. ιι+ιιι
Джон Перди
1
Типы стека количественно определяют фрагменты стека, поэтому проблем с двумя аргументами не возникает. Я не уверен, как это относится dup +, так как это не использует compose, как вы определили это выше.
Дэйв Кларк
Э, верно, я имел в виду [dup] [+] compose. Но я читаю как ; сказать ; тогда у вас есть а не . Вложение не является правильным, если вы не переверните стек так, чтобы верх был последним (самым глубоким вложенным) элементом. B × α B = ι × ι ( ι × ι ) × α ι × ( ι × α )αBB×αB=ι×ι(ι×ι)×αι×(ι×α)
Джон Перди
Возможно, я строю свой стек в неправильном направлении. Я не думаю, что вложенность имеет значение, пока пары, составляющие стек, не появляются в языке программирования. (Я планирую обновить свой ответ, но сначала нужно провести небольшое исследование.)
Дэйв Кларк
Да, вложение - это в значительной степени деталь реализации.
Джон Перди