December 27, 2011

Сопоставление объектов с образцом (pattern matching)

В функциональных языках есть интересная возможность, фактически являющаяся расширением идеи перегрузки функций - сопоставление с образцом. Для этого поддерживается специальный синтаксис шаблонов структур данных, позволяющий проверить что объект имеет определенный тип и/или поля, а также извлечь из него некоторые данные. Пример из haskell (частично взято тут wiki):

Без подсветки синтаксиса
-- f - функция от одного целого параметра
-- возвращающая целое
f :: Int -> Int
f 1 = 0
-- если ей передать 1, то она вернет 0
f _ -> 1
-- если что-либо другое - 1

-- map от чего угодно и пустого списка возвращает пустой список
map _ []     = []
-- рекурсия - map от функции и списка это конкатенация 
-- f от первого параметра и map от f и остатка списка
map f (x:xs) = f x : map f xs

-- разбор структуры
-- Foo это или Bar или Baz 
data Foo = Bar | Baz {bazNumber::Int, bazName::String}    
h :: Foo -> Int
-- Baz - это тип структуры, bazName - это имя поля
h Baz {bazName=name} = length name
h Bar {} = 0

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

Но тем не менее желание сделать что-то подобное для python возникало после каждого ковыряния в функциональщине и после каждой конструкции вида:

Без подсветки синтаксиса
if isinstance(x, Message):
    if x.mtype == DATA_READY and x.data is not None:
        #some code
        pass
    elif x.mtype == PROCESS_FINISHED:
        #some code
        pass
    # ....
# .....

А тут что-то захотелось посмотреть внимательно на модуль ast (abstract syntax tree) - давно не использовал его, последний раз еще во времена 2.4 - тогда очень жалел, что он не позволяет компилировать измененный ast (кстати делал интересный проект по портированию большого куска кода с PyQt3 на PyQt4 и ast позволил значительно автоматизировать этот перенос).

ast позволяет получить из python кода его результат после синтаксического разбора, но еще до компиляции в байтокод, исследовать его и/или изменять и компилировать новый вариант. Пример ast:

    a = f.b(1)

    =>

    Assign(
        targets=[Name(id='a', ctx=Store())], 
        value=Call(
                func=Attribute(
                    value=Name(id='f', ctx=Load()), 
                    attr='b',     
                    ctx=Load()), 
                args=[Num(n=1)], 
                keywords=[], 
                starargs=None, 
                kwargs=None
        )
    )

Фактически мы получаем исходный текст в удобном для ковыряния виде (правда несколько громоздком). Именно с абстрактными синтаксически деревьями работаю всяческие анализаторы кода, оптимизаторы и прочее. ast предоставляет некоторое количество вспомогательных функций и два класса - NodeVisitor для просмотра ast и NodeTransformer для модификации.

На этом все про ast. Что хотелось от сопоставления с образцом:

  • Чистый python синтаксис, что-бы никаких новых зарезервированных слов и IDE что-бы не ругались
  • Как-можно меньше кода при использовании
  • Обеспечить сопоставление с константой, типом, проверку атрибутов и вложенную проверку

После некоторого времени размышлений остановился на таком варианте:

Без подсветки синтаксиса
with match(x) as res:
    1 >> 2
    int >> x * 3
    str >> func_str(x)
    SomeType(c=V_c, d=V_c) >> on_val(V_c)
    SomeType(c=V_c, d=V_d) >> on_val2(x, V_c)

print "res =", res

Как это должно было-бы работать:

Без подсветки синтаксиса
if x == 1:
    res = 2
elif isinstance(x, int):
    res = x * 3
elif isinstance(x, str):
    res = func_str(x)
elif isinstance(x, SomeType) and \
     hasattr(x, 'c') and \
     hasattr(x, 'd') and \
     x.c == x.d:
    res = on_val(x.c)
elif isinstance(x, SomeType) and \
     hasattr(x, 'c') and \
     hasattr(x, 'd'):
    res = on_val2(x, x.c)
else:
    raise ValueError("{0!r} don't match any pattern!".format(x))

Совсем так, как хотелось, сразу не вышло. Вышло так:

Без подсветки синтаксиса
import python_match

@python_match.mathing
def come_func():
    # some code
    with python_match.match(x) as res:
        1 >> 2
        int >> x * 3
        str >> func_str(x)
        SomeType(c=V_c, d=V_c) >> on_val(V_c)
        SomeType(c=V_c, d=V_d) >> on_val2(x, V_c)

    print res.val

Из необязательных ограничений - нужно импортировать модуль python_match без переименования. Обернуть все функции, где используется сопоставление с образцом, декоратором 'python_match.mathing'.

Как это работает:

  • декоратор с помощью модуля inspect получает исходный код функции, разбирает его в ast и прогоняет через класс MatchReplacer
  • MatchReplacer наследует ast.NodeTransformer и перегружает метод visit_With, в котором подменяет ноду with на измененную конструкцию со сравнениями. Строка до >> изменяется на сравнение, а в строка после - подменяются переменные.
  • класс Match делает сопоставление объектов с образцом, если использовалось сравнение атрибутов.

Осталось некоторое количество ограничений, которые однако не принципиальные, так что поскольку задача скорее стояла из разряда - "как бы это сделать" я не стал заниматься дальнейшими оптимизациями/улучшениями.

Полный код тут - python_match.py, test_pm.py.

Ссылки:
          ru.wikipedia.org/wiki/haskell
          ru.wikipedia.org/wiki/Erlang
          en.wikipedia.org/wiki/Pattern_matching
          en.wikibooks.org/wiki/Haskell/Pattern_matching
          docs.python.org/library/ast.html
          github.com/koder-ua/python-lectures/blob/master/python_match.py
          github.com/koder-ua/python-lectures/blob/master/test_pm.py
          en.wikipedia.org/wiki/Abstract_syntax_tree

Исходники этого и других постов со скриптами лежат тут - github.com/koder-ua. При использовании их, пожалуйста, ссылайтесь на koder-ua.blogspot.com.

2 comments:

Anonymous said...

"Самое близкое что есть по интеллектуальности - перегрузка функций в C++" - є ще спеціалізації шаблонів (темплейт метапрограмінг) == як порахувати факторіал на С++ в компайл тайм

mohit said...

It's remarkable to pay a quick visit this website and reading the views If all colleagues about this paragraph.