Algebra Equality And Elixir Match Operator

Thoughts on the comparison between elixir match operator and Algebra equality

As the main driver of Moore's Law today seems to be the increase of processing cores instead of a processor's clock speed, modern software has to truly embrace parallel computing in order to fully use the available resources. In this scenario, functional programming started becoming increasingly relevant. More than just the newest buzzword, some are heralding it as the next step in programming evolution.

Curiously, due to my background in Mathematics and the computer science professor I had in college, my first computer science lessons were in functional programming more than 10 years ago. As much as I enjoyed writing code in a functional style, I never envisioned it gaining traction, as I felt it had a more academic flavor to it. Personally moving from functional to object-oriented programming was a revolution and enabled me to speak a more widespread dialect. It is funny how certain things play out.

Recently I have been investing some time looking more closely into Elixir. After having read some blog posts, gone through a couple of tutorials, and played the obligatory CodeSchool challenges, I decided to get myself a copy of Dave Thomas' Programming Elixir 1.3. Most resources start by explaining the match operator. As most languages use the = symbol to represent assignment, some relearning has to be done to understand what = does in Elixir.

The Match Operator

In case you haven't heard of it before, here is quick run through of how the equals sign work in Elixir.

iex(1)> a = 1
1
iex(2)> a
1
iex(3)> a = 2
2
iex(4)> a
2

Looks pretty standard right? Then what about this?

iex(1)> a = 1
1
iex(2)> a
1
iex(3)> 1 = a
1

What kind of black magic is 1 = a? Well, turns out the = symbol in Elixir kind of acts first as an assertion (==), then if the assertion in not downright false, it tries to act as an assignment (:=). I like to think of it this way:

• Is the assertion true?
• If not, are there variables on the left side whose value could be changed to make the assertion pass? If so, bind that value to that variable.
• If all the above fail, blow up.

With this in mind let's run through the previous example.

1. a = 1 is false as a is undefined. Can we assign a value to a such that the assertion would be true? In this case, yes, so let's bind the value 1 to the variable a.
2. What value is bound to a? 1.
3. Is 1 = a? Yes it is.

So what would happen, if we then asked 2 = a?

iex(4)> 2 = a
** (MatchError) no match of right hand side value: 1 

We get an error as no match between the left and the right-hand side were possible. (Did I tell you how much I like the error messages in Elixir?).

Why was Erlang (the language Elixir builds upon) designed like this? Because this opens the door to pattern matching, which can allow you to do some non-trivial assignments in a way that can be quite elegant. Here is a random example (no elegance there).

iex(1)> [1,b,c]=[1,2,[3,4]]
[1, 2, [3, 4]]
iex(2)> b
2
iex(3)> c
[3, 4]

Algebra Equality

As this behavior may differ from what some people are accustomed to, a common metaphor used to explain it is the equality in Algebra.

Joe Armstrong, Erlang’s creator, compares the equals sign in Erlang to that used in algebra. When you write the equation x = a + 1, you are not assigning the value of a + 1 to x. Instead, you’re simply asserting that the expressions x and a + 1 have the same value. If you know the value of x, you can work out the value of a, and vice versa.

-- Dave Thomas

While I think this is a good enough analogy and that the equals signs in Elixir indeed allows to do some powerful things, it still falls short if compared to the equality in Algebra, and \(x = a + 1\) is not really a good example to showcase their similarities.

In Algebra, the equality is a special binary relation called an equivalence relation. For a binary relation to be an equivalence relation, it must be:

1. Reflexive. a must be equal to a.
   $$ a = a $$
2. Symmetrical. If a equals b, then b equals a.
   $$ a = b \Longrightarrow b = a $$
3. Transitive. If a equals b, and b equals c, then a equals c.

$$ \begin{cases} a = b\\ b = c \end{cases} \Longrightarrow a = c $$

Of those three, only the transitivity is assured by the match operator. This means that with the quoted example \(x = a + 1\) Elixir will not be able to determine the value of a if it knows the value of x.

iex(1)> x = 1
1
iex(2)> x = a + 1
warning: variable "a" does not exist and is being expanded to "a()", please use parentheses to remove the ambiguity or change the variable name
  iex:2

** (CompileError) iex:2: undefined function a/0
    (stdlib) lists.erl:1354: :lists.mapfoldl/3

As the undefined variable is on the right-hand side of the match, Elixir does not try to bind a value to it. Instead, here it assumes a is a function, which is obviously undefined, hence the CompileError.

But trying to determine the value of x when the value of a is known works.

iex(1)> a = 3
3
iex(2)> x = a + 1
4
iex(3)> x
4