Дмитpий Hecтepук

Блог о программировании — C#, F#, C++, архитектура, и многое другое

Паттерн-мэтчинг на языке C#

15 комментариев

Недавно наткнулся на примеры реализации паттерн-матчинга Антона Оникийчука (лидер spbalt.net). Понятное дело что подобные вещи достаточно просто реализуются в F#, но вот на C# сделать посложнее. Что же, посмотрим во что это выльется.

Первая попытка

Итак, что такое pattern-matching? Можно начать с того, что это более умный switch который, при полной реализации, умеет намного больше. При этом, паттерн-матчинг применяется к различным типам, но “специальным” типом для него является список (или посделовательность, неважно), т.к. именно для списков используются list comprehensions. Но давайте не будем забегать вперед.

Итак, реализация Антона предлагает нам сделать fluent interface, с помощью которого каждый кейс обрабатывается как некий предикат. Например:

private int year;
public int Year {
  get {
    return year;
  }
  set
  {
    value.Match(v => v < 0, y => {throw new Exception("BCE not supported");})
         .Match(v => v > DateTime.Now.Year,
             y => {throw new Exception("Future years not supported");})
         .Match(v => true, y => {year = y;});
  }
}

Тут наверное понятно откуда взялся Match() – его реализация примитивна:

public static T Match<T>(this T target, Predicate<T> predicate,
                         Action<T> whenMatched)
{
  if (predicate(target))
    whenMatched(target);
  return target;
}

Вообще-то, то что мы сейчас реализовали – это поддержка ключевого слова when. А как же поддержка значений напрямую? Это просто:

public static T Match<T>(this T target, T value, Action<T> whenMatched)
{
  if (target.Equals(value))
    whenMatched(target);
  return target;
}

Теперь уже можно писать year.Match(0, throw new Ex("There is no 0 year")) или что-то в этом духе. Еще один интересный аспект мэтчинга – это когда нужно сделать проверку на несколько значений. Например, если год равен 666 или 1666 – бить тревогу. А вот это уже сложнее, т.к. нам не подставить params предпоследним аргументом – компилятор не даст.

Элегантного решения этой проблемы вообще не существует – разве что если T имеет тип char (тогда можно передать строку). В обобщенном случае, можно банально передавать массив. Сам метод расширения будет брать IEnumerable<T>:

public static T Match<T>(this T target, IEnumerable<T> values, Action<T> whenMatched)
{
  foreach (var t in values.Where(v => v.Equals(target)))
    whenMatched(t);
  return target;
}

и использоваться вот так:

value.Match(v => v < 0, y => {throw new Exception("BCE not supported");})
     .Match(v => v > DateTime.Now.Year,
         y => {throw new Exception("Future years not supported");})
     .Match(0, y => {throw new Exception("There is no year Zero");})
     .Match(new[]{666, 1666}, y => {throw new Exception("Bad year!");})
     .Match(v => true, y => {year = y;});

Фундаментальным вопросом остается то, что возвращает Match<T> – а примере Антона, идет возврат значения, т.е. вместо Action<T> принимается Func<T,U>, где U – тип результата. Это создает определенные проблемы т.к. исключения явно не типа U, и тем самым приходится заниматься организацией их перехвата.

Вариадичность

У нас в паттерн-матчинге есть, условно говоря, две ситуации – в одной используется list comprehension (т.е. проверка элементов списка, последовательности, и т.п.), в другой – все остальное. Мы уже посмотрели на то, как можно реализовать ПМ для простых типов, давайте теперь посмотрим на то, как сделать то же самое для списков.

Для начала, придется признать что нужны будут перегрузки. Точно так же как Func<T,...> имеет вариаций этак 16, нам потребуется аналогичные фичи вместо Predicate<T>. Естественно, для обработчика так же потребуются 16 вариаций Action<T>. И естественно, это задача для кодогенерации (кто сказал что кодогенерация это nuclear option?)

Давайте посмотрим как будет выглядеть мэтчинг для 3х аргументов:

public static IEnumerable<T> Match<T>(this IEnumerable<T> target,
                         Func<T,T,T,bool> predicate,
                         Action<T,T,T> whenMatched)
{
  if (target.Count() >= 3) {
    var values = target.Take(3).ToArray();
    if (predicate(values[0], values[1], values[2]))
      whenMatched(values[0], values[1], values[2]);
  }
  return target;
}

Тут неважно чем пользоваться – Linq или напрямую брать Enumerator и обходить, особой погоды это (наверное) не сделает. Вот типичное использование:

public string processList(IEnumerable<int> list)
{
  string result = string.Empty;
  list.Match((a,b,c) => ( a == b && b == c ),
             (a,b,c) => {result = "First 3 elements identical";});
  return result;
}

Замечу что мы все еще не научились делать из этих методов возвращаемые значения, но сделать это “правильно” невозможно в принципе – единственный вариант это когда вместо IEnumerable<T> в цепочке появляется некий контейнер который агрегирует IEnumerable<T> а также некую переменную Result, которую потом придется возвращать вручную, т.к. никакого приведения вроде implicit operator U тут не получится (не верите – попробуйте).

А где же хвост, пустой список, и т.п.?

Очень хочется показать реальный пример, поэтому постараюсь ‘закрыть’ еще пару проблем прежде чем переходить к примеру. Во-первых, мы не умеем делать мэтчинг на пустой список []. Эта проблема решается просто – мы используем старую реализацию, которая не заточена под IEnumerable:

public string processList(IEnumerable<int> list)
{
  string result = string.Empty;
  list.Match((a,b,c) => ( a == b && b == c ),
             (a,b,c) => {result = "First 3 elements identical";})
    .Match((l => !l.Any()), l => {result = "Empty list";});
  return result;
}

Теперь что касается ‘хвоста’. Поскольку мы используем не LinkedList<T> а IEnumerable<T>, рекурсивная обработка наверное должна выглядет вот так:

public void processList(IEnumerable<int> list, IList<int> result)
{
  list.Match((a,b,c) => (a == b && b == c),
             (a,b,c) => { result.Add(a);
                          processList(list.Skip(3), result); }
}

Мораль в том, что это безобразие будет порождать миллион новых перечислений, которые наверняка откушают много памяти и CPU. Использование связанного списка – пожалуй единственное решение данной проблемы.

Еще одну вещь которую пришлось сделать – это эксклюзивность кейсов в мэтчинге (раньше об этом как-то не подумал). Для этого в цепочку вклинивается null и везде делаются проверки.

Финальный пример

Рассмотрим ситуацию, в которой нам нужно обходить строку, и заменять некоторые символы – например менять --> на --&gt;. Как это будет выглядеть? Сразу скажу – достаточно кошмарно. Во-первых, мы делаем метод для перевода строки в LinkedList<char>:

public static LinkedList<char> ToList(this string target)
{
  return new LinkedList<char>(target.ToCharArray());
}

Также нам нужен будет метод для передвижения по списку:

public static LinkedListNode<T> Move<T>(this LinkedListNode<T> list, int steps)
{
  var p = list;
  while (steps --> 0)
    p = p.Next;
  return p;
}

Теперь нужны обработчики для списка (да-да, 16 или сколько там), которые во-первых умеют общаться с LinkedList<T>, а во-вторых знают что при “провале” нужно возвращать именно null:

public static LinkedListNode<T> Match<T>(this LinkedListNode<T> target,
                                         Func<T,T,T,bool> predicate,
                                         Action<T,T,T> whenMatched)
{
  if (target != null && target.Next != null && target.Next.Next != null)
  {
    var a = target.Value;
    var b = target.Next.Value;
    var c = target.Next.Next.Value;
    if (predicate(a,b,c)) {
      whenMatched(a,b,c);
      return null;
    }
  }
  return target;
}

Самое время начать использовать Boo :) Тем временем, у нас появляется “оберточный” метод для обработки строки:

public string processString(string input)
{
  var sb = new StringBuilder();
  var list = input.ToList();
  processString(list.First, sb);
  return sb.ToString();
}

Это, опять же, еще один минус отсутствия полноценных вложенных функций. Можно было создать делегат, но я поленился. Ну а теперь – самое главное – реализация нашего примитивного алгоритма:

private void processString(LinkedListNode<char> first, StringBuilder result)
{
  first.Match(
    (a,b,c) => (a == '-' && b == '-' && c == '>'),
    (a,b,c) => { result.Append("--&gt;");
      processString(first.Move(3), result); })
    .Match(c => c == null, c => {})
    .Match(c => c != null, c => { result.Append(c.Value);
             processString(first.Next, result);});
    
}

Тут есть что поизучать и пооптимизировать. Но все равно вид сего достаточно кошмарен хотя, конечно, все работает :)

Заключение

Попытка вклинить стороннюю фичу в язык который ее не поддерживает нативно – задача достаточно болезненная, и как по мне так особого value в программу она не превносит. Более того, есть огромное количество накладных расходов связаных с конверсией в LinkedList<T> – ведь насколько я понимаю, каждая буква в моем примере превратилась бы в LinkedListNode<char>. Если учесть средней размер статьи (10,000 символов), то сразу как-то становится не по себе.

Так или иначе, надеюсь что это пример показал как можно сделать что-то a la паттерн мэтчинг/list comprehension в C#. Хотя, опять же, программирование в стиле С (использование switch, for и т.п.) тоже работает весьма неплохо.

Advertisements

Written by Dmitri

18 июля 2010 в 11:47

Опубликовано в .NET, C#

комментариев 15

Subscribe to comments with RSS.

  1. что-то страшное >_ {throw new Exception(«Bad year!»);} )

    tenshi

    18 июля 2010 at 14:42

  2. повторять лень..

    tenshi

    18 июля 2010 at 14:48

  3. Hi,

    Please also check Matthew Podwysocki’s functional programming project:

    http://code.msdn.microsoft.com/FunctionalCSharp

    I hope this helps,
    Bogdan

    Bogdan Brinzarea

    19 июля 2010 at 9:17

    • Yeah, saw that, thanks. Slightly different approach there. Admittedly there’s lots of scope for experimentation with ways data is propagated along the calls.

      Dmitri

      19 июля 2010 at 9:32

  4. Ну во первых ты привел самую простую реализацию match :) там есть и более интересный сценарий — последовательный выбор с приоритетом. Я на самом деле им пользуюсь в своих проектах, когда данные нужно брать из нескольких источников с определенным приоритетом (например чтение конфигурации).

    Anton Onikiychuk

    19 июля 2010 at 9:47

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

      Alexander Tankeev

      19 июля 2010 at 13:08

      • Ну для валидации и обработки исключений есть и решения получше, например АОР через IoC контейнер (или PostSharp). А вот цепочки с протаскиванием аргумента, null-проверками и аналогичными вещами есть решения вроде этого.

        Dmitri

        19 июля 2010 at 15:03

    • > последовательный выбор с приоритетом

      Присоединяюсь, хотелось бы поподробнее. Это что-то вроде преобразования в «лесенку из if’ов»?

      mbeloshitsky

      19 июля 2010 at 13:50

      • Я думаю, просто PriorityQueue. Записываем Item-ы (T) с приоритетом (int), Читаем — ба! отсортировано!

        По русски: надо менять то-то на то-то, но вот если есть еще то-то, то уж менять то-то на вооо-т это все )))

        hack2root

        11 августа 2010 at 17:56

  5. Привет Всем!

    Опубликовал-таки я свой фреймворк :)

    Было бы здорово, если бы вы прокомментировали
    эту штуку :)

    http://expressionscompiler.codeplex.com/

    Примеры пока только в виде исходного кода — качайте, запускайте :)

    hack2root

    20 августа 2010 at 9:26

  6. О заметка просто супер! Очень понравилось. В приниципе, в сочетании с мондарическим синтаксисом C# и некоторым дальнейшем развитии и расширении идеи (для более полного охвата матчинга), и немного большим разжовыванием и развёртыванием примеров исходного кода — получилась бы очень хорошая статья, которая снескала бы большой успех и на gotdotnet.ru и rsdn.ru (и была бы опублекована в соотв. журнале).
    Мне было бы очень интересно почитать про дальнейшее развитиее этой темы. Только, вот, саму идею привязки функциоанльных неизменямых списков к матчингу на C# я бы отмёл сразу — тут луч ше бы сосредоточиться на императивном подходе с# — а именно на самих перечислителях — обходя списки через IEnumerator без отсеивания головы — при необходимости получения именно остатка (левого или правого) — выполнять это в обратном проходе. Так же — очень здорово было бы рассмотреть реализацию Матчинга в стиле Parallel programming — т.е. ориентированную именно на паралельное сравнение с патеррнами в мультипоточной среде (aka PLINQ).

    Darklight

    14 сентября 2010 at 17:04

  7. […] o Паттерн-мэтчинг на языке C# или делаем switch умнее […]

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

    Максим Матвеев

    14 февраля 2013 at 10:11

    • В случае передачи списков, на мой взгляд, можно немного поступиться принципами ФП и передавать не новый список, а его же после модификации. Тем самым, сэкономим кучу памяти и процессорного времени.
      А Вы смотрели, как решают эту проблему в F#?

      Максим Матвеев

      14 февраля 2013 at 10:15


Оставить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: