- Begin parsing this procedure, unless you have already begun to parse it. She who runes may rede it on all fours.
setTimeout(() => [JamesJoyce, DonKnuth].forEach(parse), 0);- Set J equal to zero; set K equal to zero; and continue to Code. [Click.]
- Begin parsing §J. Although they may lead to an exhaustive education, do not parse quotations at the beginning of the section. If too much time is spent decomposing Joyce, a person may never start chewing Knuth, Gardnering, Hofstadtering, sole sizing, jean splicing, pondering this, tilting at that, …
- Is the subject of the current subsection interesting to you? If it is, go to step 7.
- Are you almost but not quite a bona fide pupil? Enlist! True, we rather order our students about some, making them move step by step. It touches one’s sense of honor. And more than all, if previous to applying your brain to bits, you were lording your mind as master of maths. The transition is a keen one, we assure you, from master to pupil and back again.
- Finish parsing the current subsection, unless you have already finished parsing it. If you’re tired, take a nap (do not play video games or post any more pictures on Pinterest). Begin parsing the next subsection. If you are at the end of the section, go to step 16.
- Is the subsection marked with a “🍀”? If so, it presents code that uses library routines your browser might implement improperly (if at all). If your browser is illiterate, good luck! Craft a polyfill or implore Shem to pen a shim for you. Go back to step 7.
- Is your first name Word and your last name Smith? If English is all Latin to you, then go to step 10; otherwise, go to step 11.
- Parse any whimsical, wacky, wakey words we’ve used. Send us tips c/o Shaun via The Post. We’ll deposit them immediately. Once a month, we burn biting criticism in a huge bonfire. Go to step 12.
- If you see strange words that seem off by LUN, don’t automatically assume it’s yet another pun; what looks like punny prose might be just another slithery slew of Uh O, Spaghetti Os. Typette, our Canucked type Os!
- Work only the even exercises that have been assigned by your instructor in concordance with those whom you started parsing in step 2. Do not do the odd ones. If fellow-me-lad has no Mr. James Bates, then off, Jack, ye goes. Quick! Jump back to step 6. Yiz all in ’is army now meladies. Hump ye answers, Tommy, to step 13 after doin’ step 6.
- If K is not negative, and you’re sure done for, call us, Tic and Tock, The Clockette Brothers, at 1-900-TIC-TOCK and express your answers for evaluation. Speak slowly. Say your full name, place of birth, the street you grew up on, your mother’s maiden name, and the names of all your pets, past and present, so we know it’s really you. Then spell the name on and read the digits of an active credit or debit card (it doesn’s have to be yours) followed by all your PINs and passwords and the card’s validation code. Tell us the section, subsection, and exercise numbers you are calling about. For each exercise, recite the prompt from memory and expound your answer. Anecdotes and creative commentary are eligible for extra credit. Whine. Complain. Make excuses. Dog ate your homework? No problemo. Take your time. If your message is clear and everything is bug-free, you’ll receive a certificate in the mail; if you don’t, err less, use a different card and a better phone, increase K by one, then go back to the beginning of step 13. And don’t code like my brother. Don’t code like my brother.
- If you haven’t reached your cards’ limits yet, go back to step 7.
- Get another credit card if you can; otherwise, get a job and a debit card. Get another one. We know life is hard, but hey, “All this work and no pay don’t make us jack.” Now go back to step 7.
- Increase J by one.
- If J is less than or equal to 5, go back to step 4.
- Rest in peace! But to return.2 What a wonderful memory you have too! Twonderful morrowy! Straobinaire! Bene! […] All’s fair on all fours, as my instructor unstrict me. Watch! And you’ll have the whole inkle. Also, go back to step 3.
EXERCISES—First set (0–3)
-
Show that “Procedure for Parsing this Set of Pages” fails to be a genuine algorithm on at least three of Knuth’s five counts.
Not finite nor definite nor effective, perhaps no output.
See Knuth, Donald E., The Art of Computer Programming, Vol. 1 (Addison Wesley, 1973), page 465: answer 5. -
Will the variable K ever be equal to a value that prevents step 13 from being performed? Explain.
If a mathematician is keeping track of the value of K using pencil and paper, then no. If a computer is keeping track of the value of K using a fixed number of bits, then it depends on whether adding one to the maximum value that can be represented results in a negative value (due to overflow) or not. Sometimes it does, and sometimes it doesn't. It depends on the language and the data type. (If K is negative, step 13 is not performed.)
-
Replace the words “not negative” in step 13 with a word that will avert a long series of unfortunate events.
not negative → positive (assuming zero is not positive); not negative → one; etc. (Note: K is set to zero in step 3.)
- Bonus Points: Create a flow-chart to accompany “Procedure for Parsing this Set of Pages”.
Ticking away the moments that make up a dull day
Fritter and waste the hours in an offhand way.
Kicking around on a piece of ground in your home town
Waiting for someone or something to show you the way.
—PINK FLOYD, The Dark Side of the Moon: “Time” (1973)
Addendum
The advantages of flowcharts and of an informal step-by-step description of an algorithm are well-known; for a reference to a discussion of this, see The Art of Computer Programming, Vol. 1 (1973, 1968), page x. Yet a formal, precise language is needed to compose a computer program. And we often desire an actual program, not only blueprints for one.
The next set of exercises consists of coding problems representing some typical programming techniques and conundrums. It is recommended that students attempt the following exercises using whatever programming languages they like. There is no reason why a student should be afraid of learning the characteristics of more than one high-level programming language, to say nothing of low-level ones. The problems are framed using Java and JavaScript, but they can be adapted to other programming languages as well.
Prologue
On page 129 of A Skeleton Key to Finnegans Wake (New World Library, 2005) Joseph Campbell writes
[The Shem-Shaun conflict suggests that each of the brother opposites has developed only one half of his man’s nature. Shem, acutely aware of his need for assistance from the other half, has begged for help, but Shaun, unable to admit his need for the other, yet compelled to protest very elaborately his independence, has refused to collaborate and has insisted on his own unique power and right to occupy the seat of dictation. From the lower seat of Mercy, Shem forgives his brother even while castigating him with the lash of accusation. The female power clearly supports Shem’s belief that neither of the male powers is adquate by himself. In her younger, sisterly, and idealizing form, she dreams past the two brothers to an ideal which would synthesize the qualities of the two—a hero to come who would be as all-inclusive as was her father; but in her mature, motherly, and realistic form, she simply comes forward and embraces both of her quarreling sons, effecting through her unquestioning and no longer forward-looking love, not an ideal but an actual reconciliation of the brother battle—a reconciliation which does not require even that the antagonism should be resolved.
EXERCISES—Second set (4–10)
Java JavaScriptShem and Shaun wanted to impress their father by compiling a list of all the words he had ever spoken and offering him a program that prints words from shortest to longest and from longest to shortest. Together, Shaun and Shem composed the following partial program.
/** To: HCE. From: Shem and Shaun. */
public class ConcordancesRUs {
/**
* Prints words from longest to shortest, then prints
* them again from shortest to longest. Stack sizes
* are limited. This program may terminate at any time.
*/
public static void main(String[] words) {
Words.orderLongestToShortest(words);
print(words);
Words.orderShortestToLongest(words);
print(words);
}
private static void print(String[] words) {
for (String word : words)
System.out.println(word);
}
}
class Words {
/** Returns the smallest index of a longest string in list between lower (incl.) and upper (excl.). */
public static int indexOfFirstLongest(String[] list, int lower, int upper) {
// by Shem
if (list == null) return -1;
if (lower < 0) lower = 0;
if (upper > list.length) upper = list.length;
if (lower >= upper) return -1;
if (lower + 1 == upper) return lower;
final int i = Words.indexOfFirstLongest(list, lower + 1, upper);
if (list[i] == null) return lower;
if (list[lower] == null) return i;
return (list[i].length() > list[lower].length()) ? i : lower;
// by(e) Shaun
int i = lower < upper ? lower : -1;
for (int j = lower; j < upper; j++)
if (list[j].length() > list[i].length())
i = j;
return i; // (Shem was here)
}
/** Exchanges the strings in list that are at positions i and j. */
public static void swap(String[] list, int i, int j) {
final String tmp = list[i];
list[i] = list[j];
list[j] = tmp;
}
/** Swaps a longest string in list (between lower and upper) with the string at position i. */
public static void putLongestAt(String[] list, int i, int lower, int upper) {
Words.swap(list, i, Words.indexOfFirstLongest(list, lower, upper));
}
/** Arranges the strings in list in sorted order from longest to shortest. */
public static void orderLongestToShortest(String[] list) {
final int j = list.length;
for (int i = 0; i < j; i++) {
Words.putLongestAt(list, i, i, j);
}
}
/** Arranges the strings in list in sorted order from shortest to longest. */
public static void orderShortestToLongest(String[] list) {
for (int i = list.length; i > 0; i--) {
Words.putLongestAt(list, i-1, 0, i);
}
} }
/** To: HCE. From: Shem and Shaun. */
const ConcordancesRUs = Object.freeze({
/**
* Prints words from longest to shortest, then prints
* them again from shortest to longest. Stack sizes
* are limited. This program may terminate at any time.
*/
main: function (words) {
Words.orderLongestToShortest(words);
print(words);
Words.orderShortestToLongest(words);
print(words);
function print(words) {
alert(words.join('\n'));
}
}
});
const Words = Object.freeze({
/** Returns the smallest index of a longest string in list between lower (incl.) and upper (excl.). */
indexOfFirstLongest: function (list, lower, upper) {
// by Shem
if (list == null) return -1;
if (lower < 0) lower = 0;
if (upper > list.length) upper = list.length;
if (lower >= upper) return -1;
if (lower + 1 == upper) return lower;
const i = Words.indexOfFirstLongest(list, lower + 1, upper);
if (list[i] == null) return lower;
if (list[lower] == null) return i;
return (list[i].length > list[lower].length) ? i : lower;
// by(e) Shaun
let i = lower < upper ? lower : -1;
for (let j = lower; j < upper; j++)
if (list[j].length > list[i].length)
i = j;
return i; // (Shem was here)
},
/** Exchanges the strings in list that are at positions i and j. */
swap: function (list, i, j) {
const tmp = list[i];
list[i] = list[j];
list[j] = tmp;
},
/** Swaps a longest string in list (between lower and upper) with the string at position i. */
putLongestAt: function (list, i, lower, upper) {
Words.swap(list, i, Words.indexOfFirstLongest(list, lower, upper));
},
/** Arranges the strings in list in sorted order from longest to shortest. */
orderLongestToShortest(list) {
const j = list.length;
for (let i = 0; i < j; i++) {
Words.putLongestAt(list, i, i, j);
}
},
/** Arranges the strings in list in sorted order from shortest to longest. */
orderShortestToLongest(list) {
for (let i = list.length; i > 0; i--) {
Words.putLongestAt(list, i-1, 0, i);
}
} });
The brothers couldn’t agree on how to implement indexOfFirstLongest, however,
so they forked the code and went their separate ways.
Here is Shem’s implementation of indexOfFirstLongest.
// by Shem
if (list == null) return -1;
if (lower < 0) lower = 0;
if (upper > list.length) upper = list.length;
if (lower >= upper) return -1;
if (lower + 1 == upper) return lower;
final int i = Words.indexOfFirstLongest(list, lower + 1, upper);
if (list[i] == null) return lower;
if (list[lower] == null) return i;
return (list[i].length() > list[lower].length()) ? i : lower;
// by Shem
if (list == null) return -1;
if (lower < 0) lower = 0;
if (upper > list.length) upper = list.length;
if (lower >= upper) return -1;
if (lower + 1 == upper) return lower;
const i = Words.indexOfFirstLongest(list, lower + 1, upper);
if (list[i] == null) return lower;
if (list[lower] == null) return i;
return (list[i].length > list[lower].length) ? i : lower;
Here is Shaun’s implementation of indexOfFirstLongest.
// by Shaun
int i = lower < upper ? lower : -1;
for (int j = lower; j < upper; j++)
if (list[j].length() > list[i].length())
i = j;
return i;
// by Shaun
let i = lower < upper ? lower : -1;
for (let j = lower; j < upper; j++)
if (list[j].length > list[i].length)
i = j;
return i;
-
Is the “length” of the value
nullless than, equal to, or greater than the length of a non-null string of length zero? Explain.The answer depends on how the comparator—the function, method, or operator used to perform the comparison—is defined. In JavaScript, for example, the less than operator (
<) is an operator that expects two operands, either of which may be a string or the valuenull.* For JavaScript programmers, whether a string is “less than” another string depends on the definition of an alphabetical ordering that is at least associated with if not defined by the less than operator itself. Ordering strings by length is a similar sort of thing. In both cases we’re asking whether one value appears before another in an ordering that is based on some characteristic of two values, one or both of which may be the valuenull. If you have licence to define an operation that orders two values based on their respective “lengths,” then you get to make the rules. The question is, as Humpty Dumpty put it, “which is to be master—that’s all.” See Martin Gardner’s comments that begin on page 268 of our Penguin edition of The Annotated Alice, which was first published in 1965.* In JavaScript,
nullis a built-in value of type object that, paradoxically, signifies the absence of an object. Tony Hoare, who is credited with inventing the null reference, has apologized for it, calling it “my billion-dollar mistake.” -
If
wordsrefers to the array{"Hello", "World", "Goodnight", "Moon"}["Hello", "World", "Goodnight", "Moon"], what output is produced by the commandConcordancesRUs.main(words);? Assume the methods ofWordsare implemented as described by their comments.goodnight world hello moon
followed by
moon hello world goodnight
-
Implement
Words.swap. -
Implement
Words.putLongestAt. UseWords.swapandWords.indexOfFirstLongest. -
Implement
Words.orderLongestToShortest. UseWords.putLongestAt. -
Implement
Words.orderShortestToLongest. UseWords.putLongestAt. -
Which son’s implementation of
Words.indexOfFirstLongestdoes HCE prefer? Why?HCE favors Shaun’s, because Shem is to Shaun as Cain is to Abel.
There grew up beside you amid our orisons […] that other, Immaculatus, from head to foot, sir, that pure one, Altrues of other times, he who was well known to celestine circles before he sped aloft, our hansome young spiritual physician that was to be, […] but him you laid low with one hand one fine May morning in the Meddle of your Might, your bosom foe, because he mussed your speller on you or because he cut a pretty figure in the focus of your frontispecs (not one did you slay, no, but a continent!) to find out how his innards worked! (191)
(Other answers are possible but are not as good, because we’re the master—that’s all folks!)
To my mother and father—
Who told me songs were for the birds,
Then taught me all the tunes I know,
And a good deal of the words.
—KEN KESEY, Sometimes a Great Notion (1964)
