Как убедиться, что вывод типов метода завершится?

  • Article

Я все пропустил! Я подготовился к огромной волне анонсов по поводу выхода языка TypeScript, но форс-мажорные семейные обстоятельства оторвали меня от компьютеров, и я не добавил свою статью в очередь на публикацию. Достаточно будет сказать, что мне ОЧЕНЬ И ОЧЕНЬ нравится идея языка TypeScript. Постоянные читатели этого блога знают, что я длительное время занимался ECMAScript, и мне давно хотелось иметь что-то подобное. Поскольку первую волну я пропустил, я собираюсь рассказать о первых реакциях на этот язык, а затем написать что-то более глубокомысленное по этой теме.

Так что, вместо того, чтобы говорить сегодня о TypeScript, вот вопрос, который задал мне один из моих коллег: поскольку явно важно, чтобы компилятор языка C# не попадал в бесконечные циклы, как мы можем убедиться, что алгоритм вывода(1) типов метода завершится?

Ответ, на самом деле, довольно прост, но если вы не знакомы с выводом типов методов, тогда эта статья не будет иметь для вас никакого смысла. Если вам нужно обновить знания по этой теме, то загляните в мой архив по теме вывода типов, и особенно обратите внимание на это видео.

По сути, вывод типов методов, начиная с языка C# 3.0, работает следующим образом: мы создаем набор границ (bounds) для каждого параметра типа. Затем мы «фиксируем» каждый параметр типа к соответствующему члену из этого набора. Вывод типов метода завершается успешно, как только каждый параметр типа будет зафиксирован. Если по какой-то причине параметр типа не может быть зафиксирован, то вывод типов завершается неудачно. Мы гарантируем завершаемость процесса вывода типов путем тщательного анализа исполняемого цикла. Если текущая итерация цикла завершается без фиксации, по крайней мере, одного параметра типа, то вывод типа завершается неудачно. Таким образом, цикл вывода типов может исполняться не более n раз для метода с n параметрами типа.

Приведенное решение несколько идеализировано: давайте рассмотрим, что я имею в виду. «Граница» – это всего лишь некоторый тип, и граница может быть «верхней», «нижней» или «точной» (exact). Давайте, например, предположим, что у нас есть параметр типа Т с тремя границами: нижняя граница – Giraffe, точная граница – Mammal, и верхняя граница – Animal. Давайте предположим, что тип Animal является «бОльшим» типом, чем Mammal (поскольку все млекопитающие (Mammal) являются животными (Animal), но не все животные являются млекопитающими, так что тип Animal больше), и тип Giraffe «меньше», чем Mammal. При наличии таких границ мы знаем, что тип Т должен быть, во-первых, либо типом Giraffe, либо типом, большим чем Giraffe, поскольку тип Giraffe является нижней границей; мы не можем использовать тип, меньший чем Giraffe. Во-вторых, мы знаем, что тип Т должен быть в точности типом Mammal. И, в-третьих, мы знаем, что тип Т должен быть либо типом Animal, или типом, меньшим чем Animal, поскольку тип Animal является верхней границей. Мы не можем вывести в качестве типа больший тип, чем Animal. Компилятор языка C# понимает, что тип Mammal является единственным типом, удовлетворяющим всем трем требованиям, так что в качестве типа Т фиксируется тип Mammal. Если существует несколько типов, которые отвечают всем трем требованиям (что, конечно, невозможно при наличии точной (exact) границы!), тогда мы выбираем самый большой тип. (*)

Интересный аспект вывода типов методов заключается в том, как мы работаем с лямбда-выражениями. Предположим, у нас есть метод Select<A, R>(I<A>, Func<A, R>), где второй аргумент – это c => c.Name. Мы говорим, что A является “входным” (input) параметром типа и R является “выходным” (output) параметром типа. (Конечно, возможно, чтобы параметр типа был одновременно и входным и выходным!) Более того, мы говорим, что R «зависит» от A, поскольку тип A может определять тип R. (И, конечно, отношение «зависит» может быть циклическим.)

На высоком уровне, алгоритм вывода типов выглядит так:

  • Добавляем границы параметров типа на основе аргументов, которые не являются лямбда-выражениями, или на основе лямбда-выражений, делегат которых не содержит «входных» параметров типа.
  • Цикл:
    • Является ли параметр типа зафиксированным?
      • Вывод типа завершен успешно. Завершаем алгоритм.
    • Существует ли аргумент лямбда-выражения, конвертируемый к типу делегата, все входные типы которого известны, и выходные типы включают незафиксированные параметры типа?
      • Выводим типы возвращаемого значения для всех таких выражений, и выводим верхние границы для соответствующих выходных типов делегатов.
    • Существуют ли незафиксированные привязанные параметры типа, которые не является выходными типами делегата с незафиксированными входными типами?
      • Зафиксировать все такие параметры типа и перейти к началу итерации цикла.
    • Существуют ли такие незафиксированные привязанные параметры типа, от которых зависят явно или неявно другие незафиксированные параметры типа?
      • Зафиксировать все такие параметры типа и перейти к началу итерации цикла.
    • Если мы дошли до этого места, то мы не смогли продвинуться в нашем процессе вывода типов; у нас все еще то же самое количество зафиксированных параметров типа, что и было. Вывод типов завершается неудачно. Завершаем алгоритм.

Так, например, если у нас есть метод Select(customers, c => c.Name); где customers реализует I<Customer>, тогда мы выводим, что нижняя граница типа A является типом Customer (**). У нас нет аргумента лямбда-выражения, соответствующего формальным параметрам, тип делегата которого не содержит параметров типа, в качестве входных типов, так что мы начинаем цикл.

Все ли параметры типа зафиксированы? Нет.

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

Нет. Существующее лямбда-выражение преобразуется к типу делегата, выходной тип которого включает незафиксированный параметр типа R, но входным его типом является A, который еще не зафиксирован. Так что мы не можем произвести никакого вывода типов.

Существует ли незафиксированный параметр типа с определенными границами, который не является выходным типом делегата с незафиксированными входными типами?

Да. Для типа A определены границы, и он не является выходным типом. Точка.

Фиксируем тип А. У него есть лишь одна граница, Customer, так что мы фиксируем его к типу Customer. Мы продвинулись в выводе типов, поэтому можем переходить к началу следующей итерации.

Все ли типы параметры зафиксированы? Нет.

Существует ли лямбда-выражение, которое можно преобразовать к типу делегата, со всеми известными входными типами, и выходным типом, включающим незафиксированный параметр типа? Да!

Выводим тип. A зафиксирован к типу Customer, так что мы добавляем тип Customer.Name, скажем, тип string, в качестве нижней границы типа R.

Теперь мы должны что-то зафиксировать. Существует ли незафиксированный параметр типа с определенными границами, который является выходным типом делегата с зафиксированными входными типами?

Да. Тип R не зафиксирован, его границы определены и он является выходным типом делегата, чьи входные типы зафиксированы, так что он является подходящим кандидатом для фиксации его типа. Мы фиксируем R к его единственной границе, типу string, и переходим к новой итерации цикла.

Все ли параметры типа зафиксированы? Да. Вывод типа завершен.

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

Вы можете задать такой вопрос: следует ли из этого, что сложность алгоритма вывода типов равна O(n) по отношению к количеству параметров типа. Как выясняется, это не так, по нескольким причинам. Во-первых, с практической точки зрения асимптотическую сложность алгоритмов имеет смысл использовать, только когда n становится достаточно большим. Я никогда не видел реального примера использования более пяти параметров типа, и даже такое количество является достаточно необычным. Большинство обобщенных методов содержат один или два параметра типа. Во-вторых, анализ лямбда-выражения является дорогостоящей операцией, и в реальности имеет смысл анализировать поведение самой дорогой составляющей. Мы знаем, что в худшем случае, анализ лямбда-выражения является NP-полной задачей, так что конкретная сложность алгоритма вывода типов, на самом деле, не важна. В-третьих, вы могли заметить, что мой набросок алгоритма не содержит ответа на следующий вопрос: «существует ли незафиксированный параметр типа, который зависит от другого незафиксированного параметра типа?». Ответ на этот вопрос требует решения обхода графа, асимптотическую сложность которого мы не анализировали! Я не хочу нагружать вас скучными подробностями, просто достаточно сказать, что может существовать O(n^2) количество зависимостей, анализ каждой из которых является O(n), и мы можем выполнять его n раз, так что в самом наихудшем маловероятном случае сложность будет O(n^4). Настоящая реализация этого алгоритма в общем случае дает сложность O(n^2); а поскольку значение n обычно весьма мало, то, как я уже сказал, мы не прилагаем дополнительных усилий для написания более хитрого алгоритма, дающего лучшую асимптотическую сложность.

(*) Обратите внимание, что этот алгоритм согласуется с другими возможностями вывода типов в языке C# в двух аспектах. Во-первых, при выводе лучшего типа из набора типов мы всегда выбираем тип из этого набора. Мы никогда не сделаем так: «ну, предположим, у нас есть типы Dog и Cat, так что давайте будем использовать тип Mammal». Во-вторых, если мы сталкиваемся с несколькими «самыми подходящими» типами, мы выбираем самый большой тип из них. Есть доводы за то, чтобы выбрать самый маленький из них, но выбор самого большого типа для большинства людей интуитивно кажется лучшим решением.

(**) Предположим, что тип I<T> ковариантен по T. Если бы он был контравариантным, то мы бы вывели верхнюю границу, а если он инвариантен, но мы бы вывели «точную» границу. Смотрите серию моих статей по вариантности типов, если этого мало.

1) Прим. редактора. Под словом «вывод» имеется в виду логическая цепочка операций, выполняемая компилятором и приводящая к определению типа объекта.