После анонса C# 5.0 с его async и await, у меня появился небольшой интерес к асинхронному программированию, копание в сторону которого и послужило возникновению данного текста.
В процессе чтения статьи вы узнаете/омните.
Монада по сути состоит из трех частей.
Обычно эти две функции называются return и bind, но в шарпе мы будем их называть To[НазваниеМонады] и SelectMany.
Рассмотрим монаду Maybe, брата близнеца Nullable. Контейнер который либо может содержать значение, либо ни содержит ничего.
Одно из полезных свойств данной монады, если где-то в выражении встретился Nothing то и все выражение будет Nothing.
Вот две наши функции.
С ToMaybe все понятно, с SelectMany вроде тоже, берем контейнер m, и применяем к его содержанию функцию k если есть значение.
Допустим мы хотим сложить два числа
Видим что перед тем как складывать нам пришлось с помощью SelectMany дважды вытащить значения из контейнера. Что бы избавиться от нагромождения функция, в некоторых языках существует сахар, в Haskell do нотация, F# computation expressions, ну а мы можем вспомнить что выражение
Это
То есть реализовав дополнительный SelectMany вида
который как раз в себе и содержит то самое двойное раскрытие контейнеров, может записывать операции с Maybe в виде.
CPS по сути есть работа с колбеками, то есть вместо того что бы использовать нормальный порядок вычисления
У каждой функции появляется дополнительный параметр, в который мы передаем функцию для продолжения вычисления.
Часто используется если функция делаю асинхронный запрос куда то и мы не хотим что бы поток простаивал или фризилась gui.
Смешав монаду и CPS получим
Более менее стандартный вариант монады, это функция которая на вход принимает другую функцию, ограничимся простым случаем когда на выходе у продолжения void. Тогда монаду можно представить в виде такой делегаты.
Функции на вход подается функция k (продолжение), в которую уже передается нечто типа Т. Вот наши знакомые три функции.
ToCont — в продолжение k просто передаем значение. SelectMany — вытаскиваем r из монады, передаем в функцию f и вызываем новую монаду с общим продолжение k.
Самое время вспомнить что такое Task. Это контейнер, который в себе содержит некое действие, результат которого можно получить как с помощью свойства Result заблокировав поток, так и в CPS использую метод ContinueWith.
Создаем задачу.
Получаем результат
Раз в Task есть CPS можно попробовать одно преобразовать в другое.
Допустим у нас имеются три асинхронных сервиса. Получить контент старницы по урл, перевести текст и сделать анализ текста результат которого будет число.
Представим в уме как будет выглядеть проход по этим трем функциям в CPS, ужаснемся и сразу воспользуемся линком, преобразовав задачи в монады.
Если нам где то еще понадобиться получить переведенную страницу по урлу, может это вынести в отдельный метод
Так как везде используется ToCont, то почему бы не попробовать избавиться от лишней сущности.
Unwrap нужен что бы развернуть тип
Теперь убрав все ToCont, можно получить тот же самый результат.
Итого, можно считать что Task по сути и есть монада продолжения.
Ну и например напишем функцию которая возвращает для списка урлов, список значений Analyse. Подумайте как бы оно выглядело в CPS.
ContinueWhenAll — ждем когда завершатся все задачи, что бы получить все результаты.
Вряд ли все это имеет хоть какой нибудь практический смысл, поэтому данный текст можно рассматривать как информацию к размышлению из разряда ненормального программирования. Также все желающие могут поразмышлять на тему интерфейсов IObservable и IObserver и метода IObserver.OnNext(T value)
PS По хорошему тут бы не помешало как то затронуть те самые async с await, но желание ставить ctp у меня нет, поэтому о них у меня имеются достаточно поверхностные представления, но думаю суть там не сильно отличается от вышеизложенного, то есть идет та же работа с задачами но вместо линка используется преобразование потока вычисления с помощью компилятора.
В процессе чтения статьи вы узнаете/омните.
- Что есть монада на примере Maybe.
- Что такое CPS и монада продолжения.
- Как это связать с классом Task из TPL.
Монады
Монада по сути состоит из трех частей.
- Контейнер который содержит в себе нечто.
- Функция с помощью которой можно нечто поместить в контейнер.
- Функция которая позволяет нечто вытащить из контейнера и применить другую функцию которая вернет новый контейнер.
Обычно эти две функции называются return и bind, но в шарпе мы будем их называть To[НазваниеМонады] и SelectMany.
Maybe монада
Рассмотрим монаду Maybe, брата близнеца Nullable. Контейнер который либо может содержать значение, либо ни содержит ничего.
public class Maybe<T> {
public static readonly Maybe<T> Nothing = new Maybe<T>();
public T Value { get; private set; }
public bool HasValue { get; private set; }
private Maybe() {
HasValue = false;
}
public Maybe(T value) {
Value = value;
HasValue = true;
}
public override string ToString() {
if(HasValue)
return Value.ToString();
return "Nothing";
}
}
Одно из полезных свойств данной монады, если где-то в выражении встретился Nothing то и все выражение будет Nothing.
Вот две наши функции.
public static class MaybeEx {
public static Maybe<T> ToMaybe<T>(this T value) {
return new Maybe<T>(value);
}
public static Maybe<U> SelectMany<T, U>(this Maybe<T> m, Func<T, Maybe<U>> k) {
if (m.HasValue)
return k(m.Value);
return Maybe<U>.Nothing;
}
}
С ToMaybe все понятно, с SelectMany вроде тоже, берем контейнер m, и применяем к его содержанию функцию k если есть значение.
Допустим мы хотим сложить два числа
var a = 1.ToMaybe();
var b = Maybe<int>.Nothing;
Func<int, Maybe<int>> k = x => b.SelectMany(y => (y + x).ToMaybe());
var result = a.SelectMany(k); //result == Nothing, если заменить b = 2.ToMaybe() получим 3
Видим что перед тем как складывать нам пришлось с помощью SelectMany дважды вытащить значения из контейнера. Что бы избавиться от нагромождения функция, в некоторых языках существует сахар, в Haskell do нотация, F# computation expressions, ну а мы можем вспомнить что выражение
from x in a
from y in b
select x + y;
Это
a.SelectMany(x => b, (x, y) => x + y);
То есть реализовав дополнительный SelectMany вида
public static Maybe<V> SelectMany<T, U, V>(
this Maybe<T> m, Func<T, Maybe<U>> k, Func<T, U, V> s) {
return m.SelectMany(x => k(x).SelectMany(y => s(x, y).ToMaybe()));
}
который как раз в себе и содержит то самое двойное раскрытие контейнеров, может записывать операции с Maybe в виде.
var result =
from x in 1.ToMaybe()
from y in 2.ToMaybe()
select x + y;
CPS (Continuation-passing style)
CPS по сути есть работа с колбеками, то есть вместо того что бы использовать нормальный порядок вычисления
var x = GetPage("http://habrahabr.ru");
var y = Translate(x);
Display(y);//пусть Display это Console.WriteLine
У каждой функции появляется дополнительный параметр, в который мы передаем функцию для продолжения вычисления.
GetPage("http://habrahabr.ru",
x => Translate(x,
y => Display(y)));
Часто используется если функция делаю асинхронный запрос куда то и мы не хотим что бы поток простаивал или фризилась gui.
Смешав монаду и CPS получим
Монада продолжения
Более менее стандартный вариант монады, это функция которая на вход принимает другую функцию, ограничимся простым случаем когда на выходе у продолжения void. Тогда монаду можно представить в виде такой делегаты.
public delegate void Cont<T>(Action<T> k);
Функции на вход подается функция k (продолжение), в которую уже передается нечто типа Т. Вот наши знакомые три функции.
public static class ContEx {
public static Cont<T> ToCont<T>(this T value) {
return k => k(value);
}
public static Cont<T1> SelectMany<T, T1>(this Cont<T> c, Func<T, Cont<T1>> f) {
return k => c(r => f(r )(k));
}
public static Cont<T2> SelectMany<T, T1, T2>(this Cont<T> c, Func<T, Cont<T1>> f, Func<T, T1, T2> s) {
return c.SelectMany(x => f(x).SelectMany(y => s(x, y).ToCont()));
}
}
ToCont — в продолжение k просто передаем значение. SelectMany — вытаскиваем r из монады, передаем в функцию f и вызываем новую монаду с общим продолжение k.
Task
Самое время вспомнить что такое Task. Это контейнер, который в себе содержит некое действие, результат которого можно получить как с помощью свойства Result заблокировав поток, так и в CPS использую метод ContinueWith.
Создаем задачу.
var task = Task<int>.Factory.StartNew(() => 10); //вернуть число 10
Получаем результат
task.ContinueWith(task => Display(task.Result));
Раз в Task есть CPS можно попробовать одно преобразовать в другое.
public static Cont<T> ToCont<T>(this Task<T> task) {
return k => task.ContinueWith(task => k(task.Result));
}
Пример задачи
Допустим у нас имеются три асинхронных сервиса. Получить контент старницы по урл, перевести текст и сделать анализ текста результат которого будет число.
public static Task<string> GetPage(string url) {
return Task<string>.Factory.StartNew(() => {
Console.WriteLine("get page start " + url);
Thread.Sleep(3000);
Console.WriteLine("get page complete");
return "page content";
});
}
public static Task<string> Translate(string text) {
return Task<string>.Factory.StartNew(() => {
Console.WriteLine("translate start");
Thread.Sleep(3000);
Console.WriteLine("translate complete");
return "text translation";
});
}
public static Task<int> Analyse(string text) {
return Task<int>.Factory.StartNew(() => {
Console.WriteLine("analyse start");
Thread.Sleep(3000);
Console.WriteLine("analyse complete");
return 100;
});
}
Представим в уме как будет выглядеть проход по этим трем функциям в CPS, ужаснемся и сразу воспользуемся линком, преобразовав задачи в монады.
var result =
from x in GetPage("www.example.com").ToCont()
from y in Translate(x).ToCont()
from z in Analyse(y).ToCont()
select z;
result(Display);
Если нам где то еще понадобиться получить переведенную страницу по урлу, может это вынести в отдельный метод
private static Cont<string> GetPageTranslation(string url) {
return
from x in GetPage(url).ToCont()
from y in Translate(x).ToCont()
select y;
}
var result =
from x in GetPageTranslation("http://habrahabr.ru")
from a in Analyse(x).ToCont()
select a;
result(Display);
Так как везде используется ToCont, то почему бы не попробовать избавиться от лишней сущности.
public static Task<T1> SelectMany<T, T1>(this Task<T> c, Func<T, Task<T1>> f) {
return c.ContinueWith(task => f(task.Result)).Unwrap();
}
public static Task<T2> SelectMany<T, T1, T2>(this Task<T> c, Func<T, Task<T1>> f, Func<T, T1, T2> s) {
return c.ContinueWith(t => f(t.Result).ContinueWith(x => s(t.Result, x.Result))).Unwrap();
}
Unwrap нужен что бы развернуть тип
Task<Task<T>>
который получается при соединении двух задач.Теперь убрав все ToCont, можно получить тот же самый результат.
private static Task<string> GetTranslation(string url) {
return
from x in GetPage(url)
from y in Translate(x)
select y;
}
Итого, можно считать что Task по сути и есть монада продолжения.
Ну и например напишем функцию которая возвращает для списка урлов, список значений Analyse. Подумайте как бы оно выглядело в CPS.
private static Task<IEnumerable<int>> Analyse(IEnumerable<string> list) {
var result =
from url in list
select
from x in GetTranslation(url)
from a in Analyse(x)
select a;
return Task.Factory.ContinueWhenAll(result.ToArray(), x => x.Select(y => y.Result));
}
ContinueWhenAll — ждем когда завершатся все задачи, что бы получить все результаты.
var urls = new[] {"url1", "url2", "url3"};
var r = Analyse(urls);
r.ContinueWith(x => Console.WriteLine(x.Result.Sum()));
Заключение
Вряд ли все это имеет хоть какой нибудь практический смысл, поэтому данный текст можно рассматривать как информацию к размышлению из разряда ненормального программирования. Также все желающие могут поразмышлять на тему интерфейсов IObservable и IObserver и метода IObserver.OnNext(T value)
PS По хорошему тут бы не помешало как то затронуть те самые async с await, но желание ставить ctp у меня нет, поэтому о них у меня имеются достаточно поверхностные представления, но думаю суть там не сильно отличается от вышеизложенного, то есть идет та же работа с задачами но вместо линка используется преобразование потока вычисления с помощью компилятора.