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!