Pull to refresh

Linq To Tasks и монада продолжения

Reading time 6 min
Views 4.4K
После анонса C# 5.0 с его async и await, у меня появился небольшой интерес к асинхронному программированию, копание в сторону которого и послужило возникновению данного текста.
В процессе чтения статьи вы узнаете/омните.
  • Что есть монада на примере 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 у меня нет, поэтому о них у меня имеются достаточно поверхностные представления, но думаю суть там не сильно отличается от вышеизложенного, то есть идет та же работа с задачами но вместо линка используется преобразование потока вычисления с помощью компилятора.
Tags:
Hubs:
+20
Comments 20
Comments Comments 20

Articles