Язык F# появился в стандартной поставке VisualStudio совсем недавно, а именно с версии 2010 (на данный момент самой что ни на есть актуальной). Естественно, и все это прекрасно знают, язык функционирует на основе CLR — весь ваш код будет скомпилирован в MS IL как и любой другой язык .NET семейства.
Давайте на примере часто используемой и полезной техники «меморизация» посмотрим во что превращает ваш код компилятор. Для наглядности я буду писать сам код на F# и декомпилировать его в C#.
Итак, исходный пример:
Несколько пояснений:
Давайте теперь посмотрим к чему привела меморизация.
Время выполнения программы без меморизации 28.97 с, а с меморизацией 0.89 с. Как говориться, эффект налицо.
Смотрим во что все это компилируется. Самый интересный момент для C# программиста это конечно момент вызова функции
Давайте смотреть.
Функция
Хм… Функция
Для начала у нас есть два поля класса
Видно, что второе инициализируется объектом стандартного класса, в который передается замыкание. Первое же поле не делает ничего интересно, оно просто возвращает само себя (метод
Итак, смотрит замыкание:
Понимаем, что это класс у которого есть интересный метод:
Хм. Выглядит похоже на то что пришли где уже были. Но это не так. Тут возвращается результат вызова функции
Вот! Наконец-то мы добрались до функции
Вот он наш факториал! Мы нашли функцию, которая непосредственно вычисляет значение. Заметьте, что для рекурсии используется меморизованная версия, как мы и написали в коде на F#. Сравнение с шаблоном конвертировалось в обычный
Вернемся на шаг назад и посмотрим функцию
Вот, началось самое интересное. Как результат работы возвращается объект в параметры конструктора которого передается наше замыкание (первый аргумент) и словарь (второй аргумент). Теперь понятно почему словарь не пересоздается каждый раз.
Углубляемся:
Поля класса еще раз показывают почему кеш один на всю программу. Смотрим функцию
А вот и наша функции меморизации! Ключ передается через агрумент. Замыкание
Таким образом, в F# нет никакой магии. Ну совсем. Все эти currying (а функция
Давайте на примере часто используемой и полезной техники «меморизация» посмотрим во что превращает ваш код компилятор. Для наглядности я буду писать сам код на 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 = Program.memoizedFactorial@11.get_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 * Program.memoizedFactorial@11.get_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# внутри.