Я сейчас этим самым занимаюсь) Выложу тут когда доделаю вещи типа скоупа/продолжений/quote-eval-apply. Кстати самое трудное для меня оказалось писать сами правила редукции для выражений, а не интерпретатор

А Вы вариант Норвига на том же Лиспе из его учебника видели?

Во-первых, Computer Algebra System - это очень старая и очень развитая область с большим разнообразием систем, как коммерческих, так и OpenSource на всевозможных языках. Есть на что посмотреть и откуда потырить приёмы.
Во-вторых, term rewriting systems и graph rewriting systems - очень развитые области математики с большим количеством интересных результатов как разрешительного, так и запретительного свойства. Если максимально близко к теме чата, то можно посмотреть на реализацию языка Pure - там и term rewriting, и LLVM под капотом.

Если чесно, я вообще не смотрел как это делается по нормальному, по этому нет. Сначало пусть заработает а потом начну оптимизировать)

Круто! Будет очень интересно посмотреть. Я тоже таким в школе занимался. Но тогда мои программистские знания были очень скудны, но что-то интуицией и часами дебага я написал :D

Спасибо! graph rewriting system выглядит как то что нужно)

Ой-ой. Вот графовый вариант Вам ТОЧНО не нужен %)

На самом деле, во многих реальных CAS все делается не так красиво, как в системах переписывания. Но, зато, значительно более эффективно.

Term - это дерево, а дерево - это частный случай графа. 😃
Но так-то, да, я с Вами согласен. 😊

Ну я сейчас в универе этим занимаюсь, по интуиции и с часами дебага. Зато весело)

Ну, просто слишком жестоко получается: "что, сынок, решил символьный калькулятор для производных сделать? А почитай-ка для начала учебники от Hartmut Ehrig, разберись в DPO и SPO...". %)

А вы не слишком ли лихо киваете на Математику? Там числа - далеко не ieee754, что и позволяет относительно вольно делать преобразования.

Кроме того, там на каждом шаге можно проконтролировать результат.

Как же я сам не додумался представлять полином в виде вектора.. После этого все получается так просто и коротко, не то что у меня - пара десятков правил из школьной математики, которые в итоге не работают)

Кстати про DSL, интерпретаторы и компиляторы: https://docs.google.com/presentation/d/1Yrs5FOohrASL66qt4LNv6M0752ceYPH1GhdL3uV01B8/edit?usp=sharing

По поводу ограничений метода базирующего на правилах (https://github.com/norvig/paip-lisp/blob/master/docs/chapter8.md#85-limits-of-rule-based-approaches), разве не достаточно таки взять и отсортировать термы? Я так делаю и, по крайней мере, те проблемные кейсы из раздела прохожу.

Все можно сделать на системе переписывания, если она является Тьюринг-полной. Другой вопрос, что применение множества локальных правил часто оказывается слишком накладным, сами правила не так просто подобрать.
Возможно, Вы уже сделали то, что Норвиг предлагает в 15 главе: https://github.com/norvig/paip-lisp/blob/master/docs/chapter15.md

Понятно, логично. Я именно сортирую термы правилами a + b -> b + a | b < a (и такой же вариант для ассоциативности). Но вот собираюсь сделать то что в 15 главе, тоесть базировать на полиномах представленных в виде вектора так как это явно быстрее и проще

Нюанс с системами переписывания еще в том, что нужно осторожно подбирать как сами правила, так и стратегии их применения. Есть понятия конечной завершимости и конфлюэнтности. На том же a + b -> b + a можно легко впасть в бесконечный цикл :)

А где-нибудь нормально разобрано, как этого избегать в наиболее типичных случаях?

Существует, например, алгоритм Кнута-Бендикса.

То есть, через отношение порядка.

А без? Это вообще возможно?