*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!