Асинхронный вызов

Куча разнообразных программных интерфейсов предоставляет возможность осуществлять асинхронные вызовы чего-либо. К сожалению, иногда есть возможность осуществлять только асинхронные вызовы. Этим разработчикам нужно выразить отдельную благодарность, но иногда даже с идеальным фундаментом можно побороться выстраивая кривое здание.
Именно это здание мы и будем сейчас выстраивать.

Как же именно можно осуществлять подобные вызовы? Мне пришло в голову следующее шаманство:
Создадим объект, в который будем складывать последовательно функции, которые необходимо вызвать, а по завершению коллбэка вызывать на исполнение следующую функцию.
Что нам понадобится?

• Массив, чтобы в нём хранить функции
• Добавление функции в массив
• Исполнение текущей функции
• Индикатор, для того, чтобы понимать, когда-же закончился коллбэк.

У меня получилось вот такое прелестное чудо:

function SyncSequence(){
  this.__functions__ = new Array();
}
SyncSequence.prototype={  
  add:function(func){
    this.__functions__.push(func);    
  },
  wrapCallback:function(callback){
    var $this = this;    
    return function(){
      callback.apply(null,arguments);
      $this.runSequence();
    }
  },
  runSequence:function(){    
    if(this.__functions__.length > 0){
      this.__functions__.shift()();
    }
  }
}

В данном случае __functions__ является очередью, в который мы последовательно помещаем те вызовы, которые должны использовать.
wrapCallback создаёт функцию, которая заменит традиционный коллбэк. Основное её отличие заключается в том, что в конце исполнения данного ей коллбэка будет вызвана следующая функция в очереди.
Ну а runSequence просто запускает верхушку на исполнение. Процесс создания очереди будет выглядеть примерно так.

var ss = new SyncSequence();
ss.add(function(){
  test(1,ss.wrapCallback(testCallback))
});
ss.add(function(){
  test(2,ss.wrapCallback(testCallback))
});
ss.runSequence();

Конечно, не образец изящества, но всё-таки. Дополним код полусферическим примером:

function test(arg,callback){
  alert("Test started " + arg);
  setTimeout(function(){
    callback(arg + 100);
  },1000);
}

function testCallback(arg){
  alert("Test callback started " + arg);
}

При компоновке и запуске мне последовательно выдались 4 алерта:

• Test started 1
• Test callback started 101
• Test started 2
• Test callback started 102

Ура. Конструкция может существовать не только в невесомости, но и в условиях слабой гравитации. Поразительно, но мне для осуществления коварных планов по порабощению мира написанию одной маленькой утилиты этого богатства вполне хватило.
Будет нужно, подумаю что ещё можно будет добавить. А пока оставлю как есть.
И да, асинхронные вызовы снова стали синхронными. Троекратное ура.

Как всегда, исходные коды можно скачать.

Немного о динамических вызовах

Так сложилось, что иногда приходится писать код вида подобного вида:

if (action is SetPropertyAction)
{
   cond.AddRange(GenerateAction((SetPropertyAction)action));
}
else if (action is CommandAction)
{
   cond.AddRange(GenerateAction((CommandAction)action));
}
else if (action is FocusAction)
{
   cond.AddRange(GenerateAction((FocusAction)action));
}
else if (action is TransitionEffectAction)
{
   cond.AddRange(GenerateAction((TransitionEffectAction)action));
}
else if (action is NavigationAction)
{
   blockBody.AddRange(GenerateAction((NavigationAction)action));
}


В тех случаях, когда внести код GenerateAction в интерфейс было бы неверно или невозможно (например в качестве action может придти int), а разделение по типу необходимо возникает вопрос, каким же именно образом можно избавится от портянки?
Для начала создадим сферического коня в вакууме для последующих пыток:

internal abstract class A{}
internal class B : A{}
internal class C : A{}
internal class D : A{}

internal class Worker
{
  public int Foo(B c)
  {
    return 1;
  }
  public int Foo(C c)
  {
    return 2;
  }
  public int Foo(D c)
  {
    return 3;
  }
}

Задача проста: сделать функцию, принимающую экземпляр класса A в качестве параметра и вызывающая «правильный» метод класса Worker.
Вот она классическая портянка

public static int FooClassic(A a)
{
  if (a is B)
  {
    return worker.Foo((B)a);
  }
  else if (a is C)
  {
    return worker.Foo((C)a);
  }
  else if (a is D)
  {
    return worker.Foo((D)a);
  }
}

Замечательная вещь. Работает, но в случае если количество вариантов будет плодиться ужас лютый. А если имеется у данных классов появятся наследники для части из которых нужно создавать метод отличный от метода папочки…
Cтрашные вещи в Датском королевстве могут творится. Может быть можно сделать как-то по другому?

Что сразу приходит на ум: рефлекшен. Можно же просто получить нужный метод после чего его вызвать. Всё просто и логично. С небольшой натяжкой можно сказать что красиво.

public static int FooReflection(A a)
{
  return (int) worker.GetType().GetMethod("Foo", new[] { a.GetType() }).Invoke(worker, new[] { a });
}

Но есть одна небольшая проблема. Это долго. Заставим сферического коня немного поскакать.

const int repeatCount = 1000000;
var listObjects = new List<A> { new B(), new C(), new D() };

И дальше замер скорости кода:

for (var i = 0; i < repeatCount; i++)
{
  foreach (var obj in listObjects)
  {
    FooClassic(obj);
  }
}

Если FooClassic у меня выдаёт порядка 117 миллисекунд, то FooReflection уже тратит порядка 7 секунд. В некоторых местах ухудшение времени в 65 раз не является критичным (например, если метод за всё время вызывается пару десятков раз), но может быть можно побыстрее?
Что будет, если мы сразу станем запоминать, для какого типа был вызыван метод?

public static TResult InvokeMethod<T, TArg, TResult>(this T obj, string name, TArg arg)
{
  var key = new ComposedKey(obj, name, arg.GetType());
  Delegate value;

  if (!_methodsCache.TryGetValue(key,out value))
  {
    var parametr = Expression.Parameter(typeof (TArg), "x");
    var body = Expression.Call(Expression.Constant(obj), name, new Type[] {}, Expression.TypeAs(parametr, arg.GetType()));
    var expression = Expression.Lambda<Func<TArg, TResult>>(body, parametr);
    value = expression.Compile();
    _methodsCache[key] = value;
  }
  return ((Func<TArg, TResult>) value)(arg);
}

ComposedKey в данном случае ключ, который позвляет запоминать последовательность объектов. По имени свойства и типу апгумента можно создать функцию, вызывающую необходимый метод. В данном случае expression.Compile как раз создаёт такой метод. Теперь можно написать функцию:

public static int FooInvoker(A a)
{
  return worker.InvokeMethod<Worker, A, int>("Foo", a);
}

Такой подход позволяет ещё немного сократить время. И теперь выполнение занимает порядка 1 секунды. Небольшое, но улучшение.
В четвёртом фреймворке появился новый объект - dynamic, вызовы которого всегда происходят динамически и выбирается наиболее подходящий метод. В данном случае можно попробовать воспользоваться именно этим классом.

public static int FooDynamic(A a)
{
  return worker.Foo((dynamic) a);
}

Это самый короткий и элегантный вариант, но по времени он всё равно отстаёт от классического решения.
Результаты:

Имя метода	Скорость в миллисекундах
Classic	117
Reflection	6994
Invoker	1112
Dynamic	907

Таким образом, если скорость исполнения какого-то кода не сильно важна, то можно воспользоваться каким-либо из методов, по облегчению себе жизни. Особенно это будет полезно, если планируется серьёзное увеличение числа классов, для которых существуют перегруженные методы. В остальных же случаях лучше не пытаться взрывать себе мозг и поступать наиболее просто.

Исходные коды можно скачать по ссылке

Каррирование в C#

Под термином каррирование понимается преобразование функции, которое функцию от двух переменных переводит в функцию от одной переменной.
Предположим, что у нас была функция:
   f:  AxB  =>   C
   f: (a,b) -> a + b
Сложение взято для примера. Мы можем её преобразовать следующим образом:
   Curry(f): A => (B =>  C  )
   Curry(f): a -> (b ->a + c)
То есть теперь каждому числу Curry(f) сопоставляет функцию одной переменной. При этом выполняется равенство
   f(a,b) = Curry(f)(a)(b)
Кроме того, при помощи функции каррирования мы можем фиксировать значение первого аргумента функции f.
   AddOne   = Curry( + )(1)
   PowerOf2 = Curry( ^ )(2)
Теперь можно использовать новополученные функции. Например:
   AddOne(5)   = 6
   PowerOf2(3) = 8
Подобные функции дают некоторую гибкость, и могут быть использованы, например при использовании методов Linq.
К сожалению, в третьей версии c# нельзя использовать вот такие конструкции:

internal static class Program
{
   public static int AddFunction(int a, int b)
   {
      return a + b;
   }

   private static void Main()
   {
      var addTwo = FunctionalTools.Curry(AddFunction)(2)
      var addTwoExtention = AddFunction.Curry()(2)
   }
}

Поскольку AddFunction на самом деле является "Method Group", и особенно в случае если Curry перегружен, не может правильно определить сигнатуру метода. Поэтому придётся использовать ручное приведение типов. Вот так:

internal static class Program
{
  public static int AddFunction(int a, int b)
  {
    return a + b;
  }

  private static void Main()
  {
    var addTwo = FunctionalTools.Curry((Func<int, int, int>)AddFunction)(2)
    var addTwoExtention = ((Func<int, int, int>)AddFunction).Curry()(2)    
  }
}

Практически всё уже сказано, осталось только реализовать функционал. К сожалению, сделать самый общий тип мы не сможем, но мы можем сделать покрытие значительной части
функционала. Скажи, вы часто используете методы, которые содержат более, чем 8 параметров? Думаю, довольно редко. Поэтому вначале обьявим несколько делегатов.

public delegate TResult Func<T1, T2, T3, T4, T5, TResult>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5);
public delegate TResult Func<T1, T2, T3, T4, T5, T6, TResult>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6);
public delegate TResult Func<T1, T2, T3, T4, T5, T6, T7, TResult>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7);
public delegate TResult Func<T1, T2, T3, T4, T5, T6, T7, T8, TResult>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8);

Но обьявлять таким образом кучу делегатов скучно, долго, неинтересно и не информативно. Более того, если попытки написать функцию Curry для каждого возможного варианта не вызывают никакой радости.
Поэтому рекомендую посмотреть в сторону Text Template Transformation Toolkit, про него на хабре уже писали.

Немножечко перепишем объявление делегатов:

<# for(var index = Shapr3FuncCount; index < MaxParametersCount; index++) { #>
    public delegate TResult Func<<#= BuildTemplate(1,index) #>, TResult>(<#= BuildTemplate(1,index,x=>TypeNamePrefix+x+ArgPrefix+x) #>);
<#} #>

При этом были использованы следующие константы и функции:


   private const int Shapr3FuncCount = 5;
   private const int MaxParametersCount = 9;
   private const string TypeNamePrefix = "T";
   private const string ArgPrefix = " arg";
   private string BuildTemplate(int a,int b,Func<int,string> func){
      return string.Join(", ",System.Linq.Enumerable.Range(a, b).Select(func).ToArray());
   }
   private string BuildTemplate(int a,int b){
      return BuildTemplate(a, b, x => TypeNamePrefix + x);
   }
   private string BuildArgs(int howMany){
      return BuildTemplate(0,howMany,x => ((char)('b'+x)).ToString());
   }


Вот мы сгенерировали недостающие делегаты, теперь можно смело приступить непосредственно к написанию функций каррирования.
Всё действие будет происходить внутри конструкции:

<# for(var index = MinParametersCount; index < MaxParametersCount; index++) { #>

Собственно, ничего сложного в написании функции нет. Вот она:

public static Func<T0, Func<<#= BuildTemplate(1,index-1) #>>> Curry<<#= BuildTemplate(0,index) #>>(this Func<<#= BuildTemplate(0,index) #>> func)
{
   return a => (<#= BuildArgs(index - 2) #>) => func(a<#= index>MinParametersCount?", ":"" #><#= BuildArgs(index - 2) #>);
}

А к ней я решил добавить ещё одну функцию, которая позволит сразу зафиксировать первый аргумент какой-либо функции. Мне кажется, что это является одной из наиболее востребованных возможностей каррирования.

public static Func<<#= BuildTemplate(1,index-1) #>> Bind<<#= BuildTemplate(0,index) #>>(this Func<<#= BuildTemplate(0,index) #>> func, T0 value)
{
   return Curry(func)(value);
}

Теперь осталось только сохранится и посмотреть получивший файл. Изменяя константы можно плодить дополнительные функции, которые удовлетворит любые потребности в аргументах, хотя и сомневаюсь, что такие могут реально возникнуть.
Для удобства можно реализовать ещё несколько функций высших порядков. Я приведу лишь одну, которая позволит менять местами аргументы функции:

public static Func Flip<T1,T2,TResult>(this Func<T1,T2,TResult> func)
{
   return (x,y) => func(y,x);
}

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

Комбинатор неподвижной точки

Когда мне впервые задали вопрос о том может ли существовать функция вида Func<Func<T,T>,T> без использования конструкций вида default(T) он поверг меня в глубокий когнитивный диссонанс.
Как может существовать функция у которой неоткуда взять значения? Об очевидном варианте

T Fix<T>(Func<T,T> func){
   return func(Fix(func));
}

я не мог даже подумать. Разве возможно делать такие функции? Она будет вызываться бесконечно и не даст результата. В языках типа C# такая конструкция и правда вызовет зацикливание, но вполне может работать в языках вроде питона или хаскеля. Сейчас будет немного кода на Haskell, надеюсь синтаксис будет более-менее понятен всем.
Самый простой пример:

fix f = f( fix f)
const42 x = 42
print(fix const42) -- Угадайте, что выведет эта конструкция?

Если разложить вызов, то мы увидим, чтo имеет место быть следующая цепочка вычислений:

fix const42 -> const42 ( fix const42) -> 42

Последний переход произойдёт из-за того, что нам не нужен аргумент функции, чтобы вычислить её значение.
Возникает вопрос: если же функция будет зависеть от своего аргумента то вычисление не остановится, то как нам быть?
Ну не остановиться, и ладно. Если значение не будет использоваться, то оно и не должно быть вычислено, за что спасибо ленивости Haskell.

: - это функция добавления элемента в голову списка. Например: 1:[2,3] = [1,2,3], n:[] = [n]

Рассмотрим функцию fix (1:). Она возвращает список, который, очевидно, будет бесконечным, но тем не менее его можно будет использовать.

take 3 (fix (1:)) -> take 3 (1:fix (1:)) -> 1:take 2 (fix (1:)) -> 1:(1:take 1 (fix (1:)))
-> 1:(1:(1:take 0 (fix (1:)))) -> 1:(1:(1:[])) -> 1:(1:[1]) -> 1:[1,1] -> [1,1,1]

Вот так просто мы получили результат от функции, которая использует свой параметр. Мы даже создали полезную вещь:
repeat n = fix (n:) - Порождение бесконечного списка из одного повторяющегося элемента.
Бесконечность это не порок, главное чтобы где-нибудь, всё равно внутри или снаружи, цепочка вычислений оборвалась. Какие конструкции могут прервать цепочку?
До этого момента мы предполагали, что тип функции для fix является значимым типом. Но почему бы нам не начать использовать функцию высшего порядка? Попробуем традиционный пример:

factCore f = \x -> if x == 0 then 1 else x * f (x-1)

Тогда функция fix factCore будет являться обыкновенным факториалом. По сути каждый раз вместо функции f будет подставляться функция factCore, из-за чего всё станет крайне похоже на обыкновенную рекурсию.

Давайте попробуем что-нибудь посложнее. Например создать все последовательности длинны k состоящие из чисел от 1 до n, притом чтобы не было двух рядом стоящих одинаковых чисел. Задача высосана из пальца, но тем не менее.

allDiffCore n f = \k cond -> if k == 1 then map (\x->[x]) $ filter cond [1..n] else concat $ map (\x -> map (x:) (f (k-1) (/=x)) ) (filter cond [1..n])
sequences n k = fix (allDiffCore n) k (\x->True)

Небольшие пояснения:

filter - функция, принимающая два параметра: условия и список. Возвращает список объектов, которые удовлетворяют условию.
/= - обыкновенное "не равно". Такая вот весьма математическая запись.
concat - функция, которая объединяет список списков в один список.

На каждом шаге мы берём несколько подходящих элементов и задаём функцию которая определит, подходит ли нам следующий элемент. При помощи такого шаблона можно генерировать много разнообразных последовательностей. Например, чтобы получить все возрастающие последовательности достаточно лишь поменять часть отвечающую за функцию фильтрации, то есть (/=x) заменить на (>x).

А теперь задача на подумать: как написать функцию, которая разрешит задачу о ферзях на шахматной доске размера n*n?
Как вы уже заметили, использование функции fix (кстати она является частным случаем комбинатора неподвижной точки), позволяет избежать прямой рекурсии в функциях, что может быть полезно, например, в лямбда исчислении, поскольку там нельзя использовать обыкновенную рекурсию.

Бонусом предлагаю некий, сильно урезанный комбинатор неподвижной точки, для c#:

public static Func<T1, T2> Fix(Func<Func<T1, T2>, Func<T1, T2>> f)
{
   // Создание функции необходимо использовать, чтобы дальнейшие вызовы происходили непосредственно
   // во время передачи значения внутрь. Это позволяет избежать зацикливания
   return f(x => Fix(f)(x));
}

И дальше использование:

var fact = Fix<int, int>(self => x =>
   {
      if (x == 0)
         return 1;
      return x * self(x - 1);
   });
var result = fact(5);   // 120

Если использовать кодогенератор, то можно наплодить приемлемое для дальнейшего использования число функций.

Не переусердствуй.

Типичная задача: если коллекция IEnumerable<T>. Требуется определить, содержится ли в нём как минимум n элементов.
Уже не раз и не два видел подобное решение:
   var answer = collection.Count() > n;
Вопрос: зачем так делают люди? Даже если я отброшу чисто функциональные претензии о работе с бесконечными спискам, то остаётся проблемы производительности, возможные эффекты.
Неужели так сложно делать:
   var answer = collection.Skip(n).Any();
И все будут счастливы. Быть как можно более ленивым выгодно.

Ленивость и строгость.

Начнём цикл лекций по ленивым вычислениям.
Цикл лекций окончен, задавайте Ваши вопросы.

У любой вещи может быть ровно 4 состояния, к которым можно приписать определённые риски:

•  Не надо и не сделано. Риска нет
•  Не надо и сделано. Риск минимален, за редкими исключениями.
•  Надо и сделано. Всё хорошо, риска нет.
•  Надо и не сделано. Риск высокий, единственная действительно нехорошая ситуация.

А теперь давайте посмотрим на типичный подход некоторых языков программирования. Как некогда шутили, про отличая функционального программирования от императивного:
В функциональном программировании Вы объясняете свою проблему математику, в императивном Вы объясняете ту-же самую проблему идиоту.
С ленью можно провести некоторые подобные аналогии. Неленивое программирование недалеко ушло от идиота, скажешь — сделает. Зато ленивое имеет отличительную Русскую черту — пока не припрёт делать ничего не будет.
Императивные языки программирования обычно являются неленивыми, есть паттерны вроде Синглтонов и Итераторов, но общей картины они не меняют, поскольку это сознательный уход от традиционной парадигмы в угоду производительности и удобству. Соответственно, если мы наложим поведение на шаблон, изложенный в самом начале поста, то помимо положительных результатов, мы получим вариант «Не надо и сделано». Запомним это и ненадолго отложим.

Многие функциональные языки по природе являются ленивыми. Это не обязательный критерий, но весьма полезный. Довольно сложно работать с бесконечными списками, функциями высшего порядка и прочими прелестями, если всё что написано исполняется сразу-же. Процессорные ресурсы, как и память, к сожалению, ограничены. Примером функционального ленивого языка может служить Haskell, который лишь чуть менее ленив, чем полностью, и, если его специально не пнуть, делать ничего не будет. Любое действии, которое должно быть выполнено нужно обязательно обозначить. Я бы не стал писать этот пункт в минус, так как это особенность реализации. Соответственно исключив пункт «Надо и не сделано» у нас остаётся только один вариант «Надо и сделано», который нас более чем устраивает.

Вроде бы всё хорошо и там и там, разве не так? Частично соглашусь, но отмечу лишь, что минимальный риск — это тоже риск. Любое действие в императивном языке может порождать сайд-эффекты. Изменение состояния класса, вывод во внешний мир (монитор, консоль, файл) и так далее. Огромный процентов ошибок, которые в принципе существуют, связан именно с сайд эффектами. Часто из-за того, что ненужное изменение было произведено (кинутое не вовремя событие, заранее инициализированный объект породивший утечку памяти, не вовремя запрошенный критический ресурс, породивший блокировку). В языке с ленивой структурой выполняются лишь те действия, которые необходимы для получения конкретного результата, что значительно сокращает ряд возможных ошибок, но к сожалению не до конца. Об остальном призвана позаботиться «строгость», которой обладает, например, тот-же Haskell. Всё, что вам дано извне пришло в качестве аргументов функции, которые всегда неизменяемые (на самом деле это не так, но прежде чем начать использовать что-то изменяемое, Вы десять раз подумаете, а так ли это Вам необходимо), взаимодействия со сторонним кодом практически никакого. Сложно что-то сломать, если Вам оно попросту недоступно. Это огромный плюс, значительно увеличивающий стабильность приложения.

Слишком хорошо, чтобы быть правдой, хочется сразу же спросить — а где подвох? Подвох действительно есть. Любые правила — это ограничения, которые как позволяют избежать ошибок, так сокращают размах возможного действа. Из-за этого бывает сложно, а иногда и невозможно, построить адекватную модель. Программы на Haskell являются крайне стабильными, часто переиспользуемыми, но практически всегда маленькими. Большую модель крайне сложно уместить в рамках строгих ограничений.

Единственный путь который я вижу — разделение макропрограммирования (программирования в рамках системы, создание архитектуры) и микропрограммирования (написание конкретный функций, оптимизация частей модулей). В реальной системе только таким образом можно получить хоть какой-то профит, от введения строгости, ленивости и дополнительных ограничений. Идеального мира не существует.