Невероятные приключения в коде

Динамическое заражение, часть вторая

Russian MSDN — Thu, 21 Feb 2013 06:49:59 GMT

В прошлый раз мы обсуждали, как параметр «dynamic» стремится расшириться по программе подобно вирусу: если выражение типа dynamic «касается» другого выражения, то последнее зачастую тоже становится типа dynamic. Сегодня я хочу остановиться на менее всего понимаемом аспекте вывода типа метода, который также применяет модель заражения, когда в игру вступает параметр «dynamic».

Постоянные читатели знают, что вывод типа метода является одной из моих излюбленных тем в языке C#; для новых читателей, не знакомых с предметом, позвольте дать краткое введение. Идея в том, что когда вы имеете метод, скажем, Select<A, R>(IEnumerable<A> items, Func<A, R> projection), и вызываете его, например, следующим образом Select(customers, c=>c.Name), мы делаем вывод, что вы имели в виду Select<Customer, string>(customers, c=>c.Name), вместо разбирательства, что же вы хотели сказать. В данном случае мы, прежде всего, предполагаем, что список заказчиков есть IEnumerable<Customer>, и поэтому тип аргумента, соответствующий A есть Customer. Из этого мы выводим, что лямбда-параметр «c» имеет тип Customer, и поэтому результатом лямбда-выражения является строка, следовательно, типом аргумента, соответствующего R является строка. Алгоритм уже завершен, но когда в игру вступает параметр «dynamic» получается что-то совершенно фантастическое.

Проблема заключается в том, что конструкторы языка столкнулись при решении того, как работает вывод типа метода с параметром dynamic, с усложнением нашей основной цели конструирования, о которой я недавно рассказывал: анализ во время исполнения динамических выражений требует всей информации, которую мы вывели при компиляции. Мы используем лишь выведенные при исполнении типы для частей выражений, которые на самом деле динамические; части, которые были статически типизированы при компиляции, остаются статически типизированными и при исполнении, а не динамическими. Выше мы определили R после того, как узнали A, но что если бы «customers» был типа dynamic? Теперь у нас проблема: в зависимости от типа во время исполнения customers, вывод типа может успешно завершиться динамически даже в случае, если, казалось бы, он должен окончиться неудачно при статическом анализе. Но если вывод типа оканчивается неудачей в статическом случае, то он не является кандидатом, и, как осуждалось ранее, если набор кандидатов в группу динамически диспетчеризуемых методов пуст, то разрешения перезагрузки оканчиваются неудачей во время компиляции, а не во время выполнения. Так что, выходит, что вывод типа должен завершиться успехом при статическом анализе!

Какой беспорядок. Как нам выйти из этого затруднения? Спецификация удивительно скупа на детали, она говорит лишь:

Для аргумента любого типа, не зависящего прямо или косвенно от аргумента типа dynamic, предполагается использование [обычных правил статического анализа]. Оставшиеся типы аргументов являются неизвестными. [...] Применимость проверяется согласно [обычным правилам статического анализа] игнорируя параметры, чей тип неизвестен. (*)

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

Например, если у нас есть:

void M<T, U>(T t, L items)

с вызовом

M(123, dyn);

то вывод типа заключает, что T является целым (int) из первого аргумента. Так как второй аргумент типа dynamic, и формальный параметр типа включает параметр U, мы «помечаем» U «неизвестным типом».

Когда помеченный параметр типа «зафиксирован» к окончательному типу аргумента, мы игнорируем все остальные ограничения, вычисленные до сих пор, даже если некоторые из них противоречивы, и считаем, что тип будет «неизвестным». Поэтому в данном случае вывод типа будет успешным и сможем добавить к набору кандидатов M<int, unknown>. Как упоминалось ранее, мы опустили проверку применимости для аргументов, которые соответствуют параметрам, чьи типы были так или иначе помечены.

Но каким образом появляется транзитивное замыкание отношения зависимости? В компиляторах C# 4 и 5 мы не управляем этим достаточно уверенно, но в Roslyn мы действительно заставляем метку расширяться. Предположим, у нас есть:

void M<T, U, V>(T t, L items, Func<T, U, V> func)

и вызов

M(123, dyn, (t, u)=>u.Whatever(t));

Мы считаем, что T имеет тип int, а U – неизвестный. Затем мы говорим, что V зависит от T и U, и поэтому выводим, что тип V также неизвестен. Поэтому вывод типа завершается успешно с результатом M<int, unknown, unknown>.

Внимательный читатель здесь может возразить, что не важно, что произойдет с выводом типа метода, все идет к динамическому вызову, и лямбда-выражения, первым делом, не разрешены в динамических выводах. Однако мы бы хотели получить столько высококачественного анализа, сколько это возможно, и чтобы IntelliSense и другие средства анализа кода работали корректно даже в неверном коде. Лучше позволить U заразить V меткой «unknown» и получить успешный результат при выводе типа, чем сперва начать выпутываться и получить отказ в выводе типа. И кроме того, если произойдет чудо, и мы в будущем разрешим лямбда-выражения при динамических вызовах, мы уже будем иметь здравую реализацию вывода типа метода.

(*) Последний пункт слегка неясен по двум причинам. Во-первых, необходимо действительно сказать «чьи типы являются неизвестными при любом способе». L<unknown> рассматривается как неизвестный тип. Во-вторых, наряду с пропуском проверки применимости мы также пропускаем проверку выполнения ограничивающих условий. Что означает, мы предполагаем конструкция времени выполнения L<unknown> обеспечит тип аргумента, удовлетворяющий всем необходимым ограничениям типа общий (generic).

Динамическое заражение, часть первая

Russian MSDN — Wed, 23 Jan 2013 05:57:51 GMT

Предположим, что вы эпидемиолог, моделирующий возможное распространение сильно заразной болезни. Прямой способ моделирования серии прискорбных событий – предположить, что население может быть разделено на три категории: определенно зараженных, определенно здоровых и возможно зараженных. Если здоровый встречается с зараженным или возможно зараженным, то он переходит в категорию возможно зараженных. (Или, иначе, категория возможно зараженных транзитивно замкнута относительно отношения заражения.) Член категории возможно зараженных становится либо определенно здоровым, либо определенно зараженным после некоторых тестов. И зараженный может стать здоровым, пройдя лечение.

Такой вид модели заражения довольно распространен при конструировании вычислительных систем. Например, предположим, что у вас есть веб-сайт, принимающий строки от пользователя, сохраняющий их в базе данных и подсовывающий их другим пользователям. Например, этот блог, который собирает комментарии от вас, сохраняет их в базе данных и затем подсовывает обратно другим пользователям. Это ��така носит название Cross Site Scripting (XSS) и может случиться прямо здесь. Общий способ смягчения XSS-проблемы состоит в изменении данных, использующих модель заражения для выявления возможно злокачественных строк. Что бы вы ни делали с потенциально злокачественными строками, например, соединяли их с доброкачественными строками, результатом будет возможно злокачественная строка. Если строка с помощью некоторого теста определяется как доброкачественная, или из нее вырезаются потенциально злокачественные части, то она становится безопасной.

Возможность применения оператора «dynamic» в С# 4 и более старших версиях имеет много общего с таким типом заражения. Как я отметил в прошлый раз, когда аргумент вызова динамическая переменная, то довольно велики шансы, что компилятор определит, что результат вызова также является динамическим; зараза распространяется. Фактически, при использовании почти любого оператора в динамическом выражении, результат будет динамическим за несколькими исключениями (например, оператор «is» всегда возвращает булевский тип результата). Можно «вылечить» выражение, чтобы предотвратить распространение динамизма, отбрасывая его к типу object, или к какому-то другому не динамическому типу по вашему выбору; отбрасывание динамического типа к объекту – это изменение его идентичности.

Способ, которым dynamic вызывает заражение, является производным явлением правил работы с типами выражений в С#. Однако есть одно место, где мы явно используем модель заражения внутри компилятора для того, чтобы корректно определять тип выражения, включающего динамические типы: это один из наиболее загадочных аспектов вывода типов метода. В следующий раз я расскажу вам все о нем.

Группа из одного метода

Russian MSDN — Mon, 21 Jan 2013 12:06:47 GMT

На этой неделе я реализовывал семантический анализ динамических выражений в проекте Roslyn, так что я исследовал множество вопросов со своей командой, касающихся дизайна динамических возможностей в C# 4. В этом контексте мне очень часто задают следующий вопрос:

public class Alpha
{
public int Foo(string x) { ... }
}
...
dynamic d = whatever;
Alpha alpha = MakeAlpha();
var result = alpha.Foo(d);

Как осуществляется анализ этого кода? А более точно вопрос заключается в том, какой тип локальной переменной result?

Если тип приемника (т.е. переменная alpha) вызова метода является типом dynamic, тогда мы мало что можем сделать на этапе компиляции. Мы проанализируем типы аргументов времени компиляции и сгенерируем вызов динамического объекта, что приведет к переносу семантического анализа во время исполнения на основе типов времени исполнения динамического выражения. Но в данном случае это не так. Во время компиляции мы знаем тип приемника. Один из ключевых принципов проектирования динамических возможностей языка C# заключается в том, что если мы точно знаем тип во время компиляции, то он учитывается при анализе во время исполнения. Другими словами, мы используем тип времени исполнения только в том случае, если он действительно является динамическим; во всех остальных случаях мы используем тип времени компиляции. Если MakeAlpha() возвращает класс-наследник от Alpha и этот класс содержит несколько перегруженных версий метода Foo, то нам все равно.

Поскольку мы знаем, что собираемся выполнять анализ перегрузки методов для вызова метода Foo экземпляра типа Alpha, то мы можем выполнить «санитарную проверку» (sanity check) во время компиляции, и убедиться, что мы не упадем гарантированно во время исполнения. Таким образом, мы выполняем разрешение перегрузки, но вместо исполнения полного алгоритма (устранения неподходящих кандидатов, определения уникального наиболее подходящего кандидата, выполнения окончательной валидации кандидата), мы выполняем частичный алгоритм. Мы отсекаем неподходящие кандидаты и если у нас остается один или более кандидатов, тогда мы используем динамическую привязку метода. Если у нас не остается кандидатов, то мы выдаем сообщение об ошибке, поскольку у нас точно ничего не будет работать во время выполнения.

Теперь может возникнуть вполне резонный вопрос: механизм перегрузки методов может определить, что в группе методов (method group) существует лишь один подходящий кандидат, а значит, мы можем статически определить, что тип результата будет int, так почему мы говорим, что типом результата является dynamic?

Вопрос кажется разумным, но давайте еще немного подумаем об этом. Если вы знаете, я знаю, и компилятор знает о том, что механизм перегрузки выберет конкретный метод, то зачем вы вообще делаете динамический вызов? Почему бы не преобразовать d к типу string? Это редкая ситуация, у которой есть простое обходное решение путем добавления соответствующего преобразования типов (преобразование выражения вызова к int, или аргумента к string). Редкие, маловероятные ситуации, для которых есть простое обходное решение, являются плохими кандидатами для оптимизации в компиляторе. Вы просите динамический вызов, вот вы его и получаете.

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

public class Eta {}

И Zeta Corporation расширила его следующим образом:

public class Zeta : Eta
{
public int Foo(string x){ ... }
}
...
dynamic d = whatever;
Zeta zeta = new Zeta();
var result = zeta.Foo(d);

Предположим, мы знаем, что типом результата является int, поскольку группа методов состоит лишь из одного кандидата. Теперь предположим, что в новой версии Eta Corporation добавила новый метод:

public class Eta
{
public string Foo(double x){...}
}

Zeta Corporation перекомпилировала свой код, и, вуаля, тип возвращаемого значения внезапно изменился на dynamic! Почему изменения, сделанные Eta Corporation в базовом классе должны изменить семантический анализ класса-наследника? Это кажется неожиданным. Язык C# был тщательно спроектирован, чтобы избежать такого рода проблем, называемых «проблемами Хрупких Базовых Классов» (“Brittle Base Class” failures); см. мои другие примеры по этой теме.

Эту ситуацию можно еще ухудшить. Предположим, Eta Corporation внесла вместо этого такие изменения:

public class Eta
{
protected string Foo(double x){...}
}

Что будет теперь? Должен ли тип результата быть int при вызове снаружи класса Zeta, поскольку алгоритм перегрузки дает лишь один доступный кандидат, но будет типом dynamic при вызове изнутри класса, поскольку кандидатов будет два? Такое поведение будет еще более странным.

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

В следующий раз: динамические проблемы при выводе типов методов.

C# – это строго типизированный или слабо типизированный язык?

Russian MSDN — Tue, 15 Jan 2013 13:01:23 GMT

Сегодняшний пост, как обычно будет представлен в виде диалога.

C# – это строго типизированный или слабо типизированный язык программирования?

Да.

Ответ не очень-то полезный.

Я серьезно. Любопытно, что если вы перефразируете свой вопрос так, чтобы в нем было «И», то ответ будет таким же.

Что? Вы имеете в виду, что C# является и строго типизированным и слабо типизированным языком?

Да, C# является строго типизированным и слабо типизированным языком.

Я запутался.

Я тоже. Возможно, вам стоит точно определить, что означает для вас «строго типизированный» и «слабо типизированный».

Хм. Я не знаю точно, что я подразумеваю под этими понятиями,… возможно именно это я и хочу узнать. Что на самом деле значит, что язык является «слабо типизированным» или «строго типизированным»?

«Слабо типизированный» означает «язык использует систему проверки типов, которая мне не нравится» и «строго типизированный» означает «язык использует систему типов, которая мне нравится».

Ну уж нет!

Ну, правда.

Серьезно?

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

Но они явно значат что-то более конкретное, нежели «нравится» или «не нравится»!

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

Тогда как можно конструктивно говорить о языках программирования и их системах типов?

Вы можете дать этот дополнительный контекст. Вместо того чтобы использовать «строго типизированный» и «слабо типизированный», можно просто описать те ограничения, которые вы имеете в виду. Например, язык C# в большинстве случаев является статически типизированным языком, поскольку компилятор определяет информацию о типах каждого выражения. Язык C# в большинстве случаев является типобезопасным языком, поскольку он запрещает хранение значений одного статического типа в переменных несовместимого типа (он также предотвращает и от других подобных ошибок типизации). И язык C# в большинстве случаев является безопасным с точки зрения памяти, поскольку он предотвращает случайный доступ к невалидной памяти.

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

Но здесь есть один момент: поскольку C# является прагматичным языком, существует возможность переопределить все эти три аспекта безопасности. Оператор преобразования типов и ключевое слово “dynamic” языка C# 4 «переопределяет» проверку типов времени компиляции и заменяет ее проверками времени исполнения, блоки “unsafe” позволяют, если нужно, отключить безопасность типов и памяти. Поэтому если кто-то считает, что «строго типизированный» означает «язык, который абсолютно во всех случаях гарантирует статическую типизацию, безопасность типов и памяти при любых условиях», то он вполне сможет отнести C# к «слабо типизированным» языкам. C# не настолько строго-типизированный по сравнению с языками, которые всегда налагают эти ограничения.

Так к какому типу относится C#: строго типизированному или слабо типизированному? На этот вопрос невозможно ответить, поскольку ответ зависит от точки зрения конкретного человека, от того, с чем сравнивать, и зависит от склонности конкретного человека к использованию различных возможностей языка. Поэтому проще всего избегать использования этих терминов и говорить более точно о возможностях системы типы языка.

Невычислимое

Russian MSDN — Wed, 19 Dec 2012 09:57:38 GMT

Мы можем рассматривать компьютерную программу, как устройство, которое берет на вход набор целых чисел и выдает на выходе другой набор целых чисел. Компилятор языка C#, например, принимает на вход строки исходного кода, а это всего лишь набор огромных двоичных чисел. На выходе компилятора мы получаем либо диагностический текст, или строки IL-кода и метаданных, которые, опять-таки, всего лишь огромные двоичные числа. Поскольку компилятор не идеален, иногда его работа завершается аварийно с внутренними сообщениями об ошибках. Но эти сообщения об ошибках, также являются лишь огромными двоичными числами. Поэтому давайте возьмем за основу компьютерной программы следующую простую модель: компьютерная программа – это устройство которое, либо (1) бесконечно исполняется, не выдавая ничего на выходе, либо (2) вычисляет функцию соответствия одного целого числа другому.

Вот интересный вопрос: существуют ли такие функции, которые невозможно вычислить даже в принципе на компьютере с произвольным размером хранилища, с помощью любой программы на языке C# (*)?

Мы уже знаем ответ на этот вопрос. В прошлом году я указывал на то, что Проблема Останова не решаема ни одной компьютерной программой, поскольку даже предположение о том, что она решаема, ведет к логическому противоречию. Но Проблема Останова – это всего лишь функция на целых числах. Давайте скажем, что на вход нашей функции H поступает число, которое после записи в виде юникодной строки может содержать программу на языке C#. На выходе мы получаем 1, если программа является некорректной программой на языке C#, 2 – если программа корректна и когда-либо завершается, и 3 – если программа корректна и выполняется бесконечно. Если бы было можно написать программу, которая надежным образом вычисляла бы функцию H и всегда завершалась, тогда ее можно было бы использовать для решения Проблемы Останова, что, как известно, невозможно. Таким образом, H является невычислимой функцией.

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

Без потери общности, давайте предположим, что внешнее хранилище машины Тьюринга может хранить произвольно большое количество битов, либо нулей, либо единиц, и что внутреннее хранилище позволяет хранить фиксированное количество битов, например, n. Это достаточно серьезные ограничения, но они не являются фундаментальными. Настоящие компьютеры, конечно же, манипулируют данными, представляющие собой 32-разрядные целые или 64-разрядные числа с плавающей точкой, и тому подобное, но на некотором уровне внутри процессора, все равно происходит манипуляция на уровне битов. Нет принципиальной разницы между машиной, манипулирующей одним битом в один момент времени и машиной, манипулирующей 64 битами; второй вариант просто более удобен.

Так как��е количество правил нам нужно для описания нашей машины Тьюринга? Машина Тьюринга с n битами, описывающими внутреннее состояние может иметь 2^n возможных состояний, а также существует два возможных значения «текущей позиции» во внешнем состоянии. (**) Таким образом, у нас есть 2^(n+1) правил перехода между состояниями. Каждое правило перехода должно кодировать три вещи: (1) чему равны n бит нового внутреннего состояния? (2) на какое значение должно измениться внешнее состояние? и (3) как мы должны обновить текущее положение?

Опять-таки, без потери общности, давайте предположим, что обновление текущей позиции осуществляется таким образом: увеличение значения на единицу, уменьшение значения на единицу или использование старого значения. На практике это было бы неудобно, но в принципе этого достаточно. Итак, у нас есть три варианта. Тогда каждое правило изменения состояния имеет 2 x 2^n x 3 вариантов при наличии 2 ^ (n + 1) правил перехода. Таким образом, общее число возможных машин Тьюринга, с n битами внутреннего хранилища, равняется 3 x 2 (n + 1) в степени 2 ^ (n + 1), что, да, приводит к очень быстрому росту при увеличении n, однако все равно, является конечным числом.

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

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

Теперь мы можем найти функцию S, которая принимает одно целое и возвращает – другое. Функция S принимает n – количество бит внутреннего состояния Машины Тьюринга и выдает максимальное количество шагов, требуемое любой возможной n-битовой Машине Тьюринга, чтобы перейти в конечное состояние. Т.е. S принимает количество битов внутреннего хранилища и выдает время ожидания самой медленной n-битовой машины, которое нужно ей для останова при начале исполнения с пустого внешнего хранилища.

Вычислима ли функция S? Можем ли мы написать компьютерную программу, вычисляющую эту функцию?

Интуиция должна подсказывать, что «нет», но можете ли вы сказать почему?

Потому что, если функция S вычислима, то функция H тоже должна быть вычислимой! Все, что нам нужно для вычисления функции H, это создать компьютерную программу, которая будет компилировать указанную программу на языке C# в симулятор машины Тьюринга, исполняемой на пустом внешнем хранилище. Мы берем количество битов состояния n машины Тьюринга и вычисляем S(n). Затем мы запустим симулятор машины Тьюринга, и если это потребует более S(n) шагов, тогда мы знаем, что это одна из n-битовых машин Тьюринга, которые исполняются вечно. Таким образом, мы сможем надежно вычислить H за конечное время. А поскольку мы знаем, что функция H не может быть надежно вычислена за конечное время, тогда мы знаем, что функция S также не может быть исполнимой.

Приведенные мной здесь аргументы известны как «задача усердных бобров» (Busy Beaver), поскольку n-битовая машина Тьюринга исполняется столько, сколько работает «самый усердный бобер». Я несколько изменил привычный способ представления этой проблемы; обычно «самый усердный бобер» представлен как машина Тьюринга с k состояниями и максимальным выходным результатом, а не как n-битовая машина, которая исполняется дольше всего до останова. Хотя две главные характеристики остаются теми же самыми; обе версии такой функции невычислимы.

Интересным фактом о функции «усердных бобров» (как бы вы ее не представили) является то, что она растет чрезвычайно быстро. Представить себе подобную функцию легко; даже простые функции, такие как n! или 2^n растут невероятно быстро даже для относительно небольших значений n, таких как 100. Но наша функция «усердных бобров» S(n) растет быстрее любой вычислимой функции. Т.е. подумайте о быстрорастущей функции, для которой вы можете написать программу для ее вычисления за конечное время; функция «усердных бобров» растет быстрее этой функции, не важно, насколько хитроумную быстрорастущую функцию вы бы ни придумали. Вы знаете, почему это так? У вас есть вся необходимая информация, чтобы ответить на этот вопрос. (****)

(*) Конечно, здесь нет ничего особенного в языке C#; это всего лишь язык общего назначения. Мы отталкиваемся от предположения, что если существует функция, которую невозможно вычислить на языке C#, то ее нельзя вычислить ни одной программой, ни на одном другом языке программирования.

(**) Конечно, нам не нужен переход из конечного состояния, ну да ладно. Давайте проигнорируем эту малозначительную деталь.

(***) Конечно, может существовать несколько одинаково длинных результатов, но это не имеет значения.

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

Russian MSDN — Mon, 03 Dec 2012 14:39:05 GMT

Я все пропустил! Я подготовился к огромной волне анонсов по поводу выхода языка 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) Прим. редактора. Под словом «вывод» имеется в виду логическая цепочка операций, выполняемая компилятором и приводящая к определению типа объекта.

Доступен сентябрьский выпуск Roslyn CTP

Russian MSDN — Wed, 21 Nov 2012 06:57:32 GMT

Я рад сообщить, что выпустили третий ознакомительный выпуск («Community Technology Preview») проекта Roslyn. Roslyn, если вы еще о нем не слышали, – это кодовое имя проекта, над которым я сейчас работаю; мы переписываем компиляторы языков C# и VB таким образом, чтобы они перестали быть «черными ящиками», на вход которых подается код, внутри происходит какая-то магия и на выходе получается IL-код. Теперь этот ящик будет стеклянным, и вы сможете использовать написанные нами лексический, синтаксический и семантический анализаторы в своих собственных целях.

Сейчас мы уже реализовали семантический анализатор большинства возможностей языков C# и VB. Для языка C# готовы практически все возможности C# 3.0; нам не хватает «динамических» возможностей C# 4 и асинхронных возможностей недавно выпущенного C# 5. Также мы внесли огромное количество изменений (надеюсь хороших) в API. Для получения полного списка обновлений, для доступа к QA-форуму по проекту Roslyn, а также для его загрузки, переходите на msdn.com/roslyn.

Мы с радостью выслушаем ваши пожелания на форуме или на сайте connect.microsoft.com/visualstudio о том, что вам нравится и что не нравится в этом API; вот почему мы выпускаем эти ознакомительные выпуски так часто. (Пожалуйста, оставляйте свои комментарии в специализированном форуме, а не в комментариях этого блога; у нас есть целая команда менеджеров программ, которые их читают.) Я надеюсь, вам понравится наш последний CTP так же, как нам понравилось его создавать.

Статический анализ оператора «is»

Russian MSDN — Fri, 09 Nov 2012 08:20:32 GMT

Прежде чем переходить к сегодняшнему невероятному приключению, я хотел бы поздравить всё подразделение разработки с потрясающим продуктом, который мы запускаем официально. (Я приложил очень мало усилий к разработке Visual Studio 2012 и языку C# 5.0, поскольку был очень занят проектом Roslyn). Асинхронные возможности в языках C# и VB являются моими любимыми; новых возможностей очень и очень много, чтобы все их здесь перечислять. Поэтому загляните на страничку запуска, и, пожалуйста, присылайте свои конструктивные пожелания о том, что вам нравится, и что – нет. Мы не сможем ответить на каждое письмо, но ваше мнение для нас очень важно.

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

Но прежде чем переходить к этому, давайте напомним смысл оператора «is» в языке C#. Выражение:

x is T

для выражения x и типа T дает результат типа bool. В общем случае, если существует ссылочное преобразование, или преобразование упаковки или распаковки значения времени исполнения переменной x к типу T, тогда результат равен true, в противном случае – false. Обратите внимание, что при этом пользовательские преобразования не учитываются. Оператор «is» предназначен для определения того, что значение времени исполнения x на самом деле является типом Т, (*) и, таким образом, нам нужно учесть следующее:

Т не может быть типом-указателем
x не может быть лямбда-выражением или анонимным методом
если x является группой методов (method group) или представляет собой null-литерал (**), тогда результат будет false
если во время исполнении x представляет собой ссылочный тип и ее значение равно null, то результатом будет false
если во время исполнения x представляет собой nullable-тип, свойство HasValue которого равно false, то результатом будет false
если во время исполнения x представляет собой nullable-тип, свойство HasValue которого равно true, тогда результат будет равен вычислению выражения x.Value is T

Теперь, зная об этом, попробуйте придумать ситуации, в которых вы точно знаете, что «x is T» всегда будет true, или false. Вот несколько примеров, результат выполнения которых всегда равен true:

int i = 123;
bool b1 = i is int;
bool b2 = i is IComparable;
bool b3 = i is object;
bool b4 = "hello" is string;

Здесь, в каждом случае мы точно знаем, что, во-первых, операнд не равен null, и, во-вторых, что операнд будет всегда определенного типа, и, таким образом, оператор «is» всегда будет возвращать «true».

Прежде чем продолжить, я хочу сделать еще одно отступление. Я хочу кратко напомнить о наших критериях, когда выдается предупреждение: предупреждение должно быть (1) продуманным, (2) простым в реализации, (3) находить код, который должен, во-первых, встречаться у реальных пользователей, и, во-вторых, наверняка быть ошибочным (но это должно быть неочевидным), (4) должен существовать обходной путь в том случае, если код действительно корректен и (5) не должен приводить к появлению в существующем коде огромного количества ложных ошибок.

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

Существует множество других случаев, когда вы точно знаете, что результатом всегда будет false. Сможете вспомнить несколько других вариантов? Вот несколько вариантов, что пришли мне в голову:

bool b5 = M is Func<object>; // M является группой методов (method group)
bool b6 = null is object;
bool b7 = b5 is IEnumerable;
bool b8 = E.Blah is uint; // E является типом-перечислением (enum type)
bool b9 = i is double;

Первые два примера следуют правилам из спецификации. Для последних трех случаев благодаря статическому анализу мы знаем, что значения не могут быть преобразованы с помощью ссылочного преобразования, или преобразований упаковки или распаковки. Компилятор выдает предупреждения для всех таких простых случаев. (Хотя, конечно же, некоторые из этих примеров – особенно 6-й – очень маловероятны в реальном коде).

Все это было длительной преамбулой к вопросу, который я бы хотел сегодня рассмотреть: «как далеко мы можем зайти» при выполнении подобного статического анализа с целью выдачи предупреждения, что выражение «is» всегда равно false. Мы можем зайти значительно дальше! Я начал эту серию постов с рассмотрения случая, когда преобразование во время компиляции между x и T отсутствует, но «x is T», тем не менее, возвращало true; сегодня же я хочу обсудить вариант, когда преобразование x к T отсутствует, и x is T не может быть равно true. Существует множество случаев, когда мы знаем, что определенное выражение точно не может быть некоторого типа, но эти случаи могут быть довольно сложными. Давайте рассмотрим три сложных примера:

class C<T> {}
...
static bool M10<X>(X x) where X : struct { return x is string; }
static bool M11<X>(C<X> cx) where X : struct { return cx is C<string>; }
static bool M12<X>(Dictionary<int, int> d) { return d is List<X>; }

В случае М10 мы знаем, что X – это значимый тип и не существует объекта значимого типа, который может быть преобразован к типу string с помощью ссылочного преобразования, или преобразования упаковки/распаковки. Проверка типа должна возвращать false.

В случае М11 мы знаем, что cx является типом C<некоторый-значимый-тип>, или типом, наследующем от C<некоторый-значимый-тип>. Мы знаем, что не существует варианта, когда один и тот же обобщенный тип будет входить в иерархию наследования дважды; невозможно, чтобы тип наследовал от двух типов: C<некоторый-значимый-тип> и C<string>. Так что проверка типа должна возвращать false.

В случае М12 мы знаем, что не существует способа создать объект, базовым классом которого будет и словарь и список, независимо от типа X. Проверка типа должна возвращать false.

Во всех этих случаях мы могли бы выдавать предупреждения, но мы очень быстро приходим к тому, что это будет противоречить одному из наших принципов: «возможности реализовать функциональность просто и дешево»! Я могу потратить ценное время для нахождения эвристик, которые не будут играть никакого толка для пользователей, которые пишут реальный код. Нам где-то нужно провести границу.

И где она находится? На самом деле, чтобы определить, выдавать предупреждение или нет, когда мы точно знаем, что не существует преобразования во время компиляции x к T, мы используем следующие принципы:

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

· Один из типов является открытым. Если тип времени компиляции переменной х является значимым типом и тип Т является ссылочным типом, тогда мы знаем, что результат всегда будет равен false. (***) (Это наш вариант М10). Выдаем предупреждение.

· В противном случае, мы прекращаем статический анализ и никаких предупреждений не выдаем.

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

(*) И не дает ответов на другие интересные вопросы, вроде «существует ли возможность связать значение типа Т с этим значением?» или «может ли значение х быть присвоенным переменной типа Т?»

(**) По этому поводу спецификация содержит определенные пробелы, что привело к некоторому рассогласованию поведения компилятора C# 5.0 и Roslyn. В спецификации ничего не говорится о том, что будет, если выражение х будет пространством имен или типом, которые, конечно же, являются корректными выражениями. Компилятор выдает ошибку, в которой говорится, что выражение должно содержать значение. Поведение аналогично для свойств и индексаторов только для чтения. Компилятор C# 5.0 выдает ошибку для выражений, возвращающих void, хотя это и является явным нарушением спецификации; Roslyn выдает предупреждение, хотя в этом случае я бы предпочел исправить спецификацию. В спецификации сказано, что «x is T» должно приводить к ошибке компиляции, если Т является статическим классом; компилятор C# 5.0 ошибочно выдает false, а Roslyn выдает ошибку компиляции.

(***) Это тоже неправда; существует один случай, когда тип времени компиляции выражения х является открытым значимым типом, и Т является значимым типом, и преобразование между х и Т отсутствует, и при этом «x is T» может быть равным true. В этом случае предупреждение выдаваться не должно. Можете ли вы придумать пример, демонстрирующий эту возможность?

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

Загадка с оператором «is». Часть 2

Russian MSDN — Thu, 08 Nov 2012 06:00:00 GMT

Как я и говорил в прошлый раз, это загадка была довольно простой: мы получим такое поведение, если FooBar или тип локальной переменной x будут параметром типа (type parameter). Т.е.:

void M<FooBar>()
{
int x = 0;
bool b = x is FooBar; // корректно, true если FooBar - это int.
FooBar fb = (FooBar)x; // не корректно
}

или

struct FooBar { /* ... */ }
void M<X>()
{
X x = default(X);
bool b = x is FooBar; // корректно, true если X - это FooBar
FooBar fb = (FooBar)x; // некорректно
}

Этот пример показывает не только интересный факт об операторе «is» (который заключается в том, что выражение «is» может давать true, даже когда соответствующее преобразование типов невозможно) но и интересный факт о преобразовании типов. Говоря в общем, преобразование типов разрешено, если во время компиляции известно, что такое преобразование успешно, либо может быть успешным. Но существуют случаи, когда преобразование может быть успешным, но оно запрещено. Почему так происходит? Мне в голову приходит два фактора, основанные на дуальной природе преобразований, о которой я когда-то упоминал: преобразование типов означает «я знаю, что значение точно этого типа, даже если компилятор этого не знает, поэтому компилятор должен его разрешить» и преобразование типов означает «я знаю, что значение точно не этого типа; сгенерируй специальный код для преобразования значения одного типа к значению другого типа».

Но ни один из этих вариантов не подходит при использовании параметров типа. Если рассматривать первое значение преобразования типов, то преобразование параметра типа к конкретному типу означает «я знаю, что параметр типа относится к определенному типу». Но, в таком случае, зачем вообще использовать обобщенные параметры типа? Это все равно, что передавать в функцию в качестве параметра целое число и утверждать, что его значение всегда будет равно 12. Зачем вообще нужно передавать что-то в качестве параметра, если вы заранее знаете, чему будет равен аргумент?

Если же рассматривать второе значение, то в обобщенном коде невозможно сгенерировать специальную логику преобразования. Давайте возьмем наш первый пример. Если FooBar – это double, то придется генерировать другой код для преобразования int к double, по сравнению с вариантом, когда FooBar будет представлять собой long. У нас нет простого и дешевого способа генерации такого кода, а если учесть пользовательские преобразования типов, то нам придется добавить процесс разрешения перегрузки методов во время исполнения. Мы добавили такую возможность в C# 4; если вы хотите генерировать код произвольного преобразования типов во время исполнения, то используйте dynamic.

В следующий раз: мы ответим на вопрос: «при каких условиях оператор “is” выдает предупреждения, что говорит о том, что вызов оператора “is” является избыточным?»

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

Загадка с оператором «is». Часть 1

Russian MSDN — Wed, 07 Nov 2012 06:00:00 GMT

Возможно, что в программе с некоторой локальной переменной x:

bool b = x is FooBar;

во время исполнения присваивается b значение true, даже если преобразование типов (явное или неявное) переменной x к FooBar запрещено компилятором! Т.е. выражение:

FooBar foobar = (FooBar)x;

в той же самой программе не будет компилироваться.

Можете ли вы придумать подобный пример? Это не слишком сложная загадка, но она показывает некоторые тонкие моменты оператора «is», которые мы рассмотрим в следующий раз.

Не смешивайте out-параметры и LINQ

Russian MSDN — Tue, 06 Nov 2012 10:26:04 GMT

Я вернулся из ежегодного отпуска, проведенного в прекрасном месте на юго-западе Онтарио; прежде чем переходить к теме сегодняшнего поста, посмотрите на снимок, сделанный с помощью Windows Phone при возвращении домой. Мы находимся на высоте 37000 футов сразу за городом Биллингс, штат Монтана, за несколько минут до захода солнца:

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

Итак, достаточно о погоде. Сегодня: что не так с этим кодом?

var seq = new List<string> { "1", "blah", "3" };
int tmp;
var nums =
from item in seq
let success = int.TryParse(item, out tmp)
select success ? tmp : 0;

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

При попытке скомпилировать этот код компилятор языка C# выдаст ошибку определенного присваивания (definite assignment error), что кажется весьма странным. Почему? Подумайте о том, во что данный код будет преобразован компилятором:

var nums =
seq.Select(item=>new {item, success = int.TryParse(item, out tmp)})
.Select(transparent => transparent.success ? tmp : 0);

У нас два вызова метода и два лямбда-выражения. Очевидно, что первое лямбда-выражение устанавливает значение tmp, а второе – его читает, но у нас нет никаких гарантий того, что первый вызов метода Select приведет к вызову первого лямбда-выражения! Вполне возможно, что по какой-то странной причине он никогда его не вызовет. А поскольку компилятор не может доказать, что переменная tmp будет гарантированно проинициализирована (definitely assigned) до ее чтения, то компиляция завершается с ошибкой.

Решит ли это проблему инициализация переменной tmp в месте объявления? Конечно, нет! Программа начнет компилироваться, но это «плохая практика» изменять подобные переменные. Помните, что одна переменная будет использоваться совместно всеми исполняемыми делегатами! В таком простом примере, использующем LINQ-to-Objects, делегаты вызываются в разумном порядке, но даже небольшое изменение кода приведет к нарушению этого допущения:

int tmp = 0;
var nums =
from item in seq
let success = int.TryParse(item, out tmp)
orderby item
select success ? tmp : 0;
foreach(var num in nums) { Console.WriteLine(num); }

А что будет теперь?

Мы создаем объект, представляющий собой запрос. Объект-запроса содержит три шага: выполнить проекцию “let”, выполнить сортировку и выполнить конечную проекцию. Помните, что запрос не исполняется до запроса на получение первого результата; присваивание переменной “nums” всего лишь создает объект, представляющий запрос, но не приводит к его исполнению.

Затем мы исполняем запрос в теле цикла. Это приводит к целой цепочке событий, но в этом случае нам явно нужно выполнить проекцию “let” целиком, чтобы затем отсортировать результирующую последовательность выражением “orderby”. Выполнение лямбда-выражения проекции “let” трижды приведет к тому, что переменная tmp будет изменена три раза. Только после сортировки будет выполнена последняя проекция, в которой будет использовано текущее значение переменной tmp, а не значение из далекого прошлого!

Так как же правильно поступить в этом случае? Решение заключается в написании собственного метода расширения TryParse так, как он должен был сразу же выглядеть при появлении значимых типов, допускающих null:

static int? MyTryParse(this string item)
{
    int tmp;
    bool success = int.TryParse(item, out tmp);
    return success ? (int?)tmp : (int?)null;
}

И теперь можно переписать наш пример так:

var nums =
from item in seq
select item.MyTryParse() ?? 0;

Изменение переменной теперь ограничено телом метода, а не побочным эффектом, который используется в запросе. Старайтесь всегда избегать побочных эффектов в запросах.

Спасибо Биллу Вагнеру (Bill Wagner) за вопрос, который инициировал это сообщение.

Должен ли C# выдавать предупреждения на использование пустых ссылок

Russian MSDN — Fri, 12 Oct 2012 07:43:29 GMT

Как вы наверное знаете, компилятор языка C# анализирует константы для поиска недостижимого кода. В следующем методе компилятор предупреждает о том, что вызов метода является недостижимым.

const object x = null;
void Foo()
{
if (x != null)
{
Console.WriteLine(x.GetHashCode());
}
}

Предположим, мы уберем “if” и оставим лишь вызов метода.

const object x = null;
void Foo()
{
Console.WriteLine(x.GetHashCode());
}

Компилятор не предупредит вас о разыменовывании нулевой ссылки! И очень часто задают вопрос, почему?

И, как обычно, ответ состоит в том, что нам не нужно никакого оправдания на то, почему мы не реализовали какую-то возможность. Разработка любой возможности требует средств, времени и усилий, а также забирает средства, время и усилия от других вещей, которые были бы более полезными для пользователя, так что любая новая возможность должна оцениваться с точки зрения отношения цена/качество. Давайте подумаем об этом с такой точки зрения.

При анализе некоторой новой возможности я задаю себе следующий вопрос «является ли эта возможность частным случаем более общей задачи?» По сути, предложенная возможность предназначена для определения того, что некоторое исключение всегда будет сгенерировано. Хотим ли мы определять ситуации, когда некоторое исключение будет сгенерировано в любом случае, и выдавать об этом предупреждение? Как мы уже обсуждали, полное решение этой проблемы означает решение Проблемы Остановки (Halting Problem). Но даже без этого, мы не хотим выдавать предупреждение каждый раз, когда точно знаем, что исключение должно быть сгенерировано; тогда следующий фрагмент кода будет приводить к предупреждению:

int M()
{
throw new NotImplementedException();
}

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

Итак, давайте подумаем о возможности определения разыменования константы null. А вообще, как часто такое происходит? Иногда я создаю константы, равные null; например, чтобы написать что-то типа: «if (symbol == InvalidSymbol)», где InvalidSymbol – это константа, равная null; это позволяет читать код, как будто он написан на естественном языке. И тогда, если кто-то случайно напишет «InvalidSymbol.Name», то компилятор выдаст предупреждение о попытке разыменовывания null.

Мы уже поднимали подобные вопросы. Более того, я создал список вопросов, которые я при этом себе задаю. Так что давайте пройдемся по нему.

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

Тогда может быть, мы можем обобщить эту возможность в каком-то другом виде? Возможно, компилятор мог бы анализировать любые разыменования нулевой ссылки, а не только разыменования констант. Полное решение этой задачи, опять-таки, сводится к решению проблемы остановки, что, как мы знаем, невозможно, но мы можем использовать некоторые умные эвристики для получения разумного результата.

На самом деле даже сейчас компилятор языка C# содержит некоторые такие эвристики; они используются для оптимизации арифметических операций над nullable-типами. Если во время компиляции мы знаем, что результатом выражения всегда будет null, то компилятор генерирует более эффективный код. (Как мы это делаем, является отличной темой для будущих статей.) Однако текущие эвристики являются чрезвычайно «локальными»; например, не анализируется вариант, когда локальной переменной присваивается null, а потом она используется до переприсваивания. Так что, опять-таки, количество мест, где генерируется такое предупреждение, будет небольшим, возможно, совсем небольшим.

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

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

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

Кроме того, вы могли заметить, что такие инструменты, как Code Contracts (выпускаемый с .NET 4), ReSharper и другие аналогичные инструменты содержат возможности статического анализа для определения возможного или гарантированного доступа к нулевым ссылкам. Это еще раз доказывает, что эта возможность реализуема. Но это также говорит против добавления такого предупреждения в компилятор. Как я уже писал, если уже есть инструмент, отлично делающий некоторую работу, то зачем дублировать ее в компиляторе? Компилятор не должен быть единственным и всезнающим инструментом анализа кода; на самом деле, мы создаем Roslyn именно для того, чтобы другие компании могли разрабатывать подобные инструменты. Мы не можем реализовать все полезные возможности для анализа кода, но мы можем сделать эту работу легче для кого-то другого!

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

Когда преобразование типов им не является?

Russian MSDN — Mon, 03 Sep 2012 07:40:57 GMT

Мне очень часто задают вопрос о логике преобразования типов в языке C#, что, в общем-то, не удивительно. Преобразования типов является распространенной операцией и соответствующие правила довольно запутанные. Вот фрагмент кода, о котором у меня недавно спросили; я упростил его ради ясности:

class C<T> {}
class D
{
  public static C<U> M<U>(C<bool> c)
  {
    return something;
  }
}
public static class X
{
  public static V Cast<V>(object obj) { return (V)obj; }
}

Где «something» может представлять собой один из трех вариантов:

Вариант 1: (C)c

Вариант 2: X.Cast<C>(c);

Вариант 3: (C)(object)c

Первый вариант не компилируется. Второй и третий варианты успешно компилируются но «падают» во время выполнения, если U не является типом bool.

Вопрос: Почему первый вариант не компилируется?

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

Вопрос: Так почему тогда вторая версия компилируется?

Потому что компилятор не знает, что метод X.Cast<V> собирается преобразовывать аргумент к типу V! Все что видит компилятор, так это вызов метода, принимающего объект (и вы передаете объект), работа компилятора на этом заканчивается. С точки зрения компилятора вызов метода является «черным ящиком», и компилятор не заглядывает внутрь метода, чтобы определить, завершится ли неудачно этот метод при заданных входных данных. Это «преобразование» с точки зрения компилятора не является преобразованием, это просто вызов метода.

Вопрос: А как насчет третьего варианта? Почему он компилируется, в отличие от первого варианта?

На самом деле, третий вариант аналогичен второму; все, что мы делаем, это встраиваем вызов метода X.Cast<V>, добавляя при этом преобразование к типу object! Такое преобразование является корректным.

Вопрос: во втором и третьем случае, преобразование компилируется, поскольку в середине происходит конвертация к типу object?

Совершенно верно. Правило следующее: если существует преобразование типа S к объекту, тогда существует явное преобразование объекта к типу S. (*)

Преобразование к объекту перед «агрессивным» преобразованием говорит компилятору «забудь, пожалуйста, информацию времени компиляцию о типе преобразуемого объекта». В третьем варианте мы делаем это явно; во втором варианте мы делаем это скрытно, путем неявного преобразования к объекту передаваемого аргумента во время его преобразования к типу параметра.

Вопрос: это объясняет, почему проверка типов времени компиляции нормально не работает с LINQ выражениями?

Да! Можно подумать, что компилятор запретит глупости, типа:

from bool b in new int[] { 123, 345 } select b.ToString();

поскольку не существует преобразования из int к bool, так как же переменная диапазона b может принимать значения массива? Тем не менее, данный код компилируется, поскольку компилятор преобразует этот код к:

(new int[] { 123, 345 }).Cast<bool>().Select(b=>b.ToString())

и компилятор не имеет ни малейшего понятия о том, что последовательность целых чисел передается методу расширения Cast<bool>, который завершится с ошибкой во время выполнения. Этот метод является черным ящиком. Мы с вами знаем, что будет преобразование типов, которое завершится с ошибкой, но компилятор не знает этого.

Кстати, далеко не факт, что мы с вами тоже об этом знаем; возможно, мы используем некоторую библиотеку, отличную от поставщика запросов (query provider) LINQ-to-objects, который знает о возможности преобразования между типами, обычно запрещенными компилятором языка C#. На самом деле, это точка расширения языка, которая прячется за недостатком компилятора: так что это фича, а не баг!

(*) Обратите внимание, что я не сказал: «существует явное преобразование объекта к любому типу», потому что это не так. Можете ли вы назвать тип S, который не преобразовывается к объекту?

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

Лучший совет, который мне когда-либо давали

Russian MSDN — Tue, 28 Aug 2012 14:06:00 GMT

Сейчас всего лишь небольшая ссылка:

Прекраснейшие люди из InformIT (*) выпускают серию коротких статей по теме «лучший совет, который мне когда-либо давали», что, как мне кажется, должно быть очень интересными. Они попросили у меня пример совета, который мне давали, который помог в моей карьере программиста , хотя, как вы увидите, он на самом деле вообще не связан с программированием.

(*) Как вы возможно помните, я недавно давал совет о хороших книгах для C# разработчиков. Ради полного понимания я должен заметить, что в свободное время я занимаюсь редактированием и написанием книг о языке C# для издательства Addison-Wesley, у которой тот же владелец, что и у ресурса InformIT.

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

Глупая последовательность глупа

Russian MSDN — Tue, 28 Aug 2012 09:12:47 GMT

Сегодняшний пост как обычно будет представлен в виде диалога.

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

Это хороший вопрос, но нельзя ли немного конкретики? Для начала стоит перечислить случаи, когда неявно типизированная локальная переменная должна, а иногда не должна использовать var.

Конечно. Неявно типизированная локальная переменная должна объявляться с var в следующих случаях:

var x1 = whatever;
for(var x2 = whatever; ;) {}
using(var x3 = whatever) {}
foreach(var x4 in whatever) {}

И неявно типизированная локальная переменная не должна объявляться с var в следующих случаях:

from c in customers select c.Name
customers.Select(c => c.Name)

В обоих случаях добавить var перед переменной «c» нельзя, хотя можно использовать тип явно:

from Customer c in customers select c.Name
customers.Select((Customer c) => c.Name)

Почему?

Можно, прежде чем отвечать на ваш вопрос, я еще немного его покритикую. Действительно ли в лямбда-выражении и в выражении запроса (query expression) используются неявно типизированные переменные?

Хм... Вы правы; технически, ни в одном из этих случаях нет локальных переменных. В случае лямбда-выражения используется формальный параметр. Но формальный параметр ведет себя практически аналогично локальной переменной, так что мы можем рассматривать ее как локальную переменную. В выражении запроса компилятор преобразует переменную диапазона (range variable) в формальный параметр лямбда-выражения без типа независимо от того, является ли переменная диапазона типизированной или нет.

Не могли бы вы подробнее остановиться на последнем замечании?

Конечно. Когда мы пишем:

from Customer c in customers select c.Name

компилятор преобразовывает это выражение в:

customers.Select((Customer c) => c.Name)

Более того, он скорее преобразовывает его в:

customers.Cast<Customer>().Select(c => c.Name)

Совершенно верно. Обсуждение того, почему этот вариант может быть предпочтительнее, оставим для другого раза.

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

Теперь, когда мы прояснили ваш вопрос, давайте выясним, в чем же он заключается?

Язык C# непоследователен; var требуется для неявно типизированных локальных переменных (независимо от места объявления), но var нельзя использовать для неявно типизированных параметров лямбда-выражения (независимо от того, является ли параметр «настоящим» или же он является результатом преобразования выражения запроса). Почему?

Вы продолжаете спрашивать «Почему?», потому что он, на самом деле, является завуалированной версией вопроса «А почему не по-другому?». Т.е. на самом деле вы имеете в виду, «У меня есть представление о дизайне языков программирования; почему ваш дизайн ему не соответствует?» Но поскольку я не знаю вашего представления о дизайне языков программирования, мне тяжело сравнивать все «за» и «против» этой возможности, реализацию которой вы считаете непоследовательной.

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

Я вижу три пути. Первое, ради согласованности сделать var требуемым в лямбда-выражениях и выражениях запроса. Второе, убрать использование var для всех локальных переменных, сделав эту возможность некорректной. И третье, сделав ее везде необязательной. Так в чем же заключается ваш вопрос «А почему не так?»

Вы правы; я обратил внимание на рассогласованность поведения, но я ничего не сказал о том, как от нее избавиться. Я не знаю, как бы звучал мой вопрос «А почему не по-другому?», так что давайте рассмотрим все варианты; какие есть «за» и «против»?

Давайте рассмотрим первый вариант: var требуется везде. Это означает, что вам придется писать так:

from var c in customers join var o in orders...

А не так:

from c in customers join o in orders...

И придется писать так:

customers.Select((var c) => c.Name)

А не так:

customers.Select(c => c.Name)

Выглядит неуклюже. Что нам дает использование здесь var? Это не повышает читабельности; на самом деле, код становится даже менее читабельным. Мы платим слишком большую цену за согласованность. Первый вариант кажется неподходящим.

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

x1 = whatever;
for(x2 = whatever; ;) {}
using(x3 = whatever) 
{}
foreach(x4 in whatever) {}

С последним фрагментом нет никаких проблем; мы знаем, что переменные, объявленные в цикле foreach, всегда приводят к появлению новой переменной. Во всех остальных случаях мы добавляем новую возможность в язык программирования; теперь у нас появляются не просто неявно типизированные локальные переменные, но и неявно объявленные локальные переменные. Теперь, для объявления новой локальной переменной достаточно присвоить значение новому идентификатору.

Существует множество языков программирования, поддерживающие неявное объявление локальных переменных, но эта возможность кажется совершенно не «сишарпной». Подобные возможности поддерживаются языками, типа VB и VBScript, и даже там вы должны включить эту возможность явно в настройках с помощью опции Explicit. Цена за согласованность сильно отличается от первого случая, но она все равно очень высока. Я не думаю, что мы готовы так дорого за нее платить.

Третий вариант, везде сделать var необязательным, является всего лишь разновидностью второго варианта; опять-таки, это приведет к неявному объявлению локальных переменных.

Проектирование – это искусство нахождения компромисса среди множества противоречивых требований. В данном случае, согласованность – это цель, уступающая под напором более практичных вопросов. Это глупая согласованность.

А не является ли эта рассогласованность показателем более глубоких проблем в дизайне языка?

Да. При рассмотрении трех вариантов решения рассогласованности, я упомянул, что сделал определенные допущения по поводу того, что можно изменять, а что нет. Если бы мы могли сделать более масштабные изменения или мы бы приняли другие решения при разработке C# 1.0, то у нас не было бы таких проблем вовсе. Более глубокая проблема языка связана с тем, что объявление локальной переменной выглядит так:

type identifier ;

Это, прежде всего, далеко не идеальный синтаксис выражений. Вместо этого, давайте предположим, что синтаксис объявления локальной переменной в C# 1.0 был бы таким:

var identifier : type ;

Я понял, куда вы ведете; в JScript.NET используется этот синтаксис, и делает указание типа необязательным. И Visual Basic, конечно же, использует аналогичный синтаксис, только вместо var используется DIM, а вместо двоеточия используется «As».

Совершенно верно. Таким образом, в C# 1.0 при обязательном указании типа синтаксис был бы следующим:

var x1 : int = whatever;
for(var x2 : int = whatever; ;) {}
using(var x3 : 
IDisposable = whatever) {}
foreach(var x4 : int in whatever) {}

Да, это более многословный синтаксис. Но его значительно проще анализировать, как компилятору, так и человеку, и, скорее всего, он более очевиден для новичка. Абсолютно ясно, что в этом выражении объявляется новая локальная переменная. Кроме того, это очень напоминает объявление базового класса, что логически является аналогичным объявлением. (Вы могли бы задать и такой вопрос: «Почему ограничение типа располагается слева от идентификатора в локальных переменных, параметрах, полях, свойствах, событиях, методах и индексаторах, но справа от идентификатора класса, структуры, интерфейса и типа параметра?» Непоследовательность повсюду!)

В таком случае, мы добавили бы неявно типизированные переменные в язык C# 3.0, просто сделав аннотацию типа необязательной, позволив, таким образом, все следующие операторы и выражения:


var x1 = whatever;
for(var x2 = whatever; ;) {}
using(var 
x3 = whatever) {}
foreach(var x4 in whatever) {}
from c in customers select c.Name
from c : Customer in customers select 
c.Name
customers.Select(c => c.Name)
customers.Select((c : Customer) 
=> c.Name)

Так если этот синтаксис лучше, то почему вы им не воспользовались в C# 1.0?

Поскольку мы хотели создать привычный язык для программистов С и С++. Так что мы получили одну форму согласованности – согласованность опыта С-программистов, что через десять лет привело к проблемам согласованности самого языка C#.

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

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

Эрик снова рассуждает о языке C#

Russian MSDN — Tue, 28 Aug 2012 05:00:00 GMT

Рейчел Румелиотис (Rachel Roumeliotis), которая, помимо прочего является редактором книг о C# в издательстве O’Reilly, взяла у меня недавно интервью, в котором я рассказываю о async/await, проекте Roslyn, анализе производительности как об инженерной дисциплине, и некоторых идеях в исследовании языков программирования в будущем. Если у вас есть лишние 16 минут, то обязательно посмотрите! Запись в блоге O’Reilly Radar здесь, а также видео было опубликовано в YouTube здесь.

Еще пара моментов; первое, я упоминаю о том, что мы выпустили один ознакомительный релиз проекта Roslyn; на самом деле мы выпустили два. Видео было записано до объявления второго релиза. И второе, я хочу подчеркнуть, что заключительный аккорд моего выступления, в котором говорю об областях исследования языков программирования, появился исключительно ради развлечения. Мы не анонсировали никаких продуктов, которые будут выпущены после завершения проекта Roslyn, и мы точно не даем никаких обещаний относительно не анонсированных возможностей потенциальных продуктов. Наслаждайтесь!

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

Поведение, определяемое реализацией

Russian MSDN — Mon, 27 Aug 2012 12:17:27 GMT

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

Обычно мы говорим, что некоторая идиома языка программирования обладает неопределенным поведением, если ее использование может привести к чему угодно; она может вести себя ожидаемым образом, или может отформатировать вам жесткий диск или привести к аварийному завершению работы компьютера. Более того, разработчики компилятора даже не обязаны предупреждать вас о неопределенном поведении. (На самом деле, существуют языки программирования, в спецификации которых сказано, что использование «неопределенного поведения» в программе должно приводить к аварийному завершению работы компилятора!)

Примером неопределенного поведения в языках С, С++ и C# является запись в разыменованный указатель, в который писать не следует. Подобное действие может привести к аварийному завершению работы процесса. Но состояние памяти может быть и корректным, и это может быть важной структурой данных выполняемого приложения. Вы можете затереть существующий код другим кодом с совершенно другим поведением. Поэтому произойти может все что угодно; вы превращаете свое приложение, в приложение, делающее что-то совершенно иное.

В отличие от этого, поведение, определяемое реализацией (implementation-defined behavior) заключается в том, что у авторов компилятора есть несколько вариантов реализации некоторой возможности, и они должны выбрать один из них. Как подсказывает название, поведение, определяемое реализацией, по крайней мере, является определенным. Например, при делении на нуль спецификация языка C# позволяет генерировать исключение или возвращать некоторое значение, но авторы компилятора должны выбрать один этих вариантов. Вы можете не бояться за то, что при этом ваш жесткий диск будет отформатирован.

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

Какие причины вынуждают комитет разработчиков языка допускать для идиом языка программирования неопределенное поведение или поведение, определяемое реализацией?

Первая причина заключается в следующем: существуют ли на рынке две реализации языка программирования, которые расходятся относительно поведения конкретной программы? Если компилятор компании FooCorp компилирует «M(A(),B())» как «вызов A, вызов B, вызов M», а компилятор компании BarCorp компилирует в «вызов B, вызов A, вызов M» и ни одно из поведений не является «очевидно правильным», то существует хороший повод для комитета проектирования языка сказать «обе реализации корректны» и сделать это поведение, определяемым реализацией. Это особенно часто бывает, когда обе компании, FooCorp и BarCorp имеют в комитете своих представителей.

Вторая причина: предоставляет ли эта возможность естественное множество разных реализаций, некоторые из которых явно лучше других? Например, анализ компилятором языка C# выражения запроса (query comprehension) звучит так: «выполнить синтаксическое преобразование в эквивалентную программу, не содержащую выражения запроса, а затем выполнить ее анализ обычным образом». В данном случае существует минимум свободы у разработчика компилятора поступить как-то иначе. Например, все мы знаем, что два запроса:

from c in customers
from o in orders
where c.Id == o.CustomerId
select new {c, o}

from c in customers
join o in orders on c.Id equals o.CustomerId
select new {c, o}

семантически эквивалентны, и второй вариант, скорее всего более эффективен. Но компилятор языка C# ни в коем случае не преобразует первый вариант в вызов метода Join; он всегда преобразует его к вызову методов SelectMany и Where. Среда исполнения, конечно же, имеет полное право определить, что объект, возвращенный методом SelectMany, передается методу Where, и в случае необходимости оптимизировать его до join-а, но компилятор языка C# никогда не сделает подобного предположения. В случае использования первого варианта всегда будет вызван метод SelectMany и никогда не будет вызван метод Join. Мы хотели, чтобы преобразование выражений запросов было исключительно синтаксическим; хитрые оптимизации мы оставили среде исполнения.

В отличие от этого, спецификация языка C# говорит, что цикл foreach должен рассматриваться как эквивалентный цикл while внутри блока try, но дает реализации определенную гибкость. Компилятор языка C#, например, может сказать: «я знаю, как реализовать для массива цикл более эффективно» и использовать индексатор массива, а не преобразовывать массив к последовательности, как рекомендует спецификация. Реализация языка C# может опустить вызов метода GetEnumerator.

Третья причина: является ли возможность настолько сложной, что детальное описание точного поведения является сложным или слишком дорогим? В спецификации C# очень мало говорится о реализации анонимных методов, лямбда-выражений, деревьев выражений, динамических вызовах (dynamic calls), блоках итераторов или асинхронных блоках; в ней всего лишь дается описание желаемой семантики и некоторые ограничения поведения, оставляя все остальное на долю реализации. Разные реализации могут генерировать разный код, обеспечивая при этом желаемое поведение.

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

Func<int, int> f1 = (int x)=>x + 1;
Func<int, int> f2 = (int x)=>x + 1;
bool b = object.ReferenceEquals(f1, f2);

Предположим, мы бы требовали, чтобы b равнялась true. Как вы собираетесь определять «эквивалентность» двух функций? Анализировать «содержимое» (выполняет ли содержимое функций одно и то же?), или выполнять анализ «поведения» (приводит ли выполнение двух функций к одному результату при одних и тех же входных данных?) – еще сложнее. Комитет разработки языка программирования должен минимизировать количество открытых проблем, которые необходимо решить разработчикам компилятора! Поэтому данное поведение оставлено на усмотрение реализации; компилятор может вернуть одинаковые ссылки или нет, на свое усмотрение.

Пятая причина: накладывает ли возможность слишком большой груз на среду выполнения?

Например, поведение при разыменовывании указателя, который указывает за последний элемент массива, четко определено; это приводит к генерации соответствующего исключения. Эта возможность может быть реализована с небольшими (но не нулевыми) затратами во время выполнения. Вызов экземплярного или виртуального метода на пустом (null) объекте приводит к генерации исключения; опять-таки, эта возможность может быть реализована с небольшими, но не нулевыми затратами. Мы избавляемся от неопределенного поведения небольшой ценой времени выполнения. Но определение, что разыменовывание произвольного указателя в небезопасном (unsafe) коде допустимо, требует значительных затрат времени выполнения, поэтому мы этого не делаем; мы перемещаем груз ответственности за это на разработчика, который, прежде всего, сам отключил безопасную систему типов.

Шестая причина: препятствует ли четкое определение поведения выполнению серьезных оптимизаций. Например, язык C# определяет порядок побочных эффектов, наблюдаемых из потока, вызвавшего эти побочные эффекты. Однако поведение программы, когда побочные эффекты одного потока наблюдаются из другого потока, определяется реализацией всегда, кроме нескольких «специальных» случаев. (Как volatile-запись или вход в блок lock.) Если бы язык C# требовал, чтобы все потоки наблюдали одни и те же побочные эффекты в одинаковом порядке, то это ограничило бы эффективность работы современных процессоров; современные процессоры для достижения высокой эффективности строятся на основе исполнения с изменением последовательности команд (out-of-order execution) и сложными стратегиями кэширования.

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

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

Персистентность, фасады и красно-зеленые деревья в Roslyn

Russian MSDN — Sun, 26 Aug 2012 12:36:49 GMT

На ранних стадиях дизайна проекта Roslyn мы решили, что основной структурой данной, с которой будут иметь дело разработчики при анализе кода, будет синтаксическое дерево (syntax tree). Таким образом, одной из самых сложных задач на ранних стадиях дизайна было определение того, как мы будем реализовывать узлы синтаксического дерева, и какую информацию они будут предлагать пользователю. Мы хотели получить структуру данных со следующими характеристиками:

Неизменяемость.
Древовидное представление.
Простой доступ к родительским узлам из дочерних.
Возможность получения соответствия между узлом дерева и смещением символа в тексте.
Персистентность (persistent).

Под персистентностью (persistence) я понимаю возможность повторного использования большей части существующих узлов дерева при редактировании текста в текстовом буфере. Как мы много раз обсуждали, поскольку узлы являются неизменяемыми, то ничто не мешает использовать их повторно. Нам нужно это для обеспечения высокой производительности; мы не можем повторно анализировать огромные куски текста каждый раз при нажатии на кнопку. Нам нужно выполнить повторный разбор и лексический анализ только тех участков дерева, которые подверглись изменениям во время редактирования (*), поскольку мы обычно выполняем эту операцию между всеми нажатиями клавиш.

Когда вы попытаетесь собрать все пять вышеописанных характеристик в одну структуру данных, вы сразу же столкнетесь с проблемами:

Как вы вообще собираетесь создавать узлы дерева? Родительский и дочерний узлы ссылаются друг на друга и неизменяемы, какой из них нужно создавать первым?
Предположим, вы решили эту задачу: как вы обеспечите персистентность? Вы не можете повторно использовать дочерний узел с другим родительским узлом, поскольку вам придется сказать ему, что у него теперь новый родительский узел. Но дочерний узел является неизменяемым.
Предположим, вы смогли решить и эту задачу: при добавлении нового символа в редактируемый буфер, абсолютная позиция каждого узла, соответствующего некоторой позиции, после данного символа изменяется. Это сильно усложняет создание персистентной структуры данных, поскольку любое изменение может изменить значение большинства узлов!

Но в команде Roslyn мы постоянно делает невозможные вещи. На самом деле, мы сделали невозможное, храня два разобранных дерева. «Зеленое» дерево является неизменяемым, персистентным, не содержит ссылки на родительский узел, построено «снизу вверх» и каждый узел отслеживает ширину, а не абсолютное положение. При редактировании мы перестраиваем только часть зеленого дерева, измененного во время редактирования, что обычно занимает порядка O(log n) времени разбора узлов всего дерева.

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

Вы, как пользователь Roslyn API видите только красное дерево, а зеленое дерево является лишь деталью реализации. (И если вы посмотрите в отладчике на внутреннее состояние разобранного узла, то на самом деле вы увидите ссылку на другой разобранный узел другого типа; это узел зеленого дерева.)

Эти деревья названы «красно/зелеными» чисто случайно, поскольку маркеры именно такого цвета мы использовали для рисования структур данных во время встреч по дизайну. Никакого другого значения в этих цветах нет.

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

(*) Определение того, к каким частям дерева это относится, является довольно сложной темой; возможно, я напишу об этом позже. Например, если вы добавляете к объявлению метода ключевое слово «async», то это может привести к тому, что анализ «await(foo);» в теле метода изменится, и вместо вызова метода будет использоваться контекстное ключевое слово await.

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

Анонсируем Microsoft Roslyn June 2012 CTP

Russian MSDN — Sat, 25 Aug 2012 05:00:00 GMT

Внимание всем, я рад сообщить, что мы выпускаем вторую предварительную версию проекта Roslyn, проекта, над которым я сейчас работаю. Я невероятно рад этому!

Переходим к делу. Ключевые моменты:

Roslyn – это библиотека для анализа кода, полезная для создания компиляторов, сред разработки, механизмов рефакторинга и т. д. Она поддерживает лексический, грамматический и семантический анализы языков C# и Visual Basic. И она прекрасна.
Эта версия CTP работает в Visual Studio 2012 Release Candidate, которая совсем недавно стала доступной для скачивания.
Механизм семантического анализа языка C# теперь поддерживает большинство, хотя и не все, языковые возможности. В частности, сейчас уже поддерживаются выражения запросов, анонимные типы, анонимные функции и блоки итераторов. Самыми крупными пока нереализованными возможностями являются dynamic из C# 4 и «await» из C# 5. Арифметика над nullable-типами в основном работает, хотя генерируемый код не является оптимальным; у меня пока не было возможности заняться этим.
Мы хотим получить от вас обратную связь по поводу дизайна API и связанных с этим возможностей, таким как Interactive Window. Пожалуйста, оставляйте свои комментарии в форуме проекта Roslyn, а не в этом блоге. У нас отличная команда менеджеров, которые собирают обратную связь из форумов и используют ее, чтобы помочь нам сделать API максимально удобным для всех вас. Мы, конечно же, примем все отчеты об ошибках, но мы, прежде всего, ожидаем услышать конструктивную критику нашего API.

Более детальный обзор релиза смотрите в блоге Джейсона. Вы можете найти подробную информацию и скачать CTP с msdn.com/roslyn.

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

Прошлая эффективность не гарантирует будущих результатов

Russian MSDN — Fri, 24 Aug 2012 16:05:22 GMT

Прежде чем перейти к сути нашего сегодняшнего повествования, несколько замечаний. Во-первых, я извиняюсь за отсутствие новых постов в последние три недели; я был невероятно занят добавлением новых возможностей в семантический анализатор языка C# проекта Roslyn. Подробности об этом в следующем посте. Во-вторых, обратите внимание на страничку с блогами, посвященную инструментам разработки (Developer Tools blog aggregation page – En.); это отличная стартовая точка для получения массы полезной информации, и большая часть из нее фиолетовая. Доказательство! (En.)

Хорошо, раз мы расправились с метаинформацией о блогах, переходим к вопросу, который мне недавно задали:

При компиляции дважды одной и той же программы на языке C#, будет ли получен один и тот же двоичный результат?

Нет.

Ну, это был очень простой пост. Хотя некоторые дополнительные сведения наверняка будут полезны.

А почему?

Ну, по своей сути, язык – это не что иное, как набор строк (возможно бесконечный) (*); строка является корректной программой, если она входит в этот набор, в противном случае – программа не корректна. Компилятор – это программа, которая принимает строку, определяет, является ли она корректной с точки зрения некоторого языка, и если она корректна, то выдает эквивалентную (**) корректную строку на другом языке. Например, компилятор языка C# принимает входную строку, которая хранится в файле “.cs” и выдает на выходе программу, написанную на языке MSIL. Конечно существует масса деталей; компилятор языка C# генерирует MSIL в «переносимом исполняемом» (portable executable) формате, а не в формате, предназначенном для человека. И компилятор языка C# также принимает на вход программы в двоичном формате в виде дополнительных сборок. Но на базовом уровне, компилятор языка C# делает для вас следующее: принимает код, написанный на языке C#, анализирует его корректность и генерирует эквивалентную программу в PE (Portable Executable) формате.

Любая программа на языке C# имеет множество эквивалентных программ на языке MSIL; самым простым примером может служить добавление любого количества nop-инструкций (“no operation”) в любом месте программы. Глупым примером можем служить добавление любого проверяемого кода по любому недостижимому пути исполнения! Более интересным примером является очень частая ситуация, когда компилятор должен «создавать» уникальные имена для таких конструкций, как анонимные методы, анонимные типы, поля классов-замыканий (closure classes) и т.п. Давайте рассмотрим эти уникальные имена более подробно.

Когда компилятору для чего-то нужно создать уникальное имя, то его базовой стратегией является создание шаблона имени, которое не при каких условиях не может быть корректным, поскольку содержит символы, корректные для идентификаторов в языке MSIL, но некорректные с точки зрения языка C#. Затем в этот шаблон вставляются дополнительные строки, например имя текущего метода, после чего в конец имени добавляется числовое значение. Точный шаблон имени я описал в одном из ответов на StackOverflow; обратите внимание, что это деталь реализации компилятора, и мы думаем изменить его в будущем. (Некоторые люди жалуются, что имена слишком длинные и занимают слишком много места в таблицах метаданных; мы можем сделать их значительно короче). Основная мысль заключается в том, что уникальность гарантируется путем увеличения счетчика, с помощью которого гарантировать такую уникальность довольно просто. С практической точки зрения мы едва ли столкнемся с неуникальностью идентификаторов; их уникальность должна быть обеспечена только в пределах одной сборки и ни одна сборка не будет содержать более двух миллиардов идентификаторов, сгенерированных компилятором.

Это означает, что реальное значение идентификаторов, сгенерированных компилятором, определяется порядком анализа конкретного фрагмента кода, во время которого требуется генерация уникального идентификатора. Мы не даем никаких гарантий относительно того, что этот порядок детерминирован. Исторически, он был практически детерминирован; раньше анализатор компилятора C# был однопоточным, и, при анализе дважды одного и того же списка файлов, анализ файлов происходил в одном и том же порядке, и все типы �� программе анализировались тоже в одном порядке (***). Но обратите внимание на следующие допущения:

Во-первых, мы предполагаем, что каждый раз мы будем анализировать один и тот же список файлов в одном и том же порядке. Но в некоторых случаях этим занимается операционная система. Когда вы пишите: “csc *.cs”, порядок, в котором операционная система возвращает результирующий список файлов, является деталью реализации операционной системы; компилятор не сортирует этот список.

Во-вторых, мы предполагаем, что анализатор компилятора является однопоточным; не существует требования к тому, чтобы он был однопоточным, и, на самом деле, мы уже пробовали сделать его многопоточным в прошлом и, скорее всего, попробуем это сделать еще раз. Анализ больших программ является отличным примером задач «чрезвычайного параллелизма» (embarrassingly parallel). Как только структура программы (все типы, методы, поля и т.д.) становятся известными, тогда тело каждого метода может анализироваться параллельно; содержимое тела одного метода никак не влияет на анализ тела другого метода. Но как только компилятор станет многопоточным, ни о каком детерминированном порядке анализа файлов речи уже быть не может, а значит мы не cможем гарантировать того, что две разные компиляции приведут к генерации одних и тех же идентификаторов.

Да, все это очень интересно, вот почему я пишу обо всем об этом. Я мог бы перейти сразу к сути: компилятор языка C# по определению никогда не выдает один и тот же результат дважды. Компилятор языка C# в каждую сборку после ее компиляции вставляет вновь сгенерированный GUID, гарантируя тем самым неидентичность двух сборок. Вот цитата из спецификации CLI:

Колонка Mvid должна указывать на уникальный GUID […], идентифицирующий экземпляр данного модуля. […] Mvid должен генерироваться каждый раз для каждого модуля […] Хотя сама среда исполнения не использует Mvid, другие инструменты (такие как отладчики […]) используют тот факт, что Mvid практически всегда являются уникальными.

Вот так вот; спецификация среды исполнения требует, чтобы каждый модуль (сборка содержит один или более модулей) содержал уникальный идентификатор.

Более того: давайте не забывать о том, что IL-код не является исполняемым; еще один компилятор преобразует IL-код в машинный код. JIT-компилятор тоже не гарантирует того, что компиляция одного и того же кода дважды приведет к одинаковому машинному коду; JIT-компилятор может использовать всю доступную информацию во время исполнения для оптимизации генерируемого кода по размеру, скорости, для упрощения отладки и т.п., как ему захочется.

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

У первого пользователя, который задал мне вопрос о детерминированности компиляции, был очень интересный сценарий. Этот пользователь работал в отрасли, где код проверяется правительственными органами. Правительство хотело получить от него исходный код и результирующий исполняемый файл, который будет загружаться в процессор. Инспекторы хотели провести обзор безопасности исходного кода, прежде чем разрешить использование устройств с данными процессорами. Конечно же, очевидной атакой ненадежного поставщика является рассогласование исходного кода с результирующим двоичным результатом; исходный код надежен, а двоичный код – враждебен.

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

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

Я так понимаю, что мой совет проигнорировали и остановились на сравнении разницы двоичного кода, проверяя, что отличия заключаются лишь в колонке Mvid, упомянутой ранее. Конечно же, я предостерег их, что они используют недокументированную и абсолютно не сопровождаемую возможность компилятора. Мы не даем никаких гарантий относительно того, что это поведение компилятора не изменится. Или в более общем случае: компилятор языка C# не предназначен для работы в качестве компонента системы безопасности, так что не нужно его использовать таким образом.

(*) И строка, конечно же, является конечной, упорядоченной последовательностью символов некоторого алфавита.

(**) Что именно делает программу на одном языке «эквивалентной» программе на другом языке является другим вопросом, который мы сейчас полностью проигнорируем.

(***) Подробности довольно интересны; по сути, мы анализируем файл один за другим, создавая дерево «высокоуровневых» элементов: пространств имен, типов, методов и т.п. Получив это дерево, мы итерируем по нему, получая, таким образом, частичную упорядоченность. Наша цель – искать элементы в определенном порядке (если он существует), который гарантирует, что механизм генерации метаданных никогда не будет генерировать метаданные в «неверном» порядке; мы хотим, чтобы метаданные базового типа генерировались до метаданных производного, и чтобы метаданные внешнего класса генерировались до метаданных внутреннего класса. Существует код, для которого эти требования невыполнимы; в этом случае производительность генератора метаданных существенно снижается. Так что у нас есть законный интерес гарантировать, что мы нашли правильный порядок перебора всех типов в программе.

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

Руководство по GUID. Часть 3

Russian MSDN — Tue, 07 Aug 2012 05:57:03 GMT

Давайте напомним, о чем шла речь: GUID – это 128-разрядное целое, который используется в качестве глобального уникального идентификатора. Система генерации GUID не является безопасной; при наличии злоумышленника, намеренно создающего коллизии, уникальность GUID не гарантируется; скорее GUID представляет собой простой и быстрый способ генерации идентификаторов без коллизий для взаимно доверенных участников. Один из механизмов, обеспечивающих глобальную уникальность, заключается в генерации GUID, составные части которого уникально определяются местом и временем. Недостаток такого подхода в том, что по составным частям GUID очень легко получить информацию о компьютере, на котором данный GUID сгенерирован. Это естественно вызывает вопросы к приватности данных.

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

Во-первых, о каких данных GUID идет речь? Мы только что сказали, что первая цифра третьей секции такого «случайного» GUID равна 4. В прошлый раз я не упомянул о том, что в четвертой секции GUID содержится дополнительная информация о версии; вы можете обратить внимание, что первое шестнадцатеричное число четвертой секции всегда содержит 8, 9, a или b. Так что 6 разрядов в GUID зарезервировано для версии, а остальные 122 разряда могут быть использованы случайным образом.

Во-вторых, почему мы считаем, что случайные данные смогут обеспечить уникальность? Результат бросания монетки является случайным, но его точно нельзя назвать уникальным! Все на что мы здесь рассчитываем – это вероятная уникальность. Бросание монетки не дает уникального результата, но бросание монетки 122 раза подряд почти наверняка дает последовательность орлов и решек, которые никогда ранее не выпадали и которые наверняка не выпадут в будущем.

Давайте обсудим эти вероятности подробнее. Предположим, мы получили случайно сгенерированный GUID. Какова вероятность того, что генерация другого GUID когда-либо приведет к коллизии с данным конкретным значением? Очевидно, что при случайном и равномерном распределении вероятность коллизии составляет 2^-122. А какова будет вероятность коллизии с данным GUID при генерации серии из n GUID? Поскольку эти события независимы, то вероятности складываются (*), и ��ероятность коллизии будет составлять n, деленное на 2¹²². 2¹²² является невероятно большим числом.

В мире существует порядка 2³⁰ персональных компьютеров (не считая, конечно карманных устройств или других устройств с соизмеримой вычислительной мощностью, но давайте их проигнорируем). Давайте предположим, что мы заставим все компьютеры мира генерировать GUID; если каждый из них способен генерировать, скажем, 2²⁰ GUID в секунду, тогда где-то через 2⁷² секунд (через сто пятьдесят триллионов лет) мы получим высокую вероятность коллизии. И вероятность коллизии становится заметной лишь через тридцать триллионов лет.

Но это, если речь идет о коллизии с одним конкретным GUID. Очевидно, что значительно больше шансов возникновения коллизии где-то по мере генерации новых GUID-ов. Вспомните, что пару лет назад я анализировал вероятность коллизии при генерации случайного 32-разрядного числа; как выяснилось, вероятность коллизии стремительно возрастает примерно после 2¹⁶генераций. Это обобщенное правило, которое заключается в том, что вероятность возникновения коллизии при генерации случайного n-разрядного числа возрастает при генерации 2^n/2 значений. Так что если мы будем использовать миллиард персональных компьютеров для генерации GUID со 122 случайными разрядами, то коллизия, скорее всего произойдет при генерации 2⁶¹ экземпляров. А поскольку мы предполагаем, что 2³⁰ компьютеров будут генерировать 2²⁰ GUID в секунду, то ожидаемая коллизия произойдет где-то через 2¹¹ секунд, т.е. примерно через час.

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

Но, конечно же, мы не собираемся этого делать. Количество GUID, генерируемых на нашей планете даже и близко не равняется 2⁵⁰! Я очень удивлюсь, если в мире генерируется хотя бы 2²⁰ GUID в секунду, а это значит, что для возникновения коллизии нам потребуется 2⁴¹ секунд, что составляет около семидесяти тысяч лет. А если мы рассматриваем коллизию конкретного GUID и учтем значительно меньшее количество генерируемых в мире GUID, то на это потребуется в миллиард раз больше времени, по сравнению с исходной оценкой.

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

Так что эти шансы весьма малы.

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

Какой источник энтропии используется в качестве исходного значения для этого псевдослучайного генератора?
Какой размер данных берется из этого источника?
При запуске двух виртуальных машин на одном физическом компьютере, используют ли они один общий источник энтропии?
Основываются ли данные из этих источников на идентификаторе компьютера (таком как MAC-адрес) или на человеке, создающем GUID?
Точно зная алгоритм генерации GUID и имея конкретный GUID, возможно ли вычислить значение, используемое в качестве начального для генерации?
При наличии двух GUID, возможно ли вычислить тот факт, что они оба сгенерированы на основе одного значения энтропии? (И, таким образом, вероятно на одном компьютере.)

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

Существует еще один механизм генерации GUID. Если первое шестнадцатеричное число третьей секции равно 2, то это GUID 1-й версии, но временная метка, которого имеет немного другое значение. Если эта число равно 3 или 5, то данные получаются путем исполнения криптографической хэш-функции по уникальной строке; уникальность строки, при этом, основывается на уникальности URL. Но я не буду вдаваться в такие подробности.

Подведем итоги:

Генерируемые GUID должны быть уникальными, но не обязательно случайными. Не используйте их в качестве случайных значений.
GUID-ы, являющиеся случайными значениями, не обладают криптографической устойчивостью.
Уникальность GUID является кооперативной; если кто-то захочет использовать сгенерированное ранее значение GUID и получить, таким образом, коллизию, то никто не сможет этому помешать. Механизм генерации GUID не является безопасным.
GUID обладают внутренней структурой; как минимум шесть бит зарезервированы и обладают особым значением.
GUID могут генерироваться последовательно и обычно, так и происходит.
Только всё значение GUID является уникальным.
Существует множество разных алгоритмов генерации GUID.
Вероятность коллизии GUID, сгенерированных случайным образом, в обозримом будущем статистически очень мала.
GUID могут раскрывать информацию о времени и месте создания, либо напрямую (как в версии 1) или путем криптоанализа (в версии 4).
В будущем могут использоваться совершенно иные алгоритмы генерации.

(*) Как правильно заметили в комментариях, это приближение истинно только, если вероятность события мала и значение n относительно мало по сравнению с общим числом возможных комбинаций.

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

Руководство по GUID. Часть 2

Russian MSDN — Tue, 31 Jul 2012 20:50:37 GMT

Так каким же образом, GUID гарантированно является уникальным без централизованного контролирующего органа, аналогичного тому, что используется в системе ISBN?

Во-первых, обратите внимание на то, что количество возможных GUID-ов значительно больше количества номеров ISBN. Поскольку последняя цифра ISBN номера является контрольной суммой, то мы имеем всего лишь 10¹² возможных значений. Это всего лишь по сотне уникальных ISBN номеров на каждого жителя Земли. Это значение практически равно 2⁴⁰, поэтому ISBN номер может быть представлен 40-разрядным значением (опять-таки, игнорируя контрольную сумму). Существует 2¹²⁸ возможных GUID-ов; это по 40 триллионов уникальных GUID-ов на каждого жителя планеты. Только лишь это дает интуитивное понятие того, что гарантировать отсутствие коллизии будет довольно просто; существует огромное количество GUID-ов на выбор!

Существует несколько возможных стратегий обеспечения уникальности GUID-ов, и, на самом деле, информация об используемой стратегии закодирована в первых четырех битах третьей «группы»; практически любой GUID, с которыми вы столкнетесь, будет представлен в одном из двух видов: {xxxxxxxx-xxxx-1xxx-xxxx-xxxxxxxxxxxx} или {xxxxxxxx-xxxx-4xxx-xxxx-xxxxxxxxxxxx}.

Если используется единица, то алгоритм обеспечения уникальности является, по сути, вариацией стратегии обеспечения уникальности номеров ISBN. Уникальность GUID-а гарантируется путем использования MAC-адреса сетевой карты в качестве одной из его частей. (Сложность обеспечения уникальности MAC-адресов двух сетевых карт в мире как-то решается кем-то другим; как именно, нам, в общем-то, не важно. Стоимость решения этой проблемы перекладывается на нас, покупателей, когда мы покупаем сетевую карту.)

(UPDATE: как указал Ларри Остерман (Larry Osterman), конечно же, решение на основе MAC-адреса не содержит защиты от дурака. Во-первых, вы можете намеренно или случайно сменить MAC-адрес на другой, который уже используется. Во-вторых, производитель оборудования вообще может забыть установить этот адрес, тогда вы получите адрес со всеми нулями. В-третьих, две виртуальные машины могут использовать одну физическую сетевую карту, и они могут генерировать GUID-ы в одно и то же время достаточно быстро, что может привести к коллизиям.)

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

Однако на практике, эта система обладает несколькими слабыми сторонами. Самым очевидным недостатком является то, что эта система не работает без сетевого адаптера! Первые версии GUID-ов, сгенерированных на компьютерах без сетевого адаптера, не были гарантировано уникальными. Менее очевидным недостатком является то, что существует небольшой шанс того, что два GUID-а будут сгенерированы «одновременно». Возможно, два генератора GUID-ов были запущены одновременно на двух разных процессорах на одном компьютере в одно и то же время. Или был сгенерирован GUID, затем машинные часы были «переведены назад» и тот же самый GUID был сгенерирован снова, просто случайно. В GUID-е существует дополнительные секции, предназначенные для решения этих проблем, так что на практике они не проявляются.

Из этого алгоритма вытекает ряд интересных следствий. Во-первых, такие GUID-ы однозначно не случайны. Многие люди ошибочно полагают, что GUID-ы являются источниками недетерминированности, хотя на самом деле, они являются источниками гарантированной уникальности.

Во-вторых, GUID-ы, сгенерированные с помощью этого алгоритма, могут быть монотонно возрастающими на конкретном компьютере. На самом деле, это очень хорошее свойство; GUID-ы часто используются в качестве первичных ключей в базах данных, и вставка большого количества строк может быть значительно более эффективной, если строки уже отсортированы и вставка осуществляется после предыдущих записей. Опять-таки, это показывает, что использовать GUID-ы в качестве источника случайных 128-разрядных значений является ужасной идеей; случайные значения обычно не являются монотонно возрастающими!

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

В-четвертых, никакое подмножество разрядов GUID-а не обладает свойством глобальной уникальности, как указал на это Реймонд в далеком 2008-м. И правда, у нас нет повода ожидать, что меньший набор битов будет обладать теми же свойствами, что и больший набор битов! Вы же не ожидаете, что можно распилить самолет пополам и получить две летающие половинки.

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

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

Руководство по GUID. Часть 1

Russian MSDN — Tue, 31 Jul 2012 19:47:35 GMT

Что такое GUID? Данный акроним расшифровывается как «globally unique identifier» (глобально уникальный идентификатор); иногда GUID-ы еще называют UUID-ами, что означает «universally unique identifier» (универсальный уникальный идентификатор). (Мне непонятно, зачем нам нужны два практически идентичных названия для одного и того же, с этим ничего не поделаешь.) По сути, GUID представляет собой 128-битовое целое, и для читабельности оно записывается в шестнадцатеричном виде с помощью следующего шаблона: {xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx}.

Цель GUID-а, которая следует из его названия, заключается в уникальной идентификации чего-либо, чтобы мы могли ссылаться на что-то с помощью идентификатора и быть полностью уверены в том, что все будут знать, о чем идет речь. Давайте подумаем об этой задаче в контексте, скажем, книг. Не совсем удобно ссылаться на книгу цитируя ее всю каждый раз, когда о ней заходит речь. Вместо этого, мы даем ей идентификатор в виде названия. Проблема с названием заключается в том, что существует множество разных книг с одинаковым названием. У меня на столе сейчас лежит три книги с названием «Язык программирования C#»; если я говорю о какой-то конкретной из них, то обычно добавляю номер издания. Но нет ничего (кроме здравого смысла), что остановило бы другого издателя от выпуска книги под названием «Язык программирования C#, четвертое издание», которая отличалась бы от всех остальных.

Издатели решили эту проблему путем создания глобального уникального идентификатора для каждой книги под названием Международный стандартный книжный номер (International Standard Book Number, ISBN). Это номер из тринадцати десятичных цифр, которые вы можете увидеть практически на каждой книге (*). Как издателю удается получить уникальный номер для каждой из миллионов публикуемых книг? Они применяют подход «разделяй и властвуй»; каждый набор цифр в ISBN имеет особое значение. Каждой стране выделяется определенный диапазон номеров, и правительства этих стран затем резервируют поддиапазоны для своих издателей. Издатели затем самостоятельно решают, как назначить оставшиеся числа для каждой книги. ISBN трех изданий спецификации языка C# следующие: 978-0-321-15491-6, 978-0-321-56299-9 и 978-0-321-74176-9. Вы можете заметить, что первые семь цифр в точности совпадают; они идентифицируют промышленный код книжной продукции (978), то, что книга издана в основном в англоязычном регионе (0), издательством Addison–Wesley (321). Следующие 5 цифр выбраны издательством Addison-Wesley, последняя цифра – это контрольная сумма. Если бы я хотел уникально идентифицировать четвертое издание спецификации языка C#, то мне совсем не стоило говорить неоднозначное название; я бы мог просто указать ее номер 978-0-321-74176-9, и любой человек смог бы в точности определить, о какой книге я говорю.

Важной и неочевидной характеристикой системы уникальности ISBN является то, что она работает только, если все играют по правилам. Если издатель-мошенник решит сознательно публиковать книги с существующими ISBN-номерами, то это создаст путаницу и дискредитирует систему, поскольку номера перестанут быть уникальными. Номера ISBN не являются безопасной системой, как и GUID-ы. Номера ISBN и GUID-ы предотвращают от случайных совпадений. Аналогично, светофоры предотвращают лишь от случайных столкновений, когда все соглашаются следовать правилам проезда перекрестков; если кто-то решит проехать на красный свет, то авария станет возможной, и если кто-то хочет намеренно создать аварию, то светофоры никак не смогут этому помешать.

Замечательным свойством системы номеров ISBN является возможность «декодировать» номер и узнать что-то о книге лишь по номеру. Но у этой системы есть и существенный недостаток – ее чрезвычайно сложно администрировать. Требуется наличие международных соглашений об общем формате идентификатора, и значениях кодов отрасли и языка. В каждой стране должна существовать организация (правительственная организация или частная компания, работающая по заказу правительства), которая бы назначала номера издательствам. Получение уникального ISBN номера может стоить сотни долларов.

Получение GUID-ов не столь дорого; GUID-ы бесплатны и никакая правительственная организация не контролирует их уникальность. GUID – это номер, который вы можете сгенерировать самостоятельно, при этом никто �� мире не сможет сгенерировать такой же. Это кажется неправдоподобным. Как это работает? В следующих нескольких статьях мы рассмотрим, каким образом это достигается.

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

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

null – это не false. Часть 3

Russian MSDN — Sat, 09 Jun 2012 07:19:49 GMT

Возвращаемся к теме нашего обсуждения: мы бы хотели позволить пользователям «перегружать» операторы & и | в языке C#, и если мы хотим перегружать эти операторы, то кажется, что должна существовать возможность перегрузки операторов && и ||.

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

class C
{
string s;
public C(string s) { this.s = s; }
public override string ToString() { return s; }
public static C operator +(C x, C y) { return new C(x.s + "+" + y.s); }
}
...
Console.WriteLine(new C("123") + new C("456")); // "123+456"

Но аргументы метода вычисляются «жадно» (eagerly). Поэтому мы не можем написать:

public static C operator &&(C x, C y) {... что угодно... }

Поскольку в этом случае, когда вы напишите:

C c = GetFirstC() && GetSecondC();

Код будет преобразован компилятором в:

C c = C.op_ShortCircuitAnd(GetFirstC(), GetSecondC());

Что, очевидно, приведет к вычислению обоих операндов не зависимо от того, будет ли левый операнд равен «true» или «false».

Конечно же, с современном C# в нашем распоряжении есть тип, использование которого говорит нам: «произвести вычисления в будущем, по требованию»; это тип Func<T>. Мы можем реализовать данную версию так:

public static C operator &&(C x, Func<C> fy) {... что угодно... }

И теперь, компилятор сможет преобразовать данный код в:

C c = C.op_ShortCircuitAnd(GetFirstC(), ()=>GetSecondC());

Этот вариант будет прекрасно работать, хотя и содержит ряд проблем. Во-первых, он потенциально менее эффективный; даже если мы никогда не будем использовать второй аргумент, мы все равно тратим ресурсы на создание делегата. Во-вторых, C# 1.0 не содержал ни лямбда-выражений, ни обобщенных типов делегатов, поэтому во времена разработки первой версии языка этот вариант бы не подошел.

При решении этой задачи мы приняли, что на самом деле, здесь имеют место две вещи. Во-первых, мы должны решить, нужно ли вычислять правый операнд или нет. Если нам не нужно вычислять правый операнд, то результат может равняться левому операнду. Если мы вычисляем правый операнд, то нам нужно объединить результаты вычисления обоих операндов с помощью оператора без оптимизации вычисления логических выражений (non-short-circuiting operator).

Первая операция (т.е. определение того, нужно ли вычислять правый операнд) требует операторов operator true и operator false. Эти операторы дают ответ на вопрос: «требует ли этот операнд вычисления второго или нет?».

Но теперь мы сталкиваемся с другой проблемой. В прошлый раз у нас была проблема с операторами && и || при использовании значений, отличных от true или false. А именно, означает ли выражение x && y «вычислить y тогда и только тогда, когда x равен true» или же «вычислить y тогда и только тогда, когда x не равен false»? Очевидно, что для булевых выражений оба эти варианты эквивалентны, но они не эквивалентны для nullable Boolean. И они также не эквивалентны для определенных пользователем операторов. В конце концов, если у вас есть непротиворечивый способ преобразования вашего типа к true или false, вы просто реализовали бы неявное преобразование вашего типа к bool и использовали бы встроенные операторы && и ||.

Команда проектировщиков языка C# 1.0 решили, что правило должно быть таким: «вычислять y тогда и только тогда, когда x не false». Мы реализовали это правило с помощью оператора «operator false», который возвращает true, когда x нужно рассматривать как false, и false, когда x нельзя рассматривать как false. Понимаю, что звучит запутанно. Возможно, пример сможет помочь:

class C
{
string s;
public C(string s) { this.s = s; }
public override string ToString() { return s; }
public static C operator &(C x, C y) { return new C(x.s + "&" + y.s); }
public static C operator |(C x, C y) { return new C(x.s + "|" + y.s); }
public static bool operator true(C x) { return x.s == "true"; }
public static bool operator false(C x) { return x.s == "false"; }
}
...
C ctrue = new C("true");
C cfalse = new C("false");
C cfrob = new C("frob");

Console.WriteLine(ctrue && cfrob); // true&frob
Console.WriteLine(cfalse && cfrob); // false
Console.WriteLine(cfrob && cfrob); // frob&frob

В данном случае x && y реализовано так:

C temp = x;
C result = C.op_false(temp)? temp : temp & y;

Аналогично, выражение x || y использует «operator true» подобным же образом.

Малоизвестным фактом является то, что если для пользовательского типа вы можете использовать && и ||, то вы можете использовать его в инструкциях, принимающих bool, таких как if и while. Это означает, что вы можете написать следующее:

if (ctrue && cfrob)...

Поскольку этот код эквивалентен:

C temp = ctrue;
C result = C.op_false(temp)? temp : temp & cfrb;
bool b = C.op_true(result);
if (b)...

Правда здорово?

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

Небольшое отступление

Russian MSDN — Sat, 09 Jun 2012 06:06:14 GMT

Прежде чем мы продолжим наши изыскания, небольшое отступление. В прошлый раз я упомянул о головоломках Реймонда Смаллиана о «рыцарях и лжецах». И хотя мне очень нравятся эти головоломки, самыми любимыми его головками являются шахматные задачи, вторыми идут задачи на комбинаторику. Вот пример второго типа задач (адаптированная задача со страницы 134 книги Satan, Cantor and Infinity).

У нас есть алфавит с буквами S, E, R, M, K и V, из которых можно составлять строки; «строка» является упорядоченной последовательностью символов из этого алфавита; последовательность может содержать любое конечное число символов. Говорят, что некоторые строки «определяют» (name) другие строки.

Я буду использовать «x» и «y» в качестве переменных для строк, и, более того, мы можем сказать, что x и y никогда не содержат пустых строк. (И, как будет говориться в четвертом правиле, y содержит как минимум два символа.) Правила именования следующие:

· SxE определяет x

· Если x определяет y, то Rx определяет yy

· Если x определяет y, то Mx определяет SyE

· Если x определяет y, то Kx определяет строку, созданную путем удаления самого левого символа из y

· Если x определяет y, тогда Vx определяет строку, созданную путем реверсирования символов y

Например, SRME определяет RM, по первому правилу. Поскольку SRME определяет RM, то исходя из второго правила, мы знаем, что RSRME определяет RMRM. И, таким образом, KRSRME определяет MRM.

Судя по комментариям, у некоторых читателей возникли вопросы; обратите внимание, что я не говорю о том, что некоторые строки являются «корректными», а некоторые – нет. Я говорю скорее о том, некоторые строки определяют другие строки. Строка, которая не определяет никакую другую строку остается совершенно «нормальной» строкой; ни одна из строк не является более или менее корректной, чем другая. Например, «RM» не определяет никакую другую строку.

Задача состоит в том (и она едва ли будет слишком сложной для программистов, но довольно хитрой для непрограммистов, которые не прочитали пятнадцать более простых задач перед этим), это найти строку, которая будет определять саму себя. Решение Смаллиана состоит из 18 символов, и он призывает читателя найти более короткое решение. Я нашел решение из 12 символов, и я предполагаю, что 12 символов – это наименьшее решение, но доказать это я не могу. Я дам свое решение, а также решение Смаллиана в комментариях. Удачи!

UPDATE: Существует минимальное решение из девяти символов. Отличная работа!

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