L5 — Traversal

Goal: walk and rewrite an expression without knowing what is in it — which is how nearly every algorithm in this library is written, and how yours should be too.

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

// L1's reader once more: these inputs are ours, so a failure is a bug in the lesson.
def expr(text: String): _Expression =
  val parsed = Parser.parse(text)
  if parsed.successful then parsed.get
  else sys.error(s"lesson input failed to parse: $text")

Two methods, on every node

L4 built trees by naming nodes. Reading one back you usually cannot name them — the tree came from a parser, or from somewhere else in your program — so _Expression gives you a pair of methods that work on all of them:

def children: List[_Expression]
def rebuild(newChildren: List[_Expression]): _Expression

val e = expr("2*x + sin(y)")

e.children
// res0: List[_Expression] = List(
//   Product(a = _Number(2.0), b = _Variable("x")),
//   Sin(_Variable("y"))
// )

e.children.map(_.children)
// res1: List[List[_Expression]] = List(
//   List(_Number(2.0), _Variable("x")),
//   List(_Variable("y"))
// )

rebuild is the inverse: hand it a list the same length and you get the same shape back with new contents.

e.rebuild(List(_Number(1), _Number(2)))
// res2: _Expression = Sum(a = _Number(1.0), b = _Number(2.0))

Handing back exactly what you were given is therefore the identity, and that is worth knowing because a great deal rests on it:

e.rebuild(e.children) == e
// res3: Boolean = true

Why this exists

There are roughly 125 node types spread across twelve packages, and _Expression is not sealed — a domain can add nodes without core knowing. So a match over node types can never be exhaustive, cannot be checked, and silently stops covering the language the moment a package is added.

children / rebuild is the answer: an algorithm that does not care which node it is holding never has to ask. Write it once and it covers the matrices, the logic connectives, the transforms and everything added after you stopped looking.

A traversal is one line 

/** Every node of `e`, the node itself first. */
def nodes(e: _Expression): List[_Expression] = e :: e.children.flatMap(nodes)

nodes(e).size
// res4: Int = 6

nodes(e).map(_.toString)
// res5: List[String] = List(
//   "((2.0 * x) + sin(y))",
//   "(2.0 * x)",
//   "2.0",
//   "x",
//   "sin(y)",
//   "y"
// )

A rewrite is one more

Fold rebuild back in and you have a generic bottom-up rewriter — children first, then the node they belong to:

/** Rewrites every node, innermost first. */
def transform(e: _Expression)(f: _Expression => _Expression): _Expression =
  f(e.rebuild(e.children.map(transform(_)(f))))

transform(e) {
  case _Number(d) => _Number(d * 2)
  case other      => other
}
// res6: _Expression = Sum(
//   a = Product(a = _Number(4.0), b = _Variable("x")),
//   b = Sin(_Variable("y"))
// )

That is the same shape as rewriteOnce in the library’s own rule engine. Two notes on it. The case other => other arm is not optional — you are supplying a total function, and every node you do not care about has to come back unchanged. And case _Number(d) is a widening match that also catches an exact rational, handing you its value as a Double; harmless here, and L7 is where that matters.

Binders are not children

Now the fact that makes traversal safe, and the one that surprises people.

A binder — the variable of a derive, an integral, a limit, a sum — is deliberately left out of children:

val d = expr("derive(x^2, x)")

d.children
// res7: List[_Expression] = List(
//   Power(base = _Variable("x"), exp = _Number(2.0))
// )

One child: the body. The x that says with respect to is not in the list, and rebuild carries it through untouched. So a generic walk visits uses of a variable and never its declaration:

/** Renames every *occurrence* of a variable. */
def rename(e: _Expression, from: String, to: String): _Expression =
  transform(e) {
    case _Variable(`from`) => _Variable(to)
    case other             => other
  }

rename(d, "x", "u")
// res8: _Expression = _Derivative(
//   e = Power(base = _Variable("u"), exp = _Number(2.0)),
//   v = _Variable("x")
// )

The body was renamed and the binder was not. That is the contract, not a gap in it: a binder is a declaration, and renaming a declaration is a different operation from renaming the uses of one. If you genuinely need to rewrite a binder you have to name the node type and rebuild it by hand — the generic path will never do it for you, by design.

What that buys: substitution for free

Here is the library’s entire substitute, which replaces named definitions throughout an expression:

def substitute(e: _Expression, definitions: Map[String, _Expression]): _Expression =
  def loop(e: _Expression, seen: Set[String]): _Expression = e match
    case _Variable(n) if definitions.contains(n) && !seen.contains(n) =>
      loop(definitions(n), seen + n)
    case other =>
      other.rebuild(other.children.map(loop(_, seen)))

  loop(e, Set())

One case does the work and one case recurses. There is no binder handling anywhere in it, and it is nonetheless capture-safe:

substitute(expr("derive(f, x)"), Map("f" -> expr("x^2")))
// res9: _Expression = _Derivative(
//   e = Power(base = _Variable("x"), exp = _Number(2.0)),
//   v = _Variable("x")
// )

substitute(expr("derive(y, x)"), Map("x" -> expr("3")))
// res10: _Expression = _Derivative(e = _Variable("y"), v = _Variable("x"))

The second is the one to look at. A textual substitution would have produced derive(y, 3), which is not an expression anyone can mean. Here x occurs only in binder position, the walk never reaches it, and the answer is correctly unchanged — without a single line of code about it.

A structural walk through children cannot capture a variable, because it cannot see one.

Not every excluded field is a binder

Being absent from children only means “not a sub-expression to recurse into”. Several nodes exclude something else, and a definite integral is the instructive one — the variable is excluded, the limits are not:

expr("integral(x*y, y, 0, x)").children
// res11: List[_Expression] = List(
//   Product(a = _Variable("x"), b = _Variable("y")),
//   _Number(0.0),
//   _Variable("x")
// )

Three children: the integrand and both limits. Which is why an inner limit mentioning the outer variable is just an ordinary free occurrence, and iterated integration works without anyone having implemented it:

expr("integral(integral(x*y, y, 0, x), x, 0, 1)").eval(Environment())
// res12: Either[_Expression, _Value] = Right(_Number(0.12500000000000003))

(The last three digits are Simpson’s rule, not a traversal problem — the exact answer is 0.125, and L3 is where the step count comes from. What matters here is that nothing special was needed to make the inner limit see the outer variable.)

Other nodes keep an operator (_Comparison), a base (_Based), a direction (_Limit) out of children the same way. All of which is why rebuild is the right tool for comparing two nodes’ shape: it puts one node’s children into the other and checks everything else at the same time.

expr("derive(x^2, x)").rebuild(List(expr("x^2"))) == expr("derive(x^2, y)")
// res13: Boolean = false

Same node type, same children, different binder — and one == caught it. Comparing getClass would not have.

freeVars

The most-used traversal in the library is already written for you, and it is defined in exactly the terms above — the union of the children’s, cached:

expr("a*sin(b) + 1").freeVars
// res14: Set[String] = Set("a", "b")

It is a lazy val, so the first read walks the tree and every read after that is a set lookup. It is also inherited: a new node type gets a correct freeVars by defining children, with nothing else to remember.

Being defined from children has a consequence worth being precise about. freeVars reports the names that occur in the tree, not the names the value mathematically depends on, and binders being excluded pushes it both ways:

expr("integral(x, x, 0, 1)").freeVars
// res15: Set[String] = Set("x")

expr("integral(1, x)").freeVars
// res16: Set[String] = Set()

The first is a definite integral whose value does not depend on x at all, and x is reported because it occurs in the integrand. The second mentions x only as a binder, so it is not reported at all. Both follow from the one rule.

For what freeVars is actually asked — may I pull this factor out?, which names must a fresh variable avoid? — over-reporting is the safe direction, so this is the conservative answer rather than a rough one. (The library’s own fresh-name generator adds the binder to the set by hand, precisely because of the second case.)

dependsOn

The question you usually want, one line over the cache:

dependsOn(expr("x^2 + y"), _Variable("y"))
// res17: Boolean = true

dependsOn(expr("x^2 + y"), _Variable("z"))
// res18: Boolean = false

It looks trivial and is load-bearing. The non-linear u-substitution integrator works by forming integrand / g' for each candidate inner function g and asking whether the result is free of the integration variable — the whole tier rests on that question being decidable and cheap, which is what turns an open-ended search into a check. When you write your own rules, reach for the same shape.

Try it yourself

Write occurrences(e: _Expression, name: String): Int — how many times a variable actually appears. freeVars answers whether, never how many.

Answers ```scala def occurrences(e: _Expression, name: String): Int = nodes(e).count: case _Variable(n) => n == name case _ => false ``` ```scala occurrences(expr("x*sin(x) + x^2 + y"), "x") // res19: Int = 3 ``` ```scala occurrences(expr("x*sin(x) + x^2 + y"), "z") // res20: Int = 0 ``` Reusing `nodes` is the point: having written the walk once, a counter is a `count` over it. Two things to notice. This re-walks the tree on every call where `freeVars` is cached, so if the question is only yes-or-no, `dependsOn` is both clearer and cheaper. And the binder rule still applies: ```scala occurrences(expr("derive(x^2, x)"), "x") // res21: Int = 1 ``` One, not two — the `x` in binder position is not a child, so nothing counts it. If that is the answer you wanted, you got it for free; if it is not, you now know that you have to match the node type.

What you learned

  • children and rebuild are the whole traversal API, and they exist because _Expression is not sealed: a match over ~125 node types in twelve packages can never be exhaustive, and a generic walk covers domains added after you wrote it.
  • e.rebuild(e.children) == e is the identity; a walk is e :: e.children.flatMap(...) and a rewriter is f(e.rebuild(e.children.map(...))).
  • A binder is not a child. A generic walk sees uses and never declarations, which is why substitute is six lines and capture-safe with no code about binders at all. Rewriting a binder means naming the node type.
  • Excluded ≠ binder: a definite integral’s limits are children while its variable is not, and that asymmetry is what makes iterated integrals with variable limits work.
  • Because rebuild carries every non-child field through, p.rebuild(e.children) == e checks the node type and the binder, operator or base in one comparison.
  • freeVars is occurrence, not dependence — cached, inherited from children, and conservative in the safe direction. dependsOn is the one-line question over it, and its being decidable is what several integration tiers are built on.

Previous: L4 — Building trees without the parser · Next: L6 — The calculus API · All lessons

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