Monday, August 20, 2007

Типы: Top и Bottom

Для полноты картины нужно упомянуть еще два специальных крайних случая — типы Top и Bottom.

Тип Top (записывается как ) — это специальный тип, являющийся супертипом для всех остальных. Если быть ближе к математике — для любого t: t <: T.


В Java и C#, например, ему соответствует тип Object (правда, он не является супертипом для простых unboxed типов вроде int). Вообще в большинстве ОО языков (кроме C++) такой тип присутствует.

Другой полезный элемент системы типов — это тип Bottom , который является подтипом для любого типа. Как правило, нет ни одного значения этого типа — в противном случае, это значение допустимо было бы использовать и в контексте когда нужен тип функции (a → b), и, скажем, когда требуется тип сложной структуры данных.

Несмотря на это, тип bottom весьма полезен в некоторых случаях — он может обозначать тип функции, которая никогда не возвращает значений, например, входит в бесконечный цикл или кидать exception:

function div(a : float, b : float) : float = 
    if (a != 0)
      a / b
    else
      error 

Выражение error имеет тип bottom, технически оно выкидывает эксепшен. Благодаря этому выражение if в целом отлично проходит проверку типов1 (имеет тип float).
Однако, введение в систему типов такого специального случая ее неслабо усложняет — кроме Haskell Scala такого типа нет, вроде бы, нигде из более-менее мейнстримных языков.

1 Тут имеется ввиду выражение if, а не statement (как в C++/C#/Java). В C++/C#/Java этому соответствует тернарный оператор ?:

14 comments:

migmit said...

В Haskell его тоже нет. Есть abstract data types, но они не подтипы таких типов как Int, Float etc.

lrrr said...

Которого? Top или Bottom ?

Bottom есть, называется undefined:
Prelude> :t 1 + undefined
1+ undefined :: (Num t) => t
Prelude> 1+ undefined
*** Exception: Prelude.undefined

Vladimir Frolov said...

Небольшие поправки:

1. В С++ тоже есть тип Top. Это void*. В С++ к void* может быть приведён указатель на любой тип, как инегральный, так и определённый пользователем.

2. В большинстве ООП языков нет самого типа Bottom, зато есть экземпляр этого типа - это null. В вашем примере функция может возвращать null и это не будет иметь отношения к эксепшинам.

migmit said...

undefined - не тип, а значение. Полиморфное значение, относящееся к любому типу. Отдельного ТИПА undefined нет.

Stepan said...

В Scala есть Nothing.

lrrr said...

Vladimir Frolov> Насчет (1), не совсем получается, т.к. (void *) он супертип только для указателей. Впрочем, в java, кажется, тоже нельзя int привести к java.lang.object, в отличие от C# (поправьте меня кто-нибудь).

Насчет (2) это не совсем то, обычно ссылки рассматриваются как вариантный тип с двумя конструкторами Ref a = Ptr a | Null. Я не знаю языков [со статической типизацией] где в данном случае функция может вернуть null.

lrrr said...

В смысле, где типы вроде int и float можно было бы неявно к null привести.

lrrr said...

migmit> Да, и правда. Хотя похож. Неспроста (undefined :: Int) компилятор нормально кушает..

В процессе гугления оказалось что вроде как в предшественнике haskell -- языке Miranda был bottom. Жалко документации по нему нормальной пока не нашлось.

Stepan>Спасибо, Scala мне всегда нравилась ;)

Vladimir Frolov said...

В случае 1 - да. Дизайн языка С++ такой, что void* как Top тип разумно иметь только для указателей.

MyClass obj;
T v = obj; - В С++ это уже совершенно другой тип преобразования. Этот тип преобразования не полиморфный. Поэтому и запрещён в случае если T = void.

В случае 2 - в разных языках придумывают значения типа таких NaN (not a number, есть в JavaScript), Undefined, Infinite, NegativeInfinite. В этих случаях тот-же NaN или Infinite может вести себя как заменитель null для встроенных типов т.е. как объект типа Bottom. Правда я не знаю как это должно выглядеть в статически типизированных языках. В JavaScript типизация отсудствует.

migmit said...

Ну, в Хаскеле полиморфных значений до фига. Скажем,
Prelude> :t undefined
undefined :: a
Prelude> :t 1
1 :: (Num t) => t
Prelude> :t 1.5
1.5 :: (Fractional t) => t

lrrr said...

migmit> Кстати, насчет полиморфных типов -- вот в книжке Пирса "Types and Programming Languages" предлагается полиморфный тип (forall a.a) как замена bottom, который тоже не содержит ни одного значения (в хаскеле -- одно undefined).

lrrr said...

Vladimir Frolov> Да, проще говоря -- в C++ "по техническим причинам" нету Top-типа Object, т.к. в C++ объекты очень любят храниться на стеке а не в хипе (в отличие от C#).

Stepan said...

Ну и ещё в полуофициальной спецификации closures для Java тоже есть подтип всех типов — null.

http://www.javac.info/closures-v05.html

Не помню, что в двух других спецификациях.

Gleb said...

В Окамле тип [>] является подтипом всех остальных полиморфных вариантов - т.е. это своеобразный bottom.