From 83e8dbfff2a6fdce785af58dbb13f007c4234cf2 Mon Sep 17 00:00:00 2001 From: Ralf Jung Date: Thu, 9 Jul 2015 16:46:02 +0200 Subject: [PATCH 1/1] complete part 10 --- Makefile | 2 +- src/main.rs | 1 + src/part01.rs | 6 +++ src/part04.rs | 4 +- src/part05.rs | 6 ++- src/part08.rs | 9 +++- src/part09.rs | 6 +-- src/part10.rs | 99 +++++++++++++++++++++++++++++++++++++++-- workspace/src/part01.rs | 6 +++ workspace/src/part05.rs | 6 ++- workspace/src/part10.rs | 56 +++++++++++++++++++++-- 11 files changed, 182 insertions(+), 19 deletions(-) diff --git a/Makefile b/Makefile index c81bf58..9264efc 100644 --- a/Makefile +++ b/Makefile @@ -29,7 +29,7 @@ workspace/src/%.rs: src/%.rs Makefile dup-unimpl.sed @echo "$< -> $@" @# sed-fu: remove lines starting with "//@", and replace those ending in "/*@*/" by "unimplemented!()". @# Also coalesce multiple adjacent such lines to one. - @sed '/^\s*\/\/@/d;s|\(\s*\)\S.*/\*@@?\*/|\1unimplemented!()|' $< | sed -f dup-unimpl.sed > $@ + @sed '/^\s*\/\/@/d;s|\(\s*\)\S.*/\*@@\?\*/|\1unimplemented!()|' $< | sed -f dup-unimpl.sed > $@ workspace/src/main.rs: # Don't touch this file diff --git a/src/main.rs b/src/main.rs index d7945a5..68578fd 100644 --- a/src/main.rs +++ b/src/main.rs @@ -77,6 +77,7 @@ // * [Part 07: Operator Overloading, Tests, Formating](part07.html) // * [Part 08: Associated Types, Modules](part08.html) // * [Part 09: Iterators](part09.html) +// * [Part 10: Closures](part10.html) // * (to be continued) #![allow(dead_code, unused_imports, unused_variables, unused_mut)] mod part00; diff --git a/src/part01.rs b/src/part01.rs index ed4f73f..e73da23 100644 --- a/src/part01.rs +++ b/src/part01.rs @@ -35,6 +35,12 @@ fn number_or_default(n: NumberOrNothing, default: i32) -> i32 { } } +// It is even the case that blocks are expressions, evaluating to the last expression they contain. +fn compute_stuff(x: i32) -> i32 { + let y = { let z = x*x; z + 14 }; + y*y +} + // Let us now refactor `vec_min`. fn vec_min(v: Vec) -> NumberOrNothing { //@ Remember that helper function `min_i32`? Rust allows us to define such helper functions *inside* other diff --git a/src/part04.rs b/src/part04.rs index 9a1d22a..5c89466 100644 --- a/src/part04.rs +++ b/src/part04.rs @@ -119,7 +119,9 @@ fn mutable_borrow_demo() { /* println!("The first element is: {}", *first); */ /* BAD! */ } //@ `&mut` is the operator to create a mutable borrow. We have to mark `v` as mutable in order to create such a -//@ borrow. Because the borrow passed to `vec_inc` only lasts as long as the function call, we can still call +//@ borrow: Even though we completely own `v`, Rust tries to protect us from accidentally mutating things. +//@ Hence owned variables that you intend to mutate, have to be annotated with `mut`. +//@ Because the borrow passed to `vec_inc` only lasts as long as the function call, we can still call //@ `vec_inc` on the same vector twice: The durations of the two borrows do not overlap, so we never have more //@ than one mutable borrow. However, we can *not* create a shared borrow that spans a call to `vec_inc`. Just try //@ enabling the commented-out lines, and watch Rust complain. This is because `vec_inc` could mutate diff --git a/src/part05.rs b/src/part05.rs index b593360..6d2d813 100644 --- a/src/part05.rs +++ b/src/part05.rs @@ -48,8 +48,10 @@ impl BigInt { } // We can convert any vector of digits into a number, by removing trailing zeros. The `mut` - // declaration for `v` here is just like the one in `let mut ...`, it says that we will locally - // change the vector `v`. + // declaration for `v` here is just like the one in `let mut ...`: We completely own `v`, but Rust + // still asks us to make our intention of modifying it explicit. This `mut` is *not* part of the + // type of `from_vec` - the caller has to give up ownership of `v` anyway, so they don't care anymore + // what you do to it. // // **Exercise 05.1**: Implement this function. // diff --git a/src/part08.rs b/src/part08.rs index 7a9c093..d6b6782 100644 --- a/src/part08.rs +++ b/src/part08.rs @@ -26,7 +26,9 @@ fn overflowing_add(a: u64, b: u64, carry: bool) -> (u64, bool) { if sum >= a { // The addition did not overflow.
// **Exercise 08.1**: Write the code to handle adding the carry in this case. - unimplemented!() + let sum_total = u64::wrapping_add(sum, if carry { 1 } else { 0 }); /*@@*/ + let had_overflow = sum_total < sum; /*@@*/ + (sum_total, had_overflow) /*@@*/ } else { // Otherwise, the addition *did* overflow. It is impossible for the addition of the carry // to overflow again, as we are just adding 0 or 1. @@ -82,7 +84,10 @@ impl ops::Add for BigInt { carry = new_carry; /*@*/ } // **Exercise 08.2**: Handle the final `carry`, and return the sum. - unimplemented!() + if carry { /*@@*/ + result_vec.push(1); /*@@*/ + } /*@@*/ + BigInt { data: result_vec } /*@@*/ } } diff --git a/src/part09.rs b/src/part09.rs index 2a46d77..5a4f666 100644 --- a/src/part09.rs +++ b/src/part09.rs @@ -5,7 +5,7 @@ use part05::BigInt; //@ In the following, we will look into the iterator mechanism of Rust and make our `BigInt` compatible //@ with the `for` loops. Of course, this is all about implementing certain traits again. In particular, -//@ an iterator is something that implements the `Iterator` trait. As you can see in [the documentation](http://doc.rust-lang.org/beta/std/iter/trait.Iterator.html), +//@ an iterator is something that implements the `Iterator` trait. As you can see in [the documentation](http://doc.rust-lang.org/stable/std/iter/trait.Iterator.html), //@ this trait mandates a single function `next` returning an `Option`, where `Item` is an //@ associated type chosen by the implementation. (There are many more methods provided for `Iterator`, //@ but they all have default implementations, so we don't have to worry about them right now.) @@ -121,7 +121,7 @@ fn iter_invalidation_demo() { // ## Iterator conversion trait //@ If you closely compare the `for` loop in `main` above, with the one in `part06::vec_min`, you will notice that we were able to write //@ `for e in v` earlier, but now we have to call `iter`. Why is that? Well, the `for` sugar is not actually tied to `Iterator`. -//@ Instead, it demands an implementation of [`IntoIterator`](http://doc.rust-lang.org/beta/std/iter/trait.IntoIterator.html). +//@ Instead, it demands an implementation of [`IntoIterator`](http://doc.rust-lang.org/stable/std/iter/trait.IntoIterator.html). //@ That's a trait of types that provide a *conversion* function into some kind of iterator. These conversion traits are a frequent //@ pattern in Rust: Rather than demanding that something is an iterator, or a string, or whatever; one demands that something //@ can be converted to an iterator/string/whatever. This provides convenience similar to overloading of functions: The function @@ -146,4 +146,4 @@ impl<'a> IntoIterator for &'a BigInt { //@ then you will obtain ownership of the elements during the iteration - and destroy the vector in the process. We actually did that in //@ `part01::vec_min`, but we did not care. You can write `for e in &v` or `for e in v.iter()` to avoid this. -//@ [index](main.html) | [previous](part08.html) | [next](main.html) +//@ [index](main.html) | [previous](part08.html) | [next](part10.html) diff --git a/src/part10.rs b/src/part10.rs index 53fb0b3..e0481a8 100644 --- a/src/part10.rs +++ b/src/part10.rs @@ -1,53 +1,144 @@ -// Rust-101, Part 09: Closures (WIP) -// ================================= +// Rust-101, Part 10: Closures +// =========================== use std::io::prelude::*; -use std::io; - +use std::{fmt,io}; use part05::BigInt; +//@ Assume we want to write a function that does *something* on, say, every digit of a `BigInt`. +//@ We will then need a way to express the action that we want to be taken, and to pass this to +//@ our function. In Rust, a natural first attempt to express this is to have a trait for it. + +// So, let us define a trait that demands that the type provides some method `do_action` on digits. +//@ This immediately raises the question: How do we pass `self` to that function? Owned, shared borrow, +//@ or mutable borrow? The typical strategy to answer this question is to use the strongest +//@ type that still works. Certainly, passing `self` in owned form does not work: Then the function +//@ would consume `self`, and we could not call it again, on the second digit. So let's go with a mutable borrow. trait Action { fn do_action(&mut self, digit: u64); } +// Now we can write a function that takes some `a` of a type `A` such that we can call `do_action` on `a`, passing it every digit. impl BigInt { fn act_v1(&self, mut a: A) { + //@ Remember that the `mut` above is just an annotation to Rust, telling it that we're okay with `a` being mutated. + //@ Calling `do_action` on `a` takes a mutable borrow, so mutation could indeed happen. for digit in self { a.do_action(digit); } } } +//@ As the next step, we need to come up with some action, and write an appropriate implementation of `Action` for it. +//@ So, let's say we want to print every digit, and to make this less boring, we want the digits to be prefixed by some +//@ arbitrary string. `do_action` has to know this string, so we store it in `self`. struct PrintWithString { prefix: String, } impl Action for PrintWithString { + // Here we perform performs the actual printing of the prefix and the digit. We're not making use of our ability to + // change `self` here, but we could replace the prefix if we wanted. fn do_action(&mut self, digit: u64) { println!("{}{}", self.prefix, digit); } } +// Finally, this function takes a `BigInt` and a prefix, and prints the digits with the given prefix. +//@ It does so by creating an instance of `PrintWithString`, giving it the prefix, and then passing that to `act_v1`. +//@ Since `PrintWithString` implements `Action`, Rust now knows what to do. fn print_with_prefix_v1(b: &BigInt, prefix: String) { let my_action = PrintWithString { prefix: prefix }; b.act_v1(my_action); } +// Here's a small main function, demonstrating the code above in action. Remember to edit `main.rs` to run it. pub fn main() { let bignum = BigInt::new(1 << 63) + BigInt::new(1 << 16) + BigInt::new(1 << 63); print_with_prefix_v1(&bignum, "Digit: ".to_string()); } +// ## Closures +//@ Now, as it turns out, this pattern of describing some form of an action, that can carry in additional data, is very common. +//@ In general, this is called a *closure*. Closures take some arguments and produce a result, and they have an *environment* +//@ they can use, which corresponds to the type `PrintWithString` (or any other type implementing `Action`). Again we have the +//@ choice of passing this environment in owned or borrowed form, so there are three traits for closures in Rust: `Fn`-closures +//@ get a shared borrow, `FnMut`-closures get a mutable borrow, and `FnOnce`-closures consume their environment (and can hence +//@ be called only once). The syntax for a closure trait which takes arguments of type `T1`, `T2`, ... and returns something +//@ of type `U` is `Fn(T1, T2, ...) -> U`. + +// This defines `act` very similar to above, but now we demand `A` to be the type of a closure that mutates its borrowed environment, +// takes a digit, and returns nothing. impl BigInt { fn act(&self, mut a: A) { for digit in self { + // We can call closures as if they were functions - but really, what's happening here is translated to essentially what we wrote above, in `act_v1`. a(digit); } } } +// Now that we saw how to write a function that operates on closures, let's see how to write a closure. pub fn print_with_prefix(b: &BigInt, prefix: String) { + //@ The syntax for closures is `|arg1, arg2, ...| code`. Notice that the closure can reference variables like `prefix` that it did not + //@ take as argument - variables that happen to be present *outside* of the closure. We say that the closure *captures* + //@ variables. Rust will now automatically create a type (like `PrintWithStruct`) for the environment of the closure + //@ with fields for every captured variable, implement the closure trait for this type such that the action performed + //@ is given by the code of the closure, and finally it will instantiate the environment type here at the definition site + //@ of the closure and fill it appropriately. b.act(|digit| println!("{}{}", prefix, digit) ); } +// You can change `main` to call this function, and you should notice - nothing, no difference in behavior. +// But we wrote much less boilerplate code! + +// Remember that we decided to use the `FnMut` trait above? This means our closure could actually mutate its environment. +// For example, we can use that to count the digits as they are printed. +pub fn print_and_count(b: &BigInt) { + let mut count: usize = 0; + //@ This time, the environment will contain a field of type `&mut usize`, that will be initialized with a mutable borrow of + //@ `count`. The closure, since it mutably borrows its environment, is able to access this field and mutate `count` + //@ through it. Once `act` returns, the closure is destroyed and the borrow of `count` ends. Because closures compile down + //@ to normal types, all the borrow checking continues to work as usually, and we cannot accidentally leak a closure somewhere + //@ that still contains, in its environment, a borrow that has ended. + b.act(|digit| { println!("{}: {}", count, digit); count = count +1; } ); + println!("There are {} digits", count); +} + +// ## Fun with iterators and closures +//@ If you are familiar with functional languages, you are probably aware that one can have lots of fun with iterators and closures. +//@ Rust provides a whole lot of methods on iterators that allow us to write pretty functional-style list manipulation. + +// Let's say we want to write a function that increments every entry of a `Vec` by some number, then looks for numbers larger than some threshold, and prints them. +fn inc_print_even(v: &Vec, offset: i32, threshold: i32) { + //@ `map` takes a closure that is applied to every element of the iterator. `filter` removes elements + //@ from the iterator that do not pass the test given by the closure. + //@ + //@ Since all these closures compile down to the pattern described above, there is actually no heap allocation going on here. This makes + //@ closures very efficient, and it makes optimization fairly trivial: The resulting code will look like you hand-rolled the loop in C. + for i in v.iter().map(|n| n + offset).filter(|n| *n > threshold) { + println!("{}", i); + } +} + +// Sometimes it is useful to know both the position of some element in a list, and its value. That's where the `enumerate` function helps. +fn print_enumerated(v: &Vec) { + //@ `enumerate` turns an iterator over `T` into an iterator over `(usize, T)`, where the first element just counts the position in the iterator. + //@ We can do pattern matching right in the loop header to obtain names for both the position, and the value. + for (i, t) in v.iter().enumerate() { + println!("Position {}: {}", i, t); + } +} + +// And as a final example, one can also collect all elements of an iterator, and put them, e.g., in a vector. +fn filter_vec_by_divisor(v: &Vec, divisor: i32) -> Vec { + //@ Here, the return type of `collect` is inferred based on the return type of our function. In general, it can return anything implementing + //@ [`FromIterator`](http://doc.rust-lang.org/stable/std/iter/trait.FromIterator.html). + v.iter().filter(|n| *n % divisor == 0).collect() +} + +// **Exercise 10.1**: Look up the [documentation of `Iterator`](http://doc.rust-lang.org/stable/std/iter/trait.Iterator.html) to learn about more functions +// that can act on iterators. Try using some of them. What about a function that sums the even numbers of an iterator? Or a function that computes the +// product of those numbers that sit at odd positions? A function that checks whether a vector contains a certain number? Whether all numbers are +// smaller than some threshold? Be creative! //@ [index](main.html) | [previous](part08.html) | [next](main.html) diff --git a/workspace/src/part01.rs b/workspace/src/part01.rs index 1b2460c..ed6717c 100644 --- a/workspace/src/part01.rs +++ b/workspace/src/part01.rs @@ -24,6 +24,12 @@ fn number_or_default(n: NumberOrNothing, default: i32) -> i32 { } } +// It is even the case that blocks are expressions, evaluating to the last expression they contain. +fn compute_stuff(x: i32) -> i32 { + let y = { let z = x*x; z + 14 }; + y*y +} + // Let us now refactor `vec_min`. fn vec_min(v: Vec) -> NumberOrNothing { fn min_i32(a: i32, b: i32) -> i32 { diff --git a/workspace/src/part05.rs b/workspace/src/part05.rs index 78113b7..65f6f7d 100644 --- a/workspace/src/part05.rs +++ b/workspace/src/part05.rs @@ -26,8 +26,10 @@ impl BigInt { } // We can convert any vector of digits into a number, by removing trailing zeros. The `mut` - // declaration for `v` here is just like the one in `let mut ...`, it says that we will locally - // change the vector `v`. + // declaration for `v` here is just like the one in `let mut ...`: We completely own `v`, but Rust + // still asks us to make our intention of modifying it explicit. This `mut` is *not* part of the + // type of `from_vec` - the caller has to give up ownership of `v` anyway, so they don't care anymore + // what you do to it. // // **Exercise 05.1**: Implement this function. // diff --git a/workspace/src/part10.rs b/workspace/src/part10.rs index 570e851..9fd7642 100644 --- a/workspace/src/part10.rs +++ b/workspace/src/part10.rs @@ -1,15 +1,17 @@ -// Rust-101, Part 09: Closures (WIP) -// ================================= +// Rust-101, Part 10: Closures +// =========================== use std::io::prelude::*; -use std::io; - +use std::{fmt,io}; use part05::BigInt; + +// So, let us define a trait that demands that the type provides some method `do_action` on digits. trait Action { fn do_action(&mut self, digit: u64); } +// Now we can write a function that takes some `a` of a type `A` such that we can call `do_action` on `a`, passing it every digit. impl BigInt { fn act_v1(&self, mut a: A) { for digit in self { @@ -23,30 +25,76 @@ struct PrintWithString { } impl Action for PrintWithString { + // Here we perform performs the actual printing of the prefix and the digit. We're not making use of our ability to + // change `self` here, but we could replace the prefix if we wanted. fn do_action(&mut self, digit: u64) { println!("{}{}", self.prefix, digit); } } +// Finally, this function takes a `BigInt` and a prefix, and prints the digits with the given prefix. fn print_with_prefix_v1(b: &BigInt, prefix: String) { let my_action = PrintWithString { prefix: prefix }; b.act_v1(my_action); } +// Here's a small main function, demonstrating the code above in action. Remember to edit `main.rs` to run it. pub fn main() { let bignum = BigInt::new(1 << 63) + BigInt::new(1 << 16) + BigInt::new(1 << 63); print_with_prefix_v1(&bignum, "Digit: ".to_string()); } +// ## Closures + +// This defines `act` very similar to above, but now we demand `A` to be the type of a closure that mutates its borrowed environment, +// takes a digit, and returns nothing. impl BigInt { fn act(&self, mut a: A) { for digit in self { + // We can call closures as if they were functions - but really, what's happening here is translated to essentially what we wrote above, in `act_v1`. a(digit); } } } +// Now that we saw how to write a function that operates on closures, let's see how to write a closure. pub fn print_with_prefix(b: &BigInt, prefix: String) { b.act(|digit| println!("{}{}", prefix, digit) ); } +// You can change `main` to call this function, and you should notice - nothing, no difference in behavior. +// But we wrote much less boilerplate code! + +// Remember that we decided to use the `FnMut` trait above? This means our closure could actually mutate its environment. +// For example, we can use that to count the digits as they are printed. +pub fn print_and_count(b: &BigInt) { + let mut count: usize = 0; + b.act(|digit| { println!("{}: {}", count, digit); count = count +1; } ); + println!("There are {} digits", count); +} + +// ## Fun with iterators and closures + +// Let's say we want to write a function that increments every entry of a `Vec` by some number, then looks for numbers larger than some threshold, and prints them. +fn inc_print_even(v: &Vec, offset: i32, threshold: i32) { + for i in v.iter().map(|n| n + offset).filter(|n| *n > threshold) { + println!("{}", i); + } +} + +// Sometimes it is useful to know both the position of some element in a list, and its value. That's where the `enumerate` function helps. +fn print_enumerated(v: &Vec) { + for (i, t) in v.iter().enumerate() { + println!("Position {}: {}", i, t); + } +} + +// And as a final example, one can also collect all elements of an iterator, and put them, e.g., in a vector. +fn filter_vec_by_divisor(v: &Vec, divisor: i32) -> Vec { + v.iter().filter(|n| *n % divisor == 0).collect() +} + +// **Exercise 10.1**: Look up the [documentation of `Iterator`](http://doc.rust-lang.org/stable/std/iter/trait.Iterator.html) to learn about more functions +// that can act on iterators. Try using some of them. What about a function that sums the even numbers of an iterator? Or a function that computes the +// product of those numbers that sit at odd positions? A function that checks whether a vector contains a certain number? Whether all numbers are +// smaller than some threshold? Be creative! -- 2.30.2