DEV Community: TryAlgebra

Term rewriting system + pattern matching now in TryAlgebra

TryAlgebra — Sat, 10 Oct 2026 16:43:34 +0000

I wrote the 'term rewriting system' this spring. However, to use it in TryAlgebra, I had to create a system in which users can set up their own custom parser to convert mathematical expressions into terms and back again. This is because TRS works on terms, which have specific rules.

The workflow now looks like this: you select the expression, right-click and choose the formula you want to apply from the list of allowed formulas.

Click the arrow to perform the substitution.

This is where you write your formulas. You should create a separate file with this header and specify which TRS and parser to use. I know this may seem intimidating, but I'm working on ways to simplify the process. This is rather the prototype.

You also need to set up the algebra rules. These could be commutativity, distributivity, or your own rules.

The scariest part is the parser itself. This will be given further consideration. Currently, you specify rewriting rules to rewrite a selected expression into a term. The parser has two modes: top-down parsing with a single substitution at each level and an exhaustive top-down parser.
My aim is to make the parsing routine as intuitive as possible so that users can experiment with it. This is why I abandoned the Backus–Naur Form approach. I want something simpler and more math syntax oriented. So this part will definitely be redone.

The parsing file currently looks like this🫪.
The color indicates how the variable captures the symbols (one-multi, zero-multi or one).

Why term rewriting system is such a cool thing

TryAlgebra — Sat, 03 Oct 2026 08:04:51 +0000

The main feature of TryAlgebra is its ability to recognise formulas. Rather than applying formulas manually by rewriting expressions by hand, you simply select the expression to which you want to apply a formula, and choose it from the list of suggestions.
Previously, you created a file containing identities as a template for mathematical expressions, with placeholders that captured the actual values. TryAlgebra then attempts to apply these templates to the selected expression.

Simple string pattern matching, such as that used in regular expressions, is too restrictive. Furthermore, it does not recognize mathematical syntax, which can result in incorrect interpretation and matching. The solution is to parse the expression as a syntax tree, assigning a precedence order to each operator. Although this makes pattern matching more restrictive than simple string matching, fewer expressions will match the structured pattern. However, this approach at least preserves syntax and mathematical rules to some extent.

This still isn't very useful.
We want the system to be more flexible so that it can use some math to determine whether the expression matches the template. For example, it could apply the commutativity or distributivity properties. It could also cancel out something. This would make it really useful.

This is where the term rewriting system comes into play. It works like this: you provide it with basic mathematical identities, which it then uses to match the selected expression against the template.

These systems are used for compiler optimization and simplifying expressions, as well as in computer algebra systems. In fact, the range of applications is not as extensive as I thought. However, the idea and mathematical principles behind them are very powerful and fundamental to the entire field of mathematics. TRS is formalized in math books using notions from 'universal algebra'. This topic is also fundamental and abstracts the entire field of algebra. The main idea is that we do not need to know the actual meaning of functions; we can simply treat them as symbols, and the relationship between them can be described using equivalence classes.

I have currently implemented the TRS using saturation, which is similar to what Egg Optimizer does. Put simply, saturation involves applying identities to parts of the selected expression until it matches the template. There are few significant optimizations involved. The first is the equivalence graph, or e-graph, which stores mathematical expressions and all their rewritten versions in a compact way. The second is the congruence closure. I won't go into detail here, but this property enables more identities to be found without the need to apply mathematical rules. This property operates at a meta level and is applicable to any set of mathematical rules. It is actually a very simple property, but I will write about it in another post.

The example below illustrates how TRS algorithm is used.
It attempts to match '(ac + k)²' with '2ab + a² + b²' using listed identities. It is written in prefix notation; in TryAlgebra you'll be able to apply it to the familiar math notation. As you can see, it finds how to substitute a and b to match expressions modulo identities:

The following posts will provide more details on the main aspects of the TRS. There are actually a lot of interesting things!

Tree pattern matching

TryAlgebra — Sun, 27 Sep 2026 21:06:52 +0000

I managed to find a very effective decomposition of the pattern tree, which gives several useful properties for pattern matching. I finally finished the paper on this topic: https://zenodo.org/records/22972752

Here are the main highlights:

The algorithm treats unresolved variables as connections between different parts of the tree.
Using these connections, it identifies independent parts of the pattern, each corresponding to its own system of Diophantine equations.
During matching, the tree can be matched against independent parts of the pattern in parallel, since the result of matching one part does not affect the matching process of another.
As a bonus, the backtracking is very simple, and the algorithm can be implemented as a straightforward recursive function.

Monthly update post

TryAlgebra — Sun, 27 Sep 2026 21:04:51 +0000

A short monthly progress report:

Added the ability to select a folder/project before starting work.
Added some of the missing mathematical elements.
Improved the mathematical element selector so that it appears next to the cursor.
Added Ctrl+Z/Y support.
Added a command system for quick input.
Added a window that displays the project structure.
Added a scroll bar.
Made various minor UI improvements.

I’m currently working on the formula system. The main components are already in place. The next step is to implement the project compiler, which will collect formulas, algebraic rules, and parsing rules and link them together.

TryAlgebra is an experimental mathematical editor and symbolic computation project

TryAlgebra — Sun, 27 Sep 2026 21:02:41 +0000

It is a WYSIWYG math editor with tools for defining formulas, parsing rules, and an algebraic term rewriting system.

I’m developing the project from scratch and will use this blog to share progress, implementation details, design decisions, and experiments along the way.