SF Scala: Tim Perrett, Building Enigma with State Monad and Lenses

SF Scala: Tim Perrett, Building Enigma with State Monad and Lenses

Recording: SF Scala: Tim Perrett, Building Enigma with State Monad and Lenses

um so yeah great to be here um as alexi said i don't really get out of the south bay much which is probably my own fault but um very busy at work and things uh uh next year will be my eighth year in the scholar community um i've been around for kind of a long time now and i worked on a lot of different projects uh was one of the first five committees to aca wrote a book about lyft did a bunch of other stuff and now i'm an architect of verizon i mainly work on very large distributed application verizon building uh infrastructure so um high speed and in internet communication inside data centers um massive monitoring we do billions of events a week through scholarly stream um very into functional programming it's myself renault b arson um stu o'connor cody allen lots of scholars you guys we like it we like functional programming we do a lot of that and uh tonight i'm going to be talking to you about something a little bit odd uh it's the enigma machine um so who knows what the enigma machine is okay good yeah right crowd so um today interestingly actually um is the 73rd anniversary of breaking the m4 kriegsmarine enigma so uh which is totally a serendipitous event but uh um uh that's kind of an interesting thing so uh for those who haven't seen it um uh this is an enigma machine so um enigma machine's kind of designed uh the problem is that the the commanders wanted to cipher their messages um between the central command and and the uh uh units out in the field so in this particular case the one i decided to implement was the one for the army and the and the uh the air force um plan for the creeks marine the navy was kind of complicated so um not that it would be difficult to implement it's just a kind of run out of time what would work and everything else um anyway so this is the creekman this is the uh uh the m3 enigma machine um and this is the lady who who broke it who was working at bletchley park 73 years ago today which i think is really really cool um so uh her name is mavis betty so um anyway so i'm just going to talk about the parts and then we'll talk about how they're implemented and you know how uh decided to implement this for pure functional programming then we can talk about monads and some other interesting stuff so the first part is decor bread which is this this part at the bottom of the machine and what it basically is is you have um um uh sort of given an a if a maps to z and if you give it a z then z a maps maps to a so um you basically just do two pronged uh plugs and you kind of plug one end at one end and plug it onto the other character and then you know you kind of got maximum of a maximum of 11 plugs and uh that would be how you would uh uh you would configure that part of the machine and they kind of mix those around and and so originally when the machine was originally devised in 1980 1918 it didn't have that that was actually added later by the germans during the war so second part which is the most interesting part uh are the rotors so they come in these uh kind of interesting interesting kind of group of three connection and they have as you can see on the left hand side uh also on the right hand side they have these pins and each pin is a part of a connector that connects to the next the next rotor and so you can see on on this part i don't know it's not very high resolution but this part right here um it's part of a turnover point so each rotor has this kind of sort of three vectors of change so one is one is the um the connectors and the connectors kind of rotate like on a bezel uh like next to the actual rotor and the positions of the rotor and then the second part is that turnover point so there's kind of these latches that are kind of latching down um as the machine is turning over um and that actually shifts the next one on so the furthest rotor is the fastest rotor and now that's rotating each time and then um the next one is rotating they sort of on a random depending on the configuration and then the next one uh is rotated again so you kind of end up that was how they kind of made it uh much more deterministic from well i guess from the allies perspective it wasn't the same so if you type uh you know h and then you type h again then you get different output so um it's a simple substitution cipher but it actually was um so next part is the reflector which is one of the main things that makes the whole machine work which is a bit on the end that's such a this part right here so if you imagine if you imagine the other diagram electrical signal comes in goes down to the reflector reflector then maps that so let's say that the output was like a k it will map like k to x and then push it back through the machine the opposite way um so you kind of get this like two-fold in cyphering like with one pass of the electrical current going you know out through the rotors out to a reflector and then you know back through again um so kind of logically um by the way i must say borrow most of these images from the cryptomuseum.com site which is an awesome site if you like cryptography um and i borrowed this one from aidan it's also a really great site of information about enigma and like several other cryptographic uh devices so this is basically the process that i was just outlining um which is kind of interesting if you consider this is all being done with like actual wires that connect actual things to other things so this is all all kind of uh you know it's pretty easy to implement its software but sort of the monolithic tasks would have had to down when they're actually first dividing this it's kind of incredible so um they're actually 158 quintillion possible options of outputs for any given thing given all the rotors uh all the possible configurations all the turnovers all the ways that they could be configured together and so that kind of gives the uh that give the germans a fairly fairly high degree of confidence um uh interestingly actually if anyone's read anything about the uh why actually got broken it was just the human factor that really kind of broke it because well they just they end up selling it was like salutations and kind of they would end up realizing that hey that we've seen this kind of this kind of writing before and stuff like that so it's kind of like the human fact that they really kind of broke in the end despite all these possible options um and despite the operators being told not to do that so i guess humans um and then so just from a key perspective if anyone's going to say aha but this is going to be like a key problem how do you do the key distribution so um the keys if you like are kind of like the configurations of the machines and what they would do is they would have this day sheet and then you would say so first part of your message you would say okay like day one i'm using day one which should then employ you know that day one would be transferred into clear so that would be the bit how receiving the message you would then look at your day sheet and then you would figure out how it was that your machine should actually be configured in this case you can see use the b reflector this wheel this wheel this wheel where the rings configure the grounds and then put all the plugs in and so on and they would typically do them with a month um yeah as i mentioned creeks marine vessels often had too because then they were submerged sometimes so they didn't get they didn't get didn't get messages so demo time if i can just pull this over here how do i get that over there let's just turn on my ring for a second okay good enough does everyone see that okay i guess okay it's okay all right so if i take uh hello so it translates it so if i give it something more this is a test test test as you can see that um oh actually i've got a bug there interesting well so um if i then give it uh let's see now get the test back what's that on this machine it is yes so um yeah so then it converts the output the uh the output text if i give it kp kphn again back uh gives me the input um so it's delimited by this kind of four character spacing and that was just the way they they they did messages so if i give if i give it a bunch of input um it will then translate and that's just the way that they display they displayed messages so um so interesting thing about this let's get rid of that uh how do i show my mirroring off okay powerpoint now seems to have gone away where has that gone to sorry powerpoint decides to disappear off the screen which is very inconvenient right now uh goddammit i really hate why they've done that like this why doesn't that work so let me just see if i can get my powerpoint back seems to have disappeared that probably teach me for not using keynote okay there we are right like all microsoft products that needed restarting so let's see all right let's just jump forward a second well that was totally not smooth so all right there we go so then when we start thinking about how we're going to design this obviously these actual electrical parts they um you know how are we going to implement them so we've got kind of four logical groups um uh plug board the reflector um i haven't included the um uh well the reflector is kind of a rotor but that's an implementation detail uh the rotors and then obviously the machine itself um so kind of thinking about all of this this is kind of like they're all just character character functions um apart from of course there are multiple parts of them so when i start to think about this and think about how they actually like things are typically implemented um i always try and break things down into the smallest unit of work and the smallest unit of of ref referentially transparent work um in this case they're all charged hr so we're kind of just composing functions now the tricky thing with the enigma is as i was mentioning there are these turnover points so it's kind of like this latch that's moving around with each wheel which kind of makes that's what makes it different every time um now interestingly so we've got some code we then start to model this just using case classes so we build an algebra for okay here's my rotor the properties of rope rotor you know what wiring does it have you know where is its ring configuration and what notches what notch is the turnover notch and what position am i currently on so evidently this will be this will allow us to have an immune representation of our enigma machine and allow us to basically compose a pipeline of functions that will execute one letter transformation um so this is actually how the whole program works when you actually encounter the uh adding exit of how to actually handle the state so this part uh this part is just that function transformation oh you know that that charter charter essentially so it's kind of like okay let's just execute one character as a shot and then this part is uh if you like the state management so what happens is um like mechanically which is why i kind of like this example because it's very mechanical the thing is actually happening like it rotates and then the electrical signal goes through so it kind of translates kind of nicely and so we just we get the current state in the machine and then we modify modify modify um and we'll talk about specifically what these do in a second um and then then we say okay given the new state of the machine like execute the function and just pass in uh pass in the given character so this is just regular function composition and this part is and it's being done in the context of a statement so um let's look at the implementation so what is the statement that so um who doesn't know what a monad is nope okay one person okay one person being honest with us so that's good sir um uh my original version of this slide had a bunch of i was like who knows what monad is a bunch of algebra and then uh they're the monad laws but then i feel that would kind of be like anyway so so monad's uh on the basis that for the concept of for the sake of discussion everything with a map and a flat map is a monad obviously there are a set of laws that apply to and that's what scholarly scholars said does actually enforce that um for the sake of this discussion um estate mode addis is kind of like it's just a function given a state it will return you a new and an a so that's all there is to it and like many monads it's a it's just a very simple mechanism that can be used to provide very interesting higher level abstraction um so if we were going to implement this kind of like i mean the canonical example is a cache typically what people do is they have some var and then they like you know do something and then like write the var and then like you know then they give back some answer and then kind of got this hidden thing about the fact that var was updated or some cash was updated um you can make that referentially transparent by giving a cash doing some processing giving return cash and then whatever value it was you cared about which as it happens is exactly this now our state for enigma machine is actually machine it is actually that machine algorithm so if we were going to implement statement what would actually look like so um the implementation in scholarly if you're going to look at it is actually implemented in terms of a state statement transformer and the category of id um it's kind of if this is kind of new to you that's probably going to be a bit overwhelming so amplified and this is what essentially you have so you have a map you have flat map in order to allow to use four comprehensions then we have a run so given an s uh give us the s net the sa pair just like we were talking about and then modify which is given an s give me another s put some state as a side effect and then get the existing state um and then this part is kind of the magic which actually does the function application but um oh i say magic magic is wrong this just does regular function application there isn't it's just very obvious so if we're going to implement those map and flat map how would they look they would look exactly like this again simplified from the from the the version that's in scholarly uh only because there's some other magic in there about using functors and other things which for the sake of a small slide so i just implemented this and it this this this will work as as as needed um so like where is state mode ads so like i said statement is just it's simply threading your computation without you actually explicitly having to say so like all modes for those who haven't but have used other monads like future or option in the case of future the sort of context is the fact that it's an asynchronous computation that may fail um in the case of it's just something that may or may not be there and you're still doing you're extra executing a function on it in case you're just executing something else where the state is already present and you just you just never call out it's kind of implicitly carried around by the contextual use of this monadic device and that that's all it is um as i mentioned the actual implement uh in scholar z is more complicated and and so anyone that has worked with would be like aha this is gonna overflow because one of the things that this does do is this you end up with kind of layers and layers of recursion um and so anyone who's read rooney's paper stackless scala and stucco scholar and free free categories and things like that um uh you can just basically negate that and trade putting stuff on the stack for putting um quickly back to the heap and then you can avoid stack overflows by using state mode by simply saying my state is defined as a state t uh trampoline s of a and that is actually very uh uh very convenient um and that by the way um the trampoline is just trampoline a and it's a free function zero a so that is also just very simple um so um anyone who's looking at the previous slide say okay like well how exactly do these right middle and left things work because well that they seem to be the crux of the application no and so so that would indeed be right and that is the bit that is actually kind of given our state actually doing some applications you know actually doing some modification of that state so uh i'm using another kind of functional interest uh which is called lenses and um and so the actual program looks like this uh those right middle and left all they do is uh they bump on the next one or you know they step they step the rotor and they or they don't step the rotor depending on whether or not they are the you know the right middle or left rotor so probably looking at us thinking well what on earth is this thing because the rest of it i'm not really too sure what this magic operator does it's not a skull as the operator it's actually a monocle operator i'll talk about that in a minute um but lenses lenses are kind of this thing about i've got some valley and i want to read the valley and i want to the valley and i want to do so in a referentially transparent way um so someone who's used a case classes in skype you'll probably be familiar with copy um you know that's the obvious one works it great if you've got if you've got like one layer of adt then it will be fine uh nearly all domains that you care to work in other in any way interesting typically have like nests of those or with a tree of kind of domain objects like you know the economical players i've got a person who's got an address and the address has like you know all this kind of stuff and you get like multiple layers of kind of you know product types and it's not that useful really it becomes very noisy very quickly so lens to the rescue essentially rather than doing something like this in my case not the end of the world because i've only got two layers but you know i i we can definitely do better we can make these updates more compositional so we say no to this and instead again massively simplifying concept of a lens but this is this is i'm doing this as a vehicle to kind of explain i can have the implementation and the use all in one slide and it's it's it's very straightforward there's no magic here it's a simple function application wrapped up in a useful kind of way so lens just takes an egg given an a and a b uh they get give me an a i'll tell you the b so essentially like if i've got case class personal and i want to operate on the age then i'll you know underscore.h kind of thing so and the setting is obviously the universe give me a new age and i'll give you a new person with that age um or in this case as you can see uh the rotor what position are we interested in because we're stepping around each time we're actually incrementing that incrementing that ro for for example the furthest row to right is implementing its position every single time so we just copy that and we say okay position this is a simplification of course but so lenses essentially they allow to build modular functions to compose updates of various boy any type of domain type so scholars either ship with a lens it's kind of grown in complexity over time it was very simple it did used to just fit in one scala file now it's like a whole set of scholar files and different things and you know i mean and that just kind of it it's it's nice and it works but it's it's a little bit boilerplate because you end up having to kind of define all these things for every single type you you wanted you want to use and it just it's not that nice so so um some enterprising young soul has come along and made this library called monocle and so monocle is um basically just removing the boilerplate of operating with lenses by using macros and so rather than you having to say i want a lens for this particular field this is how i'm going to do the gang this is i'm going to do the saying so if you have any kind of product or any kind of class that case class for example that's the typical one that people want to use say hey give me a lenser for this case class and then it will figure out and you say and then you can optionally say later like i want these fields and it will figure out which what things need to be generated for that so it's just essentially a macro based cogeneration step that's you know okay code generation but it's a phase of the compiler so you know this is uh you know it's essentially code generation but just code generation you just never see so um it's really great i got to say like like this this library is actually really really great so let's look at what that actually looks like so this is all lenses for the whole thing being used in this enigma machine and then i can say given a machine i can say pipe dash arrow and which rotor do i need or which other lens do i need to operate on so then i can say okay i can have this kind of generic thing that even any lens knows how to operate on any rotor and then i just need to pass in a lens for the actual rotor i care to work on so then i can just kind of plug and play this whole thing uh you know without actually ever having to that kind of gnarly kind of nested okay i need this read the value and then actually having to reference the properties i can just pass in the right length it would do the right operation uh you know modification of the current position of whichever lens i need um there's some really kind of non-trivial stuff in in monocle if anyone's kind of interested in looking at it it is a it is a fascinating library and it allows you to do lots of other interesting things so um in fact actually all the type level.org projects that are really really awesome so um anyway just blowing through a bunch of stuff i know we only had like 30 minutes so um it's okay roundup um i think the thing for me like even as i mentioned at the start even though this is a toy application we actually build our large production systems like this it's not it's not like this is just some kind of like arbitrary thing that doesn't really work in the real world and it's great for kind of like academic curiosities we build large distributed systems like this by breaking our systems down into small referentially transparent pure functions and we model everything like that and it works perfectly and it actually is very easy to maintain so i like it because you know i always like say it gives you this frame to reason about problems in a very simple and straightforward manner and it just it's just not it's very unambiguous because it's very explicit um so statement gives you explicit immutable control over state changes um i really like it i think it's a fun little data structure um i think of other great things in scholarly so again if you're not uh if you're not all using e validation uh scholarly dot just junction or dot uh backwards slash word slash otherwise known as disjunction as a great data structure much more powerful than the scala dot either yeah i could talk about that stuff for days i think that's really really great um lenses makeup thing nested nested domain types convenient and composable uh composition is kind of the running theme here um things that are highly reusable because they're compositional are far more effective than things than than subtyping and all that kind of just just ghetto of sub programming just is really not awesome so focusing on behavior and kind of functions that delivered certain types of behavior it's a much more relatable path of building large systems um and finally like i said you know i just couldn't believe this is like the 73rd year of breaking enigma so i think it was an incredible piece of engineering electrical engineering in 1918 so yeah that's probably awesome so code is all on github um if anyone's interested in talking about it or wants to talk about anything else to do with scholarly or type level i would happily talk about it and uh with that i think i will retreat to my batcave and uh yeah happy to take any questions if anyone has them thank you very much the what mm-hmm does anyone have any questions yep using shapeless heavily at work oh that's a good question um so monocle is actually relying on shapeless it does actually use isos under the hood um so what's the difference one is built on top of the probably be the answer um i haven't used lens and shapeless men using the h list like everyone else in in shape everyone else using shapeless primarily using it for its h lists um h lists and iso that's the main thing i'm using shapeless for so i can't comment directly on on shapeless's lens implementation um other because primarily the main thing that's useful about monocle is just the fact that it has that macro support so it just kind of makes it much less boilerplate uh because of the macro support that's probably the only benefit but um um the implementations as i said it's like it's a pair of functions so there's not really too much there's not too much to move if you i mean would you mind so basically we go right middle left and um because of the way it works so basically we modify the state the state is only modified with sort of one of the curious things about an enigma is because it only only it modifies the positions and then it will pass the current through so the current goes all the way in and it goes to the reflector and then it comes all the way back so um that's kind of what you end up with here you kind of pass it through the plug board and pass it through you know the in the rotors right to left and then put it through the reflector transform it and then go left to right and then go back through the plug board and then uh so just apply that whole kind of function which is kind of backwards for how we typically think about imperative programs um you know and i guess that was kind of why i was kind of enjoying this because i think it's a i think it's an interesting thing like if you totally ignore this this program still this is like another program like all we're doing is we're building a program from smaller programs and that's basically the way to build large distributed systems programs of programs of programs and they just all composed together and that really just works really nicely let's see oh c is an input character yeah sorry that would the death was missing from here yeah but yeah all that is just it's just it's called def run and then just takes one argument which is a character but actually let me pull the code up that'll actually be easier to see but the um just pull this over here uh enigma uh there you go oh there we go okay so machine yeah so um this is actually the kind of neat bit i don't know if you can see this it's bigger yeah so this bit this bit is the kind of interesting curiosity so um this is the program um and then all i've done is uh in order to do multiples actually this i should have put on the slides actually um so yeah thank you for asking because when you use it you actually want to give it like multiple characters so um you just say okay i'll just take like any number of characters convert it to a vector um and then a map over it basically just to make sure they're all uppercase because the way the mapping works we only deal with uppercase letters um and then we filter it make sure that it's actually like it wasn't kind of like a like period or some other space or something that's not actually an a to z letter and then this is the interesting thing which is traverse you run um which is just if you've never seen that before it's just the mind-bending piece of unapplied magic in scholarship but this this part uh bottom part is basically just so eval i should just finish mentioning those so just turn it group it to a string like i said that's just a curiosity of the formatting and then eval is basically that when we were talking about given that s s give me an s and i'll give you an sa pair this is basically just the application of that which is give me the s which in this case is a machine so if we scroll up we can say run yeah so run is the one which actually gives you this state machine state machine char and then just the program and so all that thing is is just it's basically saying okay like um if you've ever used future.traverse or anything like that traverse you and traverse in scholars e are basically just generified forms of that for any for any traversable uh or any structure that has a traversable can use traverse and traverse you oh well it's for traverse you you need an apply but that's a implementation detail um but yeah so then basically all we do is we build up kind of like sort of vector of multiple states and then we just reduce them and that and and then we just rut so basically kind of under the hood they all get flat mapped together and then you just run them because you've got what you've got one of them as opposed to the list of them so it's kind of like just like future.traverse but it's just a generic version of that machine the case class that's right so machine uh uh yep machine is this one so does that mean that for every that every character that's because there's a new state that comes out of that one character then it affects what character is producing that that that's right so you're basically um so the next question from someone would probably be obviously isn't that a lot of allocation and in this particular case yeah i'm not trying to optimize anything like that but yeah it there is in every single time where machine is kind of like the position will become let's say we start in aaa position it'll be like a b c d kind of you know for each rotor kind of thing so each rotor is just having it it's it's uh it's position incremented each time so that that in the case of the uh uh the right most rotor it'll be a b c so each machine kind of each copy each step each character that's input it's kind of moving that position forward every single time does that answer your question okay perfect do you have any other questions all right thank you very much you