Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #402877
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: AVL tree insertion - programming exercise |
| Date | 2026-10-10 15:27 +0200 |
| Organization | A noiseless patient Spider |
| Message-ID | <11adef7$1ol9b$1@dont-email.me> (permalink) |
| References | <86ece2kppv.fsf@linuxsc.com> <11aaimc$n0f0$2@dont-email.me> <11aan7c$ki0$1@reader2.panix.com> <11aasbg$r60s$1@dont-email.me> <11abge0$dkj$1@reader2.panix.com> |
On 09/10/2026 21:48, Dan Cross wrote: > In article <11aasbg$r60s$1@dont-email.me>, > David Brown <david.brown@hesbynett.no> wrote: >> On 09/10/2026 14:38, Dan Cross wrote: >>> In article <11aaimc$n0f0$2@dont-email.me>, >>> David Brown <david.brown@hesbynett.no> wrote: >>>> On 09/10/2026 12:43, bart wrote: >>>>> [snip] >>>>> This 'MIX' language was something that astonished me even then. Not only >>>>> was it assembly that would totally obscure whatever algorithm was being >>>>> expressed, but it was a weird made-up assembly with unusual byte and >>>>> word sizes. >>>> >>>> Indeed. When I first saw it, I was familiar with several 8-bit >>>> assemblies (6502, Z80, 8085) and some 32-bit ARM assembly, and had read >>>> books on the 68000 family and MIPS. MIX was, to me, absurd. To be >>>> fair, the computer world was not nearly as consolidated in 1962, but I'm >>>> sure it looked fairly odd even by the standards of the time. >>> >>> If one were coming from the world of early 1960s mainframes, it >>> would perhaps be less astonishing. >> >> It would undoubtedly have been less astonishing in 1968 (when the first >> book was published) than in 1991 (when I first saw it), but I would have >> thought that even people familiar with 1960's mainframes would see it as >> strange to use a limited and highly specific artificial assembly that >> matched poorly with existing systems. > > That's the thing: I don't know that it did match poorly against > many of those systems. Word oriented machines, with word sizes > that were not powers-of-two, abstruse IO instructions; all of > that was fairly common back then. True, the IBM 360 had bucked > that trend and would set the precedent for what came later, but > that hand't happened yet. > You misunderstand me, I think. Yes, cpus had widely varying architectures, word sizes, data representations, etc., and could have instructions dedicated to particular hardware devices - and if all else failed in your code, a "halt and catch fire" instruction. It's not so much that MIX matched poorly to existing systems - they all matched poorly to each other. Implementing an algorithm on different processors' assemblies meant figuring out how to make it work with that particular word size, or how to make efficient use of the particular indexing registers and addressing modes that the cpu used. Translating from one assembly to another on a radically different architecture means two steps - you first have to figure out what the original code is really trying to do, and abstract away from the messy implementation details. Then you have to fit it into the new architecture, and add the new messy implementation details. So by using MIX, rather than a higher level, more abstract pseudo-code, anyone trying to use the code in the book on a real cpu has to do twice the work. > Moreover, assembly language programming for applications was > still common. Using assembler would have had a lot of reach, > even if it's a fairly opaque way to present algorithms. > Sure, assembly was very commonly used for applications - and for a long time afterwards. It's a major reason why the computing world is dominated by the polished turd that is the modern x86 processor - translating assembly programs into anything else is difficult, expensive and risky, so it is rarely done. >> I am sure people were already >> familiar with the pain of converting code written in assembly for one >> system into assembly for a very different system - the only advantage of >> the MIX code was that it was equally useless to everyone, and favoured >> no one! > > Ha; great description. But had he chosen Burroughs, or IBM 360, > or PDP-6, or the GE-635, or whatever else, it would have been > seen as favoring a particular vendor (and therefore irrelevant > to those using other machines) or too specific to be considered > general. I can fully understand neutrality here. He may even have wanted to avoid favouring one existing high-level language for another. But the guy was pretty smart - he could easily have invented his own hypothetical high-level language to use instead of such a low-level one. > >>> Unfortunately, he is quite adamant about this. He truly >>> believes that the best way to understand how an algorithm works >>> on a computer is to see it at the instruction level. >> >> Then he could easily have invented a machine that is powerful enough for >> the details not to matter, and not need describing. The number and size >> of registers should not matter in any way for understanding algorithms. > > Perhaps? > > I suspect that he felt that he _did_ come up with a machine > powerful enough to describe what he wanted, yet not so abstract > that one couldn't see one's way to implementing on the local > CPU. He wasn't writing for the home computer user or hobby > programmer, as home computers as we know them were yet to be > invented. He was writing for people working in a computer > center running programs on slow machines that filled a large > room, and likely doing so on punched cards, possibly in > assembler. We can look at MIX now (or even in the early 1990s) > and say, "huh, that's weird..." but in 1968 it probably would > not have raised so many eyebrows among its intended audience. > >>> Other books exist that are better references for most people; >>> certainly for most programmers: >>> >>> * "Introduction to Algorithms" by Cormen, Leiserson, Rivest, >>> and Stein is a standard. >>> * Sedgewick's books in C, simply titled, "Algorithms" are pretty >>> good, though his code style is slightly idiosyncratic. Now in >>> its 4th Edition, he has switched to Java and taken on a >>> coauthor (Kevin Wayne). >>> * "Algorithms", by Dasgupta, Papadimitriou, and Vazirani is a >>> wonderful book that, I think, strikes a nice balance between >>> formality and utility. >>> * I am rather partial to Skiena's work, "The Algorithm Design >>> Manual." >>> * "Data Structures and Their Algorithms" by Lewis and Denenberg >>> is a bit dated, but very accessible; examples are presented in >>> a Pascal-like pseudocode. >>> * "Data Structures and Algorithms" by Aho, Hopcroft, and Ullman >>> is a nice book. Be careful not to confuse it with Aho and >>> Ullman's, "The Design and Analysis of Computer Algorithms", >>> however; the latter is far denser and intended for academics >>> studying the fundamental properties of algorithms. >>> * "Algorithms + Data Structures = Programs" and the later >>> revision, "Algorithms & Data Structures", by Wirth, are >>> similarly dated, but still very nice. >>> * "Purely Functional Data Structures", by Okasaki; I include >>> this just because I think that it is fun. >> >> My bookshelves are too scattered for me to easily see what I have. But >> I am not convinced that books are good references at all these days, for >> most purposes. They are, however, still good for study if you are doing >> courses or really learning a subject. > > Oh? Nowdays we have far more available resources, so I can see > how one wouldn't necessarily reach for a book the way one would > have in days past, but what do you see as the alternative? > I don't know that there is one right answer - it depends on the depth you want to go into, how specialist the topic is, and what you are trying to get out of it all in the end. And it depends on how you personally want to learn. For deeper study and for more specialist topics, books are still the top choice for me. And I much prefer to read books than websites over breakfast. But if I want a reference or refresher on AVL trees (to pick a random topic :-) ), my first port of call is Wikipedia. If that is not enough, I might be looking for videos - there's plenty around that can give nice animations to help you understand what is going on, from five minute quick introductions to hour-long lectures. I'd look for sample code in a high level language - typically Python, but it might be interesting to look at implementations in Haskell or other significantly different languages. There are webpages full of explanations of them, and comparisons to other tree structures. And there are online courses for those looking for more academic treatment of data structures and algorithms. The internet is full of resources like this. Of course the quality is varied - you definitely want to look at more than one site to get a balanced view, and to minimise the risk of missing something important. But for technical and non-controversial subjects like this, you are going to be fairly safe with Wikipedia and a google search. >>> Did Knuth err using MIX and then MMIX for TAOCP? Perhaps; I do >>> think that neither Fortran nor Lisp would have been appropriate >>> choices; Algol perhaps. Other authors around that time or >>> slightly later either adopt a more mathematics-inspired >>> pseudonotation (Dijkstra; Hoare) algolish pseudo-code (Aho et >>> al), or a language of their own design (Wirth). >> >> As Hoare was the head of department when I was at university, and >> therefore very influential in how we were taught, I am of course partial >> to his style of notation and think that would have been the best choice! > > Could be! I've always enjoyed the notation he came up with for > CSP, for example. > I wonder how CSP is taught now that people wave bank cards or mobile phones at vending machines instead of inserting coins... (There's a fun family of microcontrollers with CSP at their heart from XMOS.)
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-06 23:08 -0700
Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-07 15:25 +0200
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-07 12:13 -0700
Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-07 21:28 +0200
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 05:31 -0700
Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 11:12 +0200
Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 11:12 +0200
Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-07 20:10 -0500
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 05:56 -0700
Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-08 15:09 -0500
Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-08 22:56 +0200
Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-08 17:29 -0500
Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 09:56 +0200
Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 01:39 +0200
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-09 00:03 -0700
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 23:53 -0700
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 10:34 +0200
Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 12:27 +0200
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 12:59 +0200
Re: AVL tree insertion - programming exercise bart <bc@freeuk.com> - 2026-10-09 11:43 +0100
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 13:20 +0200
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 12:38 +0000
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 16:05 +0200
Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 17:54 +0200
Re: AVL tree insertion - programming exercise Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-10-10 10:38 +0800
Re: AVL tree insertion - programming exercise ram@zedat.fu-berlin.de (Stefan Ram) - 2026-10-10 03:12 +0000
Re: AVL tree insertion - programming exercise Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-10-10 04:44 +0000
Re: AVL tree insertion - programming exercise "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-10-10 14:12 -0700
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 19:48 +0000
Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-09 23:18 +0000
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 15:27 +0200
Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-09 17:47 +0300
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 16:48 +0000
Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 19:08 +0300
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 18:29 +0200
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 17:44 +0000
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 23:22 +0200
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 17:43 +0000
Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 20:35 +0200
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 19:36 +0000
Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 22:08 +0200
Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:21 +0300
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 20:55 +0000
Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-10 20:22 +0000
Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:32 +0300
Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-11 15:24 +0000
Re: AVL tree insertion - programming exercise Bonita Montero <Bonita.Montero@gmail.com> - 2026-10-10 19:40 +0200
Re: AVL tree insertion - programming exercise Andrey Tarasevich <noone@noone.net> - 2026-10-10 12:39 -0700
Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:00 +0300
Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 22:28 +0200
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-10 19:02 -0700
csiph-web