Introducing Symbolic Algebra

This article is intended to give a quick overview to symbolic algebra in F#. I didn't come up with this stuff myself -- it's covered in SICP, Expert F#, and a lot of other places. However, I think it's such an important and useful topic that I wanted to post a quick overview and remark on why it matters.

Arithmetic vs. algebra in code

It's easy to do arithmetic in most high-level programming languages, including F#. By that, I first mean you can readily use F# as a calculator. For instance, in F# interactive you can run:

> 7 * (2 + 13);;
val it : int = 105

A high-level programming language like F# is better than most calculators because you can also name and save intermediate values in a computation:

let x = 2
let y = 13
7 * (x + y) // also returns 105

and you can also define functions to make computations repeatable:

let f x y =
    7 * (x + y)

f 2 13  // returns 7 * (2 + 13) = 105
f 1 1   // returns 7 * (1 + 1) = 14

You might think of some of this as algebra, rather than arithmetic, because symbols like x and y are getting involved, and being treated like numbers. I still call this arithmetic, because all that's going on here is carrying out a computation -- the letters are just placeholders.

By contrast, here's an honest-to-goodness algebra problem. Suppose I have another F# function g defined like this:

let g x y =
    7 * x + 7 * y

The question is, are the functions f and g equivalent? That is, does f x y = g x y for every possible pair of x and y you could pick? If so, their behavior as functions is indistinguishable and we say they are equal.

We can't check every single possible pair of integers x and y to verify that f x y and g x y produce identical outputs. The mathematical way to get around this is to look at the structure of f and g and see if they are equivalent. They are defined by the respective expressions $7(x+y)$ and $7x + 7y$, so we're really asking to confirm the fact: $$7(x+y) = 7x + 7y.$$ That's the real algebraic question. It turns out this is true, by invocation of one algebraic rule called the "distributive property". Out of the box, F# is not equipped to answer this question; it can't handle a comparison of two functions like f = g. (I don't blame F# -- it turns out the question of whether two expressions are equal is undecidable. That is, for algebraic expressions built out of just a few of the usual operations, there's no algorithm that can always detect equivalence.)

The good news is that F# makes it easy to encode a key algebraic idea, namely that expressions like $7(x+y)$ or $7x+7y$ are collections of symbols combined in particular structures. Once these structures are programmed into F#, they can be analyzed and manipulated.

Representing symbolic expressions

The key concept at play here is that of an algebraic expression. An algebraic expression isn't a computation, rather its a collection of symbols combined by some allowable operations. For instance, when I write "$2 + x$" is an expression that represents combining the symbols "2" and "$x$" via the operation of addition. You know how to interpret this as a computation, but resist the temptation to do so for now.

To give an unfamiliar example, "$(u \wedge v) \otimes w$" could represent an algebraic expression which first combines the symbols "$u$" and "$v$" using the "$\wedge$" operation and then combines that whole expression with another symbol "$w$" using the "$\otimes$" operation. Whether or not this can be interpreted as a computation, you can still see it has a structure.

Let's work in a familiar algebraic world where the symbols we combine are either integers or letters, and the operations that can combine them are addition, subtraction, negation, and multiplication. In this world, individual symbols like "17" or "$x$" are valid expressions, as are any combinations of these using the allowed operations. For instance, "$17 + x$" is a valid combination of $17$ and $x$ using the addition operation. You can build a bigger expression like "$y\cdot(17+x)$" by combining it with the single-symbol expression "$y$" using the operation of multiplication.

Now the task is to translate this idea to F#. We want to think of an integer like 17 and a string like "x" on the same footing, as two distinct but fungible cases of algebraic expressions. To do that, we can make our Expression type a discriminated union, having a case for numbers and variables.

type Expression = 
| Number of int
| Variable of string

With this definition, we could write down F# values like Number(17) or Variable("x"), which have more meaning than the int value 17 or the string value "x" alone. The values Number(17) and Variable("x") have type Expression, indicating that we're thinking of them as algebraic expressions, not just as an int and a string.

Numbers and variables are the simplest cases, but we also want to be able to combine them with operations to represent more complex expressions. Any two values of the Expression type should be combinable as a sum, difference, or product. While expressions like "$x+17$", "$x-17$", and "$x\cdot 17$" combine "$x$" and "17" in different ways, we want to think of all of them as the same kind of data. That suggests we should add them as extra cases to our discriminated union. (Likewise for negation, which makes e.g. $-x$ from $x$.)

type Expression =
| Number of int
| Variable of string
| Negation of Expression
| Sum of Expression * Expression
| Difference of Expression * Expression
| Product of Expression * Expression

Returning to the examples from above,

Product (Number 7,Sum (Variable "x",Variable "y"))

represents the expression $7(x+y)$ while

Sum (Product (Number 7,Variable "x"),Product (Number 7,Variable "y"))

represents the expression $7x + 7y$. You can see that the first one is a product of 7 with a sum, while the second one is the sum of two products.

The important accomplishment here is replacing a computation with a data structure that models the computation. When we thought of $7(x+y)$ as a computation, all we could do was plug in numbers for $x$ and $y$. Now that we're thinking of it more abstractly, as an expression, there are many more possibilities.

Evaluating an expression

First I want to show you that an Expression is at least as good as the corresponding F# function. Namely, you can take an Expression object, plug in numbers for the variables, and get a number as a result.

To demonstrate this, I'll use a slightly simplified version of the Expression type, where there's only one variable: $x$. That means I can replace the Variable case with a case X -- no need to let any string be a variable.

type Expression =
| Number of int
| X
| Negation of Expression
| Sum of Expression * Expression
| Difference of Expression * Expression
| Product of Expression * Expression

// for example...
Product (Number 3, Sum (X, Number 5)) // represents 3*(x+5)

What we'll do first is write a function that takes an expression as well as a given float value to "plug-in" for $x$, does the arithmetic, and returns the float result. For instance, if our expression represents $3(x+5)$ and we plug in 2.0 for $x$, we should get 21.0 back. With only one variable, this function will have a simple signature:

val evaluate : Expression -> float -> float

Once you've built a recursive data structure with an F# discriminated union, the rest of the work feels like magic. This is because you can reduce an infinite set of data (like every possible Expression you could think of) to a handful of cases, some of which are dead simple.

For instance, if you plug any number in to the expression X, you'll get that number back. That is, evalute X 5.0 should return 5.0. The other simple case is if your expression is just a number, like Number(17). It doesn't matter what value $x$ has, this expression always evaluates to 17. The only work to do for us is interpreting this 17 as a float, since that's the return type for our function.

That handles two of our six cases for the evaluate function:

let evaluate (exp:Expression) (input:float)  =
    match exp with
    | X -> input            // return the "plugged-in" value
    | Number i -> float i   // return number as a float
    | ...                   // to be determined

The other cases are combinations of existing expressions. For each of these, we have to evaluate the underlying expressions and then put the resulting float values together using the right operation. For instance $$(3+x)\cdot(2+2)$$ is the product of two expressions. If we're evaluating this product with $x=7$, the first step is to evaluate both expressions in the product. The first one, $3+x$, evaluates to 10.0 and the second one, with no appearance of $x$, evaluates to 4.0. Assuming we know both of these results, the answer is 10.0 * 4.0 or 40.0. That's just ordinary float multiplication in F#.

In short, we handle the rest of the union cases by evaluating (recursively!) the expressions that make them up and then doing the appropriate float arithmetic on the results.

let rec evaluate (exp:Expression) (input:float)  =
    match exp with
    | X -> input
    | Number i -> float i
    | Negation e -> - evaluate e input
    | Sum (e1, e2) -> (evaluate e1 input) + (evaluate e2 input)
    | Difference (e1, e2) -> (evaluate e1 input) - (evaluate e2 input)
    | Product (e1, e2) -> (evaluate e1 input) * (evaluate e2 input)

One line per case, that's all there is to it! This program treats the Expression as a set of instructions and executes them.

Operator overloading

I'll cover more things you can do with the Expression type shortly. First, let me show you some syntactic sugar that makes it much nicer to work with symbolic expressions in F#.

As you may know, F# allows operator overloading, which allows you to use arithmetic operators on types you define. That's great for symbolic programming, because it will let us write something like - X * (X + X) in place of the longer and harder to read Negative(Product(X,Sum(X,X))).

For each operator we want to use with the Expression type, we need to add a static member function to the class. The implementations match the operators to the corresponding union cases.

type Expression =
    | X
    | Number of int
    | Negation of Expression
    | Sum of Expression * Expression
    | Difference of Expression * Expression
    | Product of Expression * Expression
        static member (+) (e1,e2) = Sum(e1,e2)
        static member (*) (e1,e2) = Product(e1,e2)
        static member (-) (e1,e2) = Difference(e1,e2)
        static member (~-) (e) = Negation e

let inline (~&) (i:int) = Number(i)

It's a matter of personal preference, but I also included a unary operator "&" at the global level to package integers as Number objects. That allows me to write &3 + X rather than Number(3) + X. I chose the ampersand because its an operator I'm not likely to miss, and it outranks all of the arithmetic operators in F#'s order of operations. That means integers get interpreted as Number objects first in a line of code.

Operator overloading may not seem like a big deal, since it doesn't give us any functionality we didn't already have. However, it makes a big difference for productivity if you're working on an ambitious symbolic programming project. When you're debating between F# or Mathematica, it's nice that syntax doesn't have to be the deciding factor.

Translating an expression

If you know a bit about programming languages, you may recognize the Expression objects as abstract syntax trees for algebraic expressions. They are trees because an expression can be a combination of two sub-expressions, which can each in turn contain sub-expressions, and so on. If you draw out the nested structure of an expression, you see the characteristic branching. Here's $3\cdot(x+2)$ drawn as a tree:

Once you've got an abstract syntax tree, it's relatively easy to generate code in another programming language. For instance, you can generate a string of F# code corresponding to an expression. The way to do this is to traverse the tree, generate code for each sub-expression, and then concatenate the code snippets together.

let rec fsharp (exp:Expression) = 
    match exp with
    | X -> "x"
    | Number i -> string i
    | Negation e -> sprintf "-(%s)" (fsharp e)
    | Sum (e1, e2) -> sprintf "(%s)+(%s)" (fsharp e1) (fsharp e2)
    | Difference (e1, e2) -> sprintf "(%s)-(%s)" (fsharp e1) (fsharp e2)
    | Product (e1, e2) -> sprintf "(%s)*(%s)" (fsharp e1) (fsharp e2)

For an expression like &3 * (X + &2), the fsharp function produces the string "(3)*((x)+(2))". There are some superfluous parentheses, but otherwise this looks good. It represents the analogous computation in F#.

As a more practical example, you can generate LaTeX code from an Expression object. If you're not familiar with LaTeX, it's a markup language for typesetting math (among other things). You can look at my source code and see the implementation of a latex function that generates LaTeX code. The result of latex <| &3 * (X + &2) is the LaTeX code string:

" 3  \cdot  \left(  x  +  2  \right)"

Which renders like this: $$ 3 \cdot \left( x + 2 \right)$$ If you look at the source code, you'll see I added some logic to avoid unnecessary parentheses. This example doesn't do LaTeX justice, but if you expand the Expression type (Greek letter variables, quotients, named functions, roots, powers) you can get some spectacular results. In this file you can see an enhanced Expression type and latex function that turns this F# code

let a,b,c = Variable "a", Variable "b", Variable "c"

(-b + sqrt(b**2 - &4*a*c)) / (&2 * a)
|> latex

into LaTeX producing the following: $$\frac{ - b + \sqrt{ b ^{ 2 } - 4 \cdot a \cdot c }}{ 2 \cdot a }.$$

Transforming an expression

Arguably the most important use of Expression objects is transforming them to create new expressions. As I argued before, this is really how you know you're "doing algebra" in F#.

This code, for instance, traverses an Expression and applies the distributive property wherever possible. That is, it replaces any expressions of the form $a(b+c)$ with $ab + ac$ and any of the form $(a+b)c$ with $ac + bc$.

let rec distribute (exp:Expression) =
    match exp with
    // two cases where distributive property applies
    | Product (Sum(e1,e2), e3) -> // case (a+b)c
        Sum (distribute (Product (e1,e3)), distribute (Product (e2,e3)))
    | Product (e1, Sum(e2,e3)) -> // case a(b+c)
        Sum (distribute (Product(e1,e2)), distribute (Product (e1,e3)))
    
    // if distributive property doesn't apply, keep looking recursively
    | Product (e1,e2) -> Product (distribute e1, distribute e2)
    | Negation e -> Negation (distribute e)
    | Sum (e1,e2) -> Sum (distribute e1, distribute e2)
    | Difference (e1,e2) -> Difference (distribute e1, distribute e2)
    | _ -> exp

Thanks to F#'s powerful pattern matching, it's easy to recognize the product of a sum and see that the distributive property applies.

Another algebraic manipulation you can do is plugging one expression into another to get a new expression. By that I mean looking for every instance of a variable, $x$, in one expression and putting another expression in its place. For instance, if you start with $x^2 + 3$ and plug $x+2$ in for $x$, you get $(x+2)*(x+2) + 3$. This is the equivalent of composing the functions $f(x) = x+2$ and $g(x) = x^2+3$ to get a new function $g(f(x))$.

Here's a compose function that plugs a first expression into a second expression at every occurence of $x$:

let rec compose (inner:Expression) (outer:Expression) =
    match outer with
    | X -> inner
    | Number i -> Number i
    | Negation e -> Negation(compose inner e)
    | Sum(e1,e2) -> Sum(compose inner e1, compose inner e2)
    | Difference(e1,e2) -> Difference(compose inner e1, compose inner e2)
    | Product(e1,e2) -> Product(compose inner e1, compose inner e2)

It works a lot like evaluate except that instead of plugging in a float value at every occurence of $x$, you plug-in another expression. Putting distribute and compose together, you can do the following:

compose (X + &2) (X * X + &3)
|> distribute
|> latex;;

which gets you the correct, expanded result: $ x \cdot x + x \cdot 2 + 2 \cdot x + 2 \cdot 2 + 3 .$ If you want a challenge, try writing a function that simplifies expressions by "combining like terms". You could simplify $2\cdot 2 + 3$ to $7$ and $x\cdot 2 + 2 \cdot x$ to $4\cdot x$.

Symbolic calculus

A final important example of manipulating symbolic expressions comes from calculus. The derivative of a function $f(x)$ is another function which, roughly speaking, tells us the instantaneous rate of change in $f$ with respect to $x$ at any point $x$. The derivative of $f(x)$ with respect to $x$ is written $f'(x)$, $\frac{df}{dx}$, or $\frac{d}{dx}f$. The latter notation is nice because it shows that the "derivative with respect to $x$" is a machine, written $\frac{d}{dx}$, that acts on a function producing a new function.

Much of the work of taking derivatives is applying rules to transform the expression for $f(x)$ into another expression for $f'(x)$. The simplest derivative rule is that if $f(x) = c$, where $c$ is any number, then the derivative is $f'(x) = 0$ (constant functions have zero rate of change). Another simple rule is that if $f(x) = x$ then $f'(x) = 1$.

The rest of the rules tell you how to take derivatives of more complicated expressions, for example if $f(x)$ is a sum of two expressions $g(x) + h(x)$ with known derivatives, then $f'(x) = g'(x) + h'(x)$. If $f(x)$ is a product, like $f(x) = g(x)h(x)$, there's also a formula, but its a bit more complicated: $f'(x) = g'(x)h(x) + h'(x)g(x)$.

The point is, as you probably expected, these rules can be encoded in F# for the Expression type. The following derivative function takes an expression and returns an expression for its derivative with respect to $x$.

let rec derivative (exp:Expression) =
    match exp with
    | X -> Number 1
    | Number _ -> Number 0
    | Negation e -> Negation (derivative e)
    | Sum (e1,e2) -> Sum (derivative e1, derivative e2)
    | Difference (e1,e2) -> Difference (derivative e1, derivative e2)
    | Product (e1,e2) -> 
        Sum (Product (e1,derivative e2), Product (e2, derivative e1))

For instance, derivative (X*X) returns

Sum (Product (X,Number 1),Product (X,Number 1))

or $ x \cdot 1 + x \cdot 1 $. If your calculus skills are fresh, you'll recognize that $2x$ is the correct answer and that this result is equivalent.

Conclusion

There are countless other ways to extend and use the Expression type, and I can't mention them all here. The point is that, in F#, you can accomplish some sophisticated algebraic tasks with only a few lines of code. I'll concede that Wolfram Alpha is a free and more powerful alternative to what we've built here, but it can't do everything. If you're working in a specialized mathematical domain, it is useful to know how to build a small, fit-for-purpose symbolic algebra library. I think the examples above make a good template for such a project.