richw@ada-uts.UUCP (10/18/85)
This note is not really meant to be a response to anything, although it stemmed from the discussion of garbage collection & efficiency in LISP. First of all, I don't know of any features of any languages which are "inherently" expensive to implement, regardless of the machine architecture. For instance, ANY algorithm that takes advantage of the random-access of memory (i.e. order(1) time to fetch from memory) on most computers will have a factor of N increase in execution time when implemented on a Turing machine. Remember this when flaming about the wonder of LISP because of the speed of LISP- machines; if only there were FORTRAN-machines :-) (BTW it'd be nice to see a LISP implementation that used one of the incremental garbage collection algorithms I've been hearing about; be nice for any GC'ed language, e.g. CLU & Smalltalk, too) I also think that, like time/space tradeoffs in algorithm design, there are "abstraction/implementation-difficulty" tradeoffs in language design. That is, the more high-level abstractions provided by a language (e.g. GC), the harder it is to come up with a relatively efficient implementation (compiled or interpreted) of the language. In general, this is a result of the fact that a high-level, general feature provided by a language has to be efficient in ALL possible uses in order to compete with lower-level, tuned implementations. As an example, you could probably write a program using explicit memory allocation/ deallocation that would beat the pants off the same program if it used automatic storage management. But, then again, the former program would be much more tedious to write. I use this argument as a defense to critics of CLU, which I feel provides one of the most useful high-level constructs (iterators) of any language. I am willing to pay the price (which can actually be small) for this step towards more abstract languages. Remember that if a higher-level construct really costs in execution time, the lost time may be made up in program development time! Comments ? -- Rich Wagner
shebs@utah-cs.UUCP (Stanley Shebs) (10/22/85)
In article <15100004@ada-uts.UUCP> richw@ada-uts.UUCP writes: >First of all, I don't know of any features of any languages which are >"inherently" expensive to implement, regardless of the machine >architecture. Right, because any expensive feature can be done directly in hardware! :-) But simply compiling a call to "(sort x)" into "SORT (X)+,0" doesn't mean that the sorting won't still be O(n log n)... >(BTW it'd be nice to see a LISP implementation that used one of the >incremental garbage collection algorithms I've been hearing about; >be nice for any GC'ed language, e.g. CLU & Smalltalk, too) All Lisp Machines that I know of use incremental GC. >I also think that, like time/space tradeoffs in algorithm design, >there are "abstraction/implementation-difficulty" tradeoffs in language >design. That is, the more high-level abstractions provided by a language >(e.g. GC), the harder it is to come up with a relatively efficient >implementation (compiled or interpreted) of the language. ... > >I use this argument as a defense to critics of CLU, which I feel provides >one of the most useful high-level constructs (iterators) of any language. >I am willing to pay the price (which can actually be small) for this >step towards more abstract languages. Remember that if a higher-level >construct really costs in execution time, the lost time may be made up >in program development time! >-- Rich Wagner I personally think that the argument for "reducing development time" is a red herring. In a real software engineering environment, people spend their days reading and modifying existing code, not developing it. The advantage of higher-level constructs is that they can be understood more easily and modified more safely. CLU wins in some of these respects, but it has little advantage over a modern Lisp style. The idea of tradeoffs in language implementation is a very interesting one. I have studied the possibility of mechanizing decisions about tradeoffs, but the state of the art is still too primitive to really do it yet... stan shebs
richw@ada-uts.UUCP (10/28/85)
>> First of all, I don't know of any features of any languages which are >> "inherently" expensive to implement, regardless of the machine >> architecture. (me) > > Right, because any expensive feature can be done directly in > hardware! :-) But simply compiling a call to "(sort x)" into > "SORT (X)+,0" doesn't mean that the sorting won't still be O(n log n)... > (stan shebs) Apparently my original point about Turing machine implementations increasing the run-time order of an algorithm didn't sink in. YES, expensive features can be done in hardware. The proof that I know of that no sort can run faster than O(n log n) is based on an analysis of possible decision trees (i.e. any comparison-based sort will have a decision tree with n! leaves, so must be O(n log n) depth, or something like that -- check some algorithms text for the details). The important point is that this proof relies on assumptions about ARCHITECTURE. It assumes that more than one comparison will NOT be done at the same time. Next time you come across an algorithms text, think twice why they talk so much about RAM (random-access machines). I believe that one can find the N-th highest number in an unsorted list in less than O(n log n) time (I'd have to check my algorithms books to make sure, but...) Throw n different processors at an unsorted array, one looking for the first highest, the second looking for the second highest, etc. Have these processors work concurrently. Voila! Look, I'm no algorithms expert. But separation of language issues from architectural issues from implementation issues is RARELY done and I'd like to see people be more careful about doing so. > ... The advantage of higher-level constructs is that they can be > understood more easily and modified more safely. CLU wins in some > of these respects, but it has little advantage over a modern Lisp > style. (stan shebs) Comparing Lisp(s) and CLU is a little like comparing oranges and apples. CLU is more type-safe (because all type errors are uncovered before run-time). Lisp in more flexible and more extensible. CLU is more readable (in my opinion -- I shudder to think of the inane flames I'd have to fend off if I dared claim LISP was unreadable). Lisp is easier to learn. And so on. Neither is a "better" language. BTW, it is also hard to even judge LISP as a language because of all of its variants: Common Lisp, MacLisp, Scheme, McCarthy's original Lisp, Lisp with flavors (whatever its name is), etc. I've found that any statement I make to criticize Lisp can be countered with "but that's not a problem in <variant>-Lisp!". This is just a manifestation of Lisp's extensibility -- great! But extending Lisp to tailor it to particular needs doesn't make Lisp any better. How is extending Lisp any better than implementing generally useful procedures and/or data-abstractions in CLU? To me, they're both programming. Unfortunately, when people write nifty stuff for their Lisp, they have this need to name the result after their dog, grandmother, or favorite composer. If Franz Liszt can get his own language, why can't Richard Wagner? That's what I wanna know... :-) -- Rich Wagner P.S. Apologies to people that have reasonable respect for Lisp(s). After 5 years of listening MIT Lisp disciples rant and rave without knowing better triggers certain reflexes... They're almost as bad as those cock-sure CLUsers :-)
george@mnetor.UUCP (George Hart) (11/01/85)
In article <15100007@ada-uts.UUCP> richw@ada-uts.UUCP writes: >YES, expensive features can be done in hardware. The proof >that I know of that no sort can run faster than O(n log n) >is based on an analysis of possible decision trees (i.e. any >comparison-based sort will have a decision tree with n! leaves, >so must be O(n log n) depth, or something like that -- check >some algorithms text for the details). The important point >is that this proof relies on assumptions about ARCHITECTURE. >It assumes that more than one comparison will NOT be done at >the same time. Next time you come across an algorithms text, >think twice why they talk so much about RAM (random-access machines). > >I believe that one can find the N-th highest number in an >unsorted list in less than O(n log n) time (I'd have to check >my algorithms books to make sure, but...) Throw n different >processors at an unsorted array, one looking for the first >highest, the second looking for the second highest, etc. >Have these processors work concurrently. Voila! I, too, should probably consult an algorithms book but assuming concurrent Von Neumann processors: Seems like the nth processor would still have to sort the first n numbers from a list of N and at least look at the remaining N-n numbers (they can be discarded if they are higher than the current nth number). The first and last processors are special cases because looking for the min and max numbers in a list is a O(N) operation (I think). They only need to look at each list item once. But the 2 to N-1th processors still have to work in something close to O(n log n) time. Wouldn't it be faster to partition the list, have each processor work on a sublist and merge the results? Given m processors and a list of N numbers, this would be a O(N/m log N/m + K) operation where K is the time required to merge m sorted lists of N/m numbers. Where is Knuth when you need him......:-) -- Regards, George Hart, Computer X Canada Ltd. UUCP: {allegra|decvax|duke|floyd|linus|ihnp4}!utzoo!mnetor!george BELL: (416)475-8980
franka@mmintl.UUCP (Frank Adams) (11/02/85)
[Not food] In article <15100007@ada-uts.UUCP> richw@ada-uts.UUCP writes: >Apparently my original point about Turing machine implementations >increasing the run-time order of an algorithm didn't sink in. >YES, expensive features can be done in hardware. The proof >that I know of that no sort can run faster than O(n log n) >is based on an analysis of possible decision trees [...] >The important point >is that this proof relies on assumptions about ARCHITECTURE. >It assumes that more than one comparison will NOT be done at >the same time. Next time you come across an algorithms text, >think twice why they talk so much about RAM (random-access machines). > >I believe that one can find the N-th highest number in an >unsorted list in less than O(n log n) time You can. >Throw n different >processors at an unsorted array, one looking for the first >highest, the second looking for the second highest, etc. >Have these processors work concurrently. Voila! Actually, the proof relies on only being able to do a finite (bounded) number of comparisons at a time. In practice, you only have a finite amount of processing power available. Of course, in practice, you only have a finite number of objects to sort, too. So, at least theoretically, you have a valid point. But I know of no machine with more than ~100 processors, whereas it is not uncommon to have ~100,000 items to be sorted. Given those kind of numbers, sorting is O(n log n). (By the way, if you have n processors to sort n numbers, sorting is O(log n). Just do a shell sort.) Frank Adams ihpn4!philabs!pwa-b!mmintl!franka Multimate International 52 Oakland Ave North E. Hartford, CT 06108
richw@ada-uts.UUCP (11/06/85)
>>> I believe that one can find the N-th highest number in an >>> unsorted list in less than O(n log n) time... (me) > Seems like the nth processor would still have to sort the first n > numbers from a list of N and at least look at the remaining N-n numbers > (they can be discarded if they are higher than the current nth number). > > The first and last processors are special cases because looking for the > min and max numbers in a list is a O(N) operation (I think). They only > need to look at each list item once. But the 2 to N-1th processors > still have to work in something close to O(n log n) time. (George Hart) Well, I finally did something I should've done a long time ago. The k-th highest number in an an unsorted list of n numbers be found in O(n) time. Non-intuitive, I agree, but "will wonders never cease". See Aho, Hopcroft & Ullman's "Data Structures & Algorithms", Addison-Wesley, 1983, pp. 286-290. In particular, see section entitled "A Worst-Case Linear Method for Finding Order Statistics", p. 287. > Wouldn't it be faster to partition the list, have each processor work > on a sublist and merge the results? Given m processors and a list of N > numbers, this would be a O(N/m log N/m + K) operation where K is the > time required to merge m sorted lists of N/m numbers. (George Hart) Seems like O(N log N) to me. -- Rich Wagner