Course Notes

Cargo is a build system for Rust. As usual, you can use

cargo --help

To see a list of commands for Cargo. The main one's we'll need:

• cargo new project_name: create a new Cargo project (and directory) called cargo_name
• cargo build: Compile the project
• cargo run: Run the executable built by cargo build (rebuilds first if necessary)
• cargo clean: Cleans up build files (usually not necessary, but a good first step when troubleshooting an error)

You should go through the Hello, Cargo! section of RPL to practice this process.

Grammar:

<var-decl>  ::= let <var-ident> = <expr>
              | let mut <var-ident> = <expr>
<assign>    ::= <var-ident> = <expr>
<var-ident> ::= ; snake_case ;

Variables are immutable by default. This is generally safer (mutability is the root of much evil). If you attempt to mutate an immutable variable, you'll get a compiler error. You can reuse (i.e., shadow) variable names with declarations.

Example:

let x = 1;         // assign x to the value 1
assert_eq!(x, 1);  // assert that x is equal to 1
                   // (also, note the comment syntax)

We use the mut keyword to declare mutable variables, which are allowed to be reassigned/mutated.

Example:

let mut x = 1;
x = 2;
assert_eq!(x, 2);

Grammar:

<const-decl>  ::= const <const-ident> : <ty> = <expr>
<const-ident> ::= ; SCREAMING_SNAKE_CASE ;

Constants are like immutable variables except that:

• they are declared with the const keyword
• by convention, they are named using SCREAMING_SNAKE_CASE
• they must be type annotated
• they must be assigned to values computed at compile-time (e.g., no stdin reads)

Constants are primarily useful for code clarity.

Example:

const SPEED_OF_LIGHT : u32 = 299792458;
assert_eq!(SPEED_OF_LIGHT, 299792458);

Grammar:

<ty>          ::= <scalar-ty> | <compound-ty>
<scalar-ty>   ::= <int-ty> | <float-ty> | bool | char
<int-ty>      ::= <sint-ty> | <uint-ty>
<sint-ty>     ::= i16 | i32 | i64 | i128 | isize
<uint-ty>     ::= u16 | u32 | u64 | u128 | usize
<float-ty>    ::= f32 | f64
<compound-ty> ::= <tuple-ty> | <array-ty>
<tys>         ::= ϵ | <ty> | <ty> , <tys>
<tuple-ty>    ::= ( <tys> )
<array-ty>    ::= [<ty>；<expr>]

<int-lit>     ::= ; see docs ;
<float-lit>   ::= ; see docs ;
<char-lit>    ::= ; see docs ;
<bool-lit>    ::= true | false

<exprs>       ::= ϵ | <expr> | <expr> , <exprs>
<tuple-lit>   ::= ( <exprs> )
<tuple-field> ::= ; see docs ;
<expr>        ::= <expr>.<tuple-field>

<list-lit>    ::= [ <exprs> ]
<expr>        ::= <expr>[<expr>]

<lit>         ::= <int-lit> | <float-lit>
               | <char-lit> | <bool-lit>
               | <tuple-lit> | <string-lit>

Rust is statically typed, i.e., the type of every variable is known at compile-time. Rust does some amount of type inference (except for constant, it seems). When in doubt, type annotate variables. It doesn't hurt, and can act as a simple form of documentation.

There are two kinds of data types: scalar and compound. Here's a short outline, most of this should be familiar.

• Scalar:
  • Integers:
    • i8, i16, i32, i64, i128, and u8, u16, u32, u64, u128
    • The number indicates the number of bits used to represent the integer. The default for type inference is i32.
    • There is also isize and usize used for indexing
    • There are standard literals for decimal, hex, octal, binary, and bytes. Look them up if you need them.
    • Rust's compiler can check for integer overflow in debug mode, but wraps by default for release mode. We're gonna ignore this for now (as if we'll be writing any production code…)
  • Floating-point numbers:
    • f32 and f64. The default for type inference is f64.
    • Represented using IEEE-754 (of course)
  • Characters:
    • type: char
    • example: 'q', '✗'
    • four bytes, represent unicode scalars (characters are weird but we won't dwell on this)
  • Booleans:
    • type: bool
    • two literals: true and false
• Compound:
  • Tuples:
    • type: (t1, t2,..., tk)
    • literal: (e1, e2,..., ek)

    • accessor: p.i

      Example:

      let tup: (i32, bool, u32) = (2, true, 2);
      assert_eq!(tup.1, true);
      

  • Arrays:
    • type: [t; n] where t is a type and n is a usize for the number of elements. IMPORTANT: Arrays are fixed length.
    • Arrays are allocated on the stack. Rust panics if an index is out of bounds (in particular, it actually checks at runtime).

    • indexing: a[i], where i is a usize.

      Example:

      const J : usize = 5;
      let a : [u32; J] = [1, 2, 3, 4, 5];
      let i : usize = 2;
      assert_eq!(a[i], 3);
      

Check the appendix in RPL on Operators for details on operators, arithmetic, Boolean or otherwise. We will, of course, see more types as the course goes on (and define our own types).

Grammar:

<fun-decl>  ::= fn <fun-ident>(<params>) <block>
              | fn <fun-ident>(<params>) -> <ty> <block>
<params>    ::= ϵ | <param> | <param> , <params>
<param>     ::= <var-ident> : <ty>
<block>     ::= { <stmts> }
<fun-ident> ::= ; snake_case ;

Functions in Rust behave much like functions in other PLs. A couple key notes:

• parameters must be type-annotated
• the return type must be given if the function returns a value

There is a return keyword, but we don't often use it; the return value is the last expression in the function block. If no last expression is given then the return value is () of type () (i.e., the unit type); see the <block> case in the given grammar for more details about how the bodies of functions might look (there's a bit of trickiness with regards to semicolons but I'm not going to dwell on it since the compiler is pretty good at catching these things).

Example:

fn sum_of_squares(x : u32, y : u32) -> u32 {
    let x_squared = x * x;
    let y_squared = y * y;
    x_squared + y_squared // NO SEMICOLON
}

Grammar:

<stmts>      ::= ϵ
               | <expr>
               | <fun-decl> <stmts>
               | <stmt> ；<stmts>
               | <expr> ；<stmts>
               | <expr-no-sc> <stmts>
<stmt>       ::= <var-decl> | <const-decl> | <assign>
<expr-no-sc> ::= <if-expr> | <while-expr> | <for-expr>
<expr>       ::= <block>
               | <lit>
               | <uop-expr>
               | <bop-expr>
               | <call-expr>
               | ( <expr> )
<uop-expr>   ::= <uop> <expr>
<bop-expr>   ::= <expr> <bop> <expr>
<uop>        ::= ; see docs ;
<bop>        ::= ; see docs ;
<call-expr>  ::= <fn-ident>(<exprs>);

Statements perform actions and do not have a value. Expressions have values (and are evaluated). The only statements we've seen so far are declarations. Any expression can be assigned to a variable (you should check this, it works even for things like while expressions).

Grammar:

<if-expr>      ::= if <expr> <block> <else-if-expr>
<else-if-expr> ::= ϵ | else <block> | else if <block> <else-if-expr>
<while-expr>   ::= while <expr> <block>
<for-expr>     ::= for <var-ident> in <expr> <block>
<ret-expr>     ::= return <expr>
<expr>         ::= <if-expr> | <while-expr> | <for-expr> | <ret-expr>

Control flow is also pretty standard. A couple things to keep in mind:

• control flow is defined by expressions. This means they can be used as the values of variables; this is particularly nice for if-expressions
• the then-case and the else-case blocks must be the same type

Example.

fn is_prime(n: i32) -> bool {
    for i in 2..n {
        if n % i == 0 {
            return false
        }
    }
    true
}

Rust is a systems PL, which means that we need to care at least a little bit about how memory is managed. We won't be going all the way to the hardware; we'll take a sufficiently detailed view to be able to appreciate the interesting aspects of Rust's type/borrow system, and a sufficiently abstract view as to not get caught up in implementation details, e.g., of the memory allocator.

There are, in rough terms, three kinds of memory we need to care about (though we'll primarily focus on the latter two):

1. static memory
2. the stack
3. the heap

Static memory consists of constants used throughout the execution of a program; it's located in a fixed place which is accessible during execution and the values therein never change. For example, when we define a variable whose value is a string slice:

let x : &str = "hello world"

The "hello world" part is stored in static memory and x is given a reference to this location. This is about all we'll say about static memory.⁶

Next up, the stack. The stack consists of the values of parameters and local variables relevant to a function call.⁷ There are a lot of positive things to say about the stack:

• Values put on the stack are very quick to access─they're "right there", so to speak, when a function is called.
• The stack is compactly organized; it's first-in first-out, there's no wasted space, everything relevant to the function is there when we need it, and thrown away when we're done with it.

This seems ideal.⁸ The problem: there are three major restrictions on the kind of data that can be put on the stack:

1. The data must be fixed-size, known at compile time.
2. The data cannot change size throughout the execution of the program.
3. The data on the stack relevant to a function does not persist after control is returned to the caller.

It's worth noting before moving on that, although these are common restrictions among systems PLs, they are ultimately design decisions; this optimization allows the Rust compiler to know exactly how much memory to allocate when a function is called. There is nothing inherent to a stack which makes it so we can't store data whose size is unknown at compile time (variable-size data is a different question, that would be much harder to deal with in a stack).

So, if we want to do "reasonable" programming, i.e., programming with potentially persistent data of potentially variable size, we need to put it somewhere else in memory.

The heap is where we store this variable-size persistent data. Because the size is unknown at runtime, the program itself has to allocate that memory, i.e., it has to ask a memory allocator for the amount of memory that it wants. And because the data may be persistent, we have to tell the memory allocator when we're done with it. This also means that, when we work with data on the heap, we need a level of indirection; if a function call needs access to data on the heap we put a reference on the stack, which we can follow to get to that data.

There are a lot of negative things to say about the heap:

• Access is slower; the processor has to potentially jump around; there may (read: are likely to) be references to references to references, and following these references takes time.
• The heap is organized less compactly; if we tell the memory allocator we no longer need some data on the heap, the memory allocator can free it so that it can be used later, but this may fragment the heap, leaving "holes" that add up to a large amount of memory, but cannot be used to hold a contiguous piece of data.
• The system of allocation/deallocation is exactly the source of memory bugs:
  • A dangling point is what you get when you keep around a reference to a location on the heap that no longer contains valid data.
  • A memory leak is what you get when you allocate memory, but lose the reference to it so that it can't be freed.
  • A data race is what you get when you have multiple processes vying for the same data on the heap.

It's a kind of Pandora's box; the reality is we need the heap, we need to be able to work with variable-sized persistent data. And maybe part of our goal will be to minimize heap allocation where possible in the case that memory allocation/deallocation becomes a bottleneck, but we can't do much without it.⁹

The Picture. You'll often see diagrams of this form to describe the layout of memory. The stack and heap grow in opposite directions. And there may be "holes" on the heap due to freed memory. It's a bit of a caricature but is sufficient for our purposes.

  (HIGH ADDRS)
┌───────────────┐
│ FN1 PARAM     │ STACK
├───────────────┤ ↓↓↓↓↓
│ FN1 LOCAL VAR │
├───────────────┤
│ FN1 LOCAL VAR │
├───────────────┤
│ FN2 PARAM     │
├───────────────┤
│ FN2 PARAM     │
├───────────────┤
│ FN2 LOCAL VAR │
├───────────────┤
│ FN2 LOCAL VAR │
├───────────────┤
        ⋮
        ⋮
        ⋮
├───────────────┤
│ HEAP DATA     │
├───────────────┤
│ FREE          │
├───────────────┤
│ FREE          │
├───────────────┤
│ HEAP DATA     │
├───────────────┤ ↑↑↑↑
│ HEAP DATA     │ HEAP
├───────────────┤╮
│ CONSTANTS     ││
├───────────────┤├STATIC
│ CONSTANTS     ││
└───────────────┘╯
  (LOW ADDRS)

Okay, so we have the stack and the heap, and all systems PLs have to deal with the tradeoffs presented by these two kinds of memory. There are, in broad strokes, four ways that have become common approaches (in order roughly of decreasing user control):

1. Explicit allocation/deallocation (C)
2. Ownership (Rust)
3. Automatic Reference Counting (Swift, C++ via smart pointers)
4. Garbage Collection (Python, Java, OCaml, pretty much all high-level PLs)

I'm gonna put to RPL 4.2 here.

It is common for structures to own their data. It's possible to store references, but this requires that we discuss lifetimes (to come, I promise).

Values are moved per field so it is possible to move only a subset of the values of a structure. This should probably only be used for self-updates.

Question. Why would we want to use &str over String in a structure?

Note. References are short term. They should not usually be used to structure data.

Question. Can we build cyclic structures with references?

Derived trait

Method syntax:

<stmt-no-sc> ::= impl <struct-ident> <block>

We can have multiple implementation blocks

**Automatic reference/dereference

We use the Self keyword:

<ty>   ::= Self
<expr> ::= Self | Self { <tv-pairs> }