Существует ли иерархия выразительности для систем типов?

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

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

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

Я понимаю, что понятие «выразительность» может быть немного расплывчатым, что может объяснить, почему системы типов кажутся мне контрольными списками.

pl.programming-languages type-theory Алекс тен Бринк
источник

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

Дэйв Кларк

Я действительно должен написать свое сообщение в блоге "Как сравнивать языки программирования" ...

Андрей Бауэр,

@ Андрей Бауэр: Это было бы интересным дополнением к ответам и замечаниям, уже представленным здесь. Я уже довольно много узнал о том, как можно определить «выразительность» - возможно, мне следовало бы спросить об этом вместо этого ...

Алекс тен Бринк

Я уверен, что видел полиморфизм ранга 2, используемый в нескольких местах. Один из тех, что я помню сейчас, - это Ламмель, Пейтон-Джонс, Scrap Your Boilerplate, 2003.

Раду ГРИГОР,

@Radu GRIGore: полиморфизм ранга 2 важен, потому что он позволяет аргументам типа появляться в дважды противоположном положении, что при обычном виде двойственности позволяет моделировать экзистенциальные типы по их кодированию по Церковью. Ранг 3 просто снова дает универсальное количественное определение, и оно чередуется оттуда, так что по сравнению с ним добавляется мало выразительной силы.

CA McCann

Ответы:

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

Какие математические функции вы можете выразить в конкретной системе типов. Например, в простом типе лямбда-исчисления не все вычисляемые функции могут быть выражены. То же самое верно для Системы , но может быть выражено строго больше функций. Это не очень интересно, когда вы переходите к системам типов для языков, полных по Тьюрингу. $F$
Может ли система проверять каждую программу, написанную в системе ? Это в основном то, что первое понятие силы Коди о PTSs. Опять же , система сильнее STLC в таком порядке, так как каждый типов STLC программы в System . Аналогично, система с подтипом будет сильнее, чем система без. $A$ $B$ $F$ $F$
Существуют ли локальные преобразования (в смысле статьи Феллайзена « О выразительной силе языков программирования» ), которые позволяют программе, которая печатает в системе печатать в системе , но не наоборот. $A$ $B$
Гарантирует ли одна система типов более сильные свойства, чем другая. Например, системы линейного типа просто отклоняют больше программ, но это позволяет им делать более сильные заявления о программах, которые они принимают.

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

Сэм Тобин-Хохштадт
источник

Я предполагаю, что под «бумагой выразительности Феллайзена» вы имеете в виду его « О выразительной силе языков программирования» .

Мартин Бергер

Да, точно. Я уточнил этот ответ.

Сэм Тобин-Хохштадт

Я не уверен, что у меня есть удовлетворительный ответ на ваш вопрос, но если вы рассмотрите Системы Чистого Типа, которые являются обобщением систем, найденных в лямбда-кубе (подробный, если несколько устаревший обзор можно найти в классическом тексте Барендрегта ) то есть пара естественных понятий иерархии:

$\Gamma\vdash_A\ t\colon T$ $\Gamma\vdash_B\ t\colon T$ $\Gamma, t$ $T$ $*\colon *$ $(*,*,*)$ PTS в том смысле, что от любого другого PTS есть морфизм. Это можно рассматривать как меру выразительности системы типов, где окончательная PTS является наиболее выразительной системой.
$A$ $B$ $A$ $F_\omega$ $ECC$ $\leftrightarrow$

Коди
источник