Control::Flow

В ходе всё ещё тщетных попыток написать на C# типизированную версию клёвого и особо опасного для мозга U-комбинатора (Y-комбинатор без рекурсии):

Y = (λh.λF.F(λx.((h(h))(F))(x))) (λh.λF.F(λx.((h(h))(F))(x)))

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

delegate β ƒ<α, β>(α x);
delegate α γ<α>(γ<α> f);

static ƒ<α, β> Y<α, β>(ƒ<ƒ<α, β>, ƒ<α, β>> f) {
  return new γ<ƒ<α, β>>(h => F => f(h(h))(F))(h => F => f(h(h))(F));
}

Осталось взять всеми любимый факториал с аргументами в каррированной форме:

static ƒ<int, int> Fact(ƒ<int, int> fact) {
  return n => (n == 0) ? 1 : n * fact(n - 1);
}

И скормить его комбинатору:

var fact = Y<int, int>(Fact);
Console.WriteLine("fact(6) = {0}", fact(6));

Поздравляю, теперь вы вооружены на случай, если из C# когда-нибудь дропнут рекурсивные вызовы :)

p.s. U-комбинатор по прежнему в поиске своего типизированного аналога!

Сегодня я хочу рассказать о нововведениях мультипарадигменного (но functional-first) языка программирования общего назначения F# версии 3.0. Последняя версия F# на данный момент доступна только в составе с Visual Studio “11” Beta (качать тут), что немного грустно. Самих нововведений совсем не много, но некоторые из них достаточно значимые. Сегодня речь пойдёт об автосвойствах.

В F# достаточно запутанный синтаксис определения обычных классов, который я постоянно забываю, хотя после того как осознаёшь все нюансы, он может начинать казаться достаточно лаконичным. До версии 3.0, для того чтобы определить класс с парой get-only свойств, приходилось писать достаточно немного:

type Person(name, age) =
     member this.Name = name : string
     member this.Age  = age  : int

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

type Person(name, age) =
     member this.Name : string with get() = name 
     member this.Age  : int    with get() = age

Причём набор необходимых полей компилятор определяет сам - в тривиальном случае он просто превращает в поля все параметры primary-конструктора, которые имеют как минимум одно использование в определении членов класса. В более сложных случаях, в поля превращаются let-биндинги уровня типа. Например, у класса ниже будет два поля - параметр name используется только в инициализации let-биндинга и ни разу не используется в членах класса, поэтому поле для него создано не будет, а для самого let-биндинга mrName - будет:

type MrPerson(name, age) =
     let mrName = "Mr. " + name
     member this.Name = mrName : string
     member this.Age  = age    : int

Так как F# является полноправным жителем объектно-ориентированного мутабельного мира .NET, то язык, конечно же, предоставляет возможность определять изменяемые, get/set-свойства. Однако параметры primary-конструктора являются неизменяемыми (как и вообще любые другие параметры функций и методов F#), то их не выйдет использовать для хранения изменяемых полей. На помощь приходят изменяемые let-биндинги уровня типа, однако запись класса значительно разбухает:

type MutablePerson(name, age) =
     let mutable name = name
     let mutable age  = age
     member this.Name with get() = name : string
                       and set x = name <- x
     member this.Age  with get() = age  : int
                       and set x = age <- x

Или даже вот так:

type HugePerson(name, age) =
     let mutable name = name
     let mutable age  = age
     member this.Name with get() = name : string
     member this.Name with set x = name <- x
     member this.Age  with get() = age  : int
     member this.Age  with set x = age <- x

Обратите внимание, что параметры методов-акцессоров пишутся явно и можно объявлять “индексированные свойства”, такие же как в VB.NET, но это достаточно редко используемая возможность. Однако в F# существует ещё более громоздкий синтаксис для классов без primary-конструктора (то есть без скобочек с опциональными параметрами класса после имени типа) и let-биндингов, дающий пользователю возможность задать набор полей явно. При такой записи конструкторы должны содержать либо вызовы других конструкторов, либо инициализировать все явно определённые поля объекта (кроме помеченных атрибутом [<DefaultValue>]) и при необходимости вызывать конструктор базового класса. Определение всего этого безобразия, соответственно, распухает практически до уровня C# 2.0:

type ExplicitMutablePerson =
     new (name, age) = { name = name
                         age  = age  }

     val mutable name : string
     val mutable age  : int

     member this.Name with get() = this.name
                       and set x = this.name <- x
     member this.Age  with get() = this.age
                       and set x = this.age <- x

Обратите внимание, что в отличии от параметров primary-конструктора и let-биндингов уровня типа, к явным полям приходится обращаться точно так же, как и к другим членам класса - явно через квалификатор this (смотря как вы его назвали в том или ином члене класса). Поля по-умолчанию являются изменяемыми, поэтому требуют модификатора mutable. Неизменяемый вариант класса с явными полями принимает следующий вид:

type ExplicitImmutablePerson =
     new (name, age) = { name = name
                         age  = age }
     val name : string
     val age  : int

     member this.Name = this.name
     member this.Age  = this.age

Кстати, при такой записи возможно выполнить какой-либо дополнительный код после инициализации объекта:

type InstantiateMe =
     new () = { } // инициализация объекта
              then // side-effects тут:
                printfn "thank you!"

Теперь мы наконец подошли к новому синтаксису автосвойств, которые представляет нашему вниманию F# 3.0, неизменяемые свойства принимают вид:

type Person(name, age) =
     member val Name = name : string
     member val Age  = age  : int

Код практически идентичен самому первому, однако есть отличия. При использовании ключевого слова member val становится не нужно давать имя this-параметру, поле для значения генерируется компилятором в любом случае, а обязательное выражение после символа = является не телом get-акцессора свойства, а выражением инициализации автосвойства при инстанциировании экземпляра класса. То есть конкатенация строк в примере ниже происходит только один раз, при создании экземпляра MrPerson:

type MrPerson(name, age) =
     member val Name = "Mr. " + name
     member val Age  = age  : int

При этом так же, как в C#, вы не имеете доступа к backing-полям таких свойств. Теперь самое приятное - чтобы сделать такие свойства изменяемыми, достаточно после выражения инициализации дописать with get, set:

type MutablePerson(name, age) =
     member val Name = name : string with get, set
     member val Age  = age  : int    with get, set

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

class MutablePerson {
  public MutablePerson(string name, int age) {
    Name = name;
    Age = age;
  }
  public string Name { get; set; }
  public int    Age  { get; set; }
}

Автосвойства могут быть статическими, как и обычные свойства, достаточно использовать для определения модификатор static. Однако у автосвойств F# есть ограничения - например, их можно использовать только в типах с primary-конструктором, точно так же, как и let-биндинги уровня типа (это связано с особенностями процесса инициализации объектов в F#, о которых я постараюсь рассказать в других постах). Ещё одним важным и просто замечательным ограничением является то, что автосвойства в F# не могут быть виртуальными - это решает потенциальную проблему о “забытом” состоянии в базовом классе (к аналогичным проблемам могут приводить виртуальные field-like события в C#).

Ещё одним нюансом является то, что события в F# представляются в виде свойств, которые компилятор можно заставить компилироваться в обычные CLR-события путём аннотации свойства атрибутом [<CLIEvent>]. Этот атрибут работает и для автосвойств:

type WithEvent() =
     let doneEvent = new Event<EventHandler, _>()
     [<CLIEvent>] // автосвойство-событие
     member val Done = doneEvent.Publish
     member this.Complete() =
       doneEvent.Trigger(this, EventArgs.Empty)

Однако такой класс содержит два поля (поля для свойства Done и let-привязки doneEvent), вместо одного действительно нужного (doneEvent). Замена свойства на обычное устраняет избыточное поле. К сожалениею, в отличие от автосвойств C#, аннотировать аттрибутами методы-акцессоры ни обычных свойст, ни автосвойств - невозможно (точно так же, как в F# 2.0). Однако backing-поле автосвойства аннотировать всё же можно:

type Person(name: string, age: int) =
     [<field:NonSerialized>]
     member val FullName = name + string age with get

Автосвойства F# 3.0 производят приятное впечатление и существенно снижают уровень синтаксического шума при определении изменяемых свойств, которые достаточно частно нужны для интероперабельности с .NET-библиотеками. Однако становится важно отличать автосвойства от обычных свойств и понимать отличие выражения инициализации автосвойства от выражений значений обычных свойств, что ещё немного запутывает и без того нелёгкие правила деклараций типов F#. В то же время определять обычные классы в F# приходится гораздо реже, чем record-типы и union-типы.

Да, это случилось. В последней версии компилятора C# из состава Visual Studio “11” Beta изменилось правило разворачивания компилятором цикла foreach:

foreach (T x in xs) {
  f(x);
}

Цикл foreach - достаточно нетривиальная конструкция и имеет множество нюансов, я привожу лишь самый обычный случай, когда xs является переменной типа IEnumerable<T>. Раньше такой цикл компилировался прибилизительно следующим образом:

{
  IEnumerator<T> e = ((IEnumerable<T>) xs).GetEnumerator();
  try {
    T t;
    while (e.MoveNext()) {
      t = e.Current;
      f(t);
    }
  }
  finally {
    ((IDisposable)e).Dispose();
  }
}

Теперь компилируется вот так:

{
  IEnumerator<T> e = ((IEnumerable<T>) xs).GetEnumerator();
  try {
    while (e.MoveNext()) {
      T t = e.Current;
      f(t);
    }
  }
  finally {
    ((IDisposable)e).Dispose();
  }
}

То есть декларация переменной итерации уехала внутрь цикла while и это оказывает влияние на то, как теперь происходит замыкание на переменную итерации foreach. Так как замыкание в C# происходит по ссылке (замыкание на сами переменные, а не на их значения), то все анонимные методы и лямбда-выражения замыкаются на одну и ту же переменную и если их исполнение будет отложено за пределы цикла, то они “увидят” в переменной значение на момент последней итерации цикла, а не на момент создания анонимного метода/лямбда-выражения. Не смотря на то, что поведение чётко описано в спецификации и в некотором роде имеет право на существование, среднестатический юзер C# всё-же упёрто ожидает, что на каждой итерации цикла будет замыкаться на “fresh variable”. Ходят шутки, что изменение этого поведение убрало бы на StackOverflow добрую треть вопросов по C#.

Видимо, юзеры настолько задолбали C# team, что те решились на такой достаточно серьёзный breaking change. Однако факт остаётся фактом, теперь этот код:

using System;
using System.Collections.Generic;
using System.Linq;

static class Program {
  static void Main() {
    var xs = new List<Action>();
    foreach (var i in Enumerable.Range(1, 3)) {
      xs.Add(() => Console.WriteLine(i));
    }

    foreach (var action in xs) {
      action();
    }
  }
}

Выводит на экран ожидаемые:

1
2
3

Думаю, что решающим был тот факт, что сложно придумать пример, в котором предыдущее поведение было бы осмысленным в случае отложенного исполнения замыкания - в 99% случаях такие замыкания просто являются ошибками. Будем надеяться, что с таким изменением язык C# станет более логичным для пользователя, а скрытые ошибки, связанные с замыканием на переменную итерации foreach, сами пофиксятся, когда проекты будут собирать компилятором C# версии 5.0.

p.s. Эти изменения никак не затрагивают цикл for, в котором присутствует подобная проблема, так как цикл for на самом деле совсем не связан с переменными, которые могут определять (а могут и не определять) в части инициализации цикла.

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

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

public IDeclaredType ResourceKey {
  get { return GetType("System.Windows.ResourceKey"); }
}

public IDeclaredType EventSetter {
  get { return GetType("System.Windows.EventSetter"); }
}

public IDeclaredType Trigger {
  get { return GetType("System.Windows.Trigger"); }
}

Функция GetType() тут осуществляет поиск в словаре по ключу - полному имени типа - и производит поиск типа по сборкам в случае промаха. Функцию GetType() можно считать чистой функцией в рамках промежутка между инвалидацией всего кэша. Понятно, что поиск в кэше-словаре фактически не особо и нужны - в каждом случае использования GetType() можно кэшировать результат в инвидиадуальном поле и таким образом превратить поиск по словарю в единственный if. Проблема в том, что в моём коде сейчас 121 такой вызов и в 90% случаев параметры контантны - создавать поле и явно проверять его (ещё и под lock‘ом) на каждый usage уж совсем не хочется и не разумно. При этом инвалидируется весь кэш, мягко говоря, достаточно часто (практически на каждое нажатие пользоваталем клавиши (!) вне тел методов, так как любое такое нажатие может привести к появлению новых/исчезновению старых типов. Даже при такой частоте инвалидации, доля попаданий этого кэша составляет 99.993%, так что он всё равно очень клёвый) и превращать процедуру инвалидации в зануление тьмы полей просто неприемлимо.

Так вот, имея возможность получать на стороне функции GetType() некоторый объект, характеризующий конкретный факт её вызова, можно было бы построить гораздо более гранулярный кэш. Такие техники уже применяются в том же C#, но об этом речь пойдёт чуть позже. Давайте попробуем представить код на языке с расширением, который я бы назвал first-class call site (то есть “вызывающая сторона, являющаяся значение”), упрощающим использование подобных техник для написания всеми любимых функций вычисления факториалов:

// декларация:
static int Fact(int x, Dictionary<int, int> cache = callsite) {
  int result;
  if (cache.TryGetValue(x, out result)) return result;

  result = (x == 0) ? 1 : x * Fact(x - 1, cache);
  cache[x] = result;
  return result;
}

// использование:
Fact(6);

Всё достаточно просто и явно - надо лишь научить компилятор генерировать скрытые поля на стороне вызова и автоматически передавать их в опциональные параметры, отмеченные некоторой аннотацией, например (я пока не пытаюсь ответить на вопросы инвалидации таких “разбросанных” кэшей).

Подобную технику использует C# 4.0 dynamic - вместо того, чтобы компилировать, например, выражение доступа к члену объекта типа dynamic вида d.Foo, в простой вызов какой-нибудь функции типа GetMemberDynamic(object target, string name), компилятор совершает гораздо больше телодвижений. На каждую dynamic-операцию один раз создаётся и хранится в статическом поле специальный callsite-объект, который хранит всякую инфраструктурную фигню и самый обычный .NET-делегат, который на самом деле и вызывается на каждую динамическую операцию. При первом исполнении кода, инфраструктура C# dynamic согласно статическим правилам компилятора C# пытается разрезолвить динамическую операцию и в случае успеха компилирует (!) постой делегат, совершающий требуемую операцию. Помимо требуемой операции в делегат попадает специальный инфраструктурный код, который будет осуществлять проверку - можно-ли при повторном вызове динамической операции переиспользовать скомпилированный делегат? Например, если код foo.Bar первый раз разрезолвился в обращение к свойству Foo у класса типа ConcreteFoo, то скомпилированный делегат можно будет переиспользовать если при повторном вызове foo будет типа ConcreteFoo. В противном случае процедуру резолва придётся повторить ещё раз и инфраструктура C# dynamic подменит старый делегат, скомпилировав новый (причём последние 10 делегатов останутся в callsite-объекте, так как могут ещё пригодиться).

Всё это шаманство приводит к тому, что немного “прогревшись”, большинство динамических операции обращаются в очень эффективные (по сравнению с первым резолвом, возбуждающим компиляцию) вызовы обычных делегатов с одним-двумя if, что в некотором роде доказывает состоятельность и целесообразность кэширования на стороне вызова в подобных сценариях. Фактически, эта техника аналогична модификации исполняемого кода во время исполнения для кэширования (polymorphic inline caching), которую делает большинство современных JavaScript-движков или, например, CLR JIT для компилирования вызовов через интерфейс.

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

Интересно, я ожидал от компилятора C# в таком коде скрытого замыкания:

static class Foo {
  static void Bar(this string source) { }
  static void Main() {
    System.Action boo = "abc".Bar;
  }
}

На самом деле компилятор сгенерировал здесь точно такой же msil, как если бы метод Bar() был настоящим методом уровня экземпляра типа System.String, сохранив экземпляр строки в экземпляре делегата - так же, как сохраняет и автоматически “подставляет” в качестве первого параметра скрытый от пользователя this.

Было бы интересно иметь противоположную возможность - позволить создавать из методов уровня экземпляра делегаты с произвольным this-параметром, допустив указание произвольного экземплярного метода без экземпляра соответствующего типа (и даже нет проблем пересечения с именами статических методов):

System.Func<string, int> boo = System.String.Length;

Однако очевидная проблема данной фичи проявляется в случае использования виртуальных методов:

System.Func<Foo, int> boo = Foo.GetHashCode;

Из какого именно метода делать делегат? Из метода Foo.GetHashCode()? Что, если тип Foo не переопределяет метод GetHashCode() - брать реализацию Object.GetHashCode? Что, если первым параметром делегата передадут наследника Foo, имеющего свою реализацию GetHashCode() - вызывать эту реализацию (тогда делегат никогда не будет указывать на какой-то конкретный метод) или использовать реализацию типа Foo (что позволяет на наследниках вызовы Foo.GetHashCode(), которые могут быть недопустимы)? Допускать-ли такую запись, если метод GetHashCode() объявлен абстрактным? Кстати, Object.GetHashCode(), как и любой другой виртуальный метод, можно переопределить и одновременно сделать абстрактным, путём комбинирования модификаторов abstract и override - что делать в таком случае?

Вообщем, мягко говоря, сомнительная фича получается :)