Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #402858

Re: AVL tree insertion - programming exercise

Show key headers only | View raw

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.

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.

>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.

>> 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?

>> 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.

	- Dan C.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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 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