L4 — Building trees without the parser

Goal: construct an expression in code, so your program can generate mathematics instead of printing a string and reading it back.

import it.grypho.scala.leonardo.core.*
import it.grypho.scala.leonardo.scalar.*
import it.grypho.scala.leonardo.parser.Parser

Why not just build a string?

Because you would be encoding a tree you already have into text, and then asking a parser to recover it — a round trip with a parse error waiting at the end of it, and an escaping problem in the middle. The moment an expression comes from your program rather than from a user — coefficients out of a fit, one term per row of data, a formula assembled by a UI — build the node.

The parser exists for text you did not write. Everything it produces, you can produce directly.

The atoms

Two, and you have met both:

val x = _Variable("x")
val two = _Number(2)

_Variable is a symbolic atom and _Number a concrete value — which is L2’s distinction, and it is why one of these is a _Value and the other is not.

The operations are binary

Sum, Product, Ratio and Power each take exactly two operands. There is no n-ary sum node, so three terms are two Sums:

val built = Sum(Sum(Power(x, two), Product(_Number(3), x)), two)

built.toString
// res0: String = "(((x ^ 2.0) + (3.0 * x)) + 2.0)"

Every operation prints fully parenthesised, which looks heavy and is deliberate: it is what makes the printed form re-parse to the identical tree, whatever it is nested inside.

Parser.parse(built.toString).get == built
// res1: Boolean = true

That is the round-trip invariant the library holds itself to, and it is the cheapest test you can write against a tree you built: print it, parse it, compare.

It is also worth checking your tree against what a human would type:

Parser.parse("x^2 + 3x + 2").get == built
// res2: Boolean = true

They agree — but only because the nesting above mirrors the grammar. + associates to the left, so a + b + c is Sum(Sum(a, b), c) and a right-nested tree would be a different (if mathematically equal) expression. ^ goes the other way:

Parser.parse("2^3^2").get == Power(_Number(2), Power(_Number(3), _Number(2)))
// res3: Boolean = true

If you are going to compare trees, build them the way the grammar reads them. If you only mean to compare values, evaluate both instead.

Functions and binders are nodes too

A function node wraps its argument; nothing is special about it:

Sin(Product(two, x))
// res4: Sin = Sin(Product(a = _Number(2.0), b = _Variable("x")))

A binder is the one place the types get stricter. _Derivative takes a _Variable, not an expression — because differentiate with respect to 2x is not a thing you can mean:

_Derivative(built, Product(two, x))
// error:
// Found:    it.grypho.scala.leonardo.scalar.Product
// Required: it.grypho.scala.leonardo.core._Variable
// _Derivative(built, Product(two, x))
//                    ^^^^^^^^^^^^^^^

With a variable it is an ordinary node, and evaluating it runs the derivative:

_Derivative(built, x).eval(Environment())
// res6: Either[_Expression, _Value] = Left(
//   Sum(a = Product(a = _Number(2.0), b = _Variable("x")), b = _Number(3.0))
// )

Or call the algorithm directly

You do not have to build a node to run an algorithm — derive, simplify, integrate and the rest are plain functions over expressions. Syntax turns them into method calls, which reads better when they chain:

import it.grypho.scala.leonardo.scalar.Syntax.*

built.derive(x).simplifyFully()
// res7: _Expression = Sum(
//   a = Product(a = _Number(2.0), b = _Variable("x")),
//   b = _Number(3.0)
// )

Syntax is sugar for the algorithms and nothing else. There are no arithmetic operators on expressions — a + b does not compile for two _Expressions, and that is on purpose: + would have to choose between Sum and MatSum without knowing what it is holding, which is a decision the parser makes structurally and eval makes again at run time. Naming the node you mean costs one word and removes the guess.

The difference between the two nodes and the function, worth having straight:

  • _Derivative(e, x) is the derivative, unevaluated — a tree you can store, print, or hand to something else;
  • derive(e, x) (or e.derive(x)) computes it now and gives you the result.

Generating an expression from data

This is the payoff. A polynomial from a coefficient vector, lowest degree first — the shape collect hands back, so this is also how you get from coefficients to an expression and round again:

/** Builds `c0 + c1*v + c2*v^2 + …` from dense coefficients, lowest degree first. */
def polynomial(coeffs: Vector[Double], v: _Variable): _Expression =
  val terms = coeffs.zipWithIndex.collect:
    case (c, 0)             => _Number(c)
    case (c, 1)             => Product(_Number(c), v)
    case (c, k)             => Product(_Number(c), Power(v, _Number(k)))
  if terms.isEmpty then _Number(0) else terms.reduce(Sum(_, _))

val p = polynomial(Vector(2, 3, 1), x)
// p: _Expression = Sum(
//   a = Sum(a = _Number(2.0), b = Product(a = _Number(3.0), b = _Variable("x"))),
//   b = Product(
//     a = _Number(1.0),
//     b = Power(base = _Variable("x"), exp = _Number(2.0))
//   )
// )

p.eval(Environment().withBinding("x", _Number(2)))
// res8: Either[_Expression, _Value] = Right(_Number(12.0))

Note what did not happen: no string was built, no parser ran, and nothing could fail. A generated expression has no error case, which is the whole reason to generate one.

One trap: a constant you invent has a tier

Leonardo has an exact-arithmetic tier, and an exact value combined with an ordinary Double becomes a Double — deliberately, so that representation error can never be laundered into an exact-looking answer. Which means a constant your code makes up can demote the expression it joins:

val exactThird = Parser.parse("1/3", exact = Some(30)).get

Sum(exactThird, _Number(1)).eval(Environment())
// res9: Either[_Expression, _Value] = Right(_Number(1.3333333333333333))
Sum(exactThird, _Rational.literalLike(1, exactThird)).eval(Environment())
// res10: Either[_Expression, _Value] = Right(4/3)

Same 1, two tiers. The rule is build the constant in the tier of the expression it is about to join, and _Rational.literalLike(n, like) is how: it reads like and gives you a matching 1. You only need it when your input might be exact — L7 is where the tiers are, and it is the subtlest thing a caller of this library has to know.

Try it yourself

Write fromRoots(roots: Vector[Double], v: _Variable): _Expression building (v - r₁)(v - r₂)…, and check it by evaluating at a root. Subtraction has no node of its own — a - b is Sum(a, Product(_Number(-1), b)), which is exactly how the parser reads it.

Answers ```scala def fromRoots(roots: Vector[Double], v: _Variable): _Expression = val factors = roots.map(r => Sum(v, _Number(-r))) if factors.isEmpty then _Number(1) else factors.reduce(Product(_, _)) ``` ```scala val q = fromRoots(Vector(1, -2), x) // q: _Expression = Product( // a = Sum(a = _Variable("x"), b = _Number(-1.0)), // b = Sum(a = _Variable("x"), b = _Number(2.0)) // ) ``` ```scala q.eval(Environment().withBinding("x", _Number(1))) // res11: Either[_Expression, _Value] = Right(_Number(0.0)) q.eval(Environment().withBinding("x", _Number(-2))) // res12: Either[_Expression, _Value] = Right(_Number(0.0)) q.eval(Environment().withBinding("x", _Number(0))) // res13: Either[_Expression, _Value] = Right(_Number(-2.0)) ``` Two zeros and a `-2`, which is the check. Folding `-r` into the number is neater than building `Product(_Number(-1), _Number(r))` and gives the same tree once anything simplifies it. Multiplying the factors out is `expand`'s job rather than yours, and it collects like terms as it goes — `2x` and `-x` arrive as one term: ```scala q.expand() // res14: _Expression = Sum( // a = Sum( // a = Power(base = _Variable("x"), exp = _Number(2.0)), // b = _Variable("x") // ), // b = _Number(-2.0) // ) ``` The terms keep the order they first appeared in. To read the result as a polynomial in **one** variable — ascending powers, every other name part of a coefficient — use `normalize`, which needs to be told which variable that is: ```scala q.expand().normalize(x) // res15: _Expression = Sum( // a = Sum(a = _Number(-2.0), b = _Variable("x")), // b = Power(base = _Variable("x"), exp = _Number(2.0)) // ) ```

What you learned

  • Build the node, do not build a string. The parser is for text you did not write; a generated expression cannot fail to parse because it never was text.
  • Sum, Product, Ratio, Power are binary, and printing is fully parenthesised so the output re-parses to the same tree — parse(e.toString) == e is your cheapest test.
  • A binder takes a _Variable, which the compiler enforces.
  • _Derivative(e, x) is the derivative as a tree; derive(e, x) computes it. Syntax makes the algorithms method calls; it does not give expressions arithmetic operators, and nothing does.
  • Generating from data is the point: a coefficient vector, a list of roots, a row per term.
  • expand multiplies out and collects like terms; normalize(v) orders the result as a polynomial in v.
  • A constant your algorithm invents carries a tier — use _Rational.literalLike when the input may be exact, or you will silently demote it.

Previous: L3 — Environment · Next: L5 — Traversal · All lessons

This site uses Just the Docs, a documentation theme for Jekyll.