Sophos Cloud Optix
Prizes are now on their way to the Sophos New Year’s Eve 2010 Crossword Competition winners.
The crossword was published in the early afternoon of New Year’s Eve, Sydney time, and although entries were accepted until 07 January 2011, a few Naked Security readers obviously decided that an NYE puzzle should be solved on NYE, and not a day later!
The outright winner was from Brisbane in Queensland, Australia, who submitted a correct solution (with no hints from me) in just over an hour.
The winner wishes to be identified only as MDB, saying, “that way, the set of people who know me will know I’m not making it up, and everyone else will be instilled with the fear that Microsoft Access has somehow become sentient and started solving crossword puzzles.”
By the way, the clue for which I received the most requests for a hint was 9 Across, “The tail of the tail of a Lisp list (4).” The answer is CDDR – not exactly a word you can guess at if you don’t already know Lisp.
I shan’t explain CDDR. You’ll have to look it up if you need to know, since there are probably readers who prefer to remain in ignorance. Lisp can do that to a person. As one of the winners noted, after labouring over that answer, “Lisp is on my list of things to learn after retirement.”
Thanks to everyone who tried the puzzle, and to the many who battled through to the end. The first ten winning entries came from:
* MDB, Queensland, Australia
* Adam, Victoria, Australia
* Ty Auvil, Washington, United States of America
* Adam Garner, Queensland, Australia
* Martin Buckley, Washington, United States of America
* Steve Baxter, England, United Kingdom
* Seb, Québec, Canada
* Ange, Baden-Württemberg, Germany
* Lee Brotherston, England, United Kingdom
* Anonymous IT Student, Singapore
Well done!
Paul, I presume you realize that CDDR belongs to the same (dated) generation of CL as CAR and CDR don't you? These days it's First, Rest, and (rest(rest x)) for readability purposes. Do they even teach people CAR and CDR these days? I'm surprised you didn't ask for "the head of the tail of the head of the tail of a LISP list" (cadadr).
Congratulations to those who attempted and completed this year's crossword!
OK, I'm going to call your bluff! Let's RTFM, shall we 🙂 From the "Revised [6] Report on the Algorithmic Language Scheme" (http://www.r6rs.org/), Section 11, Base Library, page 47.
—
11.9. Pairs and lists
A pair is a compound structure with two fields called the car and cdr fields (for historical reasons). Pairs are created by the procedure cons. The car and cdr fields are accessed by the procedures car and cdr.
—
Just like it was when I learned Lisp. CAR (Contents of the Address Register) was the machine instruction used to extract the pointer to the list head from the machine word representing the list; CDR (Contents of the Decrement Register) was used to extract the pointer to the tail of a list – not the last element of the list, but, as you say, the rest of the list.
Neither first nor rest appear in the R6 Scheme index 🙂
Neither First nor Rest appear in the R6 Scheme index because Scheme is not ANSI Common Lisp compliant 😉 If you'd said Scheme instead of Lisp, you would be almost correct.
See http://www.lispworks.com/documentation/HyperSpec/… vs http://www.lispworks.com/documentation/HyperSpec/…
CAR and CDR are used for more specific purposes now, as JohnL has commented below. Before the ANSI CL standard, the implementation was a toss-up as some of the definitions were vague. AFAIK, CDR/CDDR is never defined as tail of tail anymore.
Good – you accept the HyperSpec as a satisfactory representation of the standard, and so do I, because that's all I can find online. (I'm not going to pay ANSI $30 for a PDF of a scan of the official documentation 🙂
The entry for "rest" (on the f_rest.htm page you mention above) tells us this:
rest performs the same operation as cdr
Lest there be any doubt that this is to be interpreted to mean:
rest performs the same operation as cdr
the HyperSpec also states, rather bluntly, that:
(rest list) == (cdr list)
And the HyperSpec formally documents the use of rest like this:
Syntax: rest list => tail
I therefore think you have to permit me to conclude, according to the HyperSpec documentation for "rest", that applying rest to a list returns the tail of the list, and that rest is identical to cdr. Ergo you have to accept that cdr returns the tail of a list, too, and thus that cddr gives you the tail of the tail 🙂
Gotta love standards. They're always so, aaaaaah, standardised in their terminology.
The cddr isn't the tail of the tail, it's the list after removing the first two elements, i.e. the second part of the second dotted pair…
(1 2 3 4 5 (6 7 8))
Tail = (6 7 8)
Tail of Tail = 8
cddr = (3 4 5 (6 7 8))
if you define “the tail of a list” as “the list after removing the head”, and define “the head” as “the first element”, then tail(tail(x)) is synonymous with cdr(cdr(x)). And that’s how I’m defining tail here 🙂
That’s consistent with modern Lisp terminology. For example, in the R6 Scheme book I mention above, you will find this example code where “infinite streams” are introduced:
(define head car)
(define tail (lambda (stream) ((cdr stream))))