Scheme vs. Commmon Lisp(philip.greenspun.com)
philip.greenspun.com
Scheme vs. Commmon Lisp
http://philip.greenspun.com/bboard/q-and-a-fetch-msg?msg_id=0006XQ
26 comments
> It's strange that nobody in this story seemed interested in studying why the program crashed.
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...
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...
Yep, I actually misread "thrashed" as "crashed".
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.
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 main point is that Common Lisp is better than Scheme when you need to get things done. Scheme may be more elegant, but it's not developed with a focus on practical utility (i.e. no sort function in the standard).
That's one interpretation, but Greenspun never says what happened when he tried to use the correct function; after all, his Scheme program seems to have been complete at one point, which means that rewriting in Lisp was not more "practical" as such.
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).
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).
[deleted]
Seeing the title I was ready for a good flame, but found implementation-specific nonsense instead. From the 90s.
I note how time flies: sorting 300,000 phone numbers took 30 minutes.
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.
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.
Yes, a trie sort is one kind of radix sort. However, a trie is very far from minimal memory usage. Minimal memory usage for 300 000 (USA) phone numbers is about 1.5 megabytes, 5 bytes per number. A straightforward Patricia trie in C on a 32-bit machine is going to need minimally 16 bytes per number, about three times as much, 4.5 megabytes. If you're boxing each number, that's going to double your memory usage.
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.
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.
I'm impressed with all your math and algorithm knowledge.
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.
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.
> I'm impressed with all your math and algorithm knowledge.
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.
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.
Why were they all trying to draw conclusions without any hard data? They were guessing based upon the offhand observation that the program "just thrashed." The first step should have been to profile the program.
"Thrashed" means it was using too much memory. AFAIK MIT Scheme doesn't have a memory profiler even in 2011. Memory profilers are actually hard.
This is a great approach to writing a custom reader:
http://www.pipeline.com/~hbaker1/Prag-Parse.htmlThat parse-int is 3x slower than (read) at parsing integers on sbcl
Whoa that's awesome. You should submit that on its own.
I don't get it. Sussman says Lisp can't handle it, need to use C, Greenspun proposes to use Common Lisp instead, then Sussman insists Lisp can do it.
Can someone explain how I've misread it?
Can someone explain how I've misread it?
Sussman says Lisp can't do it, need to use C; Greenspun proposes Common Lisp; Sussman says that if that's true (if CL can do it but Scheme can't), then Scheme has been a waste of time (an odd conclusion IMO); Greenspun proves that CL can do it; Bill Rozas points out that the problem is in Scheme's inefficient reader implementation, not an inherent problem with Scheme itself.
Let's see if I have this right. I could be wrong about the details here:
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?
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 initial purpose of Scheme was to implement Hewitt's Actor model in Lisp. Steele and Sussman realized that "actors" were the same as lexical closures [1].
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
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
I'm curious about what MIT Scheme's reader was doing wrong at the time, and whether or not it's been fixed. Does anyone know? Are most Scheme readers equally bad?
This story takes place in Fall 1992 ( http://philip.greenspun.com/bboard/q-and-a.tcl?topic_id=27&#... ) so I'd be really surprised if MIT Scheme hasn't fixed it.
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.
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.
Aha, thanks for the metadata. I'm surprised my 1992 date was so right-on; I'd given it two-year error bars.
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.
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.
Thanks for the info. One of the commenters in the OP mentioned that the reader in MIT Scheme was still buggy/slow in 1998, but I've been having trouble finding any MIT Scheme releases that are that old. I've never had any trouble with any Scheme reader, but then again I've never used one on pre-1998 hardware!
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.