Live-Coding Rust: Building a Generic Breadth-First Search

[00:00:03][Music] hi first of all we would like to say sorry for a considerable delay in the release of this video and this episode obviously part of it was that we perhaps wanted to be considerate about the situation with uh in russian invasion of ukraine and on the other hand we also were a little bit busy most of us were helping our friends and acquaintances in ukraine and some of us even people we we didn't really know before the uh this horrible continuation of of this war um and um i also would like to say that uh um we will keep releasing podcasts and episodes moving forward and while they are normally aware rather cheerful uh we hope that we will not be uh appearing uh tone deaf and uh even though it's always a huge privilege and always pure joy to to to talk to people uh for me and to interview people who accomplished way more than me i hope that i personally and our guests will find a way to you know to appear appropriate in this horrible times also this episode was filmed before at the start of the full-blown russian invasion and the new phase of war in ukraine so it might look a little bit inappropriately cheerful but perhaps someone even needs something cheerful in their lives these days and the last thing i want to say is that team graciously gifted us five codes that we can give away to our listeners and viewers and i would like for this giveaway to be meaningful so please in the comments uh to the youtube video write as a learner of rust what is your experience with learning what was easy for you and what was difficult and perhaps something some concrete thing you struggled with just like i struggled with uh you know search algorithms and uh three traversals and the rest perhaps you will have you will have something similar and we will pick five random entries and send you the codes for the free rust in action ebook which i mean it has praise all over the internet but i want to insert my two cents it's uh uh perhaps the best perhaps the best hands-on material to to learn rust without prior experience and let's say systems programming uh other low-level programming approaches and even though i personally had some um this book really helped me with uh kind of the other half of learning rust which is uh you know borrow semantics and how to kind of be pragmatic about um about dealing and living with with borrow checker so for me it was really and every time i open it i see something new every time i open it i find something to ponder on to ponder about and consider so yeah i guess that's it see you soon with new episodes and yeah comment below and i hope you will have peace in your life welcome back to the functional features today we're joined by tim mcnamara a rust evangelist a data scientist and well author of books that are residing on the bookshelves of uh many rust neofits and advanced users alike and uh well hopefully i know i am they are also putting those books to good use and actually learning rust so uh yeah hi tim thanks for coming to our show hey thank you so much it's a that was a very warm introduction i uh have been very surprised is the wrong word so thrilled whenever i see someone saying something like ah i read your book and i learn a lot and you know when you when you write these things or you spend hours and hours and hours uh in a project like this it's very difficult to imagine what things will be like once it is complete uh and no it's been it's been amazing to see uh how how well it it has been received right well we'll touch on the subject of writing uh of putting spoken word to to paper a little bit uh later uh but um yeah i guess uh uh let's start our our podcast with like probably the least conventional thing uh one can do in a podcast which is a live coding session so i don't know if you i don't know if you know but but uh in our podcast and the functional features podcast we have this kind of running gag that uh i personally don't know how to implement the breadth first search and rust um and uh yeah like there is literally no better way like no better way to to to kind of crush this meme and show that it's not all uh that's scary uh no better way than than by having you do that especially given that uh we know that you have a uh kind of prolific and pretty diverse youtube channel yourself with live coding sessions uh and you also post their like how-tos and tutorials as far as understanding yeah um well yeah i i hope that this works because the problem with doing things live is that things don't always work uh however i'm up for the challenge i think that it will uh i'm i'm sure it will be interesting to see whether or not i can explain things in audio while coding uh with you asking me questions at the same time but um [Music] let's let's find out i think i think it's an interesting challenge as well because graph algorithms stress or make graph graph algorithms actually uh the hardest to implement in rust because of its ownership rules yeah i guess i guess i can i can give you a little bit of uh typing typing space and i'll try my best to to kind of articulate what you what you meant there is that uh yeah this is something that i personally struggled with a lot because like i couldn't implement breadth first search like in rust not for the lack of trying right like i tried like three or four different attempts and uh like my fourth attempt i guess was just full of like rc's and like uh like reference counted uh you know memory chunks and uh and that the big issue for me was how to actually uh kind of unify this this like dihotomy between me wanting to um you know traverse a graph and uh uh perhaps like uh get like kind of wire the reference to that graph uh from one like level of recursion to another level of recursion and at the same time complying with ownership rules and as you mentioned sometimes like mutability also comes into play because i want to actually maybe do something meaningful yeah right and uh and just these three things for for a beginner they don't go well together okay so let's get yeah so let's let's just start with not really and we don't really understand our algorithm but we've created a a function here bfs that takes some graph in a start node now the question is what is it what representation do we want and i'm actually going to pick a trait because trait and traits enable us to model abstract data types quite nicely and one of the things that we will try to do is also create an associated type node now the compiler will eventually complain that i haven't done things correctly but uh in my function so we'll need to add some constraints to this but for now what i want to say is that a for a graph g we have a start node and the start variable's type is the associated type of graph right so these two types are somehow interlinked uh if i were to look on wikipedia say then i would kind of look and and and have a i require a cue one of the things about breath searching we're going and we're adding something to a queue and then we're going to explore it and if we've seen that node continue uh skip it and if we haven't add things to a queue so the next that we need to start with the queue so i'll use uh i think it's in standard collections so it's std collections there's this thing called a vic deck which is a double ended queue sorry and which is backed by a vector so it's growable it shrinks and expands now we haven't actually explicitly said which type we are going to hold inside our cue we're going to allow type reference to do this but in a sense you could imagine that its nodes will be of type graph node where graph node is the associated type now i also need a some data structure which will hold nodes that i've already seen and so i'm going to use a set for that and it's also in the standard collections module i've got a hash set data type now a hash set uh a hash set is requires a hash function i need to be able to actually constrain the type of node visited will include nodes and i want to add a couple of constraints one is i need the node to be able to be hashed otherwise it can't fit inside a hash a hash set i also want that my node type to implement equality otherwise i can't check whether or not i've already visited it so the equality trait will require that uh will enable me to be able to check whether or not some node that i'm visiting is exactly the same node that uh i've i've got an and i also want to do something sneaky some people may think this is cheap i i think it's useful i want my nodes to be implement to implement clone clone by the way implies copy uh clone and copy are a uh are two traits which which enable a type to copy itself unlike java for example the clone operation always works and it's it's well defined and now my queue and my visited variables can do things with nodes there will be one more change to graph that i need to make and it relates to this ownership or borrowing concept that we've touched on a few times i've got a loop where every iteration i'm popping something or from the front of the queue and now i want to be able to see and so the node variable inside this loop is the item that is at the front now normally when you are searching there's a target node so we can but in this case we actually have got no way of describing our goal and so we could say if we or just add a comment that if we have found our goal return here but in this implementation it doesn't actually matter we'll just traverse the entire graph yeah that's obviously good enough okay right now for every uh so the next step is for the other nodes and let's say actually i'll change this other to something that's a little more concrete neighbor and node edges let's say this is where people often get stuck when they write rust in this case in my function that i've in the code that i've just written i've got the node type and i have called a method out nodes or it's like what are my neighbors what am i connected to return those rust will complain a lot about this because if you because of the way that references work if you were to consider some type of data structure node that knows about its own nodes its own neighbors and has references to those then you create a chain of references all the way through the entire graph and the borrowing system will require that some nodes own other nodes and that won't really work because they sort of no no particular node of a graph owns the other nodes and so uh they all live and die at the same time so we actually need to change our function well we need to change um how we do this we need to say that the graph itself can uh describe the neighbors for of any given node and then and and this certainty and this this situation is also very obvious for example in doubly linked lists it's like the perfect example of what team is talking about because then literally no single for no single element you can't say okay like which element owns which of its neighbors right because like if element a owns neighbor to the right then uh you know like then eventually you will loop and you will get kind of contradictions absolutely absolutely and this is a problem because uh yeah that's a complete problem because rust's uh compiler will check will say this is an impos this is um it's sort of infinitely recursive uh and therefore i cannot i cannot it's undecidable um and it's sort of an impossible um thing to check and with and with doubly linked list you will use the same trick right you will create like an extra kind of entity and then you will delegate all the ownership to it yeah yeah yeah so in the case of say something like that you will have a often you will have a a list struct or some list type and it will have elements for example or nodes and uh you can think of the the list as kind of a manager um perhaps or something and it owns all of its um nodes in the list now one of the things that needs to change in my is the graph trait so we are relying that this graph object has a neighbors method now uh so i need to actually encode that in the type system so i define a function neighbors that takes a reference to self and a node in a reference to a particular node and returns some list or some vector of self node now this will just the way that the uh type system works is that this is an abstract the trait is abstract and so we actually don't need an implementation but the compiler will still be able to reason about this for any given implementation uh okay right so yeah but by the way uh just for the listeners i want to say that uh basically what team typed out right now is was essentially something resembling uh if you know goal for example a receiver function or receiver method i don't quite remember how they are called there where basically it takes uh as a first kind of argument quote unquote well literally argument that takes a reference to to some object some structure some thing right and then uh you know you can call it with like dot notation you can write like gra your graph dot neighbors and then you give a reference to a node there as as the only argument as the only kind of visible argument of this of this function then and what is interesting for me as a beginner in rust is that team used um notation of ampersand capital self colon colon node when talking about the uh the node argument for this abstract neighbors function so this is something that well it clearly refers to like my question is i guess why didn't you write graph colon column node instead of ah yeah south column column that is a uh so cell yeah so that's a very good question and i think it's mostly related to aesthetics so i could have definitely said that uh my neighbor's method takes its nodes are of graph node uh this will still work but the capital cell capital s self rel is as a type variable that relates to the type that the uh object uh is and it appears in a few places so with inside a trait definition one reason why you might wish to do it is because it enables you to change the type of the trait so instead of saying graph you might say yeah you might oh man yeah so we can we can change the we can refactor the name of our trait very without affecting the signatures of any of its methods uh yeah but maybe maybe also like again like kind of intuitively perhaps it's wrong maybe uh but like maybe if you just left graph there then it would allow me as a pro as a user of your code to actually uh take a type one type that is a graph like that implements graph and then actually trick it into accepting another type that implements graph or it would be i think it would be possible right i'm not sure like if we would left graph instead of self uh in the type definition yeah you can i have confused myself before doing something similar and i don't know if this is what you um what you're saying but one of the things that i did um what i've done before is create a struct node and in one of these arguments uh i i had both um the concrete type node which was which was a and also i was referring to the associated type uh node inside the graph and that that that caused some problems uh however yes you could potentially if you sorry excuse me you can uh let's say that you wanted to have an arbitrary node type uh i'm going to just we can actually insert a type variable and for some reason i said i'm going to give it the type variable v for as vertex because we've used the the term node several times already and then i might say that this requires hash equality and clone and so for anyone if you're only on listening on audio i've just replaced the the associated type with a a generic and this is possible too it makes it a little bit more complicated to uh to call i think um but the and there is a good reason why sometimes you use associated types and sometimes use generics but um i'm forgetting it right now but um so so neighbors accepts a uh a reference to some node type which is um which implements hash equality and clone and returns a vector of the same now the difference with uh the problem that you might encounter if you use if you define graph like this is that there is no guarantee that you can that the type system cannot guarantee that the nodes that are being received or returned relate to the graph itself so you could trick it into accepting the wrong type of graph sorry the wrong type of node whereas with an associated type the type system itself the compiler will actually say no you can't give me a node from some other graph like that or some other type uh i actually require the type that you've uh that's been defined for you and so yeah that's your writing implementation of currently perhaps now this is actually something i was like almost sure about that this is what the the nature of the question i tried to ask was was that that that the way you wrote it in the first place with like capital self is actually kind of the most type safe way to to approach it because then you constrained like what can and can't be done sorry for derailing it a little bit into like the matters of type safety no no no it's perfect and i mean the uh i i enjoy having to think anyway uh it's actually really interesting that because i the notion of type safety and the value of a type system is something that i never appreciated until i started programming in rust so i see rust as the kind of this middle ground between haskell and let's say java or c-sharp or something i was a python programmer beforehand and i did not care about type safety at all um and i did not understand why i needed a compiler even but after using it i've just become so reliant on the guarantees that are provided by a strong type system that i find it really difficult to go back to other languages now ah okay so we're back inside our breadth first search now we've gone for every neighbor in the neighbors of the node if we've already seen it and visited sorry if visited contains neighbor then we skip to the next neighbor that is if we've already seen the node that uh we might want to check we don't need to do that because we've already done it and the next thing we'll add is we'll visit or insert neighbor because we actually would rather not visit neighbours twice or an infinite number of times and the other thing that we need to do is our q we need to enqueue flavor now do you remember right at the start i said that i was cheating a little bit one of the things that i see it is that i required the clone trait and so i've got two functions two methods here one says q in queue neighbor which says please add my neighbor to the queue of things that i wish to search and also insert neighbor into the visitor set the visited set uh actually that's wrong uh i need to in the node i think yeah i need to i need to insert visited uh the node into visited otherwise i will uh that is brett first search implemented i believe yeah and we will we will traverse towards the entire thing now uh yeah i wonder i wonder if um uh rust will uh if rust compiler will uh agree with us about it uh so no you want me to implement on a concrete type okay let's try so now the question is okay tim uh prove it to me and i know okay so i want to um some struct the uh okay so now i actually need to do this right so one of the things that i need to do is i want to have a structure and i'm going to call this let's say let's say a amaze this was actually first implemented by conrad zussa i believe um uh in in the late world war ii um but it was related to um so to to to path searching so it anyway uh or like the the law of left hand or something yeah like uh he like how you can how he can traverse a maze yeah yeah by just touching the left wall or something yes yeah yeah so this is a one of the ways to be able to search through a mace well in in fact um arbitrarily you should be able to find any a root if if two nodes are connected in the graph breadth first search is guaranteed to find them it's not the fastest way to do so and in many ways especially if you have many branches is a very slow way to find defined paths between two nodes but it has the advantage that if your graph is of infinite size it will complete whereas depth first search has a problem and that is if your if your graph is actually infinite uh it will actually never complete it may never find the connection it will always get stuck and so in practice depth first search often has extra termination rules that don't don't really apply in the theoretical computer science case anyway so we've got our maze and i'm just going to say at the moment that it has nothing inside it and so we are going to do something which is going to look a bit strange we need to implement graph for maze uh and and i'm going to do it in a way which is probably going to make you both or anyone listening kind of angry with me well maybe not which is to say that to so i need to have my type node and we'll just say it's an i32 because that's a nice um uh we could even say that if it's a xy coordinate it could be a tuple of two numbers but and that will work as well uh now i need to implement neighbors for graph um and so let me just check what it is it takes a node and it returns a vector of notes okay so [Music] by the way this is another another reason for uh using type systems right because like uh you're stressed that's right some guy asked you to like life code in front of live audience yeah absolutely if it was if it was like javascript you could have forgotten by now what neighbors are absolutely but like this absolutely absolutely so this is uh i32 a32 now we could have uh created a a uh a type alias for this tuple type and but um and i think that when we return a vector of 32. i i think by the way if it's not obvious to anyone this is actually real so i don't actually have a demo of i'm not i'm not copying this from anywhere i'm actually it's genuinely live so uh i've got let's say this is x and y and uh actually i'm going to add a bounce and i'm going to say that minus 10 and then plus 10.

[00:32:32]so inside the this is a silly place for ah it is a silly place but actually um uh so actually i'll change my maze definition to have like a bound and i'll just say that it's 10 by 10. it's a 10 by 10 matrix um [Music] now and i've got an x and a y x is node zero i just want to double check one thing that yes it is okay good uh i've got the right variable name okay no dot zero and my y is node one so i'm actually accessing the fields of the uh i can do this i think in a way that's slightly more um i'm accessing the fields of the tuple the node argument and assigning them to local variables now i want to be able to create some vector of neighbors and um i'm just going to give it the variable name others so that it doesn't look exactly the same as the uh the method name itself and we don't get muddled up and at the end of the function i'm going to end of the method i'm going to return others as well so if x is uh greater than zero and just say there's an implied bounds for zero it's a silly thing to do i should have x bounds and y bounds um but but we don't then i want to add a uh others push and i've got x plus one oh no no no no no no no wait wait wait wait x minus 1 and then a and this is also an end and x is greater oh sorry less than or self dot bounds zero and then y is the same now not i don't think i should do the entire graph because this will get boring very very quickly uh but you can sort of see that we're building up a list of neighbors and we are maintaining very little internal state so if y is greater than zero and y is less than southbound one yeah this point about the internal state is actually very cool because you know often it's tempting to um kind of dump as much data as possible in a struct but which is like i think is a i mean again i'm not i'm not a rust expert but i think it's a perfectly kind of reasonable thing to do uh in some cases right but here what is really great about the code the team is writing is that uh well first of all uh it's uh it's generic enough to do some pretty crazy uh stuff with mazes which is uh over my head but uh on on another on another hand right it's like the fighter team is encoding a lot of a lot of stuff in computations rather than dumping a lot of data in the structures it kind of uh in as far as i can tell helps him to kind of sidestep the a lot of issues of uh that can that you can get into when trying to prove to russia is that your that your code makes sense in terms of uh ownership and borrow rules now i want to do one oh thank you so much um by the way i want to do one other thing which is we're going to add a side effect inside our uh our dfs um uh implementation is that we're going to print out our current position now in order to do so i actually need to add another constraint to so this way it will actually do something interesting when i run the breadth first search otherwise it's just as completely um it's it's actually not very interesting so i need to be able to ask that our node can implement standard format display this is not part of the core algorithm but hopefully we can actually see something um when i and it also brings us to to a rather interesting point which is that in in in in rust as opposed to haskell where in high school we just have show type class right and and something is either show like showable or not whereas in rust we they well we they i don't know yet uh in rust they actually have two type classes or two traits i guess for that one is uh display that tim just mentioned and that is debug and you can actually encode different behaviors for your uh it's like a little it's a small thing right but you can but it's very powerful because you can now uh encode completely different printing mechanisms for stuff that you want to actually you know display like in production versus something that you just want to look at as a developer while developing your system absolutely so the really interesting uh um yeah so just to explain that distinction the display trait is intended for end users well at least it's certain so you can use this to be able to uh implement logging for example or actually not so much logging but just uh just output that is designed to be intended for people outside of the developer team whereas the debug trait is intended for people who are writing the software to be able to inspect their own code and so uh i've requested that my node type implements display because i want end users to be able to see the progress of my nodes going through the now that isn't necessarily i mean in some sense it's somewhat arbitrary but uh but let's let's i think now i haven't actually we haven't actually compiled this um so we haven't even saved it to the desk i am curious as to whether or not i'm going hopefully i don't look like a complete idiot here uh so if i run bit oh we have to yeah sorry about a second of nick's uh yeah that's right we have to yeah we're in different shells right now so we need to do this okay so rusty i'm i'm in a dfs oh no we're actually breadth first um ah goodness me okay so we've got a couple of type errors so the uh first thing that i need to be able to do is i'm just checking okay so in this ah okay nope oops i'll oh yes please i was sorry i i've got a um yeah if you could get us back into the right place okay so what has happened okay the first thing is that um russ is very confused because i have implemented uh i've i've asked rust to define a function bfs that takes a graph object or something that [Music] but graph is not a concrete type it is i need something which implements graph uh now uh i think this will i think can we try this one uh this should get us somewhere if i uh should is it controlled i'll just click control control that's right yeah yeah yeah [Music] okay so we've got one of the ah and so i've actually got the wrong so i've got a okay good i can yeah yeah we also need to i think uh import hash yeah that's right so what is a hashtag well we've actually explained this so a trait is an abstract you can think of it if as a type class from haskell or if you're from sort of a java background it would look a lot like a an interface or an abstract based class rust traits are a little bit more powerful than um than interfaces in java but one of the things that that you're required to do is bring them into local scope otherwise um which kind of means that so now we'll write again okay so i'll run it yeah uh semicolon okay we need to change the thing uh okay i think that um yeah so the the interesting bit is how to tell it that it's the same graph i understand yeah that's right that's correct so go um okay i've got an extra semicolon somewhere in line 36 and i'll get rid of some easy things uh just on the struct and down here it's not davis it's bfs and i bet i bet that are that our sound engineers are already excited about like editing for the podcast yeah yeah tim don't worry we have we have people who are like who love me so much right now uh but yeah don't worry we'll we'll figure out how to edit this stuff yeah i apologize for this um it's quite yeah oh no it's i mean but but but to be honest like it's so much better than than not having these compiler errors right if it would just run and then spit out random stuff we would we would be here till tomorrow absolutely yeah now i uh this is actually i don't uh so the problem that we've got is that we want to implement graph uh i think this is right although yeah yeah i i yeah i think i think that's uh the problem that we have is that our start variable or is of the of of of an associated type relating to graph but the inference algorithm gets a little bit confused um if we i think this isn't the right way to say i think should shouldn't we just say so basically what tim just did he wrote that he wrote that the bfs function is parametric in uh type g which he said should be of trait graph implement trait graph uh but can't we just use g everywhere now can we just write like g is of type g and like this is a type g node or what's the problem yeah okay so the difficulty becomes so like why can't we use g uh common column node uh the problem is that okay so the trite the the the uh g is a concrete type which implements graph uh however the and and yes i think that we [Music] so this one here could just be so are you saying that i think that's kind of just g this one yeah so instead of so yeah so instead of impul graph uh like so this is no longer dynamic dispatch it's statically dispatching on so it on the concrete type that implements graph and then the g graph actually i'm interested i i've actually found i'm a little bit confused um i'm struggling to remember exactly whether or not this uh is legal syntax but um we can try this so what i've done now is replace the trait object which is called a trade object it's just a you know about the way that functions are or dynamic dispatches oh this is good actually because it's very good we have yeah we have completely different errors yeah so the uh uh okay this and q by the way and q and q is like pop front i think or oh sorry push sorry push yeah they have push front push back back yeah yeah and maybe this is actually something that confuses my mom a lot when when she sees me programming or she used to see me programming when we were living in the same place uh i would like i would have errors right and then i would get more errors and i would be like yay and my mom would be like well that's this is these were errors right and now you have like even more errors why are you so happy and i'm like these are different errors yeah which means that we've fixed the problem that we wanted to start with that we had originally so the enqueue method becomes push front and the other one so we can save that and then there we had it's also complaining about stuff like inserting uh like uh a thing versus like inserting a thing versus inserting a reference ah yes okay um i want to change one other do you remember when we talked about display versus debug i'm going to change things around and implement debug because it's simpler i mean it's implemented by more traits and in particular the uh the tuple trait that i've defined for node has um it automatically defines uh it's already made it the compiler will implement debug on our behalf so this oh sorry no no carry on yeah if you compile now we should just have the reference errors okay let me scroll about yeah so that we've got a couple yeah so we just have the reference errors here okay so that should be um the problem that we've got is uh we our inside our implementation of neighbors we've taken we've taken a reference to [Music] node and so our variables x and y are actually references to are actually references to some [Music] to some numbers that exist so i wonder if i dereference node right at the top then all of uh all of these things should yeah great okay we compile good cool so oh wow that was that was really really cool because you know whenever i have this sort of issues i go like oh i will clone a bunch of things i'm very sc i don't know why but i'm like very scared of like the referencing ah this this is a silly place for me to start may i i should just change that all of my tests only add neighbors if i'm above zero so i need to change the starting position i've that's why probably uh actually i should just say that if i am below bounds but um i'm only going down so i'm going to start at at five five let's say well five eight just to be interesting uh all right oops we need to compile it first okay you you do the okay hey oh okay so we traversed the graph that's so cool um yeah uh so that is a brit first search implemented in rust wow that was that was honestly yeah i imagined a lot of things i imagined you know like that exceeded my expectations for one reason because i thought that you you'll you'll be like kind of boring and we'll see we'll say you know like we have limited amount of time so let's just you know get some concrete uh type some con concrete adjacency graph and then traverse it but actually this is this is beautiful thank you so much tim honestly it's yeah we uh yeah thanks um i guess we can we can go to the to the interview part and by the way uh we will put no you should go to do you need to go to sleep i imagine i mean let's just go really briefly for some questions uh and uh of course we have uh questions from the audience this is like maybe even the most important thing um but yeah i just wanted to say that uh that yeah this code will be available in in teams on teams github or somewhere we will uh yeah we will make sure that you can all enjoy it because yeah honestly it was it was really cool right um yeah uh let me turn on my camera hello everyone and let's go through some questions i mean um i would actually like i have there's not going to be a lot of questions but uh one thing that i noticed that we talked about while you were implementing this stuff is how there are some tricks right um kind of um like kind of you could even say patterns right like for example the the stuff that we talked about when you don't know uh when you don't know who will own the thing like we introduced like a kind of as you called it manager uh entity that would own then you know uh everything um in the structure so and you know in general when i was like uh in the beginning of my career when i was just learning programming you know programming patterns were like the hot thing like everyone was talking everyone was drawing like uml diagrams also you know all this other stuff and as i kind of moved to functional programming all of this stuff reduced no no pun intended so do you think so do you think what is your take on like uh programming patterns with rust do you think yeah so yeah so and in general so i think that there is a place for patterns in the way insofar as saying that we as a programming profession let's say or as people but because we work in teams we need to be able to write code that others in three months or three years time are able to understand like it's very difficult to write code that is readable by others it's actually and so the benefit of patterns is to be able to in some sense create a common vocabulary in the programming community about you know things like iterators for example it's so commonplace to have types that actually know how to iterate over some collection that many languages uh no longer actually require you to implement an iterator uh and so that's useful i think it's but like everything there it's detrimental in some other senses because if your problem does not fit the pattern you find that actually you've sort of painted yourself into a corner of a room i don't know if you've ever tried painting a house or paint or like no actually cleaning you know if you're mopping the floor that's a better analogy if you you know and you and you kind of clean and then you get to the the corner and it's like well i'm now stuck because i'm trying to implement a pattern uh that's that's when it becomes a problem or if you uh i think there's a level of uh there's a [Music] there is a i'm trying to figure out how to describe this one issue that you will encounter as you become more proficient in rust or in a language that respects or like has a robust type system you will have a tendency to over abstract or to create very elegant uh and very uh things that will these abstractions which are uh in some sense very nice but actually they obscure your intent at least that's my unders that's that's my experience that um i think when you begin programming everything is very it's all concrete types it's all kind of simple so you then learn some more skills and you pick up bigger problems but then your tendency is to uh always reach for these very very complex systems and then advanced programmers will come sort of the swing back to simpler methods and um i think patterns are very useful for people for for teams and for people who are learning how to program but it's also important to remember that they are not uh rules or the intended is not to restrict you but actually to kind of provide you with more flexibility right right and well you wrote by now two books on rust right uh uh or or well no or more no no no no no well i've i've got rust in action okay oh yeah uh but the uh that's the only book the the full book that i've written um right um but there is actually another one but i'm we're still it's it's not yeah so it's it's not uh completely um public yet it's actually not public yet so uh but there's one coming so by the end of the year there'll be something else um as long as uh uh as long as my family i've i've got little kids i've got a career i need to be able to you know have a social life as well so we'll see yeah that's that's uh one of our most one of our biggest interviews was with sasha yurich and actually we were hanging out a lot as he was writing the book and he was saying that like for his first book it's it's the amount of time it took him like he underestimated it like by an order of magnitude yeah something about this i yeah it for me it will be close to an order of magnitude so it took me nearly five years no because it took for various reasons it was about a year before the project officially got started originally i was brought in by manning as a second author so there was a project that they had a russian action project uh 2015 i think but and that was already and but the the first order author actually pulled out so we were working together for a couple of months and then the first author kind of pulled away and then uh the publisher said do you want to karen carry on i said no we should write a better book like the the manuscript we've got so far is kind of rubbish um but then my own thing i had this idea that i wanted to write the best programming book that i had ever seen i wanted to convince myself that uh it's possible to write an excellent book and that the i had sort of noticed that the trend in technical publishing had been declining uh over a few years i think things that were published in like the late 90s were probably a lot better than things that were published in say 2012 or 2013 and uh i wanted to be able to write the a book that i would want to buy that's really difficult so the reason why uh books of quality has been declining and getting faster and faster is that it's it's simply hard it's really really hard so i spent i i would estimate between five and 10 hours a week over uh in fact you know 10 to 15 mostly so it was i tried to do two or three or four nights for two hours a night plus a uh some period in one of the weekend days which was about a three or four three to five hour period so that let's estimate roughly 10 hours a week for four years that's 2 000 hours like that's yeah uh and like the it doesn't stop it turns out that once you've written the book you then need people to like you need to advertise it otherwise they don't buy it and then it's useful it looks useless i um however wrestling action has done extremely well uh most technical books i sell fewer than say 5 000 copies over their entire lives i've sold i think about 20 000 copies in its first six months um the that's rust is growing wrestling action is a good book it's different than every other book um but uh yeah so hard to do it's actually really really hard so do you when you say that it's different well first of all it's really great to hear that um that uh you know you're making the return to the glorious books of 90s and the drawing inspiration from back then because yeah i remember like you know uh for example linux uh like a core linux uh reference by basically like reference manual and or c plus plus reference right those are references but those are well written narratively well written books as well at the same time it's just mind-blowing how good they were right um so that's great and uh also like maybe for for our viewers and listeners like uh do you do you emphasize in your book like kind of tricks and tips uh like kind of do you show do you add like to the explanation of what things are uh the explanation of how to go about like you know actually working with these things yeah so the um so i i want to answer your question i think in three ways so first of all the book is different primarily so it came out i i was starting it when the the official book by steve and carol steve klebnick and carol nichols um was nearly finished we hadn't published um i wanted something that was different than that book like there's no reason to spend money i mean out mine is not a free web book right so it needs something extra and i thought rust is being promoted as a systems programming language and so i want to teach people who had only used javascript or only used python or only used let's say java or c-sharp or anything else and they were looking at rust and saying i don't i'm scared of systems programming i'm scared of what i just i've heard that systems programming is hard and what i wanted to do was teach people enough of that so that they don't get intimidated by the jargon and so that's one of the ways that my book distinguishes itself the other thing is that we uh does it provide strategies well actually i think in chapter four it's uh devoted on like ownership and borrowing and i go through three different methods for resolving issues around ownership and borrowing for beginners i think one of the things that also makes me uh what's my book a little bit different it's kind of the third way is that i wrote it for myself i was a python programmer before i was a rust programmer i did natural language processing i wasn't even a real software engineer i was a data scientist i wrote python for being able to do text analysis and it was too slow and used too much memory and so i decided to start writing python extensions but if you read any any material on writing native extensions for python on the in c extensions for python there will often be a paragraph which is this is very dangerous you might crash your program if you you might introduce memory leaks you might do this you might do that you know effectively you'll crash your computer you'll introduce security holes and so rust provided me and i sort of see myself as like a uh russell provided me as like an everyday non-programmer like i'm not a professional scient professional computer scientist i don't not i have a humanities um degree uh i don't have a computer science degree from university and that's a bit of a that's a bit of a topic in our podcast actually like three of our previous guests including you are not trained in computer science sorry yeah yeah so uh i wanted a book for me and the and i was there are better rust programmers in the world than i am my book tries to my book was written for people who are still learning and i definitely still remember learning and i hope that i did not have kind of this expert blindness problem i think if i write if i read a book by someone who is a i find books that are written by professionals or people who are extremely good uh often very difficult to read because they have forgotten what it is like to learn there's so much there learning rust is more than a programming language it involves learning a lot of jargon it involves uh understanding some new concepts like ownership and borrowing for example when even and so there's almost multiple layers of learning that are required and my big message to people who are interested in this new interest this new high performance programming language is that they should take it slow and just learn things piece by piece and also that if they don't end up using rust actually they haven't lost out because uh you can apply a lot of the techno techniques in particular functional programming to other domains or other other programming languages as well right yeah uh absolutely yeah for sure and uh i mean if i would uh humbly could if i could humbly add something to your message when you said take it slow uh i would also suggest a complete beginners to also not be scared of uh like you know cloning your data or copying your data because if you think about it i had this huge problem that oh okay i'm writing rust it's kind of an imperative language and i must squeeze out every single bite of my like i must not even prematurely optimize but i must like everything that can be mutable must be mutable you know within like boundaries of a module let's say but it's actually false like you can clone so much and your rust programs will still be like 10 hundred times faster than your you know like php python java programs because you're like like no matter how much you even compiler optimizations aside no matter how much you will tell the rust to clone your stuff right you will not manage to clone your stuff as much as like let's say a virtual machine where you know you just copy and change everything pretty much so yeah don't be afraid of taking a slow uh you know in in practice and don't be afraid of like making it slow by cloning a bunch of things absolutely i mean the cloning where there's this idea that cloning is expensive or cloning is slow it takes 20 mil nanoseconds uh naughty you know you can fit hundreds of them inside a millisecond uh it is slow compared to uh compared to you know the for the cpu and the me yes it is slow compared to just kind of like copying data like but it's not slow from the point of view of your users or uh you as a programmer and they uh there is also plenty of time to learn more you know techniques that don't require clone but for now absolutely clone or two-string or two-owned like these methods are there for a reason and the reason is often that they're useful so use them yep yep and in general i mean sometimes people are scared of rust ergonomics but actually if you kind of take time to appreciate how many options you have as tim mentioned when you are writing grass programs to like write meaningful program reasonably quickly you will see that that ergonomics are there and in my opinion for example immutability by default is like just an ergonomic tool it kind of nudges you in the way like okay like don't worry about it just just you know create a bunch of stuff use it and you know it will be the memory will be freed you know by you know the film design so uh yeah uh i think those are good messages to to wrap it up and go to the uh questions from the audience uh but uh yeah i mean tim before we go to the questions is there anything you deeply care about that you'd like to advertise like maybe aside from your book because i i hope that will do pretty good uh job advertising your book uh i i would be very interested in learning uh how people and advertising maybe not i i would say would tell me about things that you're doing with rust and uh any problems that you're encountering um so i think i'd love to hear from you either i think the easiest way is probably twitter um and we'll probably have a link to my twitter account but the easiest way to find me is is through tim clicks t-i-m-c-l-i-c-k-s and i'm always very receptive to people's messages and yeah the other one would be the youtube channel so it's the same uh somebody it's youtube slash tim clicks or um and that will get to me there so you have similar things to me uh implementing uh search algorithms i haven't done yet but uh similar things um i have and i'm always interested in new ideas so please um send those through right well um and i actually also have something to advertise which is this podcast yes i mean we're we're making this podcast at least we're trying to make this podcast for every single listener and viewer and for example subscribing will give each of you a chance to engage with the guests in real time ask questions in youtube chat and also just as tim said about engaging with him also engage with us ask follow-up questions share your opinions in emails talk to us on twitter as well like we are all one big awesome community and i think that uh you know just maximizing uh the potential of of our kind of engagements is a very very good idea all right now let's go to questions from the audience we we don't have that much that many of them so um so and the the current questions i see they are related to the to the coding section one is are we making a path map it's i guess about the maze bit uh yeah so the we could i'm actually not sure what exactly what you mean by path path map i think yes we can create paths through we can actually use a dip first oh actually a different search algorithm called depth first search we can actually use to create a maze breadth first search will be able to traverse every node in the graph so it will be able to completely search for the entire thing that's what we've done so far and so the the only kind of strange thing that we've done in our implementation is not actually store the nodes themselves we just create them on the fly um as we kind of had like this kind of quote-unquote generator function and yeah it's it's it might look a little bit confusing i mean it was as you were writing it actually it was confusing but then it clicked when you when when i understood why you're doing these checks but yeah basically we just generated a bunch of stuff like on the fly and uh just as a demonstration that this stuff actually works and yeah and another question is actually very um interesting so the other question is is there no constraint kind in rust so i don't know if tim do you know what constraint kind is i have not used high kind of types myself i have i'm not a haskell programmer well i'll just provide i'll just provide context maybe also for the listeners for sure it could be useful so basically when you write out something like um i don't know like something like uh functor or whatever graph or or something right you would have like kind of a type variable and you would then insert this type variable in that uh constructor and you will get like okay and the and the kind of this uh kind of functor or or whatever that takes like something as like some type variable the kind would be asterisk into asterisk into constraints right right so this is so so it's not just asterisk to asterisk or at least not anymore i think that like 10 years ago it was disastrous to us but now haskell can actually say oh okay the result of applying this type to that type cons like to that thing that expects that has like a slot for type variable the result of applying this will be constrained so i guess the question is is there's a cert like is there a similar way is there even a reason a way to reason about i guess kinds in in uh not to the same extent and so rust's type system is not as sophisticated as haskell's tescos there have been discussions i've that higher kind of types will event there have been proposals made to uh to be able to do something similar in rust rust uh i i um the shortest answer would be no but you can do things that are similar with our with enums so we have some types in rust which just happens to i think use the wrong keyword enum and you can provide uh in some sense a form of restriction via some of those vari variants as well we haven't demonstrated that in the code that i've shown before but that would be the closest i think um just thinking about it is that you can emulate higher kind of types uh but you can't get to the same extent it's not quite as natural as haskell well thanks for an insightful information about the fact that they are trying to add them and also maybe it's a topic for uh to to attract haskell crowd right like to your youtube channel emulating higher kind of types and and rust and um yeah another question that i understand that this is the last question that we have um unless the producer will correct me so the final question is uh from someone who's very like practical about uh learning stuff so there's a very popular approach of like learning by building right so so the person asks like kind of what's the best way to go about learning rust and like what projects in the context of like what projects could they try to build to to learn so i don't want to promote like so this is lovely book uh no so um one of the things that distinguishes rust in action is that you build a big example in every chapter of the code every chapter of the book so we build a database we build a simulate the semi cpu emulator we um we implement a uh uh we uh http like multiple times and every time we remove one layer of abstraction and by the end we're actually create we're sending like tcp um requests um ourselves and so if you're the kind of person who likes projects um rust in action is your book there are free resources so there are several things there are several uh one that i like is um there's a tutorial for creating a text editor in rust i think it's um and i'll send the link through to um the team um for later uh and there's also a really lovely book uh related to games programming called hands-on rust and hands-on rust is a uh i think it's called hands-on rust effective programming with rust or something it implements a 2d platform game and it is it's quite fun that's that's really cool uh actually we have one more question and for our current viewers who are live uh again this will be edited out but uh rest assured that that we will get uh some way so so that you will get after we get into post-production you will get some way to like get a book for or get tim's book for free um if you're eager enough and um we have a little like a couple of uh promo codes and we will announce it when we are done with uh producing the final video and producing the podcast episode so stay tuned for that it's yeah i mean uh actually i don't know it's it's honestly your book sounds so fun yeah anyway i know what i'll be doing uh today before i go to sleep but anyway so uh uh as a so the final question for reals now i promise as a functional programmer okay i'll do it once again for the editing team so the real final question is as a functional programmer are there ways i could leverage my previous experience to kick off learning rust yes very much so so rust uh prefers higher order programming and function a functional style over almost all of its collections and so you may think of rust as an imperative language because it is normally associated with c plus however rust was originally an ml it was implemented first in ocamel and so a lot of your functional learning will flow through into rust quite naturally yeah i personally i personally from for myself like again as a rust beginner i found out that kind of the way we write functional python i i know it's kind of weird but you know like you have kind of functional wrappers around like kind of imperative sometimes imperative like loops when it's just convenient to mod or effective to modify something uh like some modify some dictionary and have like a functional api or a functional interface to it again in my like kind of beginner experience this is what i do in rust a lot to a pretty good success which means that then you will compose those functional wrappers together pretty much like as if you're writing haskell or something like that but uh yeah i don't know i mean i guess this this is a reasonable uh take on that so yeah thank you so much for joining us tim it was a huge pleasure to to talk to you and uh sorry for um for that like impromptu uh coding session it but i mean you you succeeded it was like i'm i'm still in oh and the fact that you made it uh made your implementation generic was also very very cool so yeah thanks for coming uh wonderful hey i've really enjoyed it and uh and also um a big success with the rest of the podcast i'm looking forward to uh looking looking through uh your previous episodes and and subscribing for more thanks thank you very much bye-bye you