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

For the Advanced Programming module at UEA we built a mathematics interpreter in F#, from scratch. You give it a string like d/dx(sin(x^2) + 3/4) and it parses that into a tree, differentiates the tree symbolically, simplifies what comes back, and plots it on a graph you can pan around.

This post is about the decisions that shaped it, and about how much of what the system ended up doing follows from one choice we made at the start.

The Pipeline

Every interpreter has roughly the same shape. Raw text in, structured meaning 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, and the evaluator walks the tree and computes a result. Each stage knows nothing about the others.

What makes this more than a calculator is the feedback arrows at the bottom. The AST doesn't have to travel to the evaluator and stop there. It can be transformed by the differentiator into a new AST, or handed to the plotter and re-evaluated hundreds of times at different x-values. That reuse turned out to be the most important property of the architecture, and it isn't the one we started with.

What the Parser Returns

The stub we were given combined parsing and evaluation into a single pass. The parser would see 3 + 4 and, rather than build a tree node, compute 7 on the spot. That works for simple arithmetic and it caps everything above it. You can't differentiate a number and you can't plot 7. What the rest of the system needs is the structure of the expression, which the single pass throws away at exactly the moment it has it.

So our first real decision was to separate the two 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

That's a discriminated union in F#, a type that says an expression is one of these seven things. A BinaryOp holds an operator and two sub-expressions, which are themselves Expr values, so it's trees all the way down.

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

Operator precedence is baked into the shape. Multiplication binds tighter than addition, so Mul sits lower. Walk the tree depth-first and you compute 3 * x before adding 2. The mathematics lives in the structure. Nothing downstream has to reconstruct it.

Everything else in the project depends on this. Symbolic differentiation is a transformation from one AST into another. Integration evaluates the same AST at hundreds of points. The GUI keeps the AST around and re-evaluates it whenever the user pans or zooms the graph. The general form of the principle is to keep what something means separate from what you do with it. Domain models in backend systems are the same idea.

Two-Phase Lexing

The lexer has one awkward problem. Is - subtraction or negation?

In 3 - 5 it's subtraction. In 3 * -5 and in (-5) it's negation. The character is identical and the meaning depends entirely on what came before it, so we handled it in two passes.

The first pass tokenises naively and every - becomes a Sub token. The second pass walks the token stream and reclassifies: a Sub becomes a UnaryMinus if it appears at the start of the input, after an opening parenthesis, after an operator, or after an assignment. Splitting it this way means the first pass never has to track state and the second never has to think about characters.

The same two-pass idea handles rational numbers. When the lexer sees 3/4 it has to decide whether that's the rational three-quarters or an integer division, and the rule we settled on is to treat / as a rational separator only when the accumulator has no decimal point and the denominator is a valid integer. 3/4 becomes Rational(3, 4). 3.0/4 becomes Float(3.0) Div Int(4), because the decimal point has already given up the exactness a rational is there to preserve.

Parsing: Getting Precedence Right

The parser uses recursive descent with precedence climbing. Each precedence level gets its own function, and the lower-precedence functions call the higher-precedence ones:

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

parseExpression calls parseTerm for its operands, which calls parseFactor, which calls parsePrimary. The correct tree shape falls out of the call order. 2 + 3 * 4 parses as Add(2, Mul(3, 4)), because parseTerm has already claimed the multiplication by the time parseExpression gets to look at the 3.

Exponentiation is the one place the pattern breaks. Most operators are left-associative, so 2 - 3 - 4 means (2 - 3) - 4, but exponentiation associates rightward and 2^3^2 has to evaluate as 2^(3^2) = 512 rather than (2^3)^2 = 64. Both readings produce a plausible-looking number, which is why that class of bug survives casual testing and shows up in production.

The fix is one line, 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 and build the tree leftward. Right-associative operators recurse on the base function and build it rightward.

Evaluation and the Symbol Table

Once the parser hands over an AST, the evaluator walks it depth-first. The interesting question there is state.

Mathematical expressions live in a context. After x = 5, the expression x + 3 should evaluate to 8, and that context is the symbol table, a map from variable names to values. The mutable approach stores the table as a shared object that the evaluator reads and writes. It works, but it makes evaluation order matter in ways that are hard to see from the call site, and it makes tests harder to isolate. We used F#'s immutable maps instead, so the evaluator takes a symbol table in and returns 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

Evaluating an expression leaves the table alone. An assignment returns a new table with the binding added, and the old table still exists, unchanged. That's what lets the plotter evaluate y = x^2 against hundreds of different symbol tables, one per x-value, with no interference between them. Threading state through as (input, state) -> (output, newState) is the same shape you find in Redux reducers, event sourcing and database transactions.

Six Number Types

The interpreter supports integers, floats, rationals, complex numbers, vectors and matrices, each 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 an integer meets a rational, or a float meets a complex number. We implemented automatic type promotion, where the less general type promotes to the more general one when the two meet in an operation.

The rules preserve precision wherever there's still precision to preserve. Int + Rational stays Rational, since both are exact. Float + Rational converts the rational to a float, because the float has already lost exactness and there's nothing left to protect. Anything + Complex promotes to complex. So 5 + 1/2 produces Rational(11, 2) and not Float(5.5).

Rationals simplify themselves 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)

A rational with denominator 1 collapses back to an integer, so 6/3 evaluates to Int(2) rather than Rational(2, 1), and the system always settles on the most specific type that can represent the result.

At 908 lines it's the largest module in the project, and most of that is the combinatorial expansion of every operation across every pair of types. Unglamorous code. The edge cases buried in it (division by zero in rationals, negative denominators, complex division by conjugate) are most of what makes the rest of the system trustworthy.

Symbolic Differentiation

This is the part of the project I'm most pleased with.

computeDerivative takes an AST and a variable name and returns a new AST representing the derivative. The rules you learn in calculus are implemented 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, and 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)

Between them these cover 11 mathematical functions, the product rule, the quotient rule, the power rule with both constant and variable exponents, and the chain rule composing all of it. The output is an AST throughout, never a number.

Raw symbolic derivatives are ugly, though. Put x^2 through the power rule and you get 2 * (x^(2-1) * 1), technically correct and not something any human would write. So there's 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, which turns 2 * (x^(2-1) * 1) into 2 * x. The simplifier folds constants too. 3 + 4 becomes 7, and nested multiplications flatten, so 2 * (3 * x) becomes 6 * x.

None of this works without the AST decision from earlier, because differentiation is tree transformation and a parser that evaluated as it went would have left nothing to transform.

Root Finding: Newton-Raphson

The interpreter finds roots with Newton-Raphson. Start with a guess, evaluate the function and its derivative at that point, then step in the direction the derivative suggests.

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

Convergence is quadratic, so each iteration typically doubles the number of correct digits. Our implementation runs up to 500 iterations per starting point with a tolerance of 1e-10.

The awkward part is that a single starting point might find only one root, or converge to the wrong one, or diverge entirely. Our answer is unsubtle: generate 1000 evenly spaced initial guesses across the search interval, run Newton-Raphson from every one of them, discard the failures and de-duplicate what's left. Brute force in the search space, precise once it converges.

This reuses the symbolic differentiation. The derivative Newton-Raphson needs is computed from the AST rather than approximated numerically, so convergence is exact to the precision of floating-point arithmetic instead of being limited by the size of a finite-difference step.

The GUI

The WPF GUI is where the architecture becomes tangible. A user types y = sin(x), hits Plot, and the curve appears. They click Derivative and the orange cos(x) overlay draws on top. They type bounds and the integral shades 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 read again. The plot evaluates it at hundreds of x-values, the derivative button calls computeDerivative on it and plots the AST that comes back, the integral evaluates it at the trapezoidal quadrature points, and the root finder passes it and its symbolic derivative to Newton-Raphson.

Deferred evaluation is what makes that feel smooth. 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's no error and no prompt for a value. The expression waits until something supplies a context, either the Plot button handing it hundreds of x-values or a later definition of x.

Panning and zooming re-evaluate across the new viewport bounds. That's fast enough to feel instantaneous because the AST is a lightweight data structure rather than a closure or a string that has to be re-parsed, so the user is manipulating the tree directly without knowing it.

Separating parsing from evaluation is what turned a calculator into a computer algebra system. Symbolic differentiation, the integration visualisation, root finding and interactive plotting were all out of reach while the parser was collapsing expressions into values, and all of them were straightforward once it stopped. The abstractions you choose early decide what's easy later and what's impossible. You generally have to choose them before you know which is which.

The interpreter came to about 4,700 lines of code across F# and C#, and the most important line in it is probably type Expr =.