Recursive Foundations - #2

The first glyph hums. A second joins it, then a third—repeating, not merely growing. The system awakens not through addition, but reflection. It begins to recognize its own shape.

This article continues the construction of Vellum, a C# library for symbolic mathematics. If the first hundred lines laid the foundation, this next phase was about recursion: expressions within expressions, types that reproduce their own shape, and methods that evaluate themselves through structures already in place.

The foundation was there—but it was still malleable. This is among the phases I love most in a project: everything is still open to change, but you also have a system that works. With the base types defined, new ideas could take root quickly. One example: because Add() was already present on all terms, it became possible to jump straight into implementing evaluation, figuring out the specifics along the way. That kind of immediacy—being able to build real behavior without touching the foundation: that’s a sign the design’s already holding. And it's what makes this phase so powerful—a space to cultivate ideas before they fade.

I hope what comes through in this article is the newfound sense of structure. Even with a system this raw, this feature-less on the surface, the foundation was enough to expand on seamlessly. That, to me, is the purpose of designing code with care.

1. From ExpressionComponent to True Nesting

In the early design of Vellum, I relied on an abstraction called ExpressionComponent to give expressions a place to store their terms—whether those were atomic terms or nested expressions. At the time, the list looked like this:

public class Expression<T> : Term<T> where T : ExpressionComponent
{
    public List<T> Terms { get; } 
}

public abstract class Term<T> : ExpressionComponent where T : ExpressionComponent

Here, T was intended to represent the type of term that made up the expression: for example, NumericExpression would be an Expression<NumericTerm>. But because Expression couldn't inherit from T directly as T is a generic type, this meant that nested expressions couldn’t live inside other expressions—not without casting, or a shared base like ExpressionComponent.

The workaround looked like this:

protected override Expression<ExpressionComponent> Add(Term<T> other) =>
    new([this, other]); 

This allowed mixing term types (like atomic terms and expressions), but only by returning a less-specific, lossy version of the expression. And it required treating T as a loose, somewhat inconsistent placeholder—sometimes a concrete term, sometimes a base type.

I had initially parameterized Expression<T> to represent the type of terms it would contain—for example, NumericExpression : Expression<NumericTerm>—but this quickly became brittle. Eventually, I stopped to ask: why am I trying to store T at all? Why not store the thing all T types inherit from—Term<T>? So I changed the internal structure:

public class Expression<T> : Term<T> where T : Term<T> 
{
    public List<Term<T>> Terms { get; } 
}

With this change, something important became possible. Consider the class hierarchy:

public class NumericTerm : Term<NumericTerm> { }

public class NumericExpression : Expression<NumericTerm> { } 
// Expression<NumericTerm> inherits from Term<NumericTerm>

This means:

• NumericTerm is a Term<NumericTerm>
• NumericExpression is also a Term<NumericTerm>

But NumericExpression is not a NumericTerm (because generic classes aren't covariant in C#). That distinction is key. With Terms now holding a list of Term<NumericTerm>, both atomic terms and nested expressions can live together in a single expression, without casting or special rules.

This recursive structure is what that self-referencing generic setup (CRTP) was pointing toward all along.

And the effect on the code was immediate. The Add method in Expression<T> became beautifully simple:

protected override Expression<T> Add(Term<T> other) =>
    new([..Terms, other]); 

Suddenly, it all lines up. Terms, nested or not, slide into the same slot—type-safe, consistent, no fuss. No lossy casting, no generic confusion. Just a consistent shape, folding back into itself.

2. The WithCoefficient Design

WithCoefficient() emerged from a need to distribute. Specifically, I wanted to support scalar multiplication—multiplying an entire expression by a number. That required distributing the expression’s overall coefficient (and sign) to each of its terms. The cleanest way to do that was to allow this:

int multiplier = 3; // example scalar multiplier
Term<T> newTerm = multiplier * someTerm;

Since terms in Vellum are meant to be immutable, this operation couldn’t modify the term—it had to return a new one. That meant defining a deep copying method that could safely and cleanly set a new coefficient. I thought there should be both a Copy() method for cloning the term, and a specialized WithCoefficient() method to copy and set a new coefficient.

At first, I thought Copy() should be the abstract method. Conceptually, it felt more foundational. Copy() is the root idea: take a term and reproduce it. WithCoefficient() felt like a specialization—something you might build on top of a copying mechanism.

But in practice, the opposite made more sense. The act of copying in this system wasn’t general—it was specific. So I reversed them:

public Term<T> Copy(double? coefficient = null) =>
    WithCoefficient(coefficient ?? this.Coefficient);

public abstract Term<T> WithCoefficient(double coefficient);

Copy() now delegates to WithCoefficient(), not the other way around. Why? Because WithCoefficient() has no ambiguity. It always returns the same structure, with a new coefficient. No conditionals. No null checks. It’s simple and clear. Copy(), on the other hand, adds optionality—an override if you want it. A weird flip on paper, but surprisingly clean in practice.

All a deriving class needs to do now is simply call its own constructor:

public class NumericTerm(double coefficient, Sign sign = default)
    : Term<NumericTerm>(coefficient, sign)
{
    public override NumericTerm WithCoefficient(double coefficient) =>
      new(coefficient, this.Sign);
}

And the benefits didn’t stop there. Suddenly, evaluation became a one-liner:

return Terms
    .Aggregate((a, b) => a + b)
    .WithCoefficient(CoefficientWithSign);

That final wrapper—WithCoefficient()—applies CoefficientWithSign, a convenience that pre-applies the expression’s sign through Sign * Coefficient. It’s a small thing, but it makes the math align cleanly.

The overloaded + operator already handled symbolic addition: it routes directly to the Add() method on the left-hand operand. So a + b isn't just math—it's type-aware dispatch. WithCoefficient() gave me the final wrapper, applying the sign and coefficient of the expression itself. It reads exactly like the math it represents, and somehow, it just... works.

For example, this expression:

new NumericExpression(
    [new NumericTerm(2), new NumericTerm(3)], 
    coefficient: -2
    ).Evaluate();

Evaluates to -2(2 + 3) → -10. The Aggregate() step handles the addition, and WithCoefficient() applies the outer sign and scaling.

Having a simple, robust way to recreate terms—without mutating them—feels like a quiet superpower. It means I can enforce immutability everywhere else with confidence. Every subclass just builds itself. No reflection, no cleverness—just the constructor doing what it’s supposed to. It’s kind of refreshing: constructors, behaving like constructors.

3. Simplify and Evaluate

Evaluate didn’t begin as a feature—it began as a test. I wanted to verify that the Add() methods were doing the right thing, and in doing so, stumbled into one of the cleanest behaviors in the system.

To evaluate a simple sum like 2 + 3 + 4, you write:

new NumericExpression([
    new NumericTerm(2),
    new NumericTerm(3),
    new NumericTerm(4) 
    ]).Evaluate();

Internally, the expression's Evaluate method looks like this:

public Term<T> Evaluate() 
{
    if (IsSingleTerm)
        return this;

    return Terms
        .Aggregate((a, b) => a + b)
        .WithCoefficient(CoefficientWithSign); 
}

Here’s the key: a + b doesn’t return a single Term<T>—it returns an Expression<T>, even when both operands are atomic terms. This preserves grouping and makes every addition structurally consistent. But crucially, the implementation of Add() includes a check for single-term expressions:

protected override Expression<T> Add(Term<T> other) 
{
    if (IsSingleTerm) return Terms[0] + other;

    return new([..Terms, other]); 
}

So the evaluation unfolds like this:

• Step 1: (2 + 3) becomes a single-term expression containing 5.
• Step 2: That result is added to 4. Because it's now a single-term expression, the Add() method unwraps it and adds directly.
• Step 3: Final result is a clean 9.

The full collapse looks like:

2 + 3 + 4
→ (5) + 4
→ 9

It’s just enough separation to track groupings—without introducing unnecessary layers or recursion. And all of it happens through the natural shape of the system. Really—this one pattern carried further than I ever expected.

But Evaluate() alone only handles the top-level expression. What if the terms themselves contain expressions that need to be evaluated first?

That’s where EvaluateAll() comes in:

public Term<T> EvaluateAll()
{
    List<Term<T>> evaluatedTerms = Terms.Select(term =>
        term is Expression<T> expr ? expr.EvaluateAll() : term
    ).ToList();
  
    Expression<T> newExpression = new(evaluatedTerms, Coefficient, Sign);
    return newExpression.Evaluate();
}

EvaluateAll() does a deep traversal: it walks the list of terms, evaluates any sub-expressions recursively, and then evaluates the resulting flat structure at the top level. It's the method that ties everything together—recursion, evaluation, and structure—all in one pass. It's simple, but it captures the core idea: each layer trusts the one below to simplify itself first.

Evaluate() is shallow—it assumes the terms are already simplified. It’s quick, local. EvaluateAll(), by contrast, does a full traversal. It’s for when you don’t trust your inputs yet. Now, when evaluating nested expressions, the structure holds—and becomes even more expressive.

Take the following expression:

new NumericExpression([
    new NumericExpression([2, 3, 4], coefficient: 2),
    new NumericExpression([1, 4]) ]
    ).EvaluateAll();

Mathematically, this is:

2(2 + 3 + 4) + (1 + 4) 
→ 2(9) + (5)

And because each term is immutable, distributing the coefficient is safe to do upfront—through a Simplify() call that just returns new terms with adjusted values.

Because the outer expression has a coefficient (2), the Add() method integrates that call to Simplify()—a simple LINQ query that distributes the coefficient through each term—before performing the addition:

protected override Expression<T> Add(Term<T> other) 
{
    Expression<T> simplified = Simplify();

    if (simplified.IsSingleTerm)
        return simplified.FirstTerm + other;  // FirstTerm = Terms[0]

    return new([..simplified.Terms, other]); 
}

public Expression<T> Simplify() =>
    new(Terms.Select(t => CoefficientWithSign * t).ToList());

So 2(2 + 3 + 4) is first simplified into (4 + 6 + 8) and evaluated to (18). The resulting single-term expression collapses to its first term—18—within the Add() method, which tries to add 18 + (5).

But now the right-hand side is an expression, not a term. And this is where things get subtly powerful—because Expression.Add() already knows how to collapse a single-term expression:

if (simplified.IsSingleTerm)
    return simplified.FirstTerm + other;

The logic in NumericTerm.Add() just needs to flip the operation, to let Expression.Add() take over—here's what that looks like in practice:

public class NumericTerm : Term<NumericTerm> 
{
    protected override Expression<NumericTerm> Add(Term<NumericTerm> other)
    {
        // Delegate addition to Expression.Add()
        if (other is Expression<NumericTerm> expr)
            return expr + this;

        double sum = CoefficientWithSign + other.CoefficientWithSign;
        return new([new NumericTerm(coefficient: sum)]);
    } 
}

That first if is key: it flips addition order when faced with an Expression, letting the expression’s own logic handle the details:

if (other is Expression<NumericTerm> expr)
    return expr + this;

So 18 + (5) becomes (5) + 18. Why flip? Because only the expression knows how to flatten its terms—and if we’re adding to one, we want its own logic to take over.

The final collapse looks like this:

2(2 + 3 + 4) + (1 + 4) 
→ 18 + (5) 
→ (5) + 18 
→ 23

The fact that these rules emerge naturally from the structure is what makes this system feel right. There’s no branching logic for “if the term is an expression, do this.” It’s built into the shape of the types, and how they delegate responsibility to each other.

And while Evaluate() skips aggregation for single-term expressions with:

if (IsSingleTerm)
    return this;

—that check alone doesn’t cause expressions to collapse into their contents. It just avoids unnecessary work.

But the actual collapse—when nested structures flatten fully—happens inside Expression.Add():

if (simplified.IsSingleTerm)
    return simplified.FirstTerm + other;

That’s how (9) + 3 becomes 12, not just a new layer of (9 + 3). The expression delegates to the term directly, treating it as the true representative of the structure when it's alone. It's a small decision, but one that makes recursive evaluation both safe and elegant.

4. Numeric Sugar and Initialization

With recursive structure and evaluation working smoothly, the next challenge was initialization—especially for types like NumericExpression, which often need to hold both atomic terms and nested expressions.

The goal was twofold:

• Keep nesting trivial to express.
• Allow initialization from a List<NumericTerm>, to support this implicit conversion:

public static implicit operator NumericTerm(double coefficient) =>
    new(coefficient);

This makes it possible to write clean, intuitive expressions like:

new NumericExpression([1, -2, 3])  // equivalent to (1 - 2 + 3)

But because Expression<T> now expects List<Term<T>>, not List<T>, and NumericTerm : Term<NumericTerm>, the list had to be cast:

public NumericExpression(List<NumericTerm> terms, double coefficient = 1, Sign sign = default)
    : this(terms.Cast<Term<NumericTerm>>().ToList(), coefficient, sign) { }

It’s the first clear tradeoff in the project so far. The cast is safe, given the CRTP structure, but not ideal. While the abstraction ensures type integrity, relying on a cast—even an internal one—feels like something to improve upon later.

To make usage even smoother, a third constructor was added for syntactic sugar:

public NumericExpression(params NumericTerm[] terms)
    : this(terms.ToList()) { }

This enables:

new NumericExpression(1, 2, 3)  // 1 + 2 + 3

But there's still a limitation. Because each constructor handles a specific format (either atomic or already structured), nesting expressions isn’t as seamless as it could be. For instance, writing:

new NumericExpression(
    new NumericExpression([1, 4]),
    new NumericTerm(3) 
    )

works—but it requires explicitly calling a constructor to build the nested expression. Ideally, in the future, a single unified constructor (or parser) would allow:

new NumericExpression(1, 4, [3, 2, 1])

Or even just:

"1 + 4 + (3 + 2 + 1)"

—relying on string parsing to handle the structure automatically.

For now, the constructor system is a solid step. It balances safety, clarity, and practical expressiveness, while laying the groundwork for more flexible input down the line.

The Lantern Moment: Structure Echoes Structure

If the first hundred lines were about laying a foundation, this next phase was about watching it fold in on itself—gracefully, almost effortlessly.

With recursion built into the type system, each part of Vellum began to echo the others. Expressions could contain terms, or other expressions, or even expressions made of expressions. Evaluation became a single LINQ query. Distribution of signs and coefficients followed naturally from the structure. The system didn’t just allow recursion—it understood it.

And that’s the most satisfying kind of design: where nothing feels patched, nothing feels forced. The types suggest their own behavior. You write a new method, and it works not because you made it clever—but because the foundation already knew how to support it. Even the limitations—the safe cast, the verbose constructors—felt like invitations to refine, not warnings of failure. Because the shape of the system was right. Everything else would grow from here.

A System That Knows Itself

Vellum still has no parser. No simplifier. No symbolic resolution. And yet, it can already evaluate nested expressions with sign and coefficient, distribute scaling, collapse parenthetical layers, and return the right result. Not through tricks—but through type structure, thoughtful delegation, and recursive honesty.

The next step will make all this structure more approachable—translating text into symbols, and symbols into meaning. But even now, the system knows what it is. It has shape. It has clarity, and that’s enough—for now. Sometimes, that’s the hardest part to design: a system that doesn’t need more to feel complete.