Welcome to DS210 B1 (Fall 2025)!

About this site

This site contains a complete set of resources and links for DS210 B1 for Fall 2025.

How the material works

Before lecture

• Ahead of each lecture, check the schedule for the reading associated with the next lecture and read it over (we will be moving quickly through the "lecture" part of each class so pre-reading is key).
• Complete the pre-lecture task on Gradescope - typically a quick question about the reading and/or a feedback question about the course.

During lecture

• In lecture, since we will be screens-closed for the first half each day, I will provide paper copies of key content for you to take notes on.
• In-class activities will be either paper/pencil, on gradescope, or on github classroom (URL TBD) depending on the day, and resources for those will be on this site as well.

After lecture

• A condensed version of the slides will be available on this site after the lecture under Lecture Notes.
• Homework assignments will be announced on Piazza and linked to the schedule when they are released. Due dates can be found in the schedule.
• Exam dates are on the schedule. We will have a review lecture before each exam.

Quick Links

On this site

• Course Syllabus
• B1 Lecture, HW, and Exam Schedule

External links

• 210 Piazza
• 210 Gradescope
• Prof. Wheelock coffee slots sign-up
• A1 lecture notes

CDS 210 - Fall 2025 Syllabus

Overview

This course builds on DS110 (Python for Data Science) by expanding on programming language, systems, and algorithmic concepts introduced in the prior course. The course begins by exploring the different types of programming languages and introducing students to important systems level concepts such as computer architecture, compilers, file systems, and using the command line. It then moves to introducing a high performance language (Rust) and how to use it to implement a number of fundamental CS data structures and algorithms (lists, queues, trees, graphs etc). Then it covers how to use Rust in conjunction with external libraries to perform data manipulation and analysis.

Prerequisites: CDS 110 or equivalent

Teaching Staff

Section A1 Instructor: Thomas Gardos
Email: tgardos@bu.edu
Office hours: Tuesdays, 3:30-4:45pm @ CCDS 1623

Section B1 Instructor: Lauren Wheelock
Email: laurenbw@bu.edu
Office hours: Wed 2:30-4:00 @ CCDS 1506 Coffee slots: Fri 2:30-3:30 @ CCDS 1506

If you want to meet but cannot make office hours, send a private note on Piazza with at least 2 suggestions for times that you are available, and we will find a time to meet.

Lectures and Discussions

A1 Lecture: Tuesdays, Thursdays 2:00pm-3:15pm (LAW AUD)

Section A Discussions (Wednesdays, 50 min):

• A2: 12:20pm – 1:10pm, SAR 300, (led by Zach)
• 3: 1:25pm – 2:15pm, IEC B10, (led by Zach)
• A4: 2:30pm – 3:20pm CGS 311, (led by Emir)
• A5: 3:35pm – 4:25pm CGS 315, (led by Emir)

B1 Lecture: Mondays, Wednesdays, Fridays 12:20pm-1:10pm (WED 130)

Section B Discussions (Fridays, 50 min):

• B2: Tue 11:00am – 11:50 (listed 12:15pm), 111 Cummington St MCS B37 (led by Joey)
• B3: Tue 12:30pm – 1:20 (listed 1:45pm), 3 Cummington Mall PRB 148 (led by Joey)
• B4: Tue 2:00pm – 2:50pm (listed 3:15pm), 665 Comm Ave CDS 164
• B5: Tue 3:30pm – 4:20 (listed 4:45pm), 111 Cummington St MCS B31

Note: Discussion sections B4 and B5 are cancelled because of low enrollment. Please re-enroll in B2 or B3 if you were previously enrolled in B4 or B5.

Note: There are two sections of this course, they cover the same material and share a piazza and course staff but the discussion sections and grading portals are different. These are not interchangeable, you must attend the lecture and discussion sessions for your section!

Course Websites

• Piazza

  • Lecture Recordings
  • Announcements and additional information
  • Questions and discussions

• Course Notes (https://ds210-fa25-private.github.io/):

  • Syllabus (this document)
  • Interactive lecture notes

• Gradescope

  • Homework, project, project proposal submissions
  • Gradebook

• GitHub Classroom: URL TBD

Course Content Overview

• Part 1: Foundations (command line, git) & Rust Basics (Weeks 1-3)
• Part 2: Core Rust Concepts & Data Structures (Weeks 4-5)
• Midterm 1 (~Week 5)
• Part 3: Advanced Rust & Algorithms (Weeks 6-10)
• Midterm 2 (~Week 10)
• Part 4: Data Structures and Algorithms (~Weeks 11-12)
• Part 5: Data Science & Rust in Practice (~Weeks 13-14)
• Final exam during exam week

For a complete list of modules and topics that will be kept up-to-date as we go through the term, see Lecture Schedule (MWF) and Lecture Schedule (TTH).

Course Format

Lectures will involve extensive hands-on practice. Each class includes:

• Interactive presentations of new concepts
• Small-group exercises and problem-solving activities
• Discussion and Q&A

Because of this active format, regular attendance and participation is important and counts for a significant portion of your grade (15%).

Discussions will review lecture material, provide homework support, and will adapt over the semester to the needs of the class. We will not take attendance but our TAs make this a great resource!

Pre-work will be assigned before most lectures to prepare you for in-class activities. These typically include readings plus a short ungraded quiz. We will also periodically ask for feedback and reflections on the course between lectures.

Homeworks will be assigned roughly weekly at first, and there will be longer two-week assignments later, reflecting the growing complexity of the material.

Exams Two midterms and a cumulative final exam covering theory and short hand-coding problems (which we will practice in class!)

The course emphasizes learning through practice, with opportunities for corrections and growth after receiving feedback on assignments and exams.

Course Policies

Grading Calculations

Your grade will be determined as:

• 15% homeworks (~9 assignments)
• 20% midterm 1
• 20% midterm 2
• 25% final exam
• 15% in-class activities
• 5% pre-work and surveys

I will use the standard map from numeric grades to letter grades (>=93 is A, >=90 is A-, etc). For the midterm and final, we may add a fixed number of "free" points to everyone uniformly to effectively curve the exam at our discretion - this will never result in a lower grade for anyone.

We will use gradescope to track grades over the course of the semester, which you can verify at any time and use to compute your current grade in the course for yourself.

Homeworks

Homework assignments will be submitted by uploading them to GitHub Classroom. Since it may be possible to rely on genAI tools to do these assignments, against the course policy, our grading emphasizes development process and coding best practices in addition to technical correctness.

Typically, 1/3 of the homework score will be for correctness (computed by automated tests for coding assignments), 1/3 for documenting of your process (sufficient commit history and comments), and 1/3 for communication and best practices, which can be attained by replying to and incorporating feedback given by the CAs and TAs on your work.

Exams

The final will be during exam week, date and location TBD. The two midterms will be in class during normal lecture time.

If you have a valid conflict with a test date, you must tell me as soon as you are aware, and with a minimum of one week notice (unless there are extenuating  circumstances) so we can arrange a make-up test.

If you need accommodations for exams, schedule them with the Testing Center as soon as exam dates are firm. See below for more about accommodations.

Deadlines and late work

Homeworks will be due on the date specified in gradescope/github classroom.  

If your work is up to 48-hours late, you can still qualify for up to 80% credit for the assignment. After 48 hours, late work will not be accepted unless you have made prior arrangements due to extraordinary circumstances.

Collaboration

You are free to discuss problems and approaches with other students but must do your own writeup. If a significant portion of your solution is derived from someone else's work (your classmate, a website, a book, etc), you must cite that source in your writeup. You will not be penalized for using outside sources as long as you cite them appropriately.

You must also understand your solution well enough to be able to explain it if asked.

Academic honesty

You must adhere to BU's Academic Conduct Code at all times. Please be sure to read it here. In particular: cheating on an exam, passing off another student's work as your own, or plagiarism of writing or code are grounds for a grade reduction in the course and referral to BU's Academic Conduct Committee. If you have any questions about the policy, please send me a private Piazza note immediately, before taking an action that might be a violation.

AI use policy

You are allowed to use GenAI (e.g., ChatGPT, GitHub Copilot, etc) to help you understand concepts, debug your code, or generate ideas. You should understand that this may may help or impede your learning depending on how you use it.

If you use GenAI for an assignment, you must cite what you used and how you used it (for brainstorming, autocomplete, generating comments, fixing specific bugs, etc.). You must understand the solution well enough to explain it during a small group or discussion in class.

Your professor and TAs/CAs are happy to help you write and debug your own code during office hours, but we will not help you understand or debug code that generated by AI.

For more information see the CDS policy on GenAI.

Attendance and participation

Since a large component of your learning will come from in-class activities and discussions, attendance and participation are essential and account for 15% of your grade.

Attendance will be taken in lecture through Piazza polls which will open at various points during the lecture. Understanding that illness and conflicts arise, up to 4 absences are considered excused and will not affect your attendance grade.

In most lectures, there will be time for small-group exercises, either on paper or using github. To receive participation credit on these occasions, you must identify yourself on paper or in the repo along with a submission. These submissions will not be graded for accuracy, just for good-faith effort.

Occasionally, I may ask for volunteers, or I may call randomly upon students or groups to answer questions or present problems during class. You will be credited for participation.

Absences

This course follows BU's policy on religious observance. Otherwise, it is generally expected that students attend lectures and discussion sections. If you cannot attend classes for a while, please let me know as soon as possible. If you miss a lecture, please review the lecture notes and lecture recording. If I cannot teach in person, I will send a Piazza announcement with instructions.

Accommodations

If you need accommodations, let me know as soon as possible. You have the right to have your needs met, and the sooner you let me know, the sooner I can make arrangements to support you.

This course follows all BU policies regarding accommodations for students with documented disabilities. If you are a student with a disability or believe you might have a disability that requires accommodations, please contact the Office for Disability Services (ODS) at (617) 353-3658 or access@bu.edu to coordinate accommodation requests.

If you require accommodations for exams, please schedule that at the BU testing center as soon as the exam date is set.

Re-grading

You have the right to request a re-grade of any homework or test. All regrade requests must be submitted using the Gradescope interface. If you request a re-grade for a portion of an assignment, then we may review the entire assignment, not just the part in question. This may potentially result in a lower grade.

Corrections

You are welcome to submit corrections on homework assignments or the midterms. This is an opportunity to take the feedback you have received, reflect on it, and then demonstrate growth. Corrections involve submitting an updated version of the assignment or test alongside the following reflections:

• A clear explanation of the mistake
• What misconception(s) led to it
• An explanation of the correction
• What you now understand that you didn't before

After receiving grades back, you will have one week to submit corrections. You can only submit corrections on a good faith attempt at the initial submission (not to make up for a missed assignment).

Satisfying this criteria completely for any particular problem will earn you back 50% of the points you originally lost (no partial credit).

Oral re-exams (Section B only)

In Section B, we will provide you with a topic breakdown of your midterm exams into a few major topics. After receiving your midterm grade, you may choose to do an oral re-exam on one of the topics you struggled with by scheduling an appointment with Prof. Wheelock. This will involve a short (~10 minute) oral exam where you will be asked to explain concepts and write code on a whiteboard. This score will replace your original score on the topic, with a cap of 90% on that topic.

MWF Lecture, HW, and Exam Schedule

Everything in this table that occurs in the future is subject to change. Please check the readings before each lecture. Homework and exam dates should be stable - we will make a clear announcement if they need to be changed.

This table is wide so you might need to scroll to the right to see all columns.

Lecture 1 - Welcome to DS210! (Section B)

What today will look like

• Screen-free space

Agenda

• What is this course?
• Quick introductions and logistics
• Syllabus review activity
• AI use discussion

All the material in the course will be in the service of at least one of:

1. Code development skills - tools, collaboration, best practices
2. Programming in Rust
3. Systems programming (memory, performance, types)
4. Data structures and algorithms (to be continued in DS 320)

But why are YOU taking it?

I just want to say - I hear you. Here's my job...

Why coding development skills matter

• Often never taught explicitly, can be tricky to self-teach
• Vitally important in "the real world", when you'll need to:
  • Get out of a "detached head" state without losing your head
  • Collaborate with others on code across space and time
  • Work on massive codebases and data warehouses

Why Systems Programming Matters

Knowing enough to answer

• Why is my code slow?
• Why is my app crashing?
• Why did we get hacked?

Or better yet... not having to answer those questions as often!

Why data structures and algorithms?

Knowing enough to answer

• Why is my model producing weird results?
• Is there a smarter way to do this than brute-force?
• How is this ever going to scale?

And inventing whole net new ways of working with data.

Also -

• Technical interviews
• Intellectual joy

Why are we doing this in Rust?

• A second language
• A compiled language
• A systems programming language
• A modern language
• An increasingly popular language

Logistics

What have you heard about the course?

New This Semester

1. Local dev and focus on development skills
2. Mastery vs coverage
3. In-class activities in every lecture
4. Better alignment between lectures, homeworks, and exams
5. Three exams, no final project

Why the shift to "active learning"?

• A meta-analysis of 225 studies found students in traditional lecture courses are 1.5 times more likely to fail compared to active learning environments.
• Active learning produces consistent effect sizes of 0.47-0.49 standard deviations, or half a letter grade improvement.
• Active learning reduces achievement gaps between underrepresented and majority students by 33-45%.

Our Teaching Staff

Two things to know about me...

1. I am your advocate.

• It's us against the material
• No gotchas
• Lots of practice and review in class
• Please share feedback
• I want to know who you are (coffee slots!)
• If you are struggling, please reach out early so we can help

2. I have high expectations for you.

• Grading on an absolute scale
• Less weight on homeworks, more on exams
• When you're here, you're HERE
• You CAN learn this stuff!

What this means for grading

35% course grade based on EFFORT:

• 15% homeworks
• 15% in-class activities
• 5% pre-work and surveys

65% based on MASTERY:

• 20% midterm 1
• 20% midterm 2
• 25% final exam

Lectures and Discussions

Lecture: Mondays, Wednesdays, Fridays 12:20pm-1:10pm (WED 130)

Discussion B2 - led by Joey

• Tue 11:00am – 11:50 (listed 12:15pm)
• 111 Cummington St MCS B37

Discussion B3 - led by Joey

• Tue 12:30pm – 1:20 (listed 1:45pm)
• 3 Cummington Mall PRB 148

B4 and B5 are cancelled this semester

About Section A

Section A Instructor: Thomas Gardos

• Email: tgardos@bu.edu
• Office hours: Tuesdays, 3:30-4:45pm @ CCDS 1623

Their schedule:

• Lectures are Tue / Thu 2-3:15
• Discussions are Wednesday afternoons
• Pacing may be different, so please attend B lectures and discussions!

What we share:

• Homework assignments and due dates
• Exams topics (different questions) and rough dates
• TAs and CAs

Thanks for hanging tight as we get set up!

Syllabus Review Activity (20 min)

Instructions

In groups of 2-3, spend 15 minutes answering the worksheet questions on paper.

Recap

AI use discussion (20 min)

Instructions

Think-pair-share style, each ~6-7 minutes, with wrap-up.

Form groups of 2-3 (different groups if possible!).

We're not putting this on gradescope (sorry if you filled this out on gradescope yesterday! 😅)

Round 1: Learning Impact

How might GenAI tools help your learning in this course?

How might they get in the way?

Round 2: Values & Fairness

What expectations do you have for how other students in this course will or won't use GenAI?

What expectations do you have for the teaching team so we can assess your learning fairly given easy access to these tools?

Round 3: Real Decisions

Picture yourself stuck on a challenging Rust problem at midnight with a deadline looming.

What options do you have?

What would help you make decisions you'd feel good about?

Wrap-up

By Friday

Please fill out the intro survey linked in the email and mark it complete on Gradescope.

Quick show of hands - mac/linux vs windows?

Bring your laptop and come prepared to work with the shell next class!

Lecture 2 - Hello Shell!

Intro

And the survey says...

Some FAQs

Common questions

• Exam format and content
• How I learned your names
• Where are recordings / lecture notes
• Partial credit / extra credit
• How bad til exams get a curve?

Some more points to note

• Gradescope vs GitHub Classroom
• Lecture notes for A vs B

I promise to revisit these Monday:

• Prework
• Homework and exam schedule

Motivation

What is the terminal?

What is the terminal?

... the kitchem metaphor

Shell, Terminal, Console, Command line... and what's Bash?

• The command line is the interface where you type commands to interact with your computer.
• The command prompt is the character(s) before your cursor that signals you can type and can be configured with other reminders.
• The terminal or console is the program that opens a window and lets you interact with the shell.
• The shell is the command line interpreter that processes your commands. (You might also encounter "a command line" in text-based games)

Terminals are more like applications and shells are more like languages.

Shell, Terminal, Console, Command line... and what's Bash?

Terminals come in proper nouns:

• Terminal (macOS)
• iTerm2 (macOS)
• GNOME Terminal (Linux)
• Konsole (Linux)
• Command Prompt (Windows)
• PowerShell (Windows)
• Git Bash (Windows)

Shells also come in proper nouns:

• Bash (Bourne Again SHell) - most common on Linux and macOS
• Zsh (Z Shell) - default on modern macOS
• Fish (Friendly Interactive SHell) - user-friendly alternative
• Tcsh (TENEX C Shell) - popular on some Unix systems
• PowerShell - advanced shell for Windows

Shell, Terminal, Console, Command line... and what's Bash?

BUT they are often used interchangeably in speech:

• "Open your terminal"
• "Type this command in the shell"
• "Run this in the command line"
• "Execute this in your console"

What is this all good for?

Lightning fast navigation and action

# Quick file operations
ls *.rs                    # Find all Rust files
grep "TODO" src/*.rs       # Search for TODO comments across files
wc -l data/*.csv          # Count lines in all CSV files

• How would you to this "manually"?

It's how we're going to build and manage our rust projects

# Start your day
git pull                          # Get latest team changes
cargo test                        # Make sure everything still works
# ... code some features ...
cargo run                         # Test your new feature
git add src/main.rs               # Stage your changes
git commit -m "Add awesome feature"  # Save your work
git push                          # Share with the team

For when your UI just won't cut it

• Confused by "invisible files" and folders?

ls -la

For when your UI just won't cut it

• Need to find a file where you wrote something a while ago

grep -r "that thing I wrote 6 months ago"

• Modify lots of files at once

# Rename 500 photos at once
for file in *.jpg; do mv "$file" "vacation_$file"; done

# Delete all files older than 30 days
find . -type f -mtime +30 -delete

• "Why is my computer fan running like it's about to take off?"

df -h              # See disk space usage immediately
ps aux | grep app  # Find that app that's hogging memory
top                # Live system monitor

In other words, the command line provides:

• Speed: Much faster for repetitive tasks
• Precision: Exact control over file operations
• Automation: Commands can be scripted and repeated
• Remote work: Essential for server management
• Development workflow: Many programming tools use command-line interfaces

Learning objectives for today (TC 12:30)

By the end of this lecture, you should be able to:

• Navigate your file system on the command line
• Create, copy, move, and delete files and directories at the command line
• Interpret file permissions
• Use pipes and redirection for basic text processing

We will also discuss, but you are not responsible for:

• Customizing your shell profile with aliases and functions
• Writing simple shell scripts

We'll have one of these slides every lecture and it's a great way to check in on what material you're responsible for for exams!

The file system and navigation

Everything starts at the root

Root Directory (/):

In Linux, the slash character represents the root of the entire file system.

(On a Windows machine you might see "C:" but on Linux and MacOS it is just "/".)

(We'll talk more about Windows in a minute)

Key Directories You'll Use:

/                          # Root of entire system
├── home/                  # User home directories
│   └── username/          # Your personal space
├── usr/                   # User programs and libraries
│   ├── bin/              # User programs (like cargo, rustc)
│   └── local/            # Locally installed software
└── tmp/                  # Temporary files

Navigation Shortcuts:

• ~ = Your home directory
• . = Current directory
• .. = Parent directory
• / = Root directory

Let's take a look / basic navigation demo

Demo time! First let's look at the command prompt...

Maybe half of your interactions with the shell will look like:

pwd                   # Print working directory
ls                    # List files in current directory
ls -a                 # List files including hidden files
ls -al                # List files with details and hidden files
cd directory_name     # Change to directory
cd ..                 # Go up one directory
cd ~                  # Go to home directory

Tips:

• Use Tab for auto-completion (great for paths!)
• Use Up Arrow to access command history
• Try control-c to abort something running or clear a line
• You can't click into a line to edit it, use left/right arrows (or vim, or copy-paste)

What's going on here?

The command line takes commands and arguments.

ls -la ~

The grammer is like a command in English: VERB (NOUN) ("eat", "drink water", "open door") ls is the command, -la and ~ are arguments.

Flags / Options

Special arguemnts called "options" or "flags" usually start with a dash - and can be separate or combined. These are equivalent:

ls -la
ls -al
ls -a -l
ls -l -a

BUT they typically need to come before other arguemnts:

ls -l -a ~   # works!
ls -l ~ -a   # does not work

Let's pause for the elephant in the room

• macOS is built on Unix
• Windows is entirely different
  • dir instead of ls
  • copy and move instead of cp and mv
• We strongly recommend Windows users install a terminal with bash (we'll do it today!) so we can speak the same language.

One thing is unavoidable: different paths

• / vs C:\Users\ (vote for which is a back slash!)
• This incompatibility has caused more suffering than metric vs imperial units.

Essential Commands for Daily Use (TC 12:35)

Quiz time!

What do these stand for and what do they do:

• pwd
• cd
• ls

And

• How can you "get home quickly"?

These slides make a great starting point for Anki questions!

Reverse, reverse!

• How can you see what directory you're in?
• How can you look around to see what's in the folder?
• How can you go into one of those folders?
• How can you back out?
• How can you see hidden files?

The rest of the 80% of bash commands you will mostly ever use

Demo time!

mkdir project_name        # Create directory
mkdir -p path/to/dir      # Create nested directories
touch notes.txt        # Create empty file
echo "Hello World" > notes.txt  # Overwrite file contents
echo "It is me" >> notes.text   # Append to file content

cat filename.txt          # Display entire file
head filename.txt         # Show first 10 lines
tail filename.txt         # Show last 10 lines
less filename.txt         # View file page by page (press q to quit)
nano filename.txt          # Edit a file

cp file.txt backup.txt    # Copy file
mv old_name new_name      # Rename/move file
rm filename               # Delete file
rm -r directory_name      # Delete directory and contents
rm -rf directory_name     # Delete dir and contents without confirmation

Understanding ls -la Output

-rw-r--r-- 1 user group 1024 Jan 15 10:30 filename.txt
drwxr-xr-x 2 user group 4096 Jan 15 10:25 dirname

(Don't worry about "groups"!)

We will see these kinds of permissions again in Rust programming!

Common Permission Patterns

• 644 or rw-r--r--: Files you can edit, others can read
• 755 or rwxr-xr-x: Programs you can run, others can read/run
• 600 or rw-------: Private files only you can access

(Any guesses about the numeric codes?)

Don't have permission? Don't tell anyone I told you this but...

Don't have permission? Don't tell anyone I told you this but...

• What do you think sudo stands for?

One list thing... Combining Commands with Pipes

ls | grep ".txt"          # List only .txt files
cat file.txt | head -5    # Show first 5 lines of file
ls -l | wc -l            # Count number of files in directory

Combining Commands with Pipes

More Examples:

# Find large files
ls -la | sort -k5 -nr | head -10

# Count total lines in all text files
cat *.txt | wc -l

So tell me, what's the difference...

ls -la | wc -l
ls -la > results.txt

FYI (TC 12:45 or skip)

For your awareness - Your Shell Profile

Understanding Shell Configuration Files:

Your shell reads a configuration file when it starts up. This is where you can add aliases, modify your PATH, and customize your environment.

Common Configuration Files:

• macOS (zsh): ~/.zshrc
• macOS (bash): ~/.bash_profile or ~/.bashrc
• Linux (bash): ~/.bashrc
• Windows Git Bash: ~/.bash_profile

Finding Your Configuration File:

It's in your Home directory.

# Check which shell you're using (MacOS/Linus)
echo $SHELL

# macOS with zsh
echo $HOME/.zshrc

# macOS/Linux with bash
echo $HOME/.bash_profile
echo $HOME/.bashrc

Adding aliases to you shell profile

# Edit your shell configuration file (choose the right one for your system)
nano ~/.zshrc        # macOS zsh
nano ~/.bash_profile # macOS bash or Git Bash
nano ~/.bashrc       # Linux bash

# Add these helpful aliases:
alias ll='ls -la'
alias ..='cd ..'
alias ...='cd ../..'
alias projects='cd ~/development'
alias rust-projects='cd ~/development/rust_projects'
alias grep='grep --color=auto'
alias tree='tree -C'

# Custom functions
# This will make a directory specified as the argument and change into it
mkcd() {
    mkdir -p "$1" && cd "$1"
}

Modifying your PATH

You may need to do this occasionally to make tools you install available on the command line.

# Add to your shell configuration file
export PATH="$HOME/bin:$PATH"
export PATH="$HOME/.cargo/bin:$PATH"    # For Rust tools (we'll add this later)

# For development tools
export PATH="/usr/local/bin:$PATH"

Applying Changes:

# Method 1: Reload your shell configuration
source ~/.zshrc        # For zsh
source ~/.bash_profile # For bash

# Method 2: Start a new terminal session
# Method 3: Run the command directly
exec $SHELL

Shell scripts

Shell script files typically use the extension *.sh, e.g. script.sh.

Shell script files start with a shebang line, #!/bin/bash.

#!/bin/bash

echo "Hello world!"

To execute shell script you can use the command:

source script.sh

Before it gets noisy in here... (TC 12:50)

• What does drwxr-xr-x mean?
• How can I quickly write "I'm awesome" to my affirmations.txt file?
• How can I delete my file_of_secrets.txt before the cops get here?
• How can I rename my file_of_secrets.txt so it "disappears"?
• How can I find it again?

In-Class Activity: Shell Challenge

In groups of 2-3, go to https://github.com/lauren897/ds210-fa25-b and complete the challenge.

Remember to submit on gradescope (once per group)! (There's a grace period til 1:30)

Coming up -

• Monday: git and GitHub
• Releasing HW1 (exact dates TBD but we'll give at least a full week)
• We start Rust on Wednesday!
• Wednesday also starts pre-work, we'll explain more on Monday
• I'll post a coffee slot sign-up sheet tonight
• I'll have lecture notes / a site set up by Monday

Lecture 3 - Hello Git!

The problem with "manual" version control

• Storage space (due to redundancy)
• Hard to see what changes were made when
• Hard to collaborate (merge, review)

The collaboration problem

Learning Objectives

By the end of this lecture, you should be able to:

• Understand why version control is critical for programming
• Configure Git for first-time use
• Create repositories and make meaningful commits
• Connect local repositories to GitHub
• Use the basic Git workflow for individual projects
• Use the git commands clone, checkout, add, commit, push, pull, merge

Warning - this is a lot to take in at once, but we will be practicing and developing this ALL semester

The Four (and a half) Locations

Repository (Repo): A folder tracked by Git, containing your project and its complete history.

Workspace The files on your machine right now, where we edit them

Staging Area Temporary holding spot for changes before committing

Local repository Where we store committed changes locally

Remote repository A server (like GitHub) for storing and collaborating on code

Git workflow concepts

Commit: A snapshot of your project at a specific moment, with a message explaining what changed.

Diff: The collection of specific edits in a commit. (Or generally, the differences between any two versions of a file.)

Branch: One "timeline" of commits that may diverge from other timelines

Git Workflows

Merging and Pull Requests

Merge: Combines changes from different branches. Takes commits from one branch and integrates them into another branch.

Merge Conflict: Merging may fail if both branches change the same lines. Git will point to the conflict and ask you to resolve it before finishing the merge.

Pull Request (PR): A request to merge your changes into another branch, typically used for code review. You "request" that someone "pull" your changes into the main codebase.

Git Branching

• Main branch: Usually called main (or master in older repos)
• Feature branches: Created for new features or bug fixes

• Isolates experimental work
• Enables parallel development
• Facilitates code review

Essential Git Commands

Let's take this to the command line.

One-Time Setup

# Configure your identity (use your real name and email)
git config --global user.name "Your Full Name"
git config --global user.email "your.email@example.com"

# Set default branch name
git config --global init.defaultBranch main

Note: The community has moved away from master as the default branch name, but it may still be default in some installations.

Starting a New Project - Demo/Practice (shout it out)

• Where am I?
• How can I move to my projects directory?
• How can I create a new project?
• How can I move into the project?
• git init
• What did that do?

A note about .gitignore

Anything in your repo you DON'T want tracked in git as part of you repo can go in the .gitignore file.

latexfile.aux
.ipynb_checkpoints/
.vscode
.DS_Store
/tmp

If you ever run git add and notice it added a bunch of files you don't recognize - it's time to update your .gitignore

Daily Git Workflow

# Create a descriptive branch name for the change you want to make
git checkout -b feature_branch

# Check what's changed
git status                    # See current state

# Stage changes for commit
git add filename.rs          # Add specific file to staging
git add .                    # Add all changes in current directory

git commit -m "Add calculator function" # Commit with a comment

git checkout main # Switch back to main
git merge feature_branch # Merge branch back into main
# merge merges the branch you NAME *into* the branch you're currently ON

Writing Good Commit Messages

• Start with a present / imperative verb
• Be brief and specific
• If you find yourself using "and" a lot your commits are too big

The Golden Rule: Your commit message should complete this sentence: "If applied, this commit will [your message here]"

Good Examples:

git commit -m "Add input validation for calculator"
git commit -m "Fix division by zero error"
git commit -m "Refactor string parsing for clarity"
git commit -m "Add tests for edge cases"

Bad Examples:

git commit -m "fix a bug"        # What bug
git commit -m "fix date range bug and added multi-user feature"  # Too much at once
git commit -m "trying again"    # what are you doing differently?

Working with GitHub

Why GitHub?

• Remote backup for solo work
• Easy sharing and collaboration
• Many tools and integrations

Connecting to GitHub

You CAN create a repo locally then push it to GitHub:

git init
git remote add origin https://github.com/yourusername/repository-name.git
git push -u origin main

But you can also create it from GitHub and clone it locally - what we'll usually do

# Clone existing repository
git clone https://github.com/username/repository.git

To keep things in sync your main actions are

# Get to the repository
cd repository 

# Pull any changes from GitHub
git pull

# Push your commits to GitHub
git push # you'll be prompted at this point to log into github in your terminal

Git, GitHub, and shell together - Demo

# Creating a new repo 
cd ~/ds210/assignments
mkdir assignment_01
cd assignment_01
git init

# Make a branch
git checkout -b problem1

# Make initial commit
touch README.md
echo "# Assignment 1" > README.md
git add README.md
git commit -m "Initial project setup for Assignment 1"

# Work and commit frequently
# ... write some code ...
mkdir src
touch src/main.rs
echo "some rust code" > src/main.rs
git add src/main.rs
git commit -m "Implement basic data structure"

# Merge back to the main branch
git checkout main
git merge problem1

# Push changes to GitHub
git remote add origin https://github.com/yourusername/repository-name.git
git push -u origin main
git push

Common Git Scenarios

"I made a mistake in my last commit message"

git commit --amend -m "Corrected commit message"

I want to undo a git add

git reset

"I want to undo changes I haven't committed yet"

git checkout -- filename.rs    # Undo changes to specific file
git reset --hard               # Undo ALL uncommitted changes (CAREFUL!)

I want to do something else

git log    # shows commit history
git branch # shows available branches
git rebase # is an alternative to merge
git fetch  # is like git pull but doesn't include a merge

Search and stack overflow are you friends here!

Resources for learning more and practicing

• Interactive online Git tutorial that goes a bit deeper: https://learngitbranching.js.org/
• A downloadable app with tutorials and challenges: https://github.com/jlord/git-it-electron
• Another good tutorial (examples in ruby): https://gitimmersion.com/
• Pro Git book (free online): https://git-scm.com/book/en/v2

Lecture 4 - Hello Rust!

Quick pulse check

• Who got Rust installed?
• Is anyone STILL having github authentication issues?
• How were the discussions yesterday?
• On gradescope / grade tracking and updates

How this feels is both normal and not normal

• What's a SNAFU?

So what's going well?

Think-Pair-Share

• Something you figured out after being frustrated
• A time you were able to help someone else
• An aha moment
• That you keep showing up

Rust

Learning objectives

By the end of class today you should be able to:

• Explain what a compiler and a compiled language is
• Write a simple "hello world" Rust program wiht proper syntax (fn, brackets)
• Use rustc and cargo to compile and run Rust programs
• Decide when to use mutable or immutable variables in Rust

Rust in three concepts

• Compiled
• Type-safe
• Memory-safe

What is a compiler?

What is a compiled langauge vs an interpreted one?

What is type-safety?

What is memory-safety?

Comparing to Python

R v P - Basic function writing

fn main() {
    println!("Hello, world!");
}

Key differences from Python:

• fn keyword for functions (what was it for python?)
• Braces {} for code blocks (...?)
• Semicolons ; end statements (...?)
• println! is a macro (the ! means macro) - more on this later

R v P - Variables, types, and mutability

fn main() {
    let x = 5;          // immutable by default
    let mut y = 10;     // mut makes it mutable
    y = 15;             // this works
    // x = 6;           // this would error!
    // y = "today"     // this would also error!
    
    println!("x is {}, y is {}", x, y);
}

Key differences from Python:

• Python: everything mutable by default
• Rust: immutable by default with unchangable types

R vs P Ownership and memory safety

import pandas as pd

def clean_data(df):
    df['score'] = df['score'] * 2  # Double all scores
    return df

# Original data
grades = pd.DataFrame({'name': ['Alice', 'Bob'], 'score': [85, 92]})
print("Original:", grades['score'].tolist())  # [85, 92]

# Clean the data
cleaned = clean_data(grades)
print("Cleaned:", cleaned['score'].tolist())   # [170, 184]

# Wait... what happened to our original data?
print("Original:", grades['score'].tolist())   # [170, 184] - Changed!

In Rust

#![allow(unused)]
fn main() {
// Option 1: Take ownership (original data moves, can't use it anymore)
fn clean_data_move(mut scores: Vec<i32>) -> Vec<i32> {
    for score in &mut scores {
        *score *= 2;
    }
    scores  // Returns modified data, original is gone
}

// Option 2: Borrow mutably (explicitly allows changes)
fn clean_data_borrow(scores: &mut Vec<i32>) {
    for score in scores {
        *score *= 2;
    }
    // Original data is modified, but you were explicit about it
}
}

Key differences from Python:

• Python: unclear when a variable might be changed -> unexpected behavior
• Rust: data moves are alwyas explicit

Compiling and running

Python: One Step (Interpreted)

python hello.py

• Python reads your code line by line and executes it immediately
• No separate compilation step needed

Rust: Two Steps (Compiled)

# Step 1: Compile (translate to machine code)
rustc hello.rs 

# Step 2: Run the executable
./hello

• rustc is your compiler
• rustc translates your entire program to machine code
• Then you run the executable (why ./?)

Rust with Cargo (two-in-one)

# Set-up steps (one time)
cargo new my_project
cd my_project

# Build and run (compiles automatically)
cargo run

• Cargo uses rustc under the hood

Activity

Activity 4 link

Some reminders before we look at solutions together

• Pre-work for Friday
• I have office hours today
• Homework due Monday
• Citing solutions vs breadcrumbs

Let's look at some solutions

Lecture 5 - Guessing Game Part 1

Overview of today and Monday

• Today: Part 1, in the terminal
• Monday: Part 2, in VSCode

Learning objectives

By the end of class today you should be able to:

• Use basic cargo commands to create projects and compile rust code
• Add external dependencies to a project
• Handle Rust's Result type with .expect()
• Recognize common Rust compilation errors

Live guessing game demo

I might suggest drawing a diagram of the folder structure as we explore

Key/new(ish) commands from the demo

cargo new guessing_game


nano Cargo.toml


open . # explorer . on Windows


cargo run


cargo build


cargo check


cargo run --release


./target/debug/guessing_game

Key files from the demo

Cargo.toml


Cargo.lock


.gitignore


src/main.rs


target/debug/guessing_game


target/release/guessing_game

Compiling review and reference

Option 1: Compile directly

• put the content in file hello.rs
• command line:
  • navigate to this folder
  • rustc hello.rs
  • run ./hello or hello.exe

Option 2: Use Cargo

• create a project: cargo new PROJECT-NAME
• main file will be PROJECT-NAME/src/main.rs
• to build and run: cargo run
• the machine code will be in : ./target/debug/PROJECT-NAME

Different ways to run Cargo

• cargo run compiles, runs, and saves the binary/executable in /target/debug
• cargo build compiles but does not run
• cargo check checks if it compiles (fastest)
• cargo run --release creates (slowly) "fully optimized" binary in /target/release

Back to the guessing game

We're going to add this to main.rs:

use std::io;

fn main() {
    println!("Guess the number!");
    println!("Please input your guess.");

    let mut guess = String::new();

    io::stdin()
        .read_line(&mut guess)
        .expect("Failed to read line");

    println!("You guessed: {}", guess);
}

cargo run

.expect() - a tricky concept

• read_line() returns a Result which has two variants - Ok and Err

• Ok means the operation succeeded, and returns the successful value

• Err means something went wrong, and it returns a comment on what happened

• If you use read_line() WITHOUT expect it will compile but warn you not to do that

• If you use read_line() WITH expect and it says Ok the output will be the same (user input saved to guess)

• If you use read_line() WITH expect and it says Err the program will crash and print what you wrote in .expect()

There are better ways of handling errors that we'll cover later

More on macros!

• A macro is code that writes other code for you / expands BEFORE it compiles.
• They end with ! like println!, vec!, or panic!

For example, println!("Hello"); roughly expands into

#![allow(unused)]
fn main() {
use std::io::{self, Write};
io::stdout().write_all(b"Hello\n").unwrap();
}

while println!("Name: {}, Age: {}", name, age); expands into

#![allow(unused)]
fn main() {
use std::io::{self, Write};
io::stdout().write_fmt(format_args!("Name: {}, Age: {}\n", name, age)).unwrap();
}

(which you can see will further expand!)

Adding a secret number

Adding to the toml:

[dependencies]
rand = "0.8.5"

Adding to main.rs

#![allow(unused)]
fn main() {
use rand::Rng;

let secret_number = rand::thread_rng().gen_range(1..=100);
println!("The secret number is: {secret_number}");
}

What did all that do

cat Cargo.toml 
cat Cargo.lock

cargo run
cargo run

Activity preview - let's break things!

Activity time

Activity 5

Debrief:

• Let's make a list together - how many did we find?
• Which error was the most confusing?
• Which error message was the most helpful?
• Did any errors surprise you?
• What patterns did you notice in how Rust reports errors?

Wrapping up

• Coffee slots this afternoon - stop by for 5 min if you want
• Homework due Monday at 11:59pm
• REMEMBER TO COMMENT what your commands do in Problem 1
• Oh My Git - check you have "gold" borders (you did at least five at the command line)
• There will ALSO be pre-work for Monday

Lecture 6 - Guessing Game Part 2: VSCode & Completing the Game

Learning objectives

By the end of class today you should be able to:

• Use VSCode with rust-analyzer and the integrated terminal for Rust development
• Start using loops and conditional logic in Rust
• Use match expressions and Ordering for comparisons
• Keep your code tidy and readable with clippy, comments, and doc strings

Why VSCode for Rust?

• Rust Analyzer: Real-time error checking, autocomplete, type hints
• Integrated terminal: No more switching windows
• Git integration: Visual diffs, staging, commits

Setting up VSCode for Rust

You'll need to have

• Installed VSCode
• Installed Rust
• Installed the rust-analyzer extension

Joey covered this in discussions - if you need help with these come talk to us

Opening our project

From the terminal:

cd guessing_game
code .

or use File -> Open Folder from VSCode

VSCode Features Demo

File Explorer & Navigation

• Side panel for project files
• Quick switching with Cmd+P (Mac) / Ctrl+P (Windows)
• Split editor views

Integrated Terminal

• View → Terminal or Ctrl+`
• Multiple terminals
• Same commands as before: cargo run, cargo check

Rust Analyzer in Action

• Red squiggles - Compiler errors
• Yellow squiggles - Warnings
• Hover tooltips - Type information
• Autocomplete - As you type suggestions
• Format on save - Automatic code formatting

Let's see it in action!

Cargo Clippy

• Run with cargo clippy in terminal to see suggestions
• Suggests stylistic changes that won't change the function of your code (ie refactoring suggestions)
• cargo clippy --fix will automatically accept suggestions

Completing The Guessing Game

Highlights from the compiler errors activity

Let's chat about these together

• Lots of folks hit on something like this - what happened?

"1. error ""error[E0433]: failed to resolve: use of unresolved module or unlinked crate `rand`
 --> main.rs:8:25"""

• Then playing around, people found:

-  expected `;`, found keyword `let` (deleted a semicolon)
-  invalid basic string b/c removed ""
-  linking with `link.exe` failed: exit code: 1
-  expected function, found macro `println`   (got rid of ! in println!)
-  cannot borrow `guess` as mutable, as it is not declared as mutable   (got rid of mut in declaration)
-  this file contains an unclosed delimiter (deleted a curly bracket)
-  unresolved import `std::higang`
-  failed to resolve: use of unresolved module or unlinked crate `io`
-  unreachable expression (placed code after break)

Let's walk through an interesting one

One student used cargo add rand rather than manually adding rand to the dependencies (which is totally valid!), and go this. What's going on?

warning: use of deprecated function `rand::thread_rng`: Renamed to `rng`
 --> src\main.rs:8:31
  |
8 |     let secret_number = rand::thread_rng().gen_range(1..=100);
  |                               ^^^^^^^^^^
  |
  = note: `#[warn(deprecated)]` on by default

warning: use of deprecated method `rand::Rng::gen_range`: Renamed to `random_range`
 --> src\main.rs:8:44
  |
8 |     let secret_number = rand::thread_rng().gen_range(1..=100);
  |                                            ^^^^^^^^^

warning: `scavenger_hunt` (bin ""scavenger_hunt"") generated 2 warnings

Current state (from last class):

use std::io;
use rand::Rng;

fn main() {
    println!("Guess the number!");
    
    let secret_number = rand::thread_rng().gen_range(1..=100);
    println!("The secret number is: {secret_number}");
    
    println!("Please input your guess.");
    
    let mut guess = String::new();
    
    io::stdin()
        .read_line(&mut guess)
        .expect("Failed to read line");
    
    println!("You guessed: {}", guess);
}

Making it a real game:

0. Remove the secret reveal - no cheating!
1. Compare numbers - too high? too low?
2. Add a loop - keep playing until correct
3. Handle invalid input - what if they type "banana"?

Steps 0+1

Step 0: No cheating

We just need to delete:

#![allow(unused)]
fn main() {
println!("The secret number is: {secret_number}");
}

Step 1: Comparing Numbers

First, we need to convert the guess to a number and compare:

#![allow(unused)]
fn main() {
use std::cmp::Ordering; // typically crate :: module :: type or crate :: module :: function

// Add this after reading input:
let guess: u32 = guess.trim().parse().expect("Please enter a number!");

match guess.cmp(&secret_number) {
    Ordering::Less => println!("Too small!"),
    Ordering::Greater => println!("Too big!"),
    Ordering::Equal => println!("You win!"),
}
}

Step 2: Adding the Loop

Wrap the input/comparison in a loop:

#![allow(unused)]
fn main() {
loop {
    println!("Please input your guess.");
    
    // ... input code ...
    
    match guess.cmp(&secret_number) {
        Ordering::Less => println!("Too small!"),
        Ordering::Greater => println!("Too big!"),
        Ordering::Equal => {
            println!("You win!");
            break;  // Exit the loop
        }
    }
}
}

Step 3: Handling Invalid Input

Replace .expect() with proper error handling:

#![allow(unused)]
fn main() {
let guess: u32 = match guess.trim().parse() {
    Ok(num) => num,
    Err(_) => {
        println!("Please enter a valid number!");
        continue;  // Skip to next loop iteration
    }
};
}

Back to VSCode

Completing the game

Let's paste the whole thing in and take a look

Comments & Documentation Best Practices

What would happen if you came back to this program in a month?

Inline Comments (//)

• Explain why, not what the code does
• Bad: // Create a random number
• Good: // Generate secret between 1-100 for balanced difficulty
• If it's not clear what the code does you should edit the code!

Doc Comments (///)

• Document meaningful chunks of code like functions, structs, modules
• Show up in cargo doc and IDE tooltips

#![allow(unused)]
fn main() {
/// Prompts user for a guess and validates input
/// Returns the parsed number or continues loop on invalid input
fn get_user_guess() -> u32 {
    // implementation...
}
}

The Better Comments extension

• Color-codes different types of comments in VSCode - let's paste it into main.rs and see

#![allow(unused)]
fn main() {
// TODO: Add input validation here
// ! FIXME: This will panic on negative numbers
// ? Why does this work differently on Windows?
// * Important: This function assumes sorted input
}

Visual Git Features:

• Source Control panel - See changed files
• Diff view - Side-by-side comparisons
• Stage changes - Click the + button
• Commit - Write message and commit

Still use terminal for:

• git status - Quick overview
• git log - Commit history
• git push / git pull - Syncing

Activity Time (20 minutes)

VSCode and GitHub Classroom

Wrap-up

What we've accomplished so far:

• Can now use shell, git, and rust all in one place (VSCode)
• We built a complete, functional game from scratch
• Started learning key Rust concepts: loops, matching, error handling
• We've practiced using GitHub Classroom - you'll use it for HW2!

Looking ahead

• HW1 due tonight at midnight
• HW2 released this evening
• Discussions tomorrow will focus on getting started on HW2

Lecture 7 - Variables and types

Logistics

• HW2 due next Wednesday
• I have office hours today

Circling back on comments

You definitely can make multi-line comments

#![allow(unused)]
fn main() {
// This is a single-line comment
let age = 25; // Comments can go at the end of lines

/*
   This is a multi-line comment
   Useful for longer explanations
   or temporarily disabling code
*/

/// This is a line doc comment that sits on the OUTSIDE
/** Or as a block comment (note the one ending asterisk) */
fn my_function(){
    //! This is a line doc comment that sits on the INSIDE
    /*! this is a block doc comment that sits on the inside */

}
}

Learning Objectives

• Use the mut keyword and shadowing with let to modify variables
• Declare constants using const
• Use Rust's integer types and floating-point types and understand their ranges
• Understand rust's basic types and their sizes (ints, floats,bool, char, &str)
• Use type annotation (with let) and type conversion (as)
• Work with boolean values using logical operators (&&, ||, !)
• Create, access, and destructure tuples

Variables and Mutability

Variables are by default immutable!

Let's try this and then fix it.

fn main(){
    let x = 3;
    x = x + 1; 
    println!("{x}")
}

Why can't we do this now?

fn main(){
    let mut x = 3;
    x = 9.5;
    println!("{x}")
}

One way to fix - Variable shadowing: new variable with the same name

fn main(){
    let solution = "4";
    let solution : i32 = solution.parse()
                        .expect("Not a number!");
    let solution = solution * (solution - 1) / 2;
    println!("solution = {}",solution);
    let solution = "This is a string";
    println!("solution = {}", solution);
}

Why does this work even though solution isn't mutable?

Variables vs Constants

Sometimes you need values that never change and are known at compile time:

#![allow(unused)]
fn main() {
const MAX_PLAYERS: u32 = 100;
const PI: f64 = 3.14159;
const GREETING: &str = "Hello, world!";
}

Constants:

• Are always immutable (no mut allowed)
• Use const instead of let
• Must have explicit types
• Named in ALL_UPPERCASE by convention
• Can be declared in any scope (including global)
• Must be computable at compile-time (so typically hard-coded)

When to use constants vs variables:

• Constants: Mathematical constants, configuration values, limits
• Variables: Data that might change or is computed at runtime

Types - Integers

Binary representations

Representing 13:

• In decimal (base 10): 13 = 1×10¹ + 3×10⁰
• In binary (base 2): 1101 = 1×2³ + 1×2² + 0×2¹ + 1×2⁰ = 8 + 4 + 0 + 1 = 13

For example, the number 13 in binary is 1101:

Binary:   1 1 0 1
Position: 3 2 1 0
2x^n:     8 4 2 1
Value:    8 4 0 1  → 8+4+1 = 13

T/P/S - What's the largest integer we can represent with 4 binary digits?

So what are ints, under the hood

Unsigned integers are stored in binary format.

But (signed) integers are stored in two's complement format, where:

• if the number is positive, the first bit is 0
• if the number is negative, the first bit is 1

To calculate the two's complement of a negative number, we flip all the bits and add 1.

#![allow(unused)]
fn main() {
// binary representation of 7 and -7
println!("{:032b}", 7);
println!("{:032b}", -7);
}

(Think/pair/share) Why do you think we do it this way?

Bits and bytes

• Bit: The smallest unit of data in computing - can store either 0 or 1
• Byte: A group of 8 bits - the basic addressable unit of memory
• Why 8 bits? 8 bits can represent 2⁸ = 256 different values (0-255)
• Computers typically address memory in byte-sized chunks
• (In sizes like "16 GB of RAM" GB refers to "gigaBYTES" not gigaBITS)

Integers come in all shapes and sizes

• unsigned integers: u8, u16, u32, u64, u128, usize (architecture specific size)
  • from \(0\) to \(2^n-1\)
• signed integers: i8, i16, i32 (default), i64, i128, isize (architecture specific size)
  • from \(-2^{n-1}\) to \(2^{n-1}-1\)

These numbers (like u16) refer to bits, not bytes!

if you need to convert, use the as operator

i128 and u128 are useful for cryptography

Let's try it - min and max values of int types

#![allow(unused)]
fn main() {
println!("U8 min is {} max is {}", u8::MIN, u8::MAX);
println!("I8 min is {} max is {}", i8::MIN, i8::MAX);
println!("U16 min is {} max is {}", u16::MIN, u16::MAX);
println!("I16 min is {} max is {}", i16::MIN, i16::MAX);
println!("U32 min is {} max is {}", u32::MIN, u32::MAX);
println!("I32 min is {} max is {}", i32::MIN, i32::MAX);
println!("U64 min is {} max is {}", u64::MIN, u64::MAX);
println!("I64 min is {} max is {}", i64::MIN, i64::MAX);
println!("U128 min is {} max is {}", u128::MIN, u128::MAX);
println!("I128 min is {} max is {}", i128::MIN, i128::MAX);
println!("USIZE min is {} max is {}", usize::MIN, usize::MAX);
println!("ISIZE min is {} max is {}", isize::MIN, isize::MAX);
}

Different types don't play nice together

fn main(){
    let x : i16 = 13;
    let y : i32 = -17;
    println!("{}", x * y);   // will not work
    // println!("{}", (x as i32)* y);
}

Be careful with math on ints

u8 is 8 bits and can store maximum value 2^8 - 1 = 255.

If we multiply: \(255*255=65025\).

How many bits do we need to store this value? We can take the log base 2 of the value.

>>> import math
>>> math.log2(255*255)
15.988706873717716

So we need 16 bits to store the product of two u8 values.

In general when we multiply two numbers of size \(n\) bits, we need \(2n\) bits to store the result.

Types - Floats

Why are they called floats?

• Two kinds: f32 and f64 (default)
• What do these mean?

Sizes of floats

#![allow(unused)]
fn main() {
println!("F32 min is {} max is {}", f32::MIN, f32::MAX);
println!("F32 min is {:e} max is {:e}", f32::MIN, f32::MAX);
println!("F64 min is {:e} max is {:e}", f64::MIN, f64::MAX);
}

Why these sizes?

• f32: 1 sign bit + 8 exponent bits + 23 significance bits
• f64: 1 sign bit + 11 exponent bits + 52 significance bits

Floats and Rust's type inference system

fn main(){
    let x:f32 = 4.0;
    let y:f32 = 4; // Will not work.  It will not autoconvert for you.

    let z = 1.25; // won't get automatically assigned a type yet

    println!("{:.1}", x * z);

    //println!("{:.1}", (x as f64) * z);
}

Formatting in println! (this didn't make it to your print-outs!)

You can control how numbers are displayed using format specifiers:

#![allow(unused)]
fn main() {
let total = 21.613749999999997;
let big_number = 1_234_567.89;
let small_number = 0.000123;
let count = 42;

// Float formatting
println!("Default: {}", total);         // Default: 21.613749999999997
println!("2 decimals: {:.2}", total);   // 2 decimals: 21.61
println!("Currency: ${:.2}", price);    // Currency: $19.99

// Scientific notation
println!("Scientific: {:e}", big_number);    // Scientific: 1.234568e6
println!("Scientific: {:.2e}", small_number); // Scientific: 1.23e-4

// Integer formatting
println!("Default: {}", count);         // Default: 42
println!("Width 5: {:5}", count);       // Width 5:    42
println!("Zero-pad: {:05}", count);     // Zero-pad: 00042
println!("Binary: {:b}", count);        // Binary: 101010
println!("Hex: {:x}", count);           // Hex: 2a
}

Useful patterns:

• {:.2} - 2 decimal places
• {:e} - scientific notation
• {:5} - fixed width 5
• {:b} - binary, {:x} - hexadecimal

Mini-Quiz

Take a minute to talk to a partner about what these do, then I'll call on you

1. cargo new my_project
2. cargo check
3. git add .
4. rustc hello.rs
5. git pull
6. cargo run --release
7. git commit -m "fix bug"

Types - Booleans (and logical operators)

• bool uses one byte of memory (why not one bit?)

#![allow(unused)]
fn main() {
let x = true;
let y: bool = false;

println!("{}", x && y); // logical and
println!("{}", x || y); // logical or
println!("{}", !y);    // logical not

}

Bitwise operators (just for awareness)

There are also bitwise operators that look similar to logical operators:

#![allow(unused)]
fn main() {
let x = true;
let y: bool = false;
println!("{}", x & y);  // bitwise and
println!("{}", x | y);  // bitwise or
}

But they also work on integers

fn main(){
    let x = 10;
    let y = 7;
    println!("{x:04b} & {y:04b} = {:04b}", x & y);
    println!("{x:04b} | {y:04b} = {:04b}", x | y);
    // println!("{}", x && y);
    // println!("{}", x || y);
}

So the negation of an int is...

#![allow(unused)]
fn main() {
let y = 7;
println!("!{y:04b} = {:04b} or {0}", !y);
}

Think/pair/share - What is this going to print?

#![allow(unused)]
fn main() {
let y:i8 = 7;
println!("{:016b}", y);
println!("{:016b}", !y);
println!("{:016b}", -1*y);
}

Types - Characters

• char defined via single quotes, uses four bytes of memory (that's how many bits?)
• For a complete list of UTF-8 characters check https://www.fileformat.info/info/charset/UTF-8/list.htm

#![allow(unused)]
fn main() {
let x: char = 'a';
let y = '🚦';
let z = '🦕';

println!("{} {} {}", x, y, z);
}

(Fun fact - try Control-Command-Space (Mac) or Windows-Key + . (Windows) to add emojis anywhere!)

Types - Strings

• A string slice (&str) is defined via double quotes (we'll talk much more about what this means later!)

fn main() {
    let s1 = "Hello! How are you, 🦕?";  // type is immutable borrowed reference to a string slice: `&str`
    let s2 : &str = "Καλημέρα από την Βοστώνη και την DS210";  // here we make the type explicit
    
    println!("{}", s1);
    println!("{}\n", s2);

    // This doesn't work.  You can't do String = &str
    //let s3: String = "Does this work?";
    
    let s3: String = "Does this work?".to_string();
    println!("{}", s3);

    let s4: String = String::from("How about this?");
    println!("{}\n", s4);

    let s5: &str = &s3;
    println!("str reference to a String reference: {}\n", s5);
    
    // This won't work. 
    // println!("{}", s1[3]);
    // println!("{}", s4[3]);

    // But you can index this way.
    println!("4th character of s1: {}", s1.chars().nth(3).unwrap());
    println!("3rd character of s3: {}", s4.chars().nth(2).unwrap());
}

Tuples in Rust

Tuples are a general-purpose data structure that can hold multiple values of different types.

#![allow(unused)]
fn main() {
let mut tuple = (1, 1.1);
let mut tuple2: (i32, f64) = (1, 1.1);  // type annotation is optional

let another = ("abc", "def", "ghi");

let yet_another: (u8, u32) = (255, 4_000_000_000);
}

Accessing elements of a tuple

Rust tuples are "0-based":

#![allow(unused)]
fn main() {
let mut tuple = (1,1.1);
println!("({}, {})", tuple.0, tuple.1);

tuple.0 = 2;

println!("({}, {})",tuple.0,tuple.1);

println!("Tuple is {:?}", tuple);
}

We can unpack a tuple by matching a pattern

#![allow(unused)]
fn main() {
// or pattern match and desconstruct
let mut tuple = (1,1.1);
let (a, b) = tuple;
println!("a = {}, b = {}",a,b);
}

Best Practices for tuples

When to Use Tuples:

• Small, related data: 2-4 related values
• Temporary grouping: Short-lived data combinations
• Function returns: Multiple return values
• Pattern matching: When destructuring is useful

Style Guidelines:

#![allow(unused)]
fn main() {
// Good: Clear, concise
let (width, height) = get_dimensions();

// Good: Descriptive destructuring
let (min_temp, max_temp, avg_temp) = analyze_temperatures(&data);

// Avoid: Too many elements
// let config = (true, false, 42, 3.14, "test", 100, false);  // Hard to read

// Avoid: Unclear meaning
// let data = (42, 13);  // What do these numbers represent?
}

Lecture 8 - Functions in Rust

Logistics

• Coffee slots today
• HW2 due Wednesday
• The first midterm is in two weeks

Follow-up to yesterday

• 2's complement (at the board) (but also, don't worry about it)
• The let x:u8 = 5; let y = -x; error
• Going over the shakespeare problem

Learning Objectives

By the end of this lecture, students should be able to:

• Write function signatures including parameter names, types, and return types
• Create functions that return the unit type () for side-effect-only operations
• Explain the difference between an expression and a statement in Rust
• Use expressions to assign values based on conditions

Function Syntax

We've seen lots of examples like this:

#![allow(unused)]
fn main() {
fn my_age_in_5_years(age: i16) -> i16 {
    let new_age = age + 5;
    return age; // you can just put "age" without return but "return" is clearer
}
}

General function template:

#![allow(unused)]
fn main() {
fn function_name(arg_name_1:arg_type_1,arg_name_2:arg_type_2) -> type_returned 
  // ^ This part is the "function signature"

{
    // Do stuff
    // return something
}
 // ^ This part is the "function body" and can be a statement or expression
}

Statements and expressions

Just as in math when we have:

• expressions like (\(a^2 + b^2)\)
• and equations like (\(a^2 + b^2 = c^2)\)

In rust we have expressions and statements

• Expressions simplify to a value (like a math expression)
• Statements do things but don't simplify to a value (kind of like an equation?)

So -

• y + 2 is an expression
• let x = y + 2; is a statement

Statements and expressions can be nested

let x = y + 2; is a statement BUT it INCLUDES y + 2 which is an expression

The reverse is also true - we can build complex expressions that include statements

#![allow(unused)]
fn main() {
let y = {
    let x = 2 * 3;
    x
};
}

A statement or expression - shout it out

#![allow(unused)]
fn main() {
let x = 5;                  // Statement or expression?
x + 2                       // Statement or expression?
println!("hello");          // Statement or expression?
my_function(5)              // Statement or expression?

let y = x + 2;              // Statement or expression?
{
    let z = 10;             // Statement or expression?
    z * 2                   // Statement or expression?
}                           // Statement or expression?

return x + 5;               // Statement or expression?

let x = {
    println!("doing work"); // Statement or expression?
    42                      // Statement or expression?
};                          // Statement or expression?

}

Maybe it was too easy to cheat because...

• Statements always end with semi-colons
• Expressions never end with semi-colons

Key insight: {} blocks are expressions that evaluate to their final line (if no semicolon).

Adding a semicolon turns an expression into a statement

fn main(){
    let a = {
        let x = 10;
        x + 5       // Expression 
    };
    println!("{}",a);

    let b = {
        let x = 10;
        x + 5;      // Statement 
    };
    println!("{}",b);
}

Let's look at return again now

We have two ways of returning from a function:

#![allow(unused)]
fn main() {
fn my_age_in_5_years(age: i16) -> i16 {
    let new_age = age + 5;
    return new_age;
}
}

#![allow(unused)]
fn main() {
fn my_age_in_5_years(age: i16) -> i16 {
    let new_age = age + 5;
    new_age
}
}

Why are these effectively the same thing?

But what happens if you don't return anything?

fn say_hello(who:&str) { // no -> return_type here
// fn say_hello(who:&str) -> () {
    println!("Hello, {}!",who);
}
 
fn main() {
    say_hello("world");
    say_hello("Boston");
    say_hello("DS210");

    // let z = say_hello("DS210");
    // println!("The function returned {:?}", z)
}

Functions that return no value

Functions that don't return or end in an expression return "the unit type" ()

() is an empty tuple that takes no memory (think of an empty set!)

This lets us have "side-effects only" functions that perform actions (printing, file I/O, etc.)

Passing parameters

3 ways to pass parameters

1. A parameter can be copied into a function (default for i32, bool, f64, other basic types)
2. A function can take ownership of a parameter (default for String, other complex types)
3. A function can borrow a parameter to "peek" at it without "owning" it (&str, &i32)

Examples:

#![allow(unused)]
fn main() {
fn greet_person(first_name: String, last_name: &str, age: u32) {
    // first_name now OWNS what was passed to it
    // last_name is BORROWING what was passed to it
    // age COPIED what was passed to it
    println!("Hello, {} {}! You are {} years old.", 
             first_name, last_name, age);
}
}

We'll talk a lot more about owning vs borrowing later. For now, some simple rules to get started:

Quick Rules for Beginners:

• Use &str for string parameters (lets you pass in any string without taking it)
• Use & before the parameter name when you want to "peek" at data without taking it
• Basic types like i32, f64, bool are automatically copied - no worries there
• If Rust complains about ownership, try adding & to your parameter type
• You typically can't use a reference (&) in a return value - thats why you'll see String as a return type in HW2

Examples:

#![allow(unused)]
fn main() {
fn print_name(name: &str) { /* name is borrowed - original still usable */ }
fn calculate_area(width: f64, height: f64) -> f64 { /* both copied */ }
}

Lecture 7 Review Quiz

Take 2 minutes with a partner to discuss these questions and I'll call on you

1. Can you change x to a different type using mut? Using shadowing?
2. What's the largest value a u8 can hold?
3. What are three different changes you could make so that this compiles?

#![allow(unused)]
fn main() {
let x: i32 = 10; 
let y: i16 = 5; 
let sum = x + y;
}

4. What's wrong with this? const PI = 3.14;

Function Design Principles

Best Practice - Single Responsibility

#![allow(unused)]
fn main() {
// Good: Single purpose
fn calculate_cook_time(base_time: u32, servings: u32) -> u32 {
    base_time + (servings * 2)
}

// Good: Clear separation of concerns
fn format_time(minutes: u32) -> String {
    if minutes >= 60 {
        format!("{}h {}m", minutes / 60, minutes % 60)
    } else {
        format!("{}m", minutes)
    }
}

fn display_recipe_info(base_cook_time: u32, servings: u32) {
    let total_time = calculate_cook_time(base_cook_time, servings);
    println!("Cook time for {} servings: {}",
             servings, format_time(total_time));
}
}

Common Patterns - Pure Functions vs. Side Effects

#![allow(unused)]
fn main() {
// Pure function: No side effects
fn add(x: i32, y: i32) -> i32 {
    x + y
}

// Function with side effects: Prints to console
fn add_and_print(x: i32, y: i32) -> i32 {
    let result = x + y;
    println!("{} + {} = {}", x, y, result);
    result
}
}

Common Patterns - Validation Functions

#![allow(unused)]
fn main() {
fn is_valid_age(age: i32) -> bool {
    age >= 0 && age <= 150
}

fn is_valid_email(email: &str) -> bool {
    email.contains('@') && email.contains('.')
}
}

Common Patterns - Conversion Functions

#![allow(unused)]
fn main() {
fn celsius_to_fahrenheit(celsius: f64) -> f64 {
    celsius * 9.0 / 5.0 + 32.0
}

fn fahrenheit_to_celsius(fahrenheit: f64) -> f64 {
    (fahrenheit - 32.0) * 5.0 / 9.0
}
}

Common Patterns - Helper Functions

#![allow(unused)]
fn main() {
fn get_absolute_value(x: i32) -> i32 {
    if x < 0 { -x } else { x }
}
}

Function Naming Conventions

Rust Naming Guidelines:

• snake_case
• Descriptive names that indicate purpose
• Verb phrases for functions that perform actions
• Predicate phrases for functions that return booleans (is_, has_, can_)

Examples:

#![allow(unused)]
fn main() {
fn calculate_distance(x1: f64, y1: f64, x2: f64, y2: f64) -> f64 { /* ... */ }
fn is_prime(n: u32) -> bool { /* ... */ }
fn has_permission(user: &str, resource: &str) -> bool { /* ... */ }
fn can_access(user_level: u32, required_level: u32) -> bool { /* ... */ }
}

Last thing - Using if Statements (TC 12:45)

We've glossed over this so far - let's get into some details

Syntax:

#![allow(unused)]
fn main() {
if condition {
    // 
} else if {
    // 
} else {
    //
}
}

• else if and else parts optional

Example of if in a function

fn and(p:bool, q:bool, r:bool) -> bool {
    if !p {
        println!("p is false");
        return false;
    }
    if !q {
        println!("q is false");
        return false;
    }
    println!("r is {}", r);
    return r;
}

fn main() {
    println!("{}", and(true, false, true));
}

Best Practices for if statements

1. Use consistent indentation (4 spaces or tabs)
2. Keep conditions readable - use parentheses for clarity when needed
3. Prefer early returns in functions to reduce nesting
4. Use else if for multiple conditions rather than nested if

Example of Good Style:

#![allow(unused)]
fn main() {
fn classify_grade(score: f64) -> char {
    if score > 90.0 {
        'A'
    } else if score > 80.0 {
        'B'
    } else if score > 70.0 {
        'C'
    } else {
        'D'
    }
}
}

Even though Rust doesn't require tabs like this it's still a good idea for readability!

Bringing it together with expressions

You can even use conditional expressions as values!

Python:

x = 100 if (x == 7) else 200 

Rust:

#![allow(unused)]
fn main() {
let x = 4;
let z = if x == 7 {100} else {200};
println!("{}",z);
}

// won't work: same type needed
fn main(){
    let x = 4;
    println!("{}",if x == 7 {100} else {1.2});
}

But don't do it just because you can

#![allow(unused)]
fn main() {
// This is technically valid but TERRIBLE code please DO NOT DO THIS
let x = 4;
let result = if x > 0 {
    if x < 10 {
        let temp = x * x;
        let bonus = if temp > 10 { 5 } else { 2 };
        temp + bonus
    } else {
        let factor = x / 2;
        if factor > 3 {
            factor * 3
        } else {
            factor + 1
        }
    }
} else {
    0
};
println!("Result: {}", result);
}

Lecture 9 - Loops

Follow-up from Friday

• Your papers are up here
• HW2 is due Wednesday. Please get started soon so we have time to help if you need it!

Office hours updates

Ava - Tuesday 3:45-5:45, 15th floor CDS

Prof Wheelock - Wednesday 2:30-4, 1506 in CDS

Joey - 3:30-5:30 Thursday, 15th floor CDS

Pratik - 4:00-6:00 on Fridays, 15th floor CDS

Clarifying "one expression per scope"

fn classify_grade(score: f64) -> char {
    if score > 90.0 {
        'A'
    } else if score > 80.0 {
        'B'
    } else if score > 70.0 {
        'C'
    } else {
        'D'
    }
}

fn main(){
    println!("{}",classify_grade(5.5));
}

A complete solution to Friday's exercise

fn calculate_final_price(sticker_price: f64, tax_rate: f64, has_membership: bool) -> f64 {
    // Handle edge cases
    if sticker_price < 0.0 { println!("Warning: Negative price detected!"); }
    
    if tax_rate < 0.0 || tax_rate > 1.0 { println!("Warning: Unusual tax rate: {:.2}", tax_rate); }
    
    let final_price = if has_membership {
        sticker_price * (1.0 + tax_rate) * 0.9 
    } else {
        sticker_price * (1.0 + tax_rate)
    };
    
    println!("Final Price is ${:.2}", final_price);
    
    final_price
}

A few ways to write the core of the function (without printing)

#![allow(unused)]
fn main() {
fn calculate_final_price(sticker_price: f64, tax_rate: f64, has_membership: bool) -> f64 {
    if has_membership {
        sticker_price * (1.0 + tax_rate) * 0.9 
    } else {
        sticker_price * (1.0 + tax_rate)
    }
}
}

#![allow(unused)]
fn main() {
fn calculate_final_price(sticker_price: f64, tax_rate: f64, has_membership: bool) -> f64 {
    let mut final_price = sticker_price * (1.0 + tax_rate)
    if has_membership { final_price *= 0.9; };
    final_price
}
}

#![allow(unused)]
fn main() {
fn calculate_final_price(sticker_price: f64, tax_rate: f64, has_membership: bool) -> f64 {
    let membership_discount = if has_membership { 0.9 } else { 1.0 };
    sticker_price * (1.0 + tax_rate) * membership_discount
}
}

Learning Objectives

• Use while, for, loop, break, and continue to build flexible loops
• Use break to return values from loops and continue to skip iterations
• Use for loops with ranges (.. and ..=), array iteration, and enumerate
• Create and manipulate fixed-size arrays with indexing, sorting, and length operations
• Apply loop labeling to control nested loop behavior
• Choose appropriate loop types based on use case requirements

for loops and ranges

Usage: loop over a range or collection

A range is (start..end), e.g. (1..5), where the index will vary as

$$ \textrm{start} \leq \textrm{index} < \textrm{end}. $$

Unless you use the notation (start..=end), in which case the index will vary as

$$ \textrm{start} \leq \textrm{index} \leq \textrm{end} $$

#![allow(unused)]
fn main() {
for i in (1..5) {
    println!("{}",i);
};
}

More ways to play with ranges

#![allow(unused)]
fn main() {
for i in (1..5).rev() { // reverse order
    println!("{}",i)
};
}

#![allow(unused)]
fn main() {
for i in (1..=5) { // inclusive range
    println!("{}",i);
};
}

#![allow(unused)]
fn main() {
println!("This is a test");
for i in (1..5).step_by(2) { // every other element 
    println!("{}",i);
};
}

#![allow(unused)]
fn main() {
println!("And now for the reverse");
for i in (1..5).step_by(2).rev() {
    println!("{}",i)
};
}

I suggest always trying out / printing what you're looping over during early development to make sure it's doing what you want it to do!

Arrays in Rust

• Arrays in Rust are of fixed length (we'll learn about more flexible Vec later)
• All elements of the same type (unlike tuples)
• You cannot add or remove elements from an array (but you can change its value)

What will this return?

#![allow(unused)]
fn main() {
let mut arr = [1,7,2,5,2];
arr[1] = 13;
println!("{} {}",arr[0],arr[1]);
println!("{}",arr.len());
}

for loop over an array

#![allow(unused)]
fn main() {
let mut arr = [1,7,2,5,2];
for x in arr {
    println!("{}",x);
};
}

Quick tricks for making arrays

#![allow(unused)]
fn main() {
// create array of given length and fill it with a specific value
// note the semi-colon vs the comma!
let arr2 = [15;3];
for x in arr2 {
    print!("{} ",x);
}
println!();
}

#![allow(unused)]
fn main() {
// you can still infer or annotate types
let arr2 : [u8;3] = [15;3];
}

Common Array Operations

Arrays come with useful built-in methods:

#![allow(unused)]
fn main() {
let mut scores = [85, 92, 78, 96, 88];

// Get the length
println!("Number of scores: {}", scores.len());

// Sort the array (modifies the original array)
scores.sort();
println!("Sorted scores: {:?}", scores);

// Check if array contains a value
println!("Contains 92? {}", scores.contains(&92));  // Note the & here!
println!("Contains 100? {}", scores.contains(&100));
}

Note: {:?} is debug formatting - prints the entire array contents

Iterating with Indices

Sometimes you need both the position and the value:

#![allow(unused)]
fn main() {
let fruits = ["apple", "banana", "orange"];

// Method 1: Using enumerate()
for (index, &fruit) in fruits.iter().enumerate() { // note the & here!
    println!("fruits[{}] = {}", index, fruit);
}

// Method 2: Using index range
for i in 0..fruits.len() {
    println!("fruits[{}] = {}", i, fruits[i]);
}
}

When to use each:

• Use enumerate() when you need both index and value
• Stick to index range when you need to modify array elements

Lecture 8 Review Quiz

Take 2 minutes with a partner to review functions from last lecture:

1. What's wrong with this function signature?

   #![allow(unused)]
   fn main() {
   fn calculate_area(width, height) -> f64 {
   }

2. What's wrong with this function?

   #![allow(unused)]
   fn main() {
    fn mystery(x: i32) -> i32 {
        let result = x * 2;
        result + 1;
    }
   }

3. How can you fix this so it compiles?

   #![allow(unused)]
   fn main() {
   let x = 4;
   let y = 4.5;
   let z = x + y;
   println!("{}",z);
   }

while loops

While loops continue as long as a condition remains true (very similar to python)

#![allow(unused)]
fn main() {
let mut number = 3;

while number != 0 {
    println!("{number}!");
    number -= 1;
}
println!("LIFTOFF!!!");
}

(What's a nice bit of style feedback here?)

Infinite loop

#![allow(unused)]
fn main() {
loop {
    // THIS WILL RUN OVER AND OVER FOREVER
}
}

• Similar to while (True) in python
• Need to use break to jump out of the loop!

A loop can return a value (break can act like return)

Just like the body of a function, a loop is an expression

To quit early, with or without a value:

• use return in a function
• use break in a loop

#![allow(unused)]
fn main() {
let mut counter = 0;
let final_count = loop {
    counter += 1;
    if counter > 100 {
        break counter*2; // Return twice the final counter value
    }
};
println!("{}",final_count);
}

You can also break out of for and while loops but can't get a value out of them. Can you guess why? (hint: because it's Rust, it's about safety...)

Using continue to jump to the next iteration

Think/pair/share - what is this going to print?

#![allow(unused)]
fn main() {
let mut x = 1;

let result = loop {  // you can capture a return value
    if x == 3 {
        x = x+1;
        continue;    // skip the rest of this loop body and start the next iteration
    }
    println!("X is {}", x);
    x = x + 1;
    if x==6 {
        break x*2;   // break with a return value
    }
};

println!("Result is {}", result);
}

Labeling loops to target with continue and break.

Labels let you use continue or break on any nested layer.

USE CAUTION - this can make your code hard to read and it's probably a red flag if you find yourself needing it often

fn main() {
    let mut count = 0;
    'counting_up: loop {
        println!("count = {count}");
        let mut remaining = 10;

        loop {
            println!("remaining = {remaining}");
            if remaining == 9 {
                break;
            }
            if count == 2 {
                break 'counting_up;
            }
            remaining -= 1;
        }
        count += 1;
    }
    println!("End count = {count}");
}

Loop Selection Guidelines

For Loops:

• Iterating over ranges or collections
• When you need an index of what loop you're on

While Loops:

• Continue until some condition changes
• Don't know at the start how many times to loop

Loop (Infinite):

• Breaking on complex conditions (too much to include in while)
• Breaking at different places under different conditions

Activity time

Lecture 10 - Enums and Pattern Matching in Rust

Logistics

• Actitvity 9 solutions are posted on the site
• HW3 will be due next Thursday - the night before the exam
• Exam 1 is a week from Friday
  • Format: similar to activities (a bit easier) and mid-lecture quizes - match/define, fill-in, find bugs, short answer, one short hand-coding problem
  • No notes / reference sheets
  • Monday will cover new material that will NOT be on the exam
  • On Monday I will give you a final list of topics to review
  • Wednesday will be a review session with practice problems
• HW2 is due TONIGHT at midnight
  • I have office hours today and we'll answer questions on piazza until ~6pm
  • Your submission is done when you've merged your work into main and then pushed to GitHub
  • You can check to make everything looks good by navigating to GitHub.

Grading rubric

Homework grading

• On the syllabus: 1/3 correctness, 1/3 process, 1/3 style / best practices
• In practice: 1/2 autograder (passing tests), 1/2 qualitative review (by CAs and TAs)

How this intersects with the lateness and corrections policies

• If you push your last commit before the deadline, you get full credit. If you push again within the 48-hour late submission period, your grade will get scaled to 80%, and corrections can only bring you up to 80%.
• At the 48-hour mark you will be locked out and won't be able to push until after your homework is graded.
• After your homework is graded, you have one week to submit corrections:
  • Corrections for correctness / test-passing can recover half-credit
  • Corrections from feedback (the rubric) can recover full credit
• A week after the homework is initially graded, we will shut down editing for good and record final grades (if you made corrections).

Some examples

Person 1

• You submit your homework on time and get 100% on the autograder and 70% on the rubric, so your initial grade is 85%.
• You push a new version of your homework within a week of receiving your grade, accounting for all the feedback you received, making your final grade 100%.

Person 2

• You submit your homework 24 hours late and get 100% on the autograder and 90% on the rubric, so your initial grade is 95% * 0.8 = 76%.
• You are capped at 80% for turning the assignment in late and decide not to push corrections, making your final grade 76%.

Person 3

• You submit on time passing 6/10 tests for an autograder score of 60%, and get 70% on the rubric, so your initial grade is 65%.
• You make corrections to pass all tests and fix all points of feedback, improving your autograde score to 80% and rubric score to 100%, making your final grade 90%.

Grading rubric for HW2 (will be similar for future HWs)

• We will add a "code best practices" category later (including "idiomatic" Rust, error handling, efficiency/memory usage, ownership/borrowing) but we're not ready for it yet.

Learning Objectives

By the end of this lecture, students should be able to:

• Define custom enum types with variants and associated data
• Use #[derive(Debug)] and #[derive(PartialEq)] for displaying and comparing enums
• Use match statements for exhaustive pattern matching on enums
• Work with Rust's built-in Option<T> and Result<T, E> enums

Enums

• enum for "enumeration"
• allows you to define a type (like i32 or bool) by enumerating its possible variants
• use let to create instances of the enum variants

#![allow(unused)]
fn main() {
// define the enum and its variants
enum Direction {
    North,
    East,
    South,
    West,
    SouthWest,
}

// create instances of the enum variants
let dir_1 = Direction::North;   // dir is inferred to be of type Direction
let dir_2: Direction = Direction::South; // dir_2 is explicitly of type Direction
}

Using "use" as a shortcut

enum Direction {
    North,
    East,
    South,
    West,
    SouthWest,
}
// Bring the variant `East` into scope
use Direction::East;
// Bringing two options into the current scope
use Direction::{South,West};

// we didn't have to specify "Direction::"
let dir_3 = East;

// Bringing all options in - THIS WON'T WORK IF THE ENUM IS IN THE SAME FILE
use Direction::*;
let dir_4 = North;

Using enums as parameters

We can also define a function that takes our new type as an argument.

fn turn(dir: Direction) { ... }

Displaying enums (#[derive(Debug)])

By default Rust doesn't know how to display a new enum type. We actually have to tell Rust we want to be able to do this first by adding the Debug "trait"

// #[derive(Debug)]
enum Direction {
    North,
    East,
    South,
    West,
}
use Direction::*;

fn main(){
    let dir = North;
    println!("{:?}",dir);
}

Comparing enums (#[derive(PartialEq)])

By default Rust doesn't know how to compare enum values for equality. We need to add the PartialEq "trait" to enable == and != comparisons.

// #[derive(PartialEq)]
enum Direction {
    North,
    East,
    South,
    West,
}
use Direction::*;

fn main(){
    let dir1 = North;
    let dir2 = North;
    let dir3 = South;

    println!("{}", dir1 == dir2); 
    println!("{}", dir1 != dir3); 
}

Control Flow with match

The match statement is used to control flow based on the value of an enum.

let dir = East;

match dir {
    North => println!("N"),
    South => println!("S"),
    West => {  // can do more than one thing
        println!("Go west!");
        println!("W")
    }
    East => println!("E"),
};

If we tried doing this with if/else statements it would have to look like:

// The ugly if/else version:
if dir.as_u8() == Direction::North.as_u8() {
    println!("N");
} else if dir.as_u8() == Direction::East.as_u8() {
    println!("E");
} else if dir.as_u8() == Direction::South.as_u8() {
    println!("S");
} else if dir.as_u8() == Direction::West.as_u8() {
    println!("Go west!");
    println!("W");
} else {
    // This should never happen, but compiler doesn't know that!
    unreachable!();
}

Covering all variants with match

match is exhaustive, so we must cover all the variants!

If we didn't...

enum Direction {
    North,
    East,
    South,
    West,
}
use Direction::*;
fn main() {
let dir_2: Direction = South;

match dir_2 {
    North => println!("N"),
    South => println!("S"),
    // East and West not covered
};
}

But there is a way to match anything left.

enum Direction {
    North,
    East,
    South,
    West,
}
use Direction::*;
fn main() {
let dir_2: Direction = Direction::North;

match dir_2 {
    North => println!("N"),
    South => println!("S"),
    
    // match anything left
    _ => (),  // covers all the other variants but doesn't do anything
}
}

WARNING - your catch-all has to go last or it'll gobble everything up!

match dir_2 {
    _ => println!("anything else"),
    
    // will never get here!!
    North => println!("N"),
    South => println!("S"),
}

Putting Data in an Enum Variant

• Each variant can come with additional information

#![allow(unused)]
fn main() {
#[derive(Debug)] 
enum DivisionResult {
    Answer(u32), 
    DivisionByZero,
}

fn divide(x:u32, y:u32) -> DivisionResult {
    if y == 0 {
        return DivisionResult::DivisionByZero;
    } else {
        return DivisionResult::Answer(x / y); 
    }
}

let (a,b) = (9,3);  // this is just short-hand for let a = 9; let b = 3;

match divide(a,b) {
    DivisionResult::Answer(result)  // assigns the variant value to result
        => println!("This result is {}",result),
    DivisionResult::DivisionByZero
        => println!("noooooo!!!!"),
};
}

Variants with multiple values

#![allow(unused)]
fn main() {
enum DivisionResultWithRemainder {
    Answer(u32,u32),  // Store the result of the integer division and the remainder
    DivisionByZero,
}

fn divide_with_remainder(x:u32, y:u32) -> DivisionResultWithRemainder {
    if y == 0 {
        DivisionResultWithRemainder::DivisionByZero
    } else {
        DivisionResultWithRemainder::Answer(x / y, x % y) // Return the integer division and the remainder
    }
}

let (a,b) = (9,4);
match divide_with_remainder(a,b) {
    DivisionResultWithRemainder::Answer(result,remainder) => {
            println!("the result is {}",result);
            println!("the remainder is {}",remainder);
    }
    DivisionResultWithRemainder::DivisionByZero
        => println!("noooooo!!!!"),
};
}

match as expression

The result of a match can be used as an expression.

Each branch (arm) returns a value.

#[derive(Debug)]
enum Direction {
    North,
    East,
    South,
    West,
}
use Direction::*;
fn main() {
// swap east and west
let mut dir_facing = North;
println!("{:?}", dir_facing);

let after_turning_left = match dir_facing {
    North => West,
    West => South,
    South => East,
    East => North
};

println!("{:?}", after_turning_left);
}

Beyond enums - pattern matching other types (FYI)

match works on more than just enums:

Matching tuples:

#![allow(unused)]
fn main() {
let point = (3, 5);
match point {
    (0, 0) => println!("Origin"),
    (0, y) => println!("On Y-axis at {}", y),
    (x, 0) => println!("On X-axis at {}", x),
    (x, y) => println!("Point at ({}, {})", x, y),
}
}

Matching ranges:

#![allow(unused)]
fn main() {
let age = 25;
match age {
    0..=12 => println!("Child"),
    13..=19 => println!("Teenager"),
    20..=64 => println!("Adult"),
    65.. => println!("Senior"),
}
}

Matching conditions:

#![allow(unused)]
fn main() {
let number = 42;
match number {
    x if x % 2 == 0 => println!("{} is even", x),
    x => println!("{} is odd", x),
}
}

Destructuring arrays:

#![allow(unused)]
fn main() {
let arr = [1, 2, 3];
match arr {
    [1, 2, 3] => println!("Exact match"),
    [1, _, _] => println!("Starts with 1"),
    [_, _, 3] => println!("Ends with 3"),
    _ => println!("Something else"),
}
}

Quick Review: Lectures 7-9

1. Variables & Types (Lecture 7)

#![allow(unused)]
fn main() {
let x = 5;
x = 10;  // What happens here?
}

1. Works fine
2. Compiler error
3. Runtime error

2. Functions (Lecture 8)

#![allow(unused)]
fn main() {
fn calculate(a: i32, b: i32) -> i32 {
    a + b; 
}
}

What does this function return?

1. The sum of a and b
2. The unit type ()
3. A compiler error

3. Loops & Arrays (Lecture 9)

#![allow(unused)]
fn main() {
let arr = [1, 2, 3, 4, 5];
for (index, value) in arr.iter().enumerate() {
    if value % 2 == 0 {
        ________ 
    }
    println!("Index: {}, Value: {}", index, value);
}
}

What goes in the blank to skip to next iteration without printing?

Enum Option<T>

There is a built-in enum Option<T> with two variants:

• Some(T) -- The variant Some contains a value of type T
• None

Useful for when there may be no output

• Like None or null in other languages
• Rust makes you explicitly handle them, preventing bugs that are extremely common in other languages
• This might look a little like optional parameters in python (def myfn(arg: Optional[int] = None): but functions differently)

An Option<T> example

Here's example prime number finding code that returns Option<u32> if a prime number is found, or None if not.

If a prime number is found, it returns Some(u32) variant with the prime number.

If the prime number is not found, it returns None.

fn main(){
    fn is_prime(x:u32) -> bool {
        if x <= 1 { return false;}
        for i in 2..=((x as f64).sqrt() as u32) {
            if x % i == 0 { return false; }
        } 
        true
    }

    fn prime_in_range(a:u32,b:u32) -> Option<u32> {  // returns an Option<u32>
        for i in a..=b {
            if is_prime(i) {return Some(i);}
        }
        None
    }

    let tmp : Option<u32> = prime_in_range(90,906);
    // let tmp : Option<u32> =  prime_in_range(20,22);
    println!("{:?}",tmp);
}

Extracting the contents of an Option with match

fn main() {
let tmp : Option<u32> = Some(3);
// let tmp: Option<u32> = None;

match tmp {
    Some(x) => println!("A second way: {}",x),
    None => println!("None"),
};
}

FYI - other ways to extract values (but we'll generally prefer match):

fn main() {
let tmp : Option<u32> = Some(3);
// let tmp: Option<u32> = None;

if let Some(x) = tmp {
    println!("One way: {}",x);
}

println!("Another way: {}", tmp.unwrap()); // this will panic if tmp is None!
}

Enum Option<T>: useful methods

Check the variant

• .is_some() -> bool
• .is_none() -> bool

Get the value in Some or terminate with an error

• .unwrap() -> T
• .expect(message) -> T

Get the value in Some or a default value

• .unwrap_or(default_value:T) -> T

Enum Result<T, E>

We saw this one with guessing game. Another built-in enum with two variants:

• Ok(T)
• Err(E)

Similar to Option except we have a value associated with both cases.

Useful when you want to pass a solution or information about an error.

For example:

#![allow(unused)]
fn main() {
fn divide_safely(x: f64, y: f64) -> Result<f64, String> {
    if y == 0.0 {
        Err("Cannot divide by zero!".to_string())
    } else {
        Ok(x / y)
    }
}
}

Enum Result<T, E>: useful methods

Check the variant

• .is_ok() -> bool
• .is_err() -> bool

Get the value in Ok or terminate with an error

• .unwrap() -> T
• .expect(message) -> T

Get the value in Ok or a default value

• .unwrap_or(default_value:T) -> T

Summary of Option<T> and Result<T,E>

• Option<T> has variants that look like Some(value of type T) and None
• Result<T,E> has variants that look like Ok(value of type T) and Err(error_info of type E)

Activity Time

Bonus - Simplified matching with if let (FYI)

We can't do a quick if on an enum like this:

enum Direction {
    North,
    East,
    South,
    West,
}
use Direction::*;
fn main() {
let dir: Direction = North;
if dir == North {
    println!("North");
}
}

Instead we would have to:

enum Direction {
    North,
    East,
    South,
    West,
}
use Direction::*;
fn main() {
let dir: Direction = North;
match dir {
    North => println!("North"),
    _ => (),
};
}

But this happens often enough that there's a shorthand:

enum Direction {
    North,
    East,
    South,
    West,
}
use Direction::*;
fn main() {
let dir: Direction = North;
if let North = dir { // YES THIS LOOKS BACKWARDS! It's a more like match than if
    println!("North");
};
}

You can use else to match anything else like a regular if statement

if let North = dir { 
    println!("North");
} else {
    println!("Going somewhere else");
};

Lecture 11 - Error handling in Rust

Logistics - Homework

• HW1: Posted, corrections due next Friday
• HW2: Feedback will trickle in, grades will be posted after all feedback is in
• HW3: Due next Thursday

Logistics - Exam

What I've heard from you:

• Lectures have felt rushed
• You know you've learned a lot but you're not sure you can demonstrate it
• We need more practice with Rust syntax and core concepts

So:

• I'm postponing Monday's new content until WAY later in the semester
• We'll use Monday AND Tuesday for review and practice
• I'm dropping another homework from the schedule - remaining homeworks will all have 2 weeks to complete

Solutions to Wednesday's Activity

(See class site)

Learning Objectives

By the end of this lecture, students should be able to:

• Understand what panic! does
• Decide when to use panic! vs Result<T,E>
• Use the panic! macro directly, or implicitly via unwrap or expect
• Create functions that return Result and handle both success and error cases
• Use match and ? operator to handle or pass along Result values

Rust's Error Philosophy: Errors as Data (TC 12:25)

Most languages: Errors are "exceptional" events that get thrown and caught

try:
    result = divide(a, b)
    # continue with result
except DivisionByZeroError:
    # handle error

Rust: Errors are just another kind of data that functions can return

#![allow(unused)]
fn main() {
match divide(a, b) {
    Ok(result) => { /* continue with result */ },
    Err(error) => { /* handle error */ },
}
}

Error Handling in Rust

Two basic options:

• terminate when an error occurs: macro panic!(...)
• pass information about an error: enum Result<T,E>

Option 1 : Choose to panic!

What it means to panic:

• stops execution ("crashes")
• starts "unwinding the stack" (more on that later)
• prints a message to the console
• tells us where in the code the panic occurred

Macro panic!(...)

• Use for unrecoverable errors

fn divide(a:u32, b:u32) -> u32 {
    if b == 0 {
        panic!("I'm sorry, Dave. I'm afraid I can't do that.");
    }
    a/b
}

fn main() {
    println!("{}",divide(20,7));
    // println!("{}",divide(20,0));
}

Getting more info out of a panic!

• Use RUST_BACKTRACE=1 cargo run to get a backtrace like this:

$ RUST_BACKTRACE=1 cargo run
thread 'main' panicked at src/main.rs:4:6:
index out of bounds: the len is 3 but the index is 99
stack backtrace:
   0: rust_begin_unwind
             at /rustc/4d91de4e48198da2e33413efdcd9cd2cc0c46688/library/std/src/panicking.rs:692:5
   1: core::panicking::panic_fmt
             at /rustc/4d91de4e48198da2e33413efdcd9cd2cc0c46688/library/core/src/panicking.rs:75:14
   2: core::panicking::panic_bounds_check
             at /rustc/4d91de4e48198da2e33413efdcd9cd2cc0c46688/library/core/src/panicking.rs:273:5
   3: <usize as core::slice::index::SliceIndex<[T]>>::index
             at file:///home/.rustup/toolchains/1.85/lib/rustlib/src/rust/library/core/src/slice/index.rs:274:10

   4: core::slice::index::<impl core::ops::index::Index<I> for [T]>::index
             at file:///home/.rustup/toolchains/1.85/lib/rustlib/src/rust/library/core/src/slice/index.rs:16:9
   5: <alloc::vec::Vec<T,A> as core::ops::index::Index<I>>::index
             at file:///home/.rustup/toolchains/1.85/lib/rustlib/src/rust/library/alloc/src/vec/mod.rs:3361:9
   6: panic::main
             at ./src/main.rs:4:6
   7: core::ops::function::FnOnce::call_once
             at file:///home/.rustup/toolchains/1.85/lib/rustlib/src/rust/library/core/src/ops/function.rs:250:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

Shortcuts to panic!

Both unwrap and expect will call panic! if there is an error.

#![allow(unused)]
fn main() {
let greeting_file = File::open("hello.txt").unwrap();
}

#![allow(unused)]
fn main() {
let greeting_file = File::open("hello.txt")
        .expect("hello.txt should be included in this project");
}

Quick Quiz

1. Which #[derive()] trait lets you print an enum with {:?}?

2. Why won't this compile?

#![allow(unused)]
fn main() {
enum Status {
    Loading,
    Complete,
    Error,
}

let status = Status::Complete;
match status {
    Status::Complete => println!("Finished!"),
    Status::Error => println!("An error has occurred!"),
}
}

3. What do you think this will print?

#![allow(unused)]
fn main() {
let result = Some(42);
match result {
    Some(x) if x > 40 => println!("Large: {}", x),
    Some(x) => println!("Small: {}", x),
    None => println!("Nothing"),
}
}

Enum Result<T,E>

#![allow(unused)]
fn main() {
enum Result<T,E> {
    Ok(T),
    Err(E),
}
}

Functions can use it to

• return a result
• or information about an encountered error

fn divide(a:u32, b:u32) -> Result<u32, String> {
    if b != 0 {
        Ok(a / b)
    } else {
        let str = format!("Division by zero {} {}", a, b);
        Err(str)
    }
}

fn main(){
    println!("{:?}",divide(20,7));
    // println!("{:?}",divide(20,0));
}

When to use Result<T,E> and when to panic!

• Use panic! when the error is unrecoverable
• Use Result when you want to handle the error and continue execution

Concept: Propagating Errors

Error propagation means passing errors up through multiple layers of function calls, rather than handling them immediately at the lowest level.

Think of it like a company hierarchy:

• Junior developer encounters a bug they can't fix, reports it to senior developer
• Senior dev can't solve it, escalates to team lead
• Each level decides: "Can I handle this?" or "Pass it up the chain"

Or like the court system:

• Local court -> Appeals court -> State supreme court -> Federal supreme court
• Each level can either handle the case or pass it to a higher authority

┌─────────────────┐    ┌─────────────────┐    ┌─────────────────┐
│   Function A    │───▶│   Function B    │───▶│   Function C    │
│ (high level)    │    │ (middle level)  │    │ (low level)     │
│                 │    │                 │    │                 │
│ Can decide what │    │ Maybe can't     │    │ Detects error   │
│ to do with      │    │ handle errors   │    │ but doesn't     │
│ different errors│    │ meaningfully    │    │ know context    │
└─────────────────┘    └─────────────────┘    └─────────────────┘
                                                      │
                                                      ▼
                                              Error bubbles up!

• Function C (low-level): Knows what went wrong, but not what to do about it
• Function A (high-level): Has context to decide how to respond to different errors

Propagating errors in Rust

• We are interested in the positive outcome: t in Ok(t)
• But if an error occurs, we want to propagate it ("pass the buck")
• This can be handled using match statements

// compute a/b + c/d
fn calculate(a:u32, b:u32, c:u32, d:u32) -> Result<u32, String> {
    let first = match divide(a,b) {
        Ok(t) => t,
        Err(e) => return Err(e),
    };
    let second = match divide(c,d) {
        Ok(t) => t,
        Err(e) => return Err(e),
    };    
    Ok(first + second)
}

fn divide(a:u32, b:u32) -> Result<u32, String> {
    if b != 0 {
        Ok(a / b)
    } else {
        let str = format!("Division by zero {} {}", a, b);
        Err(str)
    }
}

fn main(){
    println!("{:?}", calculate(16,4,18,3));
    println!("{:?}", calculate(16,0,18,3));
}

The question mark shortcut

• Place ? after an expression that returns Result<T,E>

• This will:

  • give the content of Ok(t)
  • or return Err(e) from the encompassing function

fn calculate(a:u32, b:u32, c:u32, d:u32) -> Result<u32, String> {
    Ok(divide(a,b)? + divide(c,d)?)
}

fn divide(a:u32, b:u32) -> Result<u32, String> {
    if b != 0 {
        Ok(a / b)
    } else {
        let str = format!("Division by zero {} {}", a, b);
        Err(str)
    }
}

fn main(){
    println!("{:?}", calculate(16,4,18,3));
    println!("{:?}", calculate(16,0,18,3));
}

Caution with ?

The ? operator can only be used in functions whose return type is compatible with the value the ? is used on.

• If you use ? on a Result<T,E>, the function must return Result<..., E> (with the same E!)
• If you use ? on an Option<T>, the function must return Option<...>.

Activity Time

Lecture 12 - Midterm Review

Welcome to Review Day!

You've learned a lot in just a few weeks! Today we'll:

• Review key concepts you need to master for the midterm
• Practice with interactive questions
• Clarify what you need to know vs. what's just context
• Build confidence for the exam

Reminders about the exam

• Friday, 12:20-1:10
• No reference sheets or calculators
• Two exam versions and set (but not assigned) seating

How Today Works

1. Quick concept review for each topic
2. Quick questions think-pair-share and cold calls

Development Tools

Shell/Terminal Commands (Lecture 2)

For the midterm, you should recognize and recall:

• pwd - where am I?
• ls - what's here?
• ls -la - more info and hidden files
• mkdir folder_name - make a folder
• cd folder_name - move into a folder
• cd .. - move up to a parent folder
• cd ~ - return to the home directory
• rm filename - delete a file

You DON'T need to: Memorize complex command flags or advanced shell scripting

Git Commands (Lecture 3)

For the midterm, you should recognize and recall:

• git clone - get a repository, pasting in the HTTPS or SSH link
• git status - see what's changed
• git checkout branch_name - switch to a different branch
• git checkout -b new_branch - create a branch called new_branch and switch to it
• git add . - stage all recent changes
• git commit -m "my commit message" - create a commit with staged changes
• git push - send what's on my machine to GitHub
• git pull - get changes from GitHub to my machine

You DON'T need to: merge, revert, reset, resolving merge conflicts, pull requests

Cargo Commands (Lecture 5)

For the midterm, you should recognize and recall:

• cargo new project_name - create project
• cargo run - compile and run
• cargo run --release - compile and run with optimizations (slower to compile, faster to run)
• cargo build - just compile without running
• cargo check - just check for errors without compiling
• cargo test - run tests

You DON'T need to: Cargo.toml syntax, how Cargo.lock works, advanced cargo features

Quick Questions: Tools

Question 1

Which command shows your current location on your machine?

Question 2

What's the correct order for the basic Git workflow?

• A) add → commit → push
• B) commit → add → push
• C) push → add → commit
• D) add → push → commit

Question 3

Which cargo command compiles your code without running it?

Rust Core Concepts

Compilers vs Interpreters (Lecture 4)

Key Concepts

• Compiled languages (like Rust): Code is transformed into machine code before running
• Interpreted languages (like Python): Code is executed line-by-line at runtime
• The compiler checks your code for errors and translates it into machine code
• The machine code is directly executed by your computer - it isn't Rust anymore!
• A compiler error means your code failed to translate into machine code
• A runtime error means your machine code crashed while running

Rust prevents runtime errors by being strict at compile time!

Variables and Types (Lecture 7)

Key Concepts

• Defining variables: let x = 5;
• Mutability: Variables are immutable by default, use let mut to allow them to change
• Shadowing: let x = x + 1; creates a new x value without mut and lets you change types
• Basic types: i32, f64, bool, char, &str, String
• Rough variable sizes: Eg. i32 takes up 32-bits of space and its largest positive value is about half of u32's largest value
• Type annotations: Rust infers types (let x = 5) or you can specify them (let x: i32 = 5)
• Tuples: Creating (let x = (2,"hi")), accessing (let y = x.0 + 1), destructuring (let (a,b) = x)
• Constants: Eg. const MY_CONST: i32 = 5, always immutable, must have explicit types, written into machine code at compile-time

What's Not Important

• Calculating exact variable sizes and max values
• 2's complement notation for negative integers
• Complex string manipulation details

String vs &str - You're not responsible for it, but let's talk about it

Quick explanation

• String = a string = owned text data (like a text file you own)
• &str = a "string slice = borrowed text data (like looking at someone else's text)
• A string literal like "hello" is a &str (you don't own it, it's baked into your program)
• To convert from an &str to a String, use "hello".to_string() or String::from("hello")
• To convert from a String to an &str, use &my_string (to create a "reference")

Don't stress! You can do most things with either one, and I will not make you do anything crazy with these / penalize you for misusing these on the midterm.

Quick Questions: Rust basics

Question 4

What happens with this code?

#![allow(unused)]
fn main() {
let x = 5;
x = 10;
println!("{}", x);
}

• A) Prints 5
• B) Prints 10
• C) Compiler error
• D) Runtime error

Question 5

What's the type of x after this code?

#![allow(unused)]
fn main() {
let x = 5;
let x = x as f64;
let x = x > 3.0;
}

• A) i32
• B) f64
• C) bool
• D) Compiler error

Question 6

How do you access the second element of tuple t = (1, 2, 3)?

• A) t[1]
• B) t.1
• C) t.2
• D) t(2)

Functions (Lecture 8)

Key Concepts

• Function signature: fn name(param1: type1, param2: type2) -> return_type, returned value must match return_type
• Expressions and statements: Expressions reduce to values (no semicolon), statements take actions (end with semicolon)
• Returning with return or an expression: Ending a function with return x; and x are equivalent
• {} blocks are scopes and expressions: They reduce to the value of the last expression inside them
• Unit type: Functions without a return type return ()
• Best practices: Keep functions small and single-purpose, name them with verbs

What's Not Important

• Ownership/borrowing mechanics (we'll cover this after the midterm)
• Advanced function patterns

Quick Questions: Functions

Question 7

What is the value of mystery(x)?

#![allow(unused)]
fn main() {
fn mystery(x: i32) -> i32 {
    x + 5;
}
let x = 1;
mystery(x)
}

• A) 6
• B) i32
• C) ()
• D) Compiler error

Question 8

Which is a correct function signature for a function that takes two integers and returns their sum?

Question 9

Which version will compile

#![allow(unused)]
fn main() {
// Version A
fn func_a() {
    42
}

// Version B
fn func_b() {
    42;
}
}

• A) A
• B) B
• C) Both
• D) Neither

Question 10

What does this print?

#![allow(unused)]
fn main() {
let x = println!("hello");
println!("{:?}", x);
}

• A) hello /n hello
• B) hello /n ()
• C) hello
• D) ()
• E) Compiler error
• F) Runtime error

Loops and Arrays (Lecture 9)

Key Concepts

• Ranges: 1..5 vs 1..=5
• Arrays: Creating ([5,6] vs [5;6]), accessing (x[i]), 0-indexing
• If/else: how to write if / else blocks with correct syntax
• Loop types: for, while, loop - how and when to use each
• break and continue: For controlling loop flow
• Basic enumerating for (i, val) in x.iter().enumerate()

What's Not Important

• Compact notation (let x = if y ... or let y = loop {...)
• Enumerating over a string array with for (i, &item) in x.iter().enumerate()
• Labeled loops, breaking out of an outer loop

Quick Questions: Loops & Arrays

Question 11

What's the difference between 1..5 and 1..=5?

Question 12

What does this print?

#![allow(unused)]
fn main() {
for i in 0..3 {
    if i == 1 { continue; }
    println!("{}", i);
}
}

Question 13

How do you get both index and value when looping over an array?

Enums and Pattern Matching (Lecture 10)

Key Concepts

• Enum definition: Creating custom types with variants
• Data in variants: Enums can hold data
• match expressions: syntax by hand, needs to be exhaustive, how to use a catch-all (_)
• Option<T>: Has Some(value) and None
• Result<T, E>: HasOk(value) and Err(error)
• #[derive(Debug)]: For making enums printable
• #[derive(PartialEq)]: For allowing enums to be compared with == and !=
• Data extraction: Getting values out of enum variants with match, unwrap, or expect

What's Not Important

• if let notation
• writing complex matches (conditional statements, ranges, tuples) - you should understand them but don't have to write them

Quick Questions: Enums & Match

Question 14

What's wrong with this code?

#![allow(unused)]
fn main() {
enum Status {
    Loading,
    Complete,
    Error,
}

match Status::Loading {
    Status::Loading => println!("Loading..."),
    Status::Complete => println!("Done!"),
}
}

Question 15

If a function's return type is Option<i32> what values can it return (can be more than one)?

• A) Some(i32)
• B) Ok
• C) Ok(i32)
• D) None
• E) Err

Question 16

What can go in the ???? to get the value out of Some(42)?

#![allow(unused)]
fn main() {
let x = Some(42);
match x {
    Some(????) => println!("Got: {}", ????),
    None => println!("Nothing"),
}
}

• A) _ and _
• B) 42 and 42
• C) x and x
• D) y and y

Question 17

What does #[derive(Debug)] do?

Error Handling (Lecture 11)

Key Concepts

• panic! vs Result: Panic when unrecoverable, Result when recoverable
• Result<T, E> for errors: Ok(value) for success, Err(error) for failure
• Error propagation: Passing errors up with match or ?
• unwrap() and expect(): Quick ways to extract values (but they can panic!)
• The ? operator: Shortcut for "if error, return it; if ok, give me the value" - only works on shared E

Quick Questions: Error Handling

Question 18

When should you use panic! vs Result<T, E>?

Question 19

Why won't this code compile?

#![allow(unused)]
fn main() {
fn parse_number(s: &str) -> Result<i32, String> {
    let num = s.parse::<i32>()?;  // parse() returns Result<i32, ParseIntError>
    Ok(num * 2)
}
}

• A) The ? operator can't be used in let statements
• B) You can't multiply by 2 inside Ok()
• C) The error types don't match: ParseIntError vs String
• D) Ok doesn't match the Result type

Question 20

When might you extract a value with .unwrap()?

• A) When you're pretty sure the value will be Ok/Some not Err/None
• B) When you want the code to crash if the value is Err or None
• C) When you want the value if Ok/Some but want to ignore it if Err/None
• D) When you want a more concise version of a match statement

Question 21

What does this return when called with divide(10, 2)?

#![allow(unused)]
fn main() {
fn divide(a: i32, b: i32) -> Result<i32, String> {
    if b == 0 {
        Err("Can't divide by zero".to_string())
    } else {
        Ok(a / b)
    }
}
}

Putting It All Together

What You've Accomplished

In just a few weeks, you've learned:

• Professional development tools (shell, git, github, cargo)
• The foundations of a systems programming language
• Sophisticated pattern matching and error handling techniques

That's genuinely impressive!

And if it doesn't feel fluent yet, give it some time. It's like you memorized your first 500 words in a new spoken language but haven't had much practice actually speaking it yet. It feels awkward, and that's normal.

Midterm Strategy

• Focus on concepts: Understand the "why" behind the syntax and it will be easier to remember
• Practice with your hands: Literally and figuratively - practice solving problems, and practice on paper
• Take big problems step-by-step: Understand each line of code before reading the next. And make a plan before you start to hand-code

Questions and Discussion

What topics would you like to clarify before Wednesday's practice session?

Activity Time - Design your own midterm

No promises, but I do mean it.

You'll find an activity released to you on gradescope to do solo or in groups.

I want you all to spend some time thinking about problems/questions that you could imagine being on our first midterm. If I like your questions, I might include them (or some variation) on the exam!

This also helps me understand what you're finding easy/difficult and where we should focus on Wednesday. It can help you identify areas you might want to brush up on as well.

Aim to come up with 2-3 questions per category (or more!). I'm defining these as:

• EASY You know the answer now and expect most students in the class will get it right
• MEDIUM You feel iffy now but bet you will be able to answer it after studying, and it would feel fair to be on exam
• HARD It would be stressful to turn the page to this question, but you bet you could work your way to partial credit

Requirements for each question:

For each question you create, please include:

1. The question itself
2. The answer/solution (if you can solve it)
3. Why you categorized it as Easy/Medium/Hard

Content Areas to Consider:

Make sure your questions collectively cover the major topics we've studied so far:

• Tools: git, shell, cargo
• Rust: Variables, types, functions, loops, enums & match, error handling

Some formats of problems to consider:

• Definitions
• Multiple choice
• Does this compile / what does it return
• Find and fix the bug
• Fill-in-the-blank in code
• Longer hand-coding problems
• Short answer on concepts (describe how x works...)

Lecture 13 - Midterm Practice Problems

Today's Goals

• Work through realistic practice problems similar to the midterm
• Practice applying multiple concepts together
• Walk through solutions step-by-step

Today's Format:

• Work individually first, then discuss with neighbors
• I'll walk through solutions after you've tried each section
• Ask questions anytime - if you're confused, others probably are too!

Exam tips

Exam format

• Short answer, fill-in, find bugs ~ 60% of the exam
• One hand-coding problem ~ 40% of the exam

Short answer tips

• I was serious about Anki / flashcards - they help!
• When approaching a block of code (to debug, find what it returns, fill in blanks):
  • Skim it quickly once to get the gist
  • Then read it slowly making sure you understand each part completely
• Write what you know - if you don't know the answer, what DO you know?

Hand-coding tips

• Read the whole problem first and make a plan
• Test your logic by imagining runs with example data
• Show your process (you can write comments by hand too!) - if I can see what you were trying to do I can give you more credit
• Check your function signature - parameter and return types should match!
• Check your syntax! - semicolons, = vs ==, .. vs ..=, ... did I mention semicolons?

See Activity 13

for the material for the rest of the lecture

First-half Discussion

Let's go through the solutions for Practice Set A together before moving to the longer problem.

Second-half Discussion

If you're finished and want to try out your solution, type it up and email it to laurenbw@bu.edu

I'll put it on the screen (anonymously) and we'll discuss it / debug it together

Questions?

What would help clarify anything before the midterm?

Lecture 14 - Stack / Heap

Logistics - Exam

• You survived the exam!
• I will have grades to you by Friday, probably sooner
• You'll have 1 week to do corrections and/or ask for an oral redo of a topic
• I dropped the hand-coding weight from ~40% to ~20% (it won't hurt you)

Logistics - Exam

Corrections requirements

• Like HW1 corrections
• An explanation of what you misunderstood and what you learned since
• A completely correct answer
• No partial credit

Oral exam option - tweaked since the syllabus

• In addition to corrections for ONE of part of the exam, you can meet with me for a short in-person conversation where we discuss your insight, you answer some related questions, and have the opportunity to recover more points (up to a cap of 90% for the section).
• Some examples:
  • You received 7/21 points (33%) for hand-coding. With corrections you can reach 66%. If you come in for an oral exam you may receive additional credit, for a final section score between 66% and 90%.
  • You received 15/18 ponts on Part 1 (83%). With corrections you can reach 92%. You can't improve your score on this section with an oral exam.
• With the corrections assignment I'll ask you to elect which section, if any, you'd like to go over together and I'll coordinate scheduling.

Logistics - other stuff

• HW3 is due tonight at midnight - Zach (from A1) has office hours 1:30-3:30 for last-minute questions
• HW2 corrections are due Thursday night
• HW4 will be posted Friday, due two weeks later

Learning Objectives

• Today: We're going to peek under the hood of how computers actually store and manage data

By the end of today, you should be able to:

• Explain what computer memory (RAM) is and how it works
• Understand what memory addresses are and why they matter
• Distinguish between stack and heap memory allocation
• Connect these concepts to Rust code you've already written
• Understand why Rust's approach to memory management is different (and better!)

What is computer memory?

Where are x, name, and scores actually stored when your program runs?

#![allow(unused)]
fn main() {
let x = 42;
let name = "Alice".to_string();
let scores = [85, 92, 78];
}

What's the difference between RAM and storage (hard drive)?

Physical difference: RAM uses electronic circuits (transistors/capacitors) that can switch instantly, while storage uses mechanical parts (spinning disks) or slower flash memory cells.

CPU + RAM relationship: The CPU (processor) is like the "brain" that does all the actual work - it reads instructions and data from RAM, processes them, and writes results back to RAM. You can think of of RAM as the CPU's "desk" where it keeps everything it's currently working on.

Key idea: Your program runs entirely in RAM! - Storage is only used to load your program into RAM initially.

A helpful metaphor for RAM

Your RAM is like an organized city made up of buildings and units

• Each unit has a unique address (like "Building A, Floor 5, Apt 12")
• Each unit can hold one piece of data (like one number, one character)
• The computer can look up any unit instantly if it knows the address
• Everyone is renting - limited space / data is lost with power off
• You get there on a bus!

When your program runs, ALL your data has to live somewhere in this city

Memory Addresses - Like Street Addresses

Every location in memory has a unique address -

Memory Address    |  Data Stored There
------------------|------------------
0x7fff5fbff6bc    |  42
0x7fff5fbff6c0    |  'H'
0x7fff5fbff6c4    |  'e'
0x7fff5fbff6c8    |  'l'
0x7fff5fbff6cc    |  'l'
0x7fff5fbff6d0    |  'o'

• Addresses are written in hexadecimal (base 16) - that's why they go up to "f"
• The computer uses these addresses to find your data super quickly
• Pointers are just variables that store memory addresses instead of values

How Memory is Organized - The Big Picture

When your program runs, memory is organized into different "neighborhoods" for different purposes:

It's as if the city has different districts (from low addresses to high addresses):

1. Text/Code - Where your compiled Rust functions live ("business district"?)
2. Static Data - Where global constants live ("city hall"?)
3. Heap - Where dynamic data lives (like "storage units" - rent them when you need them)
4. Stack - Where local variables live temporarily (most like dorms - people move in and out)

We'll mostly care about Stack vs. Heap

Why Should You Care?

Programs need to:

1. Get memory when they need to store data ("move in")
2. Give it back when they're done with it ("move out")

If programs don't give memory back your computer/program slows down and eventually crashes!

(In the housing analogy, there's a housing shortage, homelessness, and eventually a proletariat uprising?)

Three Approaches to Memory Management

Different programming languages handle this differently:

1. Manual (C/C++): "You figure it out!"

   • Programmer manually asks for memory and gives it back (C: malloc / free)
   • Super fast, but easy to make dangerous mistakes

2. Garbage Collection (Python/Java): "I'll handle it automatically!"

   • Language automatically cleans up unused memory
   • Safe but can cause random slowdowns

3. Ownership (Rust): "I'll help you get it right!"

   • Compiler enforces rules to prevent mistakes
   • Fast AND safe - best of both worlds!

This is why Rust can seem picky sometimes - it's preventing memory bugs!

Stack vs. Heap: The Two Main Memory Types

The Stack: Like a dorm, but also... like a literal stack of plates

Key idea: Last thing you put on, first thing you take off

fn main() {                    // Stack: [        ]
    let x = 42;               // Stack: [x=42     ]
    let y = true;             // Stack: [x=42, y=true]
    println!("{}", x);
}                             // Stack: [        ] ← Everything cleaned up automatically!

Stack characteristics:

• Super fast - just "put on top" or "take off top"
• Limited size - like a small tower of plates
• Automatic cleanup - when a function ends, its "plates" are removed
• Size must be known - each "plate" is a fixed size

Most Rust data you've seen lives on the stack: i32, bool, char, arrays, tuples

Stack Frames: Organized Sections

Each function call gets its own organized section called a stack frame

Stack frame holds all the data for one function call:

• Function parameters
• Local variables
• Return address (where to go back when function ends)
• Other bookkeeping info

Stack Memory:
┌─────────────────┐ ← Top of stack
│   Function C    │ ← Stack frame for Function C
│   parameters    │
│   local vars    │
│   return info   │
├─────────────────┤
│   Function B    │ ← Stack frame for Function B
│   parameters    │
│   local vars    │
│   return info   │
├─────────────────┤
│   Function A    │ ← Stack frame for Function A (main)
│   parameters    │
│   local vars    │
│   return info   │
└─────────────────┘ ← Bottom of stack

When a function ends, its entire stack frame gets removed instantly!

A short example of stack frames

When you call a function, it gets its own stack frame:

fn main() {                    // Stack: [main's stack frame]
    let x = 5;
    let result = double(x);    // Stack: [main's frame][double's frame]
    println!("{}", result);
}                              // Stack: [main's frame] ← double's frame is gone!

fn double(n: i32) -> i32 {
    let doubled = n * 2;       // This lives in double's stack frame
    doubled
}

Stack Overflow - A Real Problem!

What happens if you make too many function calls?

#![allow(unused)]
fn main() {
fn recursive_function(n: u32) -> u32 {
    if n == 0 {
        0
    } else {
        recursive_function(n - 1)  // Each call adds a new "plate" to the stack!
    }
}

// This will crash your program:
recursive_function(1_000_000);  // Too many "plates"! 
}

This is where the name "Stack Overflow" (the website) comes from!

The Heap: Like a Storage Unit Facility

Key idea: Rent storage space when you need it, different sizes allowed

fn main() {
    let name = "Alice".to_string();          // The actual "Alice" lives on the heap!
    let scores = vec![85, 92, 78, 96, 88];   // These numbers live on the heap!

    // name and scores themselves are on the stack,
    // but they contain "addresses" pointing to heap data
}

Heap characteristics:

• Flexible size - can grow and shrink as needed
• Slower access - have to "drive to the storage unit"
• Manual management needed - someone has to "return the keys"
• Much larger - way more space available than stack

Rust data that lives on the heap: String, Vec, HashMap, Box

Stack vs. Heap

String vs &str - Finally Explained!

We can explain this a bit more now with stack/heap:

String: Owned Text on the Heap

#![allow(unused)]
fn main() {
let name = "Alice".to_string();  // or String::from("Alice")
}

What happens in memory:

Stack:                    Heap:
┌─────────────┐          ┌─────┬─────┬─────┬─────┬─────┐
│ name        │          │ 'A' │ 'l' │ 'i' │ 'c' │ 'e' │
│ ├ ptr ──────┼─────────▶│     │     │     │     │     │
│ ├ len: 5    │          └─────┴─────┴─────┴─────┴─────┘
│ └ cap: 5    │
└─────────────┘

• String = the metadata on the stack (pointer, length, capacity)
• Actual text = lives on the heap
• You own it = you can modify it, and Rust will clean it up for you

&str: Borrowed Text (Points to Existing Data)

#![allow(unused)]
fn main() {
let greeting = "Hello";  // This is &str
}

What happens in memory:

Stack:                    Program Binary (Text Section):
┌─────────────┐          ┌─────┬─────┬─────┬─────┬─────┐
│ greeting    │          │ 'H' │ 'e' │ 'l' │ 'l' │ 'o' │
│ ├ ptr ──────┼─────────▶│     │     │     │     │     │
│ └ len: 5    │          └─────┴─────┴─────┴─────┴─────┘
└─────────────┘

• &str = just a pointer and length on the stack
• Actual text = lives in your compiled program (or points to someone else's String)
• You're borrowing it = you can read it, but you don't own it

Let's Watch the Stack in Action!

Here's an example showing how the stack builds up and comes down as functions are called.

The diagrams will be online after class but there's space on your paper to draw them yourselves as we go.

fn main() {
    let x = 42;                           // Stack variable
    let name = "Alice".to_string();       // Stack + Heap
    let result = process_data(x, &name);
    println!("{}", result);
}

fn process_data(num: i32, text: &str) -> String {
    let mut doubled = num * 2;            // Stack variable

    // A bracketed scope creates its own mini-stack frame!
    {
        let temp_multiplier = 10;         // New scope variable
        let temp_result = doubled * temp_multiplier;  // Another scope variable
        println!("Temp calculation: {}", temp_result);
        doubled = doubled + 1;            // Modify outer variable
    }  // temp_multiplier and temp_result are destroyed here!

    let greeting = format!("Hello {}, your number is {}", text, doubled);
    greeting                              // Return String (heap data)
}

Step 1: main() starts

Stack:                          Heap:
┌─────────────────┐            ┌─────┬─────┬─────┬─────┬─────┐
│ main():         │            │ 'A' │ 'l' │ 'i' │ 'c' │ 'e' │
│ ├ result: ???   │            └─────┴─────┴─────┴─────┴─────┘
│ ├ name: String  │                   ▲
│ │   ptr ────────┼───────────────────┘
│ │   len: 5      │
│ │   cap: 5      │
│ └ x: 42         │
└─────────────────┘

Step 2: Call process_data(x, &name)

Stack:                          Heap:
┌─────────────────┐            ┌─────┬─────┬─────┬─────┬─────┐
│ process_data(): │            │ 'A' │ 'l' │ 'i' │ 'c' │ 'e' │
│ ├ doubled: 84   │            └─────┴─────┴─────┴─────┴─────┘
│ ├ text: &str    │                   ▲   ▲
│ │   ptr ────────┼───────────────────┘   |
│ │   len: 5      │                       |
│ └ num: 42       │                       |
├─────────────────┤                       |
│ main():         │                       |
│ ├ result: ???   │                       |
│ ├ name: String ─┼───────────────────────┘ 
│ └ x: 42         │
└─────────────────┘

Step 3: Enter the bracketed scope {}

Stack:                          Heap:
┌─────────────────┐            
│ { scope }:      │           
│ ├temp_result: 840          
│ └temp_multiplier:10                   
├─────────────────┤            ┌─────┬─────┬─────┬─────┬─────┐
│ process_data(): │            │ 'A' │ 'l' │ 'i' │ 'c' │ 'e' │
│ ├ doubled: 85   │ <-modified └─────┴─────┴─────┴─────┴─────┘
│ ├ text: &str    │                   ▲   ▲
│ │   ptr ────────┼───────────────────┘   |
│ │   len: 5      │                       |
│ └ num: 42       │                       |
├─────────────────┤                       |
│ main():         │                       |
│ ├ result: ???   │                       |
│ ├ name: String ─┼───────────────────────┘ 
│ └ x: 42         │
└─────────────────┘

Step 4: Exit the bracketed scope

Stack:                          Heap:
┌─────────────────┐          ┌─────┬─────┬─────┬─────┬─────┬──────┬──────┐         
│ process_data(): │          │ 'H' │ 'e' │ 'l' │ 'l' │ 'o' │ ' '  │ 'A'  │ ...
│  └ greeting:    │          └─────┴─────┴─────┴─────┴─────┴──────┴──────┘  
│     String      │                                  ▲
│     ptr ────────┼──────────────────────────────────┘
│     len: 28     │            ┌─────┬─────┬─────┬─────┬─────┐
│     cap: 28     │            │ 'A' │ 'l' │ 'i' │ 'c' │ 'e' │
│ ├ doubled: 85   │← Still 85! └─────┴─────┴─────┴─────┴─────┘
│ ├ text: &str    │                   ▲   ▲
│ │   ptr ────────┼───────────────────┘   |
│ │   len: 5      │                       |
│ └ num: 42       │                       |
├─────────────────┤                       |
│ main():         │                       |
│ ├ result: ???   │                       |
│ ├ name: String ─┼───────────────────────┘ 
│ └ x: 42         │
└─────────────────┘

Step 5: process_data() returns

Stack:                          Heap:
┌─────────────────┐     
│ main():         │         ┌─────┬─────┬─────┬─────┬─────┬──────┬──────┐    
│ │   len: 5      │         │ 'H' │ 'e' │ 'l' │ 'l' │ 'o' │ ' '  │ 'A'  │ ...
│ │   cap: 5      │         └─────┴─────┴─────┴─────┴─────┴──────┴──────┘
│ └ result:       │          ▲
│     String      │          │
│     ptr ────────┼──────────┘  ┌─────┬─────┬─────┬─────┬─────┐
│     len: 28     │             │ 'A' │ 'l' │ 'i' │ 'c' │ 'e' │
│     cap: 28     │             └─────┴─────┴─────┴─────┴─────┘
│ ├ name: String ─┼───────────────────────┘ 
│ ├ x: 42         │ 
└─────────────────┘

Step 6: main() ends

Stack:              Heap:
┌─────────┐        ┌─────────────┐
│ (empty) │        │ (cleaned up │
└─────────┘        │  by Rust!)  │
                   └─────────────┘

Take-aways from this example

• Stack builds up as functions are called, shrinks as they return
• Bracketed scopes {} create mini-stack frames within functions
• Variables in scopes are destroyed when the scope ends, but changes to outer variables persist (you can think about what that means for shadowing...)
• Heap data can outlive the function that created it (when moved/returned)
• Rust automatically cleans up heap data when no one owns it anymore

Lecture 15 - Ownership and Vec

Logistics

• Midterm grades and corrections assignment posted
• HW3 late deadline tonight

We are here

• Last time: Stack and heap
• Today: Rust's ownership system + Vec+Box for heap data
• Next time: Borrowing and references (&, *)

Learning Objectives

By the end of today, you should be able to:

• Explain Rust's three ownership rules
• Understand when data gets moved vs copied
• Draw stack/heap diagrams showing ownership
• Use Vec<T> and Box<T> on the heap
• Debug common ownership compiler errors

Recall: stack vs heap

Stack: Fast, fixed-size, automatic cleanup

• Like a stack of plates - last in, first out
• Each function call gets its own "stack frame"
• All the simple types you've used: i32, bool, char, arrays, tuples

Heap: Flexible size, manual management (but Rust helps!)

• Like a warehouse - rent space when you need it
• For data that can grow/shrink or is really big
• String and Vec<T> store their actual data here

Key idea: Stack variables can hold pointers (addresses) to heap data

Part 1 - Ownership in Rust

Ownership tracks what variable is responsible for data that is on the heap.

Why ownership:

• It helps efficiently free up memory when it is no longer needed
• It helps prevent "undefined behavior" that arises from less-strict approaches

Rust's Three Ownership Rules

These are the fundamental rules that make Rust memory-safe:

1. Each value in Rust has an owner
2. There can only be one owner at a time
3. When the owner goes out of scope, the value will be dropped

Rule 1: Each value in Rust has an owner

#![allow(unused)]
fn main() {
let s1 = String::from("hello");  // s1 owns the string
// There is exactly ONE owner of the "hello" data on the heap
}

Stack/Heap diagram:

Stack:           Heap:
┌─────────────┐  ┌─────┬─────┬─────┬─────┬─────┐
│ s1: String  │  │ 'h' │ 'e' │ 'l' │ 'l' │ 'o' │
│ ├ ptr ──────┼─▶│     │     │     │     │     │
│ ├ len: 5    │  └─────┴─────┴─────┴─────┴─────┘
│ └ cap: 5    │  ↑
└─────────────┘  Owner: s1

Rule 2: There can only be one owner at a time

fn main(){
let s1 = String::from("hello");
let s2 = s1;  // Ownership MOVES from s1 to s2
// println!("{}", s1);  // ERROR! s1 no longer owns the data
println!("{}", s2);     // OK! s2 now owns it
}

What happens in memory:

Before move:         After move:
Stack:               Stack:
┌─────────────┐     ┌─────────────┐
│ s1: String  │     │ s2: String  │
│ ├ ptr ──────┼──┐  │ ├ ptr ──────┼─┐         
│ ├ len: 5    │  │  │ ├ len: 5    │ │ 
│ └ cap: 5    │  │  │ └ cap: 5    │ │
└─────────────┘  │  ├─────────────┘ │
                 │  │  s1: ???    │ │
                 │  └─────────────┘ │
                 │                  │
                 │  Heap:           │
                 │  ┌─────┬─────┬─────┬─────┬─────┐
                 └─▶│ 'h' │ 'e' │ 'l' │ 'l' │ 'o' │
                    └─────┴─────┴─────┴─────┴─────┘

Rule 3: When the owner goes out of scope, the value is dropped

fn main(){
{
    let s = String::from("hello");  // s owns the string
}  // s goes out of scope, heap memory is freed automatically!
println!("{}", s); 
}

Move vs Copy: The Key Distinction

Stack data gets copied

#![allow(unused)]
fn main() {
let x = 5;
let y = x;  // x is copied to y
println!("{} {}", x, y);  // Both work! 
}

Heap data gets moved

#![allow(unused)]
fn main() {
let s1 = String::from("hello");
let s2 = s1;  // s1 is moved to s2
// println!("{}", s1);  // s1 is no longer valid
println!("{}", s2);     // Only s2 works now
}

Why would an int get copied but a string get moved by default?

Think-pair-share

Passing data to functions follows the same rules

fn takes_ownership(some_string: String) {
    println!("in fn: {}", some_string);
}  // some_string goes out of scope and heap memory is freed

fn makes_copy(some_integer: i32) {
    println!("in fn: {}", some_integer);
}  // some_integer goes out of scope, but it's just a copy

fn main() {
    let s = String::from("hello");
    takes_ownership(s);         // s is moved into the function
    // println!("in main: {}", s);       // ERROR! s is no longer valid

    let x = 5;
    makes_copy(x);              // x is copied into the function
    println!("in main: {}", x);          // OK! x is still valid
}

Function return values also transfer ownership

fn gives_ownership() -> String {
    let some_string = String::from("yours");
    some_string  // Ownership moves to caller
}

fn takes_and_gives_back(a_string: String) -> String {
    a_string  // Ownership moves back to caller
}

fn main() {
    let s1 = gives_ownership();         // Ownership moves from function to s1
    let s2 = String::from("hello");     // s2 comes into scope
    let s3 = takes_and_gives_back(s2);  // s2 moves in, s3 gets it back
    // s2 is no longer valid, but s1 and s3 are
    println!("s1: {}", s1);    
    // println!("s2: {}", s2);    
    println!("s3: {}", s3);    
}

Let's draw these moves on the board.

Try to predict what happens before running:

Think-pair-share

fn main() {
    let s1 = String::from("world");
    let s2 = process_string(s1);

    println!("{}", s2);  // Will this work?
    println!("{}", s1);  // Will this work?
}

fn process_string(input: String) -> String {
    format!("Hello, {}!", input)
}

Part 2 - Vec and Box on the heap

Finally! I know some of you have been using Vec anyway because Rust's arrays are so limiting...

Now we'll get to start using Vec for real.

Why arrays were such a pain

• They live on the stack, so... they're fixed size and size must be known at compile time

What is a Vec

• Contains a single type, like an array
• Can change sizes!
• Lives on the heap

Creating Vec

#![allow(unused)]
fn main() {
// Three ways to create a Vec:
let mut numbers = Vec::new();           // Empty vector
let mut scores = vec![85, 92, 78];      // With initial data
let mut names: Vec<String> = Vec::new(); // Empty with type annotation
}

Vec in memory (let's trace vec![85, 92, 78]):

Stack:                    Heap:
┌─────────────────┐      ┌────┬────┬────┬────┐
│ scores: Vec<i32>│      │ 85 │ 92 │ 78 │ ?? │
│ ├ ptr ──────────┼─────▶│    │    │    │    │
│ ├ len: 3        │      └────┴────┴────┴────┘
│ └ cap: 4        │      capacity = 4, length = 3
└─────────────────┘

Basic Vec Operations

fn main() {
    let mut numbers = vec![1, 2, 3];

    // Add elements (might reallocate!)
    numbers.push(4);
    numbers.push(5);

    // Other basic operations
    numbers.pop();
    let num_len = numbers.len();

    // Access elements (copies the value!)
    let first = numbers[0];  
    let third = numbers[2];  

    println!("First: {}, Third: {}", first, third);
    println!("Vec: {:?}", numbers);
}

Let's draw it on the board!

Key insight: numbers[0] copies the value from heap to stack because i32 is a "copy type".

Capacity vs Length

#![allow(unused)]
fn main() {
let mut vec = Vec::with_capacity(4);  // Reserve space for 4 elements
println!("Length: {}, Capacity: {}", vec.len(), vec.capacity()); 

vec.push(1);
vec.push(2);
println!("Length: {}, Capacity: {}", vec.len(), vec.capacity()); 

vec.push(3);
vec.push(4);
vec.push(5);  // This might cause reallocation!
println!("Length: {}, Capacity: {}", vec.len(), vec.capacity()); 
}

When Vec grows beyond capacity: Rust allocates a bigger chunk of heap memory, copies all data over, and frees the old chunk. You don't have to worry about this!

Vec Ownership in Action

Moving Vec to functions:

fn main() {
    let my_vec = vec![1, 2, 3];
    let result = process_numbers(my_vec);  // my_vec moves into function

    // println!("{:?}", my_vec);  // ERROR! my_vec no longer valid
    println!("{:?}", result);     // OK! result owns the data now
}

fn process_numbers(mut numbers: Vec<i32>) -> Vec<i32> {
    numbers.push(99);
    numbers
}

Copying values FROM Vec:

fn main() {
    let numbers = vec![10, 20, 30, 40];

    // These copy values from heap to stack:
    let first = numbers[0];   // first = 10 (copied)
    let second = numbers[1];  // second = 20 (copied)

    // Original Vec still owns the heap data:
    println!("Vec still works: {:?}", numbers);
    println!("Copied values: {}, {}", first, second);
}

Stack/heap after copying:

Stack:                    Heap:
┌─────────────────┐      
│ second: 20      │ 
├─────────────────┤
│ first: 10       │   
├─────────────────┤      ┌────┬────┬────┬────┐
│ numbers: Vec    │      │ 10 │ 20 │ 30 │ 40 │
│ ├ ptr ──────────┼─────▶│    │    │    │    │
│ ├ len: 4        │      └────┴────┴────┴────┘
│ └ cap: 4        │
└─────────────────┘

What About Vec<String>?

Important difference: Vec<String> contains heap data inside heap data!

fn main(){
let mut names = vec![
    String::from("Alice"),
    String::from("Bob")
];

// This WON'T work the same way:
// let first_name = names[0];  // Can't copy String!
}

Stack/heap with Vec (heap data pointing to more heap data!):

Stack:                     Heap (Vec data):           Heap (String data):
┌────────────────┐     ┌─────────────────┐        ┌─────┬─────┬─────┬─────┬─────┐
│ names: Vec     │     │ String("Alice") │───────▶│ 'A' │ 'l' │ 'i' │ 'c' │ 'e' │
│ ├ ptr ─────────┼────▶│ ├ ptr ──────────┼────────┤     │     │     │     │     │
│ ├ len: 2       │     │ ├ len: 5        │        └─────┴─────┴─────┴─────┴─────┘
│ └ cap: 2       │     │ └ cap: 5        │
└────────────────┘     ├─────────────────┤        ┌─────┬─────┬─────┐
                       │ String("Bob")   │───────▶│ 'B' │ 'o' │ 'b' │
                       │ ├ ptr ──────────┼────────┤     │     │     │
                       │ ├ len: 3        │        └─────┴─────┴─────┘
                       │ └ cap: 3        │
                       └─────────────────┘

Why? String doesn't implement Copy - we'd be copying heap pointers, which violates ownership rules.

We'll learn how to handle this next lecture with borrowing!

Box - for when your stack data is REALLY BIG

Sometimes data that would usually go on the stack is just too big:

#![allow(unused)]
fn main() {
// This is fine - small array
let small_data = [0; 1000];

// This might crash your program - too big for the stack!
// let huge_data = [0; 10_000_000];
}

So we create a Box to force it onto the heap:

Box: Moving big data to the warehouse

#![allow(unused)]
fn main() {
let huge_data = Box::new([0; 10_000_000]);

println!("Successfully created {} numbers", huge_data.len());
}

You can actually put practically anything in a box! We'll discuss them more later, but for now, they're just another tool for us to think about stack/heap and ownership.

When do you need a box?

• Large datasets: Millions of records
• Big matrices: Large 2D arrays for data analysis
• Deep structures: Complex nested data

Just for fun - nesting things in boxes (Yes, even boxes in boxes!)

You can put complex heap-allocated types inside a Box:

// Box containing a Vec of Strings (heap in heap in heap!)
let boxed_names = Box::new(vec![
    String::from("Alice"),
    String::from("Bob"),
    String::from("Charlie")
]);

println!("Names in box: {:?}", boxed_names);

// Box in a Box (why not?)
let box_in_box = Box::new(Box::new(42));
println!("Deeply boxed value: {}", box_in_box);

// Box containing a Vec of Boxes (getting silly now!)
let boxes_in_vec_in_box = Box::new(vec![
    Box::new(1),
    Box::new(2),
    Box::new(3)
]);
println!("Box containing Vec of Boxes: {:?}", boxes_in_vec_in_box);

What's happening here?

• boxed_names: Stack has a Box pointer -> Heap has Vec metadata -> Heap has String pointers -> Heap has actual string data
• box_in_box: Stack has a Box pointer -> Heap has another Box pointer -> Heap has the number 42
• boxes_in_vec_in_box: Stack has a Box pointer -> Heap has Vec metadata -> Heap has Box pointers -> Heap has the actual numbers

Activity time before Part 3!

Random student generator

Act 1: Copy vs Move (6 students)

  fn main() {
      let x = 5;
      let y = x;
      let s1 = String::from("hello");
      let s2 = s1;
      println!("{} {}", x, y);
      // println!("{} {}", s1, s2);
  }

Act 2: Function calls and returning ownership (4 students)

  fn main() {
      let data = vec![1, 2, 3];
      let data = process(data);
      println!("{:?}", data); // Works!
  }

  fn process(mut numbers: Vec<i32>) -> Vec<i32> {
      numbers.push(4);
      numbers
  }

Act 3: Attack of the Clones (8 students)

  fn main() {
      let s1 = String::from("hello");
      let s2 = s1.clone();
      println!("{} {}", s1, s2); 
      let s3 = s1;
      let s4 = s2;
      println!("{} {}", s3, s4); 
      let names = vec![s3, s4];
  }

Finale: The Box Office (14 students!!)

fn main() {
    let ticket_number = 42;
    let venue = String::from("Stage");

    let guest_list = vec![
        String::from("Alice"),
        String::from("Bob")
    ];

    // Box in a Box!
    let vip_box = Box::new(Box::new(String::from("VIP")));

    let show = prepare_show(guest_list, vip_box);

    println!("Show at {} with ticket {}", venue, ticket_number);
    println!("Final show: {:?}", show);
}

fn prepare_show(mut guests: Vec<String>, special: Box<Box<String>>) -> Box<Vec<String>> {
    guests.push(String::from("Charlie"));
    guests.push(*special); // Unbox twice!
    Box::new(guests)
}

If you weren't selected, please leave a note on stage or email me after class so I can track you were here!

Part 3: Debugging Ownership Errors

Let's practice fixing common ownership errors you'll encounter:

Error 1: Use After Move

This code won't compile:

fn main() {
    let data = vec![1, 2, 3];
    process_data(data);
    println!("{:?}", data);  // ERROR!
}

fn process_data(vec: Vec<i32>) {
    println!("Processing: {:?}", vec);
}

Compiler error: "borrow of moved value: data"

Fix option 1: Return the data from the function

fn main() {
    let data = vec![1, 2, 3];
    let data = process_data(data);  // Get it back!
    println!("{:?}", data);  // OK!
}

fn process_data(vec: Vec<i32>) -> Vec<i32> {
    println!("Processing: {:?}", vec);
    vec  // Return ownership
}

Fix option 2: Clone the data (makes a copy)

fn main() {
    let data = vec![1, 2, 3];
    process_data(data.clone());  // Send a copy
    println!("{:?}", data);  // OK!
}

fn process_data(vec: Vec<i32>) {
    println!("Processing: {:?}", vec);
}

Error 2: Multiple Moves

This code won't compile:

fn main() {
    let message = String::from("Hello");
    let a = message;
    let b = message;  // ERROR! Can't move twice
    println!("{} {}", a, b);
}

Compiler error: "use of moved value: message"

Fix: Clone for multiple copies

fn main() {
    let message = String::from("Hello");
    let a = message.clone();  // Make a copy
    let b = message;          // Move original
    println!("{} {}", a, b);  // Both work!
}

Error 3: Trying to Copy Non-Copy Types

This code won't compile:

fn main() {
    let names = vec![String::from("Alice"), String::from("Bob")];
    let first = names[0];  // ERROR! Can't copy String
    println!("{}", first);
}

Compiler error: "cannot move out of index of Vec<String>"

Fix: Clone the specific element

fn main() {
    let names = vec![String::from("Alice"), String::from("Bob")];
    let first = names[0].clone();  // Clone just this element
    println!("{}", first);  // Works!
    println!("{:?}", names);  // Original Vec still works!
}

Lecture 16 - Borrowing and References

Logistics

• Last time: Ownership system and Vec for heap data
• Today: Borrowing and references (&, *)
• HW4 will be released today
• There's pre-work for Tuesday but not Wednesday
• No sign-ups yet for coffee today (there really is coffee)

Learning Objectives

By the end of today, you should be able to:

• Use the & operator to create references (borrowing)
• Use the * operator to dereference and access borrowed data
• Apply borrowing rules to avoid "ownership too strict" problems
• Debug common ownership and borrowing compiler errors

Part 1 - Wrapping up Ownership

Let's practice fixing common ownership errors you'll encounter:

Error 1: Use After Move

This code won't compile:

fn main() {
    let data = vec![1, 2, 3];
    process_data(data);
    println!("{:?}", data);  // ERROR!
}

fn process_data(vec: Vec<i32>) {
    println!("Processing: {:?}", vec);
}

Compiler error: "borrow of moved value: data"

Error 1: Use After Move

Compiler error: "borrow of moved value: data"

Fix option 1: Return the data from the function

fn main() {
    let data = vec![1, 2, 3];
    let data = process_data(data);  // Get it back!
    println!("{:?}", data);  // OK!
}

fn process_data(vec: Vec<i32>) -> Vec<i32> {
    println!("Processing: {:?}", vec);
    vec  // Return ownership
}

Error 1: Use After Move

Compiler error: "borrow of moved value: data"

Fix option 2: Clone the data (makes a copy)

fn main() {
    let data = vec![1, 2, 3];
    process_data(data.clone());  // Send a copy
    println!("{:?}", data);  // OK!
}

fn process_data(vec: Vec<i32>) {
    println!("Processing: {:?}", vec);
}

Error 2: Multiple Moves

This code won't compile:

fn main() {
    let message = String::from("Hello");
    let a = message;
    let b = message;  // ERROR! Can't move twice
    println!("{} {}", a, b);
}

Compiler error: "use of moved value: message"

Error 2: Multiple Moves

Compiler error: "use of moved value: message"

Fix: Clone for multiple copies

fn main() {
    let message = String::from("Hello");
    let a = message.clone();  // Make a copy
    let b = message;          // Move original
    println!("{} {}", a, b);  // Both work!
}

Error 3: Trying to Copy Non-Copy Types

This code won't compile:

fn main() {
    let names = vec![String::from("Alice"), String::from("Bob")];
    let first = names[0];  // ERROR! Can't copy String
    println!("{}", first);
}

Compiler error: "cannot move out of index of Vec<String>"

Error 3: Trying to Copy Non-Copy Types

Compiler error: "cannot move out of index of Vec<String>"

Fix: Clone the specific element

fn main() {
    let names = vec![String::from("Alice"), String::from("Bob")];
    let first = names[0].clone();  // Clone just this element
    println!("{}", first);  // Works!
    println!("{:?}", names);  // Original Vec still works!
}

What's really going on with Copy and Clone (TC 12:25)

Sometimes you actually want duplicates of your data. Rust provides two mechanisms: Copy and Clone.

• Copy: Simple bitwise copy of stack bytes. (typically of data, sometimes of pointers)
• Clone: Explicit duplication that can do whatever the type needs
  • might duplicate heap data (like String or Vec)
  • might just copy stack values (like i32)
  • might run a custom cloning function on your custom types

ROUGHLY BUT NOT EXACTLY:

• Copy duplicates values on the stack
• Clone duplicates values on the heap

Clone: Explicit Deep Copying

Use .clone() to make an explicit, complete copy of data:

fn main() {
    let mut vec1 = vec![1, 2, 3];
    let mut vec2 = vec1.clone();  // Explicit copy of ALL the data

    // Proof they're separate - modify one
    vec1.push(4);

    // Both work! They're completely separate
    println!("vec1: {:?}", vec1);
    println!("vec2: {:?}", vec2);

}

What .clone() does for Vec:

Before clone:                     After clone and push:
Stack:              Heap:         Stack:              Heap:
┌─────────────┐                  ┌─────────────┐
│ vec1: Vec   │   ┌───────────┐  │ vec2: Vec   │    ┌───────────┐
│ ├ ptr ──────┼──▶│ 1 │ 2 │ 3 │  │ ├ ptr ──────┼───▶│ 1 │ 2 │ 3 │
│ ├ len: 3    │   └───────────┘  │ ├ len: 3    │    └───────────┘
│ └ cap: 3    │                  │ └ cap: 3    │
└─────────────┘                  ├─────────────┤
                                 │ vec1: Vec   │    ┌───────────────┐
                                 │ ├ ptr ──────┼───▶│ 1 │ 2 │ 3 │ 4 |
                                 │ ├ len: 4    │    └───────────────┘
                                 │ └ cap: 4    │
                                 └─────────────┘

Adding Clone to Your Types

Use #[derive(Clone)] to make your custom types cloneable:

#[derive(Clone, Debug)]
enum Temperature {
    Fahrenheit(f64),
    Celsius(f64),
}

fn main() {
    let temp1 = Temperature::Celsius(12.0);
    let temp2 = temp1.clone();  // Now this works!

    println!("temp1: {:?}", temp1);
    println!("temp2: {:?}", temp2);
}

Copy: Automatic, Cheap Duplication

Some types are so simple that Rust can copy them automatically without .clone():

fn main() {
    // These types implement Copy - no explicit .clone() needed
    let a = 42;        // i32
    let b = a;         // Automatic copy
    println!("{} {}", a, b);  // Both work

    let e = true;      // bool
    let f = e;         // Automatic copy
    println!("{} {}", e, f);  // Both work

    let g = (1, 2);    // (i32, i32) - tuples of Copy types are Copy
    let h = g;         // Automatic copy
    println!("{:?} {:?}", g, h);  // Both work
}

Adding Copy to Your Types

Use #[derive(Copy, Clone)] for simple types (note: Copy requires Clone):

#[derive(Copy, Clone, Debug)]
enum Temperature {
    Fahrenheit(f64),
    Celsius(f64),
}

fn main() {
    let temp1 = Temperature::Celsius(12.0);
    let temp2 = temp1;  // Now automatically copies!

    println!("temp1: {:?}", temp1);
    println!("temp2: {:?}", temp2);
}

YOU CAN ONLY DO THIS IF the types inside the enum (or other structures) all have Copy as well

YOU CAN'T DO THIS IF YOUR ENUM CONTAINS STRINGS

This kind of sucks though right?

• Functions steal ownership even when they just want to read data
• You have to pass data back and forth like a hot potato
• You have to clone the contents of a vec/array when you just want to view it
• You wind up with code like this:

fn analyze_data(data: Vec<i32>, usernames: Vec<String>, big_array: Box<[i32]>) -> (Vec<i32>, Vec<String>, Box<[i32]>) {
    println!("Processing {} items", data.len());
    // ... do some data cleaning ...
    (data, usernames, big_array)  // Have to return it back!
}
fn main() {
    let my_data = vec![1, 2, 3, 4, 5];
    let my_usernames = vec!["Alice", "Bob", "Charlie"];
    let my_box = Box::new([0; 10_000_000]);
    let (my_data, my_usernames, my_box) = analyze_data(my_data, my_usernames, my_box);  // Awkward!
}

Rust's solution: Borrowing - let functions temporarily use data without taking ownership!

Part 2 - What is Borrowing? (TC 12:30)

Borrowing means temporarily accessing data without taking ownership of it.

Think of it like borrowing a book from a friend:

• Your friend still owns the book (original owner keeps ownership)
• You can read it while you have it (temporary access)
• You give it back when done (reference goes out of scope)
• Your friend can still use it after you return it (original data still accessible)

Creating References with &

The & operator creates a reference (pointer) to data without taking ownership:

fn main() {
    let data = vec![10, 20, 30];

    // Create a reference to data (borrowing)
    let data_ref = &data;

    // Both work! No ownership was moved
    println!("Original: {:?}", data);      // data still valid
    println!("Reference: {:?}", data_ref); // reference works too
}

Stack/heap diagram:

Stack:                                   Heap:
  ┌─────────────────┐
  │ data_ref: &Vec  │────┐ points to 
  ├─────────────────┤    │ the stack!
  │ data: Vec<i32>  │◄───┘            ┌────┬────┬────┐
  │ ├ ptr ──────────┼───────────────▶ │ 10 │ 20 │ 30 │
  │ ├ len: 3        │                 └────┴────┴────┘
  │ └ cap: 3        │           
  └─────────────────┘           
 

References in Functions

This is where borrowing shines:

fn main() {
    let my_data = vec![1, 2, 3, 4, 5];

    analyze_data(&my_data);         // Pass a reference
    let total = calculate_sum(&my_data);  // Still works!

    println!("Original data: {:?}", my_data);  // Still have it!
    println!("Sum: {}", total);
}

fn analyze_data(data: &Vec<i32>) {  // Takes a reference!
    println!("Processing {} items", data.len());
    println!("First item: {}", data[0]);
    // No need to return anything!
}

fn calculate_sum(data: &Vec<i32>) -> i32 {  // Also takes a reference!
    data.iter().sum()
}

No more ownership juggling! Each function borrows the data, uses it, and gives it back automatically.

Let's see it with a String

The & creates a new value on the stack that points to existing data:

fn main() {
    let name = String::from("Alice");
    let name_ref = &name;

    // name_ref is a new stack value pointing to name
    println!("Name: {}", name);      // Direct access
    println!("Reference: {}", name_ref);  // Access through reference
}

Stack diagram:

   Stack:                                Heap:
  ┌─────────────────┐
  │name_ref: &String│────┐ points to 
  ├─────────────────┤    │ the stack!
  │ name: String    │◄───┘            ┌─────┬─────┬─────┬─────┬─────┐
  │ ├ ptr ──────────┼───────────────▶ │ 'A' │ 'l' │ 'i' │ 'c' │ 'e' │
  │ ├ len: 5        │                 └─────┴─────┴─────┴─────┴─────┘
  │ └ cap: 5        │           
  └─────────────────┘        

String types: String vs &str vs &String (TC 12:35)

Lecture 17 will be the end of this craziness I promise!

You've seen different string types - let's clarify:

• String: Owned, growable string on the heap (like we've been using)
• &str: A "string slice" - a reference directly to string data (points to heap or static memory)
• &String: A reference to a String (points to the String's stack metadata)

fn main() {
    let owned: String = String::from("Hello");
    let string_ref: &String = &owned;        // Reference to the String
    let str_slice: &str = &owned;            // Slice of the string data
    let literal: &str = "Hello";             // String literal (also &str)

    println!("{}", owned);
    println!("{}", string_ref);
    println!("{}", str_slice);
    println!("{}", literal);
}

Let's draw it out! (with cold calls)

In practice: Functions usually take &str as parameters, but you can pass &String and Rust will coerce it to &str automatically!

When to borrow and when to copy/clone?

Use borrowing (&) when:

• You just need to read/use the data temporarily and don't want to pass ownership around
• The data is large/expensive to copy

Use copying/cloning when:

• You're passing data to functions that need to own it
• You need to modify a copy without affecting the original

Part 3 - References and Dereferencing (& and *) (TC 12:40)

The & Operator (Creating References)

& creates a reference to existing data:

fn main() {
    let x = 42;
    let x_ref = &x;    // Create reference to x

    let scores = vec![85, 92, 78];
    let scores_ref = &scores;  // Create reference to vec

    let name = String::from("Bob");
    let name_ref = &name;      // Create reference to string

    println!("x: {}, x_ref: {}", x, x_ref);
    println!("scores: {:?}, scores_ref: {:?}", scores, scores_ref);
    println!("name: {}, name_ref: {}", name, name_ref);
}

Memory layout:

Stack:                               Heap:
┌─────────────────┐
│ name_ref: &String──┐
├─────────────────┤  │
│ name: String    │◄─┘              ┌─────┬─────┬─────┐
│ ├ ptr ──────────┼────────────────▶│ 'B' │ 'o' │ 'b' │
│ ├ len: 3        │                 └─────┴─────┴─────┘
│ └ cap: 3        │
├─────────────────┤
│ scores_ref: &Vec┼──┐
├─────────────────┤  │
│ scores: Vec     │◄─┘               ┌────┬────┬────┐
│ ├ ptr ──────────┼─────────────────▶│ 85 │ 92 │ 78 │
│ ├ len: 3        │                  └────┴────┴────┘
│ └ cap: 3        │
├─────────────────┤
│ x_ref: &i32 ────┼──┐
├─────────────────┤  │
│ x: 42           │◄─┘
└─────────────────┘

We can go on and on...

fn main() {
    let x = 42;
    let x_ref = &x;    // Create reference to x
    let x_ref_2 = &x;    // Create another reference to x
    let x_ref_ref = &x_ref;    // Create another reference to x_ref

    println!("x_ref_2: {}, x_ref_ref: {}", x_ref_2, x_ref_ref); // thanks to the macro!
}

Memory layout:

Stack:                               Heap:
┌─────────────────┐
│ x_ref_ref:&&i32 ┼────────────┐
├─────────────────┤            │
│ x_ref_2: &i32 ──┼────┐       │
├─────────────────┤    │       │
│ x_ref: &i32 ────┼──┐ │ ◄─────┘
├─────────────────┤  │ │
│ x: 42           │◄─┘─┘
└─────────────────┘

The * Operator (Dereferencing)

* is the inverse-operation to & and extracts data:

fn main() {
    let x = 42;
    let y = 10;
    let x_ref = &x;
    let y_ref = &y;

    // let sum = x_ref + y_ref;  // Must dereference to do math!
    let sum = *x_ref + *y_ref;  // Must dereference to do math!
    println!("Sum: {}", sum);

    // sometimes Rust helpfully "auto-dereferences" for you
    println!("x: {}", x);           // Direct access: 42
    println!("x_ref: {}", x_ref);   // Through reference: 42 (auto-dereference)
    println!("*x_ref: {}", *x_ref); // Manual dereference: 42
}

Why do we need * and when will it auto-deref?

• References are pointers, not the actual data
• Some operations need the actual value, not the pointer (like math operations and comparisons, and match)
• Not always needed - Rust often auto-dereferences for convenience (like in println! or vec functions like len and contains)
• But you're always safe if you dereference yourself

Part 4 - References to Elements Inside Collections (TC 12:45)

One of the trickiest parts about references is working with elements inside collections. Let's demystify this!

fn main() {
    // Vec of Copy types (i32)
    let numbers = vec![10, 20, 30];
    let first = numbers[0];        // Copies the value
    let first_ref = &numbers[0];   // Reference to the element

    println!("Copied value: {}", first);
    println!("Referenced value: {}", first_ref);
}

Memory diagram for the numbers example:

Stack:                                    Heap:
┌─────────────────┐
│ first_ref: &i32 ┼───────────────────┐
├─────────────────┤                   │
│ first: 10       │ (copied)          │
├─────────────────┤                   │
│ numbers: Vec    │                 ┌────┬────┬────┐
│ ├ ptr ──────────┼───────────────▶ │ 10 │ 20 │ 30 │
│ ├ len: 3        │                 └────┴────┴────┘
│ └ cap: 3        │  
└─────────────────┘            

It's trickier with elements that live on the heap

fn main() {
    // Vec of non-Copy types (String)
    let names = vec![
        String::from("Alice"),
        String::from("Bob")
    ];

    // let name = names[0];        // ERROR! Can't move out of Vec
    let name_ref = &names[0];      // OK! Borrow the element
    let name_clone = names[0].clone();  // OK! Clone it

    println!("Referenced name: {}", name_ref);
    println!("Cloned name: {}", name_clone);
}

Memory diagram for the names example:

Stack:                          Heap:
┌──────────────────┐           ┌─────┬─────┬─────┬─────┬─────┐
│ name_clone:String│           │ 'A' │ 'l' │ 'i' │ 'c' │ 'e' │ (cloned copy)
│ ├ ptr ───────────┼──────────▶└─────┴─────┴─────┴─────┴─────┘
│ ├ len: 5         │           
│ └ cap: 5         │                   Vec
├──────────────────┤           ┌─────────────────┐
│ name_ref: &String┼─────────▶ │String("Alice")  │     ┌─────┬─────┬─────┬─────┬─────┐
├──────────────────┤ (to [0])  │ ├ ptr ──────────┼────▶│ 'A' │ 'l' │ 'i' │ 'c' │ 'e' │
│ names: Vec       │           │ ├ len: 5        │     └─────┴─────┴─────┴─────┴─────┘
│ ├ ptr ───────────┼──────────▶│ └ cap: 5        │
│ ├ len: 2         │ (to vec)  ├─────────────────┤
│ └ cap: 2         │           │String("Bob")    │     ┌─────┬─────┬─────┐
└──────────────────┘           │ ├ ptr ──────────┼────▶│ 'B' │ 'o' │ 'b' │
                               │ ├ len: 3        │     └─────┴─────┴─────┘
                               │ └ cap: 3        │
                               └─────────────────┘

Key insight: vec[i] tries to move/copy the value. For non-Copy types, use &vec[i] to borrow instead.

Iterating with .iter() - Why We Get References

When you iterate with .iter(), you get references to elements, not the elements themselves:

fn main() {
    let numbers = vec![10, 20, 30];

    // .iter() gives us &i32 (references)
    for num_ref in numbers.iter() {
        println!("Type is &i32: {}", num_ref);
        // To use in math, dereference:
        let doubled = *num_ref * 2;
        println!("Doubled: {}", doubled);
    }

    // Original vec still valid!
    println!("Original: {:?}", numbers);
}

Let's draw it (with cold calls)

.iter() creates references so the Vec retains ownership—iteration doesn't consume the data!

Whereas what we used before (for i in arr to loop through an array) passes ownership (or copies simple types)

Pattern Matching to Extract Values: &val (TC 12:50)

You can use pattern matching to automatically dereference:

fn main() {
    let numbers = vec![10, 20, 30];

    // Without pattern matching - need to dereference manually
    for num_ref in numbers.iter() {
        let squared = *num_ref * *num_ref;
        println!("{}", squared);
    }

    // With pattern matching - automatic dereference!
    for &num in numbers.iter() {
        let squared = num * num;  // num is i32, not &i32
        println!("{}", squared);
    }
}

The & in the pattern &num says: "Match a reference, and bind the value it points to"

Enumerate with References

.enumerate() gives you (index, &value):

fn main() {
    let scores = vec![85, 92, 78, 95];

    // enumerate gives (usize, &i32)
    for (i, score_ref) in scores.iter().enumerate() {
        println!("Score {}: {}", i, score_ref);
    }

    // Pattern match to get the value directly
    for (i, &score) in scores.iter().enumerate() {
        if score > 90 {
            println!("High score at index {}: {}", i, score);
        }
    }
}

Quick Reference: Iterator Types

fn main() {
    let vec = vec![1, 2, 3];

    // Three ways to iterate:
    for val in vec.iter() {          // val: &i32 (borrow each element)
        println!("{}", val);
    }

    for val in &vec {                // val: &i32 (shorthand for .iter())
        println!("{}", val);
    }

    for val in vec.iter_mut() {      // val: &mut i32 (mutable borrow - next lecture!)
        *val += 10;
    }

    // for val in vec {               // val: i32 (consumes the vec)
    //     println!("{}", val);
    // }
    // Can't use vec here - it was moved!
}

Activity time!

Lecture 17 - &mut and the Borrow Checker

Logistics

• Last time: Immutable references (&) and basic borrowing
• Today: Mutable references (&mut) and complete borrowing rules

Things "in flight"

• HW1 correction grading should be complete - if not let me know - your corrected % was in the update email
• HW2 correction grading is in progress, will be done by Thursday - status was in update email
• HW3 grading has started, should be done by Friday
• HW4 is open, due on 10/24 - you should have everything you need after tomorrow (Strings)
• Exam 1 corrections are due this Wednesday evening - if you're interested in an oral exam please fill out that part of the assignment.
  • There's no 48-hour late window
  • There was apparently a bug in the correction item for question 1.8 - if you already submitted a correction for that please double-check that it's there.

Learning Objectives

By the end of today, you should be able to:

• Use mutable references (&mut T) to modify borrowed data
• Understand and apply Rust's borrowing rules (the borrow checker)
• Debug more borrowing compiler errors

Let's review (and clarify) immutable borrows (TC 12:25)

Question 1 from Friday

fn main() {
    let data = vec![1, 2, 3];
    print_data(data);
    println!("{:?}", data); // Fix this!
}

fn print_data(v: Vec<i32>) {
    println!("{:?}", v);
}

Question 2 from Friday

fn main() {
    let scores = vec![85, 92, 78];
    let first = scores[0];  // This works, but...

    let names = vec![String::from("Alice")];
    let first_name = names[0];  // This doesn't! Fix it

    println!("First score: {}", first);
    println!("First name: {}", first_name);
}

A note about Question 5:

fn main() {
    let pairs = vec![(1, 2), (3, 4), (5, 6)];

    for (a, b) in pairs.iter() {
        let sum = a + b;  // Error! Can't add references
        println!("{} + {} = {}", a, b, sum);
    }

    println!("Pairs still available: {:?}", pairs);
}

This actually compiles, and practically anything I tried to do to break it compiles too.

In fact, it looks like + actually auto-dereferences &i32 (in contrast with what I said Friday).

Clarifying how *&x != x exactly

While * and & are inverse operations, dereferencing doesn't transfer ownership:

fn main() {
    let x = 42;
    let x_ref = &x;

    let y = *x_ref;  // For Copy types, this copies the value
    println!("x: {}, y: {}", x, y);  // Both work

    let name = String::from("Bob");
    let name_ref = &name;

    // let owned = *name_ref;  // ERROR! Would need to move, but we only borrowed
    let cloned = (*name_ref).clone();  // Must explicitly clone
    println!("name: {}, cloned: {}", name, cloned);
}

Stack/heap diagram:

For: let name_ref = &name; and accessing *name_ref

Stack:                               Heap:
┌─────────────────┐
│ name_ref ───────┼──┐               ┌─────┬─────┬─────┐
├─────────────────┤  │               │ 'B' │ 'o' │ 'b' │
│ name: String    │◄─┘               └─────┴─────┴─────┘
│ ├ ptr ──────────┼─────────────────▶   
│ ├ len: 3        │                     
│ └ cap: 3        │                     
└─────────────────┘                     

Summary:

• *&x gives you access to x's value
• For Copy types: makes a copy
• For non-Copy types: gives access but can't take ownership (you only borrowed!)

Draw out copy case on the board

Pattern Matching with &: Only for Copy Types!

When you use for &val in arr.iter(), the & pattern extracts the value from the reference:

fn main() {
    // With Copy types - works!
    let numbers = vec![1, 2, 3];
    for &num in numbers.iter() {
        // num is i32 (copied from &i32)
        println!("{}", num * 2);
    }

    // With non-Copy types - ERROR!
    let names = vec![String::from("Alice"), String::from("Bob")];
    // for &name in names.iter() {  // Can't move out of borrowed reference
    //      let name_copy = name.clone();
    //      println!("{}", name_copy);
    // }

    // Must keep as reference for non-Copy types
    for name in names.iter() {
        // name is &String
        let name_copy = (*name).clone();  // Need * to clone
        println!("Cloned: {}", name_copy);
    }
}

What's happening:

• &val pattern matching extracts the value, not a reference
• For Copy types: copies the value out → val is T
• For non-Copy types: would try to move → ERROR (can't move from borrowed content)
• Solution for non-Copy: use val without & → val is &T

Mutable References (&mut T) (TC 12:30)

Use &mut to create a mutable reference that allows modification:

fn main() {
    let mut data = vec![1, 2, 3];  // Must be mut to begin with!
    let data_ref = &mut data;      // Mutable reference 

    // Can modify through mutable reference:
    data_ref.push(4); 
    data_ref[0] = 10;

    println!("Modified: {:?}", data_ref);

    add_item(&mut data, 5);
    println!("After adding: {:?}", data);  // [10, 2, 3, 4, 5]
}

fn add_item(data: &mut Vec<i32>, item: i32) {  // Mutable reference parameter
    data.push(item);  // Can modify!
}

Stack/Heap with Mutable References

fn main() {
    let mut message = String::from("Hello");
    modify_string(&mut message);
    println!("{}", message);  // "Hello - modified!"
}

fn modify_string(text: &mut String) {
    text.push_str("!!!");
}

Memory progression through the function call:

Step 1: Before calling modify_string()

Stack:                               Heap:
┌─────────────────┐                 ┌─────┬─────┬─────┬─────┬─────┐
│ message: String │                 │ 'H' │ 'e' │ 'l' │ 'l' │ 'o' │
│ ├ ptr ──────────┼────────────────▶│     │     │     │     │     │
│ ├ len: 5        │                 └─────┴─────┴─────┴─────┴─────┘
│ └ cap: 5        │
└─────────────────┘

Step 2: During modify_string() call (before push_str)

Stack:                               Heap:
┌─────────────────┐ 
│ text: &mut String─────┐
├─────────────────┤     │           
│ message: String │◄────┘           ┌─────┬─────┬─────┬─────┬─────┐
│ ├ ptr ──────────┼────────────────▶│ 'H' │ 'e' │ 'l' │ 'l' │ 'o' │
│ ├ len: 5        │                 └─────┴─────┴─────┴─────┴─────┘
│ └ cap: 5        │    
└─────────────────┘

Step 3: After text.push_str(" - modified!")

Stack:                               Heap:
┌─────────────────┐ 
│ text: &mut String─────┐
├─────────────────┤     │        
│ message: String │◄────┘           ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ ├ ptr ──────────┼────────────────▶│ 'H' │ 'e' │ 'l' │ 'l' │ 'o' │ '!' │ '!' │ '!' │
│ ├ len: 17       │                 └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
│ └ cap: 18       │     
└─────────────────┘

Step 4: After function returns

Stack:                               Heap:
┌─────────────────┐    
│ message: String │                 ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ ├ ptr ──────────┼────────────────▶│ 'H' │ 'e' │ 'l' │ 'l' │ 'o' │ '!' │ '!' │ '!' │
│ ├ len: 17       │                 └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
│ └ cap: 18       │
└─────────────────┘

Borrowing Rules (The Borrow Checker) (TC 12:35)

Rust enforces strict rules about borrowing to prevent memory corruption:

• Rule 1: You can have EITHER many immutable references OR ONE mutable reference
• Rule 2: References must be valid (they cannot outlive what they refer to)

Rule 1: You can have EITHER many immutable references OR ONE mutable reference

This works (multiple immutable references):

fn main() {
    let data = vec![1, 2, 3];
    let ref1 = &data;
    let ref2 = &data;
    let ref3 = &data;

    println!("{:?} {:?} {:?}", ref1, ref2, ref3);  // All read-only
}

This works (one mutable reference):

fn main() {
    let mut data = vec![1, 2, 3];
    let ref1 = &mut data;

    ref1.push(4);
    println!("{:?}", ref1);  // Only one mutable reference
}

This does NOT work:

fn main() {
    let mut data = vec![1, 2, 3];
    let ref1 = &data;      // Immutable reference
    let ref2 = &mut data;  // ERROR! Can't have both!

    println!("{:?} {:?}", ref1, ref2);
}

Rule 2: References must be valid (they cannot outlive what they refer to)

This does NOT work:

fn main() {
    let reference;
    {
        let value = vec![1, 2, 3];
        reference = &value;  // ERROR! value will be dropped
    }  // value goes out of scope here
    // println!("{:?}", reference);  // reference would be dangling!
}

This is why you can't return from a function a reference to a variable you defined inside the function

Why These Rules Matter

Without these rules, you could have:

1. Data races: Two threads modifying the same data simultaneously
2. Use-after-free: Using memory that's been freed
3. Iterator invalidation: Modifying a collection while iterating

Rust prevents all of these at compile time!

Important: Modifying Through the Original Name

Even modifying through the original variable name counts as a mutable borrow!

fn main() {
    let mut x = 10;
    println!("{}", x);  
    let y = &x;           // Immutable borrow
    x = 20;               // ERROR! Tries to mutably borrow x
    println!("{}", y);    // y is still being used
}

Error: "cannot assign to x because it is borrowed"

Why? When you have an active reference (y), Rust must guarantee that reference stays valid. Modifying x directly would be a mutable operation, which conflicts with the immutable borrow.

fn main() {
    let mut x = 10;
    let y = &x;
    println!("{}", y);    // Last use of y

    x = 20;               // OK! y is no longer used
    println!("{}", x);
}

Key insight: The original variable name doesn't give you special privileges! While a reference exists and is being used, you can't modify the data through any path—not even the original name.

Mutable and immutable borrowing in practice

fn main() {
    let mut scores = vec![85, 92, 78, 96, 88];

    // Analyze first (immutable borrow)
    let (total, average) = analyze_data(&scores);
    println!("Total: {}, Average: {:.1}", total, average);

    // Then normalize (mutable borrow)
    normalize_data(&mut scores);
    println!("Normalized: {:?}", scores);
}

fn analyze_data(data: &Vec<i32>) -> (i32, f64) {
    let sum: i32 = data.iter().sum();
    let avg = sum as f64 / data.len() as f64;
    (sum, avg)
}

fn normalize_data(data: &mut Vec<i32>) {
    let max = *data.iter().max().unwrap();
    for item in data.iter_mut() {
        *item = *item * 100 / max;
    }
}

This works because:

• analyze_data finishes before normalize_data starts
• No overlap between immutable and mutable borrows
• Original data stays accessible in main

Note on function signatures: In these examples we use &Vec<i32> for clarity. In practice, Rust developers usually use slices (&[i32]) which are more flexible. We'll cover slices in the next lecture!

Think-Pair-Share: Mutable Borrowing vs Ownership (TC 12:40)

Question: How are mutable borrowing and transferring ownership the same, and how are they different? When should you use one vs the other?

Think (1 minute): Consider these two function signatures:

#![allow(unused)]
fn main() {
fn process_data(data: Vec<i32>) -> Vec<i32>  // Takes ownership
fn process_data(data: &mut Vec<i32>)         // Borrows
}

What are the tradeoffs? When would you choose each approach?

Mutable Borrowing vs Ownership

Similarities:

Differences:

Use &mut T (mutable borrow) when:

Use T (transfer ownership) when:

Rule of thumb:

Mixing Immutable and Mutable References

The timing matters! This works:

fn main() {
    let mut integer = 10;

    // Use immutable reference first
    let ir = &integer;
    println!("Reading: {}", ir);
    // ir is no longer used after this point

    // Now we can create a mutable reference
    let mr = &mut integer;
    *mr += 5;
    println!("After modification: {}", mr);

    // Can create new immutable references after mutable is done
    let ir2 = &integer;
    println!("Reading again: {}", ir2);
}

But this doesn't work:

fn main() {
    let mut integer = 10;

    let ir = &integer;      // Immutable reference
    let mr = &mut integer;  // ERROR! Can't create mutable while immutable exists

    println!("{}", ir);     // ir is still being used
    *mr += 5;
}

Key insight: Rust tracks when references are last used, not just when they go out of scope!

More on iter() and iter_mut() (TC 12:45)

We saw .iter() last time - now we'll add .iter_mut():

• .iter(): Gives you immutable references (&T) to each element
• .iter_mut(): Gives you mutable references (&mut T) to each element

fn main() {
    let mut numbers = vec![1, 2, 3, 4, 5];

    // .iter() - read-only access
    for num in numbers.iter() {
        println!("{}", num);  // num is &i32
        // *num += 1;  // ERROR! Can't modify through immutable reference
    }

    // .iter_mut() - mutable access
    for num in numbers.iter_mut() {
        *num += 10;  // num is &mut i32 - can modify!
    }

    println!("Modified: {:?}", numbers);  // [11, 12, 13, 14, 15]
}

Dereferencing with iter_mut()

Unlike with .iter() where you can use for &num in... pattern matching (for copy types!), with .iter_mut() you always need to dereference with * to modify the value:

fn main() {
    let mut numbers = vec![1, 2, 3, 4, 5];

    // Must use * to modify through mutable reference
    for num in numbers.iter_mut() {
        *num *= 2;  // num is &mut i32, *num is i32
    }

    println!("{:?}", numbers);  // [2, 4, 6, 8, 10]
}

Why no pattern matching? With .iter() you can work off a copy because you're just reading. With .iter_mut() you need the mutable reference itself to assign through it, so you must use *.

Enumerate with iter_mut()

You can combine .iter_mut() with .enumerate() to get both the index and a mutable reference:

fn main() {
    let mut scores = vec![78, 85, 92, 67, 88];

    // enumerate gives (usize, &mut i32)
    for (i, score_ref) in scores.iter_mut().enumerate() {
        println!("Score {}: {}", i, score_ref);

        // Modify based on index
        if i == 0 {
            *score_ref += 10;  // Bonus for first student
        }
    }

    println!("Updated scores: {:?}", scores);  // [88, 85, 92, 67, 88]
}

Type breakdown:

• i is usize (the index)
• score_ref is &mut i32 (mutable reference to the element)
• Use *score_ref to modify the value

Activity Time

Key Takeaways

1. Mutable references (&mut T): Allow modification of borrowed data
2. Borrowing rules prevent bugs: No data races, no use-after-free, no iterator invalidation
3. Two key rules: Many readers OR one writer (and not both!), references must live long enough
4. Timing matters: Rust tracks when references are last used, not just scope
5. Sequential borrowing: You can have mutable then immutable, or vice versa
6. Design principle: Separate read-only and modification phases in your code

Lecture 18 - Strings and Slices

Logistics

• Same notes as yesterday re HWs, Exams (Exam corrections are due tonight)
• I'll schedule the oral exams early Thursday, they'll start on Friday
• Request from Joey - For homeworks, please just ignore the "feedback" branch/PR, don't merge it

Learning Objectives

By the end of today, you should be able to:

• (Really!) Understand the difference between String and &str types
• Understand Unicode and UTF-8 encoding basics
• Apply ownership rules correctly when working with strings and slices

Part 1 - Review and Clarification

Clarifying - modifying through a mutable reference

fn main() {
    let mut vec = vec![1, 2, 3];
    let vec_ref = &mut vec;

    // Method 1: Call methods that modify in-place
    vec_ref.push(4); 
    // Method 2: Use * to dereference and assign
    *vec_ref = vec![5,6,7];

    println!("vec is now: {:?}", vec);  // [5, 6, 7]

    let mut x = 5;
    let y = &mut x;

    // Dereferencing is your only option here
    *y = 10;  
    println!("x is now: {}", x);  // 10
}

Understanding mut in Different Positions

fn main() {
    let mut x = 5;
    let mut y = &mut x;

    // Two different 'mut' keywords here!
    // First mut: y itself can be reassigned to point elsewhere
    // Second mut: y points to mutable data (can modify *y)

    *y = 10;  // OK - modify the value y points to
    println!("y is now: {}", y); 
    // Now that we're done with y we can look at:
    println!("x is now: {}", x); 

    // y = 5;  // ERROR! Can't assign i32 to &mut i32
    // This would try to change y from a reference into a number

    // but we could make it a different &mut i32:
    let mut z = 6;
    y = &mut z;
    println!("y is now: {}", y);

}

Key insight:

• *y = value changes what y points to
• y = &mut other changes where y points
• Methods like .push() automatically dereference, so no * needed

Review - Some common borrowing patterns

Pattern 1: Read-Only Processing

fn find_max(numbers: &Vec<i32>) -> Option<&i32> {
    numbers.iter().max()
}

fn count_even(numbers: &Vec<i32>) -> usize {
    let mut count = 0;
    for &n in numbers.iter() {
        if n % 2 == 0 {
            count += 1;
        }
    }
    count
}

fn main() {
    let data = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

    // Can call multiple read-only functions:
    let max_val = find_max(&data);
    let even_count = count_even(&data);
    let sum: i32 = data.iter().sum();

    println!("Max: {:?}, Even count: {}, Sum: {}", max_val, even_count, sum);
    println!("Original data still available: {:?}", data);
}

Pattern 2: In-Place Modification

fn double_all(numbers: &mut Vec<i32>) {
    for item in numbers.iter_mut() {
        *item *= 2;
    }
}

fn filter_positive(numbers: &mut Vec<i32>) {
    let mut i = 0;
    while i < numbers.len() {
        if numbers[i] <= 0 {
            numbers.remove(i);
        } else {
            i += 1;
        }
    }
}

fn main() {
    let mut data = vec![-2, 1, -1, 3, 0, 4];
    println!("Original: {:?}", data);

    double_all(&mut data);
    println!("Doubled: {:?}", data);

    filter_positive(&mut data);
    println!("Positive only: {:?}", data);
}

Part 2 - Slices

A slice is a reference to a contiguous portion of data without ownership:

Key points: &[T] type, borrowed references, syntax &collection[start..end]

#![allow(unused)]
fn main() {
let data = [1, 2, 3, 4, 5, 6];
let slice1 = &data[1..4];    // [2, 3, 4]
let slice2 = &data[..3];     // [1, 2, 3] - from start
let slice3 = &data[2..];     // [3, 4, 5, 6] - to end
println!("Slice3: {:?}", slice3);
}

Mutable Slices

Note the index is relative to the slice!

#![allow(unused)]
fn main() {
let mut numbers = [10, 20, 30, 40, 50];
{
    let slice = &mut numbers[1..4];
    slice[0] = 999;  // Modify through slice
}  // slice scope ends
println!("{:?}", numbers);  // [10, 999, 30, 40, 50]
}

Slices of Different Types

Slices work with any contiguous data:

• &[T] - slice of array/Vec elements
• &str - slice of string bytes (UTF-8)

fn main() {
    // Slice of an array
    let array = [1, 2, 3, 4, 5];
    let array_slice: &[i32] = &array[1..4];
    println!("Array slice: {:?}", array_slice);

    // Slice of a Vec
    let vec = vec![1.1, 2.2, 3.3, 4.4, 5.5];
    let vec_slice: &[f32] = &vec[2..];
    println!("Vec slice: {:?}", vec_slice);

    // Slice of a String (string slice = &str)
    let string = String::from("Hello World");
    let str_slice: &str = &string[0..5];
    println!("String slice: {}", str_slice); 

    // Slice of a slice
    let vec_slice_slice: &[f32] = &vec_slice[0..2];
    println!("Slice of a slice: {:?}", vec_slice_slice); 
}

Memory Representation of Slices

Slices are "fat pointers" - they contain pointer + length:

#![allow(unused)]
fn main() {
let v = vec![10, 20, 30, 40, 50];
let x = &v[1..4];  // Points to middle 3 elements
}

     STACK                    Heap
┌───────────────┐          ┌────────────────────────┐
│ x: &[i32]     │          │ 10 │ 20 │ 30 │ 40 │ 50 │
│    ptr ───────┼──────────|───►│──────────────┤    │
│    len: 3     │          └────────────────────────┘
├───────────────┤                 ▲
│ v: Vec<i32>   │                 │
│    ptr ───────┼─────────────────┘
│    len: 5     │
│    capacity: 5│
└───────────────┘

Ownership Interlude: Slice Borrowing

What do you think happens in this code?

#![allow(unused)]
fn main() {
let mut data = vec![1, 2, 3, 4];
let slice1 = &data[0..2];     
let slice2 = &mut data[2..4]; 
println!("{:?} {:?}", slice1, slice2);
}

A) Compiles fine - non-overlapping slices (indices 0 and 1 vs 2 and 3)
B) Compiler error - mixing mutable and immutable borrows
C) Runtime panic

Part 3 - Strings Deep-dive

The FOUR (or 3) kinds of Strings

#![allow(unused)]
fn main() {
let s = String::from("Hello DS210");    // Heap allocation - owned String
let s_ref: &String = &s;                // Reference to the String itself
let literal: &str = "literal";          // String slice from program binary
let slice: &str = &s[0..5];             // String slice from heap (borrows from s)
}

       STACK                    HEAP                PROGRAM BINARY
┌──────────────────┐         ┌─────────────┐      ┌─────────────┐
│ s: String        │◄─┐      │"Hello DS210"│      │  "literal"  │
│   ptr ───────────┼──┼─────►│             │      └─────────────┘
│   len: 11        │  │      └─────────────┘             ▲
│   capacity: 20   │  │           ▲                      │
├──────────────────┤  │           │                      │
│ s_ref: &String   │  │           │                      │
│   ptr ───────────┼──┘           │                      │
├──────────────────┤              │                      │
│ literal: &str    │              │                      │
│   ptr ───────────┼──────────────┼──────────────────────┘
│   len: 7         │              │
├──────────────────┤              │
│ slice: &str      │              │
│   ptr ───────────┼──────────────┘ (points to "Hello" in heap)
│   len: 5         │
└──────────────────┘

String encodings: Unicode and UTF-8

Unicode is a standard that assigns a unique number (called a "code point") to every character across all writing systems. For example:

• 'A' = U+0041
• 'é' = U+00E9
• '你' = U+4F60
• '🦀' = U+1F980

The char type in Rust stores this value directly - so there are always 4 bytes per char

UTF-8 is an encoding (a way to represent those Unicode code points as bytes in memory/files). It's one of several ways to encode Unicode:

• UTF-8: Variable-length (1-4 bytes per character), backward compatible with ASCII
• UTF-16: Variable-length (2 or 4 bytes per character)
• UTF-32: Fixed-length (always 4 bytes per character)

UTF-8 encoding uses variable-length bytes per character:

Character   UTF-8 Bytes    Binary Representation
'A'         1 byte         01000001
'é'         2 bytes        11000011 10101001
'你'        3 bytes        11100100 10111000 10101101
'🦀'        4 bytes        11110000 10011111 10100110 10000000

Strings in Rust use UTF-8 so use 1-4 bytes per character as needed.

Strings Are Collections of Characters

A String or &str is a sequence of Unicode characters encoded in UTF-8:

#![allow(unused)]
fn main() {
let emoji = "🦀🚀";                                
println!("Bytes: {}", emoji.len());                // 8 bytes (4 + 4 in UTF-8)
println!("Characters: {}", emoji.chars().count()); // 2 characters

let accents = "Aé";                                
println!("Bytes: {}", accents.len());                // 3 bytes (1 + 2 in UTF-8)
println!("Characters: {}", accents.chars().count()); // 2 characters
}

The key insight:

• .len() returns bytes, not character count!
• Use .chars() to iterate over actual characters

Converting Between char and String

#![allow(unused)]
fn main() {
// char to String
let c: char = '🦀';
let s: String = c.to_string();

// String to chars
let text = "Hello";
for ch in text.chars() {  // ch is type char
    println!("{}", ch);
}

// Collecting chars into a String
let chars: Vec<char> = vec!['H', 'i', '!'];
let s: String = chars.iter().collect(); // we'll see collect more soon
}

So THAT'S why string indexing is forbidden

text[0] would return a byte, potentially splitting a multi-byte character and corrupting Unicode data.

fn main() {
    let text = "Hello, 世界!";
    // let c = text[0];  // ERROR!

    let first = text.chars().next().unwrap();  // Safe

    let first_three: String = text.chars().take(3).collect(); // Also safe
}

Slices won't throw compiler errors but are also potentially dangerous:

fn main() {
    // ASCII - works fine
    let text = "Hello, world!";
    let hello = &text[0..5];    // OK - slices at character boundaries

    // Emoji at the boundary - PANIC!
    // let text = "🦀Hello";
    // let slice = &text[0..2];    // PANIC! - slices through middle of 🦀 (4 bytes)

    // Emoji not at boundary - OK
    let text = "🦀Hello";
    let slice = &text[4..9];    // OK - starts after 🦀, slices "Hello"
}

Ownership Interlude: String Ownership Quiz

Question: What happens here?

#![allow(unused)]
fn main() {
let s1 = String::from("Hello");
let s2 = s1;
let s3 = s2.clone();
println!("{} {}", s1, s2);  // What happens?
}

A) Prints "Hello Hello"
B) Compiler error - s1 cannot be assigned to s2 on line 2
C) Compiler error - s2 cannot be cloned on line 3
D) Compiler error - s1 cannot print on line 4
E) Runtime panic

String Concatenation

#![allow(unused)]
fn main() {
// Method 1: Mutation (keeps ownership)
let mut s = String::from("Hello");
s.push_str(" World");  // Mutates s

// Method 2: + operator (moves first string)
let s1 = String::from("Hello");
let s2 = s1 + " World";  // s1 is moved!

// Method 3: format! (no ownership taken)
let name = "Data";
let num = 210;
let result = format!("{} Science {}", name, num);  // name & num still usable
}

Ownership note: + moves first operand, format! borrows all inputs.

Function Parameters: &str vs &String

#![allow(unused)]
fn main() {
// Good: accepts &String, and &str
fn analyze_text(text: &str) -> usize { ...

// Less flexible: only accepts &String
fn analyze_ref(text: &String) -> usize { ...

// Moves ownership
fn analyze_owned(text: String) -> usize { ...
}

Best practice: Use &str parameters - more flexible, no ownership transfer.

Memory Layout: Passing &String to &str Parameter

When you pass &String to a function expecting &str, Rust converts it for you:

fn analyze_text(text: &str) -> usize {
    text.len()
}

fn main() {
    let s = String::from("Hello DS210");
    let s_ref = &s;
    analyze_text(s_ref);  // &String → &str conversion
}

         STACK                           HEAP

  ┌─ analyze_text ──┐          ┌─────────────────┐
  │ text: &str      │          │  "Hello DS210"  │
  │   ptr ──────────┼──────────┤─►┤───────────│  │
  │   len: 11       │          └─────────────────┘
  └─────────────────┘                     ▲
                                          │
  ┌──── main ───────┐                     │
  │ s_ref: &String  │                     │
  │   ptr ──────────┼──┐                  │
  ├─────────────────┤  │                  │
  │ s: String       │◄─┘                  │
  │   ptr ──────────┼─────────────────────┘
  │   len: 11       │
  │   capacity: 20  │
  └─────────────────┘

What happens:

1. s owns the heap data
2. s_ref is a reference to s itself (points to stack)
3. When passed to analyze_text, Rust converts &String → &str
4. text is a string slice pointing directly to the heap data

Think-Pair-Share: String Slice Safety

Thought Experiment:

Consider this situation:

#![allow(unused)]
fn main() {
let mut s = String::from("Hello");
let slice = &s[0..5];  // Points directly to heap data
}

The string slice slice points directly to the heap, not to s on the stack.

Question: What happens if we modify s after creating the slice?

#![allow(unused)]
fn main() {
let mut s = String::from("Hello");
let slice = &s[0..5];
s.push_str(" World!");  // String grows, might reallocate!
println!("{}", slice);  // Is slice still valid?
}

Since slice points directly to heap memory, and the String might reallocate to a new location when it grows, won't the slice pointer become invalid (dangling)?

Part 4 - Iter and Collect

More on iter() and iter_mut()

We saw .iter() before - now we'll add .iter_mut():

• .iter(): Gives you immutable references (&T) to each element
• .iter_mut(): Gives you mutable references (&mut T) to each element

fn main() {
    let mut numbers = vec![1, 2, 3, 4, 5];

    // .iter() - read-only access
    for num in numbers.iter() {
        println!("{}", num);  // num is &i32
        // *num += 1;  // ERROR! Can't modify through immutable reference
    }

    // .iter_mut() - mutable access
    for num in numbers.iter_mut() {
        *num += 10;  // num is &mut i32 - can modify!
    }

    println!("Modified: {:?}", numbers);  // [11, 12, 13, 14, 15]
}

Dereferencing with iter_mut()

With .iter_mut() you always need to dereference with * to modify the value:

Why no pattern matching? With .iter() you can work off a copy because you're just reading. With .iter_mut() you need the mutable reference itself to assign through it, so you must use *.

fn main() {
    let mut numbers = vec![1, 2, 3, 4, 5];

    // Must use * to modify through mutable reference
    for num in numbers.iter_mut() {
        *num *= 2;  // num is &mut i32, *num is i32
    }

    println!("{:?}", numbers);  // [2, 4, 6, 8, 10]
}

Enumerate with iter_mut()

You can combine .iter_mut() with .enumerate() to get both the index and a mutable reference:

fn main() {
    let mut scores = vec![78, 85, 92, 67, 88];

    // enumerate gives (usize, &mut i32)
    for (i, score_ref) in scores.iter_mut().enumerate() {
        println!("Score {}: {}", i, score_ref);

        // Modify based on index
        if i == 0 {
            *score_ref += 10;  // Bonus for first student
        }
    }

    println!("Updated scores: {:?}", scores);  // [88, 85, 92, 67, 88]
}

Intro to functions on iterators: sum() and collect()

.iter() also enables you to use:

• Math functions like sum() and max()
• The .collect() method, which can transform an iterator into various types (more on this later)

fn main() {
    let numbers = vec![1, 2, 3, 4, 5];

    // sum() consumes the iterator and returns a single value
    let total: i32 = numbers.iter().sum();
    println!("Total: {}", total);  // 15 (empty iter -> 0)

    // max() returns an Option<&i32>
    let largest = numbers.iter().max();
    println!("Largest: {:?}", largest);  // Some(5) (empty iter -> None)

    // Collect strings into a single String
    let words = vec!["Hello", "world", "!"];
    let sentence: String = words.iter().collect();
    println!("Sentence: {}", sentence);  // "Helloworld!"
    // .collect() can build different types based on the type annotation!
}

More Examples of .collect()

.collect() is very flexible - it can build different collection types based on your type annotation:

fn main() {
    // Collect chars into a String
    let letters = vec!['H', 'e', 'l', 'l', 'o'];
    let word: String = letters.iter().collect();
    println!("{}", word);  // "Hello"

    // Collect into a Vec
    let numbers = [1, 2, 3, 4, 5];
     // this is "closure" notation we'll learn later:
    let doubled: Vec<i32> = numbers.iter().map(|x| x * 2).collect();
    println!("{:?}", doubled);  // [2, 4, 6, 8, 10]

    // Collect string slices into a String
    let parts = vec!["Data", " ", "Science", " ", "210"];
    let course: String = parts.iter().collect();
    println!("{}", course);  // "Data Science 210"

    // Collect range into a Vec
    let range_vec: Vec<i32> = (0..5).collect();
    println!("{:?}", range_vec);  // [0, 1, 2, 3, 4]

    // Collect chars from a string into a Vec
    let text = "Hello";
    let char_vec: Vec<char> = text.chars().collect();
    println!("{:?}", char_vec);  // ['H', 'e', 'l', 'l', 'o']

    // Take first 3 chars and collect back into String
    let first_three: String = "Hello World".chars().take(3).collect();
    println!("{}", first_three);  // "Hel"
}

Lecture 19 - HashMap and HashSet

Logistics

• Exam 1 corrections are done, oral exams are Monday and Tuesday
• HW4 due in a week - Joey will intro in discussions on Tuesday
• Reminder to cite sources and be skeptical of AI answers

Learning Objectives

By the end of today, you should be able to:

• Use HashMap<K, V> to quickly look up data by key
• Use HashSet<T> to find unique values and check membership
• Understand what these have in common with Vec and String (besides capital letters)

What are collections?

Collections are types that can hold multiple values of a specified type.

So far

Heap-allocated collections:

• Vec<T> - Growable array of items of type T (Lecture 15)
• String - Growable text data (Lecture 18)

Stack-allocated collections:

• Arrays [T; N] - Fixed number of items, known at compile time

Today we get two more collections

• HashMap<K, V> - Look up values by key (like a dictionary)
• HashSet<T> - Store unique values (no duplicates allowed)

Both are heap-allocated and follow the same ownership patterns as Vec!

The Problem: Looking Up Data Quickly

Imagine you're analyzing customer data with a million records.

You need to find customer "Alice Smith"'s phone number quickly.

Option 1: Search through a list

#![allow(unused)]
fn main() {
let customer_data = vec![("John Doe", 12345), 
                        ("Jane Smith", 56789), 
                        ("Alice Smith", 11235),
                         /* ... 999,997 more */];

// This is slow - might check every name!
for customer in customer_data.iter() {
    if customer.0 == "Alice Smith" {
        println!("{}", customer.1);
        break;
    }
}
}

Option 2: Sort and box them?

Instead of searching, what if we kept the information in organized drawers so we could jump directly to Alice's information?

Option 3: ???

Option 3: The miraculous HashMap

(Yep, it's basically a python dict)

#![allow(unused)]
fn main() {
use std::collections::HashMap;

// Create a "phone book" for customer_data
let mut customer_data = HashMap::new();
customer_data.insert("Alice Smith".to_string(), 12345);
customer_data.insert("Bob Jones".to_string(), 56789);
customer_data.insert("Carol White".to_string(), 11235);

// Look up Alice's data instantly
match customer_data.get("Alice Smith") {
    Some(x) => println!("Alice's data is {}", x),
    None => println!("Alice not found"),
}
}

NOTE .get() returns an Option type!

Memory Layout: HashMap on Stack and Heap

What does a HashMap look like in memory?

#![allow(unused)]
fn main() {
let mut customer_data = HashMap::new();
customer_data.insert("Alice Smith".to_string(), 12345);
customer_data.insert("Bob Jones".to_string(), 56789);
}

         STACK                                    HEAP

┌──────────────────────┐             ┌──────────────────────────────┐
│ customer_data:       │             │  Bucket Array (simplified)   │
│  HashMap<String,i32> │             │                              │
│   ptr ───────────────┼────────────►│  [0]: (hash) ──────┐         │
│   len: 2             │             │  [1]: empty        │         │
│   capacity: 8        │             │  [2]: (hash) ─┐    │         │
└──────────────────────┘             │  [3]: empty   │    │         │
                                     │  ...          │    │         │
                                     └───────────────┼────┼─────────┘
                                                     │    │
                                     ┌───────────────┘    │
                                     ▼                    ▼
                              ┌──────────────┐    ┌──────────────┐
                              │"Bob Jones"   │    │"Alice Smith" │
                              │  (String)    │    │  (String)    │
                              ├──────────────┤    ├──────────────┤
                              │  56789       │    │  12345       │
                              │  (i32)       │    │  (i32)       │
                              └──────────────┘    └──────────────┘

Key points:

• HashMap lives on the stack (pointer + metadata)
• The bucket array lives on the heap
• Both keys (Strings) and values are stored on the heap
• Hash function determines which bucket stores each key-value pair

Adding and Updating Data

#![allow(unused)]
fn main() {
use std::collections::HashMap;
// Store product prices
let mut prices = HashMap::new();
prices.insert("laptop".to_string(), 999.99);
prices.insert("mouse".to_string(), 25.50);
prices.insert("keyboard".to_string(), 75.00);

// Update an existing price
prices.insert("laptop".to_string(), 899.99);  // overwrites

// Only add if not already there
if !prices.contains_key("tablet") {
    prices.insert("tablet".to_string(), 199.99);
}

// More concise way to add but avoid overwriting:
prices.entry("tablet".to_string()).or_insert(199.99);
}

How does this really work?

It's not Quite A-Z rooms with A-Z cabinets with A-Z drawers...

If you did that for our class (of 46 students):

• 9 of you have A names (~20%)
• No one has F, I, N, O, P, Q, R, U, X, Z
• Not a great use of space!

Okay, then we'll just make... two A rooms

This is kind of how libraries do it:

We have the Dewey Decimal System:

• Looking for "The Rust Programming Language"?
  • Turn it into code "005.133"
  • Find the appropriate shelf : "005.8-005.212"
  • Find the book on that shelf
• Looking for "The Lord of the Rings"?
  • Turn it into code "823.912"
  • Find the right shelf: "823-824"
  • Find the book on that shelf

And we can have some shelves cover fewer numbers and some shelves cover more...

But we don't know at first what the distribution will be!

The solution - hashes

A hash function takes any input and converts it to a number.

Key properties:

• Deterministic: Same input always produces same output
• Fast: Takes milliseconds even for large inputs
• Uniform: Spreads values evenly across a range
• Avalanche effect: Small changes in input → big changes in output
  • hash("Alice") -> 42
  • hash("alice") -> 8374 (just lowercase 'A' changed everything!)
• Hard to invert and Collisions are rare -> useful in security (eg passwords!)

A Toy Hash Function Example

Here's a simplified hash function to show the concept (real ones are much more sophisticated!):

#![allow(unused)]
fn main() {
fn toy_hash(s: &str) -> i32 {
    let mut hash: i32 = 0;
    for ch in s.chars() {
        hash = hash.wrapping_mul(31).wrapping_add(ch as i32);
    }
    hash 
}

// Examples:
println!("{}", toy_hash("Alice")); 
println!("{}", toy_hash("Bob"));    
println!("{}", toy_hash("alice"));  // (lowercase 'a' changes everything!)
}

Real hash functions (like the ones Rust uses) are much more complex and optimized, but they follow the same principle: turn any input into a number that can be used as an array index!

What does Rust use? Depends on what you're hashing, but if you must know... the default is SipHash 1-3 (have fun going down that rabbit hole!) - it is slower but more secure

From Hash Value to Bucket Index

Important distinction: The hash value is NOT the same as the bucket index! (ie the code isn't the shelf)

Let's say we have a HashMap with 8 buckets:

1. Calculate hash value (can be any i32):
   hash("Alice") = 1,234,567,890

2. Convert to bucket index using modulo:
   bucket_index = 1,234,567,890 % 8 = 2

3. Store in bucket [2]

Why use modulo?

• Hash values can be HUGE (billions)
• We only have a limited number of buckets (e.g., 8, 16, 100)
• Modulo (%) wraps the hash value to fit our bucket array

So here's what HashMap does

• Turns a key into a hash
• Turns a hash into a bucket array index
• Stores the (key, value) pair at the bucket array index

Iterating on a HashMap

Continuing our example:

#![allow(unused)]
fn main() {
use std::collections::HashMap;

let mut prices = HashMap::new();
prices.insert("laptop".to_string(), 999.99);
prices.insert("mouse".to_string(), 25.50);
prices.insert("keyboard".to_string(), 75.00);

// Look at all products and prices
for (product, price) in prices.iter() { // product and price are both &
    println!("{}: ${:.2}", product, price);
}

// Give everything a 10% discount
for (product, price) in prices.iter_mut() { // product is &, price is &mut
    *price = *price * 0.9;
}

// And printing them again
for (product, price) in prices.iter() { // product and price are both &
    println!("{}: ${:.2}", product, price);
}
}

Ownership Interlude: What happens here?

#![allow(unused)]
fn main() {
use std::collections::HashMap;
let product = String::from("smartphone");
let mut prices = HashMap::new();
prices.insert(product, 599.99);
println!("Product: {}", product);  // What happens?
}

Common Pattern: Counting Things

Let's count how many times each word appears in text:

#![allow(unused)]
fn main() {
use std::collections::HashMap;

let text = "the cat sat on the mat";
let mut word_counts = HashMap::new();

for word in text.split_whitespace() {
    let new_count = match word_counts.get(word) {
        Some(x) => x+1,
        None => 1
    };
    word_counts.insert(word.to_string(), new_count);
}

for (word, count) in &word_counts {
    println!("'{}' appears {} times", word, count);
}
}

Alternatively:

#![allow(unused)]
fn main() {
use std::collections::HashMap;

let text = "the cat sat on the mat";
let mut word_counts = HashMap::new();

for word in text.split_whitespace() {
    let count = word_counts.entry(word.to_string()).or_insert(0); // this gives a mutable reference!
    *count += 1;
}

for (word, count) in &word_counts {
    println!("'{}' appears {} times", word, count);
}
}

Take-away: .entry().or_insert() gives you a mutable reference to the value in the key-value pair!

HashSet - the baby sibling of HashMap

The Problem: Duplicate Data

You have customer data but some customers appear multiple times:

#![allow(unused)]
fn main() {
let customers = vec![
    "Alice", "Bob", "Alice", "Carol", "Bob", "Devon", "Alice"
];
}

How many unique customers do we have? (How would you solve this without hashing?)

HashSet: Automatic Uniqueness

(Yep, you've seen this too in a python set)

#![allow(unused)]
fn main() {
use std::collections::HashSet;

let customers = vec!["Alice", "Bob", "Alice", "Carol", "Bob", "David", "Alice"];

// Put all customers in a HashSet - duplicates automatically removed
let unique_customers: HashSet<&str> = customers.iter().cloned().collect();

println!("Original list: {} customers", customers.len());  // 7
println!("Unique customers: {}", unique_customers.len());   // 4

// See who the unique customers are
for customer in &unique_customers {
    println!("Customer: {}", customer);
}
}

Understanding .iter().cloned().collect()

Let's break down what's happening in that HashSet creation:

#![allow(unused)]
fn main() {
let customers = vec!["Alice", "Bob", "Alice"];
let unique: HashSet<&str> = customers.iter().cloned().collect();
}

Step by step:

1. .iter() - Creates an iterator over references to the elements

   • Type: Iterator<Item = &&str> (references to string slices)

2. .cloned() - Makes copies of each reference

   • Takes each &&str and "clones" it to get &str
   • For Copy types like &str, i32, this is cheap (just copies the pointer/value)
   • Type: Iterator<Item = &str>

3. .collect() - Gathers all items into a HashSet

   • Looks at the type annotation (: HashSet<&str>)
   • Creates a HashSet and inserts each &str, automatically removing duplicates
   • Type: HashSet<&str>

Creating HashSets from Different Vec Types

From Vec - Copy types are simple:

use std::collections::HashSet;

fn main(){
    let numbers = vec![1, 2, 3, 2, 4, 1, 5];

    // Option 1: Use .iter().cloned().collect()
    let unique_nums: HashSet<i32> = numbers.iter().cloned().collect();
    println!("{:?}", numbers);  // still valid

    // Option 2: Use .into_iter().collect() (consumes the Vec)
    let unique_nums: HashSet<i32> = numbers.into_iter().collect();
    // println!("{:?}", numbers);  // won't compile

    println!("{:?}", unique_nums);  // {1, 2, 3, 4, 5} (order may vary)
}

Strings work the same way - clone or move ownership

use std::collections::HashSet;

fn main(){
    let names = vec![
        String::from("Alice"),
        String::from("Bob"),
        String::from("Alice")
    ];

    // Option 1: Clone all Strings (original Vec still valid)
    let unique_names: HashSet<String> = names.iter().cloned().collect();
    println!("Original: {:?}", names);  // Still works!
    println!("Unique: {:?}", unique_names);

    // Option 2: Move Strings into HashSet (consumes the Vec)
    let unique_names: HashSet<String> = names.into_iter().collect();
    // println!("{:?}", names);  // ERROR! names was moved
}

Checking if something is in the hashset

#![allow(unused)]
fn main() {
use std::collections::HashSet;

let mut valid_products = HashSet::new();
valid_products.insert("laptop".to_string());
valid_products.insert("mouse".to_string());
valid_products.insert("keyboard".to_string());

// Check if a product is valid
let product_to_check = "tablet";
if valid_products.contains(product_to_check) {
    println!("{} is a valid product", product_to_check);
} else {
    println!("{} is not in our catalog", product_to_check);
}
}

A realistic example

You have 100,000 customer IDs and need to check if 10,000 orders are from valid customers. Which is faster?

#![allow(unused)]
fn main() {
// Option A: Keep customer IDs in a Vec
let customers_vec = vec![/* 100,000 customer IDs */];
for order_id in order_ids {
    if customers_vec.contains(&order_id) {
        // Process valid order
    }
}

// Option B: Keep customer IDs in a HashSet
let customers_set: HashSet<_> = customer_ids.into_iter().collect();
for order_id in order_ids {
    if customers_set.contains(&order_id) {
        // Process valid order
    }
}
}

They look the same - the difference is in how they work

• Vec has to potentially check ALL 100,000 each time to find a match! Up to 100k TIMES 10k operations
• HashSet just hashes each order and checks against the list - only order 10k

Activity 19 - Explain the Anagram Finder

On gradescope you'll find a complete program for finding anagrams. The code is functional (for once!) - your job is to understand it.

You can discuss in groups but each gradescope submission has a cap of 2.

1. Take some time to explain in the in-line commments what each line of code is doing.
2. In the triple /// doc-string comments before each function, explain what the function does overall and what its role is in the program.
3. Consider renaming functions and variables (and if you do, replacing it elsewhere!) to make it clearer what's going on

You can paste this into your IDE/VSCode or Rust Playground - whichever's easier.

Regardless of how far you get, paste your edited code into gradescope by the end of class.

Lecture 20 - Structs and Methods

Logistics

• HW3 was graded - you have until Sunday at midnight (11:59pm Sunday) if you want to do corrections
• Oral exams are today and tomorrow
• HW4 is due Friday (Joey will cover in discussion tomorrow)

Learning Objectives

By the end of today, you should be able to:

• Define custom data types using structs
• Implement methods and associated functions with impl blocks
• Use different types of self parameters (&self, &mut self, self)

The Problem: Organizing Related Data

Imagine you're analyzing customer data. You could use separate variables:

#![allow(unused)]
fn main() {
let customer_name = "Alice Smith";
let customer_age = 25;
let customer_state = State::NY;
let customer_member = true;
}

Problem: Easy to mix up, hard to pass around, no guarantee they belong together!

Solution: Group related data into a custom type called a "struct".

#![allow(unused)]
fn main() {
enum State {
    MA,
    NY,
    // ...
}
struct Customer {
    name: String,
    age: u32,
    state: State,
    member: bool,
}

let alice = Customer {
    name: "Alice".to_string(),
    age: 25,
    state: State::NY,
    member: true,
};
}

Benefit: All related data stays together and has clear names.

Using Your Struct

#![allow(unused)]
fn main() {
#[derive(Debug)]
enum State {
    MA,
    NY,
    // ...
}

#[derive(Debug)]
struct Customer {
    name: String,
    age: u32,
    state: State,
    member: bool,
}

let mut alice = Customer {
    name: "Alice".to_string(),
    age: 25,
    state: State::NY,
    member: true,
};

// Access fields with dot notation
println!("{}'s age is {}", alice.name, alice.age);

// Modify fields (if struct is mutable)
alice.age = 26;
println!("{:?}", alice); // since customer (and State!) have Debug
}

Memory insight: How structs store data

     STACK                     HEAP
┌──────student─────┐           
│ name: ptr  ──────┼──────────► ┌─────────────┐
│       len: 11    │            │"Alice Smith"│
│       cap: 11    │            └─────────────┘
│ age: 20          │
│ state: 0 (NY)    │  ← Just a number representing the variant
│ member: 1 (true) │  ← Just 0 or 1
└──────────────────┘

Tuple structs: When you don't need field names (TC 12:30)

Sometimes you want type safety but don't need named fields:

#![allow(unused)]
fn main() {
#[derive(Debug)]
struct Point3D(f64, f64, f64);
#[derive(Debug)]
struct BoxOfDonuts(i32);

let point = Point3D(3.0, 4.0, 5.0);
let temp = BoxOfDonuts(12);

// Access with .0, .1, .2
println!("X: {}, Y: {}, Z: {}", point.0, point.1, point.2);
}

Benefit: Prevents accidentally mixing up similar data types.

Ownership Interlude: Struct Move Quiz

Question: What happens in this code?

#![allow(unused)]
fn main() {
struct Point { x: f64, y: f64 }
struct NamedPoint { name: String, point: Point }

let p1 = Point { x: 1.0, y: 2.0 };
let np1 = NamedPoint { name: "Origin".to_string(), point: p1 };
let np2 = NamedPoint { name: "Copy".to_string(), point: p1 };
}

A) Compiles fine - Point is copied
B) Compiler error - p1 was moved
C) Runtime panic

Creating similar structs with update syntax

Sometimes you want to create a new struct that's mostly the same as an existing one, but with a few fields changed.

The long way (repetitive!):

#![allow(unused)]
fn main() {
#[derive(Debug)]
enum State {
    MA,
    NY,
    // ...
}
struct Customer {
    name: String,
    age: u32,
    state: State,
    member: bool,
}

let alice = Customer {
    name: "Alice".to_string(),
    age: 25,
    state: State::NY,
    member: true,
};

// Want to create another NY member? Copy all the fields!
let bob = Customer {
    name: "Bob".to_string(),
    age: 30,
    state: State::NY,      // Same as alice
    member: true,          // Same as alice
};
}

The better way (using ..):

#![allow(unused)]
fn main() {
// Create bob with only the fields that differ
let bob = Customer {
    name: "Bob".to_string(),
    age: 30,
    ..alice  // Copy remaining fields (state, member) from alice
};

// Create another NY member
let charlie = Customer {
    name: "Charlie".to_string(),
    age: 28,
    ..alice  // Gets state: NY and member: true from alice
};
// alice is still valid! The copied fields (state, member) are Copy types
}

Important ownership note: The .. syntax will move any non-Copy fields that aren't explicitly specified. In our example, state and member are both Copy types, so alice remains valid. But watch out:

#![allow(unused)]
fn main() {
// A different struct with a non-Copy field at the end
struct Order {
    customer_name: String,
    quantity: u32,
    notes: String,  // Not a Copy type!
}

let order1 = Order {
    customer_name: "Alice".to_string(),
    quantity: 5,
    notes: "Rush delivery".to_string(),
};

let order2 = Order {
    customer_name: "Bob".to_string(),
    ..order1  // This MOVES order1.notes! order1 is now invalid
};

// but this is safe!
let order3 = Order {
    customer_name: "Bob".to_string(),
    ..order1.clone()
};
}

Part 2: Methods - Adding behavior to your data

What Are Methods?

Methods let you add behavior (functions) that belong to your struct:

#![allow(unused)]
fn main() {
struct Rectangle {
    width: f64,
    height: f64,
}

// Instead of separate functions:
fn calculate_area(rect: &Rectangle) -> f64 { ... }
fn calculate_perimeter(rect: &Rectangle) -> f64 { ... }

// You can attach them to the struct:
impl Rectangle {
    fn area(&self) -> f64 { ... }        // Method
    fn perimeter(&self) -> f64 { ... }   // Method
}

// Usage: rect.area() instead of calculate_area(&rect)
}

Benefit: Methods keep related functionality together with the data.

Basic Method Example

#![allow(unused)]
fn main() {
#[derive(Debug)]
struct Rectangle {
    width: f64,
    height: f64,
}

impl Rectangle {
    fn area(&self) -> f64 {
        self.width * self.height
    }
}

let rect = Rectangle { width: 10.0, height: 5.0 };
println!("Area: {}", rect.area());  // Much cleaner than area(&rect)
}

Self?

What is self?

self is a special parameter that refers to the instance of the struct the method is called on.

#![allow(unused)]
fn main() {
let rect = Rectangle { width: 10.0, height: 5.0 };
rect.area();  // When you call area(), "self" inside area() refers to rect
}

Think of it like: "the rectangle that I'm calculating the area of."

Understanding &self (Borrowed Reference)

#![allow(unused)]
fn main() {
#[derive(Debug)]
struct Rectangle {
    width: f64,
    height: f64,
}

impl Rectangle {
    fn area(&self) -> f64 { 
        self.width * self.height
    }
}

let rect = Rectangle { width: 10.0, height: 5.0 };
let a = rect.area();  // rect.area() is like calling area(&rect)
println!("{}", rect.width);  // rect is still usable!
}

Why &self?

• We just need to read the data, not change it
• The rectangle is still usable after the method call
• Most methods use &self - it's the safest default

Understanding &mut self (Mutable Reference)

#![allow(unused)]
fn main() {
#[derive(Debug)]
struct Rectangle {
    width: f64,
    height: f64,
}

impl Rectangle {
    fn scale(&mut self, factor: f64) {  
        self.width *= factor;
        self.height *= factor;
    }
}

let mut rect = Rectangle { width: 10.0, height: 5.0 };
rect.scale(2.0);  // Changes rect's width and height
println!("{}", rect.width);  // Now 20.0 - rect was modified!
}

Why &mut self?

• We need to change the struct's data
• The struct must be declared mut to call these methods
• Use when the method modifies internal state

Passing self itself (taking ownership)

#[derive(Debug)]
struct Rectangle {
    width: f64,
    height: f64,
}

impl Rectangle {
    fn into_area(self) -> f64 {  
        self.width * self.height
        // Rectangle is consumed here!
    }
}

fn main(){
    let rect = Rectangle { width: 10.0, height: 5.0 };
    let a = rect.into_area();
    // println!("{}", rect.width);  // ERROR! rect was moved
}

Why self?

• The method consumes the struct
• Use for conversions or when the struct shouldn't be used again
• Less common - only use when you truly need to consume

Quick Reference

We've seen lots of these before! (dot methods) (TC 12:40)

You've been using methods all semester - now you know what they really are!

#![allow(unused)]
fn main() {
let mut numbers = vec![1, 2, 3];
numbers.push(4);           // What's really happening?
let size = numbers.len();  // What about this?
}

Under the hood, these are methods implemented on the Vec struct:

#![allow(unused)]
fn main() {
impl<T> Vec<T> {
    // push takes &mut self - it needs to modify the vector
    fn push(&mut self, value: T) {
        // ... add value to the vector
    }

    // len takes &self - it just reads the length
    fn len(&self) -> usize {
        // ... return the length
    }

    // new doesn't take self at all - it creates a new Vec
    fn new() -> Vec<T> {
        // ... create empty vector
    }
}
}

Now it makes sense!

• numbers.push(4) calls push(&mut numbers, 4) (needs &mut self to modify)
• numbers.len() calls len(&numbers) (needs &self to read)
• Vec::new() has no instance yet so no self parameter!

More Examples You've Used

The pattern: If a method can be called multiple times on the same value, it uses &self or &mut self. If it can only be called once (like unwrap()), it takes self.

Constructor Functions

You can create your own "constructor" functions like Vec::new to make building structs easier:

#![allow(unused)]
fn main() {
#[derive(Debug)]
struct DataSet {
    name: String,
    values: Vec<f64>,
}

impl DataSet {
    // Constructor - no self parameter, returns new instance
    fn new(name: String) -> DataSet {
        DataSet {
            name, // shorthand for name: name 
            values: Vec::new(),
        }
    }
}

// Much easier than writing out the whole struct:
let dataset = DataSet::new("Experiment".to_string());
}

Enums vs Structs

Remember the temperature problem from homework? Let's redo it with impl (which works for enums too!) and then structs

Approach 1: Enum (what you've seen before)

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, Copy)]
enum Temperature {
    Celsius(f64),
    Fahrenheit(f64),
}

impl Temperature {
    fn to_celsius(&self) -> f64 {
        match self {
            Temperature::Celsius(val) => *val,
            Temperature::Fahrenheit(val) => (val - 32.0) * 5.0 / 9.0,
        }
    }

    fn to_fahrenheit(&self) -> f64 {
        match self {
            Temperature::Celsius(val) => val * 9.0 / 5.0 + 32.0,
            Temperature::Fahrenheit(val) => *val,
        }
    }
}

let temp = Temperature::Celsius(25.0);
println!("{}°F", temp.to_fahrenheit());  // 77°F
}

Key idea: A temperature is either Celsius or Fahrenheit. The enum says "this value IS one of these variants."

Approach 2: Struct (more flexible)

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, Copy)]
enum Scale {
    Celsius,
    Fahrenheit,
}

#[derive(Debug)]
struct Temperature {
    value: f64,
    scale: Scale,
}

impl Temperature {
    fn new(value: f64, scale: Scale) -> Temperature {
        Temperature { value, scale }
    }

    fn to_celsius(&self) -> f64 {
        match self.scale {
            Scale::Celsius => self.value,
            Scale::Fahrenheit => (self.value - 32.0) * 5.0 / 9.0,
        }
    }

    fn to_fahrenheit(&self) -> f64 {
        match self.scale {
            Scale::Celsius => self.value * 9.0 / 5.0 + 32.0,
            Scale::Fahrenheit => self.value,
        }
    }
}

let temp = Temperature::new(25.0, Scale::Celsius);
println!("{}°F", temp.to_fahrenheit());  // 77°F
}

Key idea: A temperature has a value and a scale. The struct groups related data together.

When to Use Each?

Combining Them is Powerful!

Notice in the struct version, we used both:

• Struct (Temperature) to group value and scale together
• Enum (Scale) to represent that scale is one of two alternatives

This is a very common pattern in Rust! Use structs to group related data, and enums inside structs to represent choices.

Pre-activity example: Student grade tracker

#![allow(unused)]
fn main() {
#[derive(Debug)]
struct Student {
    name: String,
    grades: Vec<f64>,
}

impl Student {
    fn new(name: String) -> Student {
        Student {
            name,
            grades: Vec::new(),
        }
    }

    fn add_grade(&mut self, grade: f64) {
        self.grades.push(grade);
    }

    fn average(&self) -> f64 {
        if self.grades.is_empty() {
            0.0
        } else {
            self.grades.iter().sum() / self.grades.len() as f64
        }
    }
}

// Usage
let mut alice = Student::new("Alice".to_string());
alice.add_grade(85.0);
alice.add_grade(92.0);
println!("{}'s average: {:.1}", alice.name, alice.average());
}

Activity time

In groups of 5-6, you'll design a struct-based system for a real-world scenario.

Focus on:

• What fields belong in your structs
• What enums represent choices in your domain
• What methods you need and what type of self parameter each uses
• How structs and enums work together

Write as much proper code as you can

• Use enum, struct, and impl
• Use self, &self and &mut self in your method signatures
• But feel free to leave the inside of each method unimplemented()

Be ready to present:

• Choose one person who will come to the front to explain your design
• We'll go by task, so we'll hear two approaches to each problem

Lecture 21 - Pattern Matching and Review

Logistics

• HW4 due Friday night
• HW3 corrections due Sunday night
• Feedback on pre-task value: mixed
• After oral exams and corrections, 25/50/75 %iles: 86%, 92%, 95%
• Our next midterm is in 2 weeks
• Changes to corrections procedure for midterm 2

Presenting Struct Design from Monday

See PDFs - 10 min

Learning Objectives

By the end of today, you should be able to:

• Use pattern matching to extract data from structs and enums
• Apply simple pattern guards for conditional matching
• Review ownership concepts from L14-L20

Part 1 - Pattern Matching with Structs

Getting data out of enums and structs

The same match statements we saw for enums works for structs:

#![allow(unused)]
fn main() {
#[derive(Debug)]
struct Book {
    title: String,
    year: u32,
    rating: f64,
    genre: Genre,
}

enum Genre {
    Fiction,
    NonFiction,
    Mystery,
    SciFi,
}

// Extract data from enums
fn describe_genre(genre: &Genre) -> &str {
    match genre {
        Genre::Fiction => "Literary fiction",
        Genre::NonFiction => "Factual content",
        Genre::Mystery => "Mystery and suspense",
        Genre::SciFi => "Science fiction",
    }
}

// Extract data from structs
fn get_rating(book: &Book) -> f64 {
    match book {
        Book { rating, .. }  => *rating,
    }
}

fn check_highly_rated(book: &Book) -> bool {
    match book {
        Book { rating, .. } if *rating >= 4.5 => true,
        _ => false,
    }
}
}

Pattern Guards for Complex Conditions

#![allow(unused)]
fn main() {
#[derive(Debug)]
struct Book {
    title: String,
    rating: f64,
    pages: u32,
}
}

#![allow(unused)]
fn main() {
fn classify_book(book: &Book) -> &'static str {
    match book {
        Book { rating, pages, .. } if rating >= 4.5 && pages >= 400 => {
            "Epic Bestseller"
        }
        Book { rating, pages, .. } if rating >= 4.5 => {
            "Highly Rated"
        }
        Book { pages, .. } if pages >= 600 => "Epic",
        Book { pages, .. } if pages >= 300 => "Standard Novel",
        Book { rating, .. } if rating < 2.0 => "Needs Review",
        _ => "Short Read",
    }
}
}

Destructuring in Let Bindings

#[derive(Debug)]
struct DataPoint {
    x: f64,
    y: f64,
    label: String,
    confidence: f64,
}

let point1 = DataPoint {
    x: 1.5, y: 2.3,
    label: "Positive".to_string(),
    confidence: 0.95,
};

let point2 = DataPoint {
    x: 5.0, y: -1.1,
    label: "Negative".to_string(),
    confidence: 0.70,
};

#![allow(unused)]
fn main() {
// Destructure in let binding
let DataPoint { x, y, label, confidence } = point1;
println!("({}, {}) - {} ({:.1}%)", x, y, label, confidence * 100.0);

// Partial destructuring
let DataPoint { label, confidence, .. } = point2;  // Ignore x, y
println!("We only learned: {} ({:.1}%)", label, confidence * 100.0);

// In function parameters
fn print_coords(DataPoint { x, y, .. }: &DataPoint) {
    println!("Point at ({:.2}, {:.2})", x, y);
}
}

Ownership Interlude: Destructuring Moves Quiz

Question: After this destructuring, what can we still use?

#![allow(unused)]
fn main() {
let point = DataPoint {
    x: 1.0, y: 2.0,
    label: "test".to_string(),
    confidence: 0.9,
};

let DataPoint { x, label, .. } = point;
}

What's still usable: point, point.x, point.y, point.label, point.confidence?

Part 2: Review of L14-L20

Stack vs. Heap (Lecture 14)

• Stack: Fast, fixed-size, automatic cleanup (LIFO - "stack of plates")
  • Each function call gets a stack frame
  • Stores simple types: i32, bool, char, arrays, tuples
  • Variables cleaned up when function ends
• Heap: Flexible size, manual management (Rust helps!)
  • For data that can grow/shrink or are very large
  • Types like String, Vec, HashMap, Box store data here
  • Stack holds pointers to heap data
• Memory addresses: Every location has a unique address to a physical part of RAM (like 0x7fff5fbff6bc)

Ownership Rules (Lecture 15)

The three fundamental ownership rules:

1. Each value has an owner
2. Only one owner at a time
3. When owner goes out of scope, value is dropped

Key concepts:

• Move semantics: let s2 = s1; moves ownership for heap types (String, Vec)
• Copy semantics: let y = x; copies value for stack types (i32, bool)
• Clone: .clone() creates explicit copy of heap data (and copies stack data)
• Function calls: Passing to function moves or copies (same rules)
• Return values: Transfer ownership back to caller

Borrowing and References (Lecture 16)

• Creating references: & operator borrows without taking ownership
  • let data_ref = &data; - both data and data_ref usable
• Functions with references: fn process(data: &Vec<i32>) - can use data without moving it
• Dereferencing: * operator accesses value through reference
  • *x_ref > *y_ref to compare values, and for use in match
  • Often auto-dereferenced (eg println! and arithmetic)
• Pattern matching: for &num in numbers.iter() extracts values (Copy types only)

Mutable References (Lecture 17)

Borrowing rules (the borrow checker):

• Rule 1: Many immutable references OR one mutable reference (not both!)
• Rule 2: References must not outlive what they point to

Mutable references (&mut T):

• fn modify(data: &mut Vec<i32>) - can change borrowed data
• Must declare variable as mut to create mutable reference
• Can't have other references (mutable or immutable) at same time
• Use * to modify through reference: *x = 10;

Reference timing:

• Rust tracks when references are last used
• Can create new references after previous ones stop being used

Strings and Slices (Lecture 18)

• String types:
  • String: Owned, growable string on heap
  • &str: String slice - reference to string data (points to the heap)
    • string literals point to the binary itself
    • string slices built on owned strings point to the heap
    • they have the same type/structure (a "fat pointer")
  • &String: Reference to a String (points to the stack)

Slices:

• Syntax: &data[start..end], &data[..3], &data[2..]
• &[T]: Slice of array/Vec elements (pointer + length)
• Slices are references - don't take ownership

UTF-8 encoding:

• Characters can be 1-4 bytes
• .len() returns bytes, not character count
• Use .chars() to iterate over characters
• No text[0] indexing - would fail to compile

Iterators:

• .iter(): Generates immutable references &T
• .iter_mut(): Generates mutable references &mut T
• .iter().enumerate(): Generates pairs (i32, &T)
• .iter_mut().enumerate(): Generates pairs (i32, &mut T)
• .collect(): Collapse iterators into target type

HashMap and HashSet (Lecture 19)

Hash functions:

• Convert any input to a number (deterministic, fast, uniform distribution)
• Used to determine bucket index: hash % capacity

HashMap<K, V>:

• Hashes the key to get a hash value
• Creates a bucket array that stores hash values and pointers to (key, value) pairs
• Create: HashMap::new() or collect from iterator
• Insert: .insert(key, value) - overwrites if key exists
• Get: .get(&key) returns Option<&V>
• Check: .contains_key(&key) returns bool
• Iterate: for (key, value) in map.iter()
• Pattern: .entry(key).or_insert(value) for counting/defaults

HashSet:

• Stores unique values (no duplicates)
• .insert(value), .contains(&value)
• Create from Vec: vec.iter().cloned().collect()
• Fast membership testing (better than Vec for large data)

Structs and Methods (Lecture 20)

Defining structs:

#![allow(unused)]
fn main() {
struct Customer {
    name: String,
    age: u32,
    member: bool,
}
}

• Group related data together
• Access fields with dot notation: customer.name
• Tuple structs: struct Point(f64, f64, f64);
• Update syntax: Customer { name: "Bob".to_string(), ..alice }

Methods (impl blocks):

#![allow(unused)]
fn main() {
impl Customer {
    fn new(name: String) -> Customer { ... }  // Constructor
    fn display(&self) { ... }                 // Read-only
    fn update_age(&mut self, age: u32) { ... } // Modify
    fn into_name(self) -> String { ... }      // Consume
}
}

Some function signature best practices

#![allow(unused)]
fn main() {
// ❌ BAD: Unnecessary ownership transfer
fn bad_process(key: String, value: f64) -> f64 {
    value * 2.0  // Doesn't need to own `key`!
}

// ✅ GOOD: Flexible parameter
fn good_process(key: &str, value: f64) -> f64 {
    value * 2.0  // Accepts both String and &str
}

// ❌ BAD: Dangerous unwrap
fn bad_lookup(map: &HashMap<String, i32>, key: &str) -> i32 {
    map.get(key).unwrap()  // Panics if key missing!
}

// ✅ GOOD: Safe Option handling
fn good_lookup(map: &HashMap<String, i32>, key: &str) -> Option<i32> {
    map.get(key).copied()  // Returns Option for safety
}
}

Debug Quiz

Question: What's wrong with this code?

#![allow(unused)]
fn main() {
fn get_first_line(text: String) -> &str {
    let lines: Vec<&str> = text.lines().collect();
    if lines.is_empty() {
        ""
    } else {
        lines[0]
    }
}
}

A) Should return Option<&str> for safety
B) Can't return reference to text which goes out of scope
C) collect() is unnecessary here

A few common ownership issues

#![allow(unused)]
fn main() {
#[derive(Debug, Clone)]
struct Data { value: i32, label: String }

// Issue 1: Unnecessary ownership
fn process_label(label: String) -> String {  // Should be &str?
    label.to_uppercase()
}

// Issue 2: Lifetime problem
fn get_first_item(items: Vec<String>) -> &String {  // ERROR - Can't return ref to owned data!
    &items[0]
}

// Issue 3: Move in loop
fn analyze_data(data_list: Vec<Data>) {
    for data in data_list {  // Moves each Data
        println!("{:?}", data);
    }
    println!("Count: {}", data_list.len());  // ERROR - data_list moved!
}

// Issue 4: Borrowing conflict
fn modify_and_read(items: &mut Vec<i32>) {
    let first = &items[0];  // Immutable borrow
    items.push(42);         // ERROR - Mutable borrow while immutable exists!
    println!("First: {}", first);
}
}

Lecture 22 - Generics and Type Systems

Logistics

• HW4 due tonight (new policy doesn't apply)
• New HW policy for HW5-7 (see Piazza after class)

Take-aways from "comfort-check" quiz

Most comfortable:

• Stack and heap memory
• What .clone() does
• .iter() vs .iter_mut()
• &self, &mut self, self

High variance:

• Ownership and borrow-checker rules
• Why you can't do text[0] on a String
• Modifying a Vec when using .iter()

Least comfortable:

• What .collect() does
• .entry().or_insert() for hashmaps
• .get() on hashmaps returning an Option
• Tuple structs

Learning Objectives (TC 12:25)

By the end of today, you should be able to:

• Write generic functions and structs using type parameters
• Use trait bounds to constrain generic behavior
• Recognize when you've been using generics all along

The Problem with Type-Specific Functions

Python is dynamically typed and quite flexible. We can pass many different types to a function:

def max(x, y):
    return x if x > y else y

>>> max(3, 2)
3
>>> max(3.1, 2.2)
3.1
>>> max('s', 't')
't'

Very flexible! Any downsides?

• Requires inferring types each time function is called
• Incurs runtime penalty
• No compile-time guarantees about type safety

Type system approaches (review)

Dynamic Typing (Python, JavaScript, Ruby, R):

• Types checked at runtime
• Flexible coding
• Prone to runtime errors

Static Typing (C/C++, Java, Rust, Go):

• Types checked at compile-time
• Fast execution
• Early error detection

Rust without generics

Rust is strongly typed, so we would have to create a version of the function for each type:

#![allow(unused)]
fn main() {
fn max_i32(x: i32, y: i32) -> i32 {
    if x > y { x } else { y }
}

fn max_f64(x: f64, y: f64) -> f64 {
    if x > y { x } else { y }
}

fn max_char(x: char, y: char) -> char {
    if x > y { x } else { y }
}
// ... etc., etc.
}

Problem: Supporting N types = writing N functions!

fn main() {
    println!("{}", max_i32(3, 8));      // 8
    println!("{}", max_f64(3.3, 8.1));  // 8.1
    println!("{}", max_char('a', 'b')); // b
}

The dilemma: Python's flexibility with runtime costs vs. Rust's safety with code duplication?

Solution: Generics give us both flexibility AND compile-time guarantees!

Compiling generic functions (Monomorphization)

Insight: Generics = compile-time code generation for zero runtime cost!

     SOURCE CODE                    COMPILED OUTPUT
┌─ fn max<T>(x: T, y: T) ─┐       ┌ Specialized Functions ─┐
│   where T: PartialOrd   │  ───► │ fn max_i32(x: i32, ...)│
│ {                       │       │ fn max_f64(x: f64, ...)│
│   if x > y { x } else{y}│       │ fn max_char(x: char,..)│
│ }                       │       └────────────────────────┘
└─────────────────────────┘            Monomorphization

A Simple Generic Example (TC 12:30)

Let's try writing a super simple generic function. Use the <T> syntax to indicate that the function is generic:

#![allow(unused)]
fn main() {
fn passit<T>(x: T) -> T {
    x
}
}

The T is a placeholder for the type (could be any letter, but T for "Type" is conventional).

#![allow(unused)]
fn main() {
fn passit<T>(x: T) -> T {
    x
}

let x = passit(5);
println!("x is {}", x);      // x is 5

let x = passit(1.1);
println!("x is {}", x);      // x is 1.1

let x = passit('s');
println!("x is {}", x);      // x is s
}

This works! The function just passes through whatever type it receives.

Okay but that was pretty boring...

Let's try writing a generic max function.

#![allow(unused)]
fn main() {
fn max<T>(x: T, y: T) -> T {
    if x > y { x } else { y }  
}
}

... but wait, there's a compiler error!

Problem: Not all types support > comparison!

The Rust compiler is thorough enough to recognize that not all generic types may have the behavior we want.

Solution: Trait bounds specify required behavior.

Trait Bounds: Constraining Generic Types

So how can we make our max function? We need to add a trait bound to specify that T must support comparison:

use std::cmp::PartialOrd;

fn max<T: PartialOrd>(x: T, y: T) -> T {
    if x > y { x } else { y }  // Now it works!
}

fn main() {
    // Type inference determines T:
    println!("{}", max(5, 10));     // T = i32
    println!("{}", max(3.14, 2.7)); // T = f64
    println!("{}", max('a', 'b'));  // T = char
    let i = num::complex::Complex::new(10, 20);
    let j = num::complex::Complex::new(20, 5);
    // println!("{:?}", max(i, j));  // Won't compile if T doesn't implement PartialOrd
}

Key insight: T: PartialOrd = "T must support comparison operations"

We can place restrictions on the generic types we would support.

Quick note on use std::cmp::PartialOrd;

PartialOrd needed to be imported from std::cmp::PartialOrd

(We didn't have to do this for things like #[derive(PartialOrd)] because those were macros!)

Other imports we might need:

#![allow(unused)]
fn main() {
use std::fmt::{Debug, Display};
use std::cmp::{PartialOrd, Eq, Ord};
use std::ops::{Add, Sub, Mul, Div};
}

Some traits like Copy, Clone, PartialEq are in the prelude (automatically imported), but others need explicit imports.

Monomorphization in Action (TC 12:35)

// What you write:
fn max<T: PartialOrd>(x: T, y: T) -> T {
    if x > y { x } else { y }
}

fn main() {
    println!("{}", max(5, 10));    
    println!("{}", max(3.14, 2.7));
}

// What the compiler generates (conceptually):
fn max_i32(x: i32, y: i32) -> i32 {
    if x > y { x } else { y }
}

fn max_f64(x: f64, y: f64) -> f64 {
    if x > y { x } else { y }
}

fn main() {
    println!("{}", max_i32(5, 10));    
    println!("{}", max_f64(3.14, 2.7));
}

Generic Structs

#![allow(unused)]
fn main() {
#[derive(Debug)]
struct Point<T> {
    x: T,
    y: T,
}

// Type inference at work:
let int_point = Point { x: 5, y: 10 };     // Point<i32>
let float_point = Point { x: 3.14, y: 2.7 }; // Point<f64>
}

Generic Struct Memory Layout

     STACK
┌─ Point<i32> ───┐
│ x: 5  [4 bytes]│
│ y: 10 [4 bytes]│
└────────────────┘
   8 bytes total

┌─ Point<f64> ─────┐
│ x: 3.14 [8 bytes]│
│ y: 2.7  [8 bytes]│
└──────────────────┘
   16 bytes total

Memory insight: Generic structs adapt their size to the contained types!

Methods on Generic Structs

#![allow(unused)]
fn main() {
#[derive(Debug)]
struct Point<T> {
    x: T,
    y: T,
}

impl<T> Point<T> {
    fn new(x: T, y: T) -> Point<T> {
        Point { x, y }
    }
    fn get_x(&self) -> &T {
        &self.x
    }
}

// Works for any type:
let point1 = Point::new(1, 2);      // Point<i32>
let point2 = Point::new(1.5, 2.5);  // Point<f64>
println!("{}", point1.get_x());
println!("{}", point2.get_x());
}

Trait Bounds on Methods (TC 12:40)

Sometimes a method only works for certain types. Let's implement a swap method:

#![allow(unused)]
fn main() {
#[derive(Debug)]
struct Point<T> {
    x: T,
    y: T,
}
// This won't compile!
impl<T> Point<T> {
    fn new(x: T, y: T) -> Point<T> {
        Point { x, y }
    }
    fn swap(&mut self) {
        let temp = self.x;   // Might not be Copy!
        self.x = self.y;
        self.y = temp;
    }
}
}

Problem: We're trying to move self.x out, but T might not implement Copy! (Compiler error gives a different helpful suggestion to add Clone)

Solution: Add a trait bound to the impl block:

#![allow(unused)]
fn main() {
#[derive(Debug)]
struct Point<T> {
    x: T,
    y: T,
}

// Only implement swap for types that are Copy
impl<T> Point<T> {
    fn new(x: T, y: T) -> Point<T> {
        Point { x, y }
    }
}

impl<T: Copy> Point<T> {
    fn swap(&mut self) {
        let temp = self.x;  // OK - T implements Copy
        self.x = self.y;
        self.y = temp;
    }
}

let mut point = Point::new(2, 3);
println!("{:?}", point);  // Point { x: 2, y: 3 }
point.swap();
println!("{:?}", point);  // Point { x: 3, y: 2 }
}

Key insight: impl<T: Copy> means "this implementation only exists for types that implement Copy"

Common Traits and Bounds (TC 12:45)

#![allow(unused)]
fn main() {
use std::fmt::Debug;  // Need to import Debug!

// Debug: Check if it can be printed with {:?}
fn debug_value<T: Debug>(val: T) {
    println!("Value: {:?}", val);
}

// Clone: Check if it can be duplicated with .clone()
fn duplicate<T: Clone>(val: &T) -> T {
    val.clone()
}

// Copy: Check if it is automatically copied (no moves)
fn safe_copy<T: Copy>(val: T) -> (T, T) {
    (val, val)  // val still usable!
}
}

Built-in Generic Types (You Know These!)

Remember these from earlier in the semester?

#![allow(unused)]
fn main() {
// Option<T> - maybe has a value
let maybe_number: Option<i32> = Some(42);

// Result<T, E> - success or error
let outcome: Result<i32, String> = Ok(42);

// Vec<T> - growable array
let numbers: Vec<i32> = vec![1, 2, 3];

// Box<T> - heap-allocated value
let boxed_data: Box<i32> = Box::new(5);
}

Now you understand what the <T> means!

These are all generic types that work with any type T.

When you wrote Option<i32>, you were using a generic enum specialized for i32.

When you wrote Result<f64, String>, you were using a generic enum specialized for returning f64 on success and String on error

Ownership Interlude: Trait Bounds Quiz

Question: Explain this function signature / why it's a "safe" max

#![allow(unused)]
fn main() {
use std::cmp::PartialOrd;

fn safe_max<T: PartialOrd + Clone>(x: &T, y: &T) -> T {
    if x > y { x.clone() } else { y.clone() }
}
}

Answer: We take &T parameters to avoid moving the arguments, but need Clone to return an owned T. PartialOrd enables the comparison operation!

Generic vs. Type-Specific Implementations (TC 12:50)

Even though we have generic methods defined, we can still specify methods for specific types!

#[derive(Debug)]
struct Point<T> {
    x: T,
    y: T,
}

// Generic implementation - works for any type T
impl<T> Point<T> {
    fn new(x: T, y: T) -> Point<T> {
        Point { x, y }
    }
}

// Specialized implementation - ONLY for Point<i32>
impl Point<i32> {
    fn distance_from_origin(&self) -> f64 {
        ((self.x.pow(2) + self.y.pow(2)) as f64).sqrt()
    }
}

// Specialized implementation - ONLY for Point<f64>
impl Point<f64> {
    fn distance_from_origin(&self) -> f64 {
        (self.x.powi(2) + self.y.powi(2)).sqrt()
    }
}

fn main(){
    let int_point = Point::new(3, 4);
    println!("Distance: {}", int_point.distance_from_origin()); // 5.0

    let float_point = Point::new(3.0, 4.0);
    println!("Distance: {}", float_point.distance_from_origin()); // 5.0

    // let char_point = Point::new('a', 'b');
    // char_point.distance_from_origin(); // Error! No such method for Point<char>
}

Why Use Specialized Implementations?

• Different algorithms work better for different types (ints, floats)
• Some methods only make sense for certain types
• Sometimes you want drastically different behavior (eg are_you_a_float)

Readable bounds using where

#![allow(unused)]
fn main() {
use std::cmp::PartialOrd;
use std::fmt::Debug;

fn analyze_data<T>(values: &[T]) -> Option<T>
where
    T: PartialOrd + Clone + Debug
{
    values.iter().max().cloned()
}
}

This is the same as:

#![allow(unused)]
fn main() {
fn analyze_data<T: PartialOrd + Clone + Debug>(values: &[T]) -> Option<T> {
    values.iter().max().cloned()
}
}

Use where when you have multiple bounds - it's more readable!

"Polymorphism" and "Monomorphization"

We say max is polymorphic and the compiled functions are monomorphic. The process of going from one to the other is monomorphization.

  GENERIC SOURCE                 COMPILER OUTPUT (roughly)
┌─────────────────┐            ┌─────────────────┐
│ fn max<T>(x, y) │  ────────► │ fn max_i32(...) │
│ where T: Ord    │            │ fn max_f64(...) │
│ { ... }         │            │ fn max_char(...)│
└─────────────────┘            └─────────────────┘
     One source                 Multiple functions

What we mean by "zero cost polymorphism"

The compiler generates specialized functions for each type you use.

#![allow(unused)]
fn main() {
max(5, 10);     // Compiles to direct i32 comparison (as fast as hand-written max_i32)
max(3.14, 2.7); // Compiles to direct f64 comparison (as fast as hand-written max_f64)
}

"Zero cost" means:

• No runtime type checking ("is this an i32 or f64?")
• No performance penalty compared to writing separate functions by hand

This is different from languages like Java (type erasure adds overhead) or Python (dynamic dispatch at runtime).

Activity time

See Gradescope and our B1 website (linked on Piazza) for Activity 22 instructions

Lecture 23 - Traits

Logistics

• HW5-7 opt in emails due tonight if you're interested
• I moved a couple topics around for next week (you probably won't notice unless you're reading far ahead)

Learning Objectives

By the end of today, you should be able to:

• Define and implement traits for custom types
• Understand what #[derive(...)] really does
• More on trait bounds for writing flexible functions
• Recognize more traits you've been using all along (Debug, Clone, PartialEq)

The Problem: Code Duplication Across Types

Let's say we want to print information about different types:

#![allow(unused)]
fn main() {
struct SoccerPlayer {
    name: String,
    age: u32,
    team: String,
}

struct Dataset {
    name: String,
    rows: usize,
    columns: usize,
}
}

#![allow(unused)]
fn main() {
// Without traits, we need separate functions:
fn describe_player(p: &SoccerPlayer) {
    println!("{}, age {}, plays for {}", p.name, p.age, p.team);
}

fn describe_dataset(d: &Dataset) {
    println!("{}: {} rows × {} columns", d.name, d.rows, d.columns);
}
}

Problem: We're duplicating the pattern of "describe this thing" for each type!

Solution: Traits let us define shared behavior across different types.

What Are Traits?

A trait defines shared behavior - a set of methods that types can implement. Let's define a custom trait for the behavior we want:

#![allow(unused)]
fn main() {
trait Describable {
    fn describe(&self) -> String;
}
}

This says: "Any type that implements Describable must provide a describe method that takes an immutable self reference and returns a String."

Now we can implement this trait for our types:

#![allow(unused)]
fn main() {
impl Describable for SoccerPlayer {
    fn describe(&self) -> String {
        format!("{}, age {}, plays for {}", self.name, self.age, self.team)
    }
}

impl Describable for Dataset {
    fn describe(&self) -> String {
        format!("{}: {} rows × {} columns", self.name, self.rows, self.columns)
    }
}
}

From other languages: Similar to interfaces in Java or protocols in Swift

Using traits in function parameters

Now we can write one function that works with any type that implements Describable:

#![allow(unused)]
fn main() {
fn print_description(item: &impl Describable) {
    println!("{}", item.describe());
}

// Works with both types!
let player = SoccerPlayer {
    name: "Messi".to_string(),
    age: 36,
    team: "Inter Miami".to_string()
};
let data = Dataset {
    name: "iris".to_string(),
    rows: 150,
    columns: 4
};

print_description(&player);  // Messi, age 36, plays for Inter Miami
print_description(&data);    // iris: 150 rows × 4 columns
}

Key insight: The function doesn't care about the specific type, only that it can be described!

Didn't we do this last time kinda?

The &impl Describable syntax is shorthand for what you saw last lecture. Here's the equivalent using generics:

#![allow(unused)]
fn main() {
// Short form (what we just saw)
fn print_description(item: &impl Describable) {
    println!("{}", item.describe());
}

// Long form (using generic type parameter)
fn print_description<T: Describable>(item: &T) {
    println!("{}", item.describe());
}
}

Both do exactly the same thing! They both say: "accepts a reference to any type T that implements Describable"

When to use which?

• &impl Trait - simpler, good for single parameters
• <T: Trait> - better when you need multiple parameters of the same type or have complex, multi-trait criteria

#![allow(unused)]
fn main() {
// This ensures both parameters are the SAME type
fn compare<T: Describable>(item1: &T, item2: &T) {
    println!("{}", item1.describe());
    println!("{}", item2.describe());
}
}

A More Complete Example: The Person Trait (TC 12:30)

Let's define a trait with multiple methods:

#![allow(unused)]
fn main() {
trait Person {
    // Required methods - must be implemented
    fn get_name(&self) -> String;
    fn get_age(&self) -> u32;

    // Default method - can be overridden
    fn description(&self) -> String {
        format!("{} ({})", self.get_name(), self.get_age())
    }
}
}

New feature: Default implementations! Types get this method for free unless they override it.

Implementing Person for SoccerPlayer

#![allow(unused)]
fn main() {
struct SoccerPlayer {
    name: String,
    age: u32,
    team: String,
}

impl Person for SoccerPlayer {
    fn get_name(&self) -> String {
        self.name.clone()
    }
    fn get_age(&self) -> u32 {
        self.age
    }
    // We get description() for free from the default!
}
}

#![allow(unused)]
fn main() {
let messi = SoccerPlayer {
    name: "Lionel Messi".to_string(),
    age: 36,
    team: "Inter Miami".to_string(),
};

println!("{}", messi.description());  // Lionel Messi (36)
}

Implementing Person for Another Type

#![allow(unused)]
fn main() {
struct Student {
    first_name: String,
    last_name: String,
    year_born: u32,
}

impl Person for Student {
    fn get_name(&self) -> String {
        format!("{} {}", self.first_name, self.last_name)
    }

    fn get_age(&self) -> u32 {
        2024 - self.year_born
    }

    // Again, description() comes for free!
}

let student = Student {
    first_name: "Alice".to_string(),
    last_name: "Chen".to_string(),
    year_born: 2003,
};

println!("{}", student.description());  // Alice Chen (21)
}

Using Traits in Functions

#![allow(unused)]
fn main() {
fn greet(person: &impl Person) {
    println!("Hello, {}! I see you're {} years old.",
             person.get_name(), person.get_age());
}

greet(&messi);    // Hello, Lionel Messi! I see you're 36 years old.
greet(&student);  // Hello, Alice Chen! I see you're 21 years old.
}

Alternative syntax (same meaning):

#![allow(unused)]
fn main() {
fn greet<T: Person>(person: &T) {
    println!("Hello, {}!", person.get_name());
}
}

Both mean: "This function works with any type T that implements Person"

Trait Extension: Building on Other Traits

Sometimes you want one trait to require another trait. This is called trait extension or supertraits.

#![allow(unused)]
fn main() {
// Employee extends Person - any Employee must also be a Person!
trait Employee: Person {
    fn employee_id(&self) -> u32;
    fn department(&self) -> String;

    // Can use Person methods in default implementations
    fn badge_name(&self) -> String {
        format!("{} - #{}", self.get_name(), self.employee_id())
    }
}
}

Syntax: Employee: Person means "to implement Employee, you must also implement Person"

Implementing Extended Traits

#![allow(unused)]
fn main() {
struct Engineer {
    first_name: String,
    last_name: String,
    age: u32,
    emp_id: u32,
}

// First, implement the base trait (Person)
impl Person for Engineer {
    fn get_name(&self) -> String {
        format!("{} {}", self.first_name, self.last_name)
    }

    fn get_age(&self) -> u32 {
        self.age
    }
}

// Then, implement the extended trait (Employee)
impl Employee for Engineer {
    fn employee_id(&self) -> u32 {
        self.emp_id
    }

    fn department(&self) -> String {
        "Engineering".to_string()
    }
    // badge_name() uses the default implementation
}
}

The Debug Trait

Debug is a trait that enables printing with {:?}:

#![allow(unused)]
fn main() {
trait Debug {
    fn fmt(&self, f: &mut Formatter) -> Result;
}
}

When you write #[derive(Debug)], Rust automatically implements this trait for you!

Manually implementing Debug (you usually don't need to):

#![allow(unused)]
fn main() {
use std::fmt;

enum Direction {
    North, South, East, West,
}

impl fmt::Debug for Direction {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            Direction::North => write!(f, "North"),
            Direction::South => write!(f, "South"),
            Direction::East => write!(f, "East"),
            Direction::West => write!(f, "West"),
        }
    }
}

let dir = Direction::North;
println!("{:?}", dir);  // North
}

Takeaway: #[derive(Debug)] automatically generates this code for you!

The Display Trait

Display is like Debug, but for user-friendly output with {}:

#![allow(unused)]
fn main() {
use std::fmt;

impl fmt::Display for Direction {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            Direction::North => write!(f, "→ Going North"),
            Direction::South => write!(f, "↓ Going South"),
            Direction::East => write!(f, "→ Going East"),
            Direction::West => write!(f, "← Going West"),
        }
    }
}

let dir = Direction::North;
println!("{}", dir);   // Going North
println!("{:?}", dir); // North
}

Debug vs Display:

• Debug ({:?}): For developers/debugging - can be derived
• Display ({}): For end users - must be manually implemented

The Clone and PartialEq Traits

Clone: Enables explicit duplication with .clone()

#![allow(unused)]
fn main() {
trait Clone {
    fn clone(&self) -> Self;
}
}

When you derive it: let copy = original.clone(); works!

PartialEq: Enables comparison with == and !=

#![allow(unused)]
fn main() {
trait PartialEq {
    fn eq(&self, other: &Self) -> bool;
}
}

When you derive it: if point1 == point2 { ... } works!

#![allow(unused)]
fn main() {
#[derive(Clone, PartialEq)]
enum Status {
    Active,
    Inactive,
}

let s1 = Status::Active;
let s2 = s1.clone();           // Clone trait
if s1 == s2 {                  // PartialEq trait
    println!("Same status!");
}
}

So what Does #[derive(...)] Actually Do?

#[derive(...)] is a macro that auto-generates trait implementations.

#![allow(unused)]
fn main() {
// What you write:
#[derive(Debug, Clone, PartialEq)]
struct Point {
    x: i32,
    y: i32,
}

// What Rust generates (conceptually):
impl Debug for Point { /* ... */ }
impl Clone for Point { /* ... */ }
impl PartialEq for Point { /* ... */ }
}

Our common derivable traits:

• Debug - debug printing with {:?}
• Clone - explicit copying with .clone()
• Copy - implicit copying (for simple types)
• PartialEq - equality comparison with ==
• Eq - full equality (rare, requires PartialEq)
• PartialOrd - ordering with <, >, etc.
• Ord - total ordering (rare, requires PartialOrd)