19 ноября 2010 в 03:14

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

В предыдущих заметках (часть 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 реализовано через монады, которые в свою очередь являются частью стандартной библиотеки языка, не языка).

Буду рад комментариям и отвечу на вопросы.
+18
4938
42
shai_xylyd 45,0
Похожие публикации

Комментарии (19)

0
EugeneGavrin #
Спасибо )
+2
vanxant #
Не могли бы вы привести пару примеров задач, которые «через монады» решаются проще, чем методами традиционного ООП?
+2
shai_xylyd #
Пара примеров есть в статье: это построение списков и описание асинхронного процесса вычисления.

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

Второй уже серьезно влияет на архитектуру приложения — монады позволяют комбинировать существующие асинхронные методы в новые асинхронные методы, разделяя описание процесса вычисления от самого вычисления. Плюсом является то, что асинхронный код выглядит предельно «синхронно» и императивно. Архитектура приложения, которое ориентировано на использование callback'ов, отличается от такой, где используются монады.

Используя монаду State можно через код неявно протаскивать IoC-контейнер (макро достижение). Через монаду Maybe организовать хотелку C#-программистов оператор "?." (микро достижение).

Simon Peyton Jones написал потрясающую статью про реализацию STM в Haskell через монады — Beautiful concurrency.

Через монады так же реализован Parsec в Haskell — библиотека для удобного описания парсера, когда описание парсера в языке Haskell (то есть его исходный код) максимально приближено к форме БН. Хотя мне больше нравиться подход Nemerle: парсер описывается макросом, который в свою очередь при компиляции генерирует код для разбора.

Про другие применения монад можно почитать в статье Евгения Кирпичева Монады
0
irriss #
Спасибо за статью и ответ.

А как насчет дебага всего этого дела? Могу представить что это адцкий ад наверное?
+1
LexL #
Я бы использовал Nemerle, если бы это был синтаксический суперсет от C#.
Типо языкового расширения…

А так поменяли тип и имя параметра местами в описании функций, выкинули return, другие косметические изменения ради изменений, но не пользы…
0
shai_xylyd #
На самом деле такой синтаксис более продуман, но это не так важно, как возможность использовать преимущества макросов (например, PEG и Computation expressions).

Скоро будет релиз, в котором будет конвертер из C# в Nemerle, а так же возможность компилятором Nemerle компилировать C# файлы. То есть берем проект на C#, а новый функционал пишем уже на Nemerle)
0
LexL #
Возможно новый функционал и продуман, но не базовый.

Базовый функционал надо писать «по-новому».

1) Поменять местами тип и название параметра в описании методов, плюс влепить между ними двоеточие. Разделять запятой, а не точкой с запятой.
3) Заменить угольные скобки на квадратные в описании генериков. Это массив или доступ по индексу?
4) Тип результата функции писать в конце метода, опять через двоеточие. Кроме того, void все еще есть :)
5) Лямбду через минус, а не через знак равно.

Вы хотите сказать, что этим косметическим изменениям есть объяснение, кроме как — мы не хотим, чтобы все было как в C, а хотим чуть-чуть из Pascal?
+1
shai_xylyd #
Конечно есть они более логичны и последовательны.

1. В случае generic-метода у нас вначале идет объявление параметра, а затем его использование:

// Nemerle
public Wrap[T](a : T) : List[T] { ... }
// C#
public List<T> Wrap<T>(T a) { ... }

Объявление переменной с указанием типа или с использованием вывода типа выглядит однородно:

// Nemerle
def a : string = "...";
def a = "...";
// C#
string a = "...";
var a = "...";


2. Ну в C# тоже запятой параметры разделяются.

3. Я не знаю почему, кажется разумной причины нет, но я как то читал, что вроде это устраняет неоднозначности и упрощает парсер языка.

4. Уже в первом пункте раскрыл.

5. Лямбда через знак равно, через минус функциональный тип описывается, например

def a : int -> string = x => x.ToString();
0
LexL #
Вот реально чего не хватает в C#, это такого:
class MyClass 
{
  [MyTransform]  
  public int Property { get; set;}
}

abstract class PropertyTransformAttribute<T>: Attribute
{
   public string PropetyName { get; private set;}  

   public delegate void Setter(object self, ref T oldValue, T newValue);
   public delegate T Getter(object self, T oldValue);

   public virtual Expression<Setter> TransformSetter(Setter setter) { return setter; }
   public virtual Expression<Getter> TransformGetter(Getter getter) { return getter; }  
}

class MyTransformAttribute: TransformAttribute<int>
{

   public override Expression<Setter> TransformSetter(Setter setter) 
   {
      return (sender, ref oldValue, newValue) =>
      {
         if (oldValue == newValue) return;
         oldValue = newValue;
         ((MyClass)sender).RaisePropertyChanged(PropertyName);
      }      
   }
}


И чтобы эта трансформация вызывалась компилятором до codegen…
+1
Meroving #
А разве все эти AOP фреймворки типа postsharp не этим занимаются?
0
LexL #
занимаются, но конкретно с этим примером очень плохо дело обстоит.
глядя в сборку на полученный код, становится тоскливо…

хотелось бы простой трансформатор кода, без всяких AOP наворотов
0
shai_xylyd #
Это можно будет делать, компилятор Nemerle будет понимать и .cs файлы и .n файлы, внутри .cs можно будет использовать макроатрибуты (макросы, которые выглядят как атрибуты, но переписывают код на этапе компиляции.
0
LexL #
Вот это будет здорово!
0
VladD2 #
> Скоро будет релиз, в котором будет конвертер из C# в Nemerle, а так же возможность компилятором Nemerle компилировать C# файлы. То есть берем проект на C#, а новый функционал пишем уже на Nemerle)

Уже есть. В последних инсталляторах уже есть поддержка компиляции C#-файлов. Сейчас уже основные глюки выловлены, так что можно пользоваться (хотя, конечно, какие-то ошибки будут, наверно).
0
VasilioRuzanni #
«но, в отличие от C#, эти языки поддерживают концепцию более высокого уровня, которая позволяет реализовать асинхронные вычисления в стиле async/await в виде библиотеки, а не на уровне языка.»

А что мешает, собственно, в C# это реализовать в виде библиотеки?
0
shai_xylyd #
Не будет поддержки со стороны языка. В ООП стиле можно писать и на C, но отсутствие поддержки со стороны языка делает это дело сложным. Тоже самое и тут.
0
VladD2 #
> А что мешает, собственно, в C# это реализовать в виде библиотеки?

Отсутствие возможности расширять синтаксис. Без сокрытия деталей реализации код будет ужасен и никто не захочет писать такой код.

Для поддержки подобного в C# нужно менять компилятор. Собственно в C# 5.0 и будет введен синтаксис для подержи асинхронного программирования. Но это будет конкретная реализация которая будет гвоздями прибита к языку. В случае Nemerle реализация — это макрос. Его можно подключить в виде библиотеки, а чтобы использовать в конкретном файле проекта нужно еще открыть с помощью using.
0
VoidEx #
> Имя этой концепции — монада.

В тред врывается Haskell-программист!
0
shai_xylyd #
Уже боюсь… надеюсь я монадами ничего не напутал.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.