Scheme vs. Commmon Lisp
philip.greenspun.com
philip.greenspun.com
Also, from what I can tell, he ran a Lisp system that used virtual memory, which the Scheme system didn't.
It's also incredible that Sussman is reported to suggest shutting down Scheme just because of the problem in this story. And that Sussman himself (coauthor of the legendary SICP book) doesn't seem to bother studying the program.
Nothing in this anecdote makes any sense.
You are presuming the terms "never never land" and "just thrashed" refer to a crash, i.e. an abnormal termination. I read them to refer to a program that got bogged down in either unanticipated and extensive computation or abnormally slow I/O. In the context of the story the latter makes perfect sense.
What I suspect is missing from the story is something like Sussman shifting from anticipating a system problem with utilization of system resources to the realization that it was a suboptimal library routine. (That is, a problem with a solution that was the proverbial "simple matter of programming".)
Of course, in hindsight we all have perfect vision...
That doesn't really change anything, however; his program was acting abnormally, and there is nothing suggesting that anyone tried to attack the problem systematically through a process of elimination and deduction.
There's just not enough information in the anecdote, and (in my opinion) everyone comes out of it looking a bit silly because of the missing pieces.
There is nothing to be learned from this anecdote that sheds any philosophical light on Scheme vs. Lisp, life at MIT, etc. We learn that Scheme has/had a function that one should not use, and that computers used to be really dinky things. So I truly don't know why Greenspun wrote down this anecdote.
His point about the Lisp program being smaller is interesting, but still entirely anecdotal: we know nothing about the program, and for all we know, Greenspun was a Scheme novice at the time of the story.
I have a deep dislike for anecdotal "X vs. Y" stories because they don't shed any light on anything; they're just glib, cheap observations that make for a good story (albeit in this case, not that good).
in python (and yes, this cheats a bit):
nums = [random.randint(1000000000,9999999999) for x in range(0,300000)] nums.sort()
total time < 1 second on my macbook air.
As I think about it, seems like a trie would be a good solution, you can add to it as you go with minimal memory usage. When done, you can just read off the trie top to bottom.
I think he has an order-of-magnitude error: he says the 3600 was paging continuously because it was "reading a 30 megabyte file into VM", but 30 megabytes / 300k phone numbers is 100 bytes per phone number, which seems like a lot for a text file full of phone numbers. I think he had 3 million phone numbers, ten or eleven bytes each, so 30 or 33 megabytes, so building a naive trie in memory on a 64-megabyte machine is not going to work.
If you wanted to sort a 30-megabyte file of 3 million phone numbers, a machine with four 9-track tape drives, no disk, and a kilobyte or so of memory would be able to do it in 22 passes over the tapes. (Practically you'd probably need at least 12 kilobytes.) On 1970-era tape drives, running at 1.25 megabytes per second, each pass would take a little under a minute.
From the fact that the 64-megabyte RISC machine ran at 50 MIPS and was considered capable of handling "massive data sets", I'm guessing this anecdote dates to about 1992, plus or minus 2 years, which means that the machine in question probably had about a 5-megabyte-per-second SCSI disk and maybe a shared ten-megabit Ethernet. Without doing any nifty compression or anything, on a machine like that, you could easily read thirty one-megabyte chunks off the disk, sorting each one in memory before writing it to a temp file, and then merging the thirty one-megabyte chunks in a second pass. This is not too far from what GNU sort or Unix sort would have done, and it would have used a total of 120 megabytes of disk transfer, about 24 seconds. That is, it would have been CPU-limited, not I/O-limited. And you could have even done it in MIT Scheme, which was perfectly capable of reading a megabyte of numbers into memory even in 1990.
One comment; the guy responsible for scheme read posted in a comment on philg's site acknowledging that read was too slow for the described task.
As to the size of the task, interesting math. I'd bet on you being correct as to the size of the file implying more numbers.
You shouldn't be! I'm disappointed to discover that radix trees are usually relegated to a graduate-level data-structures class along with such curiosities as AVL trees, interval trees, and double-ended priority queues.
http://www.pipeline.com/~hbaker1/Prag-Parse.htmlCan someone explain how I've misread it?
Before it was called "Scheme," Sussman was writing papers about a lisp subset that could be optimized. Some folks tried to write an optimizing compiler, known as "T."
http://mumble.net/~jar/tproject/
Common Lisp was a superset of a bunch of vendor Lisp systems, even more monstrously complex than any individual vendor Lisp.
So if I follow the author: If a CL implementation was indeed faster and better-optimized than the simpler Scheme dialect, then what was the purpose of Scheme?
The Lambda Papers [2] describe the early implementation details of Scheme, and it was these papers that influenced the development of T [3].
[1] "The History of Scheme" http://labs.oracle.com/projects/plrg/JAOO-SchemeHistory-2006... [2] "The Lambda Papers" http://library.readscheme.org/page1.html [3] "History of T" http://www.paulgraham.com/thist.html
Sussman's readiness to kill the MIT Scheme project at that point indicates to me that he thought other implementations were less buggy, e.g. mzscheme (later PLT, later Racket). But admittedly I'm reading sense into the story when there might not be any. The story was written more than 5 years after it occurred, and written hastily. For example, either "300,000 phone numbers" is wrong or "30Mbyte file" is wrong.
I think that in general Philip is more interested in telling good stories than in being sure they are accurate. There is at least one example of people who claim their careers have been ruined by this attribute of his.