Class 20 — Wednesday, November 4
A9 first, on the projector. Then while.
A9 was due last night. A10 goes out today and is due Tuesday, November 10. The reading for Monday is [CU] 6.1 — while Loops.
Outline
totalcarried, then as a loop — keyboards down- Walks — pairs, at the keyboard
- Before the break: save to GitHub
copyas a loop — predict, then run- Building lists with a loop — pairs again
- A loop that never stops, and a loop with no list — keyboards down
- Loops over numbers — pairs
- Before you leave: save again
- Before Monday
1. total carried, then as a loop
Keyboards stop. Predict first.
Recursion
Monday’s page had a second total, in its section 6, which we did not reach. The sum so far travels down as an argument, and the Empty case hands it back:
// all the units added up
int total(Lst<Integer> units) {
return totalFrom(0, units);
}
// sum, the units added up so far, plus the units still to add
int totalFrom(int sum, Lst<Integer> units) {
return switch (units) {
case Lst.Empty() -> sum;
case Lst.Link(var u, var rest) -> totalFrom(sum + u, rest);
};
}Evaluate totalFrom(101, Lst.of(4, 10, 20)) by hand. Here are the first four steps:
totalFrom(101, Lst.of(4, 10, 20))
->
totalFrom(101, Link(4, Link(10, Link(20, Empty))))
->
return switch (Link(4, ...)) {
case Lst.Empty() -> 101;
case Lst.Link(var u, var rest) -> totalFrom(101 + u, rest);
};
->
return totalFrom(101 + 4, Link(10,...))
->
return totalFrom(105, Link(10,...))Journal: Finish the evaluation yourself
totalFrom(105, Link(10, Link(20, Empty)))
->
return switch (Link(10, ...)) {
case Lst.Empty() -> 105;
case Lst.Link(var u, var rest) -> totalFrom(105 + u, rest);
};
->
return totalFrom(105 + 10, Link(20, Empty))
->
totalFrom(115, Link(20, Empty))
->
return switch (Link(20, ...)) {
case Lst.Empty() -> 115;
case Lst.Link(var u, var rest) -> totalFrom(115 + u, rest);
};
->
return totalFrom(115 + 20, Empty)
->
return totalFrom(135, Empty)
->
return switch (Empty) {
case Lst.Empty() -> 135;
case Lst.Link(var u, var rest) -> totalFrom(135 + u, rest);
};
->
return 135
->
135Loop
The loop statements, e.g. while below, avoid making function calls at every suffix of the list at the expense of a new evaluation rule.
// all the units added up
int total(Lst<Integer> units) {
int sum = 0;
Lst<Integer> todo = units;
while (todo instanceof Lst.Link(var u, var rest)) {
sum = sum + u;
todo = rest;
}
return sum;
}The former function parameters, sum and units, become local names, sum and todo, and they are updated with = on every step of the loop.
Which line of the loop does what totalFrom(sum + u, rest) did?
The two assignments together. sum = sum + u is the sum + u, and todo = rest is the rest: the call carried two new values down, and the loop puts the two new values into the same two names and goes round again. The loop stops where totalFrom reached its Empty case. Traced one directory per time round, as week 4’s for each was:
sum → 0 todo → [list: 4, 10, 20]
sum → 4 todo → [list: 10, 20]
sum → 14 todo → [list: 20]
sum → 34 todo → [list: ] the condition is false: return 34while (todo instanceof Lst.Link(var u, var rest)) asks whether todo is a link, and if it is, names its parts u and rest for the body, as Monday’s case did.
The new evaluation rules are:
An important consequence of switching from function parameters to mutable local names to hold results of computations is that we now need to be explicit about the values these names hold (a part of the program state). The reason is that the names will be changing on the go. In contrast, function parameters get substituted all at once when we evaluate a function call, and, hence, you don’t need to worry about the program state. We will use {sum -> 0} to show the parts of the state that we care about. We also will use a short hand to avoid showing directory/heap separately as follows: rest->112 (directory) and 112: Link(...) (heap) become just rest->Link(...).
total(Lst.of(4, 10, 20)), with the rules above. The whole state is in braces at every step, {sum -> 0, todo -> ...}; u and rest are in it while the body runs; the condition’s outcome is in square brackets, as in the rule; while (...) { ... } stands for the whole loop after its first appearances.
total(Lst.of(4, 10, 20))
->
int sum = 0;
Lst<Integer> todo = Link(4, Link(10, Link(20, Empty)));
while (todo instanceof Lst.Link(var u, var rest)) {
sum = sum + u;
todo = rest;
}
return sum;
-> {sum -> 0, todo -> Link(4, Link(10, Link(20, Empty)))}
while (todo instanceof Lst.Link(var u, var rest)) {
sum = sum + u;
todo = rest;
}
return sum;
-> [cond ->* true] {sum -> 0, todo -> Link(4, ...), u -> 4, rest -> Link(10, Link(20, Empty))}
sum = sum + u;
todo = rest;
while (todo instanceof Lst.Link(var u, var rest)) {
sum = sum + u;
todo = rest;
}
return sum;
-> {sum -> 4, todo -> Link(4, ...), u -> 4, rest -> Link(10, Link(20, Empty))}
todo = rest;
while (...) { ... }
return sum;
-> {sum -> 4, todo -> Link(10, Link(20, Empty))}
while (...) { ... }
return sum;
-> [cond ->* true] {sum -> 4, todo -> Link(10, ...), u -> 10, rest -> Link(20, Empty)}
sum = sum + u;
todo = rest;
while (...) { ... }
return sum;
-> {sum -> 14, todo -> Link(10, ...), u -> 10, rest -> Link(20, Empty)}
todo = rest;
while (...) { ... }
return sum;
-> {sum -> 14, todo -> Link(20, Empty)}
while (...) { ... }
return sum;
-> [cond ->* true] {sum -> 14, todo -> Link(20, Empty), u -> 20, rest -> Empty}
sum = sum + u;
todo = rest;
while (...) { ... }
return sum;
-> {sum -> 34, todo -> Link(20, Empty), u -> 20, rest -> Empty}
todo = rest;
while (...) { ... }
return sum;
-> {sum -> 34, todo -> Empty}
while (...) { ... }
return sum;
-> [cond ->* false] {sum -> 34, todo -> Empty}
;
return sum;
-> {sum -> 34, todo -> Empty}
return 34
->
342. Walks
- The navigator (not typing) says the examples first. Then they say the steps the function takes.
- The driver types the above, and decides how each step becomes Java.
- If either of you is stuck, drop the roles for a minute and talk it over.
- Swap at every function.
In a new file Walks.java, beside ByHand.java. Each function is a while loop with the pattern above, no call to itself and no Lst.fold. A // line above it, and at least two Check.is lines in main, one on the empty list, Lst.of().
total
int total(Lst<Integer> units) — section 1’s loop, with Monday’s checks worked out again: 34 on [4, 10, 20], 0 on the empty list.
Done when both pass.
length
int length(Lst<Integer> units) — how many units there are. length(Lst.of(4, 10, 20)) is 3.
Done when two checks pass, one on the empty list.
largest
If you are done, here are two more.
int largest(Lst<Integer> units) — the largest unit, and 0 for the empty list. Math.max(a, b) is the larger of two numbers.
Done when checks pass with the largest first, with it last, and on the empty list.
countOutlined
int countOutlined(Lst<Integer> units) — how many units are outlined: 10 and up. The loop’s body has a question in it: week 4’s count-outlined, in Java.
Done when checks pass on [4, 10, 20], on [4, 7] and on the empty list.
3. Before the break: save to GitHub
Everyone, before the break.
In IDEA: Git → Commit… (Ctrl+K). Tick your files, write a line saying what you did, then Commit and Push… and Push. Then open your repository on GitHub and check that the commit is there.
If the push is refused, leave it for the end of class: your work is on this machine either way. The same project at home, and what to do when a push is refused: Git and GitHub at home.
4. copy as a loop
Write your prediction in the Journal before anyone runs anything.
Monday’s copy built the same list again, one link at a time, with a switch. Here is our first attempt at translating it into a loop form.
void main() {
IO.println(copy(Lst.of(1, 2, 3)));
}
// TODO: we wish it to return the same list, rebuilt
Lst<Integer> copy(Lst<Integer> units) {
Lst<Integer> made = new Lst.Empty<>();
Lst<Integer> todo = units;
while (todo instanceof Lst.Link(var u, var rest)) {
made = new Lst.Link<>(u, made);
todo = rest;
}
return made;
}What does it print?
[list: 3, 2, 1]. The loop meets 1 first and puts it in front of nothing; then 2 in front of that; then 3 in front of both, so the first element in ends up last. Monday’s copy put each element in front of the copy of its rest, which was built first, so the order held. For + the order of a walk did not matter; for building a list it does. The function is not a copy, so it gets its real name below: backwards.
5. Building lists with a loop
Pairs, the same way, in Walks.java.
backwards
Lst<Integer> backwards(Lst<Integer> units) — section 4’s loop, under its real name. backwards(Lst.of(1, 2, 3)) is [list: 3, 2, 1].
Done when two checks pass, one on the empty list.
copy
Lst<Integer> copy(Lst<Integer> units) — the same list, in order, with no switch. What comes out backwards twice comes out in order.
Done when Check.is(copy(units), units) passes, and the empty list gives the empty list.
outlined
Lst<Integer> outlined(Lst<Integer> units) — the outlined units only, 10 and up, as a loop with a question in its body. It comes out backwards too. Decide what to do about that, and say so in the // line.
Done when checks pass on [4, 10, 20], on [4, 7] and on the empty list.
copies
If you are done, here is one more.
Lst<String> copies(int n, String x) — n copies of x, as a loop: no list to walk, so a number counts instead. copies(3, "green") is [list: green, green, green], and copies(0, "green") is the empty list.
Done when both checks pass.
6. A loop that never stops, and a loop with no list
Keyboards stop.
Section 1’s total, with one line left out:
int total(Lst<Integer> units) {
int sum = 0;
Lst<Integer> todo = units;
while (todo instanceof Lst.Link(var u, var rest)) {
sum = sum + u;
}
return sum;
}What does total(Lst.of(4, 10, 20)) do?
It never comes back: todo is never changed, so the condition is true every time round, and the body adds 4 forever. The red square in IDEA stops it. Java checked that Monday’s switch had both of its cases; nothing checks that a loop ends. A loop stops when its condition turns false, and this one’s never does. A call on rest always arrived, because rest is shorter; a loop arrives only if its body moves todo on.
The reading’s first loop has no list in it at all. Summer.java adds up 1 + 2 + ... + n:
Nothing plays the part of todo. What changes each time round, and what does the condition look at?
7. Loops over numbers
Pairs, the same way, in Walks.java.
sumTo
int sumTo(int n) — 1 + 2 + ... + n, the reading’s Summer without the keyboard input: sumTo(100) is 5050, and sumTo(0) is 0.
Done when both checks pass.
countDigits
int countDigits(int n) — how many digits n has, for n from 0 up: countDigits(2026) is 4, countDigits(7) is 1, and countDigits(0) is 1. n / 10 drops the last digit.
Done when all three pass.
doublings
If you are done, here are two more.
int doublings(int start, int limit) — how many times start doubles before it passes limit: doublings(1, 100) is 7, and doublings(100, 50) is 0. Then, without running it: what does doublings(0, 100) do, and why?
Done when both checks pass and you can say what the third call does.
fromDigits
int fromDigits(Lst<Integer> digits) — the number the digits make: fromDigits(Lst.of(1, 2, 3)) is 123, and no digits is 0. Quiz 6’s fold (s, d) -> s * 10 + d, as a loop over the list.
Done when both checks pass.
8. Before you leave: save again
As before the break, in section 3: commit, push, and check that the commit is on GitHub.
9. Before Monday
A10 is due Tuesday, November 10. The reading, [CU] 6.1 — while Loops, is due before Monday’s class, and Quiz 7 is on it.