Choosing and Repeating

1.1Java is strongly, statically typed

Variables have types, data has types, and those types must be compatible and known at compile time. Week 1 showed you one kind of type error. There are others, and they all arrive before the program ever runs.

Two errors from one run. That is normal — the compiler reports everything it can find, so always start reading at the first one.

1.2It is not only variables that have a type

• Methods have a return type. That void in public static void main means “returns nothing”.
• Expressions have a type — the type of the value they evaluate to. The expression 10 + 3 has type int.

So int i = 10 + 3; is fine and boolean b = 10 + 3; is not. Run it and read the two types the error names.

1.3boolean is its own type

Java has a boolean type for every true/false value, and it is not compatible with the numeric types. Other languages disagree. This is valid C++:

bool b = true;
int i = 10 + b;   // i is 11 — fine in C++

The Java equivalent will not compile at all.

Did you know?

The type is named after a person. George Boole published An Investigation of the Laws of Thought in 1854, arguing that logic could be done as algebra — with values that are only ever true or false. There were no computers to apply it to. Eighty-three years later a 21-year-old master’s student, Claude Shannon, noticed in his 1937 MIT thesis that Boole’s algebra described exactly what a circuit of relay switches does — and the two halves of your boolean finally met. Source: Wikipedia — A Symbolic Analysis of Relay and Switching Circuits.

1.4The operators that produce a boolean

A lone boolean is dull. They become useful as the type of a whole expression, built with these:

These combine, as long as the types line up. Enter 15, then try 7:

2.1The if statement

Now that a program can say whether something is true, it can use that to decide what to do next. The syntax, with the angle brackets standing in for your own code:

Before the code: M4 draws this same choice as a diamond with two arrows that reunite — the picture behind the syntax.

if (<condition>) {
    <what to do when the condition is true>
}

2.2Two ifs are not an if-else

What about when the condition is false? The obvious move is a second if. It has two problems, and the second one is nastier than it looks.

1. What about exactly 100? Neither condition is true, and the program says nothing. Separate conditions need separate care, and this is a good place to introduce a logic bug quietly.
2. The first block changed i. By the time the second if is tested, i is 101 — so both messages print for a single input. Run it above and watch it happen.

Take care to branch the right way on equality.

Brian W. Kernighan & P. J. Plauger, The Elements of Programming Style, 2nd ed., 1978 Portrait: Ben Lowe, 2012 · CC BY 2.0

An else block fixes both, because the two branches become genuinely exclusive: exactly one of them runs.

Did you know?

The first IF in a high-level language had three exits and no else at all. FORTRAN for the IBM 704 offered only the “arithmetic IF”: IF (X) 10, 20, 30 jumps to statement 10 if X is negative, 20 if it is zero and 30 if it is positive. The true/false “logical IF” you are learning here only arrived with FORTRAN IV in 1962. Source: Wikipedia — Fortran.

if (<condition>) {
    <code when the condition is true>
}
else {
    <code when the condition is false>
}

2.3Many conditions: else if

You can nest an if-else inside an else, and it works. But when you are choosing on one value and nothing else, it is nicer to lay the cases out at the same level.

The conditions are tested one after another until one is true, or the final else is reached. So order matters — and you can use that deliberately, putting a specific case before an overlapping general one:

Now move the i == 42 branch to the bottom of the ladder and run it again with 42. It becomes unreachable — and nothing warns you.

3.1When every test is “is it equal to…”

Suppose x being 1, 5, 87 or 120 means one thing and anything else means another. With an if that is a long boolean condition:

if (x == 1 || x == 5 || x == 87 || x == 120) { ... }
else { ... }

Bearable for four cases. Painful for twenty, and worse if each case does something different. A switch is a compacted else if ladder restricted to equality — one readable line per case, easy to add to.

Did you know?

A char can sit in that list because to the machine it is a small number. In ASCII 'A' is 65 and 'a' is 97. The gap of 32 was deliberate: in 1963 the committee placed the lowercase letters so that each differs from its capital by a single bit, which made case-insensitive matching, keyboards and printers simpler to build. That is why switch, < and + all work on characters. Source: Wikipedia — ASCII (history).

3.2break, and what happens without it

A switch checks the cases in order, and when it finds a match it starts running there and keeps going — through every case below it — until it hits a break or the end of the block. Predict the output before you run this.

Three lines. It starts at the match, not at the top — and then nothing stops it. A missing break is one of the most common bugs in this whole subject.

3.3Fall-through on purpose

Used deliberately, it is how you group cases that share an action:

4.1Same idea, less punctuation

Conditionals in Python work essentially as they do in Java, with mildly different syntax: elif rather than else if, a colon rather than braces, and indentation doing the work that { } does in Java.

4.2Once you have it in one language

Every imperative language works the same way here — the ideas transfer and only the syntax changes. That is worth noticing now, because it is the reason this subject teaches two languages at once rather than one twice as deeply.

4.3match — Python’s switch, sort of

Before version 3.10 Python had nothing like switch, only a hack with dicts that returns known values rather than running code. Since 3.10 there is a structural pattern matching statement:

match <subject>:
    case <pattern 1>:
        <action 1>
    case <pattern 2>:
        <action 2>
    case _:
        <default action>

Notice what is missing: there is no break, because there is no fall-through. Only the matching block runs. That is the major practical difference from a Java switch — Python’s version comes from functional pattern matching rather than C’s fancy jump.

Which means the stacked-label trick from section 3.3 is gone. In its place, | gives one case several values:

Which does start to look like an if/elif again. The line between them is genuinely fuzzy; match may make later changes tidier, or may not.

5.1Repetition is boooooring

To print 1 to 10 with what you know so far, you write ten println lines. To print 1 to 1000 you write a thousand — and who is going to check that code?

The real killer is this: what if the number changes every time the program runs? The user picks it. You cannot write out lines for a number you do not know. Until you have a loop, that program is not merely tedious to write — it is impossible.

A cycle of operations, then, must be understood to signify any set of operations which is repeated more than once.

Ada Lovelace, Note E to her translation of Menabrea’s Sketch of the Analytical Engine, 1843 Portrait: Antoine Claudet, 1843 · public domain

That is very likely the first definition of a loop ever written down — and it needs no jargon at all. A loop is a group of steps you do more than once.

Did you know?

Sequence, selection and iteration are not just convenient — they are enough. The Böhm–Jacopini theorem (1966) proves that any computable function can be written using only those three ways of combining sub-programs. Everything software has ever done can, in principle, be built out of Sections 2 and 5 of this page. Source: Wikipedia — Structured program theorem.

5.2The while loop

while (<condition>) {
    <code>
}

It repeats the code for as long as the condition is true. Like an if, the condition must be a boolean expression. Three moving parts: set a variable up, test it, change it.

Compared with the fixed version, only the condition changed — i <= 10 became i <= n. The impossible program became trivial.

Read that as a loop and look for the exit condition. There isn’t one. Every loop you write, ask the same question: what makes this stop?

M4 draws this same question as an arrow that loops back on itself — the same trap, before a single line of Java exists.

5.3The for loop

A for loop gathers those same three parts into one line, in order:

for (<initialisation>; <condition>; <modification>) {
    <code>
}

Read for (int i = 1; i <= n; i++) as “for i from 1 to n in steps of 1”. Change the details and you change the pattern — i += 2 from 2 gives the even numbers, from 1 gives the odd ones.

5.4while vs for: which is best?

Neither. They are functionally equivalent — every while converts to a for and back. Java allows empty statements, so a while becomes for (; i <= 10; ), and an infinite while (true) becomes for (;;). Going the other way, you just unpack the three parts.

Since the machine cannot tell them apart, the choice is about what you tell the reader:

5.5For-each: walking a collection

for (<type> <name> : <iterable collection>) {
    <code>
}

Read it as “for each element in the collection…”. It hands you the elements one at a time and you never touch an index, so you cannot get the index wrong.

Civilization advances by extending the number of important operations which we can perform without thinking about them.

Alfred North Whitehead, An Introduction to Mathematics, 1911 Portrait: unknown, 1923 · public domain

What counts as an “iterable collection”? Arrays, and anything that implements Iterable — which is most things in the Java library with a linear order. Notably not a String:

The error message tells you the rule exactly: can only iterate over an array or an instance of java.lang.Iterable. Changing char to String does not help — the problem is what you are walking, not what you pull out of it.

A for-each is just syntactic sugar. For an array the compiler writes out the ordinary loop for you:

for (int index = 0; index < a.length; index++) {
    int i = a[index];
    System.out.println(i);
}

5.6do-while: test afterwards

Both loops so far check the condition before the first pass. Sometimes you need to run the body first — most often because you need the input before you can judge it.

do {
    <code>
}
while (<condition>);   // note the semicolon

Written with a plain while, the prompt-and-read has to appear twice: once before the loop and once inside it. Once you are writing the same code in two places, look for a better way — here, this:

Let the machine do the dirty work.

Brian W. Kernighan & P. J. Plauger, The Elements of Programming Style, 2nd ed., 1978 Portrait: Ben Lowe, 2012 · CC BY 2.0

The input box above holds three lines — 3, 5, then 6 — because the program will ask three times. A do-while body always runs at least once.

6.1Loops inside loops

Once you are inside a block you can write any statement, including another loop. Nesting is how you handle multi-dimensional data and anything of the form “for every x, for every y…”.

Note the inner loop’s stopping condition: j < i uses the outer loop’s variable. That is common and useful — the inner loop does a different amount of work each time around.

6.2Two dimensions

The same shape walks a two-dimensional array. Rows need not be the same length, so the inner condition is data[i].length, not one fixed number:

Three dimensions is one more level of nesting, and so on. Matrix multiplication is the classic triple nest — and note there that the names i and j can be reused in a later set of loops, because a variable declared in a for header is local to that loop.

…there is a recurring group of one or more cycles; that is, a cycle of a cycle, or a cycle of cycles.

Ada Lovelace, Note E, 1843 — nested loops, named 115 years before Java Portrait: Antoine Claudet, 1843 · public domain

6.3Loops with almost no body

Only the middle part of a for header is restricted — it has to evaluate to a boolean. The other two can be almost any expression, so a loop can have an empty body and still do work:

Write clearly — don’t be too clever.

Brian W. Kernighan & P. J. Plauger, The Elements of Programming Style, 2nd ed., 1978 — the book’s first rule Portrait: Ben Lowe, 2012 · CC BY 2.0

The genuinely useful version of this is remembering that a loop body can be a single statement with no braces at all. Combined with a for-each, that reads beautifully:

6.4Finishing early with break

You met break in a switch. In a loop it ends the loop and the program carries on from the next statement after it. In nested loops, the question is which loop — run this and see:

Only the current loop. What break really does is jump to the end of the current block — usually the next }. The outer loop keeps going and starts a fresh inner loop each time.

To leave both at once, label the outer loop and break to the label:

6.5continue: skip just this one

The inverse of break. It abandons the rest of this iteration and goes back to the start of the loop.

It reads best as a filter: “this one is no good, next please”. With a labelled continue, the prime finder from 6.1 loses both the isPrime variable and the trailing if:

Same answers as 6.1, less bookkeeping. Compare the two and decide for yourself which one you would rather read in six months.

7.1The shape of a Python loop

Python has while and for, but its for is always a for-each — there is no three-part header. To count, you iterate over range(n), which gives 0, 1, …, n−1:

7.2break and continue

Both work in both kinds of loop, and mean exactly what they meant in Java: break stops the loop immediately and resumes after it; continue skips the rest of this iteration and goes back to the start.

Python has no labelled break. To leave nested loops you restructure — commonly with a flag variable, or by moving the inner loop into a function once you have those.

Automating repetition is the whole point of a loop — but the chart is honest about the other half: sometimes the loop costs more than the tedium it removes.

7.3Loop-else — the genuinely strange one

Python lets you attach an else clause to a loop. It runs when the loop ends because its condition failed — and a break skips it.

8.1Fifty variables is not a plan

Averaging two marks needs two variables. Three needs three. Fifty needs fifty — and then someone has to check that all fifty names appear correctly in the sum.

Worse is the flexible version. Handling “2 or 3 marks” with an if already looks fragile, and it breaks the moment the user enters 0, 1, or 4. Two problems, one answer:

1. You do not want to invent a new variable name for every value.
2. You want one piece of code that copes with every reasonable case.

That is exactly what an array is for.

8.2What an array actually is

A block of contiguous memory, cut into equal-sized elements. Each element holds one value of the array’s declared type, so once you know where the array starts, reaching element i is just an offset from that address — which is essentially what the number in the square brackets does.

• The number of elements is the length.
• The first element has index 0, the second 1, and the last is at length − 1. This is 0-indexing, and it is normal across most languages — see M2 for why.

Line by interesting line:

I found this amazing: only about 10 percent of professional programmers were able to get this small program right.

Jon Bentley, Programming Pearls: Writing Correct Programs, CACM 26(12), 1983 — on binary search Portrait: Wikimedia Commons, 2013 · CC BY-SA 4.0

Bentley gave professional programmers an hour to write binary search over an array. Ninety percent shipped a bug — almost all of them at the boundaries. When your loop bound looks obviously right, that is exactly the feeling those programmers had.

Did you know?

It was not only the students. In 2006 Joshua Bloch, who wrote much of the Java library you are about to use, found the same class of bug in java.util.Arrays.binarySearch — (low + high) / 2 overflows once the array is big enough. It had been shipping in the JDK, he wrote, “after lying in wait for nine years or so”. The published version in Bentley’s own Programming Pearls had it too. Source: Joshua Bloch, Google Research blog, 2 June 2006.

8.3Arrays plus loops

Section 8.1 wanted one program for any number of marks. With an array and a loop you finally have it — and the loop bound comes from the array itself:

The underlying type need not be primitive either — String[] words = new String[2]; works exactly the same way.

8.4More than one dimension

Nothing new: just add more brackets. new int[2][2] gives a 2×2 grid.

The interesting part is that int[][] is an array of arrays, not a special two-dimensional object. Append [] to a type to mean “array of that”, and int[][] reads as “array of int[]”. Two consequences:

• values[i] hands you back a whole int[], which is why data[i].length in section 6.2 made sense.
• The rows do not have to be the same length. new int[3][] creates the outer array and lets you size each row yourself — a ragged array that uses only the space it needs.

8.5Fixed size, and what a variable really holds

A Java array is not resizable. You can point the variable at a new, bigger array, but the data does not come with it unless you copy it.

And pointing the variable somewhere else does not destroy the old array — the variable simply stops referring to it. If something else still refers to it, it is still there, unchanged:

After the reassignment b[1] is still 4, but a[1] is 0. This is your first real encounter with references, and it will come back repeatedly from Week 6 onwards.

8.6Tidbits worth knowing

8.7The two array errors you will actually meet

The common one is going out of bounds. Notice when it is caught:

The first line prints, then it throws. This is a run-time error, not a compile error — even though a human can see that 23 is too big, the compiler cannot decide this in general, so it does not try.

…every occurrence of every subscript of every subscripted variable was on every occasion checked at run time against both the upper and the lower declared bounds of the array.

C. A. R. Hoare, The Emperor’s Old Clothes, 1980 ACM Turing Award Lecture Portrait: Rama, 2011 · CC BY-SA 2.0 fr

That is Hoare describing his own Algol compiler in the 1960s. When customers were later offered the option to switch those checks off for speed, they unanimously told him not to — they already knew how often subscript errors happen, and how badly they end. He then adds:

I note with fear and horror that even in 1980, language designers and users have not learned this lesson.

C. A. R. Hoare, same lecture Portrait: Rama, 2011 · CC BY-SA 2.0 fr

So the exception you just saw is not Java being fussy. It is a Turing Award winner’s hard-won argument, finally built into the language.

The other one is caught at compile time: using an array you never initialised.

Two errors, two moments. Knowing which kind you are looking at tells you where to go looking — a compile error is in the text of your program, a run-time error is in what it was given.

9.1No arrays here

Python, unlike almost every other imperative language, has no array type as a basic type. Libraries add them — NumPy most famously — but vanilla Python uses the list as its “collect a bunch of data together” type.

Lists are indexed like Java arrays, from 0. Two differences, both from Python’s dynamic type system:

• They have no fixed size.
• Their elements may have different types.

9.2Changing the length

append(elem) adds to the end. insert(pos, elem) puts one at pos, moving what was there — and everything after it — up one place.

9.3Joining lists together

+ builds a new list, += and extend add to the end of an existing one:

9.4Slice assignment

A whole list can be dropped into the middle of another with a slice: l[a:b] = m replaces everything the slice covers with the contents of m. Both indices mean “just before that position”.

Which gives a neat trick: a slice of zero width, like l[1:1], covers nothing, so nothing is removed and m is simply squeezed in at that point.

9.5A typical list program, explained

Everything from this section in one short program: build a list, grow it, read from both ends, walk it, change it, search it. Point at an underlined part to see what it does, then press Run.

10.1Why Python has three more of these

Java keeps its primitive types to the smallest set it could get away with, and does everything else through classes and objects. Python has a different goal: a wide range of tools with lightweight syntax, at some cost in uniformity.

So Python ships three more data structures with syntax of their own. Java has two of the three — not by default, more work to use, and more structured in return. There is no Java tuple at all.

Internally these are classes, like everything else. Python just gives you special syntax so you never have to see that part.

Data dominates. If you’ve chosen the right data structures and organized things well, the algorithms will almost always be self-evident.

Rob Pike, Notes on Programming in C, Rule 5, 1989 Portrait: Kevin Shockey, 2010 · CC BY 2.0

10.2Dictionaries

A dict (hash-map, associative array, hash-table — same idea, many names) stores key–value pairs. You get at a value with square brackets and its key, exactly as you would with a list index.

Iterating takes a moment’s thought, because every entry has two halves. Plain for k in d: gives you the keys:

A typical dict program. Counting is the classic job for a dict: each word is a key, and its value is how many times it has turned up. Point at an underlined part to see what it does.

10.3Sets

The mathematical idea, built in: a collection with no duplicates and no guaranteed order. Add the same element five times and one survives.

You cannot pull an element out by position — if you could, it would be a list, and Python already has one of those. What you can do is ask whether something is in it, and combine sets with the usual operations:

To change one, use add and remove — there is no index to assign to. And the negation of in is not in, not not x in.

A typical set program. Sets answer “who, without repeats?” and “who is in both?”. Point at an underlined part to see what it does.

10.4Tuples

A tuple is a list you cannot change. Index it, iterate it, read it — but you cannot assign to an element, add one or remove one. That sounds like a limitation until you notice how often you never needed to change the data anyway, which makes tuples the natural way to bundle a few values together.

It is the comma that makes a tuple, not the parentheses — the brackets just look nicer. Which leads to one genuinely odd edge case:

Everything else works the way you would now expect: primes[0] for an element, for p in primes: to walk it. This is the same tuple d.items() handed you in 10.2.

A typical tuple program. Tuples bundle a few values that belong together, and unpacking takes them apart again. Point at an underlined part to see what it does — and run it to the end, because the last line fails on purpose.

11.1Easy in Python

Each person has a name (a str) and a favourite number (an int). Python’s dynamic types make a list of pairs trivial:

11.2…and stuck in Java

Try the same thing in Java and you cannot even write the declaration:

???[] people = ???[];   // what type goes here?

people[i] = name? num?  // and how do both go in one cell?

• A Java array has one element type, so it cannot hold Strings and ints together.
• Java has no tuple.
• Java does have List, but it has the same type restriction.

11.3The answer with nothing new: parallel arrays

Keep the halves in separate arrays, kept in step by index. All the types match, so Java is happy — and names[i] goes with numbers[i] because you make sure it does.

Why “kept in step” is doing a lot of work

Nothing in the language ties names[3] to numbers[3]. Sort one array and forget the other, insert into one and not the other, and the data is silently wrong — no error, no crash. It works, but the correctness lives in your head rather than in the code.

Bad programmers worry about the code. Good programmers worry about data structures and their relationships.

Linus Torvalds, git mailing list, 27 July 2006 Portrait: Krd (photo) Von Sprat (crop/extraction), 2014 · CC BY-SA 4.0

11.4What C and C++ do: struct

Java’s culture comes from C and C++, where this problem has a name. A struct is literally a way to bundle data of different types — often called “plain old data”:

struct data {
    std::string name;
    int num;
};

With that, one collection holds the pairs, and the rest of the program looks much like the Java above — just without the second array.

11.5The Java version: a class that only carries data

class Data {
    public String name;
    public int num;
}

Structurally close to the struct, with four differences worth naming:

• The keyword is class.
• Each data member is marked public.
• You create one with new, exactly as with Scanner.
• You reach a member with the dot operator: d.name.

Two things will look unfamiliar. It is not marked public, which is what lets it share a file with another class. And it has no methods at all — no main, nothing.

M2.1Not an accident, and not only about memory

The usual explanation is that index i is an offset from the start of the array, so the first element sits at offset 0. True, and it is where the convention came from. But there is a better argument, and it is about ranges.

In 1982 Edsger Dijkstra wrote a one-page note, EWD 831, asking how to write “the numbers 1 through 10”. There are four options:

The first form wins on two counts: the length is simply upper minus lower, and an empty range is the harmless a ≤ i < a. Adopt it, then start indices at the smallest natural number, and you get 0 ≤ i < N — which is exactly the shape of every for loop you have written today.

M2.2Duff’s device, and switches with no breaks

The Ed arrays reading uses a switch with no breaks to pick where to start reading values — deliberately falling all the way down. That looks like a party trick. It is actually a technique with a name and a date.

In 1983 Tom Duff, then at Lucasfilm, needed to copy data faster than a straightforward loop allowed. The answer was loop unrolling: do eight copies per iteration instead of one, so the loop’s own overhead is paid one-eighth as often. The awkward part is the leftovers — what if the count is not a multiple of eight? Duff’s answer was to interleave a switch through a do-while, jumping into the middle of the unrolled body so the remainder is handled first.

It is legal C, it is genuinely clever, and Duff himself expected it to start an argument. Today compilers unroll loops for you, so it is history rather than advice — but it is why fall-through exists at all, and it is worth knowing that the ugly thing in the reading is a fossil of real engineering.

M3.1The letter that started it

In March 1968 the Communications of the ACM published a two-page letter by Edsger Dijkstra arguing that the goto statement — jump anywhere, from anywhere — should be abolished from high-level languages. His argument was not that it was inelegant. It was that with unrestricted jumps you cannot describe where a running program has got to, so you cannot reason about it — and neither can the person reading it.

The quality of programmers is a decreasing function of the density of go to statements in the programs they produce.

E. W. Dijkstra, CACM 11(3), March 1968 Portrait: Hamilton Richards, 2002 · CC BY-SA 3.0

The famous title, Go To Statement Considered Harmful, was not Dijkstra’s — the editor, Niklaus Wirth, supplied it. It went on to spawn a whole genre of “considered harmful” papers, including several arguing the opposite.

M3.2What replaced it, and what survives

What won was structured programming: build programs out of blocks with one way in and one way out — sequence, selection, repetition. That is precisely the if, the switch and the loops in sections 2 to 7. Everything you learned this week is the settlement of that argument.

Java took it literally. goto is a reserved word in Java that does nothing — you cannot use it as a variable name, and you cannot use it to jump either. What Java offers instead is the labelled break and continue from section 6.4, with one rule that makes all the difference:

So the labelled break is not a loophole. It is the largest amount of jumping that can be allowed while keeping the thing that made structured programming worth having.

The price of reliability is the pursuit of the utmost simplicity.

C. A. R. Hoare, The Emperor’s Old Clothes, 1980 ACM Turing Award Lecture Portrait: Rama, 2011 · CC BY-SA 2.0 fr