Есть ли причина иметь нижний тип в языке программирования?

49

Тип дна - это конструкция, которая в основном появляется в математической теории типов. Он также называется пустым типом. Это тип, который не имеет значений, но является подтипом всех типов.

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

Какой смысл иметь этот странный тип в языке программирования? Это не так часто, но он присутствует в некоторых, таких как Scala и Lisp.

GregRos
источник
2
@SargeBorsch: ты уверен в этом? Конечно, никто не может в C явно определить voidданные ...
Василий Старынкевич,
3
@BasileStarynkevitch нет значений типа void, и тип блока должен иметь одно значение. Кроме того, как вы указали, вы даже не можете объявить значение типа void, это означает, что это даже не тип, а специальный угловой регистр в языке.
Сардж Борщ
2
Да, C в этом причудлив, особенно в том, как пишутся указатели и типы указателей на функции. Но voidв Java почти то же самое: не совсем тип и не может иметь значений.
Сардж Борщ
3
В семантике языков с нижним типом нижний тип считается не имеющим значений, а скорее имеет одно значение, нижнее значение, представляющее вычисление, которое никогда не завершается (обычно). Поскольку нижнее значение является значением каждого типа, нижний тип может быть подтипом каждого типа.
Теодор Норвелл
4
@BasileStarynkevitch Common Lisp имеет тип nil, который не имеет значений. Он также имеет нулевой тип, который имеет только одно значение, символ nil(aka, ()), который является типом единицы.
Джошуа Тейлор

Ответы:

33

Я приведу простой пример: C ++ против Rust.

Вот функция, используемая для создания исключения в C ++ 11:

[[noreturn]] void ThrowException(char const* message,
                                 char const* file,
                                 int line,
                                 char const* function);

А вот эквивалент в Rust:

fn formatted_panic(message: &str, file: &str, line: isize, function: &str) -> !;

С чисто синтаксической точки зрения конструкция Rust более разумна. Обратите внимание, что конструкция C ++ определяет тип возвращаемого значения, хотя он также указывает, что не собирается возвращать. Это немного странно.

В стандартном примечании синтаксис C ++ появился только в C ++ 11 (он был добавлен сверху), но различные компиляторы некоторое время предоставляли различные расширения, так что сторонние инструменты анализа должны были быть запрограммированы для распознавания различных способов. этот атрибут может быть написан. Стандартизация этого явно явно лучше.


Теперь о пользе?

Тот факт, что функция не возвращает, может быть полезен для:

  • оптимизация: после него можно удалить любой код (он не вернется), нет необходимости сохранять регистры (так как их не нужно восстанавливать), ...
  • статический анализ: он устраняет ряд потенциальных путей исполнения
  • ремонтопригодность: (см. статический анализ, но людьми)
Матье М.
источник
6
voidв вашем примере C ++ определяет (часть) тип функции, а не тип возвращаемого значения. Это ограничивает значение, которому разрешена функция return; все, что может преобразовать в пустоту (что ничто). Если функция returns, за ней не должно следовать значение. Полный тип функции void () (char const*, char const*, int, char const *). +1 за использование char constвместо const char:-)
Clearer
4
Это не означает, что имеет смысл иметь нижний тип, просто имеет смысл комментировать функции, независимо от того, возвращаются они или нет как часть языка. На самом деле, поскольку функции могут не возвращаться по разным причинам, представляется целесообразным каким-то образом кодировать причину, а не использовать универсальный термин, что-то вроде сравнительно недавней концепции аннотирования функций на основе их побочных эффектов.
GregRos
2
На самом деле, есть причина сделать «не возвращать» и «иметь тип возврата X» независимым: обратная совместимость для вашего собственного кода, так как соглашение о вызовах может зависеть от типа возврата.
дедупликатор
это [[noreturn]] синтаксис или дополнение функциональности?
Зайбис
1
[продолжение] В целом, я бы просто сказал, что обсуждение преимуществ ⊥ должно определить, что можно квалифицировать как реализацию ⊥; и я не думаю, что система типов, у которой нет ( a → ⊥) ≤ ( ab ), является полезной реализацией ⊥. Так что в этом смысле SysV x86-64 C ABI (среди прочих) просто не позволяет реализовать ⊥.
Алексей Шпилкин
26

Карл ответил хорошо. Вот еще одно использование, которое, я думаю, никто не упомянул. Тип

if E then A else B

должен быть тип, который включает в себя все значения в типе Aи все значения в типе B. Если тип Bis Nothing, то тип ifвыражения может быть типом A. Я часто объявляю рутину

def unreachable( s:String ) : Nothing = throw new AssertionError("Unreachable "+s) 

сказать, что код не ожидается, будет достигнут. Так как его тип Nothing, unreachable(s)теперь может использоваться в любом ifили (чаще), switchне влияя на тип результата. Например

 val colour : Colour := switch state of
         BLACK_TO_MOVE: BLACK
         WHITE_TO_MOVE: WHITE
         default: unreachable("Bad state")

У Scala такой тип Ничего.

Другой вариант использования для Nothing(как упоминалось в ответе Карла) - List [Nothing] - это тип списков, каждый из членов которых имеет тип Nothing. Таким образом, это может быть тип пустого списка.

Ключевое свойство Nothingэтого делает эти варианты использования работающими не в том, что у него нет значений - хотя в Scala, например, у него нет значений - это в том, что он является подтипом любого другого типа.

Предположим, у вас есть язык, в котором каждый тип содержит одно и то же значение - давайте назовем его (). В таком языке тип модуля, который имеет ()единственное значение, может быть подтипом каждого типа. Это не делает его типом дна в том смысле, что имел в виду ОП; ОП было ясно, что тип дна не содержит значений. Однако, поскольку это тип, который является подтипом каждого типа, он может играть почти ту же роль, что и нижний тип.

Haskell делает вещи немного по-другому. В Haskell выражение, которое никогда не генерирует значение, может иметь схему типа forall a.a. Экземпляр схемы этого типа объединится с любым другим типом, поэтому он эффективно действует как нижний тип, даже если (стандартный) Haskell не имеет понятия о подтипировании. Например, errorфункция из стандартной прелюдии имеет схему типа forall a. [Char] -> a. Так что вы можете написать

if E then A else error ""

и тип выражения будет таким же, как тип A, для любого выражения A.

Пустой список в Haskell имеет схему типов forall a. [a]. Если Aэто выражение, тип которого является типом списка, то

if E then A else []

является выражением того же типа, что и A.

Теодор Норвелл
источник
В чем разница между типом forall a . [a]и типом [a]в Haskell? Разве переменные типа уже не определены количественно в выражениях типа Хаскеля?
Джорджио
@Giorgio В Haskell универсальная квантификация неявна, если ясно, что вы смотрите на схему типов. Вы даже не можете писать forallна стандартном Haskell 2010. Я написал квантификацию явно, потому что это не форум на Haskell, и некоторые люди могут быть не знакомы с соглашениями Haskell. Так что нет никакой разницы, кроме того, что forall a . [a]не является стандартным, тогда как [a]есть.
Теодор Норвелл
19

Типы образуют моноид двумя способами, вместе образуя полукольцо . Это то, что называется алгебраическими типами данных . Для конечных типов это полукольцо имеет прямое отношение к полукольцу натуральных чисел (включая ноль), что означает, что вы подсчитываете, сколько возможных значений имеет тип (исключая «неопределенные значения»).

  • Тип дна (я его назову Vacuous) имеет нулевые значения .
  • Тип единицы имеет одно значение. Я назову как тип, так и его единственное значение ().
  • Композиция (которую большинство языков программирования поддерживают довольно напрямую через записи / структуры / классы с открытыми полями) является операцией продукта . Так , например, (Bool, Bool)имеет четыре возможных значения, а именно (False,False), (False,True), (True,False)и (True,True).
    Тип блока - это элемент идентификации операции композиции. Например, ((), False)и ((), True)являются единственными значениями типа ((), Bool), поэтому этот тип изоморфен самому Boolсебе.
  • Альтернативные типы несколько игнорируются в большинстве языков (языки OO поддерживают их наследованием), но они не менее полезны. Альтернатива между двумя типами Aи в Bосновном имеет все значения Aплюс все значения B, следовательно, тип суммы . Например, Either () Boolимеет три значения, я назову их Left (), Right Falseи Right True.
    Нижний тип является единичным элементом суммы: Either Vacuous Aимеет только значения формы Right a, потому Left ...что не имеет смысла ( Vacuousне имеет значений).

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

Теперь, на самом деле, вы можете продвинуться далеко вперед, обеспокоившись только одной стороной проблемы (составной моноид), тогда вам явно не нужен тип bottom. Например, даже у Haskell долгое время не было стандартного типа дна. Теперь это называется Void.

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

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


mb21 напоминает мне, что это не следует путать с нижними значениями . В ленивых языках, таких как Haskell, каждый тип содержит нижнее «значение», обозначаемое . Это не конкретная вещь, которую вы могли бы явно передать, а то, что «возвращается», например, когда функция зацикливается вечно. Даже Voidтип Haskell «содержит» нижнее значение, то есть имя. В этом свете тип дна Хаскелла действительно имеет одно значение, а тип его единицы имеет два значения, но в обсуждении теории категорий это обычно игнорируется.

leftaroundabout
источник
«Нижний тип (я его назову Void)», который не следует путать со значением bottom , которое является членом любого типа в Haskell .
mb21
18

Может быть, это зацикливается навсегда, или, может быть, это исключение.

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

Кроме того, даже если Nothing(имя Scala для нижнего типа) не может иметь значений, List[Nothing]это ограничение не имеет, что делает его полезным в качестве типа пустого списка. Большинство языков обходят это, создавая пустой список строк другого типа, чем пустой список целых чисел, что имеет смысл, но делает пустой список более многословным для записи, что является большим недостатком в ориентированном на список языке.

Карл Билефельдт
источник
12
«Пустой список на Haskell - это конструктор типов»: несомненно, здесь важнее то, что он полиморфный или перегруженный, то есть пустые списки разных типов являются разными значениями, но []представляют их все и будут созданы для конкретный тип по мере необходимости.
Питер ЛеФану Лумсдайн
Интересно: Если вы пытаетесь создать пустой массив в интерпретаторе Haskell, вы получите очень определенное значение с очень неопределенным типом: [a]. Точно так же :t Left 1дает Num a => Either a b. На самом деле оценки выражения силы типа a, но не из b:Either Integer b
Джон Дворжак
5
Пустой список является конструктором значений . Немного смущает, что используемый конструктор типов имеет то же имя, но сам пустой список является значением, а не типом (ну, есть и списки уровня типа, но это совсем другая тема). Часть, которая заставляет пустой список работать для любого типа списка, подразумевается forallв его типе forall a. [a]. Есть несколько хороших способов подумать forall, но для того, чтобы понять это, нужно время.
Дэвид
@PeterLeFanuLumsdaine Это именно то, что значит быть конструктором типов. Это просто означает, что это тип с отличным от *.
GregRos
2
В Haskell []это конструктор типов и []это выражение, представляющее пустой список. Но это не значит, что «пустой список Хаскелла является конструктором типов». Контекст проясняет, []используется ли он как тип или как выражение. Предположим, вы заявляете data Foo x = Foo | Bar x (Foo x); теперь вы можете использовать его Fooкак конструктор типа или как значение, но это просто случайность, когда вы выбрали одно и то же имя для обоих.
Теодор Норвелл
3

Для статического анализа полезно документировать тот факт, что определенный путь к коду недоступен. Например, если вы пишете следующее в C #:

int F(int arg) {
 if (arg != 0)
  return arg + 1; //some computation
 else
  Assert(false); //this throws but the compiler does not know that
}
void Assert(bool cond) { if (!cond) throw ...; }

Компилятор будет жаловаться, что Fничего не возвращает хотя бы по одному пути кода. Если Assertбы он был помечен как не возвращаемый, компилятору не нужно было бы предупреждать.

USR
источник
2

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

Он также может использоваться как универсальная функция в типах функций ( any -> bot) для обработки ошибок при отправке.

И некоторые языки позволяют вам на самом деле устранить botошибку, которая может использоваться для предоставления пользовательских ошибок компилятора.

Telastyn
источник
11
Нет, тип дна не тип устройства. Нижний тип вообще не имеет значения, поэтому функция, возвращающая нижний тип, не должна возвращаться (т.е. генерировать исключение или цикл бесконечно)
Basile Starynkevitch
@BasileStarynkevitch - я не говорю о типе устройства. Тип модуля отображается на voidобщих языках (хотя и с немного другой семантикой для одного и того же использования), но не null. Хотя вы также правы в том, что большинство языков не моделируют нуль как нижний тип.
Теластин
3
@TheodoreNorvell - ранние версии Tangent делали это - хотя я и являюсь его автором, так что, возможно, это обман. У меня нет ссылок, сохраненных для других, и прошло много времени с тех пор, как я провел это исследование.
Теластин
1
@Martijn. Но вы можете использовать null, например, указатель сравнения для nullполучения логического результата. Я думаю, что ответы показывают, что есть два различных вида нижних типов. (a) Языки (например, Scala), где тип, который является подтипом каждого типа, представляет вычисления, которые не дают никаких результатов. По сути, это пустой тип, хотя технически часто заполняется бесполезным нижним значением, представляющим нетерминацию. (b) Языки, такие как Tangent, в которых нижний тип является подмножеством любого другого типа, поскольку он содержит полезное значение, которое также встречается в любом другом типе, - ноль.
Теодор Норвелл
4
Интересно, что некоторые языки имеют значение с типом, который вы не можете объявить (общий для литерала null), а другие имеют тип, который вы можете объявить, но не имеют значений (традиционный нижний тип), и что они выполняют несколько сопоставимые роли ,
Мартейн
1

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

Рассмотрим статически типизированный язык, в котором условные выражения являются выражениями (поэтому конструкция if-then-else удваивается как троичный оператор C и друзей, и может существовать аналогичный многопоточный оператор case). Функциональный язык программирования имеет это, но это происходит и в определенных императивных языках (начиная с 60-го АЛГОЛА). Тогда все выражения ветвления должны в конечном итоге создать тип всего условного выражения. Можно просто потребовать, чтобы их типы были равны (и я думаю, что это имеет место для троичного оператора в C), но это чрезмерно ограничительно, особенно когда условное выражение также может использоваться как условное выражение (не возвращая никакого полезного значения). В общем, каждый хочет, чтобы каждое выражение ветви было (неявно) конвертируемым к общему типу, который будет типом полного выражения (возможно, с более или менее сложными ограничениями, позволяющими компилятору эффективно находить этот общий тип, см. C ++, но я не буду вдаваться в эти подробности здесь).

Существует два типа ситуаций, когда общий вид преобразования обеспечивает необходимую гибкость таких условных выражений. Один уже упоминался, где тип результата - тип единицыvoid; это, естественно, супертип всех других типов, и разрешение любого (тривиально) преобразования в него позволяет использовать условное выражение в качестве условного выражения. Другое связано со случаями, когда выражение возвращает полезное значение, но одна или несколько ветвей не могут его создать. Они обычно вызывают исключение или включают в себя переход, и требовать, чтобы они (также) производили значение типа целого выражения (из недостижимой точки), было бы бессмысленным. Именно такую ​​ситуацию можно изящно обработать, предоставив предложения, переходы и вызовы, вызывающие исключения, которые будут иметь такой эффект, нижний тип, тип, который можно (тривиально) преобразовать в любой другой тип.

Я бы предложил написать такой нижний тип, *чтобы предложить его конвертируемость в произвольный тип. Он может служить другим полезным целям внутри компании, например, при попытке вывести тип результата для рекурсивной функции, которая не объявляет ничего, модуль вывода типов может назначить тип *любому рекурсивному вызову, чтобы избежать ситуации "курица и яйцо"; фактический тип будет определяться нерекурсивными ветвями, а рекурсивные будут преобразованы в общий тип нерекурсивных. Если нет нерекурсивных ветвей вообще, тип останется *и правильно укажет, что у функции нет никакого способа когда-либо вернуться из рекурсии. Помимо этого и в качестве типа результата функции вызова исключений, можно использовать*как тип компонента последовательностей длиной 0, например, пустого списка; Опять же, если когда-либо элемент будет выбран из выражения типа [*](обязательно пустой список), то результирующий тип *будет правильно указывать, что это никогда не вернется без ошибки.

Марк ван Леувен
источник
Так есть ли идея, которая var foo = someCondition() ? functionReturningBar() : functionThatAlwaysThrows()может вывести тип fooas Bar, поскольку выражение никогда не может дать ничего другого?
Суперкат
1
Вы только что описали тип устройства - по крайней мере, в первой части вашего ответа. Функция, которая возвращает тип модуля, совпадает с той, которая объявлена ​​как возвращающая voidв C. Вторая часть вашего ответа, где вы говорите о типе для функции, которая никогда не возвращается, или о списке без элементов - это действительно так. нижний тип! (Это часто пишется как, _|_а не как *. Не знаю почему. Возможно, потому что это похоже на (человеческое) дно :)
andrewf
2
Во избежание сомнений: «не возвращает ничего полезного» отличается от «не возвращает»; первый представлен типом Unit; второй по типу Bottom.
Андрей
@andrewf: Да, я понимаю разницу. Мой ответ немного длинноват, но я хотел бы подчеркнуть, что тип единицы измерения и тип дна играют (разные, но) сопоставимые роли, позволяя использовать определенные выражения более гибко (но все же безопасно).
Марк ван Леувен
@supercat: Да, это идея. В настоящее время в C ++ , который является незаконным, хотя это было бы справедливо , если functionThatAlwaysThrows()были заменены явным throw, из - за особого языка в стандарте. Наличие типа, который делает это, было бы улучшением.
Марк ван Леувен
0

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

Во многих языках функция может возвращать «void». Что именно это означает, зависит от языка. В C это означает, что функция ничего не возвращает. В Swift это означает, что функция возвращает объект только с одним возможным значением, и поскольку существует только одно возможное значение, это значение принимает нулевые биты и фактически не требует никакого кода. В любом случае, это не то же самое, что «дно».

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

Если разработчик языка чувствует, что это так, то нет никаких причин, чтобы не иметь такого типа. Реализация не сложна (вы можете реализовать ее точно так же, как функцию, возвращающую void и помеченную как «не возвращается»). Вы не можете смешивать указатели на функции, возвращающие bottom с указателями на функции, возвращающие void, потому что они не одного типа).

gnasher729
источник