2024-04-01 - Week 01 - Morning

Back to Software Construction, Spring '24

Link to 2024-04-01 Afternoon

What is software construction?

Software construction is the central part of software engineering that deals with coding and debugging large programs in a structured way.

Large means from a few thousand to hundreds of thousands or million lines of code. In this class, you will probably be writing or changing up to one thousand lines of code individually, and contributing to the One Class Project which may be tens of thousands of lines of code.

Structured means the code will follow a specification, either formal or informal, communicated and agreed upon by multiple people (your teammates and classmates), and used to define and enforce the interfaces between different parts of our code. But there we go italicizing yet another term that we have to define!

We will be introducing a lot of terms in this class, some that have everyday meanings, but we will use them in a very specific way that practitioners and software craftspeople use in the industry to build effective, robust, and flexible code, from small prototypes up to the truly monumental pieces of software that power our world.

It may seem like a hazy cloud of words at first, or learning a foreign language.

Similarly, when you first walk into a woodworking shop or makerspace, you may see a lot of unfamiliar tools and not know what they are for, or even what to call them to ask a question. This is a normal experience, and when taken one-at-a-time, we'll learn and build confidence as we work our way through the "shop" of software construction.

Over time, we'll make the meanings of these words precise as we practice using the tools themselves. You'll be given lots of examples and practice in both constructing software and communicating with your fellow engineers-in-training.

The surrounding competencies, practices, and sub-disciplines that surround software construction to make up software engineering include

• requirements engineering: how to communicate with your community to know what to build
• design: how to make a plan and divide up your project into smaller parts, and possibly sub-parts and sub-sub-parts s needed
• specification: how to make precise what it means for your project to achieve its goals
• refactoring: how to refine, enhance, shorten, simplify, or otherwise improve your code while maintaining existing functionality
• testing: how to verify that your project meets your specifications and doesn't regress while refactoring
• maintenance: tracking bugs or ways your project can improve, monitoring its performance, and its lifetime after being released
  • this is an important topic, but we will not cover it in this course.

Over the course of the 10 weeks of this class, in this track we'll practice three sub-tracks.

• git version control
• programming in Rust with the rustlings exercise

In the mornings we'll introduce, discuss as a class, and take notes away from a computer to think about all three. You are asked to take notes in a notebook with pen, or a tablet is next best with a stylus or your finger. A notebook is recommended so that you don't have loose sheets of paper scattered in multiple locations that are hard to find. The Evergreen Bookstore sells a nice selection; nothing fancy is required.

The act of writing slows down your focus and helps you absorb material as it moves from your eyes, through your brain, and to your fingertips.

In the afternoon, in lab we'll apply what we've thought about and do hands-on practice in the lab. From there, you'll read your notes and again the material will move from your eyes, through your brain where you'll recall what we talked about this morning, and again to your fingertips as you type this material on a computer.

Both phases are necessary and important. Without the thinking phase, we tend to get caught in a "guess-and-check" mode of working which is very short-term and reactive. Without the typing

One of the first tools we'll use is a version control system called Git, a tool that was written expressly for helping thousands of people around the world co-develop one of the largest and most stable software projects around: the Linux operating system. You can read more about the history of Git and Linux here.

Some of you may have used Git before, perhaps in the Fall and Winter quarter of Upper Division CS. This quarter, we will focus on understanding the concepts and the underlying operation of Git via its graph representation of commits.

To do this, we are going to play the game of tic-tac-toe, which many people used to first learn to play on paper with pen/pencil.

We'll pause here. Pair up with the person next to you, draw a grid that looks like the hash sign # with enough space to write X and O, and take turns drawing your symbols.

Here are rules how to play.

Now, think back on your game and how you would define this problem more precisely so that you could write a program to play the game automatically (a TicTacToeSolver).

Over the next week, we'll use this problem to practice both

• version control skills with git
• software construction skills to define and write a solver

We'll call it Git-Tac-Toe (groans are appropriate here) and play it on an ASCII grid that can be stored in plaintext like this.

|_|_|_|1
|_|_|_|2
|_|_|_|3
 1 2 3

Graphs in Game Theory

Before we show the same as git commits instead of an abstract graph, let's talk about a problem that might occur with you and your opponent this afternoon when you attempt to play Git-Tac-Toe.

If two people edit a file at the same time (let's say you and your opponent both add your names to the README.md file) you might be heading for a merge conflict. This is a normal part of software projects with more than one user (and sometimes you can even have conflicts with yourself working on different machines).

If one of your commits and pushes their changes to the remote (GitHub) first, the other one will see this message saying that their local and remote repos have diverged.

What to do next? Well, it is not possible to push in this case and expect GitHub to know how to merge this.

Git is telling you that as far as it can tell, you are the one without the latest changes, so if you want to push, you have to first pull and resolve the merges to your satisfaction locally, then commit and push again.

"Fast-forward merges" between a local and remote mean that one of them is just a subset of the other, and different commits can be added in a straight line to sync them.

For example, if your local repo looks like this

gitGraph
  commit id: "abc123"

and your remote repo looks like this

gitGraph
  commit id: "abc123"
  commit id: "def456"

Then the local can be "fast-forwarded" by simply pulling one single commit def456 and appending it to your local repo. Then both local and remote are now in sync, now merge conflicts or resolutions needed.

gitGraph
  commit id: "abc123"
  commit id: "def456"

and your remote repo looks like this

gitGraph
  commit id: "abc123"
  commit id: "def456"

Since in our example above, the local can't be fast-forwarded to match the remote, when you git pull, you'll be asked the first time what your default merge strategy is.

For this class, the default strategy of merging is to set rebase to false.

In order to pull and merge the change from remote, we're going to commit a move locally first, X makes move 2.

When you commit successfully (locally), git will display the commit hash, usually the first 7 characters. You can see above that this most recent commit has hash d8fa02b

You can then use the hash to dump the complete contents of what was committed in this node of the git graph. For example, the diff of the lines added and removed, as well as the timestamp, the author, etc.

When you type

git pull

after this commit, you'll see the merge commit message appear giving you a chance to add more details if you wish. In this case, it uses the default text editor nano on many UNIX systems.

You can also set your GIT_EDITOR environment variable in your shell file to vim or to code, if you've aliased code to VSCode on your system.

Save and exit, then the merge will complete, and a merge is just another commit.

When we show the local graph, we see that this most recent merge is the latest commit to the graph, and including it, we have 4 commits locally that are not on the remote yet.

We can now git push to the remote.

On the GitHub remote, you can see these commits are displayed as if they were a nice linear timeline

We know that is not the case, but the fact that we were able to push means that the latest commit is a valid merge combining the latest state on both the remote and the local, so no information was lost.

Any changes can be reverted if necessary in case we want to undo or go back in our game.

On our github remote, we can see the latest game state in board.txt

https://github.com/TheEvergreenStateCollege/game-00/commit/d8fa02bd69b9caa5c35cb32c0980fbeb01e2040f

 _ _ _
|_|_|X|1
|_|O|_|2
|_|_|_|3
 1 2 3

Remember the graph? Now we label the nodes with git hashes, and show the diffs that move the game state from one node to the next.

Here's the first commit that sets up the empty board, and also writes the players names into README.md

The next commit hash cbaff95 makes the first move for O.

The next commit makes the second move to X.

After that, O make the third move, and the screenshot above shows how you will play Git-Tac-Toe on your own.

• Edit the text file board.txt
• Add your O or X
• git add, git commit, and git push

Below, we go back in time so that O can make a new Move 5 to change the game's outcome. We checkout a specific past commit, and then use the new git switch command to create a new branch starting at that point.

Note that main was our only branch before, and was the same as HEAD, but now as we create a new branch, HEAD follows redo and main stays with the original game where X won.

We can see that Git branches are just labels or sticky notes. They don't refer to the whole timeline, just a particular commit in a timeline, usually the latest one, and they can be moved around.

A lot of mayhem can follow if you don't keep your branch names straight between local and remote. In the next screenshot, we try to push without specify a branch name, and Git reminds us to be explicit, and strongly recommends that we keep the local and remote branch names the same.

Here is the Pull Request that results from us going "back in time" to make a new Move 5.

https://github.com/TheEvergreenStateCollege/game-00/pull/1

The merge conflict is not surprising, remember. Both the redo and the main branch have changes to the same file board.txt

At this point we end our demonstration, but in the afternoon lab, you are asked to play the game to the (bitter?) end to show that its outcome is indeed different than the original game.

Then merge your redo branch into main locally, resolve any conflicts, add, commit, push, merge, and close the Pull Request.

This follows our standard Git Workflow that we've been developing and following for the past two quarters, and that is very common in industry.

cargo new <project_name>
cd <project_name>
cargo build
cargo run

use std::mem::size_of;
  
fn main() {

    // For each of lines below, try picking a value that you think will cause typechecking to fail
    let a: u8 = 1;
    let b: u16 = 1;
    let c: u32 = 1;
    let d: u64 = 1;
    let e: i8 = -1;
    let f: i16 = -1;
    let g: i32 = -1;
    let h: i64 = -1;

    let i: char = '🥸';
    let j: bool = false;
    let k: f32  = 1.0;
    let l: f64 = 2.2;
    let m: [u8; 2] = [1,1];
    let n: (u16, bool) = (2, true);
    let o: i32 = 1;
    let p: i64 = 1;

    let q: usize = size_of::<u8>();
    let r: usize = m.len();

    // Try and guess what number if printed out for each of these;
    println!("sizeof u8 {}", size_of::<u8>());
    println!("sizeof u16 {}", size_of::<u16>());
    println!("sizeof u32 {}", size_of::<u32>());
    println!("sizeof u64 {}", size_of::<u64>());
    println!("sizeof i8 {}", size_of::<i8>());
    println!("sizeof i16 {}", size_of::<i16>());
    println!("sizeof i32 {}", size_of::<i32>());
    println!("sizeof i64 {}", size_of::<i64>());

    println!("sizeof bool {}", size_of::<bool>());
    println!("sizeof char {}", size_of::<char>());
    println!("sizeof f32 {}", size_of::<f32>());
    println!("sizeof f64 {}", size_of::<f64>());
    println!("sizeof [u8; 2] {}", size_of::<[u8; 2]>());
    println!("sizeof [u64; 100] {}", size_of::<[u64; 100]>());

}

Although we will learn more about Rust types and basic programming language primitives in the afternoon, we can begin to sketch out here an interface for our top-level solver.

enum Cell {
    EMPTY,
    X,
    O
}
  
struct Move {
    target: (u8, u8),
    player: Cell,
}
  
struct Board {
    cells: Vec<Vec<Cell>>,
    player_to_move: Cell,
}
  
// Takes in a current board state, including the player to move next
// and returns the sequence of moves which brings the game to shortest conclusion
fn solve(board: Board) -> Vec<Move> {

}

This week, we talked in very general terms about Requirements Engineering: we want to make a tic-tac-toe solver.

Next week, we'll begin talking about the first part of turning that into a design, and that's by

• Abstracting away many differences between winning board states and moves and
• Specifying different modules and interfaces between them.

As you learn about Rust types and functions, try to come up with pseudocode function signatures (function name, typed arguments, return type) that might be needed in a tic-tac-toe solver.

1. From https://www.planradar.com/gb/software-for-construction/
2. Created with https://wordart.com
3. Etsy's Engineering Blog: Code As Craft