Каковы практические проблемы с типами пересечения и объединения?

22

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

Похоже, что система типов, которую я реализовал до сих пор, могла (с небольшой дополнительной работой) включать типы пересечений и объединений, например, вы могли бы иметь:

  • <Union String Integer>
  • <Union Integer Foo>
  • Пересечение двух типов выше было бы простым Integer
  • Союз двух типов будет <Union String Integer Foo>

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

Каковы плюсы / минусы включения таких функций в систему типов?

mikera
источник

Ответы:

26

Вот несколько вещей, которые нужно иметь в виду:

  • Хотя мы обычно думаем, что знаем, что мы подразумеваем под теоретико-множественным пересечением и объединением, было несколько разных взглядов на то, что именно являются типами пересечения и объединения . Так что стоит закрепить это, прежде чем приступить к реализации.
  • S A S ASA"как" уточняет ") тогда как правила формирования для обычных произведений и сумм следующие: SA SA
    SATASTASATASTA
    SATBSTABSATBS+TA+B
  • Поскольку пересечения и объединения могут использоваться для более точных утверждений о поведении программы во время выполнения, естественно, что типизация становится чувствительной к порядку оценки. Например, в статьях (2) и (4) ниже объясняется, почему «очевидные» (и довольно стандартные) правила типизации и подтипов для пересечений и объединений на самом деле несостоятельны для ML-подобных языков (из-за наличия побочных эффектов и окончание). Вы были предупреждены!
  • По тем же причинам глобальный вывод типов обычно становится непрактичным или неразрешимым. Действительно, вся концепция «основного типа», возможно, представляет собой «красную сельдь», поскольку функция может удовлетворять многим различным свойствам, которые не имеют отношения к ее предполагаемому использованию (например, « foo переводит простые целые числа в целые числа больше 7»). Вместо этого практические подходы к пересечениям и объединениям (см. (3) , (4) ), как правило, основаны на комбинации вывода и проверки.

Я полагаю, что некоторые из вышеперечисленных пунктов могут звучать негативно, хотя я бы не назвал их «минусами», а просто «реальностью» пересечения и объединения типов. С другой стороны, с точки зрения языкового проектирования, одна из причин, по которой усилия по поддержке пересечений и объединений (и для их правильного определения!) Заключается в том, что они позволяют более точным свойствам программ выражаться довольно постепенно, что требует гораздо менее радикальное преобразование, чем, скажем, теория зависимого типа.

Краткий список чтения:

  1. Дизайн языка программирования Форсайт от Джона С. Рейнольдса
  2. Типы пересечений и вычислительные эффекты Роуэн Дэвис и Фрэнк Пфеннинг
  3. Практическая проверка типа уточнения Роуэн Дэвис (диссертация)
  4. Трехсторонняя проверка типов Джошуа Данфилдом и Фрэнком Пфеннингом
Ноам Цайлбергер
источник
Отличный ответ, большое спасибо. Ссылки были особенно полезны и поучительны - так что спасибо, что указали мне правильные направления!
Микера