Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Rust: imperative language 2.0

Masaki Hara
November 10, 2019

Rust: imperative language 2.0

Although Rust incorporates many methodologies from functional programming, it can rather be "an imperative programming language 2.0", considering its familiarity with mutable references. In this talk, I'll describe Rust in terms of mutable references.

Rustは関数型プログラミングの手法を多く取り入れていますが、ミュータブルリファレンスを多用するというその性質から、Rustはむしろ「手続き型言語2.0」であるということもできるでしょう。 本講演では、ミュータブルリファレンスに注目してRustの特徴を説明します。

Masaki Hara

November 10, 2019
Tweet

More Decks by Masaki Hara

Other Decks in Programming

Transcript

  1. 2019/11/10 “Rust: Imperative Language 2.0” 1 Rust: Imperative Language 2.0

    Masaki Hara (@qnighy) Software Engineer at Wantedly, Inc. 2019/11/10 fpc2019japan
  2. 2019/11/10 “Rust: Imperative Language 2.0” 2 Myself • Software Engineer

    at Wantedly • Ruby on Rails and Golang • Wantedly People (Business card scanner & SNS) • Current interest: Rust • Former interests: formal methods, competitive programming, math, ...
  3. 2019/11/10 “Rust: Imperative Language 2.0” 4 Table of contents •

    Rust • Lifetime story • Shared XOR mutable • Ownership • Lifetimes • References as locks • Advanced topics
  4. 2019/11/10 “Rust: Imperative Language 2.0” 7 Rust: https://www.rust-lang.org/ • Capable

    of being nearly as low-level as C • Nearly as fast as C – see Benchmarks Game results. • Safe abstractions – guaranteed freedom from UB. Part I > Rust
  5. 2019/11/10 “Rust: Imperative Language 2.0” 8 Rust: https://www.rust-lang.org/ • Best-effort

    safeguard for memory-leak freedom, panic- freedom, portability, language forward-compatibility and cross-compilability. • Functional-esque abstractions – parametric polymorphism (generics), ADT (enums), type classes (traits) • Language designs focused on consistency and orthogonality. Part I > Rust
  6. 2019/11/10 “Rust: Imperative Language 2.0” 9 Rust: https://www.rust-lang.org/ • Officially

    distributed tools – everyone uses the same tool • Rustup – compiler version manager and installer • Cargo – package manager and build tool • Rustfmt – formatter • Clippy – linter • RLS – language server (editor & IDE support) • Great effort on documentation • Great effort on community inclusion Part I > Rust
  7. 2019/11/10 “Rust: Imperative Language 2.0” 10 Rust: https://www.rust-lang.org/ • It

    achieves performance and safety at the same time thanks to references, ownership and lifetime. &'a T &'a mut T Box<T> References Smart pointers Part I > Rust
  8. 2019/11/10 “Rust: Imperative Language 2.0” 11 Rust: https://www.rust-lang.org/ • It

    achieves performance and safety at the same time thanks to references, ownership and lifetime. &'a T &'a mut T Box<T> Uncopyable (i.e. ownership is managed) Part I > Rust
  9. 2019/11/10 “Rust: Imperative Language 2.0” 12 Rust: https://www.rust-lang.org/ • It

    achieves performance and safety at the same time thanks to references, ownership and lifetime. &'a T &'a mut T Box<T> Lifetimes Part I > Rust
  10. 2019/11/10 “Rust: Imperative Language 2.0” 13 Rust: https://www.rust-lang.org/ • It

    achieves performance and safety at the same time thanks to references, ownership and lifetime. &T &mut T Box<T> Part I > Rust
  11. 2019/11/10 “Rust: Imperative Language 2.0” 14 Rust good points •

    They’re classified as: Great ecosystems included Not unique but advanced Almost inherent to Rust (for now) • rustfmt ← gofmt • clippy ← flake8 • Cargo ← npm • rustup ← rbenv • ADT • Traits (type classes) • RAII • Move semantics • Ownership • Lifetimes • Shared XOR mutable Part I > Rust
  12. 2019/11/10 “Rust: Imperative Language 2.0” 15 Rust good points •

    They’re classified as: Great ecosystems included Not unique but advanced Almost inherent to Rust (for now) • rustfmt ← gofmt • clippy ← flake8 • Cargo ← npm • rustup ← rbenv • ADT • Traits (type classes) • RAII • Move semantics • Ownership • Lifetimes • Shared XOR mutable This talk’s focus Part I > Rust
  13. 2019/11/10 “Rust: Imperative Language 2.0” 17 Lifetime story Ownership Shared

    XOR mutable Compiler optimization Easy-to-reason behavior Fearless concurrency Lifetime Less allocation Part II > Lifetime story
  14. 2019/11/10 “Rust: Imperative Language 2.0” 18 Lifetime story Ownership Shared

    XOR mutable Compiler optimization Easy-to-reason behavior Fearless concurrency Lifetime Less allocation Performance is important, but this talk doesn’t focus on it. Part II > Lifetime story
  15. 2019/11/10 “Rust: Imperative Language 2.0” 19 Lifetime story Ownership Shared

    XOR mutable Compiler optimization Easy-to-reason behavior Fearless concurrency Lifetime Less allocation Part II > Lifetime story
  16. 2019/11/10 “Rust: Imperative Language 2.0” 20 Lifetime story Ownership Shared

    XOR mutable Compiler optimization Easy-to-reason behavior Fearless concurrency Lifetime Less allocation Part II > Lifetime story
  17. 2019/11/10 “Rust: Imperative Language 2.0” 21 Example 1: shallow clone

    a = [[0] * 2] * 2 a[0][0] = 100 print(a) # [[100, 0], [100, 0]] Python Part II > Lifetime story
  18. 2019/11/10 “Rust: Imperative Language 2.0” 22 Example 1: shallow clone

    a = [[0] * 2] * 2 a[0][0] = 100 print(a) # [[100, 0], [100, 0]] Python Part II > Lifetime story
  19. 2019/11/10 “Rust: Imperative Language 2.0” 23 Example 1: shallow clone

    • Non-reproducing mimic let mut a = vec![vec![0; 2]; 2]; a[0][0] = 100; eprintln!("{:?}", a); // [[100, 0], [0, 0]] Rust Part II > Lifetime story
  20. 2019/11/10 “Rust: Imperative Language 2.0” 24 Example 1: shallow clone

    • Non-reproducing mimic let mut a = vec![vec![0; 2]; 2]; a[0][0] = 100; eprintln!("{:?}", a); // [[100, 0], [0, 0]] Rust Part II > Lifetime story
  21. 2019/11/10 “Rust: Imperative Language 2.0” 25 Example 1: shallow clone

    • Reproducing mimic let a = vec![Rc::new(RefCell::new(vec![0; 2])); 2]; (&a[0]).borrow_mut()[0] = 100; eprintln!("{:?}", a); // [RefCell { value: [100, 0] }, RefCell { value: [100, 0] }] Rust Part II > Lifetime story
  22. 2019/11/10 “Rust: Imperative Language 2.0” 26 Example 1: shallow clone

    • Reproducing mimic let a = vec![Rc::new(RefCell::new(vec![0; 2])); 2]; (&a[0]).borrow_mut()[0] = 100; eprintln!("{:?}", a); // [RefCell { value: [100, 0] }, RefCell { value: [100, 0] }] Rust Part II > Lifetime story
  23. 2019/11/10 “Rust: Imperative Language 2.0” 27 Example 1: shallow clone

    • Reproducing mimic let a = vec![Rc::new(RefCell::new(vec![0; 2])); 2]; (&a[0]).borrow_mut()[0] = 100; eprintln!("{:?}", a); // [RefCell { value: [100, 0] }, RefCell { value: [100, 0] }] Rust RefCell opts into this behavior Part II > Lifetime story
  24. 2019/11/10 “Rust: Imperative Language 2.0” 28 Example 1: shallow clone

    • Reproducing mimic let a = vec![Rc::new(RefCell::new(vec![0; 2])); 2]; (&a[0]).borrow_mut()[0] = 100; eprintln!("{:?}", a); // [RefCell { value: [100, 0] }, RefCell { value: [100, 0] }] Rust RefCell opts into this behavior Part II > Lifetime story
  25. 2019/11/10 “Rust: Imperative Language 2.0” 30 What was the problem?

    a = [[0] * 2] * 2 a[0][0] = 100 print(a) # [[100, 0], [100, 0]] Python Part III > Shared XOR mutable
  26. 2019/11/10 “Rust: Imperative Language 2.0” 31 What was the problem?

    a = [[0] * 2] * 2 a[0][0] = 100 print(a) # [[100, 0], [100, 0]] Python Part III > Shared XOR mutable
  27. 2019/11/10 “Rust: Imperative Language 2.0” 32 What was the problem?

    •Mutation is the problem a = [[0] * 2] * 2 a[0][0] = 100 print(a) # [[100, 0], [100, 0]] Python Part III > Shared XOR mutable
  28. 2019/11/10 “Rust: Imperative Language 2.0” 33 What was the problem?

    •Mutation is the problem →declarative programming Part III > Shared XOR mutable
  29. 2019/11/10 “Rust: Imperative Language 2.0” 34 What was the problem?

    •Mutation is the problem →declarative programming •Mutating a shared reference is the problem →imperative programming 2.0! Part III > Shared XOR mutable
  30. 2019/11/10 “Rust: Imperative Language 2.0” 35 Shared XOR mutable •A

    reference can be shared with others. •It can be mutable (writable). •But not both. Part III > Shared XOR mutable
  31. 2019/11/10 “Rust: Imperative Language 2.0” 36 Shared XOR mutable •A

    reference can be shared with others. •It can be mutable (writable). •But not both. &T &mut T Part III > Shared XOR mutable
  32. 2019/11/10 “Rust: Imperative Language 2.0” 38 flock(2) For reading a

    file For writing to a file Part III > Shared XOR mutable
  33. 2019/11/10 “Rust: Imperative Language 2.0” 40 PostgreSQL row-level locking (simplified)

    Requested Lock Mode Current Lock Mode FOR SHARE FOR UPDATE FOR SHARE X FOR UPDATE X X Part III > Shared XOR mutable
  34. 2019/11/10 “Rust: Imperative Language 2.0” 41 Shared XOR mutable •A

    reference can be shared with others. •It can be mutable (writable). •But not both. Rust applies the general principle for shareable resources to memory regions. Part III > Shared XOR mutable
  35. 2019/11/10 “Rust: Imperative Language 2.0” 43 Detecting copies • Copying

    mutable references may break the shared XOR mutable principle. fn dup(x: &mut i32) -> (&mut i32, &mut i32) { (x, x) } Rust Part IV > Ownership
  36. 2019/11/10 “Rust: Imperative Language 2.0” 44 Detecting copies • That

    means, we cannot copy a general type T. (unless T: Copy is specified) fn dup<T>(x: T) -> (T, T) { (x, x) } Rust Linear type by default (More accurately this is an affine type. We can drop values at any time) Part IV > Ownership
  37. 2019/11/10 “Rust: Imperative Language 2.0” 46 Sequential mutation • Ownership

    forbids multiple uses. • This is too restrictive. let mut a = Vec::new(); a.push(42); a.push(84); eprintln!("{:?}", a); Rust push mutates a push mutates a eprintln! reads a Part V > Lifetimes
  38. 2019/11/10 “Rust: Imperative Language 2.0” 47 Sequential mutation • This

    code is OK because a is sequentially mutated. • Ensure a is unique at a time let mut a = Vec::new(); a.push(42); a.push(84); eprintln!("{:?}", a); Rust &'a mut Vec<i32> &'b mut Vec<i32> &'c Vec<i32> 'a 'b 'c Part V > Lifetimes
  39. 2019/11/10 “Rust: Imperative Language 2.0” 49 Example 2: just readonly

    • Is this a value class? class Revision { constructor( readonly name: string, readonly files: ReadonlyMap<string, string>, ) { } } TypeScript Part VI > References as locks
  40. 2019/11/10 “Rust: Imperative Language 2.0” 50 Example 2: just readonly

    • Unexpected mutation const worktree: Map<string, string> = new Map(); worktree.set("README.md", "foo"); const rev1 = new Revision("rev1", worktree); worktree.set("a.ts", ""); const rev2 = new Revision("rev2", worktree); TypeScript Part VI > References as locks
  41. 2019/11/10 “Rust: Imperative Language 2.0” 51 Freedom from third-party mutation

    • ReadonlyArray<T> may be modified from another owner. • T[] may be modified from another owner too. • (There’s Object.freeze, but it’s irrelevant to types) Part VI > References as locks
  42. 2019/11/10 “Rust: Imperative Language 2.0” 52 Freedom from third-party mutation

    • &T cannot be modified from another owner. • &mut T cannot be modified from another owner too. • Acquiring &T or &mut T is like acquiring locks statically. Part VI > References as locks
  43. 2019/11/10 “Rust: Imperative Language 2.0” 53 Freedom from third-party mutation

    • &T cannot be modified from another owner. • &mut T cannot be modified from another owner too. • Acquiring &T or &mut T is like acquiring locks statically. Rust references are easy to reason about. Part VI > References as locks
  44. 2019/11/10 “Rust: Imperative Language 2.0” 54 Easy to reason about

    → optimization • Famous XOR-swap is optimized away to simple moves. pub fn swap(x: &mut u32, y: &mut u32) { *x ^= *y; *y ^= *x; *x ^= *y; } Rust Part VI > References as locks
  45. 2019/11/10 “Rust: Imperative Language 2.0” 55 Easy to reason about

    → optimization • Famous XOR-swap is optimized away to simple moves. …in some old Rust versions. • Rust noalias annotations are sometimes too aggressive that it occasionally hits LLVM bugs. • Current version of Rust (1.39.0) disables noalias annotations for &mut references. Part VI > References as locks
  46. 2019/11/10 “Rust: Imperative Language 2.0” 56 Easy to reason about

    → optimization • Values behind &T is constant across function calls: (optimized to always return 0) pub fn observe_diff(x: &i32, f: fn(i32)) -> i32 { let a = *x; f(a); a - *x } Rust Part VI > References as locks
  47. 2019/11/10 “Rust: Imperative Language 2.0” 57 Almost functionally interpretable •

    Actions on &mut references are almost functionally interpretable. pub fn f(v: &mut Vec<i32>, x: i32); Rust f :: [Int] -> Int -> [Int] Haskell Part VI > References as locks
  48. 2019/11/10 “Rust: Imperative Language 2.0” 59 Deep immutability • &T

    is deep-immutable by default. This is a mere consequence of the shared XOR mutable principle. &'a mut &'b mut T &'a &'b mut T &'a mut &'b T &'a &'b T &'b T &'b T &'a T &'a mut T Part VII > Advanced topics
  49. 2019/11/10 “Rust: Imperative Language 2.0” 60 Spatial Splitting • &mut

    references are often temporally split. let mut a = Vec::new(); a.push(42); a.push(84); eprintln!("{:?}", a); Rust Part VII > Advanced topics
  50. 2019/11/10 “Rust: Imperative Language 2.0” 61 Spatial Splitting • They

    are sometimes spatially split too. let mut x = (1, 2); std::mem::swap(&mut x.0, &mut x.1); eprintln!("{:?}", x); Rust Part VII > Advanced topics
  51. 2019/11/10 “Rust: Imperative Language 2.0” 62 Spatial Splitting • They

    are sometimes spatially split too. let mut x = (1, 2); std::mem::swap(&mut x.0, &mut x.1); eprintln!("{:?}", x); Rust Different parts of x are borrowed simultaneously. Part VII > Advanced topics
  52. 2019/11/10 “Rust: Imperative Language 2.0” 63 Spatial Splitting • They

    are sometimes spatially split too. • Structs/enums: Rust automatically detects borrowing of different fields. • Slices: there’s split_at_mut which does this explicitly . Part VII > Advanced topics
  53. 2019/11/10 “Rust: Imperative Language 2.0” 64 Concurrent mutations • We’ve

    avoided concurrent mutations until now. • They’re useful if used carefully: • Logging • Debugging • Manipulating graph-like structures • Generating unique IDs • More than simple paralellism • Essentially concurrent business logics Part VII > Advanced topics
  54. 2019/11/10 “Rust: Imperative Language 2.0” 65 Concurrent mutations • Interior

    mutability opts into concurrent mutations. • Interior mutability primitives Cell<T> Atomic* RefCell<T> RwLock<T> Mutex<T> Part VII > Advanced topics
  55. 2019/11/10 “Rust: Imperative Language 2.0” 66 Concurrent mutations • Interior

    mutability opts into concurrent mutations. • Interior mutability primitives Cell<T> Atomic* RefCell<T> RwLock<T> Mutex<T> Single-threaded Thread-safe Part VII > Advanced topics
  56. 2019/11/10 “Rust: Imperative Language 2.0” 67 Concurrent mutations • Interior

    mutability opts into concurrent mutations. • Interior mutability primitives Cell<T> Atomic* RefCell<T> RwLock<T> Mutex<T> Lockless Lockable Part VII > Advanced topics
  57. 2019/11/10 “Rust: Imperative Language 2.0” 68 Interior mutability • Interior

    mutability types are mutated through shared references. fn increment(counter: &Mutex<i32>) { let mut counter = counter.lock().unwrap(); *counter += 1; // automatically unlocked } Rust Part VII > Advanced topics
  58. 2019/11/10 “Rust: Imperative Language 2.0” 69 Interior mutability • Interior

    mutability types are mutated through shared references. fn increment(counter: &Mutex<i32>) { let mut counter = counter.lock().unwrap(); *counter += 1; // automatically unlocked } Rust Part VII > Advanced topics
  59. 2019/11/10 “Rust: Imperative Language 2.0” 70 Interior mutability with locks

    • RefCell<T>, Mutex<T>, RwLock<T> all put T behind locks. • Only one can reference its contents at a time. Mutex<i32> i32 42 Part VII > Advanced topics
  60. 2019/11/10 “Rust: Imperative Language 2.0” 71 Interior mutability with locks

    • RefCell<T>, Mutex<T>, RwLock<T> all put T behind locks. • Only one can reference its contents at a time. •→it still obeys shared XOR mutable rules. The container is shared. The contents are mutable. Part VII > Advanced topics
  61. 2019/11/10 “Rust: Imperative Language 2.0” 72 Interior mutability without locks

    • Cell<T>, Atomic* can be considered to do lock-mutate- unlock at once. • These are like limited versions of RefCell<T> / Mutex<T> optimized for specific use-cases (from users’ point of view). Part VII > Advanced topics
  62. 2019/11/10 “Rust: Imperative Language 2.0” 73 Reference-counted pointers • Rc<T>

    / Arc<T> are reference-counted smart pointers. • Pointee are immutable by default (shared XOR mutable!) • Often combined with interior mutability. This is analogous to usual “references” in many other programming languages. • When used without interior mutability, this works like purely functional data structure.
  63. 2019/11/10 “Rust: Imperative Language 2.0” 74 Table of contents •

    Rust • Lifetime story • Shared XOR mutable • Ownership • Lifetimes • References as locks • Advanced topics Thank you for listening!