Derive: Rules That Turn Inputs Into Outputs

The step that removes the recursion is to add one to both sides: $$T(n)+1=2T(n-1)+2=2(T(n-1)+1).$$ Write $U(n)=T(n)+1$. The line above says $U(n)=2U(n-1)$, so each step doubles the previous value. Unrolling $n$ times gives $$U(n)=2^{n}U(0)=2^n(T(0)+1)=2^n.$$ Subtract one: $T(n)=2^n-1$. Check the listed values: $2^1-1=1$, $2^2-1=3$, $2^3-1=7$, and $2^6-1=63$, which is the value E1.3 computes.

Now the sum. The template of section 1.3 adds a term between two whole numbers, with the term and the next value supplied as procedures. Set the term slot to $k\mapsto 2^k$ and the next slot to $k\mapsto k+1$. Running from 0 to $n-1$ produces $$2^0+2^1+\cdots +2^{n-1}.$$ To evaluate it, multiply by $2-1=1$ and telescope: $$(2-1)(2^0+\cdots +2^{n-1})=2^n-1.$$ Every interior power cancels against the double of the power before it; only $2^n$ and $-1$ survive. So the sum equals $2^n-1=T(n)$. At $n=8$ the template adds $1+2+4+8+16+32+64+128=255$, and the recurrence gives $T(8)=2\times 127+1=255$. The same template that summed the integers from 1 to 10 performs the tower count, because only its two slots changed.

(a) Each of the four inputs is a multiple of sixty. On such an input the quotient is a whole number, so keeping the whole part and taking the nearer whole number give the same result. A test built from the four rows therefore runs only on inputs where the rules coincide, and every such test passes for both. The two rules are different procedures, and the four-row table cannot tell them apart. Passing every test you can draw from the table establishes the second line of the contract on those rows; it says nothing about the rows between them, which is the fourth line at work.

(b) Let $t$ be the elapsed seconds and write $t=60q+r$ with $0\le r<60$. Round down returns $q$. Round to nearest returns $q$ while $r<30$ and $q+1$ while $r\ge 30$. The first disagreement above 60 therefore sits at $r=30$, which is $t=90$. At 90 seconds the quotient is $1.5$; round down returns 1 and round to nearest returns 2. The value 90 is not in the table, so no test drawn from the four rows can reach it. A reader who concluded "the rule is round down" from a perfect score on the four rows has made a claim the table does not support.

Number the additions from the inside out. The innermost is addition 1, the next is addition 2, and the outermost is addition $n$. Immediately before addition $k$ runs, additions $1$ through $k-1$ have finished and additions $k+1$ through $n$ have not started. That leaves $n-k$ additions waiting outside the one about to run, which is the claimed count. At $k=1$ the count is $n-1$, so the deepest point of the process has $n-1$ waiting additions. At $k=n$ the count is 0, and the process contracts.

The storage claim follows from what each waiting addition holds. Addition $j$ cannot run until the value of the smaller nest on its right arrives, and it must keep the reading on its left in the meantime. So the $n-1$ waiting additions at the deepest point hold $n-1$ readings, and the innermost addition holds the last reading, so every one of the $n$ readings is live at once. For $n=12$ that is 11 waiting readings plus the twelfth as the current operand. The looping process keeps only a counter and a running sum, which is 2 numbers, whatever $n$ is. The arithmetic performed is the same in both cases; what differs is the amount of state the process must carry. This is why a pause in the delegating process cannot be described by its variables alone: the waiting readings live in the interpreter, not in the program's names.