Scale By The Bay 2019: James Earl Douglas, Functional Electromagnetism

Scale By The Bay 2019: James Earl Douglas, Functional Electromagnetism

Recording: Scale By The Bay 2019: James Earl Douglas, Functional Electromagnetism

[Music] so I read on the internet this one time that something like half of the English language comes directly from French vocabulary which maybe isn't too surprising if you've studied languages but I found that pretty interesting and so did the French writer Alexander Duma he was teaching himself English and while reading an English book he noticed the similarities to French and he exclaimed to himself well English is merely French just badly pronounced this may be an apocryphal story I don't know but it's it's nice for this talk this is a talk about finding functional patterns in unexpected places as Duma found with his French vocabulary we can find that recognizing functional programming patterns in unfamiliar systems can actually help us better understand both those systems and our own concepts from functional programming so in this talk we're specifically going to take our knowledge of functional programming and see how we can use that to reason about software-defined radio and we'll do that by looking through the lens of category theory so we will break this up into four sections and please stop me with any questions along the way there's going to be a lot of material especially if you don't have a background in signal processing or category theory or functional programming I encourage you to ask any questions and I can clarify things as we go but otherwise we'll start with a simple technique that I like to use for visualizing categories which will be very informal I'm not a mathematician by any stretch and then we will go into three basic concepts from category theory and that's function composition functors and natural transformations for each one of these we will I'll briefly introduce the theory then we'll take a familiar example from functional programming and see how we can use that to learn about software-defined radio so let's start with visualizing categories at its core a category is really just a collection of objects and arrows and again this is very informal so given a category C it has some arbitrary objects X Y Z and some arbitrary arrows X 2i y 2z you might recognize this in terms of programming where your X Y Z might be some types and your arrows X 2y y 2z might be some function types there's some other things in a category that we will get to like the composition operator and there's a whole lot of stuff that we're not going to cover we're just gonna skip over like laws and things like that so in programming we can use category theory to think about the category of types so in the category of types our objects are very simple flat types like int or string or some class that you might write and arrows are just functions between them so there could be an arrow from it to string or string to int in this example and these are just functions that taken it and produce a string or take a string and produce an int and thinking about programming in in terms of this category this category of types can be really useful for helping reason about the sort of domain of possible program types that we can write we can also think of not just flat types as a category but type constructors as a category so for example we might think about option or the option type constructor as itself a category and in this category our objects are options of things so we might have an option of a or option of B that could be an option of int or string or whatever these are objects in our option category and similarly arrows in the option category go from one option to another so I'm a function you give me an option of a and I'll spit out an option of B and this isn't limited to any one type constructor so we can start adding as many of these as we like so think about the category of the list type constructor so just like with option objects in this category are lists of things so we could have a list of a list of B for some types a and B and arrows in this category are just functions that operate on lists of things okay so that is visualizing categories as they apply to programming now let's see how they apply to radio and before we go there I want to kind of give a quick overview of what we're actually using here for our radios so we will be transmitting and receiving a simple signal and to do that we'll be using a hack RF one which is just an off-the-shelf software defined radio that you can buy and there's a wealth of software out there that you can use to drive the thing we will using goo new radio specifically goo new radio companion which is a GUI graphical front-end atop of a new radio which we'll get into depth in in a minute we're also going to be receiving the signal on a actually a digital TV tuner these are really really inexpensive off-the-shelf devices that were originally intended for receiving TV signals over the air until it was discovered that they're actually a very cheap software-defined radio receiver and so they're very popular to use and decoding all kinds of signals across the radio spectrum so we'll be driving the receiver with this program called GQ rx which looks something like this this is nice because it gives us a waterfall diagram so we can see signals over time across a band and well I'm also using this cheap handheld transceiver to receive the signal that way we can hear it when we transmit it and on something that's not actually connected to my computer so you know that it's really going over the air okay so in canoe radio which I've got here this is how we build a software-defined radio in canoe radio so in this example we have a very simple radio there based on these five blocks and I should point out in new radio everything is done graphically using blocks and connections between blocks and so the way to think about this is each of these blocks is some operation that can operate on a signal a signal is some series of sampled values over time so in this radio and everything flows from left to right in this flow graph so we have five blocks in our radio we have a source and that's producing a Morse code signal that we're going to eventually transmit that blocks and then sends the signal to the next block which is an amplifier this amplifier actually reduces the amplitude by half because we don't actually need to transmit very much power for this demo that amplified signal then goes to the third block which is our narrowband FM modulator and that just takes our our signal and modulates it so that it can be transmitted and received using narrowband FM which is a common way to modulate and demodulate a signal I should point out narrowband FM is really inefficient way to send Morse code and no one actually does it that way but it makes for a nice demo because we can receive it on hardware like this so once we modulated this signal we want to filter out any high-frequency components that may have been introduced by the math or or anywhere else and that we do not want to transmit so we get rid of those and then finally we pass our signal to a sync which in this case is just a driver for that hack RF so I'm gonna spin this up and hopefully we can hear it Oh before I do let me switch frequencies here so we're gonna be on the UHF band and we're going to watch on this waterfall diagram and listen on the little handheld radio note that it's not attached okay so we had to end that transmission with my callsign so that it's nice and legal all right so let's go back to our radio we can stop this from transmitting okay so telling this back to how we came into this we were talking about visualizing categories so this flow graph is itself implemented in Python and under the covers all of the signal processing in canoe radio is done in C or maybe C++ so there's not really any advanced type theory going on in either of those two languages but that's okay as just a user of the companion this graphical flow flow graph we can still reason about it in terms of categories so our flow graph has two main things it has these blocks which as I said are operations on signals and it has the connections between them which kind of represent the signals feeding from one block to the next and so it turns out that signals are like an object in a category and blocks are like an arrow so our signals are discrete values and if you're familiar with functional reactive programming you may recognize this even though the signal is values over time it's still it's still a singular thing it's an object in our flow graph category and blocks are functions that take a signal and produce a signal so there are arrows on the category so we're gonna use this through the rest of the talk and build on it but the the key takeaway here is that if we're looking at a system in this case a radio as long as we can identify objects and arrows and be a little bit informal about the laws of category theory we can use categories to really visualize anything okay before we move on to composition are there any questions on what we just saw sweet so in category theory a category has more than just objects and arrows and one of the things that it has is a composition operator and all this does is assemble pairs of arrows so here's our category from before we have our objects X Y Z we have arrows X to Y and Y to Z so if we wanted for example an arrow from X to Z we could assemble these two using composition to get it so we take why does he compose it with X to Y and that gives us X to Z and note how the arguments to the composition operator are sort of reversed we we have the first function that will ultimately be applied as kind of the inner value in this composition or the second argument but mostly that's just convention in functional programming we have composition and it takes a few different forms depending on what language you're coming from for example Haskell has the dot operator so this says n compose M Scala has the and then and composed methods which basically do the same thing although their orders are reversed from each other but all of these are really just no different from a simple lambda expression that given some input applies it to M and then applies that to N and spits out the result so let's find composition in our radio I'm going to drill down into this block which is our source and as you can see it's actually built from many lower-level blocks and it turns out this is composition so in our radio we have this nice high-level abstract thing it's just five blocks a source and amplifier a modulator a filter and a sink but to build that source it takes a lot more we have to have the the actual C Morse code that we want to send and a carrier on which we want to transmit that and we also have a throttle which is a sort of side effect of how do new radio works and I think and so to keep all of this complexity off of our primary flow graph we make this sort of sub block by composing all of these components together so let's look at how how we can think about composing blocks so let's abstract this to just M and n if we have two blocks and maybe these are lower-level blocks like in our source here we want to put them together into a logical higher-level block called M and then n so in practice this is just wiring them directly together you wire the output of em to the input of n but this is actually composition so m and then n is the same as n compose m so composition is great for hiding complexity we can take really as many functions as we want and start putting them together like we've done here so we've actually composed more than just two arrows here we've composed arrows with more arrows with more arrows until we're kind of at the right level of abstraction that we want ok let's talk about functors in category theory a functor is essentially a mapping between categories a functor can map objects from one category into another and it can map arrows from one category into another so here we have categories at C and D and we have the category of functors which just has one one functor F so we would say that F in this case is a functor from C to D and it can map objects so here we're taking a C object called a and we're turning it into a D object called F of a using the F function arrow a to B we can turn that into a de arrow F of A to F of B and as we'll see this is really useful for cases where maybe we already have an F of a and we have an arrow a to B and we want to be able to apply that arrow to that object we to do so we need to use something like a functor to pull it into the D category so that its input matches the type of object that we're dealing with in programming we have particularly in functional programming we have something very similar but there's there's one interesting difference and that's that to map objects in our categories we're not using a functor we just use a type constructor and as far as I understand this is a practical limitation of basically the way we've our type system works but essentially we have the same thing through a combination of type constructor and functor so let's quickly dive into this so we have our category of plane types like intense string we have our category of optional types like option event option of string and to map objects from one to the other we use the option type constructor but to map arrows from one to the other we use a functor and so in this case our function is from the category of types to the category of options of types the way this is implemented typically in languages like Haskell or in Scala libraries like Scala Zed or cats is just as a type class so the way we can read this in terms of that diagram is given an arrow a to B and I'll go back that's this arrow we can pull that into the option category to make an F of A to F of B so you give me an A to B and I will give you a function that then takes enough of a and returns an F of B and that's exactly what we see here so this is our function a to beat this is our functor mapping it and turning it into a function that takes an F of a where F is option here and returns enough of B and here's a concrete example of that so let's say we want to turn actually this is exactly what we have on the previous slide so a functor for option has to be able to take any arbitrary a to be arrow and turn it into an option of a to option of b arrow and it's pretty simple to implement this we just pattern match on what this option is and if it's if it's none there's really nothing to do if it's some of a meaning this option has some a value in it then to produce an option B we just passed that a value to this function from the other the types category in object-oriented languages like Scala will sometimes see functors implemented slightly differently in this case as a method on some option like type so what this says is there exists a type option and it has a parameter a to to map functions into that category we have a very similar function that takes our A to B and returns a function option a to option B which is sort of encapsulated by this whole trait so once again given our A to B we can then take an option of a and produce an option of B this is the same thing we saw in the previous slide just a slightly different way to do it so let's find a functor in our radio specifically i want to look at the amplifier block here up until now i've been talking about signals as sampled values over time these are digital signals but amplification is itself a function that while it's operating on these signals over time it actually doesn't care about time the way it amplifies has nothing to do with when the signal is happening or how the signal is changing over time it just takes numbers as an input multiplies them by a constant and spits them out so it's actually useful to think about to sort of divorce the amplifier from the concept of time and think about it differently so for example imagine we have a signal in time which we call a time domain signal f of T where T represents time that signal might be something simple like a sine wave so our signal varies in time as a sine wave our amplifier on the other hand as I said it doesn't care about time so our we would represent that perhaps as f of X where X is supposed to indicate that time doesn't matter and so these are these are two types of of signals that kind of relate to the slide we saw on types and options of types so we have sort of undesignated signals and time domain signals and it turns out that it it's really useful to think of these as two separate categories so there's a lot here so let me go through it so f of T as I said before is a signal as a time domain signal is just sine of T and so that is an object in the time domain signals category that we just made up F of X on the other hand that's our amplifier that's just a function that takes a number and spits out a number it doesn't care about time so we put that in the signals category as an arrow so our amplifier we know is taking this function and applying it to time domain signal so there's actually we can reason about a implied functor somewhere that knows how to convert signals into time domain signals as well as signal arrows into time domain signal arrows so two for our amplifier to work with this model we imagine this functor taking our amplify function pardon me our amplify arrow and pulling it into the time domain signals category so that we can apply our time domain signal f of T to it so the key takeaway is that functors are essentially a way for us to use objects and arrows from some different category if we're given a time domain signal from this category and we're given a an arrow from a different category as long as we have a functor that map's between those two categories we can apply them from in a different category all right now let's move on to natural transformations and this one will be a lot so please stop me if you have any questions okay so let's imagine three categories C D and E and C has one object X now let's add a functor F so f is a function to D just like we saw before so given some C object X if we need to make a D object out of it we can use the F function we're going to ignore arrows for a minute similarly if we have a C object X and we want a Yi object out of it we can use a G functor which is a functor from CDE so a natural transformation is in category theory is an arrow between functors and this is how we might represent it so given a natural transformation P it's an arrow between these two functors F and G so remember these are our functors and so given given everything that we've got here if we have an f of X that was produced by this F functor and we want to get a G of X we can use this natural transformation to produce it for us so it will take us from this f of X to this G of X and then we can add another one in the reverse so that we can go back in the other direction in functional programming we see natural transformations usually as a squiggly arrow like this but you can see that that underlying pierrot from before is here so you give me enough of a and that's this guy over here and I will give you a G of a and that's this one over here so here's an example natural transformation from option to list so this says if you give me an option of a I will give you a list of a and again that's pretty simple a none turns into the empty lists and a sum turns into a unary list something interesting here is that this natural transformation and if I go back the the generalization of it actually has nothing to do with functors at least we haven't declared it in terms of functors even though we know from category theory that a natural transformation is an arrow between functors so that's kind of a practical limitation but it's still interesting to think about if we have a natural transformation there must be some functors somewhere even if they're just you know notional and for those functors to exist there must actually be a third implied category and so that might look like this the category of types which we've seen before so from our category of types we can get to option or to lists using functors right so option the type constructor is essentially a functor that turns a into option today list the type constructor is a functor that turns a into a list of a and then so option to list turns out to be a natural transform between these two functors oh and L all right so we're running out of time so I might have to rush through this part but one thing I wanted to talk about in in to get us to the natural transformations in our radio is the frequency domain so I'm going to do this really quick okay so imagine a signal that is produced by summing for different sine waves and here are our four sine waves at the top and here's the result of summing them in time it turns out there's another way to represent signals and that's with frequency as the dependent variable so over here we have a time domain signal that's the sum of four sine waves over here we have a frequency domain signal which is the same it's the sum of four sine waves and so what we're looking at is there's three points which they're sort of represented as spikes here sorry four points represented as spikes each representing a sine wave at a particular frequency so these two graphs at the bottom this time domain signal in this frequency domain signal are showing the exact same information they're just different ways of representing it okay so now that we know a little bit about the time domain in the the frequency domain I want to show you how we can use that to build a digital filter and this is actually what we're using in our radio here and I'm gonna have to rush really quickly through this so let's look at our filter okay so here are our four spikes from before these are our four sine waves in frequency and in green hopefully you can see there's another function on here which is sort of a square wave and on the right we have the product of these two so it's zero everywhere because the green signal is only to find right here and it's zero everywhere else and then likewise the blue signal is defined on these four points and zero everywhere else so when we multiply these things together we get just a bunch of zeros but if we make that green signal a little bit wider so that it overlaps one of these spikes then the output is nonzero at that one point where they're both nonzero and if we keep making this thing wider and wider you can see that our output includes more and more of the input because we're multiplying these two signals together and they're zeroing each other out less and less and this is the concept of a digital filter if we have this source signal with these four sine waves but we only want three of them in the output for example all we have to do is come up with a signal that we can multiply together and zero out the stuff that we don't want I apologize for rushing this is a lot so so let's look at our actual transmit filter that we have here so the way that this filter works is it uses exactly this principle so it takes a signal a time domain signal converts it into the frequency domain so that we can do this frequency domain multiplication converts it back into the time domain and then spits it back out and it turns out that this is a natural transformation so using our time and frequency domains as categories as before imagine we have a time domain signal that's our samples over time coming into the filter we need a frequency domain signal so that we can multiply it and and filter components that we don't want so we have to convert our time domain signal into a frequency domain signal and in DSP this is done using the Fourier transform but really this is actually a natural transformation because we're converting this constructed type into that constructed type and then we have to go back in the other direction and in practice this is done with an inverse Fourier transform and it turns out that that is also a natural transformation because it's taking us from this constructed type to that one and just like before we're sort of ignoring the middle category and and we can infer that there actually must be functors for both of these to be natural transformations so the takeaway is that natural transformations convert values between between types constructed by some functor so we've got a time domain signal we need a frequency domain signal these are two categories we can use a natural transformation to do so so hopefully this has shown that recognizing functional patterns in places that we didn't expect to find them can help us reason about those systems as though we were doing functional programming even though as I said this is all Python and C and also it I find that this helps me understand the functional programming patterns better because it's just a new perspective on on the same ideas that I may have already been developing okay so we're a little bit over time this talk was based on this paper categories for the working hardware designer which I highly recommend if you're interested in this idea and where we used DSP the author of this paper used she wrote a Hardware definition language I think for VLSI design or something but it's a really neat paper and then if you're interested in category theory everything I did in this talk was based on this book by Peirce and if you're interested in signal processing find me after and we can play with these radios or you can check out that the book by Owen so I think maybe we'll take questions offline yeah okay cool thank you [Applause] you