/* A Transition Guide to Rust for Advanced Computer Science Students Chuck Liang, Hofstra University Note: at the same URL there is a .rs version of this file. This version is .txt so it can be displayed in a browser. */ #![allow(unused_variables)] /* compiler directives to skip warnings */ #![allow(unused_assignments)] #![allow(dead_code)] /* Rust is a difficult language to learn, even for seasoned programmers. It's perhaps most difficult for programmers who are only familiar with languages with a garbage collector, including Java, Python and Go. The majority of modern programming languages rely on automatic garbage collection but only a handful, including Rust, do without it in order to minimize runtime overhead. Find all resources on rust-lang.org. Once you've Rust installed, compile this program with `rustc transitionguide.rs` and run it with `./transitionguide`. Most Rust projects live in "cargo crates", but this is a stand-alone program. This guide is written for people who have already seen a spectrum of different programming languages and are familiar with the following: 1. Smart pointers and move semantics in modern C++. In particular, familiarity both in theory and in practice of the concepts of LIFETIME and OWNERSHIP. 2. Lambda expressions, closures and Monadic error handling using the `Option`, `Maybe` or `Result` monads. 3. A statically typed functional language in the ML class, such as Haskell, F#, or Scala. In particular, type inference and pattern matching with algebraic data types. Roughly speaking, you can think of Rust as F# without a garbage collector. Of these points, the first concerning C++ is most critical. Data types in Rust can be divided into two categories: those that can be copied and those that can't be. Specifically, a data type can be copied if it implements the `Copy` trait. A `trait` is similar to an interface and is a crucial part of Rust. A type can implement this trait only if it's of a fixed size that's known at compile-time, and is contiguous in memory (and therefore can be completely allocated on the stack and copied in one pass with a procedure akin to `memcpy` in C). Data that can be copied include primitive types for numerical values (i32, u32, f64, etc), booleans, and single characters. If you define a data structure that contains only copyable values, then that struct can also be copied (you can automatically derive the Copy trait for it). For example, Rust arrays must have their size known at compile time, and so an array of :Copy values can itself be copied. However, if some part of your data structure contains (smart) pointers to heap-allocated data, such as in the case of a std::Vec (vector), then it cannot be copied. Unlike C++, you cannot redefine the copy semantics of a type: only contiguous data that does not contain pointers to heap can be copied and they're always copied in the same way (there is another trait, `Clone`, that can be implemented in different ways). It is important that copying observes strong invariants. If a type cannot be copied, it is *moved*. Whenever you write an assignment statement in Rust: a = b; it is most similar to `a = move(b)` in modern C++ with its default move semantics. If you take C++ and restrict it to references and the built-in std smart pointers, avoid raw pointers and avoid defining your own copy/move semantics, and replace all "a=b" with "a=move(b)", then it's somewhat close to Rust. Somewhat. In a Rust assignment "a=b", if the type of a and b is copyable, then b is copied to a, otherwise, it's moved to a. Move semantics are the only semantics in Rust. A TRANSFER OF OWNERSHIP always occurs during a move. It is also not possible to redefine the move semantics of a type in Rust because a crucial difference between Rust and C++ is that the rules of LIFETIMES are checked at COMPILE TIME. Once "move occurs", you can no longer refer to the item that was moved because its lifetime has ended (recall that lifetime refers to how long something is guaranteed to stay in the same location in memory). If `a = b` resulted in a move, then any subsequent reference to b will result in a compiler error. C++ will continue to allow you to refer to the moved object, which could result in dereferencing a null pointer. For the rust compiler to check if your program is well-behaved, the semantics of copy and move has to be fixed. It can't allow you to change them arbitrarily, like you can in C++: mystruct(const mystruct& other) { // copy constructor cout << "too lazy to copy"; } mystruct(mystruct&& other) { // move constructor cout << "too tired to move"; } Let's look at how the rust compiler checks an actual function: */ fn copy_or_move() { let mut x = 3; // type of x is inferred, 'mut' required for mutation let y = 4; x = y; // copy occurs because integers implement the Copy trait println!("y is still usable and still has value {}",y); let a = vec![1,2,3]; // vectors are heap-allocated and not copyable let b = a; // move occurs //let first = a[0]; // WON'T COMPILE! } /* If you compile this function with the last line uncommented (try it), you will see the following compiler error (line numbers may vary): -------- 80 | let a = vec![1,2,3]; | - move occurs because `a` has type `Vec`, which does not implement the `Copy` trait 81 | let b = a; | - value moved here 82 | let first = a[0]; | ^ value borrowed here after move | help: consider cloning the value if the performance cost is acceptable | 81 | let b = a.clone(); | ++++++++ -------- This is your first encounter with the RUST BORROW CHECKER, dreaded by most newcomers to Rust but you've been well-prepared. The compiler gave clear reasons for why it didn't compile the code: it violated the rules of lifetimes: `a` should not be referenced again after the move. However, the advice it gave you about cloning should be ignored: the performance cost is almost never acceptable. Many newbies will call .clone() profusely (the Clone trait can be implemented for most types) in order to escape the borrow checker. This is wrong. Find another way to write your program because Rust shares with C++ the principle of "zero overhead abstraction." However, the way this principle is realized is very different in the two languages. Both languages waste little effort to check for memory violations at runtime, but only Rust will check for these violations at compile time. Ironically, despite promoting the zero-overhead concept, most custom copy constructors in C++ actually clone instead of copy. But that's the least of C++'s problems. The following C++ code will compile and print out junk: vector v{1,2,3,4} int& second = v[1]; v.push_back(5); v.push_back(6); cout << second; // what's printed won't be 2 Why does it print junk? (run it if you don't believe me). Because when the vector is mutated by the push_backs, new memory had to be allocated for the vector to stay contiguous in memory. The original memory for 1,2,3,4 wasn't enough. The lifetime of the data referenced by `int& second` ended because it's no longer at the same location in memory, yet the reference itself is still ALIVE! But rust will protect you from the zombie reference: it won't even compile. */ fn undead_reference() { let mut v = vec![1,2,3,4]; let second = &v[1]; v.push(5); // print!("{}", second); // COMPILER ERROR if uncommented } /* The compiler error here would be -------- 135 | let second = &v[1]; | - immutable borrow occurs here 136 | v.push(5); | ^^^^^^^^^ mutable borrow occurs here 137 | print!("{}", second); | ------ immutable borrow later used here -------- The error is caused by a violation of the rules of lifetimes but more fundamentally, it's a violation of the rules of safe mutation (something I call personally the "principle of exclusive mutation"). That is, you can't change something while it's still being used. Even if you adopt exclusively unique_ptr/make_unique for managing heap memory in C++, there can still be memory leaks because of violations of this principle. About Pointers and Refereces There are two types of pointers in Rust: smart pointers and "borrows". A borrow is something in between a pointer and a reference in C++. A borrow can be immutable or mutable, as in `let r=&mut x`. Note that there's a difference between `let r1=&mut x` and `let mut r2=&x`. r1 can be used to mutate x (with *r+=1), and r2 can be changed to reference something other than x (unlike a c++ reference), but it can't mutate x. With `let mut r3=&mut x` you can do both. r1 and r3 are considered mutable borrows but r2 is immutable. Immutable borrows (&x) can be copied but mut ones (&mut x) can't be. During the lifetime of a mut borrow, NO OTHER BORROWS OF THE SAME VALUE CAN EXIST, mutable or immutable. This is the most important rule of safe mutation (more on why later). However, if there are no live muts, there can be multiple immutable borrows, which is why non-muts are copyable. A borrow can be created explicitly using the & (or &mut) operator (you can also say `let ref (mut) second = v[1]`). They can also be created implicity. When you access the vector via expressions like `v[1]` or `v.push`, you're creating borrows (mut or not) implicitly. Think of them as v->get(1) and v->push. A borrow can be dereferenced using the * operator, like a pointer in C++. However, unlike a C++ pointer, you cannot perform pointer arithmetic. Did you know that in C++, given an array A, A[i] and i[A] are the same, because both are just *(i+A)? Interesting trick for your next nerd party. You can avoid transfers of ownership with borrows, just like with references in C++, but unlike C++ pointers, mixing borrows with smart pointers won't create the same kind of chaos. For example, transfers of ownership (move) also occurs when you pass a non-copyable object to a function, or return one from a function. But you can avoid that by passing a borrow. Most rustaceans use the terms "borrow" and "reference" interchangebly. All borrows must refer to allocated data because after they're deallocated, you can't use the borrows again (unless you assign them to reference something else). They can reference both stack- and heap-allocated data. There is NO NULL REFERENCE in Rust (at least not in "safe" rust). Another type of reference, called a "slice", consists of a memory address and a length. They reference a contiguous block of memory of a certain length. For example, given an array or vector A of type T, the slice `&A[2..6]` refers to A[2] through A[5]: this slice would have type `&[T]`. When heap memory is first allocated, they are pointed to by smart pointers. The built-in smart pointers in Rust are essentially the same as the ones in C++ std: `Box` corresponds to unique_ptr, `Rc` corresponds to shared_ptr and `Weak` corresponds to weak_ptr. Even Rust doesn't have a better solution when pointers form cyclic graphs, except for a combination of Rc (referece counter) and Weak. The only situation when safe Rust can still produce a memory leak or dangling pointer is when not enough or too many Rc's are designated Weak. You might be disappointed by this news, but consider the reasons. The compiler cannot predict the value of a reference counter in an Rc just as it cannot in general predict the value of any variable at runtime. If we cannot detect the problem at compile time, what kind of overhead would it incur at runtime? You would have to generate a *spanning tree*, traversing the pointer graph until you've created an acyclic closure. That's a rather expensive algorithm, and is in fact what a *garbage collector* would do. But that's exactly what we're trying to avoid. Fortunately, in most situations that require shared pointers it's easy to determine which, if any ones should be downgraded to weak pointers. For example, in a doubly-linked list, the "next" pointers can be Rc and the "previous" pointers can be Weak. In the observer design pattern, the pointers from observers to observed objects can be Rc and the pointers in the other direction should be Weak. Speaking of design patterns, Rust should NOT be considered an object oriented programming language, at least not in the sense of Java. There is no support for inheritance and only minimal support for dynamic dispatch. If you want to do heavy OOP, go back to javaland. None of the smart pointers can be copied, but Rc can be cloned in O(1) time by incrementing the reference counter. Box and Rc implement "deref coercion": given `let b = Box::new(a),` `b.x` is equivalent to `a.x`. Box::new is the equivalent of make_unique in C++. =============== +++++++++++++++++ What Kind of Mutations are Safe The pure typed lambda calculus gives us many *invariants* such as the Church-Rosser property, which says that we can evaluate an expression any way we want and it will give us the same result at the end: this means we have the greatest freedom in finding the *optimal* way to run a program. Unfortunately we can't guarantee this property often enough. Take, for example, the following program in the language "lambda7b": define x = 2; define f = lambda y: (x = x*0; y;); define g = lambda y: (x = x+1; y;); g(f(1)); cout x; This little program would print 1 under call-by-value (if f is called first) and 0 under call-by-name (if g is called first). This program is clearly not admissible in lambda calculus (typed or untyped) as it violates the Church-Rosser property. What is the source of the impurity? It's easy to point to mutation (destructive assignment) as the culprit: in a language without mutation (Haskell, Elm), this example would not be possible. But are all forms of mutation equally inadmissible in lambda calculus? It's hardly possible to write all algorithms efficiently without mutation. Let's try to write the above example in Rust, which allows mutations. The syntax of lambda x.E in Rust is |x|{E}. */ fn can_church_rosser_live_alongside_mutations() { let mut x = 2; let mut f = |y:i32|{x=x*0; y }; let mut g = |y:i32|{x=x+1; y; x }; // Note that f and g are both "mut" because the closure itself // changes each time it's called. We can define f and g but // we can only call one of them. Their lifetimes cannot intersect. // The offending line won't compile: //g(f(1)); // COMPILER ERROR if uncommented } /* **The fact that Rust allows destructive assignment does not by itself mean that there's a loss of the Church-Rosser property.** It's not just mutation but mutation from two different borrows. Uncomment the call to g(f(1)) and look at the compiler error message, which will include: ----- let mut f = |y:i32|{x=x*0; y }; ------- - first borrow occurs due to use of `x` in closure | first mutable borrow occurs here let mut g = |y:i32|{x=x+1; y; x }; ^^^^^^^ - second borrow occurs due to use of `x` in closure g(f(1)); - first borrow later used here ----- Let's look at this problem another way. Not all destructive assignments are equally "destructive." We know that many loops with "i++" at the end can be rewritten as tail-recursive functions without destructive assignment. This means that at least some loops are actually admissible as purely functional programs, does it not? The infamous "x=x+1" can be explained in the following way in lambda calculus. The construct (let x=v in E) is equivalent to (lambda x.E)v. That is, bind x to v then evaluate E, which may have free occurrences of x. We can't "mutate" x but we can define a new version of it, under a different lambda binder, with a different value. Suppose an expression had the following format: let x = 1 in ..outer1.. let x = x+1 in ..inner.. ..outer2.. This term is equivalent to (lambda x. ..outer1.. (lambda x. ..inner..)x+1 ..outer2..) 1 That is, inside the body of the outer lambda, there is an inner definition of another x, with value bound to the outer x plus 1. outer1 and outer2 designate the portions of the body of the outer lambda x before and after the inner lambda (with body ..inner..). Assume a call-by-value, left-to-right order of evaluation. We know that there are actually two x's in the program (it's not even necessary to alpha-convert them). When implementing such an expression, we should allocate a different memory location for each x. But ARE THERE CIRCUMSTANCES IN WHICH WE CAN MAKE AN OPTIMIZATION, and REUSE the memory for the outer x to store the inner x? Clearly, that is only possible if the outer x does not appear free again in the ..outer2.. portion. That is, if the value of the outer x WON'T BE NEEDED AGAIN. The logic here is a generalization of the justification for the elimination of tail-recursion: if we won't need the values on the current stack frame again, there's no need to create a new frame. However, here we are applying the "contrapositive" of this logic: mutation, x=x+1, can be admissible in pure lambda calculus if there are no further references to the value of x before the mutation. It's not just variables declared 'mut' that can be mutated. We should realize that "end of lifetime" is also a form of mutation. When something gets deallocated from memory, or moved, it mutates. */ fn exclusive_mutation() { let mut u = 2; let bu = &u; // an explicit borrow u += 1; // mutates //println!("{}",bu); // COMPILER ERROR - bu invalidated by mutation. let v = vec![1,2,3]; let w = v; // move occurs //println!("{}",v[1]); // COMPILER ERROR - moving is also a mutation } /* The dreaded borrow checker is in fact checking for only one thing: **MUTATION MUST INVALIDATE ALL OTHER REFERENCES** Rust is still not pure lambda calculus; it can make system calls and do input/output. But Rust have greater invariants of the kind that we want from pure programs. When using Rust, especially as a replacement for C++, it will often have the look and feel of an imperative language with loops, references and destructive assignment. In fact, Rust doesn't even guarantee tail-recursive optimization in all cases: recursion is generally discouraged. But despite how it looks, it is actually closer to pure typed lambda calculus than many "functional" languages, including F# and Scala. As an important example of the safe rules of mutation, let's try to reproduce a C++ memory leak that occurs even with smart pointers: struct node { unique_ptr A; unique_ptr next; // pointer to next node struct node(int n) { A = make_unique(n); } //constructor }; void it_still_leaks() { unique_ptr P = make_unique(10); P->next = move(P); // this line causes a memory leak. *** } The leak is easily observed by calling the function in an infinite loop. It still leaks despite unique_ptr/make_unique exclusively managing heap memory. In the offending line, the unique pointer P->next "ate itself:" two mutations (move and assign) were being made to it at the same time. The following is a close-enough equivalent. */ struct node { a : Vec, next : Option>, // Box is basically equivalent to unique_ptr } fn does_it_leak() { let p = node { a : vec![5;10], next : None, }; let mut P = Box::new(p); // Box::new is equivalent to make_unique //P.next = Some(P); // this line emulates the C++ memory leak } // no, it won't compile /* The line that would've caused a memory leak was caught by the borrow checker: ------ 424 | P.next = Some(P); | ^^^^^^ - value moved here | | | value partially assigned here after move ------ Since P.next is part of P, it was mutated when moved. But the value was needed again in the assignment. Two mutable references to P->next (and to P) had intersecting lifetimes. The rules of exclusive mutation insist that the two mutations take place in separate stages: the second one should not start before the first one is complete. Incidentally, in a garbage-collected language such as Java, P.next=P won't cause a memory leak but it would've created a loop that would make traversing the linked list rather difficult to terminate. Rust guarantees that pointers created with Box form *trees* in memory. */ /* NOW FOR THE BAD PART Programming in Rust is a different experience, with many surprises for newcomers, including advanced ones. EVEN BUBBLESORT CAN GO WRONG! fn bubblesort(v: &mut [T]) { for i in 0 .. v.len()-1 { for k in 1 .. v.len()-i { if v[k](v: &mut [T]) { for i in 0..v.len()-1 { for k in 1 .. v.len()-i { if v[k] &i32 { return &x; } I hope you know that this function would return a dangling reference because x gets popped from the stack, and even the C++ compiler will warn you about it. But Rust's compiler error message will say: 235 | fn d(x:i32) -> &i32 { | ^ expected named lifetime parameter This is because all references have associated with them the lifetimes of the data that they reference: the full syntax is &'t where 't is a called a "lifetime parameter." Newbies to rust are often confused about how to use lifetime parameters: sometimes they think that it would allow them to specify how long something should live, and may write something like fn d(x:i32) -> &'static i32 { return &x; } because the 'static lifetime refers to the duration of the entire program. But this won't compile either. You can't extend lifetimes: things die when they're supposed to. The purpose of the lifetime parameter is for you to PROVE to the compiler that your program observes the rules of lifetimes. In many situations, the compiler can infer the correct lifetime, like it can infer types, but here it can't figure it out, so it's asking you for proof. Of course you can't provide proof because the reference returned would outlive x. But the following compiles: */ fn d2() -> &'static str { return "string literals really do have 'static lifetime"; } /* A literal (constant) has to be part of the source code itself, so it must exist statically in memory for the duration of the program, and thus have the 'static lifetime. How about the following: fn d3(x:&i32, y:&i32) -> &i32 { if (x(x:&'t i32, y:&'t i32) -> &'t i32 { if (x (x:&'u i32, y:&'t i32) -> &'t i32 { if (x(x:&i32, y:&'t i32) -> &'t i32 { return y; } /* These generic (template) functions are parameterized by lifetime variables ('t, 'u). We've restricted d3 so that the lifetimes of x and y are compatible. In d4, the notation 'u:'t should be read as "'u lives at least as long as 't." Thus the returned borrow references data that will still be alive for duration 't. In d5, the lifetime of x doesn't matter, so it's not necessary for you to provide it. Change things around to see what kind of error messages the compiler will give. In the final example we show how to define a simple struct: */ #[derive(Copy,Clone,Debug,Eq,PartialEq,Ord,PartialOrd,Hash)] struct date { year : u16, // 16 bit unsigned integer month : u8, day : u8, } /* A large number of traits can be derived automatically for many types. For the date type, Copy is also derivable because the struct can be represented contiguously in memory. The Ord trait is derived from the Ord trait implementations of the components of the type, and is the lexicographical ordering dependent on the order in which the fields are defined. The Debug trait allows date structs to be printed with the string formatter {:?}. To have it printed in a custom way you will have to manually define the Display trait. You can custom define most traits EXCEPT COPY. */ fn change_day(the_date:&mut date, d:u8) { the_date.day = d; } fn thats_not_what_I_changed() { let mut today = date { month:4, day:12, year:2024, }; let y = &today.year; change_day(&mut today,13); //println!("year {}", y); // WON'T COMPILE AND THAT'S NOT FAIR! } /* However, the function `thats_not_what_I_changed` fails to compile if its last line is uncommented, because the reference y was used after a mutation to the date structure. But that's so unfair! The change was to the day, not the year! But the rust compiler doesn't look inside functions. It just sees that a &mut of the object was passed to the function. The function could've done nothing at all and it would still be an error. Perhaps in future this can improve, or a syntax could be provided to allow us to specify what part of the struct will mutate. For now, we just have to work around the borrow checker. The easiest solution is to re-borrow y after the mutation, or pass only the value(s) to be mutated to the function */ fn change_u8(x:&mut u8, newvalue:u8) { *x = newvalue; } fn now_you_know_what_I_changed() { let mut today = date { month:4, day:12, year:2024, }; let y = &today.year; change_u8(&mut today.day,13); println!("year {}", y); } /* If we want the safety of Rust, we have to live with the fact that sometimes its compiler takes a little more convincing. To conclude this introduction, the main function of this program reinforces and further illustrates the principles we've discussed. It also introduces some other features of rust (pattern matching and error handling). ALL THE COMMENTED-OUT LINES OF CODE WOULD CAUSE COMPILER ERRORS. */ // function called from main: (doesn't have to be defined first) fn f1(s:String) -> String // a function that takes and returns ownership { let mut s2 = s; //moves again to another local var s2.push_str(" and that ends that string"); return s2; // transer ownership of local var }// called from main fn main() { // main use std::str::from_utf8; //this function returns a Result monad let mut a1:[u8;3] = [97,98,99]; // size of array is part of its TYPE let mut a2 = a1; // array size is known at compile time, copyable a1[1] = 66; // a1 still usable because the above line copies, not moves let a2_slice:&[u8] = &a2[1..3]; // slice reference to 98, 99, "bc" // from_utf8 interprets &[u8] as string slices (type &str): match from_utf8(a2_slice) { Ok(string_slice) => {println!("a2 slice as str: {}",string_slice);}, Err(_) => {eprintln!("conversion of &[u8] to &str failed");} }//match let a1_as_str:&str = from_utf8(&a1[..]).unwrap_or("UNEXPECTED ERROR"); println!("but a1 is now {}",&a1_as_str); // A string slice (&str) must refer to allocated data. The type String // is implemented underneath with a vector (Vec) and is therefore // heap-allocated and not copyable. let mut s1 = String::from("abcd"); let mut rs = &s1; // a "borrow" of s1 let mut s2 = s1; // MOVE OCCURS //println!("can I still print the string with rs1? {}", rs1); rs = &s2; // valid because rs is declared with "let mut .." println!("but I can re-borrow: {}",rs); s2.push_str("efg"); // mutate string (implicity mutable borrowing occurs) //println!("is rs still a valid borrow of s2? {}",rs); // move something back into s1 (because it's mut s1) s1 = "hello world".to_owned(); // another way to create an "owned String" // move (transfer of ownership) also occurs when passing a String to // a function, and when a string is returned from a function let s3 = f1(s1); //println!("{} has been transformed into {}",&s1, &s3); // How can I do anything with a variable if gets "moved" so easily? // I can BORROW it with a reference (alias), without taking ownership: let s4 = f2(&s3[..]); // f2 defined after main println!("{} has been transformed into {}",&s3, &s4); ///// When you have a borrow of a non :Copy value, don't try to // to dereference it as it would try to create a temporary copy // of the value, which of course it could not: let b4 = &s4; //let s5 = *b4; // "move occurs ... does not implement the Copy trait" ///// mutable references must exist (live) exclusively: let mut x = 1; let rx = &x; x += 1; // mutation invalidates all references, even for copyable things //let y = *rx + 1; // would work in C but not here... // let mb4 = &mut b4; // cannot create a mutable ref to an immutable value let mb2 = &mut s2; // OK *mb2 = String::from("aaabbb"); //OK, move occurs assert_eq!(6, mb2.len()); // while s2.len()<100 { mb2.push('x'); } // add chars to end while mb2.len()<100 { mb2.push('x'); } // add chars to end println!("s2 is now {}",&s2); // ok but mb2 can't occur after this line }//main fn f2(s: &str) -> String { let mut s2:String = String::from(s); s2.push_str(" and that ends that string"); return s2; // transer ownership of local var }