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

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

Обработка строк — сравнение C# и F#

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

У меня есть приложение, с помощью которого я пишу статьи вроде этой. Называется это приложение TypograFix и суть его в том, что оно помогает мне готовить тексты к публикации в итернете. Одна из фич этого приложения – правильное типографирование текста, которое делается с помощью парсера, который обходит текст и производит нужные замены (например, меняет --> на --> что до читателя доходит как →. До сегоняшнего момента, код который делает эту замену был написал на C#. Читается он, прямо скажем, сложно. В этом посте я хочу показать как можно написать подобный парсер на F#, и в чем отличия подобного подхода.

Было бы здорово, если бы для замены определенных последовательностей в тексте можно было использовать String.Replace() или на худой конец Regex.Replace(). К сожалению, для HTML это не вариант – вам нужно знать не только местоположение символа, но также и контекст, то есть общую ситуацию в которой парсер находится в данный момент. Например, если вы в теге <code>, то естественно что замены кавычек делать не стоит. Более того, подход при котором в конце получается объектная модель (например с использованием Microsoft.mshtml или другого парсера) мне тоже не подходит т.к. я люблю периодически отказываться от тегов в пользу символьной репрезентации – например я использую символы {{ и }} для разделения блоков кода.

Так вот, к чему это я? На данный момент, мой подход можно проиллюстрировать вот так:

public string Transform(string text)
{
  var sb = new StringBuilder();
  for (int i = 0; i < text.Length; ++i)
  {
    switch (text[i])
    {
      case '-':
        if (text[i+1] == '-' && text[i+2] == '>')
        {
          sb.Append("&rarr;");
          i += 2;
          continue;
        }
        else goto default;
    }
  }
}

Согласитесь, выглядит не очень. У меня сейчас этот метод (с тысячью всяких примочек) занимает несколько сотен строк кода, и абсолютно не рефакторится по причине завязки на разные состояния взаимодействия (большинство из которых вообще представляют из себя поля на уровне класса).

Как нам может помочь F#? В принципе, он может дать нам возможность лучше разделить наш код на отдельные кейсы (например “кавычки” или “тире и прочерки”) которые нам нужно обрабатывать. Единственная проблема – нам придется отказаться от строк в пользу списков, что безусловно ударит по производительности. Моя задача – типичный пример того, как можно отдать чуть-чуть производительности на откуп читабельности кода.

Итак, давайте начнем с основ. Поскольку строка – это последовательность символов (ну, по крайней мере так считает F#), ее нужно для начала преобразовать в список. Делается это достаточно просто:

let x = "Hello"
let y = Seq.toList(x)
Console.WriteLine(List.length y) // пишет 5
Console.WriteLine(List.toArray y) // пишет Hello

Пример выше иллюстрирует текст как список (именно список, а не последовательность – sequence – букв), а также возможность получения обратно строки (в примере выше – как char[], но из этого можно и System.String построить). Если у вас возникло удивление от названия метода toList() (еще недавно ведь было to_list(), не так ли?), вам нужно обновить свой компилятор F#.

Имея список, можно делать его обход. Основной порыв в данном случае – начать “подсматривать” элементы списка и соответственно заменять их по мере необходимости. Примерно вот так:

let rec Transform text =
  match text with
  | '-' :: '-' :: '>' :: t -> Seq.toList("&rarr;") @ Transform t
  | h :: t -> h :: Transform t
  | [] -> []
 
let input = "a --> b"
let result = input |> Seq.toList |> Transform |> List.toArray
Console.WriteLine(new string(result)) // пишет a --&rarr; b

Такой подход позволяет нам четко выделять все кейсы в отдельные строчки и при этом нам не нужно использовать злое слово goto. Почему? Для этого нам сначала нужно разобраться с контекстом. Что такое контекст? Это по сути дела некий набор состояний – один большой мутабельный god object который содержит различные состояния определенной трансформации. Есть два таких состояния:

  • Собственно контекст, т.е. стек (Stack<string>) которые содержит те теги, в которых парсер находится на данный момент.

  • Набор переменных, которые символизируют различные внутренние состояния, не связанные с тегами. Например, bool флажок, описывающий, открыты ли у нас кавычки.

Вообщем-то, представление в данном случае не важно. Важно лишь то, что все специальные случаи вроде “обрабатывать как есть если мы в теге <code>” можно с помощью очень полезного для pattern matching-а ключевого слова where:

// подразумевается, что этот метод стал вложенным в другой метод,
// в котором объявлены элементы контекста
let rec Transform text =
  match text with
  | h :: t when context.CannotReplace -> h :: Transform t
  ...

Но это еще не все. В нашем коде фигурирует паттерн '-' :: '-' :: '>', а писать такое, согласитесь, весьма неудобно. Легче было бы написать "-->", но к сожалению такой подход не сработает, т.к. просто вставить сюда строку нельзя. Зато можно определить дополнительную функцию (partial pattern matching) которая делала бы проверку именно “префикса” текущей строки:

let rec (|Prefix|_|) s l =
  if s = "" then
    Some(Prefix l)
  else
    match l with
    | h :: (Prefix (s.Substring(1)) xs) when h = s.[0] -> Some(Prefix xs)
    | _ -> None

Используя эту вспомогательную функцию, мы можем писать подобый код:

let rec Transform text =
  match text with
  | Prefix "-->" t -> Seq.toList("&rarr;") @ Transform t
  | h :: t -> h :: Transform t
  | [] -> []

Этот подход несколько понизил читаемость кода т.к. теперь перед каждым случаем использования длинного префикса (а для однобуквенных префиксов он не особо нужен) теперь фигурирует слово Prefix. Конечно я мог бы выбрать слово покороче, но суть не в этом, а в том что это слово есть, и следовательно оно отвлекает.

Давайте посмотрим на более сложный пример в плане паттерн-матчинга – попробуем заменить x на &times; только в тех случаях, когда буква x расположена между двумя числами (например в 2×2). Как это сделать? Примерно вот так:

let rec Transform text =
  match text with
  | Prefix "-->" t -> Seq.toList("&rarr;") @ Transform t
  | a :: 'x' :: c :: t when Char.IsDigit(a) && Char.IsDigit(c) ->
      a :: Seq.toList("&times;") @ c :: Transform t
  | h :: t -> h :: Transform t
  | [] -> []

В примере выше сразу несколько “усложнений” ситуации – мы опять используем длинный список элементов в паттерне, но помимо этого мы используем when а также делаем достаточно неинтуитивную конкатенацию списков. Неинтуитивную потому, что обычно есть соблазн писать либо :: либо @ для соединения списков, а тут получается что мы соединяем два списка с головами a и c соответственно. Ну да ладно, не проблема, ведь все работает.

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

let Transform text:String =
  let input = text |> Seq.toList
  let buffer = new StringBuilder()
  let buffering = ref false
  let rec TransformImpl text =
    match text with
    | ']' :: t when !buffering ->
      Console.WriteLine(buffer.ToString());
      // обрабатываем ссылку, а потом...
      buffering := false
      TransformImpl t
    | h :: t when !buffering ->
      buffer.Append(h:char)
      TransformImpl t
    | '[' :: t ->
      buffer.Clear()
      buffering := true
      TransformImpl t
    | Prefix "-->" t -> Seq.toList("&rarr;") @ TransformImpl t
    | a :: 'x' :: c :: t when Char.IsDigit(a) && Char.IsDigit(c) ->
        a :: Seq.toList("&times;") @ c :: TransformImpl t
    | h :: t -> h :: TransformImpl t
    | [] -> []
  new string(input |> TransformImpl |> List.toArray)

В примере выше, нам пришлось воспользоваться ключевым словом ref для того чтобы сделать переменную buffering изменяемой внутри нашего паттерн-матчинга. Причем в данном случае, мы не могли воспользоваться ключевым словом mutable и оператором <-, а вместо этого нам пришлось использовать ref (т.е. создание ссылочного типа), а также операторами := для присваивания и ! для считывания. Увы, в данном примере F# не добавил читабельности.

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

Итак, попробую прорезюмировать плюсы и минусы данного подхода. Сначала о хорошем:

  • Больше не нужно писать большой switch-блок в котором используется злое ключевое слово goto.

  • Если длина ожидаемого паттерна фиксирована, его можно описать с помощью обычной строки.

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

  • Паттерны с неорганиченной длинной сложнее разбирать. В C# мы бы могли использовать поиск по строке и Substring() для выделения определенного элемента.

  • У паттернов должен быть определенный порядок исполнения, нарушив который мы ломаем всю систему. Тем самым, имеет место ситуация, в которой схожие по предназначению паттерны находятся далеко друг от друга лишь потому, что некоторые из них обязательно должны быть в начале разбора. N.b.: я не исключаю, что можно выделять выборку целых блоков внутри одного паттерн-матчинга путем создания дополнительных вложенных функций.

  • Использование F# не добавило задаче той системности, которая могла бы сделать код полностью читаемым. Все равно нужно писать документацию к разным кейсам, точно так же как я это делал в C#.

  • Существуют определенные проблемы с мутабельностью, которые периодически будут появляться со временем разростания “контекста” разбора.

Надеюсь что в этом примере мне удалось наглядно продемонстрировать альтернативный подход к разбору строк в ситуации, когда обычные парсеры не работают. Не уверен что стоит рекоммендовать этот подход для всех типов задач, т.к. обычно для парсеров скорость разбора является критичной. Для меня к счастью она таковой не является, поэтому я продолжу использовать F#. Посмотрим, к чему меня это приведет. ■

Реклама

Written by Dmitri

18 февраля 2010 в 13:32

Опубликовано в f#

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

Subscribe to comments with RSS.

  1. Я так понял, что это Ваша программа? Возможно, кто-то еще захотел бы ей пользоваться, может выложить куда-то?

    melkorilya

    19 февраля 2010 at 12:11

    • Есть open-source версия на http://code.google.com/p/typografix/. Сейчас же программа содержит много NFR-компонентов (например MSAGL) а также завязки на собственные веб-сервисы. Желание написать доступную open-source версию есть, а вот времени нет.

      Dmitri

      19 февраля 2010 at 13:03

  2. F# — это сила! Определенно.

    build_your_web

    20 февраля 2010 at 1:26

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

    ChackNorris .net

    23 февраля 2010 at 0:22

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

    чешир

    9 августа 2011 at 8:10


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

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

Логотип WordPress.com

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

Фотография Twitter

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

Фотография Facebook

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

Google+ photo

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

Connecting to %s

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