/* A Transition Guide to Rust for Advanced Computer Science Students Chuck Liang, Hofstra University */ #![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. 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. Of these points, the first concerning C++ is most critical. As a rough analogy, if C++ is C# without a garbage collector then Rust is F# without a garbage collector. But rough analogies teach us little. Let's get into the details. 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. 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 fixed size 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. That is, 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 usually becomes a null pointer. For the rust compiler to check if your program is well-behaved, it has to fix the semantics of copy and move. It can't allow you to change them like you can in C++: mystruct(const mystruct& other) { // copy constructor cout << "no paper in the copier"; } 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: -------- 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. 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 not allow the zombie reference to eat your brain: 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 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 in C++, 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 predicate the value of a reference counter in an Rc (how many pointers are pointing to the same memory) 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. =============== +++++++++++++++++ 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 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: Suppose we have a program with the following structure: lambda x: ... let f = (lambda x:E) in ... f(x+1) ... We know that there are actually two x's in the program, one bound by the outer lambda and one bound by the inner one. We can alpha-convert one of them to something else. When implementing this program, we should allocate different memory locations for the two x's. But what if THERE IS ONLY ONE OCCURRENCE of the outer-bound x in the entire term. That is, what if the x in f(x+1) is the only place that it occurs. In that case, we can make an optimization (similar to tail-recursion optimization) to REUSE the memory for the outer x to store the inner x when evaluating E. The x inside E "becomes" x+1. However, if the outer x also occurred elsewhere (in the ...) then such an optimization cannot be made: the destruction of the outer x clearly must invalidate all other references to x, EXCEPT ONE. The optimization - the mutation - does not contradict the rules of lambda calculus **if there are no other references to what's being mutated.** */ fn exclusive_mutation() { let mut u = 2; let bu = &u; // an explicit borrow u += 1; // mutates //println!("{}",bu); // compiler error -bu invalidated by mutation. } /* Now if we include "end of lifetime" as a form mutation, then the borrow checker is really looking for one thing: the existence of other references to a value after its mutation. Rust is still not pure lambda calculus (it has I/O). 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 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. But despite how it looks, it is actually closer to pure typed lambda calculus than many "functional" programming languages, including F# and Scala. As a better example of Rust's rules of mutation, let's try to reproduce a C++ a memory leak: 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 managing the 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. */ struct node { a : Vec, next : Option>, // Box is a smarter pointer } fn does_it_leak() { let p = node { a : vec![5;10], next : None, }; let mut P = Box::new(p); //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 ------ "partially assigned" : 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. */ /* 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 1..v.len() { for k in 1 .. v.len()-i { if v[i](v: &mut [T]) { for i in 1..v.len() { for k in 1 .. v.len()-i { if v[i] &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 and be stack-allocated. 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 // 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 }