Why are algebraic properties important?

This is an episode of Thoughts on Functional Programming, a podcast by Eric Normand.

Subscribe: RSSApple PodcastsGoogle PlayOvercast

We often write software to automate an existing physical process. But what makes this possible? When translating from physical to digital, something must be preserved. In this episode, we look into what is preserved across that translation and why algebraic properties might help us find it.

Transcript

Eric Normand: Why are algebraic properties important? In this episode we ask, "How can we even write programs that do really useful work?" My name is Eric Normand, and I help people thrive with Functional Programming.

This is an important topic. We write software often to automate an existing physical, real-world process. Maybe we did it by moving papers around. Maybe we talked to each other, but it's a physical process.

What makes it possible to translate this physical process into software? Put another way, a computer is just a big complex circuit that controls the flow of electrons. How can it be a bank? How is it possible that this thing is a bank?

Banks nowadays run on computer software, so there must be some similarity between a bank and banking software. Now, when I say a bank, I mean like an old-school bank before computers existed. They basically did the same function, which is keeping track of money, who owes who what, the loans and stuff like that. That's what the bank did.

When it was translated from a physical process with people moving papers around, writing, and stuff like that to software, something had to be preserved. What was preserved so that the bankers, the accountants look at the bank software and say, "Yes, that's doing what we did?"

It's not doing what they did. There's not moving papers around. It's not writing in a book. It's not getting a check, copying it into an account record or a ledger, and summing columns. It's not doing any of that. It's just electrons. Why would they say that it is the same?

Something must be preserved. What is that preserved thing? I'm not sure about this, but I think the answer is that there is a similar structure between the bank and the bank software. Something in the structure of it is the same. There's no atoms shared. There's not even subatomic particles shared between them.

It's not the same, but the structure could be similar. What do I mean by "structure?" There are certain relationships. In this ledger, this book that represents your account in the old-style bank, this is one account. It's a book. There is a relationship between the transactions that are recorded in this book and, let's say, rows in a database table. They have similar fields.

It's got a debit column and a credit column. The database table has a debit column. There are relationships. There's arity. One person can have multiple accounts that are captured in both. There's the order. Here's the order that the transactions were processed in. There's also a similar order in the relational database that got stored in the table.

Quantity — you write down a number for the amount of money that was transferred from one account to another. That quantity was written in pen in decimal digits. In the database, it's stored in memory as some binary number, but there's the quantity. We know how to relate the two. We understand mathematically that they're both representing the same quantity.

There are all those things that are pretty straightforward that any programmer could start to piece apart. There are other things that we don't look at often enough, and those are the algebraic properties. These are things like associativity or commutativity. Associativity says that I can basically sum the debits and credits in any kind of grouping.

When you write the transactions into your book, they're going to arbitrarily land on different pages, depending on where on the page you start, how many transactions happened before this transaction. It's going to be on this page, or the next page, or whatever.

I could go page by page, summing that page, writing the sum at the bottom, go to the next page, writing the sum of the bottom. They're arbitrarily grouped by page. It's like these 30 transactions, and then the next 30 transactions, and then the next 30 transactions.

I make the sum of each page, and then I could just sum the sum from each page. That will give me the total in the whole book. What if they had a book with 20 lines per page, not 30 lines per page? Would that break anything?

No, it wouldn't break anything. We know that if you group it by 20, you're going to get the same answer as if you group it by 30. It's not going to break anything. Meanwhile, our database table, we just sum the whole thing all at once.

Except maybe not. It's stored as a B-tree on the disk. How does the sum function work in Postgres? Does it work on the B-tree level? Does it get all the data and then sum it all up in one go? We don't know. The thing is, we don't have to know. It doesn't matter. That is associativity. It doesn't matter how it's grouped.

It doesn't matter if you break it up into a million pieces and then put those pieces together, or break it in half and put those pieces together. It doesn't matter. That is a thing that's shared between these two things. That, to me, is an important property.

Here's another thing. Let's say I write some checks, give one check to my plumber, one check to my electrician, one check to my gardener. I'm just making this up. I give them in a certain order, plumber, electrician, gardener. Will they arrive at the bank in that order? Probably not.

They are all going to go to the bank at different times, depending on what they have to do that day. Maybe the gardener always goes every day, and the electrician goes on Fridays. Who knows? Maybe they want to send it in the mail. The mail doesn't arrive in order. They arrive at the bank in some random order and then end up inside the bank.

They're not ordered in any particular way. They're just put on someone's desk. Maybe they're put on two different people's desks. Does that matter? The order in a bank doesn't matter.

Transactions are coming in, out of order. You write them in the book. They only order a little bit because banks want to collect fees when they write a negative number in the book. Like, "Oh, we summed it up, and it was negative at the end of the day." In theory, they only do that at the end of the day. They allow out-of-order transactions to happen.

For instance, I pay my gardener. My account happens to go negative, but in the stack, at the bank, there's a check to me for more than what I owed the gardener. It should go back positive. It doesn't matter if they do the gardener's check or my check first. There are little wrinkles like that, but in general, the order of the checks doesn't matter.

The order of transactions doesn't matter, because we know we're going to sum them up at the end of the day. That is preserved in the database. The order of the transactions shouldn't matter. Why am I bringing these up? When we're writing our software, we need tools to help us search for things in the real world that are important.

We're observing this process. We're hired by the bank. They're like, "Automate this, please. It's so inefficient. We want to do it digital." You have to observe what they're doing. You're not going to make the system do just that. You're not building a robot to replace a person. You're building a pure information system.

What do you look for? We're taught a lot in school, and in books, and in our workplace training, we're trained to look for has-a relationships, order is important, quantity, whether duplicates are important, that kind of thing. We're trained to look for that, but we're not trained to look for these algebraic properties.

I think we should be looking for them, because it's stuff that mathematicians have spent a lot of time studying and figuring out. These things have a lot of history behind them, a lot of person years of study. They've identified them.

They've identified them in the world, abstracted them, and talked about their properties independently of the thing. These are things that can be abstracted, separated from their context, and translated into our software.

We should do that, because the more clues we have, the more tools we have for analyzing the thing that we are automating, the better. The more tools, the better. We need more help. We don't want to be reinventing things every time. We should look at these algebraic properties.

I'm going to recap. We write software to automate processes very often, some kind of bureaucracy, some kind of information system turned into a digital system. How is it possible that this circuit, this software is able to do the same work as a physical process?

There must be something translated, something that's preserved when we translate, and that's the structure. We talked about a bunch of structures, relationships, arity, order, quantity, has-a relationships, is-a relationships, things like that.

It's also important to look at some things that are less commonly looked at, like idempotence, associativity, commutativity, whether there's an identity or a zero. These are called "algebraic properties." Mathematicians have studied these. There's a lot of prior work on them.

They give us more insights, more places to look when we're trying to translate stuff into software.

If you like this episode, you can go to lispcast.com/podcast. There, you'll find audio, video, and text transcripts — wow, all three — of all the past episodes. You'll also find links to subscribe and to find me on social media where you can talk to me.

Ask me questions. I will throw up a podcast episode trying to answer them, giving my opinions. I am very aware that these are just opinions. I would love it if you had a differing opinion, or would like a clarification, or something like that. Love it.

This has been my thought on Functional Programming. My name is Eric Normand. Thank you for listening, and rock on.