I have recently been re-reading Wuthering Heights, for the first time in however many decades. I’m not sure what prompted me to reach the book down from the shelves, and I wasn’t sure either how I would take to it in my dotage. Isn’t it a book for the young and over-romantic? Yet I am engrossed and carried away. What passionately driven writing! Utterly extraordinary. But you knew that.
Should I be surprised that Emily Brontë’s teacher in Brussels wrote of her “She had a head for logic, and a capability of argument unusual in a man and rarer indeed in a woman …”?
Back to logic for me. And so here is the revised chapter on primitive recursive functions from GWT2, just 11 quick pages. Some from a more computer science background complained a bit about what I wrote in the previous edition (and should indeed be similarly dissatisfied with the similar treatment in IGT2). I have, in particular, tried to make the passing remarks about “for” loops and “do while” loops less misleading. Have I succeeded?
Updated (with thanks to RM for his comment).
Re footnote 1, p 56, “We are fixing the value of the function for one input in terms of its already-settled value for a smaller input: and that is not circular.” —
Would it be worth mentioning (somewhere) the similarity to proofs by induction?
p 61, “For C1 we just remark that the initial functions S, Z, and Iki are effectively computable by trivial algorithms.” —
What is the trivial algorithm for computing S? I think it can be tricky to see how this is supposed to work.
If I want to define Z in Python, for example, it is trivial:
def Z(n): return 0
But for S, I would write … what?
def S(n): return n + 1
That’s certainly trivial! It assumes we already have addition, though. Is that allowed?
p 61, “Set the variable fact to the initial value 1.”, etc —
I think it’s awkwardly worded and isn’t how a for-loop would normally be described. It’s also questionable technically, because it describes a loop that always happens at last once. That’s not how for-loops work in Basic or in any other language I can remember right now. For a for-loop, the ‘are we finished’ test should happen before the body of the loop.
(I thought that had been cleared up last time (or earlier), so that zero iterations were allowed. The old version definitely does allow it: see footnote 4, p 61.)
For- and while-loops that have the test before the loop body are used far more in programming that ‘do-while’ loops that have the test at the end. I’d be worried about subtle bugs in end-test loops, especially if they had a syntax that normally goes with test-at-the-start loops.
I also think it’s potentially confusing to have “if y equals n then exit the loop” when the loop is to n-1.
I’m not sure it’s worth trying to rescue this if you want the more-English-like version to correspond line-by-line to the ‘snappier’ one. The old GWT didn’t have a more-English-like version, and I don’t think that lack was a significant problem.
(Minor point: if you want it to look like Basic, the ‘next’ statement should include the loop variable — so ‘Next y’ in the example.)
Re p. 56, fn: “Would it be worth mentioning (somewhere) the similarity to proofs by induction?” — yes, revised the footnote so it now at least hints at the link.
Re p. 61, top: It is enough for the trivial initial functions to be computable (if anything is!), so even the talk of trivial algorithms, if that can be misdirect, can just be dropped.
Re p. 61 bottom: Thanks in particular for this. Agreed I should have had the loop counter tested on entry rather than exit. But I think so doing can still preserve (improve!) the parallel between the more-English-like version and the Basic-style code.
I reluctant to say that talk of trivial algorithms (or similar) should be dropped. It’s just that, thinking back to when I was a student, people who normally knew what to say in proofs sometimes found it hard to work out what to say in ‘trivial’ cases. And I’m not sure myself what the algorithm for S is meant to be. Is it to use ordinary +? Should it instead use S but make a level distinction somehow?
Re the test being before the body of the loop, rather than after, so that the body might not be executed at all, I don’t know why I didn’t think of this yesterday, but it’s necessary for a correct translation of the equations. The factorial of zero, for example, is computed (using the equations) without doing any multiplications; however, if the for-loop’s test is at the end, at least one multiplication is always done.
Anyway, on p 62 (including footnote 4), you contrast bounded ‘for’ loops with ‘do while’ loops. Unfortunately, ‘do while’ normally indicates a loop with the test as the end, so that the loop body is always executed at least once. In C / Java syntax:
do { … stuff …} while (condition)
So I think it would be better to say talk of ‘while’ loops rather than ‘do while’ loops.