Я работаю над компилятором для конкатенативного языка и хотел бы добавить поддержку вывода типов. Я понимаю Хиндли-Милнера, но я изучаю теорию типов по ходу дела, поэтому не знаю, как ее адаптировать. Является ли следующая система надежной и достоверной?
Термин - это литерал, композиция терминов, цитата из термина или примитив.
Все термины обозначают функции. Для двух функций и , , то есть, сопоставление обозначает обратную композицию. Литералы обозначают ниладические функции.
Термины, отличные от состава, имеют основные правила типа:
Заметно отсутствуют правила для применения, поскольку в конкатенативных языках их нет.
Тип - это литерал, переменная типа или функция из стеков в стеки, где стек определяется как кортеж с правым вложением. Все функции неявно полиморфны по отношению к «остальной части стека».
Это первое, что кажется подозрительным, но я не знаю точно, что с ним не так.
Чтобы улучшить читаемость и сократить скобки, я предполагаю, что в схемах типов. Я также буду использовать заглавную букву для переменной, обозначающей стек, а не одно значение.
Есть шесть примитивов. Первые пять довольно безобидны. dup
принимает верхнее значение и производит две его копии. swap
изменяет порядок двух верхних значений. pop
отбрасывает верхнее значение. quote
принимает значение и создает цитату (функцию), которая его возвращает. apply
применяет цитату к стеку.
Последний комбинатор compose
должен взять две кавычки и вернуть тип их конкатенации, то есть . В статически типизированном конкатенативном языке Cat этот тип очень прост.compose
Однако этот тип слишком ограничен: он требует, чтобы производство первой функции точно совпадало с потреблением второй. В действительности вы должны принимать разные типы, а затем объединять их. Но как бы вы написали этот тип?
Если вы позволите обозначать разницу двух типов, то я думаю, что вы можете написать тип правильно.compose
Это по - прежнему относительно просто: compose
принимает функцию и один . Его результат потребляет поверх потребления не произведенного , и производит поверх производства не потребленного . Это дает правило для обычного состава.
Тем не менее, я не знаю, что этот гипотетический самом деле соответствует чему-либо, и я достаточно долго гонялся за ним по кругу, так что, думаю, я ошибся. Может ли это быть простой разницей в кортежах?
Есть ли что-то ужасно сломанное в этом, чего я не вижу, или я нахожусь на чем-то вроде правильного пути? (Я, вероятно, ошибочно определил некоторые из этих вещей, и был бы признателен за исправления в этой области).
compose
слишком ограничено? У меня сложилось впечатление, что это хорошо, как это. (например, ограничение может быть обработано объединением, как для применения, как в λ-исчислении)twice
определение какdup compose apply
, которое берет цитату и применяет ее дважды.[1 +] twice
все в порядке: вы составляете две функции типа . Но это не так: если , проблема в том, что , поэтому выражение запрещено, хотя оно должно быть допустимым и иметь типа . Конечно, решение состоит в том, чтобы поместить классификатор в нужное место, но я в основном задаюсь вопросом, как на самом деле написать тип без некоторого циклического определения. ∀ A b .[pop] twice
A ≠ Acompose
Ответы:
Следующий тип ранга-2 представляется достаточно общим. Это намного более полиморфно, чем тип, предложенный в вопросе. Здесь переменная квантифицируется по непрерывным фрагментам стека, который захватывает функции с несколькими аргументами.
Греческие буквы используются для переменных остальной части стека только для ясности.
Он выражает ограничения, что выходной стек первого элемента в стеке должен быть таким же, как входной стек второго элемента. Соответствующее создание экземпляра переменной для двух фактически аргументов - это способ заставить ограничения работать должным образом, а не определять новую операцию, как вы предлагаете в этом вопросе.В
Я считаю, что проверка типов типа ранга 2 в общем неразрешима, хотя была проделана некоторая работа, которая дает хорошие результаты на практике (для Haskell):
Правило типа для композиции просто:
Чтобы система типов работала в целом, вам нужно следующее правило специализации:
источник
dup +
должен иметь тип потому что имеет тип . Но вывод типа при отсутствии аннотаций является абсолютным требованием, поэтому ясно, что мне нужно вернуться к чертежной доске. У меня есть идея для другого подхода, и я буду писать об этом, если это сработает.+
dup +
, так как это не использует compose, как вы определили это выше.[dup] [+] compose
. Но я читаю как ; сказать ; тогда у вас есть а не . Вложение не является правильным, если вы не переверните стек так, чтобы верх был последним (самым глубоким вложенным) элементом. B × α B = ι × ι ( ι × ι ) × α ι × ( ι × α )