Project 27: Symbolic Differentiation Engine

A self-contained deep-dive from the canonical Math from Foundations to Machine Learning curriculum.

  • Difficulty: Intermediate
  • Time: 2-3 weeks
  • Language: Python
  • Prerequisites: Projects 5 and 26
  • Source: ML-Math P08

What You Will Build

Build a small computer-algebra engine that tokenizes and parses expressions into an abstract syntax tree, differentiates the tree recursively, simplifies the result, prints it with correct precedence, and verifies it numerically. Support constants, variables, sums, products, quotients, integer powers, and common unary functions such as sine, cosine, exponential, and logarithm. Preserve a distinction between parsing, transformation, simplification, evaluation, and display so bugs can be localized. The engine must show an optional derivation trace naming each rule applied. Verification samples legal domain points and compares the symbolic derivative with Project 26’s central differences, turning symbolic manipulation into a testable software contract.

Real World Outcome

Entering sin(x*x) + x^3/log(x) returns a readable derivative, a tree/step trace, simplification before-and-after, and a verification table over valid positive x values. Malformed input and illegal domains produce deterministic parser or evaluator diagnostics rather than Python exceptions.

Core Question

How can differentiation rules be represented as local tree transformations that compose correctly for arbitrarily nested expressions?

Concepts You Must Understand First

  1. Expression trees: operators are internal nodes and literals/variables are leaves. See Abelson and Sussman, Structure and Interpretation of Computer Programs, symbolic-data sections.
  2. Grammar and precedence: parsing must distinguish unary minus, grouping, exponentiation, and function calls.
  3. Derivative rules: linearity, product, quotient, power, and chain rules. See Stewart, Calculus.
  4. Structural recursion: differentiate children and combine them according to node type.
  5. Safe simplification: identities like x+0=x are local; aggressive algebra can change domains or divide by zero.

Build Milestones

  1. Define immutable AST node types, a tokenizer, and a precedence-aware parser with round-trip tests.
  2. Implement evaluation with variable environments and clear domain errors.
  3. Add recursive derivative rules and a trace recording which rule produced each subtree.
  4. Implement conservative simplifications such as constant folding, neutral elements, and zero products.
  5. Numerically validate generated derivatives over seeded legal samples and report counterexamples.

Hints in Layers

  1. Begin with prefix-constructed ASTs before writing the parser; prove transformation logic independently.
  2. Treat each node as owning evaluate, differentiate, and format, or use exhaustive visitors.
  3. For verification, scale tolerance with function magnitude and reject samples too close to domain boundaries.

Common Pitfalls and Debugging

  • Symptom: -x^2 differentiates as 2x. Cause: unary-minus precedence was parsed incorrectly. Fix: add explicit grammar tests and print the AST.
  • Symptom: nested functions miss factors. Cause: chain rule omitted the inner derivative. Fix: test sin(x^2) and trace each recursive result.
  • Symptom: simplification changes valid domains. Cause: cancellation such as x/x -> 1 ignored x=0. Fix: keep simplification conservative or track assumptions.

Definition of Done

  • Parsing and pretty-printing preserve structure for a representative expression suite.
  • Every supported node differentiates recursively with a named rule trace.
  • Simplification reduces obvious clutter without unsafe cancellations.
  • Numerical checks agree at many seeded valid points within tolerance.
  • Syntax, unknown-function, and domain errors are deterministic.
  • The implementation does not delegate differentiation to SymPy or another CAS.

Previous: Project 26 · Complete learning path · Next: Project 28