PART II

Uh, my padawan learner, you need a little more, and I will outline some 'principles' that actually have some lasting value:

Some major events in programming language design were in the 1950s -- Fortran (arrays, IF statements, and loops), Cobol (hierarchical data structures, IF statements, and loops), Algol (nice source code nesting, name scoping, and call by reference, value, and name, that last one a bit amazing), APL (clever things with arrays and a very sparse syntax -- interpretive), and LISP (a programming language that can examine and change its source code as it runs, with too many parentheses, interpretive).

Then, for icing on that cake, the 1960s were the 'golden age' of programming language design. So, there was PL/I (borrowed from Fortran, Cobol, Algol, and a little from assembler; had some exceptional condition handling NICELY connected with storage management and task management) and Algol 68 (oops, I never learned it!). Somewhere in or near there was C, Pascal, Ada, and Simula.

'Object-oriented' programming (OOP)? Given a language with aggregates, e.g., Fortran arrays and/or Cobol data structures, memory pointers, and dynamic memory allocation, the basics of OOP were immediately obvious and commonly reinvented by any programmer who ever hit a keyboard. IBM had it in microcode in the early 1970s.

Fortran? It didn't have pointers, but after a few lines of assembler it did! Another way was just to have a COMMON block (that is, an 'external' name, that is, 'resolved' by the linkage editor) with one array and use array addresses as memory pointers. If need a little more for manipulating addresses, then write a few, very short assembler routines.

Dynamic memory allocation? Not a lot new there. Actually, for each power of 2, have a root of a chain of pointers for free space of size that power of 2. So, an array of 64 pointers each 64 bits long should be sufficient for a while!

Then, roughly, if want some memory of size m where 2^(n - 1) < m <= 2^n, then go to the root for size 2^n and allocate the first block on the chain and correct the chain. If there is no free block of memory on that chain, then for some k > n allocate a block of size 2^k, use that memory to put its blocks of size 2^n on the chain, and allocate one of those. Can also slightly modify this scheme to free the block of size 2^k when it is empty of blocks of size 2^n. The scheme is fast and easy to implement and especially effective on a virtual memory computer where can get a lot of page alignment and where the 'wasted' free space is mostly just disk space.

Garbage collection (that is, compress out holes)? Not a lot new: Keep references and then move the memory and update the references. Can have some advantages for long running, complicated, production software but has a well deserved reputation for being slow. So far Microsoft's implementation seems to be at least reasonably fast.

'Collections'? Use AVL trees as in the first edition of Knuth's 'The Art of Computer Programming'.

Hashing? Don't miss extensible hashing!

C? A toy language written at Bell Labs for word whacking and so small the compiler could run in 8 KB or 5 KB or some such of main memory. It was so lacking in features that the usual fix-ups people did for OOP were eventually provided in a pre-processor called C++.