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

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

Перегрузка оператора

Python позволяет программистам изменять значение некоторых своих синтаксических конструкций, когда эти конструкции применяются к объектам определяемых программистом классов (более подробно определение синтаксиса Python обсуждается в предыдущей статье). Программисты могут сделать это, определив специальные методы в определении класса. Когда интерпретатор Python увидит, что определенный оператор (например, +) применяется к объектам класса, для которого определен такой специальный метод (например, __add__), интерпретатор вызовет этот метод.

В приведенном ниже примере класс vector позволяет пользователям создавать объекты, представляющие двумерные векторы. В определении класса есть метод __eq__.

class vector():
    def __init__(self, *coordinates):
        self.coordinates = coordinates
def __eq__(self, other):
        return self.coordinates == other.coordinates

Метод __eq__ вызывается, когда два объекта vector передаются оператору infix==.

>>> v = vector(1, 2)
>>> w = vector(3, 4)
>>> (v == w, v == v)
(False, True)

Встроенный язык для логических схем

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

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

Для целей этого примера предположим, что программист представляет биты, используя целые числа Python 0 и 1. Один из подходов, который может использовать программист, состоит в том, чтобы определить функцию, которая работает с целыми числами и использует встроенные логические операторы Python для целых значений.

def equal(x, y):
    return (x & y) | ((1 - x) & (1 - y))

Ниже приведены два подхода, которые может использовать программист Python (первый — императивный стиль, а второй — функциональный стиль) для реализации функции равенства equals для битовых векторов с использованием функции равенства equal для битов, которая определена выше. Вы хотели бы, чтобы ваша библиотека схем соответствовала всем этим различным подходам (поскольку эти подходы отражают разные компромиссы, которые могут подходить для разных вариантов использования, или просто потому, что у программистов могут быть разные предпочтения или уровни опыта работы с Python).

def equals(xs, ys):
    z = 1
    for i in range(len(xs)):
        z = z & equal(xs[i], ys[i])
    return z
def equals(xs, ys):
    from functools import reduce
    es = [equal(x, y) for (x, y) in zip(xs, ys)]
    return reduce((lambda e0, e1: e0 & e1), es)

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

>>> equals([0,1,1], [0,1,1])
1

Используя перегрузку, можно предоставить новые определения для встроенных операторов &, | и -, которые программисты уже использовали для определения функций equal и equals. Приведенное ниже определение класса circuit включает методы __or__, __and__ и __rsub__, соответствующие способу использования этих трех инфиксных операторов.

class circuit():
    def __init__(self, op='bit', args=None):
        self.op = op
        self.args = [] if args is None else args
def __or__(self, other):
        return circuit('or', [self, other])
def __and__(self, other):
        return circuit('and', [self, other])
def __rsub__(self, other):
        if not isinstance(other, int) or other != 1:
            raise ValueError('can only subtract from 1')
        return circuit('not', [self])
def __repr__(self):
        return 'circuit("' + self.op + '", ' + str(self.args) + ')'
def __str__(self):
        return self.__repr__()

Чтобы упростить просмотр схем после их создания, приведенное выше определение также включает рекурсивный метод __repr__ и эквивалентный метод __str__. Первый метод вызывается, когда Python пытается отобразить объект класса (например, в интерактивной подсказке), а второй вызывается, когда встроенная функция Python str применяется к объекту класса. класс circuit.

Теперь программист может построить схему, используя знакомые инфиксные операторы. Единственное отличие состоит в том, что вместо использования целых чисел Python для представления битов, составляющих входные данные (то есть, базовые случаи), программисты могут использовать объекты circuit, представляющие битовые константы.

c0 = circuit("bit", 0)
c1 = circuit("bit", 1)
c2 = 1 — (c0 & c1)

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

>>> equal(c1, c2)
circuit("or", [circuit("and", [circuit("bit", 1), circuit("not", [circuit("and", [circuit("bit", 0), circuit("bit", 1)])])]), circuit("and", [circuit("not", [circuit("bit", 1)]), circuit("not", [circuit("not", [circuit("and", [circuit("bit", 0), circuit("bit", 1)])])])])])

Даже более сложный метод equals работает безупречно, независимо от того, заданы ли ему списки битовых векторов или списки базовых схем.

>>> equals([c0, c1], [c0, c1])
circuit("and", [circuit("or", [circuit("and", [circuit("bit", 0), circuit("bit", 0)]), circuit("and", [circuit("not", [circuit("bit", 0)]), circuit("not", [circuit("bit", 0)])])]), circuit("or", [circuit("and", [circuit("bit", 1), circuit("bit", 1)]), circuit("and", [circuit("not", [circuit("bit", 1)]), circuit("not", [circuit("bit", 1)])])])])

Портативные или специализированные вложения через наследование

Преимущество определения circuit в разделе выше заключается в том, что программисты могут создавать новые схемы, используя существующие встроенные операторы Python. Однако для проверки или обхода структуры данных схемы программисты должны ознакомиться с определением вашего класса. Используя наследование, вы можете устранить это второе препятствие.

Приведенный ниже вариант класса circuit представляет схемы как словари (точнее, как объекты классов, наследующие все возможности словарей).

class circuit(dict):
    def __or__(self, other):
        return circuit({'or': [self, other]})
def __and__(self, other):
        return circuit({'and': [self, other]})
def __rsub__(self, other):
        if not isinstance(other, int) or other != 1:
            raise ValueError('can only subtract from 1')
        return circuit({'not': [self]})

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

>>> c0 = circuit({"bit": 0})
>>> c1 = circuit({"bit": 1})
>>> import json
>>> print(json.dumps(equals([c0, c1], [c0, c1])))
{"and": [{"or": [{"and": [{"bit": 0}, {"bit": 0}]}, {"and": [{"not": [{"bit": 0}]}, {"not": [{"bit": 0}]}]}]}, {"or": [{"and": [{"bit": 1}, {"bit": 1}]}, {"and": [{"not": [{"bit": 1}]}, {"not": [{"bit": 1}]}]}]}]}

В качестве другого примера этого более специализированного подхода рассмотрим приведенный ниже класс circuit, производный от класса Graph в библиотеке NetworkX. В этой реализации каждый объект circuit представляет собой граф, в котором узлы соответствуют базовым случаям или операциям, а ребра соединяют узлы операций с их операндами. Метод, соответствующий бинарному оператору, такому как &, выполняет следующие шаги:

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

Обратите внимание, что для того, чтобы иметь математическую нотацию в метках узлов при окончательном отображении схемы, для строк имени оператора используется нотация LaTeX.

from networkx import Graph, union
class circuit(Graph):
    def __init__(self, arg=None):
        Graph.__init__(self)
        if arg is not None:
            self.add_nodes_from([str(arg)])
def __or__(self, other):
        c = union(
            circuit("$\\vee$"),
            union(self, other, rename=("l-", "r-"))
        )
        c.add_edges_from([
            ("$\\vee$", "l-" + list(self.nodes)[0]),
            ("$\\vee$", "r-" + list(other.nodes)[0])
        ])
        return c
def __and__(self, other):
        c = union(
            circuit("$\\wedge$"),
            union(self, other, rename=("l-", "r-"))
        )
        c.add_edges_from([
            ("$\\wedge$", "l-" + list(self.nodes)[0]),
            ("$\\wedge$", "r-" + list(other.nodes)[0])
        ])
        return c
def __rsub__(self, other):
        if not isinstance(other, int) or other != 1:
            raise ValueError('can only subtract from 1')
        c = union(circuit("$\\neg$"), self, rename=("", "n-"))
        c.add_edges_from([("$\\neg$", "n-"+list(self.nodes)[0])])
        return c

Этот подход позволяет визуализировать графическую диаграмму непосредственно из объекта circuit с помощью библиотеки NetworkX. Чтобы продемонстрировать, как это может сделать программист, рассмотрим следующую схему c, построенную с использованием исходного метода equals (обратите внимание, что он не был изменен и все же работает с объектами новейшего варианта circuit).

c = equals(
    [circuit('$x_0$'), circuit('$x_1$')], 
    [circuit('$y_0$'), circuit('$y_1$')]
)

Поскольку c наследует все функции объекта NetworkX Graph, программист может проверять его узлы и ребра. В приведенном ниже примере извлекаются последние три узла и количество ребер в графе схемы. Обратите внимание, что имя каждого узла представляет собой строку, описывающую путь к этому узлу от общего выходного узла схемы (где 'l' и 'r' представляют левый и правый подграфы соответственно).

>>> (list(c.nodes)[-3:], len(c.edges))
(['r-r-l-n-$x_1$', 'r-r-r-$\\neg$', 'r-r-r-n-$y_1$'], 18)

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

def position(n):
    # Generate coordinates based on the path
    # encoded in the node name.
    x = sum(
        {'l':-1, 'r':1}.get(c, 0)/(2**(i+3)) 
        for (i, c) in enumerate(n.split('-'))
    )
    y = n.count('-')/8
    return (x, y)

С помощью функции положения отобразить схему c в виде графика очень просто, используя функцию draw_networkx. Позиции визуализированных узлов задаются путем создания словаря с использованием position, а метки для визуализированных узлов получаются путем взятия последнего компонента имен узлов в c.

from networkx import draw_networkx
draw_networkx(
    c,
    pos=dict((n, position(n)) for n in c.nodes),
    labels=dict((n, n.split('-')[-1]) for n in c.nodes),
    node_size=1000,
    node_color="orange"
)

Дальнейшее чтение

В этой статье представлен краткий обзор перегрузки операторов в Python с мотивирующим примером, включающим ряд встроенных предметно-ориентированных языков для определения схем. Библиотека Python, которая адресована точно такому же сценарию использования, рассмотренному в этой статье, называется схема, которая определяет встроенный язык для построения схем, как определено в библиотеке схема. Другие примеры многофункциональных и широко используемых предметно-ориентированных языков, встроенных в Python, включают веб-фреймворк Django и библиотеку анализа данных pandas. Однако даже небольшие встроенные библиотеки, такие как типирование, используют перегрузку операторов, чтобы упростить работу программистов.

Многие другие языки программирования поддерживают некоторую форму перегрузки операторов, а также введение пользовательских инфиксных, префиксных и даже постфиксных операторов. Некоторые языки имеют обе эти особенности. Более общим термином для возможности перегрузки операторов является специальный полиморфизм: возможность предоставлять несколько определений для одной и той же синтаксической конструкции (при этом либо интерпретатор, либо компилятор определяет, какое определение использовать на основе типов). входов). Существуют и другие отдельные типы полиморфизма, такие как параметрический полиморфизм: возможность применять одну и ту же функцию (имеющую одинаковое синтаксическое определение) к аргументам разных типов. Вы могли заметить, что определения equal и equals в этой статье на самом деле являются примерами параметрического полиморфизма.

Эта статья также доступна в формате Jupyter Notebook и в формате HTML на GitHub.