1 Motivation

First and foremost, the idea came from Philipp Oppermann’s Writing an OS in Rust blog series.

1.1 Why?

1.1.1 Why Operating Systems?

We first became interested in operating systems after exploring xv6, which is an OS used as a teaching tool in systems courses.

1.1.2 Why Rust?

"Code is written for others to understand the developer’s thoughts, and it accidentally runs on computers." — Matthias Felleisen

This quote comes from Matthias’s talk Types are like the Weather, Type Systems are like Weathermen. He admits he wasn’t the first to say this, but we can’t find the original quote.

We needed a systems programming language, in which we could express our ideas clearly. C is too close to assembly. C++ suffers because of its history with C. We wanted features commonly associated with functional programming languages—expressive types, pattern matching, default immutability, and macros (C-style macros don’t count). We aren’t particularly concerned with performance, but the fact that Rust mostly provides these features as zero cost abstractions is satisfying. Rust’s emphasis on safety (absence of undefined behavior) is also appreciated. We are happy to wrestle with rustc, if it means less issues at runtime. As a side-note, Rust’s compiler emits excellent error messages, which makes the language even more enjoyable to work with.

1.1.3 Why Systematic Design?

The preface of How to Design Programs describes the philosophy behind how we approach our project:

By “good programming,” we mean an approach to the creation of software that relies on systematic thought, planning, and understanding from the very beginning, at every stage, and for every step.

In our introductory computer science course, we learned the design recipe: systematic design that started with small functions. In that course, the essence of it boiled down to the idea that functions follow their data.

1.1.3.1 The Design Recipe

Let’s give an example by implementing length, which takes the length of a list.

Step 1: Data Definitions

We first want to study the data definition of a list.

;; A [Listof X] is one of:

;; - '()

;; - (cons X [Listof X])

;; and represents a sequence of ordered data.

(struct cons (el lst))

For any action we want to perform on a list, there are two different cases we need to handle. The case where it’s an empty list, and the case where it’s a non-empty list (a cons).

The design recipe specifies a template that acts as a blueprint for a function that applies an action on a data structure. For a list, that would look like the following:

(define (list-temp lst)

(cond [(empty? lst) ...]

[(cons? lst)  ... (first lst) ... (rest lst) ...]))

Then, when we want to write a function on a list, we can copy this template and fill in the blanks to perform the action we want.

To dive deeper, you can read How to Design Programs or Recursion as Structural Decomposition.

Step 2: Signature, Purpose Statement, Header

We’re writing length, which takes in a list and produces a number representing its length. If we assume Natural to represent non-negative integers, then we can write the signature of length as follows:

;; length : [Listof X] -> Natural

We also want to write what the purpose of the function is – why does it need to exist? What is its use-case?

;; Computes the length of the given list.

The purpose statement is concise. Note that this example is somewhat contrived – it just reiterates the name of the function. After a copy-paste of the template and renaming the function, we get this so far:

;; length : [Listof X] -> Natural

;; Computes the length of the given list.

(define (length lst)

(cond [(empty? lst) ...]

[(cons? lst)  ... (first lst) ... (rest lst) ...]))

We’re off to a great start!

1.1.3.2 The Design Recipe in Rust

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

use List::*;

#[macro_export]
macro_rules! list {
    ( $( $x:expr ),* ) => {
        {
            let mut temp_l = Empty;
            $(
                temp_l = Cons($x, Box::new(temp_l));
            )*
            temp_l
        }
    };
}

enum List {
    Empty,
    Cons(i32, Box<List>),
}

// Computes the length of the given list.
fn length(l: &List) -> u32 {
    match l {
        Empty => 0,
        Cons(_, rest) => 1 + length(&(*rest)),
    }
}

fn main() {
    println!("{}", length(&list!(1, 2, 3)));
}

1.1.3.3 Systematic Design in our OS

TODO: Elaborate more on exactly how we’re applying systematic design to our OS.

An operating system is considerably larger than a function, consisting of numerous complex components. As a group, we want to use this as an opportunity to systematically design and implement a reasonably challenging project, testing the accumulation of ideas we learned in Northeastern’s CS curriculum.