What it does
A read-eval-print loop: type an expression, get a result. Variables can be bound and reused. Expressions that cannot be fully evaluated — because they contain unbound variables — are simplified as far as the algebra allows and printed back.
The twist is that it does this for two entirely different kinds of value. One calculator
works over integers, with the arithmetic you would expect. The other works over
multisets — collections where elements carry a multiplicity, so
{a, a, b} is distinct from {a, b} — with summation,
intersection and subtraction defined over those multiplicities.
From text to tree
Parsing runs in two stages. Input arrives in infix notation, which is convenient to type and inconvenient to evaluate, because precedence and associativity are implicit in it.
- The shunting-yard algorithm converts infix to Reverse Polish Notation, making precedence explicit in the ordering rather than implicit in the syntax.
- RPN is then consumed into a recursive parse tree, where each node is either a literal, a variable, or an operator with children.
Once the expression is a tree, everything downstream — evaluation, simplification, printing — is recursive descent over an immutable structure, which is exactly the shape functional code is good at.
One engine, two types
The obvious implementation is two calculators that duplicate their parsing and evaluation logic with different types substituted. The better one uses Scala's type abstraction so that a generic base handles the entire evaluation pipeline, and each concrete calculator only supplies what is genuinely specific to it — its value type and the meaning of its operators.
Integer addition and multiset summation are the same operation as far as the tree walker is concerned: combine two children of the same type into one. Only the combining function differs.
Simplification
The simplification engine is deep pattern matching over the tree, applying reduction rules — identity properties, distributivity, and so on — to collapse redundant structure.
The important detail is that it works bottom-up. Simplifying from the root down means an outer rule fires against children that have not been reduced yet, so redundancy nested a few levels deep survives. Reducing children first means every rule sees its subtrees in their simplest form, and nested redundancies like adding zero or multiplying by one are fully resolved in a single pass.
Printing it back
Output is a small problem in its own right. A parse tree printed naively brackets every operator, producing technically correct and completely unreadable output. The formatter tracks operator precedence and emits parentheses only where removing them would change the meaning — so a simplified expression comes back looking the way a person would write it.
Why it was worth doing
It is a compiler front end in miniature: tokenise, parse to a tree, transform the tree, render it back. Doing it in Scala with immutable structures makes every transformation a function from one tree to another rather than a mutation, which means intermediate states can be inspected, tested and compared directly.