понедельник, 28 февраля 2011 г.

Мимолётом о числах Чёрча

Классическое определение числа Чёрча - эта функция, которая принимает два значения: функцию и аргумент. И применяет функцию к аргументу какое-то число раз.

0 ≡ λfx. x
1 ≡ λfx. f x
n ≡ λfx. fn x


для таких чисел легко определить добавление единицы:

succ ≡ λnfx. n f (f x)

сложение двух чисел:

plus ≡ λmnfx m succ (n f x)

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

pred ≡ λnfx. ngh. h (g f)) (λu. x) (λu. u)

Может быть я глуп, но осознать это я не смог. Но можно попробовать написать немного проще:
Для начала рассмотрим такую конструкцию

pair ≡ λfsc. c f s
fst ≡ λp. (λfs. f)
snd ≡ λp. (λfs. s)


Благодаря её можно создавать кортежи и обращаться к ним:

fst (pair x y) → x
snd (pair x y) → y


Теперь всё просто:

init ≡ pair 0 0
next ≡ λp. pair (snd p) (succ (snd p))
pred ≡ λn. fst (n next init)


мы строим ряд:

0 → (0, 0)
1 → (0, 1)
2 → (1, 2)
n → (n-1, n)


и беря первый аргумент подобной пары получаем число на единицу меньшее, чем было передано.

четверг, 25 ноября 2010 г.

Немного а Drag'n'Drop в WPF.

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

Вначале всё казалось просто и понятно: есть Drag Source, который по каким-то действиям может инициировать драг-н-дроп, описав те эффекты, с которыми может оперировать Drop Target. Дальше, дроп таргет реагирует на события, такие как DragEnter, DragOver, Drop, применяя те или иные эффекты, после чего уже Drag Source реагирует на совершённые действия (например завершение операции путем дропа или отмены).
Немного сумбурно, поэтому попытаюсь изобразить на картинке:
Схематичное изображение процесса Drag'n'Drop
По сути две части (Drag Source и Drop Target) должны являться независимыми, но просматривая примеры использования я не обнаружил независимой реализации. Практически везде обработка действия Move (чаще всего удаление данных из источника) происходила в реализации метода OnDrop. То есть сам Drop Target определял действия с Drag Source.

Создадим небольшое приложение, пусть главное окно выглядит так:
<Window x:Class="DragDropTest.MainWindow"
    xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
    Title="Drag'n'Drop Test" Height="350" Width="525">
  <StackPanel>
      <ListBox x:Name="DragSource" SelectedValuePath="Content"
        GiveFeedback="OnGiveFeedbackRaised"
        QueryContinueDrag="OnQueryContinueDragRaised"
        PreviewMouseMove="DragSource_OnPreviewMouseMove" >
        <ListBoxItem>first</ListBoxItem>
        <ListBoxItem>second</ListBoxItem>
      </ListBox>
    <TextBox x:Name="AddTextBox"></TextBox>
    <Button Click="OnAddPressed">Add</Button>
  </StackPanel>
</Window>
Я не стал сильно мучиться с тем, как именно начинать операцию Drag'n'Drop, поэтому код DragSource_OnPreviewMouseMove выглядит следующим образом (чуть более правильно начало описывается тут):
private void DragSource_OnPreviewMouseMove(object sender, MouseEventArgs e)
{
  if (e.LeftButton == MouseButtonState.Pressed && DragSource.SelectedItem != null)
  {
    var data = new DataObject(DataFormats.Text, DragSource.SelectedValue);
    DragDrop.DoDragDrop(DragSource, data, DragDropEffects.All);
  }
}
Теперь посмотрим, что же мы можем узнавать при помощи фидбека:
  • GiveFeedbackEventArgs позволяют узнать, какой именно эффект сейчас используется и позволяет задать вид курсора.
  • QueryContinueDragEventArgs позволяет узнавать состояние операции, получить состояние клавиш на текущий момент.
Последнее кажется несколько странным, поскольку от состояния клавиш Drag Source не может получить никакой полезной информации, из-за того что эффект определяется поведением Drop Target'а. Начиная с этого места мы имеем первый хак:
private void OnGiveFeedbackRaised(object sender, GiveFeedbackEventArgs e)
{
  _lastEffect = e.Effects;
}
А именно сохранение последнего применённого эффекта, который нам и предстоит обрабатывать по окончанию действия. Следующая бочка дёгтя заглючается в следующем:
Вопреки логике, событие QueryContinueDrag с Action равным DragAction.Drop не приходит. Про это даже заведена бага. Для разрешения проблемы я использовал следующий грязный трюк: можно считать что Drag'n'Drop завершился в тот момент, когда левая кнопка мыши перестала быть зажатой. Мне кажется, что подобное поведение будет правильным для большинства сценариев.
private void OnQueryContinueDragRaised(object sender, QueryContinueDragEventArgs e)
{
  if((e.KeyStates & DragDropKeyStates.LeftMouseButton) == DragDropKeyStates.None)
  {
    OnEndDrag(_lastEffect);
  }
}
И уже на OnEndDrag обрабатывается завершение операции, а именно удаление элемента из списка если выбрано действие Move.
Готовое приложение можно скачать отсюда. Оно, по сути, является независимой реализацией Drag Source и позволяет корректно вставлять текст, например, в Word или Notepad++ (кстати что любопытно они используют разные комбинации клавиш, для создания эффекта Move).

четверг, 14 октября 2010 г.

На злобу дня

Некоторые люди создают совершенно глупые системы, которые якобы не позволяют выносить внутрикорпоративную информацию из офиса. Где-то такие системы могут и работать, но уж точно не в обществе программистов.
Что самое печальное — одна из таких систем внедрена на моей текущей работе. После того, как «Dropbox» продолжил отлично работать вместе с этой системой защиты, относительно её качества у меня не осталось никаких сомнений.
Но кроме своей полной бесполезности система имеет свойство доставлять некоторые неприятности. Например, при выборе файла для отправки через браузер вылезает предупреждение о том, что так поступать нехорошо и приходится убивать процесс. Жутко неудобно. При этом, если вбивать сразу полный путь, то всё работает великолепно. Но заниматься строковой магией вручную противно.
И пока я не разберусь, как же система перехватывает обращения к диалогу выбора файла родилось временное решение: добавить действие копирование полного адреса в контекстное меню файла.

Для этих целей была написана жутко длинная и крайне сложная программа
class Program
{
  [STAThread]
  public static void Main(string[] args)
  {
    if(args != null && args.Any())
    {
      Clipboard.SetText(string.Join(string.Empty,args));
    }
  }
}
А дальше пошли разбирательства с расширениями Windows Shell. Следует сказать, что дела с ним раньше я особо не имел, поэтому делал всё максимально рабоче-крестьянски. По быстрому ознакомившись со статьёй на мсдне в реестре были создан ключ HKEY_CLASSES_ROOT\*\Shell\CopyPath\Command.
В значение HKEY_CLASSES_ROOT\*\Shell\CopyPath лежит красивое название для пункта меню.
В HKEY_CLASSES_ROOT\*\Shell\CopyPath\Command нахожится G:\CopyItemsPath.exe "%1". То есть вначале путь до программы, а потом аргумент, который отвечает за путь до выбранного файла.

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

вторник, 12 октября 2010 г.

«Что есть null» или «Как нам дальше жить»

Мне довольно часто приходится писать бизнес-приложения на объектно ориентированных языках достаточно высокого уровня, например C# или Java. Всё нижесказанное не относится к языкам вроде С++.

За время использования C# у меня успело выработаться довольно строгое отношение к null: встреча с этим значение означает ошибку. Практически всегда.
Если в списке нет элементов, то это должен быть пустой список, а не null.
Если мы вызываем какой-то метод объекта, то null в качестве представителя определённо является ошибкой.
Передача null внутрь метода, который не умеет обрабатывать подобное значение тоже приведёт к ошибке.
От постоянных
if(arg == null)
{
  throw new ArgumentNullException("arg");
}
начинают уставать глаза.
Крайне редко получается, что null являлся одним из значений, при этом не выделяясь среди прочих. Чаще всего, он предполагает какое-то специфические действия.

При этом, ошибки связанные с тем, что что-то не было инициализировано а куда-то пришёл null в качестве недопустимого аргумента периодически возникают. Частично этой проблеме помогают контракты и программист может знать, куда можно передавать null а куда нельзя напрягаясь немного меньше.
Но ведь мы, программисты, люди ленивые и напрягаться не хотим вообще, не так ли? Может быть просто стоит запретить null как значение? Это уже сделано например в Haskell.

Но как же быть тогда с методами, которые предполагают использование null? Нельзя же просто от них отказаться?
Для решения этой проблемы умные люди уже давно завели специальный тип. Можно его описать примерно вот так
public class Maybe<T>:IEquatable<Maybe<T>>
{
  /// <summary>
  ///   Default empty instance.
  /// </summary>
  public static readonly Maybe<T> Empty;
  
  /// <summary>
  ///   Instance constructor.
  /// </summary>
  public Maybe(T value);
  
  /// <summary>
  ///   Gets the underlying value, if it is available
  /// </summary>
  public T Value { get; }
  
  /// <summary>
  ///   Gets a value indicating whether this instance has value.
  /// </summary>
  public bool HasValue { get; }
}
Это очень похоже на стандартную Nullable обёртку, для типов передающихся по значению. На самом деле Empty и есть null, разница лишь в том, что он строго типизирован и совершать недопустимые операции с ним немногим сложнее.
На первых взгляд подобное введение сродни обмену шила на мыло, но всё-таки мы получили одно важное преимущество:
Появятся целые участки кода, в которых Maybe не будет участвовать. Цепочки методов, которые не принимают null и не возвращают его. Теперь никто не передаст туда это значение по ошибке, не вызовет метод с недопустимым параметром или не вернёт null из-за желания поставить на будущее заглушку.
Код сам по себе стал чуть более правильным. Возможно, даже чуточку быстрее (не придётся проводить дополнительные проверки, поскольку отсутствие null будет гарантированно системой типов). К сожалению, подобные конструкции продолжают плодить кучу ветвлений, которые затрудняют читабельность. Давайте попытаемся повысить удобство.

От ветвлений никуда не уйдёшь, если необходимы две ветви вычисления, но ситуация меняется кардинальным образом если есть только одна ветвь. Расширим определение класса Maybe методом
public IEnumerable<T> AsEnumerable()
{
  if (HasValue)
  {
    yield return Value;
  }
}
Это даёт возможность работать с элементов Maybe, как с последовательностью. При этом значению Empty будет соответствовать пустая последовательность, а значимому выражению последовательность из одного элемента.

Maybe<int> delay = GetDelayForOperation(/*  */);
delay.AsEnumerable().ForEach(x => Thread.Sleep(x));
Кстати, а почему-бы не сделать и сам Maybe наследником IEnumerable? Это немного укротит запись, сделает её более читабельной. Кстати, умные люди тоже додумались до такого способа, хоть и предложили решить его несколько иначе.
Но, лично мне, не нравится написание огромного количества лямбд. Кроме того, это не очень удобно, при использовании нескольких аргументов.
Maybe<int> delay1 = GetDelayForOperation(/*  */);
Maybe<int> delay2 = GetDelayForOperation(/*  */);
delay.ForEach(x => delay2.ForEach(y => Thread.Slep(Math.Max(x,y))))
Согласитесь, понять с первого раза что делает эта конструкция довольно сложно. Хотя, я думаю, кто-то уже увидел тут приевшиеся цепочки вычислений и функцию bind.
К счатью, в C# есть так называем язык запросов, который позволяет писать SQL-подобные выражения. Для того, чтобы ипользовать эту возможность понадобитья ещё один класс и немого тёмной магии
public static class Maybe
{
  public static Maybe<V> SelectMany<T, U, V>(this Maybe<T> source, Func<T, Maybe<U>> k, Func<T, U, V> s)
  {
    if (!source.HasValue)
      return Maybe<V>.Empty;
    var u = k(source.Value);
    if (!u.HasValue)
      return Maybe<V>.Empty;
    return s(source.Value, u.Value).ToMaybe();
  }
}
Подобная конструкция позволит записывать жутко страшные выражения весьма компактно. Например вместо
result = null;
var d = GetDirectory();
if(d != null)
{
  var f = GetFile(d);
  if(f != null)
  {
    var lines = GetFileLines(f,d);
    if(lines != null)
    {
      result = lines.Count();
    }
  }
}
можно писать
var result = from d in GetDirectory()
       from f in GetFile(d)
       from lines in GetFileLines(f,d)
       select lines.Count();
И главное, никаких лямбд. На самом деле они просто скрыты за этой языковой конструкцией, но для восприятия это не имеет значения.

Бочкой дёгтя в этой ложке мёда можно считать то, что в настоящее время нет средств чтобы запретить использование null в языке вроде c#, поэтому отказ от null и использование Maybe может быть только на уровне негласной договорённости или правила для StyleCop.
На данный момент я пытаюсь сделать совсем маленький проект, следуя подобной договорённости. Ощущения пока положительные, но для чего-то более масштабного, как мне кажется, необходима поддержка на уровне языка.

Есть ещё несколько маленьких удобств, которые облегчают кодирование и отладку, но они не стоят того, чтобы о ни упоминать. Если хотите, посмотрите более подробно в исходнике.

вторник, 21 сентября 2010 г.

Точечное расстройство

Обнаружил в интернете простенький однострочник на F#. И сразу же подумал, а почему бы не попробовать написать тот-же пример в бесточечном стиле. Вначале погуглил на тему как делать композиции в F#. Оказалось довольно просто:
> (>>);;
val it : (('a -> 'b) -> ('b -> 'c) -> 'a -> 'c)

то есть (f >> g) x на самом деле g(f(x)) и

> (<<);;
val it : (('a -> 'b) -> ('c -> 'a) -> 'c -> 'b)

что преобразует (f << g) x в f(g(x))

Вроде всё просто и понятно. Пишем код.
let sorted = Seq.forall (fun (a,b) -> a <= b) << Seq.pairwise

Не катит, код сообщения такой.
Value restriction. The value 'sorted' has been inferred to have generic type val sorted : ('_a -> bool) when '_a :> seq<'_b> and '_b : comparison Either make the arguments to 'sorted' explicit or, if you do not intend for it to be generic, add a type annotation.

Зато всё превосходно работает вот так:
let sorted xs= Seq.forall (fun (a,b) -> a <= b) << Seq.pairwise <| xs

Данный факт меня крайне расстроил. Я не знаю как записать выражение в бесточечном стиле. Надеюсь что всё-таки я верблюд и чего-то не понимаю.

вторник, 22 июня 2010 г.

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

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

Как же именно можно осуществлять подобные вызовы? Мне пришло в голову следующее шаманство:
Создадим объект, в который будем складывать последовательно функции, которые необходимо вызвать, а по завершению коллбэка вызывать на исполнение следующую функцию.
Что нам понадобится?
  • Массив, чтобы в нём хранить функции
  • Добавление функции в массив
  • Исполнение текущей функции
  • Индикатор, для того, чтобы понимать, когда-же закончился коллбэк.
У меня получилось вот такое прелестное чудо:
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
Ура. Конструкция может существовать не только в невесомости, но и в условиях слабой гравитации. Поразительно, но мне для осуществления коварных планов по порабощению мира написанию одной маленькой утилиты этого богатства вполне хватило.
Будет нужно, подумаю что ещё можно будет добавить. А пока оставлю как есть.
И да, асинхронные вызовы снова стали синхронными. Троекратное ура.

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

понедельник, 21 июня 2010 г.

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

Так сложилось, что иногда приходится писать код вида подобного вида:
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);
}
Это самый короткий и элегантный вариант, но по времени он всё равно отстаёт от классического решения.
Результаты:
Имя методаСкорость в миллисекундах
Classic117
Reflection6994
Invoker1112
Dynamic907

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

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