Ownership

The following program is rejected

fn example3(x : String) -> String {
   let y = x;

   println!("{}",y);

   return x;
}

because

22 | fn example3(x : String) -> String {
   |             - move occurs because `x` has type `String`, which does not implement the `Copy` trait
23 |    let y = x;
   |            - value moved here
...
27 |    return x;
   |           ^ value used here after move

Rust applies by default the move semantics we know from C++. Unlike C++, Rust statically checks that there is no access to any variable that has been moved.

Like in C++, we can explicitly apply the copy semantics.

fn example3b(x : String) -> String {
   let y = x.clone();

   println!("{}",y);

   return x;
}

In general, we could simply always perform a (deep) copy (build a clone).

Can this be down automatically? See C++ where we can overload the assignment operator and copy constructor.

Yes! Rust uses overloading based on traits (more on traits further below).

#[derive(Clone,Copy)]
struct Rectangle {
    x : i32,
    y : i32
}

fn example4() {
    let p = Rectangle{x : 1, y : 2};
    let q = p;

   println!("{} {}",q.x, p.x);

}

Automatically derive the trait instances Clone and Copy (assignment) for Rectangle.
Implies a “copy” assignment operator for Rectangle

How Rust enforces ownership statically

Rust employs a “fancy” type system to control access to resources.

Let us revisit some of the earlier examples.

fn example3(x : String) -> String {
   // 1. x : String_Owner
   let y = x;
   // 2. y : String_Owner
   // 3. x : String_No_longer_the_owner
   // The type of x has changed to the above assignment.
   // Ownership is moved from the right-hand to the left-hand side.


   println!("{}",y); // Can access y, cause y is the owner.

   return x; // Cannot access x, cause x is no longer the owner.
}

Rust uses a form of a “linear” type system.

We find refined types such as String_Owner
The type of a variable may change, e.g. becomes String_No_longer_the_owner

Consider the following example where we explicitly build a clone.

fn example3b(x : String) -> String {
   // 1. x : String_Owner
   let y = x.clone();
   // 2. y : String_Owner
   // 3. x : String_Owner
   // We build a clone.
   // Hence, there is no ownership transfer.

   println!("{}",y); // Can access, y is the owner

   return x;         // Can access x is the owner
}

Consider the following example where we implicitly build a clone.

#[derive(Clone,Copy)]
struct Rectangle {
    x : i32,
    y : i32
}

fn example4() {
    let p = Rectangle{x : 1, y : 2};
    // 1. p : Rectangle_Owner
    let q = p; // "=" is overloaded, corresponds to let q= p.clone()
    // 2. q : Rectangle_Owner
    // 3. p : Rectangle_Onwer


   println!("{} {}",q.x, p.x); // Access okay

}

Borrowing

fn example6() {
    let p = Square{x : 1};
    let q = &p;

    println!("{} {}",q.x, p.x);

}

Borrow access to the value stored in p via a reference!

Borrowing in Rust must obey a number of rules.

Cannot change borrow values

fn example7() {
    let mut p = Square{x : 1};
    let q = &p;

    p.x = 2;
    println!("{} {}",q.x, p.x);
}

yields

cannot assign to `p.x` because it is borrowed
  --> overview.rs:68:5
   |
66 |     let q = &p;
   |             -- borrow of `p.x` occurs here
67 |
68 |     p.x = 2;
   |     ^^^^^^^ assignment to borrowed `p.x` occurs here
69 |     println!("{} {}",q.x, p.x);
   |                      --- borrow later used here

In detail, here is the reasoning carried out by the Rust type checker.

fn example7b() {
    let mut p = Square{x : 1};
    // 1. p Square_Owner
    let q = &p;
    // 2. q Square_Borrowed
    // 3. p Square_Owner_Borrowed

    p.x = 2; // Cannot overwrite a borrowed value!
    println!("{} {}",q.x, p.x);
}

The following works however.

fn example8() {
    let mut p = Square{x : 1};
    // 1. p Square_Owner
    {
     let q = &p;
     // 2. q Square_Borrowed
     // 3. p Square_Owner_Borrowed

        println!("{} {}",q.x, p.x);
        // read access is okay
    }
    // From here on we find
    // 4. p Square_Owner

    p.x = 2; // Can access p.x cause owner

    println!("{}",p.x);
}

Traits

Traits describe a collection of methods that share the same type.

Geometric objects examples

trait Shape {
    fn area(s : &Self) -> i32;
}

impl Shape for Rectangle {
    fn area(r : &Rectangle) -> i32 {
        return r.x * r.y;
    }
}

impl Shape for Square {
    fn area(s : &Square) -> i32 {
     return s.x * s.x;
    }
}

Self refers to the shared type
Self is an implicit parameter of the trait Shape
In essence, the trait Shape represents a predicate Shape(Self)
We use borrowing here to avoid copying

Summing up the area of two geometric objects.

fn sum_area<A:Shape,B:Shape>(x : &A, y : &B) -> i32 {
   return Shape::area(x) + Shape::area(y);
}


fn example9() {
    let r = Rectangle{x : 1, y : 2};
    let s = Square{x : 3};

    println!("{}",sum_area(&r,&s));

}

A:Shape is a type constraint and states that x implements the trait Shape
In standard logic notation written Shape(A)
Method calls are written Shape::area(x)

Traits are not types, traits are predicates/type constraints

Traits describe a collection of methods that share the same type
Traits are type constraints (predicates)

Recall

trait Shape {
    fn area(s : &Self) -> i32;
    }

impl Shape for Rectangle {
    fn area(r : &Rectangle) -> i32 {
        return r.x * r.y;
    }
}

Using some pseudo syntax, the above effectively represents the following.

// Not legal Rust.
// Highlights that Self is the implicit argument for each trait.
trait Shape(Self) {
    fn area(s : &Self) -> i32;
}

impl Shape(Rectangle) {
    fn area(r : &Rectangle) -> i32 {
        return r.x * r.y;
    }
}

Recall

fn sum_area<A:Shape,B:Shape>(x : &A, y : &B) -> i32 {
   return Shape::area(x) + Shape::area(y);
}

Using some pseudo syntax, the type of sum_area represents the following condition.

forall A, B. Shape(A) and Shape(B) => fn sum_area(x : &A, y : &B) -> i32

A and B are universal type parameters where
the predicates Shape(A) and Shape(B) must be satisfied.

Traits can have several (type) parameters

Consider

trait Add<T> {
    fn add(x : Self, y : T) -> Self;
}

impl Add<bool> for i32 {
    fn add(x : i32, y : bool) -> i32 {
        if y {
            return x;
        } else {
            return 0;
        }
    }
}

fn example_add() {
    println!("{}", <i32 as Add<bool>>::add(1, true));
    println!("{}", <i32 as Add<bool>>::add(2, false));
}

Add is a binary predicate
Using standard logic notation, written as Add(Self, T)
Via <i32 as Add<bool>> we select the instance Add(i32,bool)

Let’s be funny. We give a recast of the “shapes” example where we effectively ignore “Self”.

trait ShapeC<T> {
  fn area(s : &T) -> i32;
}

impl ShapeC<Rectangle> for Rectangle {
    fn area(s : &Rectangle) -> i32 {
        return s.x * s.y;
    }
}

impl ShapeC<Square> for Square {
    fn area(s : &Square) -> i32 {
        return s.x * s.x;
    }
}

fn sum_area_c<T,S>(x : &T, y : &S) -> i32 where T : ShapeC<T>, S : ShapeC<S> {
    return <T as ShapeC<T>>::area(x) + <S as ShapeC<S>>::area(y)
}


fn example9_c() {
    let r = Rectangle{x : 1, y : 2};
    let s = Square{x : 3};

    println!("\n rectangle area = {}", <Rectangle as ShapeC<Rectangle>>::area(&r));
    println!("{}",sum_area_c(&r,&s));

}

Traits - syntactic sugar for method calls

Rust introduces some syntactic sugar to make look method calls “nicer”.

Here’s the above example written using Rust’s “method” notation.

trait Shape2 {
    fn area2(&self) -> i32;
}

impl Shape2 for Rectangle {
    fn area2(&self) -> i32 {
        return self.x * self.y;
    }
}

impl Shape2 for Square {
    fn area2(&self) -> i32 {
     return self.x * self.x;
    }
}


fn sum_area2<A:Shape2,B:Shape2>(x : &A, y : &B) -> i32 {
   return x.area2() + y.area2();
}


fn example10() {
    let r = Rectangle{x : 1, y : 2};
    let s = Square{x : 3};

    println!("{}",sum_area2(&r,&s));

}

Dynamic traits are abstract types

Traits may seem like interfaces but they are not.

Interfaces
- Interfaces are types
- A value of an interface type implements the methods described by the interface
Traits
- Traits describe a collection of methods that share the same type
- Traits are type constraints

In Rust, we can represent interfaces via dynamic traits.

fn sum_area3(x : Box<dyn Shape2>, y : Box<dyn Shape2>) -> i32 {
    return x.area2() + y.area2();
}


fn example11() {
    let r = Box::new(Rectangle{x : 1, y : 2});
    let s = Box::new(Square{x : 3});

    println!("{}",sum_area3(r,s));

}

dyn Shape2 effectively represents an abstract type that implements the trait Shape2
In logical notation, dyn Shape2 corresponds to exists A. Shape2(A) => A
In essence, exists A. Shape2(A) => A represents an interface (in the Go or Java sense)
What does Box mean?
- The memory space of an interface cannot be statically computed
- It can either be a Rectangle or a Square (the size of the memory space occupied is different)
- Hence, we need to allocate the (interface) value on the heap.
- In Rust, this is reflected in the type via Box

Traits are translated via the dictionary-translation method

Traits describe a collection of methods that share the same type
Each trait translates to a “dictionary” that holds the method definitions

The dictionary-translation method by example for our running example “shapes”.

Translation of method implementations

impl Shape for Rectangle {
    fn area(r : &Rectangle) -> i32 {
        return r.x * r.y;
    }
}

impl Shape for Square {
    fn area(s : &Square) -> i32 {
     return s.x * s.x;
    }
}

translates to

fn area_rec(r : &Rectangle) -> i32 {
        return r.x * r.y;
}

fn area_sq(s : &Square) -> i32 {
        return s.x * s.x;
}

Replace traits by dictionaries plus method lookup

fn sum_area<A:Shape,B:Shape>(x : &A, y : &B) -> i32 {
   return Shape::area(x) + Shape::area(y);

}

translates to

fn sum_area_dict<A,B>(m1 : fn(&A) -> i32, m2 : fn(&B) -> i32, x : &A, y : &B) -> i32 {
    return m1(x) + m2(y);
}

Each predicate/trait is turned into a dictionary
Shape(A) is represented by m1 : fn(&A) -> i32

Insertion of dictionaries

The function call

sum_area(&r,&s)

translates to

sum_area_dict(area_rec, area_sq, &r, &s)

Data types and pattern matching in Rust

Data types

pub enum Exp {
    Int {
        val: i32
    },
    Plus {
        left: Box<Exp>,
        right: Box<Exp>
    },
    Mult{
        left: Box<Exp>,
        right: Box<Exp>
    },
}

Box required
Otherwise, recursive definition (without indirection)

Pattern matching

fn eval(e : &Exp) -> i32 {
    match e {
      Exp::Int { val } => return *val,
      Exp::Plus { left, right } => return eval(left) + eval(right),
      Exp::Mult { left, right } => return eval(left) * eval(right),
    }
}

Nested patterns

Check for “0 * right” and immediately return 0 instead of evaluating right.

fn eval2(e : &Exp) -> i32 {
    match e {
      Exp::Int { val } => return *val,
      Exp::Plus { left, right } => return eval(left) + eval(right),
      Exp::Mult { left, right } =>
            match **left {
                Exp::Int{val : 0} => return 0,
                _ => return eval(left) * eval(right)
            }
    }
}

Don’t care patterns

Patterns are tried from top to bottom.

Don’t care pattern _ matches all remaining cases.

// Behavior different from eval.
fn eval3(e : &Exp) -> i32 {
    match e {
      Exp::Plus { left, right } => return eval(left) + eval(right),
      Exp::Mult { left, right } => return eval(left) * eval(right),
      _ => return 1,
    }
}

Examples

fn example12() {
   {
       let e = Exp::Int { val : 1 };
       println!("{}", eval(&e));
   }

   {
       let e = Exp::Plus{left : Box::new(Exp::Int { val : 1 }), right : Box::new(Exp::Int { val : 2})};
       println!("{}", eval(&e));
   }
}

Conclusion

We have seen:

Ownership and borrowing
Overloading via traits
Data types and pattern matching

Complete source code

///////////////////////////////
// Ownership + Borrowing

fn example1(x : i32) -> i32 {
   let y = x;  // Local type inference.

   // y = 1;   // Variables are immutable by default.

  return x+y;
}


fn example2(x : i32) -> i32 {
   let mut y = x;  // Mutable variables must be declared explicitly.

   let z = y;

   y = 1;

  return x+y+z;
}


/*

Rust uses a form of a "linear" type system.
1. We find refined types such as String_Owner.
2. The type of a variable may change, e.g. becomes String_No_longer_the_owner


fn example3(x : String) -> String {
   // 1. x : String_Owner
   let y = x;
   // 2. y : String_Owner
   // 3. x : String_No_longer_the_owner
   // The type of x has changed to the above assignment.
   // Ownership is moved from the right-hand to the left-hand side.


   println!("{}",y); // Can access y, cause y is the owner.

   return x; // Cannot access x, cause x is no longer the owner.
}
*/


fn example3b(x : String) -> String {
   // 1. x : String_Owner
   let y = x.clone();
   // 2. y : String_Owner
   // 3. x : String_Owner
   // We build a clone.
   // Hence, there is no ownership transfer.

   println!("{}",y); // Can access, y is the owner

   return x;         // Can access x is the owner
}


#[derive(Clone,Copy)]
struct Rectangle {
    x : i32,
    y : i32
}

fn example4() {
    let p = Rectangle{x : 1, y : 2};
    // 1. p : Rectangle_Owner
    let q = p; // "=" is overloaded, corresponds to let q= p.clone()
    // 2. q : Rectangle_Owner
    // 3. p : Rectangle_Onwer


   println!("{} {}",q.x, p.x); // Access okay

}

struct Square {
    x : i32
}

fn example5() {
    let p = Square{x : 1};
    let q = &p;

    println!("{} {}",q.x, p.x);

}

fn example6() {
    let p = Square{x : 1};
    let q = &p;

    println!("{} {}",q.x, p.x);

}


/*
fn example7() {
    let mut p = Square{x : 1};
    let q = &p;

    p.x = 2;
    println!("{} {}",q.x, p.x);
}
*/


/*
fn example7b() {
    let mut p = Square{x : 1};
    // 1. p Square_Owner
    let q = &p;
    // 2. q Square_Borrowed
    // 3. p Square_Owner_Borrowed

    p.x = 2; // Cannot overwrite a borrowed value!
    println!("{} {}",q.x, p.x);
}
*/


fn example8() {
    let mut p = Square{x : 1};
    // 1. p Square_Owner
    {
     let q = &p;
     // 2. q Square_Borrowed
     // 3. p Square_Owner_Borrowed

        println!("{} {}",q.x, p.x);
        // read access is okay
    }
    // From here on we find
    // 4. p Square_Owner

    p.x = 2; // Can access p.x cause owner

    println!("{}",p.x);
}


//////////////////////////
// Traits

trait Shape {
    fn area(s : &Self) -> i32;
}

impl Shape for Rectangle {
    fn area(r : &Rectangle) -> i32 {
        return r.x * r.y;
    }
}

impl Shape for Square {
    fn area(s : &Square) -> i32 {
     return s.x * s.x;
    }
}

fn sum_area<A:Shape,B:Shape>(x : &A, y : &B) -> i32 {
   return Shape::area(x) + Shape::area(y);
}


fn example9() {
    let r = Rectangle{x : 1, y : 2};
    let s = Square{x : 3};

    println!("{}",sum_area(&r,&s));

}

// Method notation known from OO.

trait Shape2 {
    fn area2(&self) -> i32;
}

impl Shape2 for Rectangle {
    fn area2(&self) -> i32 {
        return self.x * self.y;
    }
}

impl Shape2 for Square {
    fn area2(&self) -> i32 {
     return self.x * self.x;
    }
}


fn sum_area2<A:Shape2,B:Shape2>(x : &A, y : &B) -> i32 {
   return x.area2() + y.area2();
}


fn example10() {
    let r = Rectangle{x : 1, y : 2};
    let s = Square{x : 3};

    println!("{}",sum_area2(&r,&s));

}


fn sum_area3(x : Box<dyn Shape2>, y : Box<dyn Shape2>) -> i32 {
    return x.area2() + y.area2();
}


fn example11() {
    let r = Box::new(Rectangle{x : 1, y : 2});
    let s = Box::new(Square{x : 3});

    println!("{}",sum_area3(r,s));

}

// Traits can have several (type) parameters


trait Add<T> {
    fn add(x : Self, y : T) -> Self;
}

impl Add<bool> for i32 {
    fn add(x : i32, y : bool) -> i32 {
        if y {
            return x;
        } else {
            return 0;
        }
    }
}

fn example_add() {
    println!("{}", <i32 as Add<bool>>::add(1, true));
    println!("{}", <i32 as Add<bool>>::add(2, false));
}


trait ShapeC<T> {
  fn area(s : &T) -> i32;
}

impl ShapeC<Rectangle> for Rectangle {
    fn area(s : &Rectangle) -> i32 {
        return s.x * s.y;
    }
}

impl ShapeC<Square> for Square {
    fn area(s : &Square) -> i32 {
        return s.x * s.x;
    }
}

fn sum_area_c<T,S>(x : &T, y : &S) -> i32 where T : ShapeC<T>, S : ShapeC<S> {
    return <T as ShapeC<T>>::area(x) + <S as ShapeC<S>>::area(y)
}


fn example9_c() {
    let r = Rectangle{x : 1, y : 2};
    let s = Square{x : 3};

    println!("\n rectangle area = {}", <Rectangle as ShapeC<Rectangle>>::area(&r));
    println!("{}",sum_area_c(&r,&s));

}

// Dictionary-translation

fn area_rec(r : &Rectangle) -> i32 {
        return r.x * r.y;
}

fn area_sq(s : &Square) -> i32 {
        return s.x * s.x;
}

fn sum_area_dict<A,B>(m1 : fn(&A) -> i32, m2 : fn(&B) -> i32, x : &A, y : &B) -> i32 {
    return m1(x) + m2(y);
}


fn example9_dict() {
    let r = Rectangle{x : 1, y : 2};
    let s = Square{x : 3};


    println!("{}",sum_area(&r,&s));

    // The call
    //    sum_area(&r,&s)
    // translates to

    println!("{}",sum_area_dict(area_rec, area_sq, &r, &s));
}


////////////////////////////////////////////////
// Data types and pattern matching in Rust

pub enum Exp {
    Int {
        val: i32
    },
    Plus {
        left: Box<Exp>,
        right: Box<Exp>
    },
    Mult{
        left: Box<Exp>,
        right: Box<Exp>
    },
}

fn eval(e : &Exp) -> i32 {
    match e {
      Exp::Int { val } => return *val,
      Exp::Plus { left, right } => return eval(left) + eval(right),
      Exp::Mult { left, right } => return eval(left) * eval(right),
    }
}

// Nested patterns
// Check for "0 * right" and immediately return 0 instead of evaluating right.
fn eval2(e : &Exp) -> i32 {
    match e {
      Exp::Int { val } => return *val,
      Exp::Plus { left, right } => return eval(left) + eval(right),
      Exp::Mult { left, right } =>
            match **left {
                Exp::Int{val : 0} => return 0,
                _ => return eval(left) * eval(right)
            }
    }
}

// Comments.
// left is of type &Box<Exp>
// 1. *left to get Box<Exp>
// 2. **left to get Exp

// Don't care pattern.
// Behavior different from eval.
fn eval3(e : &Exp) -> i32 {
    match e {
      Exp::Plus { left, right } => return eval(left) + eval(right),
      Exp::Mult { left, right } => return eval(left) * eval(right),
      _ => return 1,
    }
}




fn example12() {
   {
       let e = Exp::Int { val : 1 };
       println!("{}", eval(&e));

       println!("{}", eval2(&e));

       println!("{}", eval3(&e));
   }

   {
       let e = Exp::Plus{left : Box::new(Exp::Int { val : 1 }), right : Box::new(Exp::Int { val : 2})};
       println!("{}", eval(&e));
   }
}

fn main() {

    println!("Hello {} {}", 5, "World!");  //  Type of placeholders inferred.

    println!("{}", example1(5));

    println!("{}", example2(5));

    println!("{}", example3b(String::from("Hallo")));

    example4();

    example5();

    example6();

    example8();

    example9();

    example10();

    example11();

    example12();

    example_add();

    example9_c();

    example9_dict();

}

The Rust programming language

The Rust programming language

Immutable variables by default

Ownership

How Rust enforces ownership statically

Borrowing

Cannot change borrow values

Traits

Geometric objects examples

Traits are not types, traits are predicates/type constraints

Traits can have several (type) parameters

Traits - syntactic sugar for method calls

Dynamic traits are abstract types

Traits are translated via the dictionary-translation method

Data types and pattern matching in Rust

Data types

Pattern matching

Nested patterns

Don’t care patterns

Examples

Conclusion

Complete source code