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

    После анонса 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 у меня нет, поэтому о них у меня имеются достаточно поверхностные представления, но думаю суть там не сильно отличается от вышеизложенного, то есть идет та же работа с задачами но вместо линка используется преобразование потока вычисления с помощью компилятора.
    Share post

    Similar posts

    Comments 20

      0
      Это же перевод, кмк, потому как я уже читал почти слово в слово такую же статью где-то.
        0
        Вы могли еще читать здесь же, месяц назад. В прошлой версии в ней содержалась ссылка на сайт который нельзя называть, поэтому меня забанили. Эта версия уже без ссылки.
          0
          Точно:) Спасибо, классная статья
          • UFO just landed and posted this here
          +1
          1. МонадА по сути состоит из трех частей.

          2.… ну а мы можно вспомнить что выражение…
            0
            Если честно, я бы вообще не вспоминал про монады в данном случае.

            Проще было бы показать CPS на примерах, потом заметить, что одна операция (композиция функций в cps) повторяется очень часто и выделить ее в функцию (которая в Cont называется bind).

            Радует, что широкие массы потихоньку просвещаются. :)

            PS: кстати, может быть. кого-нибудь заинтересует Arrowlets, там тоже скрывается plumbing (в неместном жаргоне можно сказать «абстрагируется поток управления»), только немного по-другому
              +2
              перевод просто T________________T
                0
                «Тогда монаду можно представить в виде такой делегаты.» :D
                  0
                  Что не так?
                    +1
                    Как монаду можно представить в виде «делегаты»? Делегат — это просто функция по сути :)
                      0
                      newtype Cont r a = Cont { runCont :: (a -> r) -> r }
                      В чем вам видеться разница runCont и просто функции?
                        +1
                        То, что вы привели — хаскельное определения record'а, с полем типа ((a -> r) -> r), для получения которого создаётся функция-акцессор ``runCont`` с сигнатурой (Cont r a -> ((a -> r) -> r)).

                        Исходная фраза такова: «Тогда монаду можно представить в виде такой делегаты». Вы меня извините, но это звучит как полный бред. Не «монаду» можно представить в виде «делегаты», а тип вычисления в монаде Cont можно представить в виде типа делегата .NET.
                          0
                          То есть, выражение
                          монаду Cont можно представить в виде newtype Cont r a = Cont { runCont :: (a -> r) -> r }
                          некорректное?
                            +1
                            Некорректное. Монада — это _тип_вычисления_ (Cont<T>, IEnumerable<T> и т.п.) и две функции: возврата тривиального вычисления (return) и композиции вычислений (bind). То есть монада — это тройка из одного типа и двух функции.

                            А вот newtype Cont r a = Cont { runCont :: (a -> r) -> r } — это _тип_монадического_вычисления_, часть этой тройки. Это нельзя называть самой «монадой».

                            IEnumerable<T> — это не монада, это опять же тип вычисления внутри монады Linq to Objects, тип монадического вычисления.
                              –1
                              Теперь я понял о чем вы, да это было бы более корректно, но я в начале сказал что она состоит их трех частей, поэтому думаю из контекста должно быть понятно о чем речь.
                +2
                Почему-то мне выражение
                GetPage("http://habrahabr.ru", 
                    x => Translate(x, 
                        y => Display(y)));
                


                как-то понятней чем
                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);
                


                но может это просто слегка другой способ записи…

                Хотя, как мне кажется, где-то был тоже красивый вариант с помощью хелпер-класса «AndThen». Там выходило что-то вроде:
                Async.Do(GetPage('...')).AndThen(Tranlsate).AndThen(Analyze).AndThen(Display);
                

                … или это просто подумалось что это реально можно реализовать…
                *запускаю студию и засучиваю рукава* :)
                  +1
                  а скажите пожалуйста, в коде вида a => a(...) используется анонимная рекурсия?
                  К примеру:
                  public static Cont<T> ToCont<T>(this Task<T> task) {
                  	return k => task.ContinueWith(task => k(task.Result));
                  }


                  Статья понравилась, но вот такие моменты не понял.
                    0
                    Нет. k — это просто некая функция колбек, протаскиваемая через выражения.
                    Например
                    var task = Task<int>.Factory.StartNew(() => 10);
                    var cont = task.ToCont();
                    Action<int> k = x => Display(x);
                    cont(k);
                    //Тут нет никакой рекурсии.
                    k => task.ContinueWith(task => k(task.Result));// k == Display
                    //->
                    task.ContinueWith(task => Display(task.Result))
                    

                      0
                      разобрался. в том случае это просто аргумент возвращаемой лямбды.
                      не знаю я .NET'а =)
                    0
                    Как-то у меня с монадой Maybe сложилось по-другому, а именно так. Основное с чем я не согласен — это с созданием своего типа а-ля option<'t>, т.к. вместо него можно использовать null.

                    Only users with full accounts can post comments. Log in, please.