При отсутствии изменяемых типов, есть ли случай для параметров инвариантного типа? - PullRequest
2 голосов
/ 26 марта 2020

Java Массивы не полностью безопасны по типу, поскольку они ковариантны: ArrayStoreException может встречаться в массиве с псевдонимами. Java Коллекции, с другой стороны, инвариантны по своему параметру типа: например, List<Thread> не является подтипом List<Runnable> (что может быть несколько нелогично). Мотивация, похоже, связана с тем, что List s и другие коллекции mutable , поэтому, чтобы сохранить систему типов в здравом уме, параметры их типов обязательно должны быть инвариантными.

Если только язык программирования поддерживаемые неизменяемые типы, может ли работать система типов, в которой параметры типа являются либо ковариантными, либо контравариантными (но никогда не инвариантными)? Другими словами, чтобы использовать Scala способ выражения дисперсии, нужно иметь List[+E], Function[-T, +R], Map[+K, +V], et c. Я знаю, что есть некоторые более старые языки (например, GNU Sather ), которые, похоже, избегают поддержки только ко-/ контравариантных типов параметров.

Мой общий вопрос: в мире Полностью неизменяемые типы данных, есть ли случай, когда требуется конкретный инвариантный тип параметра (в отличие от ко-или контравариантного)? Существуют ли примеры для неизменных структур данных, которые будут корректны только с параметром инвариантного типа?

1 Ответ

2 голосов
/ 03 апреля 2020

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

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

Поскольку вы уже определили различные случаи, когда параметр типа не может быть ковариантным, и различные случаи, когда параметр типа не может быть противоположным (например, Function [-T, + R] это хорошо, но обратное было бы совершенно несостоятельным), хороший подход - искать случаи, когда один и тот же параметр типа используется дважды , один раз таким образом, который не может быть ковариантным, и один раз таким образом, что не может быть противоречивым. Тривиальным примером будет UnaryOperator [T] <: Function [T, T], аналогично Java s java .util.function.UnaryOperator <T>, чей метод apply возвращает тот же тип, который принимает , UnaryOperator [String] нельзя использовать в качестве UnaryOperator [Object] (потому что вы не можете передать ему произвольный объект), но UnaryOperator [Object] также нельзя использовать в качестве UnaryOperator [String] (потому что даже если вы передадите ему String, он может вернуть какой-то другой объект.)

Для более реалистичного примера c. , , представьте двоичное дерево поиска TreeMap [K, + V] <: Map [K, V], аналогичное Java s java .util.TreeMap , Предположительно мы хотим поддерживать такие методы, как 'firstKey' и 'floorEntry' и 'iterator' и т. Д. (Или, по крайней мере, некоторые из них), поэтому мы не можем сделать K контравариантным: TreeMap [Object, Foo] can ' не может использоваться в качестве TreeMap [String, Foo], потому что, когда мы получаем ключ, ключ может не быть String. </p>

И поскольку это двоичное дерево поиска, ему необходим Comparator [K] для внутреннего использования, что сразу затрудняет ковариантность K: если вы используете TreeMap [String, Foo] в качестве TreeMap [Object, Foo], то вы неявно используете Comparator [String] в качестве Comparator [Object], что не работает Теперь, поскольку карта, безусловно, содержит только строковые ключи, возможно, метод get может обойти это, предварительно проверив тип ключа перед вызовом, используя Comparator [String]; но методы 'floorEntry' и 'floorEntry' по-прежнему остаются проблемой: какая запись идет «до» или «после» произвольного объекта, который нельзя сравнить с ключами на карте?

И даже если вы сказали, что ваша карта неизменна, вам, вероятно, все еще нужен какой-то метод 'put', просто функциональный, который возвращает измененную копию карты. (Чисто функциональные красные чёрные деревья поддерживают те же инварианты и асимптотические наихудшие сложности c времени, что и изменяемые, так что, за исключением системы типов, это, безусловно, разумная вещь.) Но если TreeMap [String, Foo] может быть используется как TreeMap [Object, Foo], тогда его метод 'put' должен поддерживать возврат бинарного дерева поиска, содержащего ключ non -String - даже если его Comparator [String] не определяет упорядочение таких ключей.

(В комментарии вы упоминаете, что Scala фактически определяет Map [K, + V] с типом инвариантного ключа. Я никогда не использовал Scala, но держу пари, что именно поэтому.)

...