Episode post here. Transcription by Prexie Miranda Abainza Magallanes.
Matt Teichman:
Hello and welcome to Elucidations, an
unexpected philosophy podcast. I’m Matt Teichman, and with me today
is Gabriella Gonzalez, creator of the Dhall Programmable
Configuration Language, longtime evangelist
for the Haskell Programming Language,
author of the Haskell for all blog, and
Engineering Manager at Arista
Networks. She is here to discuss the
intersection of algebra and programming. Gabriella Gonzalez, welcome.
Gabriella Gonzalez:
Thank you very much for having me on your
podcast.
Matt Teichman:
Absolute pleasure to have you. So I think that
when a lot of people hear the word algebra, the thing they think of
is high school algebra. Like, the math teacher gives you a problem,
two times x equals 16; now solve for x. Whereas people who’ve gone off
to study a little bit more math in college often come across this
thing called abstract algebra, which is somehow related to the high
school algebra, but it’s a little more general. What exactly is
abstract algebra?
Gabriella Gonzalez:
So typically, when we think about
algebra, we think numbers, maybe even simple arithmetic. The idea
behind abstract algebra is that you take these algebraic operations,
but they work on things that are not numbers. For example, we’re going
to be talking about how you can add things like code, or programs, not
just simple numbers. That’s what makes it abstract: the fact that
it’s no longer on numbers anymore; abstract algebra is a bit more
general than that. That’s kind of a first order approximation of
what’s going on, but I feel like it’s a useful way to get started, in
thinking about it.
Matt Teichman:
So you can add and multiply other stuff
besides just numbers. In some sense that we can actually make
precise.
Gabriella Gonzalez:
Exactly. Yup.
Matt Teichman:
Well, that’s crazy. So I don’t know, I have
two cups of water, and I pour one over the other. Is that adding?
What would be an example of adding something that’s not two numbers?
Gabriella Gonzalez:
One example I like to give is a
recipe. Let’s take plus and multiplication. In a recipe, imagine that
“times” is that you specify that you want to use more than one
ingredient. Typically, when you read a recipe, you’ll say: OK, the
ingredients are A, B, and C. So you can imagine that you could
represent that algebraically as A “times” B “times” C. And then often,
in recipes, you can substitute one ingredient for another
ingredient. Maybe you substitute—I don’t know, I’m bad at
this—honey with sugar, or—
Matt Teichman:
—yeah, or agave, or some other sweetener.
Gabriella Gonzalez:
Exactly. Yeah. The way you can represent
that is using plus. So the idea is that A plus B means that you can
use either ingredient A, or you can use ingredient B. And if you
think about it, many of our algebraic intuitions are correct, if we
define recipes using that convention.
Let me give an example. One of the arithmetic rules that you’ve probably learned in school is the concept of distributivity, where you say that if I take A and I multiply it by B plus C, that’s the same thing as A times B, plus A times C. If you think about that from a recipe standpoint, it’s saying, OK: if I need ingredient A, and I need ingredient B or C, that’s the same thing as saying, I need either ingredient A and ingredient B, or I need ingredient A and ingredient C. That algebraic intuition still holds, when talking about recipes, even though we’re not really talking about numbers anymore.
Matt Teichman:
Right. At first, I was a little bit thrown by
the idea that “times” means “and”, and “plus” means “or”, because—I
don’t know, I’m just used to thinking of “times” as the number
thing. But it seems like what we’re getting at, here, is that part of
the essence of being “times” and part of the essence of being
“plus” is for this distributivity law to apply. That if you tried to
strip what does it mean for something to be a times operation, and
what does it mean for some to be a plus operation down to the bare
essentials, one of the things you’d get is this distributivity
property.
Gabriella Gonzalez:
Actually, my first encounter with this
idea of algebra working on things other than numbers was not abstract
algebra—it was linear algebra, and vector algebra too. One of the
two, in some order. I remember the instructor was going through a
great deal of effort to explain, I think it was vector spaces. I don’t
remember all the details, truthfully, but they spent a lot of time
saying: you can imagine that in these vector spaces, if you add two
vectors, that addition is commutative, and it’s associative, and it
also has some identities.
I was almost bored, or underwhelmed, by the whole presentation of these very simple arithmetic rules, and it was only later, in retrospect, that I realized that that whole underwhelmingness or simplicity was actually the point. Mathematics is not really supposed to be complicated. The idea is that we want to be able to take complex concepts, and we want to be able to reduce them to simpler concepts, because we already have an intuition for things like plus and multiplication, at least for numbers. If we can re-use that intuition for more complex things, like vector spaces, or for matrices in linear algebra, or for recipes, as in the example I just gave, then that allows us to amplify our intuition when thinking about these things, instead of getting bogged down in lower level details.
Matt Teichman:
So if a recipe says you need bananas, and
either honey or agave, in a way, that’s synonymous with saying you
need to have bananas and agave, or bananas and honey.
Gabriella Gonzalez:
That’s correct, and you can generalize
this. Instead of just thinking about the ingredient list as satisfying
algebraic properties, you can actually imagine that the recipe
itself—the sequence of steps in the recipe—can be viewed as
algebraic, in the same way. So for example, you can imagine that A
times B means “first do A, and then do B.” Whereas A plus B, can be
viewed as saying, “you can either do A, or you can do B.”
Matt Teichman:
Interesting. So now we’ve shifted which
aspect of the recipe we’re looking at, and we’ve noted that something
else in the recipe also has this plus-times structure, or this or-and
structure. So and seems to go along with times, and or seems to
go along with plus, in these analogies.
Gabriella Gonzalez:
Boolean algebra is a simple version of
this. You can actually do it both ways, but typically, the convention
in Boolean algebra is that times means and, and plus means
or. And again, the same laws hold, so you can imagine that ‘A and B
or C’, is the same thing as ‘A and B, or A and C’. Boolean algebra
crystallizes the core essence of what’s going on here, too.
Matt Teichman:
You and I are both big fans of computers, and
I have to say this description of times-like operations in a recipe
and plus-like operations in a recipe reminds me of writing a computer
program. Because a lot of what you’re doing when you’re writing a
computer program is: you’re telling the computer, first do this, and
then do that, and then do one of these things, maybe under certain
conditions, and then do this, and then do this. It’s actually a lot
like writing a recipe. So would that be another type of example?
Gabriella Gonzalez:
Yeah. All programming languages will have
some notion of ‘do this’, followed by ‘do that’. It’s not very common
at all for a programming language to be able to say, do this, or do
that.
But there actually is one example I can think of from my personal favorite programming language, which is Haskell. Haskell has a domain specific language called software transactional memory, which lets you do exactly this. It lets you specify transactions, which are basically atomic operations on mutable variables. But very often these atomic operations, they can compete, and what you can basically say is, you can have this notion of or, where you say, I have two transactions I would like to run. And sometimes, transactions can fail for whatever reason.
For example, a transaction might say, “I have this precondition.” Perhaps some variable needs to be greater than zero, or some Boolean value needs to be false. And this transaction cannot proceed until that condition is met. And so what you can do is you can actually add two transactions and say, “Try transaction A first. And if that transaction is not able to make progress, perhaps due to a precondition, then instead fall back on transaction B.”
So if you imagine that sequencing is multiplication, and alternation between transactions is plus, then it still observes the same algebraic rule, where you can say, “If I do transaction A times transactions B plus C—in other words, if I have transaction A, followed by transactions B, or transaction C, then that should give me the same result as try to run transaction A followed by transaction B, or try to run transaction A followed by transaction C.” You get the same result, either way. It satisfies that same distributivity rule.
Matt Teichman:
So would it be fair to say that a fleshed out
example of that would be: first, try to run ‘part one’ on this machine
in the network. Then, if that machine in the network isn’t available,
try to run it on another machine. That would be the ‘or’, in the
context of writing a distributed software application.
Gabriella Gonzalez:
Yeah, that is very similar in spirit. The
idea is that the existence or availability of the machine is acting
kind of like a precondition. The ‘plus’ here is saying, check to see
if this program’s precondition is satisfied. If not, fall back on the
second program, which may run on different machine, as in your
example.
Matt Teichman:
What would be another example of something
that has this sort of ‘plus-times’ structure in computer programming?
Gabriella Gonzalez:
I think a very simple example that many
programmers will be able to relate to will be regular expressions, or
regexes, for short. So in a regex, you have a language that
specifies a pattern in a string, and you use Regex to match against
strings using this pattern. In the simplest case, the regular
expression will tell you if the pattern matches or it does not.
Matt Teichman:
Like if I wanted to write code to recognize
e.g this is an email address, because it has the shape of an email
address, or this is a phone number, because this has the shape of a
phone number. I would use a regular expression for that.
Gabriella Gonzalez:
Yeah. Also, in cybersecurity, you will
often see regular expressions come up. So, for example, they might
look for some sort of a signature to detect if something is malware,
like a known bad string. Regular expressions very often have a few
core primitive operations. First, you can say the simplest regular
expression string would be something like ‘ABC’. That’d be like, first
match the character A, then match the character B, then match the
character C. And you have a notion of ‘or’ in regular expressions,
i.e. you can say, ‘A | B’. that’s the same thing as saying ‘match A
or match B.’
The idea is that sequencing in regular expressions plays a role very similar to multiplication. And the symbol ‘|’ (pronounced ‘bar’), or alternation, plays a role very similar to addition. In fact, there are other operations—for example, there’s a notion of a Kleene star, which says: ‘match this zero or more times, or ‘plus,’ which means ‘match this one or more times.’ Those actually also have algebraic interpretations, but I won’t go into those right now. Even though the regex language doesn’t use the plus or multiplication symbols, morally, it is basically a form of algebra.
Matt Teichman:
That’s cool. It really seems like a lot of
stuff—more than meets the eye—has this structure. So is this one
of those cases where we’ve come up with a mathematical abstraction,
and the mathematical abstraction finds its unity amongst what appear
to be very disparate things? Or is it a case where, actually, if we
squint a little bit, we can see that, in fact, ingredients are a lot
more like regular expressions than we thought?
Gabriella Gonzalez:
Yeah, as we said, many of these examples
are very similar in spirit. You could imagine that ingredient list is
kind of like a regular expression, where you’re saying: okay, I’m
matching this ingredient, and this ingredient, or I’m matching this
ingredient, or this other ingredient. So—
Matt Teichman:
—I’m matching what I do to the recipe?
That would be the analogy?
Gabriella Gonzalez:
It could be an analogy either to the
ingredient list, or to the actual sequence of steps, too. That’s kind
of the neat thing about mathematics: once you start thinking of things
in terms of these more abstract concepts, you start to see all these
sorts of connections between various application domains. So you can
see that a recipe is kind of like a regex, which is kind of like a
boolean. Mathematics is very good for cross-pollination of ideas
across various domains, because then you can leverage your intuitions
in one domain, and apply that for reasoning about other domains.
Matt Teichman:
Wow. So if I come to a great insight about
ingredients, which just has to do with the ‘plus-iness’ and
’times-iness’ of them, I can maybe carry that over into whatever I’m
doing with regular expressions, or distributed software, or whatever
the other domain is.
Gabriella Gonzalez:
Let me give an example of why it can be
helpful to find connections between various mathematical domains. For
example, in multiplication, whenever you exponentiate something—in
other words, raise some value to some power—there is a fast way of
doing it, that doesn’t involve just taking the number and multiplying
itself, over and over again. Actually, a much more efficient way is to
take the number and to keep squaring it—that leads to much more
efficient algorithm. But that’s cool, because if you can exponentiate
things that are not numbers, then you can actually reuse that same
algorithm, and it still works, and produces the same speedup.
For example, let’s say you have a way of compiling regular expressions to finite state automatons. Regular expressions have a notion of multiplication—in fact, they also have a notion of exponentiation. So if you continue this analogy, and say that in a regular expression, I want to match some expression n times, that’s analogous to taking that expression and raising it to the n$^{th}$ power. Whenever you’re trying to compile or interpret that regular expression, you can interpret that exponentiated regular expression using that same fast exponentiation trick, and it still works, because that exponentiation trick does not actually care whether the underlying thing is a number or not. All it cares about is that it has some notion of multiplication—which regular expressions do—and the reason the algorithm works is because it works against this abstract notion of multiplication, rather than working against numbers specifically.
Matt Teichman:
Cool! So we’re really starting to see the
payoff, then, of going abstract. If we try to distill plus and
times to their bare essence, without assuming anything about how
whether we’re working with numbers, or one of something, or two of
something, or any of that aspect of the interpretation of times and
plus, we really just distill it down to whether these are
commutative operations, or distributive operations, or associative
operations. If we distill it down to stuff like that, the fewer the
assumptions you made about a trick to speed up an algorithm, the
better it’s going to generalize.
Gabriella Gonzalez:
Yeah. In abstract algebra, they have
various different families of abstract interfaces that you can program
against. Let’s start with a notion of a semigroup. A semigroup is:
imagine you have just plus, and you also have one rule, which is
that the plus operation needs to be associative—meaning that if I
add X and Y, and then add Z, that should give me the same result if I
were to have instead added X with (Y plus Z).
Then you can take that semigroup interface, and you can add some additional features to it to turn it into a monoid. A monoid is the same thing as a semigroup, but it also has a notion of a zero. For example, we mentioned that X plus zero should always equal X. Zero plus X should always equal X. Those are called the identity laws. There are also richer interfaces, that build on top of semigroup and monoid. Sometimes, you can have something which can be a monoid in two separate ways. We talked about numbers, and you can think of them as a monoid where, plus is addition, and zero is zero. But if you really wanted to, you could say ‘I’m going to make plus represent multiplication, and make zero represent one,’ and the same rules still hold, because multiplication is associative, and one is its identity. Numbers can be viewed as a monoid, either via addition or multiplication.
Another example of something that can be a monoid in two separate ways would be boolean values. One monoid would be where ‘plus’ is ‘and’, and ‘zero’ is ‘true’. The associativity law still holds, and the identity laws still hold there. Another monoid on Boolean values is where ‘plus’ is ‘or’, and ‘zero’ is ‘false’, and the associativity laws still hold, and the identity laws still hold. So very often, when you have some sort of a structure, like numbers, or Boolean values, which is a monoid in two different senses, we can actually try to mix them, and we say: okay, one of these two monoids, we’ll make that the plus, and the other one of these monoids, we’ll make that multiplication. And then, one of these identities, we’ll call that one ‘zero’, and another identity, we’ll call that ‘one,’
Usually, you know which one to pick, by which way makes the distributive law hold. For example, for numbers, making 0 the zero and 1 the one gives you the correct distributivity law. For Boolean values, it could go either way. You will find that these arithmetic operations arise very commonly, when you have two monoids which overlap on the same type of value. Whenever you have two monoids that overlap in this way, so that they have a zero, a one, a plus, a times, and they satisfy the various associativity laws, they satisfy the identity laws, and they satisfy the distributivity law, we call that a semiring. There are other generalizations of this too. For example, if you research more into this, you can learn about rings, and groups, and so forth. But for today’s conversation, we’re going to be covering mostly semirings.
Matt Teichman:
So if we view the natural numbers—the
counting numbers—as a semigroup, we don’t have 0 yet. Which might
sound crazy, but actually, in ancient Greece, they didn’t have 0 yet;
it was invented in India later. Imagine we just have 1, 2, 3, 4, 5,
etc., and then the one thing we can do with them is add. Once we
incorporate 0 into that, we’ve gone from the structure of a
semigroup to the structure of a monoid. A monoid is similar to a
semigroup, in that it has this associative operation defined on it,
plus, except that it also has an identity element. Anything plus
the identity element is that thing back again.
We often intuitively think of 0 as being nothing, like there’s “none” of something—that kind of interpretation—but really, in this context, the only crucial role that 0 is playing is this identity thing: the fact that if we add any number to 0, we get that number back. That’s the only reason we care about 0, in this context.
Gabriella Gonzalez:
Another example along the same lines
would be lists, or in particular, a non-empty list. A list which must
have at least one element is analogous to numbers without a 0. You can
take non-empty lists, and you can concatenate them, and you’re
guaranteed that the result will still be a non-empty list. But there
is no identity element—no zero yet. And then, if we change them to
be lists, which could be potentially empty, now you can concatenate
them, but you also have the zero value, which would be the empty list.
It’s important to stress that technically, even the natural numbers with zero, and even empty lists, are still semigroups. Remember, semigroup is an interface. It’s the operations that you declare to support, and when you program against an abstract interface, you don’t have to use all the operations that are available to you. Anything that works on semigroups will work for both non-empty lists, and it will also work for lists too. But an algorithm that programs against this monoid interface would only work with lists. It would not work with non-empty lists, because they don’t support that abstract interface.
Matt Teichman:
And then this semiring thing is kind of a
“double monoid,” where we have two associative operations that we can
perform, and two different identity elements, each of which
corresponds to one of the operations. We call the one that corresponds
to the plus-like operation zero, and the identity element that
corresponds to the times-like operation one. Then there are some
rules about how they have to play nicely together. So we have this
menagerie of different kinds of abstract algebras. We have semigroups,
monoids, and semirings, and we introduced this notion of an identity
element. What would be the identity elements in the examples we
discussed earlier, such as the recipes or the regular expressions?
Gabriella Gonzalez:
For the regular expression example, the
zero would be a regular expression that always fails to match
anything; it never succeeds. One would be a regular expression which
matches the empty string, typically denoted by $\epsilon$, in regular
expression notation. You can imagine that the zero would satisfy the
absorption law here. In the regular expression notation, they don’t
really have a notation for zero, but you can imagine that if they
did—if you wrote a regular expression like 0 $\cdot$ A—then, by
the absorption law, 0 $\cdot$ A should equal 0. So if you try to match
something that will always fail, followed by matching A, that itself
cannot match, because the first part will fail, and we’ll never get to
the A in the first place.
Matt Teichman:
So just like 0 $\cdot$ 5 is 0, a program that
says ‘fail’ is the same as a program that says: ’look for the
character M, and then fail.’
Gabriella Gonzalez:
Exactly. So for ingredient lists—again,
we don’t really have notation for this ingredient list—but you can
imagine zero would be an ingredient that is unsatisfiable. Something
that you could never buy; maybe it’s pricesless. And one would be the
empty set of ingredients. It’s trivially satisfiable; you always have
it. We don’t have any notation for that, but conceptually, if we did,
you could write it that way.
Matt Teichman:
What about in the case of concurrent and
parallel programming?
Gabriella Gonzalez:
Yes. So in the software transactional
memory example I mentioned earlier, zero would be the transaction
that always fails, and one would be the transaction that does
nothing and always succeeds.
Matt Teichman:
You mentioned that if we were to strictly give
regular expressions an identity element (a zero and a one), we
would be adding something that’s not in the language already. And
perhaps that raises the question: look, we’ve been writing regular
expressions for decades now, so why bother studying their algebraic
properties?
Gabriella Gonzalez:
I think one of the really important
reasons is that we want to be able to re-use these abstract
interfaces. So the regular expression DSL is a decent DSL—
Matt Teichman:
—DSL means ‘domain-specific language,’ for
those keeping score at home—
Gabriella Gonzalez:
—but we still might want to be able to
re-use other tools, if we can program to this abstract interface. Let
me give an example. So in Haskell, there’s a sum function. In fact,
many programming languages will have a sum function, where you’ve
given a list of elements, and you will add up those elements. But
remember, we’re trying to generalize the notion of number. So what
if we could sum a list of things that are not just numbers? Like, what
if we could sum a list of regular expressions?
So you can imagine that if regular expressions can implement this abstract interface of addition, multiplication, zero and one, then we could stick zero or more regular expressions in a list, and just call sum on that list. Now we’ll get a regular expression that will match one of those regular expressions in that list. In the programming world, the reason why we program against abstract interfaces is so that we can reuse the same function in multiple different domains. The sum function can be used for things that are not numbers, and in math, there’s a similar notion of re-use, too. The idea is that if you can prove something against an abstract interface, then that proof holds for anything that supports that same abstract interface.
Matt Teichman:
Right. Lots of programming languages come with
a sum function, such that if I give that function the list “1, 2,
3,” it’ll add all the numbers in the list, and give me back 6. But one
immediate, very cool payoff to having a more generalized notion of
plus is that we can also “add up” lists of other stuff, besides just
numbers. Anything else that has the same structure. And in fact, the
Haskell programming language literally does this. It has a generalized
notion of summing so that you don’t have to write new code to be able
to sum a list of actions to be performed in order, versus a list of
numbers. The general sum code already accomplishes that.
One cool argument that you’ve made is that although computer programming tends to go through a lot of fads, drawing inspiration from abstract mathematics in the patterns that you use and the code you write can offer us more staying power. I wonder if you could say something about why that is?
Gabriella Gonzalez:
When I first started programming, I
didn’t know anything about functional programming. I grew up on
QBasic, and later
C /
[C++](https://en.wikipedia.org/wiki/C_(programming_language).
Matt Teichman:
Oh, man! Give me some
Nibbles any day
of the week. Love that.
Gabriella Gonzalez:
I remember the Nibbles program. Back
then, for me, programming was just a very boring and mundane thing. I
remember very early on when I was programming, I would try to solve
some problem, and it was never clear to me what was the right way to
solve it. Because there where always lots of different fads: there
was object-oriented programming, there was procedural programming. And
even within those subdomains, there were all sorts of nontrivial
design decisions for how to structure a problem.
I kind of just ran adrift, trying to figure out what was the fad of the day that I should be following, and it seemed kind of very ad hoc and arbitrary. I wanted something that was a little more timeless—a little more self-obvious, self-evident. And the first time I got a taste of that was when I learned Haskell, or, more generally, functional programming. That was the very first thing that showed me the intersection between math and computer science. Once I started seeing all these mathematical patterns that (to me) satisfy those self-evident, self-obvious criteria, I thought: this is going to stay. This has lasting power, and everything else is just window dressing on top of that.
Matt Teichman:
My experience is somewhat similar, perhaps
partially because it took so long for there to be hardware where you
really could use languages like Haskell. A lot of this stuff was
originally explored only as pure math, but of the cool payoffs of that
is that whenever something is made production ready—ready for you to
start writing software with it and putting it out there in the
world—it’s been really rigorously mathematically studied for a
while, before it’s put out there. It’s kind of cool writing programs
that make your computer do stuff in a framework that has also been
thoroughly explored as pure math.
Gabriella Gonzalez:
One thing I’d like to stress is, it’s not
just having a connection to mathematics, because you can take almost
anything and mathematize it, if you sprinkle enough formality on top
of it. In fact—
Matt Teichman:
—enough Greek letters.
Gabriella Gonzalez:
Yeah; I did this a lot when I was a
kid. I was very into math. I would literally spend my free time just
coming up with random math puzzles for various real life phenomena
around me, just to keep myself busy, before I discovered video games,
basically. And—
Matt Teichman:
—I see a puzzle book coming on!
Gabriella Gonzalez:
And so, it’s not just that there is a
mathematical connection. It’s that there is a simple mathematical
connection. For example, if we can find a connection between code and
simple algebra, that’s better, because simple algebra is something
that is taught to students at a very young age, and so they can re-use
their intuition. What I really liked about functional programming was
not so much that it was just mathematical, but because the mathematics
that it connected to was very simple.
I would like to revisit the example I gave earlier, about when I first learned about vector spaces. The instructor was going through the basics, very pedantically, very slowly, and I felt underwhelmed. And when you stumble across functional programming for the first time, it will seem underwhelming, because they’ll be teaching you these very simple and boring things like how to create a record, how to create a sum type, lists, functions—
Matt Teichman:
—oh look, it’s a constant function. It
always returns the same thing. Big whoop.
Gabriella Gonzalez:
And you’re thinking, so what? Here are
all these other languages that are just throwing all these sorts of
very flashy abstractions at me, like
actors or distributed
programming. Functional
programming is throwing me all these very boring concepts. And then,
the real breakthrough you get, when you’re learning functional
programming, is realizing that the boring concepts are actually all
you need. Everything else is just assembled from those simple
mathematical primitives.
We’ve been talking about algebraic concepts. In functional programming, there’s another notion of multiplication and addition. A record type can be viewed as the product of zero or more types. That’s a notion of multiplication, but now it’s at the type level, rather than at the term level. Similarly, in functional programming, there’s a notion of a sum type, which, again, is a type-level notion of addition. Then there’s also a notion of a zero: there’s an empty or a void type, which is uninhabited, and there’s a notion of one, which in Haskell, at least, they call the unit type, which is kind of like an empty tuple (or an empty record), which has no fields. They behave kind of similar to the algebraic operations that we’ve been discussing before.
Another example is that a function type is similar to exponentiation. So a function from $A$ to $B$ can be viewed as $B$ raised to the $A^{th}$ power. The key insight of functional programming is that these simple algebraic types are really all you need for programming. Everything else is just window dressing on top of those core foundational abstractions.
Matt Teichman:
One thing I’ve found is that it’s a little
hard to explain to somebody who hasn’t done it before, but it’s kind
of amazing the way you can build up the really fancy interfaces—the
actor model, and so forth—out of nothing but these very simple
abstractions, because they’re simple abstractions that are designed to
be basic building blocks. Then, what you find is that you don’t have
to have special code that whispers sweet nothings to the compiler to
magically make the thing happen, often in ways that you can’t predict,
or study, or know anything about. You can just do it using the plain
vanilla version of whatever language we’re working in, whether it’s
Haskell, or a similar language. That’s certainly one place where I’ve
experienced this expressive power.
Gabriella Gonzalez:
Yeah. I think it goes back to the notion
of portability and cross-pollination between domains. One thing that
many listeners will find is that if they learn functional programming,
many of those idioms that they learn will actually translate well to
other programming languages, because they’re foundational. Whereas,
for example, if you try to translate object-oriented idioms to a
functional programming language, it will not translate as well,
because they’re not as foundational in nature.
A lot about math, and math-adjacent fields like functional programming, is about this notion of cross-pollination. We want to be able to take something that we learned in one domain, and we want to be able to reuse that or transfer that to another domain. That’s why we care a lot about these foundational, reusable, abstract interfaces. And abstract algebra, like we’ve been talking about before, is just one example of that, where we can take algebraic connections we make in one area and find algebraic connections in other areas, too.
Matt Teichman:
Another fascinating argument you’ve made is
that abstract algebra is a more natural fit for human reasoning than a
lot of other areas of abstract math. I’m not sure exactly what you
might have had in mind there—maybe topology, or analysis; I don’t
know. How does that argument go?
Gabriella Gonzalez:
The key phrase here is equational
reasoning. Equational reasoning is the idea that you understand a
program’s behavior by simple substitution. Typically, in most
programming languages, the way you understand what the program does
is: you simulate the program as some subroutine, and you keep track of
some state in some side column. In a functional programming language,
the way you “simulate a language” is by simply substituting values
with the things that they refer to. That is called equational
reasoning. Thinking about things in terms of these abstract
interfaces tends to make this equational reasoning scale much better
to larger examples. Because if you ever do equational reasoning, the
first time, it is very tedious. It is quite a chore, truthfully; most
people don’t do it. They just kind of hand-wave it.
But if you can think about things in terms of abstract operations, like addition and multiplication, which are equipped with laws, like the associativity law, the identity laws, the distributivity law, the zero law, then those laws are very useful for short circuiting the reasoning process, and you can often use them to simplify very gnarly expressions. It’s similar to the symbolic reasoning that you learn in school for algebraic expressions, like polynomials, and so forth. You can do the exact same thing with code too, because code can behave kind of like those polynomials, and you can simplify code without knowing what underlying variables you’re even referring to.
Matt Teichman:
Philosophers will maybe be familiar with these
concepts under the label referential transparency and referential
opacity. An expression is referentially transparent just in case
you can substitute any sub-expression inside of it for another one
that refers to the same thing. The amazing thing is that this topic,
which so much ink has been spilled over in philosophical logic, is
actually really useful for computer programming. Because you can take
a program that says XYZ in it, and if the code is referentially
transparent, you can substitute different expressions inside of it for
other expressions that are equal to the same thing, and actually
transform the code very easily.
Gabriella Gonzalez:
The key thing here is that you can reason
abstractly about code. Let me give you a very simple example. Suppose
I have a function whose input is X, and whose output is X plus
zero. If I know that X plus zero is always X, I can just get rid of
the “plus zero,” even if I don’t know what X is. That’s an example of
what I mean by abstract or symbolic reasoning. Very often, when we
need to prove code is correct, we want to prove that code is correct,
even when we don’t know what the input is. Part of the reason might be
that it’s not easy (or safe, or cheap) to run that function, and test
it on live data. So we need to be able to understand what the function
does, even when the data is not present yet. That’s why we need this
capability to reason symbolically about programs.
Matt Teichman:
Right, exactly. You never know what a user is
going to do with a program; they’re always going to do some weird
thing you never thought of. If you’re not careful about weird things
the user is going to do, you’re going to get the blue screen of death
and all kinds of unpleasantness. We want to head that off in advance.
Gabriella Gonzalez, thank you so much for joining us. This has been amazing.
Gabriella Gonzalez:
You’re very welcome. Thank you for having
me on your podcast.
Elucidations isn't set up for blog comments currently, but if you have any thoughts or questions, please feel free to reach out on Twitter!