Pull to refresh

Асинхронное программирование и Computation Expressions

Programming *
В предыдущих заметках (часть I, часть II) об async/await в C# 5 я написал, что подобный подход реализован в таких языках, как Haskell, F# и Nemerle, но, в отличие от C#, эти языки поддерживают концепцию более высокого уровня, которая позволяет реализовать асинхронные вычисления в стиле async/await в виде библиотеки, а не на уровне языка. Забавно, что в Nemerle сама эта концепция реализована в виде библиотеки. Имя этой концепции — монада. Помимо асинхронных вычислений монады позволяют реализовать другие вкусности, такие как list comprehension, continuation, превращение грязных функций в чистый блок, через который неявно протаскивается состояние, и множество других.

Некоторые монады реализуют такие «хотелки» C# программистов, как yield коллекции или yield foreach и yield из лямбда выражения.

Цель этой заметки — введение в асинхронное программирование и computation expressions в Nemerle, но она так же может быть полезна тем, кто изучает F#, так так реализация асинхронного программирования в Nemerle была сделана с оглядкой на него в F#. С другой стороны, кому-нибудь может быть интересно, как некоторые задачи, которые являются проблемой в других языках (После всех асинхронных вызовов), решаются с помощью computation expressions в пару строк.

Наверное, каждый, кто осознал что такое монада, пишет статью о том, что такое монада. Не стал исключением и я. Постараюсь сделать описание максимально сжато, чтобы те, кто знают вспомнили, а другие смогли понять дальнейшее повествование.

Монады


Монада является порождающим паттерном, поддержка которого встроена в язык. В основе реализации этого паттерна следующая пара:

полиморфный тип

interface F<T> {
...
}

и пара операций над ним

class M {
  static public F<T> Return<T>(T obj) { ... }
  static F<U> Bind<T,U>(F<T> obj, Func<T, F<U>> fun) { ... }
}

Return позволяет «завернуть» любое значение в монаду, а Bind проводить над ней трансформации. Очень слабую аналогию можно провести с StringBuilder, которому в параметре конструктора передаем начальное значение, а затем методами Append* его изменяем.

Если заменить F на IEnumerable, то сигнатура Bind напоминает сигнатуру SelectMany из Linq. Это не удивительно, так как Linq с большими оговорками тоже является монадой. Об этом, кстати, интересно рассказывал Bart De Smet на PDC2010 с докладом «LINQ, Take Two – Realizing the LINQ to Everything Dream» (ссылка).

Если Linq является монадой, то попробуем оформить простое Linq выражение:

var nums = Enumerable.Range(-2, 7);
var sqrt = from n in nums where n >=0 select Math.Sqrt(n);

с помощью M-операций. В начале объявим M-операции:

static class MList
{
    static public IEnumerable<T> Return<T>(T obj) 
    { 
        var list = new List<T>();
        list.Add(obj);
        return list;
    }
    static public IEnumerable<U> Bind<T, U>(this IEnumerable<T> obj, Func<T, IEnumerable<U>> fun) 
    {
        return obj.SelectMany(fun);
    }
    static public IEnumerable<T> Empty<T>()
    {
        return Enumerable.Empty<T>();
    }
}

И перепишем Linq выражение:

var nums = Enumerable.Range(-2, 7);
var sqrt = nums
    .Bind(n => n >= 0 ? MList.Return(n) : MList.Empty<int>())
    .Bind(n => MList.Return(Math.Sqrt(n)));

Получилось даже хуже, чем с Linq, но это вызвано тем, что поддержка монад не встроена в C#. В случае Nemerle это код можно следующим образом, объявляем M-операции:

class MList
{
  public Return[T](obj : T) : IEnumerable[T]
  { 
    def data = List();
    data.Add(obj);
    data
  }
  public Bind[T, U](obj : IEnumerable[T], f : T->IEnumerable[U]) : IEnumerable[U]
  {
    obj.SelectMany(f)
  }
  public Empty[T]() : IEnumerable[T]
  {
    Enumerable.Empty()
  }
}

И переписываем Linq выражение:

def mlist = MList();
def nums = Enumerable.Range(-2, 7);
def sqrt = comp mlist 
{
  defcomp n = nums;
  defcomp n = if (n >= 0) mlist.Return(n) else mlist.Empty();
  return Math.Sqrt(n :> double);
};

В начале вспомним, что def в Nemerle — немьютабельный аналог var в C#, if — тернарная оператор (?:), а вызов конструктора не требует new. Теперь к делу, оператор comp объявляет начало монадических вычислений, следующий за ним параметр предоставляет M-операции, а затем идут собственно вычисления.

По сравнению с Linq мы имеем три строчки, вместо одной, но эти строки выглядят как обыкновенный код, который работает с одной переменной, а фактически он порождает новую коллекцию из исходной. Этот пример приведен в учебных целях, ниже будут примеры, которые повторить обычным кодом очень сложно. Разберемся как он работает.

defcomp — магический оператор, который «превращает» монаду (в данном случае типа IEnumerable[T]) в значение (типа T), а return, наоборот, переводит значение в монаду. На самом деле, никакой магии нет, просто выражение

defcomp n = nums;
...

раскрывается компилятором в

mlist.Bind(nums, n => ...)

Computation expressions


Если бы мы обсуждали язык Haskell, то на этом рассказ про монады можно было закончить. Но в случае с гибридными языками (функциональные/императивные) дело обстоит немного сложнее, так как в них существуют такие управляющие конструкции как операторы условия, циклы и yield. Чтобы понять, как это представляет проблему, можно попытаться выразить через M-операции монадические вычисления, которые содержат цикл, а внутри цикла оператор defcomp.

Решение этой проблемы достаточно простое, нужно добавить в набор M-операций методы, которые занимаются трансформацией операторов ветвления и циклов, например While будет иметь следующую сигнатуру:

public F<FakeVoid> While<T>(Func<bool> cond, Func<F<FakeVoid>> body)

И когда компилятор встретит цикл, тело которого содержит монадические операторы, то он в начале трансформирует тело цикла в цепочку Bind, так как Bind возвращает F<T>, то эту цепочку можно завернуть в лямбду "() => body()", типа Func<F<T>>, так же компилятор заворачивает в лямбду условие цикла, а затем передает эти лямбды M-операции While.

Каждая M-операция должна возвращать монаду, но цикл ничего не возвращает, следовательно нет и значения, которое можно завернуть в монаду. Для этих целей используется сингелтон типа FakeVoid.

Теперь можно дать неформальное описание computation expression, это монада для императивных языков. В случае a-la haskell, компилятор переписывает только defcomp и return внутри монадических вычислений, как уже было замечено в случае императивных языков переписываются и управляющие конструкции, в таблице ниже перечисленные все операторы, которые переписываются:
defcomp разворачивает монаду в значение, по смыслу близко к присваиванию
callcomp разворачивает монаду, используется, когда значение не важно
return заворачивает аргумент в монаду, используется в конце блока монадических вычислений, по смыслу близко к возвращению из функции
returncomp аргумент — монада, возвращает эту монаду как результат блока монадических вычислений, в отличии от return не заворачивает её повторно
yield заворачивает аргумент в монаду и производит действия, аналогичные yield return
yieldcomp аргумент — монада, производит действия, аналогичные yield return, в отличии от yield не заворачивает аргумент повторно
if, when, unless, while, do, foreach, for, using, try...catch...finally монадические версии обыкновенных управляющих конструкций

Еще пара слов про провайдеры M-операций. Официально они называются билдерами и при построении computation expression используется используется утиная типизация, то есть билдеры должны содержать методы, которые использует компилятор, но билдер не обязан реализовывать какой-либо интерфейс. Это решение позволяет реализовывать билдеры частично, если в computation expression планируется использовать не все возможности. Кстати, такой подход мы уже использовали, создавая MList билдер (реализована поддержка только defcomp и return).

Другая причина, почему не используются интерфейсы, в том, что они накладывают более строгое условие на сигнатуру M-операций. Требуется только совместимость монад и M-операций по типу. Например, в примерах выше предполагалось, что монада имеет один generic-параметер, но она запросто может иметь их несколько, для дальнейшего повествования это не важно, но это можно изучить на примере монады Continuation.

Для тех, кто хочет писать свои билдеры, лучший совет — изучать исходники Computation expressions.

Примеры стандартных билдеров



Стандартные билдеры встроены в библиотеку Computation Expressions и вместо того, что бы создать их экземпляр и передать comp как параметр, достаточно передать в качестве параметра их имя.

List

Билдер list поддерживает стандартные управляющие конструкции языка, а так же yield и yieldcomp. В качестве монады использует list[T] (стандартный список в Nemerle). Данный билдер интересен тем, что реализует две давние «хотелки» C# программистов: yield из лямбды и yield коллекции. В начале посмотрим на аналог Linq запроса из начала статьи:

def num = Enumerable.Range(-2, 7);
def sqrt : list[double] = comp list 
{
  foreach(n in num)
    when(n >= 0)
      yield Math.Sqrt(n);
}

Как видно, билдер list позволяет использовать yield выражения по месту не требуя объявлять для этого функцию, так же его можно использовать вместо Link to objects. Мне кажется, что этот код читать намного проще, чем эквивалентное linq выражение.

Рассмотрим теперь другую «хотелку» — yield коллекции, в начале я объявляю локальную функцию, которая генерирует последовательность, а затем два раза её вызываю и делаю yield коллекций.


def upTo(n)
{
  comp list { for(mutable i=0;i<n;i++) yield i }
}
def twice = comp list
{
  repeat(2) yieldcomp upTo(3);
}
Console.WriteLine(twice);
//[0, 1, 2, 0, 1, 2]

Мне пришлось написать свой генератор, а не использовать «Enumerable.Range(0, 3)» из-за типов: yieldcomp ожидает на вход монаду, её тип в данном случае list[int], а «Enumerable.Range(0, 3)» возвращает IEnumerable[int]. Что бы преодолеть это несоответствие существует другой билдер — enumerable.

Enumerable

Этот билдер во многом повторяет билдер List, только использует IEnumerable[T] как тип монады и позволяет строить бесконечные последовательности. Перепишем последний пример:

def twice = comp enumerable
{
  repeat(2) yieldcomp Enumerable.Range(0, 3);
}
foreach(item in twice) Console.Write($"$item ");
//0, 1, 2, 0, 1, 2 

Array

Аналогично list и enumerable ведет себя array, только использует array[T] в качестве типа монады.

Async

Самый сложный, но очень полезный билдер, во многом напоминает будущий async/await в C#. Он используется для построения асинхронных вычислений, комбинируя уже существующие асинхронные вычисления.

Он поддерживает все операции, кроме yield и yieldcomp.

Тип монады этого билдера — Async[T]. Объекты этого типа описывают асинхронное вычисление, результатом которой будет значение типа T (подобно Task<T> в C#), если асинхронная операция не возвращает значение, то вместо T используется конкретный тип FakeVoid. Операция Bind, её тип Async[T]*(T->Async[U])->Async[U], «продолжает» асинхронное вычисление (типа Async[T]) функцией, эта функция берет на вход объект типа T (результат асинхронного вычисления) и возвращает новое асинхронное вычисление типа Async[U].

Другим ключевым типом является абстрактный класс ExecutionContext, экземпляры его потомков отвечают за запуск асинхронной операции (например, в текущем потоке, в потоке из ThreadPool'а или используя SynchronizationContext), вот его сигнатура:

public abstract class ExecutionContext
{
  public abstract Execute(computatuion : void -> void) : void;
}

Для запуска асинхронной операции нужно вызвать метод Start объекта описывающего асинхронную операцию (класс Async[T]), передав ему объект типа ExecutionContext, если метод вызван без аргументов, то асинхронная операция запускается используя ThreadPool.QueueUserWorkItem.

В расширении (async CTP), которое позволяет использовать реализацию async/wait в C# уже сегодня идет множество методов расширений, которые дополняют существующие классы асинхронными операциями. В библиотека с реализацией монады async не предоставляет таких расширений, но зато предоставляет простой способ их построить на основе уже существующих примитивов. Например, рассмотрим часть существующей сигнатуры HttpWebRequest, отвечающей за асинхронное выполнение запроса, существующего с первой версии framework'а:

public class HttpWebRequest : WebRequest, ISerializable
{
  public override IAsyncResult BeginGetResponse(AsyncCallback callback, object state);
  public override WebResponse EndGetResponse(IAsyncResult asyncResult);
}

Теперь создадим асинхронное расширение, которое подходит для использования в монадических вычислениях, используя эти примитивы.

public module AsyncExtentions
{
  public GetResponseAsync(this request : HttpWebRequest) : Async[WebResponse]
  {
    Async.FromBeginEnd(request.BeginGetResponse(_, null), request.EndGetResponse(_))
  }
}

Следует напомнить, что _ в Nemerle особый символ, в данном случае через него используется каррирование (запись f(_) эквивалентна x => f(x)). Подобным образом можно создавать обертки для любых стандартных асинхронных вычислений.

Попробуем на Nemerle написать что-нибудь из (C# 101) Async samples, например, параллельную загрузку нескольких веб страниц и печать заголовка, я опустил код расширения GetHtml() и GetTitle(), статья и так уже затянулась.

public PrintTitles() : Async[FakeVoid]
{
  comp async
  {
    def response1 = HttpWebRequest.Create("http://www.ya.ru").GetResponseAsync();
    def response2 = HttpWebRequest.Create("http://www.habr.ru").GetResponseAsync();
    defcomp response1 = response1;
    defcomp response2 = response2;
    Console.WriteLine(response1.GetHtml().GetTitle());
    Console.WriteLine(response2.GetHtml().GetTitle());
  }
}

В первых двух строчках запускаются асинхронные операции загрузки страниц, эти методы возвращают объекты описывающие асинхронные операции в момент выполнения, с точки зрения компилятора тип этих объектов Async[WebResponce] (монада). В следующих двух строчках происходит раскрытие монады в значение, на другом уровне смысла это означает ожидание результатов. В последних строчках происходит обработка результатов.

Забавно, что пост-рассуждение о том, как правильно это (дождаться результатов всех асинхронных вызовов) сделать в javascript оказался очень горячим: 90 добавлений в избранное, 100 комментариев. Но вернемся к нашему примеру.

Главное, что нужно вспомнить, что монада это порождающий паттерн, вы создали функцию описывающую асинхронное вычисление, но не запускающее его, запустить его можно так PrintTitles().Start().GetResult(). На самом деле это очень важно, так как это может служить источником ошибок, если метод возвращает Async[T], нужно отдавать отчет в том, запускает ли этот код вычисления или только их конструирует. Для различия, наверное, стоит использовать соглашение на именование, например методы, которые запускают вычисления должны иметь суффикс Async.

Во второй своей статье об async/await в C# я писал, что обработку результатов асинхронных вычислений await запускает в SynchronizationContext'е потока которое запустил асинхронные вычисления. В Nemerle в этом отношении предусмотрена большая гибкость, есть возможность переносить вычисления с одного потока на другой. Рассмотрим обработчик нажатия кнопки:

private button1_Click (sender : object,  e : System.EventArgs) : void
{
  def formContext = SystemExecutionContexts.FromCurrentSynchronizationContext();
  def task = comp async
  {
    Thread.Sleep(5000);
    callcomp Async.SwitchTo(formContext);
    label1.Text = "success";
  }
  _ = task.Start(SystemExecutionContexts.ThreadPool());
}

В начале мы получает ExecutionContext, который запускает вычисления в текущем SynchronizationContext, затем мы описывает асинхронную операцию: Thread.Sleep эмулирует тяжелое вычисление, переключаем execution context на execution context gui потока и выводим результат. Само вычисление запускаем в ExecutionContexts пула потоков.

Выглядит как магия, но на самом деле все это уже было, callcomp просто раскрывает монаду, когда её значение не важно. Но зачем её тогда вообще раскрывать? Дело в побочных эффектах и состоянии, на протяжении монадических операций через них протаскивается состояние, монада в момент раскрытия имеет доступ к этому состоянию и может его изменить, что здесь и происходит. В этом примере состояние хранит информацию в каком контексте выполнять код, и в случае изменения этой информации, переключается на новый контекст. За подробностями могу порекомендовать пойти почитать исходники, они интересные.

Помимо Async.SwitchTo есть и другие интересные монады влияющие на поток выполнения, например, Async.Yield говорит, что execution context изменился, хотя не меняет его. В некоторых случаях это ничего не делает, в случае, когда использовался ThreadPool, это действие провоцирует прыжок на другой поток из пула.

Заключение


В заключении могу только отметить, что монады это очень богатая тема. В этой статье я не затронул таких классических монад как State, Cont (continuation), Maybe (другая «хотелка» C# fanboy). О них можно почитать во других статьях, я постарался дать практическое объяснение, благодаря которому можно начать использовать асинхронное программирование и монады list/enumerable в Nemerle и знать, что происходит под капотом.

Во многом реализация await/async в будущем C# и монадический подход к асинхронному программированию в Nemerle похожи, но есть одно замечание для поддержки await/async необходима следующая версия языка, а асинхронное программирование в Nemerle реализовано через монады, которые в свою очередь являются частью стандартной библиотеки языка, не языка).

Буду рад комментариям и отвечу на вопросы.
Tags:
Hubs:
Total votes 32: ↑25 and ↓7 +18
Views 14K
Comments Comments 19