John West wrote:
Dr Jefyll wrote:
"Most computer applications boil down to searching and sorting."
BigEd wrote:
"I believe that virtually every important aspect of programming arises somewhere in the context of sorting or searching!" (Donald Knuth, The Art of Computer Programming, Volume 3, "Sorting and Searching")
It's worth noting that these two quotes are saying opposite things. The first is the one that people often think Knuth was saying, but if you read the preface to Vol. 3, it is clear that he was not. A bit more context makes it clear:
Knuth wrote:
The title “Sorting and Searching” may sound as if this book is only for those systems programmers who are concerned with the preparation of general-purpose sorting routines or applications to information retrieval. But in fact the area of sorting and searching provides an ideal framework for discussing a wide variety of important general issues:
How are good algorithms discovered?
How can given algorithms and programs be improved?
How can the efficiency of algorithms be analyzed mathematically?
How can a person choose rationally between different algorithms for the same task?
In what senses can algorithms be proved “best possible”?
How does the theory of computing interact with practical considerations?
How can external memories like tapes, drums, or disks be used efficiently with large databases?
Indeed, I believe that virtually every important aspect of programming arises somewhere in the context of sorting or searching!
A full exploration of sorting and searching will cover virtually everything that is important. None of those things are themselves sorting or searching.
Interesting point! This actually makes more sense
I had never understood the idea of all programs involving searching and sorting --- as I said above, this is not true for micro-controllers --- it is somewhat more plausible for desktop-computers, but still a pretty gross simplification.
So Donald Knuth was saying that studying searching and sorting allows the student to encounter most of the important aspects of programming --- that is more reasonable --- it is still not totally true though, as Donald Knuth takes a much more mathematical approach to programming than most people do (I would expect most high-school students are interested in writing a video game and have little or no interest in algorithmics).
Anyway, this thread has gone way OT. Why are we discussing Pascal?
I designed vino816 as a Forth system for the 65c816. I am not going to support quotations (anonymous nested functions) because the 65c816 lacks enough registers to have a local-frame pointer (as I said, a zero-page pointer could be used, but it would be slow). I am unlikely to implement vino816 because the chance of having any users is zilch --- if I did implement it, I would focus on supporting micro-controllers (as I said, accessing I/O ports, doing logic on data going in and out, and circular buffers) --- none of this has anything to do with Pascal, which is a desktop-computer language.
All of this discussion of Pascal seems to have started because I said that William Mensch may have been thinking of Pascal, but it would have to be a crippled version of Pascal without nested functions --- he may have been thinking of C, which is like a crippled Pascal (plus you get ugly syntax!) --- he definitely wasn't thinking about Forth.
Forth needs two stacks: a data-stack and a return-stack --- the 65c816 lacks support for a data-stack --- the X register can be used, but there is no pre-decrement or post-increment addressing-mode, so you get a lot of DEX DEX and INX INX code-sequences (as I said though; with peephole-optimization this can be reduced to some extent).
Login
Register
FAQ
Search
