Я хотел бы знать, какая библиотека сопрограмм подходит для реализации следующего алгоритма, который представляет собой упрощенную модель проблемы коммутативной обработки шаблонов из символьных выражений (предстоит решить) в C ++ с открытым исходным кодом система компьютерной алгебры ). В целом, правильно ли предполагать, что требуются стеки сопрограммы? Есть ли альтернативы C ++ вне сопрограмм?
Учитывая два дерева (или DAG) произвольной длины, содержащих три типа узлов, черный / красный с произвольным числом дочерних элементов; чёрные узлы имеют своих детей в фиксированном порядке, в отличие от чёрных узлов, порядок детей не имеет значения; и уходит. Алгоритм определения соответствия обоих деревьев сильно усложняется коммутативной природой красных узлов и тем фактом, что не имеет канонического порядка, поэтому вы не можете просто отсортировать все дочерние элементы узла . Пример:
Source Pattern
red1--->leaf1, leaf2 Red1--->Leaf1, Leaf2
| |
red2--->leaf1, leaf2 Red2--->Leaf2, Leaf1
Стандартный (некоммутативный) случай легко реализуется с использованием иерархии классов и рекурсивного вызова виртуальной функции-члена match(), которая соответствует самому узлу, а затем каждому из дочерних элементов. Здесь leaf1 и Leaf2 оказываются разными, рекурсивный вызов возвращает False. Однако, если красные являются коммутативными, то на красном узле алгоритм 1. должен пройти через все перестановки своих узлов, и 2. если вызов к красному match() успешен, цикл перестановки должен быть приостановлен, потому что это может произойти что вызывающий абонент терпит неудачу и требуется другое совпадение. Недостаточно сохранить состояние в вызывающей стороне, поскольку сам вызываемый объект мог бы сам вызывать match(), и его тоже нужно перезапустить, иначе пропущено возможное решение.
На функциональном языке yield в рекурсивном вызове поможет. Например, пакет matchpy имеет реализацию Python. Это похоже на задачу сопрограммы, но какую библиотеку вы бы использовали? boost::coroutine подходит только для этого? С ++ 20 принесет нам эту функциональность? Может ли Clang сделать это уже?