Пишите код, который читается как спецификация

Как я уже упоминал немного ранее, существует несколько ошибок в коде компилятора, который анализирует нарушение классами правила отсутствия циклических зависимостей базовых классов (поскольку классу запрещено прямо или косвенно наследовать от себя самого, а также запрещается прямо или косвенно наследовать от собственных вложенных классов). Ошибки в основном проявляются в том, что мы случайно обнаруживаем циклические зависимости в подозрительном обобщенном коде (generic code), который на самом деле, циклов не имеет. Эти ошибки являются результатом модификации кода определения циклических зависимостей из C# 1.0, вместо переписывания его с нуля для обработки обобщений. К сожалению, мы не смогли исправить эти ошибки в C# 4, поскольку существуют хитрые граничные сценарии, и мы посчитали, что риск исправления этих ошибок слишком велик.

Существует несколько коварных проблем, в основном связанных с тем, что мы не можем знать, содержит ли набор базовых типов циклы, пока не узнаем, что из себя представляют эти базовые типы, но анализ строки базового типа, вида “C.D<E.F>” требует, чтобы мы знали базовые типы для C, поскольку D может быть вложенным типом базового класса C, а не самого класса C. Т.е. мы получаем классическую проблему курицы и яйца. Код, преобразующий строки в типы должен надежно справляться с проблемой циклов базовых типов, поскольку класс определения циклов базовых типов зависит от его результатов!

Как я уже говорил, я предложил новый алгоритм, который реализует спецификацию более точно, и захотел его проверить. Для использования этого алгоритма, вместо модификации существующего компилятора, я быстро написал несколько заглушек на C#, просто для того, чтобы получить некоторый результат. Одна из проблем в существующем компиляторе заключается в том, что совершенно не понятно, какая часть кода отвечает за реализацию определенной строки спецификации. В «макете» моего компилятора я хотел убедиться в том, что спецификация реализуется действительно точно; это может выявить проблемы с логикой в реализации, либо в спецификации. Поэтому я хотел написать код, который бы читался как спецификация.

Этот небольшой кусок кода сделал меня невероятно счастливым. Вот фрагмент спецификации:

Класс непосредственно зависит от своего прямого базового класса (если такой существует) и непосредственно зависит от класса, в который он непосредственно вложен (если такой существует). Полный набор классов, от которых зависит класс, является рефлексивным и транзитивным замыканием отношения непосредственной зависимости.

Прежде всего, что это за штука, «рефлексивное и транзитивное замыкание»?

Рассмотрим «отношение» (relation) – функцию, которая принимает два аргумента и возвращает тип Boolean, который говорит о том, выполняется отношение или нет. Отношение, назовем его ~>, является рефлексивным, если отношение X~>X истинно для всех X. Отношение является симметричным, если выполнение отношения A~>B всегда влечет выполнение отношения B~>A. И отношение является транзитивным, если из выполнения отношений A~>B и B~>С следует выполнение отношения A~>C.[i]

Например, отношение «меньше или равно» для целых чисел является рефлексивным: X≤X истинно для всех X. Но не является симметричным: 1≤2 – истинно, но 2≤1 – ложно. И это отношение транзитивно: если выполняются отношения A≤B и B≤C, то отношение A≤C также выполняется обязательно.

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

Отношение «является родителем для», если рассматривать его для людей, не является рефлексивным, поскольку человек не может быть собственным родителем. Это отношение не симметрично: если A является родителем для B, тогда B точно не является родителем для A. И оно не транзитивно: если A является родителем для B и B является родителем для C, то А не является родителем для C (хотя A является прародителем для C).

Можно взять нетранзитивное отношение, такое как «является родителем для» и создать из него транзитивное отношение. Мы просто создаем новое отношение, которое в точности совпадает с исходным, но мы принудительно делаем его транзитивным. В данном случае мы получим отношение «является предком»: если A является предком для B, и В является предком для C, тогда A обязательно является предком для C. Говорят, что отношение «является предком» является транзитивным замыканием отношения «является родителем».

Аналогичным образом мы можем определить рефлексивное замыкание и т.п.

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

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

static HashSet<T> TransitiveClosure<T>(
    this Func<T, IEnumerable<T>> relation,
    T item)
{
    var closure = new HashSet<T>();
    var stack = new Stack<T>();
    stack.Push(item);
    while(stack.Count > 0)
    {
        T current = stack.Pop();
        foreach(T newItem in relation(current))
        {
            if (!closure.Contains(newItem))
            {
                closure.Add(newItem);
                stack.Push(newItem);
            }
        }
    }
    return closure;
}
static HashSet<T> TransitiveAndReflexiveClosure<T>(
    this Func<T, IEnumerable<T>> relation,
    T item)
{
  var closure = TransitiveClosure(relation, item);
  closure.Add(item);
  return closure;
}

Обратите внимание, что, по сути, мы выполнили обход в глубину (depth-first traversal) графа, полученного с помощью отношения транзитивного замыкания, избегая прохождение уже пройденных регионов.

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

static IEnumerable<TypeSymbol> DirectDependencies(TypeSymbol symbol)
{
// SPEC: Класс непосредственно зависит от своего прямого базового класса (если такой существует)…
if (symbol.BaseTypeSymbol != null)
yield return symbol.BaseTypeSymbol;
// SPEC: ...и непосредственно зависит от класса
// SPEC: в который он непосредственно вложен (если такой существует).
if (symbol.OuterTypeSymbol!= null)
yield return symbol.OuterTypeSymbol;
}

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

static HashSet<TypeSymbol> Dependencies(TypeSymbol classSymbol)
{
// SPEC: Полный набор классов, от которых
// SPEC: зависит класс является рефлексивным
// SPEC: и транзитивным замыканием отношения

// SPEC: непосредственной зависимости
    return TransitiveAndReflexiveClosure(DirectDependencies, classSymbol);
}

Вот, что я хотел получить: код, который читается практически так же, как и спецификация.

Обратите внимание, что я принял решение сделать эти методы статическими методами класса Policy, а не методами класса TypeSymbol. Я хочу логически и физически отделить стратегии от внутреннего устройства. Например, я могу использовать те же самые классы представляющие классы, структуры, пространства имен и т.п. для реализации компилятора VB, вместо C#. Я хотел, чтобы стратегии языка C# были в классе, чья единственная ответственность заключалась бы в реализации этих стратегий.

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

Набор базовых интерфейсов – это транзитивное замыкание базовых интерфейсов.

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

static HashSet<TypeSymbol> BaseInterfaces(TypeSymbol interfaceSymbol)
{
// SPEC: Набор базовых интерфейсов – это транзитивное замыкание
// SPEC: базовых интерфейсов.
return TransitiveClosure(ExplicitBaseInterfaces, interfaceSymbol);
}

На самом деле, транзитивное замыкание присутствует в нескольких местах спецификации языка C#, и теперь у меня есть механизм, который я могу использовать для реализации всех их, а не только тех, которые требуются моему прототипу.

Последнее замечание: обратите внимание, что я возвращаю изменяемую коллекцию (mutable collection). Если бы я разрабатывал эти методы для публичного использования, я, скорее всего, вместо изменяемой коллекции возвращал бы неизменяемую, что позволило бы мне свободно кэшировать результаты. Эти методы могли бы быть сохранены в памяти, поскольку набор зависимостей не будет изменяться с течением времени. Но для моего маленького прототипа, мне было лень, поэтому я возвращаю изменяемую коллекцию и не кэширую результат.

Надеюсь, мы воспользуемся этим алгоритмом в следующем выпуске компилятора.

 

Оригинал статьи


[i] Кстати, мы настаиваем на использовании волнистой стрелки ~>, как потенциального оператора в будущих версиях языка C#. Недавно мы решили, что a~>b может означать ((dynamic)a)b(). Оператор известен под названием «naj-оператор» по имени Cyrus Najmbadi, человека, который предложил этот оператор команде разработчиков C#. Если у кого-то есть хорошие идеи по поводу того, что же должен означать naj-оператор, пишите в комментариях.