F#: Во что превращается ваш код после компиляции

Язык F# появился в стандартной поставке VisualStudio совсем недавно, а именно с версии 2010 (на данный момент самой что ни на есть актуальной). Естественно, и все это прекрасно знают, язык функционирует на основе CLR — весь ваш код будет скомпилирован в MS IL как и любой другой язык .NET семейства.

Давайте на примере часто используемой и полезной техники «меморизация» посмотрим во что превращает ваш код компилятор. Для наглядности я буду писать сам код на F# и декомпилировать его в C#.

Итак, исходный пример:

let memoize f =
    let cache = System.Collections.Generic.Dictionary()
    fun x ->
        if cache.ContainsKey(x) then
            cache.[x]
        else
            let res = f x
            cache.[x] <- res
            res

let rec memoizedFactorial =
    let factorial x =
        match x with
        | a when a = 0I -> 1I
        | x -> x * memoizedFactorial (x - 1I)
    memoize factorial
    
let now = System.DateTime.Now

let arguments = [10000I .. 10100I]
let factorials = arguments |> List.map memoizedFactorial

let timeDiff = System.DateTime.Now - now
printfn "Time: %A" timeDiff

Несколько пояснений:

• Будем считать 101 факториал от 10000 до 10100. Для того чтобы было подольше.
• Засекаем время выполнения нашего расчета.
• Поскольку в F# нет встроенной меморизации, используем самодельную. Она примает как аргумент любую фукцию, инициализирует кеш и создает лямбда-выражение, которое используется для проверки существования элемента в кеше, вызова настоящей функции, если элемент отсутствует, и добавления элемента в кеш.
• Для наглядности я создал отдельную меморизированую функцию memoizedFactorial. Эффект основан на том, что мы определяем фукцию memoizedFactorial без аргументов, а как результат возвращаем другую функцию, которой мы в последствии и будем передавать аргументы. Таким образом у нас получается, что memoizedFactorial существует в единственном экземпляре, как объект и наш кеш будет одним и тем же при множественных вызовах функции.

Давайте теперь посмотрим к чему привела меморизация.
Время выполнения программы без меморизации 28.97 с, а с меморизацией 0.89 с. Как говориться, эффект налицо.

Смотрим во что все это компилируется. Самый интересный момент для C# программиста это конечно момент вызова функции memoizedFactorial. Почему не пересоздается локальный кеш функции?
Давайте смотреть.

Функция main:

public static void main@()
{
    memoizedFactorial@11-1 = LazyExtensions.Create<FSharpFunc<BigInteger, BigInteger>>(new Program.clo@11-1());
    memoizedFactorial@11 = [e-mail]_Value();
    now@18 = DateTime.Now;
    arguments@20 = SeqModule.ToList<BigInteger>(new Program.arguments@20(0, new BigInteger()));
    factorials@21 = ListModule.Map<BigInteger, BigInteger>(Program.memoizedFactorial, Program.arguments);
    timeDiff@23 = (TimeSpan) (DateTime.Now - Program.now);
    fp@1 = new PrintfFormat<FSharpFunc<TimeSpan, Unit>, TextWriter, Unit, Unit, TimeSpan>("Time: %A");
    PrintfModule.PrintFormatLineToTextWriter<FSharpFunc<TimeSpan, Unit>>(Console.Out, Program.fp@1).Invoke(Program.timeDiff);
}

Хм… Функция memoizedFactorial стала отдельным объектом. Кроме того, переменных нет совсем — все они стали полями класса internal static class $Program. В целом с точностью до конкретных классов код должен быть понятен. Углубляемся в memoizedFactorial.

Для начала у нас есть два поля класса $Program:

internal static FSharpFunc<BigInteger, BigInteger> memoizedFactorial@11;
internal static Lazy<FSharpFunc<BigInteger, BigInteger>> memoizedFactorial@11-1;

Видно, что второе инициализируется объектом стандартного класса, в который передается замыкание. Первое же поле не делает ничего интересно, оно просто возвращает само себя (метод get_Value).

Итак, смотрит замыкание:

internal class clo@11-1 : FSharpFunc<Unit, FSharpFunc<BigInteger, BigInteger>>
{
    // Methods
    internal clo@11-1();
    public override FSharpFunc<BigInteger, BigInteger> Invoke(Unit arg00@);
}

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

public override FSharpFunc<BigInteger, BigInteger> Invoke(Unit arg00@)
{
    return Program.memoizedFactorial@11-1();
}

Хм. Выглядит похоже на то что пришли где уже были. Но это не так. Тут возвращается результат вызова функции memoizedFactorial@11-1. Наконец-то смотрим эту функцию:

internal static FSharpFunc<BigInteger, BigInteger> memoizedFactorial@11-1()
{
    return memoize<BigInteger, BigInteger>(new clo@13());
}

Вот! Наконец-то мы добрались до функции memoize. И до еще одного замыкания. Замыкание — это наследник того же класса, смотрим сразу метод Invoke:

public override BigInteger Invoke(BigInteger x)
{
    if (LanguagePrimitives.HashCompare.GenericEqualityIntrinsic<BigInteger>(x, BigInteger.Zero))
    {
        return BigInteger.One;
    }
    return (x * [e-mail]_Value().Invoke(x - BigInteger.One));
}

Вот он наш факториал! Мы нашли функцию, которая непосредственно вычисляет значение. Заметьте, что для рекурсии используется меморизованная версия, как мы и написали в коде на F#. Сравнение с шаблоном конвертировалось в обычный if. Также попутно замечаем, что два BigInteger сравниваются через их хеши.

Вернемся на шаг назад и посмотрим функцию memoize:

public static FSharpFunc<a, b> memoize<a, b>(FSharpFunc<a, b> f)
{
    return new memoize@3<a, b>(f, new Dictionary<a, b>());
}

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

Углубляемся:

internal class memoize@3<a, b> : FSharpFunc<a, b>
{
    // Fields
    public Dictionary<a, b> cache;
    public FSharpFunc<a, b> f;

    // Methods
    internal memoize@3(FSharpFunc<a, b> f, Dictionary<a, b> cache);
    public override b Invoke(a x);
}

Поля класса еще раз показывают почему кеш один на всю программу. Смотрим функцию Invoke:

public override b Invoke(a x)
{
    if (this.cache.ContainsKey(x))
    {
        return this.cache[x];
    }
    b res = this.f.Invoke(x);
    this.cache[x] = res;
    return res;
}

А вот и наша функции меморизации! Ключ передается через агрумент. Замыкание f мы уже знаем через поля объекта. Секрет разгадан.

Таким образом, в F# нет никакой магии. Ну совсем. Все эти currying (а функция memoizedFactorial это оно и есть), функции как first-class citizens на самом деле являются просто автоматически сгенерированными классами и объектами. Надеюсь что моя статья поможет кому-то лучше понять как же работает F# внутри.