Продолжаю тему, поднятую предыдущем постом - трансформации компиляторов .NET-языков, связанные с компиляцией различных анонимных методов/лямбда-выражений.

Теперь настало время заглянуть во внутреннюю кухню F#, поддерживающего значения функционального типа (а так же делегаты CLI), как и любой другой нормальный функциональный язык. Значения функционального типа в F# представляются для CLI наследниками следующего типа:

namespace Microsoft.FSharp.Core {
  [Serializable]
  public abstract class FSharpFunc<T, TResult> {
    public abstract override TResult Invoke(T func);
  }
}

Хм, только функции типа T -> TResult? Именно! Абсолютно все значения функционального типа в F# выражаются таким типом - 'a -> 'b. Данный тип напоминает типы делегатов .NET - он имеет метод Invoke() (который можно использовать чтобы вызвать F#-функцию из любого другого .NET языка). Замыкания натурально представляются в F# в виде полей наследников данного класса (обратите внимание на флаг сериализуемости, речь о нём пойдёт чуть позже).

Функции от нескольких аргументов могут представляться как функции, получающие один параметр-кортеж из аргументов. Например, fun(x,y) -> x + y представляется для CLI следующим образом:

[Serializable]
class foo@7 : FSharpFunc<Tuple<int, int>, int> {
  public override int Invoke(Tuple<int, int> tuple) {
    int x = tuple.Item1;
    int y = tuple.Item2;
    return x + y;
  }
}

Другой вариант представления функций от нескольких аргументов - в каррированной форме. В данном случае функция fun x y -> x + y (или просто (+)) представляеться как функция от аргумента int и возвращающее значение типа int -> int, применив к которой второй аргумент, можно получить результат сложения. То есть F# мог бы скомпилировать что-то вида:

[Serializable]
class bar@5 : FSharpFunc<int, FSharpFunc<int, int>> {
  public override FSharpFunc<int, int> Invoke(int arg) {
    return new bar@6(arg);
  }
}

[Serializable]
class bar@6 : FSharpFunc<int, int> {
  internal int x;
  internal bar@6(int x) { this.x = x; }

  public override int Invoke(int y) {
    return this.x + y;
  }
}

А вызовы такой функции представлялись бы в виде f.Invoke(1).Invoke(2), что выглядит логично, но совсем не претендует на производительность - если такую функцию вызывают сразу со всеми аргументами, а не каррируют (применяют не все аргументы), то мы получаем абсолютно ненужное создание экземпляра класса + копирования в поля на каждый аргумент, кроме последнего. F# глубого оптимизирует это дело и на самом деле создаёт следующий тип:

[Serializable]
class hh@7 : OptimizedClosures.FSharpFunc<int, int, int> {
  public override int Invoke(int x, int y) {
    return x + y;
  }
}

Ага, значит в недрах стандартной библиотеки F# таки есть тип для удобного представления значений функционального типа с несколькими аргументами в каррированной форме. Давайте посмотрим на его определение:

[Serializable]
public abstract class FSharpFunc<T1, T2, TResult>
  : FSharpFunc<T1, FSharpFunc<T2, TResult>> // <---
{
  // аналог Invoke с двумя аргументами
  public abstract override TResult Invoke(T1 arg1, T2 arg2);

  // переопределение FSharpFunc<T1, FSharpFunc<T2, TResult>>.Invoke()
  public override FSharpFunc<T2, TResult> Invoke(T1 arg) {
    // возвращаем FSharpFunc<T2, TResult>, передавая в замыкание this и arg
    return new Invoke@2920<T2, TResult, T1>(this, arg);
  }

  [Serializable]
  class Invoke@2920<T2, TResult, T1> : FSharpFunc<T2, TResult>
  {
    // исходная функция и её первый аргумент в замыкании
    public FSharpFunc<T1, T2, TResult> f;
    public T1 t;

    internal Invoke@2920(FSharpFunc<T1, T2, TResult> f, T1 t) {
      this.f = f;
      this.t = t;
    }

    public override TResult Invoke(T2 arg) {
      // теперь у нас есть оба аргумента, вызываем Invoke(T1, T2)
      return this.f.Invoke(this.t, arg);
    }
  }
}

То есть на самом деле всё равно создаётся FSharpFunc<T1, FSharpFunc<T2, TResult», вызвав у которого Invoke() с первым аргументом, нам вернётся другая функция, применив к которой второй аргумент, мы получим результат. Так в чём же выигрыш, ведь опять требуется выделять память под замыкание для первого аргумента? Трюк в том, что значение функционального типа с аргументами в каррированной форме не вызываются как f.Invoke(arg1).Invoke(arg2), для подобных вызовов в стандартной библиотеке определено несколько перегрузок статического метода InvokeFast (реальная реалзиация немного отличается от приведённой ниже названием типов аргументов):

public static TResult InvokeFast<T1, T2, TResult>(
  FSharpFunc<T1, FSharpFunc<T2, TResult>> func, T1 x, T2 y)
{
  var func2arg = func as OptimizedClosures.FSharpFunc<T1, T2, TResult>;
  if (func2arg != null) return func2arg.Invoke(x, y);

  return func.Invoke(x).Invoke(y);
}

public static TResult InvokeFast<T1, T2, T3, TResult>(
  FSharpFunc<T1, FSharpFunc<T2, FSharpFunc<T3, TResult>>> func, T1 x, T2 y, T3 z)
{
  var func3arg = func as OptimizedClosures.FSharpFunc<T1, T2, T3, TResult>;
  if (func3arg != null) return func3arg.Invoke(x, y, z);

  var func2arg = func as OptimizedClosures.FSharpFunc<T1, T2, FSharpFunc<T3, TResult>>;
  if (func2arg != null) return func2arg.Invoke(x, y).Invoke(z);

  return InvokeFast<W>(func.Invoke(x), y, z);
}

// и так далее...

Значит перед вызовом любой функции с аргументами в каррированной форме F# производит проверку типа, может ли данная функция сразу принять несколько аргументов или нет. В случае функции трёх аргументов в каррированной форме, например, F# сначала пытается вызвать функцию со всеми тремя аргументами, затем в случае неудаче пытается вызвать сразу с двумя аргументами, а третий аргумент передать возвращённой функции. В случае неудачи и в этомт раз, F# вызывает функцию с одним аргументом и пытается тем же “быстрым” способом вызвать получившуюся функцию двух аргументов в каррированной форме.

Удивительно, но всё это безобразие оказывается гораздо эффективнее f.Invoke(arg1).Invoke(arg2).Invoke(arg3) в абсолютном большинстве повседневных случаев (проверка типа - достаточно дешевая операция), однако всё равно не следует увлекаться функциями с большим количеством аргументов (я бы не советовал более 2-3 аргументов) в каррированной форме. Функции из стандартной библиотеки F# применяют дополнительные оптимизации чтобы не осуществлять данные проверки на каждый вызов функции правила свёртки внутри List.fold, например.

Теперь давайте отойдём от type parameters hell и рассмотрим то, как в F# представляются функции без возвращаемого значения или без аргументов (а такие функции имеют место в не являющимся чистым функциональном языке). Для представления таких функций в C#/VB.NET стандартная библиотека .NET предлагает набор типов делегатов System.Action<>. В F# для обозначения отсутствия возвращаемого значения или входных параметров используется тип unit и единственное значение данного типа - (). Во большинстве случаев F# компилирует методы и функции, возвращающие/принимаюшие unit, как обычные void-методы/методы без аргументов. Однако в случае значений функционального типа, unit приходится материализовать:

/// f :: unit -> unit
let f = (fun() -> Console.WriteLine("привет!"))

Компилируется в:

[Serializable]
class f@3 : FSharpFunc<Unit, Unit> {
  public override Unit Invoke(Unit unitVar0) { // <---
    Console.WriteLine("привет!");
    return null; // null - и есть значение ()
  }
}

Да, получается совсем незначительный оверхэд, однако в случае использования в F# обычных делегатов .NET, никаких фиктивных значений типа unit вводиться не будет:

let a = Action(fun() -> Console.WriteLine("привет!"))

Преобразуется в отдельный тип:

[Serializable]
sealed class a@4 { // <--- не наследник FSharpFunc!
  internal void Invoke() { // произвольная сигнатура
    Console.WriteLine("привет!");
  }
}

Окей, с этим разобрались, какие же ещё отличия есть в компиляции анонимных делегатов C# и значений функционального типа в F#? Внимательный читатель мог обратить внимание на то, что F# в наследниках FSharpFunc генерирует конструкторы, копирующие данные замыкания в поля класса. Зачем компилировать “лишние” конструкторы, если можно из метода, создающего closure-класс, заполнять public-поля closure-класса (в F# поля closure-классов иногда почему-то имеют модификатор internal), как это делает C#? Я не отвечу на вопрос “почему так сделано”, скорее всего поля оставили public/internal просто так (или это вообще баг p3ynO1), ведь поля можно сделать private и абсолютно любой F# код продолжет исправно работать! Как же так, ведь C# использует для полей public чтобы метод, создающий анонимный делегат, мог обращаться к переменным, взятым в замыкание, считывать и изменять их?

Тут открывается ещё одно важное отличие компиляции замыканий в F# и C# - переменные, взятые в замыкание в F# не могут быть изменяемыми. Многие, кто пробовали работать с F#, наверняка сталкивались с таким ограничением (очень правильным ограничением), выражаемым в ошибку компиляции FS0407. Это ограничение имеет большое влияние на код, генерируемый для представления замыкания - можно создавать экземпляр closure-класса и просто передавать в него “снимок” значений локальных переменных замыкания (в F# - через конструктор closure-класса), продолжая далее использовать эти локальные переменные, так как они не могут измениться и в точности равны значениям, заключённым в созданном closure-классе. Это позволяет не выделять взятые в замыкания переменные на куче (и обращаться к ним, как к полям closure-класса), а лишь копировать их значения в местах создания closure-класса. В очень редких случаях, когда “замыкаемость” на изменяемые переменные всё же необходима или удобна, F# предоставляет удобную обёртку изменяемых значений - ref-ячейки.

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

let sharedClosure() =
  let xs = Array.zeroCreate 1000000
  let index = ref 0 // ячейка с изменяемым значением

  let notEventUsed = Action(fun() ->
    Console.WriteLine(xs.[!index] : int))

  fun() -> index := !index + 1

И посмотрим на то, что внутри:

sealed class notEventUsed@21 // не наследник FSharpFunc
{
  public int[] xs;
  public FSharpRef<int> index;

  public notEventUsed@21(int[] xs, FSharpRef<int> index) {
    this.xs = xs;
    this.index = index;
  }

  internal void Invoke() {
  	Console.WriteLine(this.xs[this.index.Contents]);
  }
}

[Serializable]
class sharedClosure@24 : FSharpFunc<Unit, Unit> {
  public FSharpRef<int> index;

  internal sharedClosure@24(FSharpRef<int> index) {
    this.index = index;
  }

  public override Unit Invoke(Unit unitVar0) {
    this.index.Contents = this.index.Contents + 1;
    return null;
  }
}

public static FSharpFunc<Unit, Unit> sharedClosure() {
  int[] xs = ArrayModule.ZeroCreate<int>(1000000);
  FSharpRef<int> index = Operators.Ref<int>(0);
  Action notEventUsed = new Action(new notEventUsed@21(xs, index).Invoke);
  return new sharedClosure@24(index);
}

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

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

Осталось осветить ещё одну особенность генерации кода в F# - сериализуемость замыканий. Внимательный читатель наверняка заметил множество аннотаций [Serializable] в примерах кода из этого поста.

Компилятор F# имеет встроенный механизм автосериализации, который отмечает атрибутом [Serializable] все типы, определяемые в F# (пока не встретит атрибут [<AutoSerializable false>]). Так как функциональные типы ничем не хуже любых других типов, то сериализации могут быть подвергнуты и они, что позволяет сериализовать структуры данных из функций, как пример - не вычисленный LazyList из F# PowerPack, различные computation expressions. Ещё один юзкейс - замыкания, пересекающие границу доменов .NET-приложений:

open System

let showFromOtherDomain (message: string) =
  let domain = AppDomain.CreateDomain "Temp"
  try domain.DoCallBack(fun() -> Console.WriteLine message)
  finally AppDomain.Unload domain

Аналогичный код на C# просто упадёт из-за невозможности сериализовать closure-класс, а код на F# выполнится как ожидается. К сожалению, компилятор F# иногда не отмечает closure-классы как сериализуемые и найти этому разумное объяснение я не смог, но нашёл один конкретный случай - когда в замыкание попадает значение типа массива .NET (в этом посте рассмотрен такой случай и аннотации атрибутом [Serializable] действительно нет). Если у Вас есть информация на этот счёт, то буду рад, если вы поделитесь комментарием.