Math for hackers

ChaosWest TV intro music

Herald: Good afternoon, everybody, and
welcome back to Chaos TV West.

We are going to see a prerecorded
talk by Michael Sperber

about mathematics for hackers.

Michael is… once was a mathematics
student, but never finished his degree

and is in the process of
revisiting this old love of his.

Dieser Vortrag wird auch
simultan übersetzt in Deutsch.

And, well, enjoy.

Michael Sperber: Welcome!

Well, I'm here to get you all
excited about math for hackers.

Now, you can have an entire hacker's
life without having encountered

much of mathematics. After all, this
conference and this community to a large

degree really is about finding unexpected
behavior in software such as Heartbleed.

I mean, there's zillions of examples, but
Heartbleed is an example where, you know,

the OpenSSL API exposed secret memory
through a regular API call. That was

certainly unexpected. Now, you might
consider this unexpected behavior to be

just an inevitable part of software
development because it's so complex,

right? Things that you didn't expect
happen due to all the complications and

the complexity. On the other hand, with
critical infrastructure, such as OpenSSL,

you really want certain aspects of that to
really run reliably, correctly. And so

really, that unexpected behavior comes
down to a correctness issue. And,

of course, that's where mathematics might
come in because mathematics deals in

correctness a lot of the time in the form
of proofs. Now, you can certainly apply

proofs to software systems to great
benefit. But of course, proofs are often

tedious and a lot of work. They involve a
great deal of mathematical intuition.

You might not feel like that today, and
you don't have to, because I will talk

about something else today. I will instead
talk about mathematics as a language.

Right. This is not a new idea,
it's hundreds of years old.

Here's a quote from Galileo
that said, well,

the world really can only be understood
in terms of the language of mathematics.

And, you know, a lot of
mathematics concerns itself with finding

formal methods for the world around us.
Now I want to emphasize the fact that

really mathematics doesn't really model
the world around us directly. It really

does that through the detour through our
perception, right?

Mathematics really is
a fundamentally human construct

that our mind uses to understand
the world around us.

And in that way, it's also a social
construct because, well, we don't really

need mathematics, if not for communication
between different people.

And that's really where, you know, the
value of mathematics for software comes in

because software also is an image, sort of.
Our perceptions perceptions of the world

around us, a lot of the time. At least
useful software is. So, one particularly

useful part of mathematics for hackers,
for software construction, is, well, first

of all, the language of equations. And
here's a couple of equations, right?

x plus two equals six, that's very simple,
specifies the value for x.

This next equation, well, it has...
so x is a variable

and the next equation has two variables,
has x and y.

So it has two x squared plus
two y minus two equals zero.

That's a quadratic equation. Might even
have, you know, several solutions. And

finally, there's an equation that involves
a function whose definition is unknown.

It just says, well,
f(5) plus f(7) equals 70.

Now, you know,
when it comes to functions,

well, those are things that also
exist in software. So we might

conceivably use the language of equations
involving functions to describe functions

in our software. So we might take that
equation to describe that piece of

software written over on the right-hand
side. And, well, you know, we could try to

kind of work through it. Right? You can
see there's a function, there's a variable

that's external to that function. So it
goes across several invocations of it,

called y. And it's initialized to 7.

And maybe if we call f(5),
x is going to be five.

Y'know, try to go through it in your mind.

z is going to stash
the old value of y, which is seven,

and then y is going to be set to x.

So it's not going to be five. And then we
multiply x with the old value of y, so we

multiply 5 with 7 getting 35.
So f(5) might return 35.

And with f(7), we then after that call f(7)
y is now 5,

we stash the old value
in z, so it's now 5

x is 7,
and it returns 35 again.

Only the product, the multiplication,
works in the other order.

And the sum of that is 70, so you might
say, well, that equation describes that

function over there. But really, we had to
go through a lot of detail and sort of

tracing through the program to figure that
out. And also, it only works with that

initial value of y and it only works if we
call those functions from left to right.

But the language of equation doesn't say
anything like that, that we really need to

respect order or something like that.
Really, f(5), in mathematics, should

always return the same value. Otherwise,
you know, it becomes much harder to really

consistently apply the language of
equations to programs. Therefore,

Really, that's I guess the first hint
that mathematics gives you,

is that you should write functions that
always return the same value given the

same input. But, I digress.
Another aspect of the language of

equations is a concept called
substitution, that you probably know. So

imagine that first equation says x equals
to 7. And then there's a formula that

has that variable occurring. And in the
context of that first equation, what we

can do is you can kind of plug in that
equation, we can substitute every

occurrence of x with the number 7 in
this case and then use that to figure out

the final result of that formula. That's
also something that fundamentally only

works, you know, if x doesn't change over
time. If your functions really return the

same value every time you call them with
the same input. Now, the substitution

principle is not just for equations of the
form where you say x is a certain number.

You might also have an equation that
expresses x in terms of another variable,

such as z in this case. And you know, that
first equation means, well, I can plug in

2z every time x occurs in that formula and
use that to do further evaluation or

simplification of that formula. And what's
more, it also works the other way around,

right? I can work. I can sort of read that
equation in the second line, also from

right to left. So order does not matter.
So that's a fundamental principle of a

branch of mathematical algebra, right,
that we have variables and that we have

that substitution principle and that we
have equations. So well, here's a well

known algebraic formula, the binomial
formula, or one of them, at least.

You might've learned that at high school.
But today I want to look at a couple of

more slightly more fundamental equations
that might be part might have been part of

your school algebra class. So I want to
point out that all of these equations have

names, and you might try to think of them
right now, but I'll try to go through them.

You might think of the names and
then I'll resolve when I'm done. So the

first equation says when you multiply
three numbers, it doesn't matter whether

you will first multiply the first and the
second one and then the result with the

third one, or whether you first multiply
the second and the third one and then

multiply with the first (I'm going from
right to left here). The second equation

says you can swap the two arguments of a
multiplication, and the third one says

that you can kind of multiply out a sum in
the sense that,

when you have
a times the sum of b and c,

you can multiply a individually,
with each of the of the sums there.

Now here are the names:
The first one says, well, it doesn't

matter which way we associate the
multiplication with these three numbers,

so it's called "associativity".

The second one? Well, it comes
from a verb that says "to swap".

So it's called "commutativity".

And the third one is about distributing
a multiplication over an addition.

So it's called "distributivity".

And so these are all very valuable
and useful equations, but

really the most useful one is the first
one, associativity.

And associativity is something that
works not just for plus.

It also works for multiplication,
for example.

So really, when you talk about
associativity, you don't talk about it in

isolation. You have to say what operation
you mean is associative or is not

associative; in this case, "plus" or
"times". Moreover, associativity is

something that's not restricted to
numbers. So, for example, here are two

Boolean equations that specify
associativity for a Boolean "or" or "and",

so with the "or" operation you can take
three Boolean values, it doesn't matter

which way you "or" them up,
you always get the same result.

And the same works for
the Boolean "and" operation.

While these are kind of primitive values,

but you can also have
values that have structure.

So, for example, you might
program with a list data structure.

So you have a list with elements,
a1, a2, and so on, until aN.

And you might take two lists, where the
second one has elements b1, b2, ..., bm

and you concatenate them together. I
wrote this with that funny bow tie symbol

there, concatenation. So you concatenate
these two lists, and that operation,

that concatenates any two lists is,
if you think about it, also associative.

Now, what value does it have
to know that an operation is associative?

So here's a classic example where that's
valuable. One way to think about,

associativity as well: you can move the
parentheses around, right? And if you can

move the parentheses around, it doesn't
matter where they are. And that means that

you can leave them out entirely if you
have sort of a chain of the same kind of

operation. So imagine you have a large
parallel computation that's structured in

the following way: you have individual
computations a, b, c, d and so on until z,

and they're all independent of one
another. And to get the result of your

overall computation, you all combine them
with that operation that's written as that

black rhomboid. I'm just going to say
diamond from now. So the diamond

operation. And so the combination works
with a diamond operation. But if you know

that the diamond operation is associative,
it means you can sort of bunch up your

"abc"s any way that you like. And so, for
example, you might say, Well, if I've got

four machines working on this computation,
I can split my individual computations in

four bunches. Combine, you know, diamond,
the first bunch, the second bunch, the

third bunch and the fourth bunch, and then
combine the results of those and I get the

same results. It doesn't really matter if
it's five bunches or six or seven, or even

if it's irregular, right? And so that's
the freedom that associativity gives you

in distributing your computation. And
this, what what I just told you, this is a

classic big data abstraction for large
scale parallel computations called

MapReduce. But I really want to talk about
something more fundamental today, which is

how we think about the things that happen
in our software. So here is an excerpt

from the Java API documentation and ir
draws an oval, so it has to do with

graphics, with images. And you notice,
right the draw over operation, it has

returned type void and the documentation
there talks about it in terms of pixels.

Now, really, we think of an oval as this
thing, right, as an object or a shape or

something like that, right, as an entity
in its own right. But if you look at the

documentation there, you can see that
drawOval doesn't create an object that

corresponds to the notion or mind has of
an oval, right? It just flips the colors

of a bunch of pixels in some imagined
canvas that drawOval paints on. So that's

very different, right? And then the notion
of having a thing that's an oval is really

something that our mind reconstructs from
those pixels. But that gives us a very

limited sort of API for dealing with
images. And you can do that differently in

a way that that is amenable to algebra and
mathematics. And well, you can find that

in several places. One that's particularly
accessible is the Racket Image Teachpack

library that comes with the racket system.
So I put a download link down there,

generally a great system to play with. And
so this is how it works: Well, Racket is a

lisp like language, so the syntax works of
a different from Java or C in that when

you call a function, the parentheses go,
around the function call and the arguments

and the arguments are separated by white
space rather than commas. So first thing

is you call a function called circle, you
pass it three arguments: 50, solid, and

red, and it returns a red circle. Well, as
you might imagine. But really, I want you

to understand that it doesn't flip pixels
or something like that. It really returns

an object representing the circle. And
it's only the racket API that then

displays that object as an actual picture
that we can view. But it could also do

something else with that picture: save it
to a file, send it to somebody over the

network or something like that. So well,
first function returns a circle. Second

function is also square function that
returns a square. You can see I can put

something, I can put outline instead of
solid to say that I want just the outline

of a square or there's this blue star at
the bottom returned by the star function.

So these three functions are kind of
primitive in the way that they create

images out of thin air from a bunch of
numbers and strings. And here's another

such function called right triangle that
creates a triangle out of thin air. Now

there's three more operations here that
don't create something out of thin air. So

there's the rotate function, for example:
it takes an image. An existing image - it

has to exist before you call "rotate" and
rotates it, in this case by 10 degrees,

just a little bit. And then there's two
other functions, flip-vertical, which

flips an image vertically and flip-
horizontal, which flips it horizontally,

so creates a mirror image, if you will.
Now, these two functions, they transform

an image in some way. And what's important
to understand is an image object goes in

and they returned an image object also.
And that image object that's returned, you

can pass it to other operations. So, for
example, that's what happens here. You

can, for example, rotate that triangle
again, as we did on the slide before. And

you can pass that result, you can stick it
into flip-vertical to then flip the

rotated image. Now what you see here is
particular examples. So "what happens to

the triangle when you first rotate and
then flip?" But some of these things can

be generalized to general equations that
hold for all images. So here's two very

simple examples. The first one says, Well,
if I flip an image and I flip it again, I

get the same image out again. And then I
think hopefully plays to your visual

imagination or intuition. The second
equation says, Well, if you flip

horizontally and then vertically or you do
it the other way around your first flip

vertically and then horizontally, you get
the same result. And again that should

conform to your visual intuition. So those
are traditional equations that

characterize how images work and how image
construction works. And we can get some

particularly useful equations from these
three operations that are on this slide

here. Now what they do is, they don't just
take one image and output one image the

way that rotate and the flips do, but they
take two images each and return one image

that results from combining them. So the
first function, "beside", takes two images

and sticks them together horizontally,
gives you the resulting image. "above"

puts them above each other. Gives you the
result. An "overlay" puts them on top of

each other. And these are operations. You
know, they have the same form as "plus" or

list concatenation or multiplication or
"or" or "and" in the sense that "or" takes

two Booleans and returns a Boolean. "plus"
takes two numbers, returns a number.

"beside" takes two images, returns an
image. Same thing for "above" and

"overlay". And whenever you have that, you
have a function that takes two things and

returns one thing, you can think about
associativity and you should. And in fact,

these functions, if you kind of work again
for your visual intuition, you figure out

that "beside", "above" and "overlay" are
all associative operations. So, with

"overlay", for example, should be
especially intuitive and that if you have

three images on top of each other, it
should not matter whether you first kind

of staple the top ones together and then
the bottom one to the bottom, or whether

you first staple together the bottom two
and then put the top one on top. In each

case, you have layers in the same
sequence. Now what can you do knowing that

you have an associative operation? We
already talked about parallelization.

Generally, you can do optimizations based
on some of the other equations, for

example, the equation that says, "flip-
horizontal twice doesn't do anything". You

can use that to optimize, right? When you
see somebody doing a flip twice, you just

throw out those operations. You don't have
to compute the actual flip. You can also

imagine computations where you can cache
intermediate results in the same way that

you kind of process that parallel
computation in a tree-shape, and it gives

you great flexibility in that caching and
recombining the cached values. So you can

generally just use that for performance.
You could also turn those equations into

what's called property based testing.
Right. You could stick in random values

for the variables and test whether
equations are actually fulfilled. And that

might help you debug or ensure the
correctness of your library. And finally,

if you really need something to be
correct, then you could provide for the

proofs giving you added assurance using a
technique called induction, because you

combine two things into a thing that you
kind of have to walk that construction

backwards. But again, this talk is not
really concerned with proof so much. But

again, I mentioned that earlier, I really
want to talk about the modeling aspect

that this mathematical way of thinking
about it suggests, right? Again, remember

of the Java drawOval function that just
flips the color of a bunch of pixels. And

here is the picture. But really, we view
this picture - our minds views this

picture as a bunch of concentric circles,
and each circle is a thing in its own

right. Now, I don't know what's intuitive
to you, but apparently it was intuitive to

some people to create that first function
drawOval. And that mathematical intuition

really tells you, well, make pictures,
make images into objects and then create

abstractions based upon them. So we can
use mathematics to kind of create you

create equations after the fact. But
really, mathematics gives us great

suggestions as what the library, what the
API should look like in the first place

that. Well, I often see people doing
something else, so that intuition might

have something to do with that
mathematical understanding. So let me talk

a little bit more about that language of
mathematics. Now that we figured out the

importance of associativity or equations
in general. So, people working in algebra,

they always talk about structures that
have three pieces, right? One piece is a

mathematical set. So just a collection of
a bunch of things, of objects. Then they

have operations on those sets and then
they have equations involving those

operations. On the right hand side, you
can see what we know already. So we have

some set "M"; it could be anything, could
be Booleans, could be numbers, could be

images. And then you have an Operation
Diamond that combines two of those M's

into one M. We here's a little bit funny
notation, right? With a cross there. What

it says is there's two inputs right cross,
cross, cross for each input. And so the

diamond operation has one M as an input,
another M as an input. And then there's

the arrow and that says that there's also
an M as the output. And then finally,

there's that associativity equation that
we've already seen quite a few times

today. And those three things packaged up
together, the set and the operation on

that set (in this case just a single
operation) and equations (in this case,

associativity), this is all called a semi
group. There are other algebraic

structures that we'll see. Now this
translates directly to programing. Your

set "M" in mathematics might just be a type
in your program. And these semi groups, they

occur in lots of places. So all of those
things that we've already seen with

associativity, you could just kind of
shorten your language and say, all of

those things are semi groups. So, for
example, at the top, it says: if you take

the mathematical set of real numbers,
(that's that funny "R", that hollow "R"),

the real numbers, with the plus operation,
(it takes two numbers from the "R" set and

produces one number), of course, has
associativity and therefore it's a semi

group. Lists, with concatenation, fulfill
the associativity equation. Therefore,

they form a semi group. And, for example,
the "overlay" operation from the images,

just as "beside" and "above" do, has that
same shape, right? Combines two images

into one image and fulfills associativity,
Therefore, images and "overlay" form a

semi group. Now, a semi group is not the
only algebraic structure, but it's a

fairly humble one. It can't do a whole lot
and therefore kind of mathematicians build

up from them. They take a simple algebraic
structure and they add more operations or

something else to it. So, for example, the
next step up from a semi group is

something called a monoid. So you take a
semi group and you add something, and I'll

try to explain what that is. So again, you
have to set you have a binary operation,

that diamond operation. And you also say
that in that system, there has to be a

special element. And you have to know what
it is. And that element is called

"bottom". That's what that line says, you
know, that upside-down tee, that's what I

call "bottom". And it also has to be part
of that set M. And now, as usual because

every monoid is a semi group, the
associativity equation holds. And the

bottom line explains about the identity
element about the bottom element, where it

says, Well, if you use the diamond
operator to combine "a" with the identity

or identity with "a", you get back "a". In
German, you often use the word "neutral

element". So it's neutral with with
respect to the binary operation that you

have in your semi group. And hopefully
that appeals to your intuition as it does

to mine. And if you take an algebra class
at the university level, you might learn

about more involved algebraic structures,
such as groups and rings and fields. And

every time you go a step up, right, a
monoid is a semi group plus a neutral

element. A group is a monoid with even
more operations and more equations. A Ring

even involves a another operation and more
laws. Same thing for a field. So, you just

add a bunch of stuff as you go up the
ladder. But for hacking, really? For

computing, for writing software, the two
most important ones from that stack here

are semi group and monoid and you don't
really have to worry about the rest unless

you really write mathematically inclined
software that involves those algebraic

instructions. So we've seen a bunch of
semi groups. Have we seen a bunch of

monoids? Yeah. Well, essentially all the
semi groups that we've already seen are

also monoids. So for example, the plus
operation on the numbers; zero is the

identity there: you add zero to a number,
you get back that same number. With

multiplication, well you multiply a number
by one, you get back that same number. If

you have a list you concatenate with it
the empty list, doesn't matter whether

it's left or right, well, sure enough, you
get the same list. Now the bottom three

examples might look a little bit funny
because they suggest that there's an

identity for this those operations, but
they all are the empty image, so they're

invisible. And so that points that out to
you. And monoids - I can't really over

emphasize this - monoids are everywhere
around us. So, a well-known software

engineer asked me a while ago and said:
Well, your mathematical structure is all

good and well, but what about really
concrete software things? You know, we use

shopping carts. How could you possibly use
mathematical structure for a shopping

cart? Therefore as well, a shopping cart -
you might have a shopping cart associated

with your account at some shop. Right? But
on another day you might go shopping, you

forget to log into your account. But you
can usually still fill a shopping cart.

Now, once you checkout that shopping cart,
you buy the stuff in it, it will usually

ask you to log in. Now there's two
shopping carts, one inside your account

and the one that you just filled. They
have to be combined into one. And really,

it's worthwhile to think about what
properties that combination operation

should have. But there's many other
examplesfor monoids. I have some concrete

examples from applications that I've
worked on. A famous paper in functional

programing, for example, is about
financial contracts - sure ehough, they

form a monoid. Recently, I talked to a
company that makes configurable flower

bouquets, so you might have well, you
might combine two flowers, two sets of

flowers into one to form a bouquet. You
know, all kinds of things. Monoliths

really are everywhere around us. So much
that, my friend Conal Elliott has elevated

this to a general design principle,
whenever you write software for a

particular domain, you should look for
mathematical algebraic structure. And

because monoids are so common, one thing
that you can always try is look for binary

operation on your objects. Check of the
associative law holds. Look for an

identity. And if you don't find that
binary operation, OK, but it's not

associative, you know, that's maybe a sign
that you should try to make it

associative. Doesn't always work, but
frequently does. And and usually gives you

some improvement in the process. Same
thing for identity: If there isn't one,

you might make one up, trusting that you
might need it later. Conal calles this the

Tao check. Something that I really like.
It's whether the software model that

you're creating aligns with mathematics.
And that means, with the deeper structure

of the universe that humanity has
discovered in the hundreds of years that

were there before computing. Monoids are
also useful in differentiation from things

that are not monoids. So, for example, the
maximum operation that gives you the

bigger of two numbers does not form a
monoid. It gives you a semi group. It's

associative, but well, there's no
identity, right? Thinking about it, you

might think, well, but can't I take minus
infinity or something like that? But of

course, that's not a real number. But it
maybe gives you a hint as to how you could

complete that structure if you really need
a monoid. I'll get back to that in a

second, but first I want to talk about a
general principle in that, it's not just

discovering monoids in the domain of
objects around you, you can also construct

monoids systematically. Specifically, you
can create larger monoids out of smaller

ones. So this is probably the most
complicated slide that I have. So don't

worry, it'll be over in the second, but
we'll try to go through it line by line.

So imagine you have two momoids. The first
one is called M1, the second one is called

M2, and each has their own diamond
combination operation. The first one is

called Diamond 1, the second one is called
Diamond 2. The first one takes two M1s,

gives you back an M1. The second one takes
two M2s and gives you back an M2. Now,

using those two momoids, you can create a
larger monoid by taking pairs of elements

from M1 and M2. That's what those funny
cross means. It's something called the

Cartesian product; out of two sets, it
forms the set of pairs where there's one

from each of those two sets in there. And
in order to make that a monoid, we have to

define the binary operation. I'm just
going to call it diamond. You can see the

diamond is defined in such a way that one
pair out of M1 and M2 goes in, another pair

out of M1 and M2 goes in and it returns
another pair out of M1 and M2. And the way

it's defined is, you take two pairs and
you combine the first elements from both

pairs using the M1 monoid and the Diamond
one operation. And you combine the second

elements of both pairs using the diamond
operation from the M2 monoid. And sure

enough, that gives you an operation that's
associative. I didn't put that on the

slide, but it also gives you an identity
with a pair that consists of the

individual identities from M1 and M2. You
know, that works. Also, sometimes you have

a semi group lying around, but you really
need a monoid. I mean, a semi group that's

not a momoid, but you really need a
monoid. Here's a little construction that

will build a monoid from a semi group. So
again, we start with the set. We start

with a binary operation on that set called
diamond, and then we create another set

that I call M-bottom (again, that funny
upside-down tee that you see there). And

we create it by adding artificially one
new element to it, right? It can be in

there before. And then we define a new
operation, Diamond-bottom, that operates

on that set. And and we just define it in
such a way that,if either side of that

operation is the identity, the bottom
element, we just have it return the other

side. So, "a, Diamond-bottom, bottom"
returns, you "a", and the same thing the

other way around. And whenever that
operation is called on two things that are

not bottom, we just call the original
operation. And sure enough, that gives you

a monoid. [glitch] that the thing before,
the M before, was just a semi group, and

you might have seen that construction when
programing. So, for example, the Java

library has something called an option,
and that is exactly that. And again, when

you're defining abstractions like that,
the mathematical notion of the

mathematical equations can provide a guide
as to how that API should behave if it's

supposed to be reasonable. If you're still
bear with me and have a little bit of

patience left, here's another concept it's
a little bit more abstract called the

homomorphism. And that's useful and
thinking about APIs, at least APIs that

combine in this way via something like a
monoid. So look at the first equation: It

says, well, if you take an overlay of two
images, a and b, - more like this - right,

and you rotate it, that is the same as
taking one image, rotating it, take

another image, rotating it and slapping
them together after the fact. And what

that means is really, "rotate" here is
what's called a homomorphism that can kind

of slip inside the overlay operation. Or
another way to talk about it is, commutes

or can trade places with the overlay
operation in that, on the left hand side

of the equation, the rotate is outside and
the overlay is inside, and on the other

side of the equation, it's exactly the
other way around. With the next equation

there flip-vertical of beside, [noise
while indicating the flip], right, and

then the idea is, well, you flip one, you
flip one and then do "beside". That's

certainly eminently reasonable, but if you
think about it, it might depend on the

alignment that you choose for your images
as you put them side to side, right, you

might decide to align them by the top half
like this. And then you might come to the

conclusion that that equation does not
hold. So, but again, it provides a guide.

It probably should hold - you should
design the "beside" operation in such a

way that it works. Now the equation at the
bottom really does not work, right? There

it is. But if you have five minutes after
this talk, or even now, you might think

about an equation that's very similar to
that one, that does hold and that gives

you some insight. That's also a useful
notion when you're designing APIs. Here's

another useful notion in that, Well, with
images, there's the visual aspect, right,

that if you perceive images by looking at
a certain pair of coordinates and

perceiving a certain color. And that color
might be, you might represent it by a

value and that value might come from
different types. And that gives you

different notions of images. So, for
example, the image of bools well, so it

means each coordinate can only be on or
off, or black and white. So it gives you

black and white picture. The next one,
where there's just a number there might

give you some some notion of grayscale. Or
you would, of course, then as in the

bottom two examples, you could stick RGB
triples in there to give you arbitrary

colors or even an alpha channel or
something like that. So when you have a

type such as image that has a parameter,
very frequently you can add a little bit

of structure, what's called a map
operation that you might have seen (not

going to worry about the details there),
but you might get a structure called a

functor. And the word functor comes from a
particularly abstract branch of algebra

called category theory. But even, you
know, the mathematicians sometimes call

that abstract nonsense. But, despite the
term, it really is something that's very

useful and very insightful and it gives
you a lot of insight into the structure of

things. And category theory frequently
describes relationships between things

through diagrams that are quite beautiful.
So here's a characterization of the idea

of a monoid. You don't have to understand
the diagram, but maybe, after this and

after you've mastered monoids for a while,
you'll have look at category theory and

enjoy it. You get more complicated
diagrams such as this one in more involved

abstractions such as, I mentioned functor.
There's also the infamous monad and these

are things that are practical, eminently
practical for creating higher order and

generally higher level abstractions.
Again, not for this talk. That's a

different talk. But I hope I've instilled
in you the sense that mathematics, at

least this kind of simple mathematics, is
useful. If you felt that it hasn't been

simple, that it's been hard, I want to
point out that, well, it might be hard to

understand everything that's been on the
slides on this talk, but it's not due to

the fact that it's complicated. It's not.
There's not a lot of moving parts or

something like that, but it is abstract,
and the human mind needs some time. It

finds it difficult to deal with
abstraction, and therefore you might -

also, if you're interested in this stuff -
you might give your mind some time to get

adjusted to those mathematical concepts
and maybe look at it again a couple of

weeks. Just have a brief look. You know,
maybe look for a monoid or just a binary

operation, look for associativity and by
and by, that stuff will become more

familiar and commonplace to you, and
you'll find it easier to deal with it. And

once that happens, I think you'll find
that very satisfying. So that's pretty

much it. If you want to read up some more
detail on this, I put in four references

that are linked from the slides that you
hopefully download from somewhere. But you

can also just search for those titles and
you'll find those papers. So first one is

a paper by Brent Yorgey that really takes
that idea of using monoids to structure an

image library to the limit. That's just a
great paper. Then there's a book by Sandy

Maguire on algebra-driven design, applies
that idea to different practical settings.

Conal Elliot gave a great foundational
type talk on something called denotational

design. So that's a video. Also has a
paper, but I really recommend you look at

the video. And the classic paper that
introduced this notion of dealing with

images by combining them is by Peter
Henderson, something called functional

geometry. And I hope you'll enjoy looking
at that stuff as much as I will. And I

hope you enjoy the Congress. I hope to see
you around. Well, have a good time. Bye.

Herald: So thank you for this interesting
talk, Michael. And there are a few

questions from the internet already. And
for those who haven't asked questions yet,

if you use the hashtag #rc3cwtv on either
Twitter, Mastodon or the proper IRC

channel, we can still include them in this
Q&A. And the first question I would like

to ask you, Michael, is maybe a strange
one, but you mentioned this concept of

homomorphisms of the monoids. And I was
wondering whether we could do the reverse

rounds. Could could you use these
mathematics to visualize APIs?

Michael: That's an excellent question. So
let me think about it for a moment..., so

with a monoid... So yeah, so the answer
is, first of all, yes. So with the monoid,

one way to think about a monoid is not
just this abstract thing that's going on

right, but since, any value in the monoid,
can kind of be built up by this operation

that's sitting in the monoid, you could
also just represent a monoid not just by

some abstraction, but you can build what's
called a free structure, and that is tree

structured and that you could visualize.
So that's one half of the answer. And on

the last slide, I had to reference the
very first reference on a paper by Brent

Yorgey shows how that works. And it's
generally a paper on visualization. So

that would be one half of the answer. The
other half is that I remember one

industrial project that I've worked on
where people wanted - so there was kind of

a complicated data flow problem, and the
requirement of the customer was, well,

people want to assemble a configuration
for a scheduling problem in semiconductor

fabrication, if you will. And they said,
Well, we want we just want a bunch of

boxes and arrows, and people should be
able to arrange that visually to specify a

configuration. And we ended up looking for
the right formalism to do that. In fact,

there is one in category theory. And
category theory generally is diagrams, but

there is a concept in Category theory
which just happened to fit, and we found

it by going from the customer requirement
to the mathematics. And that gave us a

naturally and very pleasant and actually
mathematically precise visualization form

for that. So I'd argue it's a great tool
to think about visualization. Hope that

helps a little bit.
H: OK, so we can finally look forward to

this, this kind of Neuromancer-like
landscapes while hacking.

Michael: Well, yeah, it feels like that
sometimes, yes.

H: Another question was from a viewer who
had never seen such sexy algebra in their

life: Whether you're willing to submit a
proposal next year to go into a little

more in-depth continuation of this talk.
M: Sure. I'm very happy to.

H: That's a short answer to a relatively
long...

M: OK. Can't say you haven't been warned,
but yeah, I'll try.

H: Yeah, and also it needs to be accepted
by the content team, obviously. Another

question that is about something you said
you wouldn't talk about, and that is about

formal verification of algorithms M:
Yeah, but none the less might be useful

for the audience to know if they're
seeking formal verification for

algorhithms. What avenues you would
suggest to people, especially people

without much of a formal background in
mathematics, to start looking at, as in,

placed for further learning.
M: Yes. Yeah, that's that's an excellent

question. So I think one place that I'd
start with, and I think there have been

talks about this at earlier iterations the
of the Congress that I'm sure you can

find. There is, in fact, there's a new, if
you will, family of programing languages

that are based on strong types called
dependent types. And they're very

expressive and they allow you to express
mathematical properties. Now, in the old

days, we would write down a mathematical
property, of a program that we wanted to

have, and then we would use - if things
are good, we would use a proof assistant

to find the proof, and that would be a
very cumbersome process that you would

have to do. Now, with this new family of
programing languages, Idris and Agda are

two prominent examples, what you can do is
you can give the type and you can push a

button (essentially - it's not quite so
easy, but there's actually IDE support

where you can push a couple of buttons and
it will generate a program that has that

type). And that program is guaranteed to
be correct, right? Because with the

combination of the type and the program
itself, there is the proof right there

sitting there. And that, at least for
simpler things, takes away a lot of the

burden, at least at the burden of getting
into this kind of tool. It's still kind of

intricate work to put together more
complicated proofs, but to get into that

medium, it's just great fun and it's a
very satisfying activity. And you don't

have that impression that you sometimes
have with proof assistants that you're

kind of fiddling in the dark with a
screwdriver. So, it it's a concrete place

that you're looking for. I would I would
recommend looking at a programing language

called Idris and maybe look at some of the
Congress talks that we've had about in the

past.
H: Yeah. Having been to at least one of

those Congress talks, I also would ask a
follow up question to that: Does the new

typing capability that, for example, Rust
provides, rise to this level that you

mentioned with Idris and other languages,
or is that not advanced enough for that

yet?
M: I'm not an expert on rust. I haven't

seen IDE support on that level. I'm pretty
sure the type - I mean Rust has a type

system that has a specific kind of
expressive capability that allows you to

express memory safety. Right? And then
because, your type-correct program, if

you're not using the unsafe features, is
guaranteed, is kind of proven to be

correct and to adhere to those to those
memory safety criteria. But I have not

seen the general expressivity that
language is like Idris gives you in Rust.

Maybe there's a way to do it, but I'm I'm
reasonably confident it's not as practical

and not as easy to get into.
H: Yeah, and also it's very off-topic

since you said you wouldn't be talking
about this anyway right now. So we're sort

of veering. One of the other questions is,
will you be around in the 2D world

sometime to talk directly to people from
the audience?

M: Yeah, sure, we'll do that right after
the talk. Maybe after a little lunch

break.
H: And then what nickname will you be and

where will you be hanging out?
M: My Twitter handle, which was also being

called "sperbsen".
H: We have this 2D rc3 world, this kind of

online adventure thing where the people
visiting are walking around with their

avatars and, well you haven't been there
yet, I take it from your...

M: No, no, no. I have been there. I'm just
saying my avatar there has the same name

as my Twitter handle.
H: I'm sorry. I'm sorry for interrupting

you..
M: So it's called "sperbsen" "Sperber" was

not available anymore.
H: I apologize.

M: So I'll be there.
H: And I think this... There's another

question, and it's: Could something like a
Turing machine have been constructed with

the mathematics of 2000 years ago?
M: So I got to Turing machine and I got

mathematics as of two thousand years ago,
but I lost...

H: Could something like a Turing machine
be constructed with the mathematics of two

thousand years ago. This may be a bit of a
speculative question.

M: I don't see anything that wasn't there.
I don't see why not. I'm not 100 percent

sure what exactly the mathematics of 2000
years ago was, right. You know, my basic

knowledge goes back a couple of hundred
years, but the basic mechanism of a Turing

machine is very simple. It's not my
preferred mechanism to talk about

mathematics and hacking, but, sure, why
not?

H: And the, I think, final question is
[...] start teaching Haskell in teaching?

M: Well, that's a great question. It kind
of goes, I'm doing a workshop later on

teaching programing. I think teaching
programing using Haskell is a terrible

idea. So obviously, you all know, I'm a
big fan of functional programming. I

actually do a lot of Haskell in my daily
life. and I've given talks using and on

Haskell in the past. But Haskell is a
programing language coming out of the

research community and used for
professional programing. If you really

want to do an effective introduction to
programing, you're well off using

specialized programing languages for
learning. That's what I will advocate

later today at 4pm Middle European Time.
H: OK, thank you. And this concludes the

session, thanks for being here.
M: Thank you. Thanks for having me.

postroll music

Subtitles created by c3subtitles.de
in the year 2021. Join, and help us!