Reading 1: Static Checking

As a running example, we’re going to explore the hailstone sequence, which is defined as follows: Starting with a number n, the next number in the sequence is n/2 if n is even, or 3n+1 if n is odd. The sequence ends when it reaches 1. Here are some examples:

2, 1
3, 10, 5, 16, 8, 4, 2, 1
4, 2, 1
2n, 2n-1 , … , 4, 2, 1
5, 16, 8, 4, 2, 1
7, 22, 11, 34, 17, 52, 26, 13, 40, …? (where does this stop?)

Because of the odd-number rule, the sequence may bounce up and down before decreasing to 1. It’s conjectured that all hailstones eventually fall to the ground – i.e., the hailstone sequence reaches 1 for all starting n – but that’s still an open question. Why is it called a hailstone sequence? Because hailstones form in clouds by bouncing up and down until they eventually build enough weight to fall to earth.

Computing hailstones

# Python
n = 3
while n != 1:
    print(n)
    if n % 2 == 0:
        n = n / 2
    else:
        n = 3 * n + 1


print(n)

// JavaScript (or TypeScript, this code works in both languages)
let n = 3;
while (n !== 1) {
    console.log(n);
    if (n % 2 === 0) {
        n = n / 2;
    } else {
        n = 3 * n + 1;
    }
}
console.log(n);

But we are not using JavaScript in this class, strictly speaking. We are using TypeScript, which extends JavaScript with the ability to declare types in the program. In this case, we can specify that the variable n has type number:

let n: number = 3;

A type is a set of values along with operations that can be performed on those values.

TypeScript has several built-in types, including:

• number, which represents both integers and floating-point numbers
• boolean, which represents true or false
• string, which represents a sequence of characters

Operations are functions that take inputs and produce outputs (and sometimes change the values of the inputs themselves). The syntax for operations varies, but we still think of them as functions no matter how they’re written. Here are several different syntaxes for an operation in Python or TypeScript:

• As an operator. For example, a + b invokes the operation + : number × number → number. (In this notation: + is the name of the operation, number × number before the arrow gives the types of the two inputs, and number after the arrow gives the type of the output.)

• As a function. For example, Math.sin(theta) calls the operation sin: number → number. Here, Math is not an object. It’s the class that contains the sin function.

• As a method of an object. For example, str1.concat(str2) calls the operation concat: string × string → string.

• As a property of an object. For example, str.length calls the operation length: string → number. Note the lack of parentheses after str.length.

Contrast TypeScript’s str.length with Python’s len(str). It’s the same operation in both languages – taking a string and returning its length – but it just uses different syntax.

Some operations are overloaded in the sense that the same operation name is used for functions that take different types of arguments. The operator + is overloaded in TypeScript. With numbers, 5 + 3 naturally produces 8. But when + is used on strings, it does string concatenation instead, so “5” + “3” produces “53”. Overloading is not limited to operators like +; methods and functions can also be overloaded. Most programming languages have some degree of overloading.

TypeScript is a statically-typed language. Variables can be assigned a type at compile time (before the program runs), and the compiler can therefore deduce the types of expressions using those variables. If a and b are declared as number, then the compiler concludes that a+b is also number. In fact, the VS Code environment does this while you’re writing code, so you can see all the relevant errors while you’re still typing.

JavaScript and Python, by contrast, are dynamically-typed languages, because this kind of checking is deferred until runtime (while the program is running).

Static typing is a particular kind of static checking, which means checking for bugs at compile time. Bugs are the bane of programming. Many of the ideas in this course are aimed at eliminating bugs from your code, and static checking is the first idea that we’ve seen for this. Static typing prevents a large class of bugs from infecting your program: to be precise, bugs caused by applying an operation to the wrong types of arguments. If you write a broken line of code like:

"5" * "6"

that tries to multiply two strings, then static typing will catch this error while you’re still programming, rather than waiting until the line is reached during execution.

Static types at compile time, dynamic types at runtime

// TypeScript to compile
function hello(name: string): string {
    return 'Hi, ' + name;
}
let greeting: string = hello('types');

// JavaScript generated
function hello(name) {
    return 'Hi, ' + name;
}
let greeting = hello('types');      

Support for static typing in dynamically-typed languages

# Python function declared with type hints
def hello(name: str) -> str:
    return 'Hi, ' + name

It’s useful to think about three kinds of automatic checking that a language can provide:

• Static checking: the bug is found automatically before the program even runs.
• Dynamic checking: the bug is found automatically when the code is executed.
• No checking: the language doesn’t help you find the error at all. You have to watch for it yourself, or end up with wrong answers.

Needless to say, catching a bug statically is better than catching it dynamically, and catching it dynamically is better than not catching it at all.

Here are some rules of thumb for what errors you can expect to be caught at each of these times.

Static checking can catch:

• syntax errors, like extra punctuation or spurious words. Even dynamically-typed languages like Python do this kind of static checking. If you have an indentation error in your Python program, you’ll find out before the program starts running.
• misspelled names, like Math.sine(2). (The correct spelling is sin.)
• wrong number of arguments, like Math.sin(30, 20).
• wrong argument types, like Math.sin("30").
• wrong return types, like return "30"; from a function that’s declared to return a number.

In general, static checking can detect errors related to the type of a variable – the set of values it is allowed to have, which is known at compile time in statically-typed languages like TypeScript – but is generally unable to find errors related to a specific value from that type.

Dynamic checking can catch, for example:

• specific illegal argument values. For example, the expression x/y is erroneous when y is zero, but well-defined for other values of y. So divide-by-zero is not a static error, because you can’t know until runtime whether y is actually zero or not. But divide-by-zero can be caught as a dynamic error; Python throws ZeroDivisionError when it happens.
• illegal conversions, i.e., when the specific value can’t be converted to or represented in the target type. For example, in Python, int("hello") throws ValueError, because the string "hello" cannot be parsed as a decimal integer.
• out-of-range indices or missing keys, e.g., using a too-large index on a string or array. In Python, "hello"[13] throws IndexError, and {'a': 1}['b'] throws KeyError.

But you may have noticed that the dynamic-checking examples above all came from Python. What about dynamic checking in TypeScript? TypeScript does the static checking, but its runtime behavior is entirely provided by JavaScript, and JavaScript’s designers decided to do no checking for many of these cases. So, for example, when a string or array index is out of bounds, or a key is not found in a map, JavaScript returns the special value undefined, rather than throwing an error as Python would. When dividing by zero, JavaScript returns a special value representing infinity rather than throwing an error. No checking makes bugs harder to find than they might otherwise be, because the special values can propagate through further computations until a failure finally occurs much farther away from the original mistake in the code.

Surprise: number is not a true number

let n: number = 5;
n = n + ".0";

let odd: number = 2**30 - 1;         // an odd number
let oddSquared: number = odd * odd;  // the square of an odd number should be odd

let sum: number = 7;
let n: number = 0;
let average: number = sum/n;

let x: number = 0;
x += 0.1; x += 0.1;
x += 0.1; x += 0.1;
x += 0.1; x += 0.1;
x += 0.1; x += 0.1;
x += 0.1; x += 0.1;
// x should be 1.0

let n: number = 2**53 - 1000;
while (n !== 2**53 + 1000) {
    n = n + 1;
}

Let’s change our hailstone computation so that it stores the sequence in a data structure instead of just printing it out.

For that, we can use an array type. Arrays are variable-length sequences of another type, similar to Python lists. Here’s how we can declare an array of numbers and make an empty array value:

let array: Array<number> = [];

Here’s the hailstone code written with arrays:

let array: Array<number> = [];
let n: number = 3;
while (n !== 1) {
    array.push(n);
    if (n % 2 === 0) {
        n = n / 2;
    } else {
        n = 3 * n + 1;
    }
}
array.push(n);

If we want to wrap this code into a reusable module, we can write a function:

/**
 * Compute a hailstone sequence.
 * @param n  starting number for sequence.  Assumes n > 0.
 * @returns hailstone sequence starting with n and ending with 1.
 */
function hailstoneSequence(n: number): Array<number> {
    let array: Array<number> = [];
    while (n !== 1) {
        array.push(n);
        if (n % 2 === 0) {
            n = n / 2;
        } else {
            n = 3 * n + 1;
        }
    }
    array.push(n);
    return array;
}

Take note of the /** ... */ comment before the function, because it’s very important. This comment is a specification of the function, describing the inputs and outputs of the operation. The specification should be concise, clear, and precise. The comment provides information that is not already clear from the function types. It doesn’t say, for example, that the return value is an array of numbers, because the Array<number> return type declaration just below already says that. But it does say that the sequence starts with n and ends with 1, which is not captured by the type declaration but is important for the caller to know.

We’ll have a lot more to say about how to write good specifications in a few classes, but you’ll have to start reading them and using them right away.

function hailstoneSequence(n: number): Array<number> { ... }

Change is a necessary evil. But good programmers try to avoid things that change, because they may change unexpectedly. Immutability – intentionally forbidding certain things from changing at runtime – will be a major design principle in this course.

There are two aspects to immutability: whether a value is mutable or immutable, and whether a reference (such as a variable) can be reassigned or not.

Mutation refers to changing the content of a value. An immutable type is a type whose values can never change once they have been created. The string type is immutable in both Python and TypeScript. Once a string is created, you can’t make it shorter, or longer, or replace any of its characters. You would have to create a new string containing the changes you want.

By contrast, the array type is mutable in TypeScript, just like lists are mutable in Python. You can change the contents of an array or list – adding elements, removing elements, or replacing elements.

Python also has immutable sequences, tuples, which cannot be changed once created. TypeScript doesn’t have immutable tuples, but it does have ReadonlyArray, which is an array type that omits the mutator operations. When you use ReadonlyArray as a type in your code, you can’t call push() to add elements, or splice() to delete elements, or reassign elements like arr[i] = .... TypeScript will report a compiler error, because it can’t find those operations in the ReadonlyArray type.

Reassignment means changing where a variable points. Python allows any variable to be reassigned, but TypeScript allows us to declare constants, which are unreassignable: names that are assigned to a value once, and can never be reassigned. To make a reference unreassignable, declare it with the keyword const instead of let:

const n: number = 5;

If the TypeScript compiler isn’t convinced that your const variable will only be assigned once at runtime, then it will produce a compiler error. So const gives you static checking for unreassignable references.

It’s good practice to use const for as many variables as possible. Like the type of the variable, these declarations are important documentation, useful to the reader of the code and statically checked by the compiler.

function hailstoneSequence(n: number): Array<number> {
    let array: Array<number> = [];
    while (n !== 1) {
        array.push(n);
        if (n % 2 === 0) {
            n = n / 2;
        } else {
            n = 3 * n + 1;
        }
    }
    array.push(n);
    return array;
}

function hailstoneSequence(n: number): ReadonlyArray<number> {
    let array: ReadonlyArray<number> = [];
    while (n !== 1) {
        array.push(n);
        if (n % 2 === 0) {
            n = n / 2;
        } else {
            n = 3 * n + 1;
        }
    }
    array.push(n);
    return array;
}

Writing the type of a variable down documents an assumption about it: e.g., the variable n will always refer to a number. TypeScript actually checks this assumption at compile time and guarantees that there’s no place in your program where you violated this assumption.

Declaring a variable const is also a form of documentation: a claim that the variable will never be reassigned after its initial assignment. TypeScript checks that too, statically.

We documented another assumption that TypeScript (unfortunately) doesn’t check automatically: that n must be positive.

Why do we need to write down our assumptions? Because programming is full of them, and if we don’t write them down, we won’t remember them, and other people who need to read or change our programs later won’t know them. They’ll have to guess.

Programs have to be written with two goals in mind:

• communicating with the computer. First persuading the compiler that your program is sensible – syntactically correct and type-correct. Then getting the logic right so that it gives the right results at runtime.
• communicating with other people. Making the program easy to understand, so that when somebody (possibly you) has to fix it, improve it, or adapt it in the future, they can do so.

We’ve written some hacky code in this reading. Hacking is often marked by unbridled optimism:

• Bad: writing lots of code before testing any of it.
• Bad: keeping all the details in your head, assuming you (and everyone using your code) will remember them forever, instead of writing them down in your code.
• Bad: assuming that bugs will be nonexistent or else easy to find and fix.

But software engineering is not hacking. Engineers are pessimists:

• Good: write a little bit at a time, testing as you go. In a future class, we’ll talk about test-first programming.
• Good: document the assumptions that your code depends on.
• Good: defend your code against stupidity – especially our own! Static checking helps with that.

from math import sqrt
def fun_fact_about(person):
    if sqrt(person.age) == int(sqrt(person.age)):
        print("The age of " + person.name + " is a perfect square: " + str(person.age))

Our primary goal in this course is learning how to produce software that is:

• Safe from bugs. Correctness (correct behavior right now) and defensiveness (correct behavior in the future) are required in any software we build.
• Easy to understand. The code has to communicate to future programmers who need to understand it and make changes in it (fixing bugs or adding new features). That future programmer might be you, months or years from now. You’ll be surprised how much you forget if you don’t write it down, and how much it helps your own future self to have a good design.
• Ready for change. Software always changes. Some designs make it easy to make changes; others require throwing away and rewriting a lot of code.

There are other important properties of software (like performance, usability, security), and they may trade off against these three. But these are the Big Three that we care about in 6.102, and that software developers generally put foremost in the practice of building software. It’s worth considering every language feature, every programming practice, every design pattern that we study in this course, and understanding how they relate to the Big Three.

Why we use TypeScript in this course

The main idea we introduced today is static checking. Here’s how this idea relates to the goals of the course:

• Safe from bugs. Static checking helps with safety by catching type errors and other bugs before runtime.

• Easy to understand. It helps with understanding, because types are explicitly stated in the code.

• Ready for change. Static checking makes it easier to change your code by identifying other places that need to change in tandem.