Building a Mathematics Interpreter in F#: From Parser to Symbolic Calculus

Most university programming projects are CRUD apps or data pipelines. This one was a compiler.

For the Advanced Programming module at UEA, we built a mathematics interpreter from scratch in F#: a system that takes a string like d/dx(sin(x^2) + 3/4), parses it into a tree, differentiates it symbolically, simplifies the result, and plots it on an interactive graph.

This post walks through the decisions that shaped the interpreter, what made them interesting, and what I learned about building systems that are designed to grow.

The Pipeline

Every interpreter follows roughly the same shape. Raw text goes in, structured meaning comes out. Ours has four stages:

The lexer breaks the input into tokens. The parser arranges those tokens into a tree that represents the mathematical structure. The evaluator walks the tree and computes a result. Each stage knows nothing about the others.

The feedback arrows at the bottom are what make this more than a calculator. The AST can be fed back into the pipeline: transformed by the differentiator into a new AST, or re-evaluated hundreds of times by the plotter at different x-values. That reuse is the most important property of the architecture, and it was not the one we started with.

The Decision That Changed Everything

The original stub we were given combined parsing and evaluation into a single pass. The parser would see 3 + 4, and instead of building a tree node, it would immediately compute 7. This works for simple arithmetic, but it creates a ceiling. You cannot differentiate a number. You cannot plot 7. You need the structure of the expression, not just its result.

Our first major decision was to separate these concerns completely. The parser returns an abstract syntax tree:

type Expr =
    | Number of NumberType
    | Variable of string
    | BinaryOp of BinaryOperator * Expr * Expr
    | UnaryOp of UnaryOperator * Expr
    | FunctionCall of string * Expr
    | VectorLiteral of Expr list
    | MatrixLiteral of Expr list list

This is a discriminated union in F#, essentially a type that says "an expression is one of these seven things." A BinaryOp contains an operator and two sub-expressions, which are themselves Expr values. It is trees all the way down.

Here is what the tree looks like for 2 + 3 * x:

The parser respects operator precedence. Multiplication binds tighter than addition, so Mul sits lower in the tree. When the evaluator walks this tree depth-first, it naturally evaluates 3 * x before adding 2. The structure encodes the mathematics.

This separation unlocked everything that followed. Symbolic differentiation works by transforming one AST into another. Integration evaluates the same AST at hundreds of points. The GUI stores the AST and re-evaluates it whenever the user pans or zooms the graph. None of that is possible if you throw away the structure during parsing.

The principle generalises: separate what something means from what you do with it. Parse once, use many times. It is the same idea behind domain models in backend systems, and it shows up everywhere once you start looking.

Two-Phase Lexing

The lexer has a subtle problem to solve: is - subtraction or negation?

In 3 - 5, it is subtraction. In 3 * -5, it is negation. In (-5), it is negation. The character is identical but the meaning depends on context. Our lexer handles this with a two-phase approach:

Phase 1 tokenises everything naively. Every - becomes a Sub token.

Phase 2 walks the token stream and applies a context rule: if a Sub token appears at the start of the input, after an opening parenthesis, after an operator, or after an assignment, it gets reclassified as UnaryMinus.

This is cleaner than trying to handle it inline during scanning. Phase 1 does not need to track state. Phase 2 does not need to understand character-level parsing. Each phase has a single concern.

The same pattern applies to rational numbers. When the lexer sees 3/4, it needs to decide: is this the rational number three-quarters, or is it integer division? The rule: only treat / as a rational separator if the accumulator has no decimal point and the denominator is a valid integer. So 3/4 becomes Rational(3, 4), but 3.0/4 becomes Float(3.0) Div Int(4).

Parsing: Getting Precedence Right

The parser uses recursive descent with precedence climbing. Each precedence level gets its own function:

parseExpression  ->  handles + and -    (lowest precedence)
parseTerm        ->  handles * / %      (medium)
parseFactor      ->  handles ^          (highest binary)
parsePrimary     ->  handles atoms      (numbers, variables, functions, parens)

Lower-precedence functions call higher-precedence ones. parseExpression calls parseTerm for its operands, which calls parseFactor, which calls parsePrimary.

This naturally produces the correct tree shape. The input 2 + 3 * 4 parses as Add(2, Mul(3, 4)) because parseTerm grabs the multiplication before parseExpression can claim the 3.

There is one place where this pattern breaks: exponentiation.

Most operators are left-associative. 2 - 3 - 4 means (2 - 3) - 4. But exponentiation is right-associative. 2^3^2 must be 2^(3^2) = 512, not (2^3)^2 = 64. The difference between 512 and 64 is the kind of bug that passes casual testing and fails in production.

The fix is a one-line change in how the parser recurses:

| Pow :: tail ->
    let tokens', rightExpr = parseFactor tail   // recurse on parseFactor, not parseFactorRest
    (tokens', BinaryOp(Exponentiation, leftExpr, rightExpr))

Left-associative operators recurse on their own "rest" function, building the tree leftward. Right-associative operators recurse on the base function, building rightward. It is a small difference in code and a large difference in correctness.

Evaluation and the Symbol Table

Once the parser produces an AST, the evaluator walks it depth-first. The interesting part is how it handles state.

Mathematical expressions live in a context. After x = 5, the expression x + 3 should evaluate to 8. That context is the symbol table: a map from variable names to values. The question is how to manage it.

A mutable approach would store the symbol table as a shared object that the evaluator reads and writes. That works, but it makes the evaluation order matter in subtle ways and makes testing harder. Instead, we used F#'s immutable maps. The evaluator takes a symbol table in and returns a new one out:

let evaluateStatement (statement: Statement) (symbolTable: SymbolTable)
    : NumberType * SymbolTable =
    match statement with
    | ExpressionStmt expr ->
        let value = evaluateExpr expr symbolTable
        (value, symbolTable)                          // table unchanged
    | Assignment(varName, expr) ->
        let value = evaluateExpr expr symbolTable
        let newTable = Map.add varName value symbolTable
        (value, newTable)                             // new table returned

An expression evaluation never changes the table. An assignment returns a new table with the binding added. The old table still exists, unchanged. This means you can evaluate the same AST against different symbol tables without interference, which is exactly what the plotter does when it evaluates y = x^2 at hundreds of different x-values.

The functional threading pattern, taking state in and returning new state out, shows up constantly in well-designed systems. It is the same idea behind Redux reducers, event sourcing, and database transactions. The shape is always the same: (input, state) -> (output, newState).

Six Number Types

The interpreter supports integers, floats, rationals, complex numbers, vectors, and matrices. Each is a case in a single discriminated union:

type NumberType =
    | Int of int
    | Float of float
    | Rational of int * int
    | CustomComplex of float * float
    | Vector of float list
    | Matrix of float list list

The interesting problem is what happens when you add an integer to a rational, or multiply a float by a complex number. We implemented automatic type promotion: when two different types meet in an operation, the less general type promotes to the more general one.

The promotion rules preserve precision where possible. Int + Rational stays Rational (exact arithmetic). Float + Rational converts the rational to a float (because the float already lost exactness). Anything + Complex promotes to complex. This means 5 + 1/2 produces Rational(11, 2), not Float(5.5).

Rationals auto-simplify through GCD:

let simplifyRational (num: int) (den: int) : int * int =
    let g = gcd num den
    let newNum = num / g
    let newDen = den / g
    if newDen < 0 then (-newNum, -newDen) else (newNum, newDen)

And a rational with denominator 1 collapses back to an integer: 6/3 evaluates to Int(2), not Rational(2, 1). The system always finds the most specific type that can represent the result.

This module is the largest in the project at 908 lines, and most of that is the combinatorial expansion of operations across type pairs. It is unglamorous code. But getting the edge cases right (division by zero in rationals, negative denominators, complex division by conjugate) is what makes the system trustworthy.

Symbolic Differentiation

This is the part of the project I am most proud of.

The computeDerivative function takes an AST and a variable name, and returns a new AST representing the derivative. It implements the rules you learn in calculus, but as recursive tree transformations:

Constant rule: The derivative of a number is zero.

| Number _ -> Number(Int 0)

Variable rule: The derivative of x with respect to x is 1. Any other variable is treated as a constant.

| Variable name when name = varName -> Number(Int 1)
| Variable _ -> Number(Int 0)

Product rule: d/dx[f * g] = f' * g + f * g'

| BinaryOp(Multiplication, left, right) ->
    BinaryOp(Addition,
        BinaryOp(Multiplication, computeDerivative left varName, right),
        BinaryOp(Multiplication, left, computeDerivative right varName))

Chain rule: d/dx[f(g(x))] = f'(g(x)) * g'(x)

| FunctionCall(funcName, argExpr) ->
    let innerDerivative = computeDerivative argExpr varName
    let outerDerivative = match funcName.ToLower() with
        | "sin" -> FunctionCall("cos", argExpr)
        | "cos" -> UnaryOp(Negation, FunctionCall("sin", argExpr))
        | "exp" -> FunctionCall("exp", argExpr)
        | "ln"  -> BinaryOp(Division, Number(Int 1), argExpr)
        ...
    BinaryOp(Multiplication, outerDerivative, innerDerivative)

The function handles 11 mathematical functions, the product rule, quotient rule, power rule (both constant and variable exponents), and composes them through the chain rule. It is entirely symbolic: the output is an AST, not a number.

But raw symbolic derivatives are ugly. The derivative of x^2 through the power rule produces 2 * (x^(2-1) * 1). Technically correct, but no human would write that. So there is a simplification pass:

| BinaryOp(Multiplication, Number(Int 1), right) -> simplifyExpr right
| BinaryOp(Addition, Number(Int 0), right) -> simplifyExpr right
| BinaryOp(Exponentiation, base_, Number(Int 1)) -> simplifyExpr base_
| BinaryOp(Exponentiation, _, Number(Int 0)) -> Number(Int 1)

These rules apply recursively until the expression stops changing. After simplification, 2 * (x^(2-1) * 1) becomes 2 * x. The simplifier also folds constants (3 + 4 becomes 7) and flattens nested multiplications (2 * (3 * x) becomes 6 * x).

What makes this architecturally interesting is that none of it would work without the AST decision from earlier. Differentiation is tree transformation. If the parser had evaluated expressions immediately, there would be no tree to transform.

Root Finding: Newton-Raphson

The interpreter finds roots of functions using the Newton-Raphson method. The algorithm is elegant: start with a guess, evaluate the function and its derivative at that point, and step in the direction the derivative suggests.

x_next = x_current - f(x_current) / f'(x_current)

Each iteration typically doubles the number of correct digits (quadratic convergence). Our implementation runs up to 500 iterations per starting point with a tolerance of 1e-10.

The trick is that a single starting point might only find one root, or converge to the wrong one, or diverge entirely. Our solution: generate 1000 evenly-spaced initial guesses across the search interval, run Newton-Raphson from each one, discard failures, and de-duplicate the results. It is brute-force in the search space but precise in the convergence.

This approach reuses the symbolic differentiation. The derivative needed by Newton-Raphson is computed from the AST, not approximated numerically. That means the convergence is exact to the precision of floating-point arithmetic, not limited by a finite-difference step size.

The GUI: Making Mathematics Interactive

The WPF GUI is where the architecture becomes tangible. A user types y = sin(x), hits Plot, and sees the curve appear. They click Derivative and the orange cos(x) overlay draws on top. They type bounds and see the integral shade blue beneath the curve. They click Find Roots and markers appear at the zeros.

Behind every one of those interactions is the same AST being reused. The plot evaluates it at hundreds of x-values. The derivative button calls computeDerivative on it, producing a new AST that gets plotted the same way. The integral evaluates it at the trapezoidal quadrature points. The root finder passes it (and its symbolic derivative) to Newton-Raphson.

One decision that made this work smoothly is deferred evaluation. When the user types y = x^2 + 3, the interpreter detects that x is a free variable and stores the AST without evaluating it. There is no error, no prompt for a value. The expression waits until the user gives it a context, either by clicking Plot (which supplies hundreds of x-values) or by defining x later.

The plotting itself re-evaluates on interaction. When the user pans or zooms, the graph recalculates across the new viewport bounds. Because the AST is a lightweight data structure (not a closure, not a string to re-parse), this is fast enough to feel instantaneous. The user is directly manipulating the tree without knowing it.

The Takeaway

The single decision to separate parsing from evaluation turned a calculator into a computer algebra system. Every feature that followed, symbolic differentiation, integration visualisation, root finding, interactive plotting, was only possible because the parser preserved the structure of the input instead of collapsing it into a value.

That is the lesson I keep coming back to in software engineering: the abstractions you choose early determine what is easy and what is impossible later. Get the data model right and features fall out naturally. Get it wrong and every feature is a fight against your own architecture.

The interpreter is about 4,700 lines of code across F# and C#. The most important line is probably type Expr =. Everything else follows from that.