Rust Hack Github
Elisabet Schwartzkopf
The aim of this tutorial is to take you to a place where you can read and writeenough Rust to fully appreciate the excellent learning resources availableonline, in particular The Book.It's an opportunity to try before you buy, and get enough feeling for thepower of the language to want to go deeper.
As Einstein might have said, "As gentle as possible, but no gentler.". There is alot of new stuff to learn here, and it's different enough to require somerearrangement of your mental furniture. By 'gentle' I mean that the features arepresented practically with examples; as we encounter difficulties, I hope toshow how Rust solves these problems. It is important to understand the problems beforethe solutions make sense. To put it in flowery language, we are going for a hikein hilly country and I will point out some interesting rock formations on the way,with only a few geology lectures. There will be some uphill but the view will beinspiring; the community is unusually pleasant and happy to help.There is the Rust Users Forum and an activesubreddit which is unusually well-moderated.The FAQ is a good resource ifyou have specific questions.
First, why learn a new programming language? It is an investment of time and energyand that needs some justification. Even if you do not immediately landa cool job using that language, it stretches the mental muscles and makes you abetter programmer. That seems a poor kind of return-on-investment but if you'renot learning something genuinely new all the time then you will stagnate and belike the person who has ten years of experience in doing the same thing over and over.
Rust is a statically and strongly typed systems programming language. staticallymeans that all types are known at compile-time, strongly means that these typesare designed to make it harder to write incorrect programs. A successful compilationmeans you have a much better guarantee of correctness than with a cowboy languagelike C. systems means generating the best possible machine code with full controlof memory use. So the uses are pretty hardcore: operating systems, device driversand embedded systems that might not even have an operating system. However, it'sactually a very pleasant language to write normal application code in as well.
There is a fast-growing ecosystem of available libraries through Cargobut here we will concentrate on the core principles of the languageby learning to use the standard library. My advice is to write lots of small programs,so learning to use rustc directly is a core skill. When doing the examples in thistutorial I defined a little script called rrun which does a compilation and runsthe result:
rustup is the command you use to manage your Rust installation. When a new stable releaseappears, you just have to say rustup update to upgrade. rustup doc will openthe offline documentation in your browser.
Personally I'm a fan of Geany which isone of the few editors with Rust support out-of-the-box; it's particularly easyon Linux since it's available through the package manager, but it works fine onother platforms.
Zed Shaw's advice about learningto program in Python remains good, whatever the language. He says learning to programis like learning a musical instrument - the secret is practice and persistence.There's also good advice from Yoga and the soft martial arts like Tai Chi;feel the strain, but don't over-strain. You are not building dumb muscle here.
I'd like to thank the many contributors who caught bad English or bad Rust for me,and thanks to David Marino for his cool characterizationof Rust as a friendly-but-hardcore no-nonsense knight in shining armour.
I fairly frequently get asked how to implement a linked list in Rust. Theanswer honestly depends on what your requirements are, and it's obviously notsuper easy to answer the question on the spot. As such I've decided to writethis book to comprehensively answer the question once and for all.
Just so we're all the same page, I'll be writing out all the commands that Ifeed into my terminal. I'll also be using Rust's standard package manager, Cargo,to develop the project. Cargo isn't necessary to write a Rust program, but it'sso much better than using rustc directly. If you just want to futz around youcan also run some simple programs in the browser via play.rust-lang.org.
It should be noted that the authentic Rust learning experience involveswriting code, having the compiler scream at you, and trying to figure outwhat the heck that means. I will be carefully ensuring that this occurs asfrequently as possible. Learning to read and understand Rust's generallyexcellent compiler errors and documentation is incredibly important tobeing a productive Rust programmer.
Although actually that's a lie. In writing this I encountered way morecompiler errors than I show. In particular, in the later chapters I won't beshowing a lot of the random "I typed (copy-pasted) bad" errors that youexpect to encounter in every language. This is a guided tour of having thecompiler scream at us.
We're going to be going pretty slow, and I'm honestly not going to be veryserious pretty much the entire time. I think programming should be fun, dang it!If you're the type of person who wants maximally information-dense, serious, andformal content, this book is not for you. Nothing I will ever make is for you.You are wrong.
But all of these cases are super rare for anyone writing a Rust program. 99%of the time you should just use a Vec (array stack), and 99% of the other 1%of the time you should be using a VecDeque (array deque). These are blatantlysuperior data structures for most workloads due to less frequent allocation,lower memory overhead, true random access, and cache locality.
Linked lists are as niche and vague of a data structure as a trie. Few wouldbalk at me claiming a trie is a niche structure that your average programmercould happily never learn in an entire productive career -- and yet linked listshave some bizarre celebrity status. We teach every undergrad how to write alinked list. It's the only niche collectionI couldn't kill from std::collections. It'sthe list in C++!
Several people apparently read the first paragraph of this PSA and then stopreading. Like, literally they'll try to rebut my argument by listing one of thethings in my list of great use cases. The thing right after the firstparagraph!
Just so I can link directly to a detailed argument, here are several attemptsat counter-arguments I have seen, and my response to them. Feel free to skipto the first chapter if you just want to learn some Rust!
Yes! Maybe your application is I/O-bound or the code in question is in somecold case that just doesn't matter. But this isn't even an argument for usinga linked list. This is an argument for using whatever at all. Why settle fora linked list? Use a linked hash map!
Yep! Although as Bjarne Stroustrup notes this doesn't actuallymatter if the time it takes to get that pointer completely dwarfs thetime it would take to just copy over all the elements in an array (which isreally quite fast).
Unless you have a workload that is heavily dominated by splitting and mergingcosts, the penalty every other operation takes due to caching effects and codecomplexity will eliminate any theoretical gains.
You've already entered a pretty niche space -- most can afford amortization.Still, arrays are amortized in the worst case. Just because you're using anarray, doesn't mean you have amortized costs. If you can predict how manyelements you're going to store (or even have an upper-bound), you canpre-reserve all the space you need. In my experience it's very common to beable to predict how many elements you'll need. In Rust in particular, alliterators provide a size_hint for exactly this case.
Then push and pop will be truly O(1) operations. And they're going to beconsiderably faster than push and pop on linked list. You do a pointeroffset, write the bytes, and increment an integer. No need to go to any kind ofallocator.
Well, this is complicated. A "standard" array resizing strategy is to growor shrink so that at most half the array is empty. This is indeed a lot ofwasted space. Especially in Rust, we don't automatically shrink collections(it's a waste if you're just going to fill it back up again), so the wastagecan approach infinity!
Linked lists on the other hand unconditionally waste space per element.A singly-linked list wastes one pointer while a doubly-linked list wastestwo. Unlike an array, the relative wasteage is proportional to the size ofthe element. If you have huge elements this approaches 0 waste. If you havetiny elements (say, bytes), then this can be as much as 16x memory overhead(8x on 32-bit)!
Great! Linked lists are super elegant to use in functional languagesbecause you can manipulate them without any mutation, can describe themrecursively, and also work with infinite lists due to the magic of laziness.
Rust also lets you easily talk about sub-arrays with slices. Your usualhead/tail split in a functional language is just slice.split_at_mut(1).For a long time, Rust had an experimental system for pattern matching onslices which was super cool, but the feature was simplified when it wasstabilized. Still, basic slice patterns are neat! And of course,slices can be turned into iterators!
Note that I'm not saying that functional programming is necessarily weak orbad. However it is fundamentally semantically limited: you're largely onlyallowed to talk about how things are, and not how they should be done. Thisis actually a feature, because it enables the compiler to do tons of exotictransformations and potentially figure out the best way to do thingswithout you having to worry about it. However this comes at the cost of beingable to worry about it. There are usually escape hatches, but at some limityou're just writing procedural code again.
Even in functional languages, you should endeavour to use the appropriate datastructure for the job when you actually need a data structure. Yes,singly-linked lists are your primary tool for control flow, but they're areally poor way to actually store a bunch of data and query it.
64591212e2