8 ms·

Scheme vs. Commmon Lisp

60 points by ekm2 15y ago

rcrowley 15y ago
I/O is always the problem.
- rbranson 15y ago
  Fucking disk I/O. Get some SSDs.
nemoniac 15y ago
This is a great approach to writing a custom reader: http://www.pipeline.com/~hbaker1/Prag-Parse.html
- spacemanaki 15y ago
  Whoa that's awesome. You should submit that on its own.
- aidenn0 15y ago
  That parse-int is 3x slower than (read) at parsing integers on sbcl
meric 15y ago
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?
- rntz 15y ago
  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.
  - hapless 15y ago
    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/ 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?
    - groovy2shoes 15y ago
      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-2006public.pdf http://labs.oracle.com/projects/plrg/JAOO-SchemeHistory-2006... [2] "The Lambda Papers" http://library.readscheme.org/page1.html http://library.readscheme.org/page1.html [3] "History of T" http://www.paulgraham.com/thist.html http://www.paulgraham.com/thist.html
vessenes 15y ago
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.
- kragen 15y ago
  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.
p9idf 15y ago
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.
- kragen 15y ago
  "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.
lobster_johnson 15y ago
It's strange that nobody in this story seemed interested in studying why the program crashed. If I'm a novice programmer and I do something ambitious like reading a lot of data, and that results in a crash, then I will want to know what particular behaviour is leading to a crash: for example, if I'm using the right functions and not something that becomes pathological when used naively. 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.
- tygorius 15y ago
  > 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...
  - lobster_johnson 15y ago
    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.
groovy2shoes 15y ago
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?
- brlewis 15y ago
  This story takes place in Fall 1992 ( http://philip.greenspun.com/bboard/q-and-a.tcl?topic_id=27&topic=NE43+Memory+Project 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.
  - groovy2shoes 15y ago
    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!
  - kragen 15y ago
    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.
muyuu 15y ago
Seeing the title I was ready for a good flame, but found implementation-specific nonsense instead. From the 90s.

60 points by ekm2 15y ago

rcrowley 15y ago

I/O is always the problem.

rbranson 15y ago
Fucking disk I/O. Get some SSDs.

nemoniac 15y ago

This is a great approach to writing a custom reader: http://www.pipeline.com/~hbaker1/Prag-Parse.html

spacemanaki 15y ago
Whoa that's awesome. You should submit that on its own.
aidenn0 15y ago
That parse-int is 3x slower than (read) at parsing integers on sbcl

meric 15y ago

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?

rntz 15y ago
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.
- hapless 15y ago
  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/ 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?
  - groovy2shoes 15y ago
    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-2006public.pdf http://labs.oracle.com/projects/plrg/JAOO-SchemeHistory-2006... [2] "The Lambda Papers" http://library.readscheme.org/page1.html http://library.readscheme.org/page1.html [3] "History of T" http://www.paulgraham.com/thist.html http://www.paulgraham.com/thist.html

vessenes 15y ago

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.

kragen 15y ago
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.

p9idf 15y ago

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.

kragen 15y ago
"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.

lobster_johnson 15y ago

It's strange that nobody in this story seemed interested in studying why the program crashed. If I'm a novice programmer and I do something ambitious like reading a lot of data, and that results in a crash, then I will want to know what particular behaviour is leading to a crash: for example, if I'm using the right functions and not something that becomes pathological when used naively. 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.

tygorius 15y ago
> 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...
- lobster_johnson 15y ago
  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.

groovy2shoes 15y ago

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?

brlewis 15y ago
This story takes place in Fall 1992 ( http://philip.greenspun.com/bboard/q-and-a.tcl?topic_id=27&topic=NE43+Memory+Project 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.
- groovy2shoes 15y ago
  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!
- kragen 15y ago
  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.

muyuu 15y ago

Seeing the title I was ready for a good flame, but found implementation-specific nonsense instead. From the 90s.