programming and human factors
by Jeff Atwood
What do you think the single greatest invention in computer science is? Besides the computer itself, I mean.
Seriously, before reading any further, pause here for a moment and consider the question.
I've talked before about how young so-called modern computer programming languages really are, and it bears repeating for context.
C is roughly as old as I am; FORTRAN is as old as my parents. But what about the new kids on the block? The TIOBE software TCPI metrics page provides some data on language popularity going back to the year 2001. Consider the tender age of many of the newest, hippest programming languages:
Ruby is barely a teenager. JavaScript and PHP haven't even hit their teens yet.
For all our talk about fancy new programming language features, I sometimes think we forget the one fundamental building block underlying all of them: the humble routine. Take it from Steve McConnell, who urges us to Use Routines, Routinely:
Aside from the invention of the computer, the routine is arguably the single greatest invention in computer science. It makes programs easier to read and understand. It makes them smaller (imagine how much larger your code would be if you had to repeat the code for every call to a routine instead of invoking the routine). And it makes them faster (imagine how hard it would be to make performance improvements in similar code used in a dozen places rather than making all the performance improvements in one routine). In large part, routines are what make modern programming possible.
If you're not old enough to remember life before routines, I thought James Shore had a great example of the stark difference in his excellent article Quality With a Name:
Before structured programming:
1000 NS% = (80 - LEN(T$)) / 2 1010 S$ = "" 1020 IF NS% = 0 GOTO 1060 1030 S$ = S$ + " " 1040 NS% = NS% - 1 1050 GOTO 1020 1060 PRINT S$ + T$ 1070 RETURN
After structured programming:
public void PrintCenteredString(string text) {
int center = (80 - text.Length) / 2;
string spaces = "";
for (int i = 0; i < center; i++) {
spaces += " ";
}
Print(spaces + text);
}
The humble routine is the backbone of all programming in any modern language. I'm sure you're the very model of a modern programmer, so I won't bore you with a long explanation of why routines are a good idea. The original 1998 IEEE McConnell article covers the rationales behind routines quite well. There's also a greatly expanded version of that material in Chapter 7 of Code Complete 2.
Routines are so fundamental to today's programming that they are essentially invisible. That's the problem with routines: they only take a minute to learn, but a lifetime to master. If bad unstructured programming was possible, so is bad structured programming. You can write FORTRAN in any language. Wrestling with the ineffable essence of a routine is, almost to a first approximation, what programming now is:
Good programmers -- regardless of whatever language they happen to be working in -- understand the importance of crafting each routine with the utmost care. The routines in your code should be treated like tiny, highly polished diamonds, each one more exquisitely polished and finely cut than the last.
I'll grant you this isn't a particularly deep insight. It's not even original advice. But if you believe, as I do, in constantly practicing the fundamentals, you'll never stop mastering the art of writing the perfect routine.
It is, after all, the single greatest invention in computer science.
of course old languages, still in use, use routines. As somebody who works using java, VB .Net and COBOL [http://en.wikipedia.org/wiki/COBOL#History_and_specification] routines are used in all although sometimes called different things.
Stephen on June 7, 2008 2:16 AMJeff, you often talk about raising the abilities of the mass of average developers. By that standard, there is no development more important then the Relational Database and SQL. It's basic theory and tools are still in use after nearly 40 years, and it's at the heart of almost every major system.
Where are all the alternatives to databases, like languages have alternatives? Where are all the new frameworks and platforms? The storage and retrieval strategies? The theoretical work?
Databases have seen (tentative) changes like Object database systems and XML storage. These are trivial (and poor) compared to the changes that "the procedure" has seen, such as Object Oriented programming and functional languages. Codd got it right from the start, but procedures... we're still not sure how to do them right.
Codd on June 7, 2008 2:29 AM@Matt Johnson-
Applying the Atwood scale to a non-linear space, it would be the grape, and the oboe, respectively.
sTickler on June 7, 2008 2:56 AMoops, that was Simon Wright
sTickler on June 7, 2008 2:57 AMCodd: Tools designed for mediocre developers only serve to keep them mediocre. The relational model hasn't moved an inch precisely because developers concerned with such things lack the capacity to improve upon it.
Will on June 7, 2008 3:04 AMSorry to nitpick, but this is a pet peeve of mine:
each one more exquisitely polished and finely cut than the next.
So, you're saying, polished(n) polished(n+1)?
You mean that they get progressively LESS polished and finely cut?
While that may actually be the case in practice, as we write sloppier and sloppier code as the a deadline approaches, it's hardly something we should aspire to.
I think you meant:
each one more exquisitely polished and finely cut than the *last*.
The polished(n+1)polished(n) is so essential. We're not perfect; we never will be. I'm happy when I look at code I wrote last month and see how utterly terrible it is, but how much better it is than the code I wrote last year. When I stop being grossed out by last year's code, I've stopped growing, and it's time to stop coding and be a manager.
Isaac Z. Schlueter on June 7, 2008 3:05 AMI disagree with all of you! :-)
No, seriously: I contend that, taken together as a single invention, the Graphical User Interface and the Mouse is the single greatest invention in computer science ever. Without that, computers would have forever remained the playground of ascetic men that wear white lab coats and thick glasses to work - computers would never have been commercialized.
Without commercialization, there would have been only a fraction of the funds available to develop matters to where we are today. Even worse - without commercialization, computers would have had no real significance in the world - okay, maybe they would have been useful for larger corporations... think the airline industry. But certainly not on the scale we see today. Would we even have had PDA's? iPods? Cellphones? It's hard to say.
Johan Pretorius on June 7, 2008 3:14 AMInteresting timing of this post, Jeff - I was just reading through some of the code for Pac-Man (http://cubeman.org/arcade-source/pacman.asm) and wishing it was written in something a bit more readable than assembly language. I kept wishing there were some routines!
Does anyone know when routines started coming to the fore? Even better - does anyone know who wrote the first routine? That'd be an interesting fact for the resume: "created the backbone of Computer Science".
Scott Jackson on June 7, 2008 3:24 AMReally? The single greatest invention in computer science? Not PageRank, or QuickSort, or Chomsky hierarchy of formal languages, or pointers or recursion or Von Neumann architecture, but mere routines?
Of course, the perspective is of a former Editor in Chief of IEEE Software, who's latest publication includes such CS heavyweights as "
Should You Adopt Open Source Software?" and "Making Statistics Part of Decision Making in an Engineering Organization". IEEE Software is not a Computational Theory organization, but a Software Engineering and Engineering Management publication.
Surely you (and Steve McConnell) mean "The Greatest Invention in Software Engineering!" Joel would be most displeased with your bastardization of the great field of lambda calculus, computability theory, and finite state automatons.
/TongueInCheek
Does anyone know who wrote the first routine? That'd be an interesting fact for the resume: "created the backbone of Computer Science".
Perhaps Fortran II in 1958? One of the primary features is "separate compilation of subroutines".
http://en.wikipedia.org/wiki/Fortran#FORTRAN_II
Jeff Atwood on June 7, 2008 3:55 AMI don't know if there is a proper term for it, but rather than any single thing I think the greatest invention in CS are designs that allow one interface (as in code not gui) to be used for conceptually same things. I guess I mean generic programming but broader, not just templates.
Besides templates, there is inheritance that allows everything that can be done to parent class object to be done to sub class objects. Then there is function overloading and implicit type conversions for function parameters as done in C++. And finally, duck typing that only cares that object has an interface to do the asked thing and no predetermined knowledge about the object is required.
Obviously all these can be used badly, but I like the idea of write-once-use-for-everything-that-has-interface-for-that. Without this kind of features everything would be a special case and demand special treatment.
Bloodboiler on June 7, 2008 4:17 AMI have a better question: Why does every code monkey consider himself qualified to comment authoratively on matters of computer science?
Will on June 7, 2008 4:20 AMAh, yes, i remember my early days with the C-64 and countless "GOTO" and "GOSUB" calls. Remember: Do NOT sequentially name your code lines. Otherweise, if you have to insert Code in-between, you are screwed. You can of course add to existing lines, but I think the C-64 was limited to 2 "screen-lines" per code line.
Nothing says more "I love you!" then when you have a 1500-Line BASIC Program where you need to insert something between lines 50 and 51. Ah yes, it's an easy change of course...
50 GOSUB 1501
1501 old code of line 50 + the new stuff
150x RETURN
If there would be a way to get the flow of a typical C-64 Basic application I think you would get a diagram that looks the the organization structure of many big companies...
Anyway, just keep in mind that "computer science" is a narrow and a wide subject at the same time. The routine is good for programmers, but employees in other areas of computer science would possible give other answers. Network Engineers may hail some network protocol, i.e. "The best invention was TCP/IP, as it finally allowed students from the east coast and west coast to share their porn collection without much hassle on the cost of the company" whereas Mainboard Designers might think of some standard (i.e. the IBM AT or later the ATX) that made creation of compatible Third-Party Mainboards that fit a wide range of existing PCs.
Michael Stum on June 7, 2008 4:25 AMBy the way, your blog silently eats and brackets :)
That should have been:
1501 existing code of line 50 with the additions you want to make
"Does anyone know who wrote the first routine?"
That would probably depend on how loosely you want to interpret this.
Konrad Zuse WROTE routines (he called them plans) in a relatively high level language called Plankakl that he designed in the early 1940s... but nobody actually ever built a compiler for that language until 1998... other than that, early programmers used functions in machine code and assembly languages which underneath act just like functions in C. i.e. you pushed your arguments on the stack and the location to jump back to and then jumped execution to the address the function was located and the function read the arguments from the stack and processed them, then jumped back to the stored return address. Then they used macros to help simplify the push/call/pop/return logic. That's pretty much how C functions work underneath, C just makes it a lot easier to write them and more readable.
But isn't the routine an essential developmnt in the progress of computer science?
I think that it would have been implemented by someone somewhere sometime anyhow. It is greatly useful and greatly efficient, but it is not a great original idea.
Maurice Wilkes must be a candidate: he's credited with the development of microprogramming (there's a paper from 1953), macros and subroutine libraries. Aged 94, still at the University of Cambridge Computer Lab - which he ran for 35 years.
http://en.wikipedia.org/wiki/Maurice_Wilkes
"But isn't the routine an essential developmnt in the progress of computer science?"
Yes, and it was actually more essential in the beginning than it is now, because memory constraints were such that it was really impossible to do anything at all useful without them. I'd be willing to bet that some form of routine was used on the very first computer that was able to be programmed.
And to hit on the first comment's complaint: it's disassembled code -- but even the comments suggest the existence of routines.
It would not surprise me to hear that routines predate the compiler or perhaps even assembler. There's not much "computer sciency" stuff behind the idea.
jldugger on June 7, 2008 5:12 AMHow long should this routine be? How long is too long?
Well, to see a practical life example I just got thrown in to work with:
line 121 : "int main (int argc, char* argv[])"
line 2177: } /* main */
This is most definitely "too long". And be sure, in that piece of junk called "software", this is not even the longest routine. No, I saw a 7000-liner already, and I can't tell, what other neat surprises may be still be hidden there.
(BTW, 7000 lines: Weren't were times where we wrote a whole operating system in less than that?)
How short is too short?
When is code "too simple" to be in a routine?
Actually _never_. Such short routines get inlined these days anyway, so even a zero liner (sic!) can have it's use without any "performance impact". Especially in object oriented programming where a lot of routines just do nothing until inherited. ;)
Vinzent Hoefler on June 7, 2008 5:21 AMI used to work in the computer gaming industry, and there was a time when unrolling loops was imperative, so we often had functions that were several thousand lines long. I think the longest one I ever had was around 150,000 lines where we had to do 2 operations per pixel on a 320x240 screen. But luckily we didn't really have to maintain that, we just wrote programs that wrote the C files.
Gerald on June 7, 2008 5:32 AMActually, I believe the single greatest invention in C.S. is the Data Type. Seriously, think about it: the array, the binary tree, the hash table... How would you do anything useful without them?
Of course, programming without routines is a pain in the... somewhere, but how would you manage information without arrays? Or how would you search without trees?
Martin on June 7, 2008 5:34 AMUps, my mistake, I wanted to write the "data structure", not the "data type"
Sorry
Martin on June 7, 2008 5:36 AMWith routines, it comes down to whichever was the first chipset to support either JMP or call, as those instructions formed the basis for early routines within assembly programming.
These higher-level languages that supported routines were being compiled down into the same instructions, with different variations and techniques used to support parameters (since they were not supported at the time). These early languages that supported routines didn't simply extrapolate the process out numerous times throughout the code, but rather they compiled them into lower-level assembly routines.
With jump and return (these basic instructions had many different names in different architectures) support in chipsets, you have the foundations of what a routine is - so routines are very very old and very fundamental.
Nik Cubrilovic on June 7, 2008 5:37 AMI think you have come way too late. Hopper's whole concept of a "compiler" is the greatest invention in computer science. Everything else is just arguing over the paint job.
Robert Cooper on June 7, 2008 5:37 AMOh ye, and instructions themselves can be considered routines, its just that they are wired.. very meta (and depends how far you want to go ;))
Nik Cubrilovic on June 7, 2008 5:38 AMhttp://en.wikipedia.org/wiki/A-0_programming_language
Robert Cooper on June 7, 2008 5:40 AMI would agree with Robert on that one. Although routines certainly came before the compiler, the compiler is probably much more important in the advancement of computer science.
Perfect pick - you just have to look into the assembly code of Microsoft's Basic for Commodore 64 to see how things are not always arranged as routines, in order to save bytes. This was definitely not written with maintenance in mind.
Lars D on June 7, 2008 5:43 AMWith this post I feel obliged to explain how the computer do routines. Basically in the memmory there is the stack, and in the processor are the registers. One of the registers is called Program Counter (PC) which tells what instruction you are executing and gets incremented after each instruction is done. When you call a routine you basically put the values of the PC and all the others registrers in the stack so you have all the registrers avaible to your subroutine. Then you JMP (JMP basically put a value in the PC register, this value is the instruction you want to execute now) to the subroutine code in the memmory and when you finish de subroutine you take all the values back from the stack in the registers, the last one to be put back is the PC and it's incremented. So the next instruction to be executed is the one of the program right after the subroutine call.
The point of all of this? It's the part where you put all the values in stack and taking then back cause (besides causing stackoverflow) the function call overhead. So use your subroutines wisely, and use C-like macros (#define) whenever possible because those are simply copy-and-paste of the code (so no overhead, well except for the pre-processor), the code itself will be bigger but more fast. And by all means try not to use recursion.
Nice plug for the boardgame Othello. Wasn't, 'A minute to learn, a liftime to master', writ large across the box? Very '80s.
Wrapping my head around the the use of 'gosub' in basic was my very first challenge in learning about programming, also in the 80's.
Nanu nanu!
Tarkin on June 7, 2008 5:46 AM I was just reading through some of the code for Pac-Man (a href="http://cubeman.org/arcade-source/pacman.asm"http://cubeman.org/arcade-source/pacman.asm/a) and wishing it was written in something a bit more readable than assembly language.
@Scott Jackson: Look at what it says at the bottom of that page: "Disassembled 9289 instructions.". In other words, that doesn't necessarily have to be written in assembly.
Also: IMO assembly isn't a language, it's just an instruction set...
Giel on June 7, 2008 5:53 AM"So use your subroutines wisely, and use C-like macros (#define) whenever possible because those are simply copy-and-paste of the code (so no overhead, well except for the pre-processor), the code itself will be bigger but more fast. And by all means try not to use recursion."
Unless you're programming for embedded systems where clock cycles are still at a premium, you probably want to avoid using macros unless you have a really really good reason. The few clock cycles you gain by using macros instead of functions is no longer worth the loss of type and scope safety in most projects.
Gerald on June 7, 2008 5:54 AM"Also: IMO assembly isn't a language, it's just an instruction set..."
It's a low-level language. It allows you to express the instruction set in a somewhat human readable manner. i.e. MOV EAX,DWORD PTR SS:[ESP+34h] instead of having to express it in a sequence of binary or hex digits representing opcodes, operands and offsets.
How about the invention of high level programming languages themselves??
Reed on June 7, 2008 6:36 AMWhy "the routine"? Why not the microchip, which rendered buildings full of vacuum tubes obsolete? Why not the keyboard which made programming a lot easier compared to punch cards? Even if you restrict your choice to software: Why not the compiler (or even just the lexer)? -- not having to write machine instructions directly is arguably a bigger improvement than getting rid of line numbers.
JHerold on June 7, 2008 6:39 AMThe point everyone in the comments seems to miss is that, without functions, none of these other things would have been possible. From the point of view of abstracting electronics into algorithms, and being able to do useful things with computers, and build upon prior work, the routine is clearly most important.
Of course, it's a bit mistaken to give CS credit for functional algorithms. Mathematicians have been doing that centuries, it just took us a little while to figure out how to express them in a way machines could use.
All this talk of hardware is silly.
Dijkstra said it best, as usual: "Computer science is no more about computers than astronomy is about telescopes."
Isaac Z. Schlueter on June 7, 2008 6:42 AMthe code itself will be bigger but more fast.
Yeah right. If the code still fits into the processor cache that's fine. But once it doesn't anymore, the performance impact of cache misses are *much* larger than any "non-inlined" simple routine you did not write as macro (not to consider the "performance impact" of the developer when it comes to actually maintaining such code).
And by all means try not to use recursion.
You wouldn't believe what a good job most of today's compilers can do on recursive code. Tail recursion is especially simple - you can't do better by handcrafted assembler. After all, the jump back to the top of the routine is needed then. :)
One advice: Measure *before* you optimize. Or as D.E. Knuth said: "Early optimization is the root of all evil."
So if you still write macros to gain speed you may actually making it *slower*. Measurably. Believe me. BTDT.
Vinzent Hoefler on June 7, 2008 6:49 AMYou're hardly comparing like with like. Which one of these is easier to read/understand?
Before:
1000 CENTER% = (80 - LEN(TEXT$)) / 2
1010 SPACES$ = ""
1020 FOR N = 0 TO CENTER STEP 1
1030 SPACES$ = SPACES$ + " "
1040 NEXT N
1050 PRINT SPACES$ + TEXT$
1060 RETURN
After:
public void PrtCntdStr(string t) {
int c = (80 - t.Len) / 2;
string s = "";
l:
if (c == 0) goto p;
s += " ";
c --;
goto l;
p:
Print(s + t);
}
At the end of the day, while I broadly agree that I couldn't do my job without routines, the examples given didn't do much to support the argument (as I hope my counter-example demonstrates when you are prepared to muddy the water a little).
Dino on June 7, 2008 6:59 AM With this post I feel obliged to explain how the computer do routines.
Some computers use that sort of mechanism, those with CPUs with too few registers to hold the arguments passed, or which run OSes with requirements for support of such CPUs (x86 compatibility mode rather than x64). Other computers, such as Sparc based machines or an x64 based machine running 64-bit OS pass arguments in registers for most calls. Good compilers will inline functions to avoid the overhead in either system.
And by all means try not to use recursion.
If you have a recursive problem, use recursion, and profile the cost of maintaining your own stack against the one the OS and hardware supports. Even if the arguments are passed in registers, you still have to save the values somewhere if you have a non-tail-recursive recursive call, and building your own structures to support that in an iterative manner is unlikely to be worthwhile either in terms of performance or code clarity.
You can have too many lines in a routine, so you create lots of little routines and then you have a really long list of routines and pretty soon the names begin to become less meaningful and it becomes harder to get a handle on the code.
So often times I still write long routines with long comment lines of '/////////////////////////////// to divide them into logical chunks
rather than writing shorter ones. There's a happy medium.
Maybe it's a bit like the goto debate
Well, I guess I was on the same wavelength, because in all honesty I picked the algorithm, as the element of linear (potentially recursive) thought that was the greatest contribution of computer science.
Neal Davis on June 7, 2008 7:09 AMSome more candidates:
Goto/Jmp/Br
Without jumps, only very trivial programs would be possible. Although these are nowadays deeply hidden behind the compiler, like quantum physics is hidden behind Einsteinian physics.
Pointers
Without pointers, stacks would be impossible and thus routines would be seriously crippled. Yet again, these are now generally hidden, but more like Einsteinian physics behind Newtonian.
Structures
Without structures, parameter passing would be cumbersome. The simile here might be sand on a beach or atoms behind molecules perhaps.
The hierarchy continues up the scale through routines, objects, libraries, protocols, etc. ...
Paul on June 7, 2008 7:09 AMI'm going with "free compilers" as the greatest invention. Poor college students and people in developing countries otherwiese would never know of Computer Science because of the high cost of compilers.
david on June 7, 2008 7:12 AMI think Binary Arithmetic is the most important part of computer science (outside of hardware).
Billkamm on June 7, 2008 7:16 AMNot that the routine isn't important, but I think you should give some credit to Alan Turing's Bombe (http://en.wikipedia.org/wiki/Bombe). It did help save the free world
Mike on June 7, 2008 7:18 AMI agree the example is poor, both versions are almost line for line equivalent, and if there's any difference in readability it's down to indentation and names.
The significant difference that isn't highlighted here is that the first version is called using GOSUB, and T$ is a global variable not an argument, with all the problems that entails.
Which then shows the benefit when you need to nest routine calls with arguments and return results e.g. when the second version is implemented more realistically as:
void PrintCenteredString(string text, int lineLength)
{
Print(CenterString(text, lineLength));
}
string CenterString(string text, int lineLength)
{
...
}
wishing it was written in something a bit more readable than assembly language. I kept wishing there were some routines!
One of my project managers back in 1980 was a strong advocate of macro assembler. It was possible to create routines and code that is surprisingly readable in assembler.
Joe on June 7, 2008 7:24 AMGerald said:
"Unless you're programming for embedded systems where clock cycles are still at a premium, you probably want to avoid using macros unless you have a really really good reason. The few clock cycles you gain by using macros instead of functions is no longer worth the loss of type and scope safety in most projects."
I forgot to mention that I'm in fact programming (in VHDL) a processor inside a FPGA and with that processor I will build a crude game (using caracter map as graphics) in assembly. The problem is that the FPGA only has 2kb of memmory, which only 1kb is avaible for the program and the data. So that is why I'm a little bit crazy about processor cycles nowadays. It's mind numbling to think how to make a computer instruction and how the processor grows exponentially with every single instruction that you add.
For example, in order to save memmory we created 3 separate instructions to load a data in the register: LOAD, LOADLO, LOADHI. The processor is 16bit so we use 4 bits for the instruction and registers adressed in 4 bits (16 registers). So LOAD has [instruction number, 4 bits] [the register where the data will be loaded, 4 bits] and in the next cycle comes the adress of the data in 16 bits. LOADLO and LOADHI serve to load constants in the register, but each only use one cycle (LOAD uses two, one for the instruction and the other for the adress, using twice as much memmory too), the first one only loads data in the 8 less significant bits of the register and the last loads data in the 8 most significant bits. So LOADLO is [instruction number, 4 bits] [the register where the data will be loaded, 4 bits] [the constant 8 bits].
So to load 00 0A (hex, 10 in decimal) in the register I have:
LOADLO Rx, 0A
To load 0A 00 (hex, 2560 in decimal):
LOADHI Rx, 0A
To load 0A0A (hex, 2570 in decimal):
LOADLO Rx, 0A
LOADHI Rx, 0A
If you think about it most constants you load in a given program are less than 256 so I'm saving quite a bit of memmory doing this.
Sorry about all this mumbling about cycles and memmory, I'm getting crazy with all this binary stuff, sharing makes the nightmares go away.
Hoffmann on June 7, 2008 7:57 AMCome on people... the greatest invention in computer science (so far) is easy to answer. It's the Mouse.
Ethan on June 7, 2008 8:40 AMGrace Hopper's first compiler (A-0) was fundamentally subroutines...
see a href="http://en.wikipedia.org/wiki/A-0_programming_language"http://en.wikipedia.org/wiki/A-0_programming_language/a
Frankly I'm not sure the concept of "most important" is at all valid. "What are the most important concepts?" or "critical points in history" are better questions.
But if I do play the game... my vote is: the compiler (and that includes assemblers really); programming in binary is a real bummer.
a href="http://niyati123.blogspot.com/2008/02/first-compiler.html"http://niyati123.blogspot.com/2008/02/first-compiler.html/a
MIHondo on June 7, 2008 8:45 AMIf you ever have the opportunity I recommend seeing Robert Martin do his talk on functions. It helped me to understand and master the power of the routine.
Liam McLennan on June 7, 2008 8:45 AMIt the internets - guyz!
Cornelito on June 7, 2008 8:59 AMI wouldn't vote for the routine. I'd vote for the concept of putting code and data in the same memory.
Doug Voorhies on June 7, 2008 9:03 AMIt looks like you're looking for a fight, so... the greatest invention in computer science, I'll have to go with Dope Wars. It got millions of kids to get their TI-82s to stop displaying the Sierpinski gasket and start shopping for the best prices on heroin.
Or...
O-notation. The logic gate. The integrated circuit. S-expressions, defmacro, and eval. TCP/IP. Digital systems.
I think one thing we struggle with here is an inability to go back to just before these great discoveries and look forward at what leaps they were. There's an awful lot below the subroutine that you're taking for granted.
Even in the arena where the subroutine does the most, information hiding and abstraction, earlier discoveries like the transistor and assembly language compete for attention...
No offense to the software squad, but if you really want to call it Computer Science, then the top dog is without a doubt the microprocessor.
J. Stoever on June 7, 2008 9:08 AMSomeone quoted Dijkstra, which is really appropos for this topic. He started programming in 1952 and contributed much to the field, inventing the mutex, for instance. He gave a Turing Award lecture in 1972 called "The Humble Programmer" which is a classic, here's a link to the text:
http://www.cs.utexas.edu/~EWD/transcriptions/EWD03xx/EWD340.html
He makes the case for abstraction by arguing that we have small brains, and have to live within their limits, so anything that helps us limit the amount of "stuff" we consider at one time is good. This piece is from an era when there was debate over whether subroutines were a good thing or not... we've come a long way!
Carl on June 7, 2008 9:12 AMHmmm.... but you can write code without functions.
You can't write code (at least useful code) without jz or jnz
Come on!
The binary digit (bit) was an invention. Check out "Code" by Charles Petzold.
The stored program idea - that is that a program is just at some level data for something to run. Inherent in the work of Turing, polished by Von Neumann.
Everything since is just optimization.
jefu on June 7, 2008 9:25 AM"No offense to the software squad, but if you really want to call it Computer Science, then the top dog is without a doubt the microprocessor."
That depends on who's definition of computer science you use. There is plenty of disagreement on that topic, but in my experience computer engineering is a separate field from computer science and the microprocessor would fall under an advancement in computer engineering.
I think the context in this clearly isn't about hardware :P
Best Regards,
Gerald
Gerald said:
"Unless you're programming for embedded systems where clock cycles are still at a premium, you probably want to avoid using macros unless you have a really really good reason. The few clock cycles you gain by using macros instead of functions is no longer worth the loss of type and scope safety in most projects."
I go by the rule that if a subroutine uses more cycles to be called than it executes itself it's not wroth to be a subroutine. The real problem is small functions that are called all the time and are recursive. When I said "whenever possible use C-like macros" I should have said "when is viable".
Hoffmann on June 7, 2008 9:38 AMRoutines?
Computer Programs are routines...
I guess the most important invention is networking computers
I'm going to claim that the compiler and the computer itself are special cases of the most important computer science invention: the idea of a universal machine.
The idea is a machine which can take a description of a machine in data, and emulate it. The computer is an implementation of this idea in hardware. The interpreter in software. The compiler translates from one way of writing the description to another.
The universal machine is also first in 1937. Software predates hardware.
Matthew L. on June 7, 2008 9:51 AMI also agree that that kind of optmization should be one of the last used in order to improve performance, but programmers should keep in mind the overhead always.
Hoffmann on June 7, 2008 9:54 AM"I go by the rule that if a subroutine uses more cycles to be called than it executes itself it's not wroth to be a subroutine. The real problem is small functions that are called all the time and are recursive. When I said "whenever possible use C-like macros" I should have said "when is viable"."
There would be very few cases where a subroutine/function uses less clock cycles than calling it does. And in that case, using an inline function is a better choice than a macro; you get the performance benefits of using a macro and the maintenance/type safety/scoping benefits of functions.
The only time I ever use macros any more is when it makes things a lot easier to read and understand, such as using them in message mapping, i.e.:
START_PACKETMAP(pack)
PACKET_MAP( PACKET_FOO, OnFoo )
PACKET_MAP( PACKET_FOOTOO, OnFooToo )
END_PACKETMAP
Best Regards,
Gerald
Logic, because you can't solve problems without it, followed by memory, to bypass the effort required to re-solve those problems.
Greg on June 7, 2008 10:05 AMJeff,
for accuracy, consider that Computer Science in itself has little do do with computers, even with programming. The single greatest achievement in Computer Science is the concept of tractability and intractability) of problems. You know, the O(n) stuff. They are so fundamental that an algorithm is just a jumbled assembly of words from a language grammar without tractable problem to implement. Languages in itself are not a computer term either but another concept deeply entrenched in Discrete Mathematics which found very cool use in building computer languages.
Now, Software Engineering as a science is closer to what you are referring to. Computer Science is much drier than Software Engineering and much more methodical in its approach. The "bad code" you often write about is an outgrowth of ignorance of so many "programmers" out there who found their way into software field when money seemed good and roadside coding education replaced the good sense of learning the fundamentals before pounding the computer metal.
BugFree on June 7, 2008 10:20 AMJeff,
for accuracy, consider that Computer Science in itself has little to do with computers, even with programming. The single greatest achievement in Computer Science is the concept of tractability and intractability) of problems. You know, the O(n) stuff. They are so fundamental that an algorithm is just a jumbled assembly of words from a language grammar without tractable problem to implement. Languages in themselves are not a computer term either but another concept deeply entrenched in Discrete Mathematics which found very cool use in building computer languages.
Software Engineering as a science is closer to what you are referring to. Computer Science is much drier than Software Engineering and much more methodical in its approach. The "bad code" you often write about is an outgrowth of ignorance of so many "programmers" out there who found their way into software field when money seemed good and roadside coding education replaced the good sense of learning the fundamentals before pounding the computer metal.
BugFree on June 7, 2008 10:22 AMAfraid my vote goes for Assembler, invented (I believe) by David Wheeler in Cambridge in 1951-1952. It's the earliest point I can think of where software was taken out of the hands of theoretical mathematicians (an endless roll of paper and a pencil with an eraser on the end) and physicists (mercury delay tubes and bit switches, what fun).
Assembler (generically) may be a bit of a headache, but at least it allows fairly normal people to think syntactically and semantically about what they are doing.
Not that Dr Wheeler was exactly normal. I was taught by him ... it was an interesting experience.
real_aardvark on June 7, 2008 10:24 AMI personally feel the Keyboard is the most important invention.
Ofcourse keyboards existed before computers connecting one to a computer actually gave programmers enough mental leyway to start thiking about stuff to improve their programs
Languages are a tiny part of CS.
The greatest was Von Neumann's architecture. Then Denning's Working Set virtual memory. Dijkstra's semaphore.
One could argue Multics and Tenex operating systems.
fishtoprecords on June 7, 2008 10:27 AMYou're not a raving lunatic Simon :P
But I don't agree with you, though I guess it depends on what type of software you're developing. Object oriented design doesn't work well in some areas. That's one of the reasons I still do a lot of programming in C++ instead of languages that force me to use objects for everything; I have the flexibility to mix object oriented and procedural design. Although the same effect can be had by using singletons, it just feels wrong to me sometimes.
I think overall object-oriented design is a great thing in the industry. I certainly wouldn't say it has hurt the industry.
"Even if you could design the perfect object model for your application it will quickly disintegrates, under the weight of maintenance, in to a collection of "bucket" classes with weak cohesion and tight coupling."
If you design the right object model, there's no way that happens, unless you're not giving much thought to the object model when you're doing maintenance and just throwing around a bunch of quick hacks.
Best Regards,
Gerald
Well, I think that if we are talking about the greatest inventions in Computer Science, you'd have to start at the Turing Machine. After all, this is the theoretical abstraction for all computing machines.
After that, I'd probably pick something like context free grammars (which you could probably argue isn't even Computer Science, but it surely has been a major tool for developing programming languages).
Doug Jones on June 7, 2008 10:29 AMWe're really talking about block structure, not routines (which existed long before autocoder hit the scene). Learn Algol60 if you want to appreciate it in all its glory. Seriously. You have _no idea_.
Will on June 7, 2008 10:39 AMI've always thought the stack is one of the great computer inventions.
Certainly, routines existed before the stack, but the concept of a stack is less obvious than "let's try and reuse this code". Before stacks, routines were called by (for instance) BALR, "Branch And Link Register"[*]. The next IP address was placed in the named register, and the PC was changed to the routine. Returning consisted of jumping to the address in the register. But think of how painful this is: there's no place to put local variables, and recursion can't be done (unless you make your own area to store the link register values).
[*] IBM 360. They didn't have IP and PC registers, I'm just stealing the Intel terms.
Phil on June 7, 2008 10:39 AMThe first routine is likely to have been in either Fortran II or Lisp (or FORTRAN II and LISP, as they were then, lower-case letters not having been invented at the time).
Of course, it's entirely likely that people did them in assembly beforehand; it's even possible that some early processors had builtin support for them (as does the M68K, for instance).
Robert Synnott on June 7, 2008 10:43 AMI said the internet :(
Justus on June 7, 2008 10:47 AMAccording to Maurice Wilkes (mentioned in Dave Smith's comment), there are only two ideas in Computer Science: abstraction and caching.
When he told us undergrads this, it was obviously a bit annoying having just spent 3 years trying to get our heads round the Cambridge CS course. However, I still often think about what he said and, unsurpringly, I've yet to come up with a counter example.
To steal Robert Cooper's phrase, every CS invention is just a paint job over those two ideas.
James on June 7, 2008 11:04 AMI'll add my vote to the compiler list. Compilers are so much more than 'glorified Assemblers'. In their day Assemblers were a great advance over machine coding. But Compilers gave rise to a myriad of different languages whose individual dialects might be tailored to specific industries and problem sets.
Favorite examples: COBOL, Fortran, APL
The biggest improvement in most compilers was the incorporation and application of optimizing techniques.
Favorite example: Turbo Pascal
Coming in second place to compilers are Interpreters and Virtual Machines. However, these didn't become viable solutions until the hardware was fast enough and memory big/cheap enough to run interpreted applications.
Favorite examples: REXX, Java, PHP
===============
I disagree with routine as a greatest candidate. It is simply a packaging of code. Look back to the COBOL paragraph, which are blocks of code that can be executed singularly or repetitively. These code blocks were made available by a compiler. Assemblers made the macro available to repeat blocks of code. It isn't the concept of a block of code (routine) that is the greatest, but the technology that enables this blocking.
James: I don't think it's true that everything is just a paint job over those two ideas (abstraction and caching). I think it's more accurate to say that there are only two kinds of ideas: abstraction ideas and caching ideas.
The distinction there is that many -- most, in fact -- of the abstraction ideas are not merely "oh, let's use abstraction here"; the actual way that one uses abstraction, and the abstractions that one chooses to use, are a critial part of the idea.
(Or perhaps you say that an art gallery only has two basic paintings; paper and canvas. Everything else is just a paint job over those two.)
My first reaction was to have flashbacks to BASIC programming on the CBM64, numbering lines by tens to be able to insert new ones; and living without GOSUB or passing parameters. Somehow we didn't seem to mind so much, though.
My second reaction was: well, what about the class? In OOP, creating a good class (and its well-polished methods) is as important today as it was to create a generally well-tested and useful routine back in the days of structured programming (in C and Pascal in my case). Surely it is efficient organization of code that is hard to master, not just in the context of routines.
My third reaction was that I feel old, and I'm only 34. Such is the life of a programmer.
Aikimark: APL has never been a compiled language in the sense you describe.
Will on June 7, 2008 11:24 AMI say the turing machine(together with the church-turing thesis) if it qualifies as an "invention" is the most radical one in the computer SCIENCE field.
kunjaan on June 7, 2008 11:39 AMI vote for routine as a process of abstraction. We have a long and productive history of hardening large concepts into smaller representations. Today's macro is tomorrow's micro. This process enables us to think and program at a higher level.
Routine is a form of sequence control. In the 1940's, the Mark I was called an automatic sequence controlled calculator. In the 1950's, electronic computers had only transfer or jump operations to control their sequence - but then programmers used a technique called "sub-programs" to implement routines. In the 1960's, this technique was hardened into machine op codes like "transfer and set index" to effect subroutine linkage. By the time of the IBM 360 in 1964, the "branch and link" opcode itself was a call to a microcode routine.
So this process of abstraction takes useful ideas and compacts them into lower / harder layers of the system to allow programmers to create at higher / softer levels. A good example is the stack, which moved from a very useful programming technique to a machine instruction within a few years.
For a while, this process produced very high levels of abstraction in the form of programming languages like APL. But more recently, perhaps due to the drop in hardware costs, there has been a dramatic drop back down to languages like C and its derivatives, where a routine more closely resembles its 50 year old origin.
If we talk about "first" in terms of inventions, it wasn't 1937 or Konrad Zuse or whoever claims to first having built something called computer - no, it happened almost 200 years before with Charles Babbage's Difference and later his Analytical Machine. Although the machine was never built during Babbage's lifetime, first programs were already written for it by (surprise, surprise) Ada Byron Lovelace. Yes, right. The first programmer - at least to our knowledge - was a woman. And she did it more than 150 years ago.
For a short, simplified overview see http://www.maxmon.com/1830ad.htm
It "was intended to use loops of Jacquard's punched cards to control an automatic calculator, ... This machine was also intended to employ several features subsequently used in modern computers, including sequential control, branching, and looping."
So it could have known subroutines already. ;)
Vinzent Hoefler on June 7, 2008 12:00 PMBefore your article, if given a more specific question of "What is the Greatest Invention in Programming", I'd for better or worse would answer "The Object". However, as Object is a direct descendant of the routine, I'd have to recognize it's superior claim. Of course I should note that your check list for good routines, is a good guide for well balanced objects.
Eric on June 7, 2008 12:32 PMI'd argue that the pointer or, more precisely, the BUN (branch unconditionally and return) is more important. With pointers, one can represent redundant functionality without having redundant structures.
Among other things, this allows the representation of other operations as numbers which, so happen, to correspond to addresses in main memory. This is key. Numbers can act on numbers rather than merely representing a quantity or value.
Without this fundamental power of indirection and collapsing representation as reference, software would be far less-efficient and even harder to debug. You'd have no routines forced redundancy at the lowest-level of operations.
Keith on June 7, 2008 12:32 PMPointers + Records. Programmers are provided with considerably more power with a combination of pointers and records than they are with routines. Linked lists, stacks, queues, heaps, binary trees, all the other kinds of trees, graphs.... The concept of pointers to structs that contain more pointers is the single most powerful invention with regard to data structures.
Benson on June 7, 2008 12:44 PMWhat you mean is this...
After structured programming:
public void PrintCenteredString(string text)
{
int center = (80 - text.Length) / 2;
string spaces = "";
for(int i = 0; i center; i++)
{
spaces += " ";
}
Print(spaces + text);
}
Note how each curly brace (or scope in C/C++) has it's own line? It's the proper formatting that doesn't look like some sort of abortion. And everytime I see the formatting you use, it makes me think this. Imagine a man walking along writing something, but then he slips and falls, and OOPS, all his writing gets messed up. That's exactly what the inconsistent depth level of the curly braces reminds me of.
I also remember the c64 and the goto and gosubs, that was the basic language back in the day (and I guess sort of still is).
Pascal also had the goto, but didn't use the line numbers and so you could (as my uncle told me back in those days) write goto h*ll and I thought that was so cool.. (I was 10 back then, everything with that four letter word was cool).
And so when I tried out (and bought) Delphi I had to try out the goto H*ll thingy.
What I also remember from those days was 6502 assembler language. I remember writing some easy demos making sprites move over the screen while I could type something at the same time. ea = NOP back then, and I remember A9 also meant something, just that I can't remember what it was now..
Ah. Those were the days. we even had some great games back then ;)
Hm.
I think it is just impossible to define the single best invention in computer science, as there are lots of things you cant really compare.
For programming, yes, routines - or, being a bit more abstract - general abstractions from goto (that is, loops, routines) are one of the really big things.
However, how do you compare the complexity theory to this?
Is the knowledge that finding some shortest hamilton cycle takes a lot of time better of worse than saving a buch of keystrokes?
Is the idea of having a program look at your programs, optimize a bit and turn it into assembler better or worse than the idea of stacks (that is, the basic of many programming languages)?
Or is the idea of the lambda calculus better or worse then the idea of using magnetic hard drives?
I am unable to answer such questions, as all of these are significant inventions.
Hk on June 7, 2008 1:13 PMIf it's all abstraction and caching, then abstraction is rather broadly defined. Consider: coding schemes, the concept of an instruction set and higher level languages that can be translated down to it, the concept of manipulating sequences of instructions as data, the concept of an algorithm, the concept of indirection, the concept of a virtual machine, the concept of hierarchical decomposition of a problem, the various techniques that are used to implement hierarchical decomposition, the various themes like hashing that are broadly useful to implement efficient algorithms...
So a statement like "the only ideas are caching and various abstractions" might not be false, but how much information does it convey?
William Newman on June 7, 2008 1:23 PMAbstractions are like potato chips: handy algorithmic themes like alpha-beta which evidently took people years to find, computability and Turing completeness and asymptotic complexity classes like NP, compressibility and information theory and learning, continuations, in fact the entire menagerie of techniques to express synchronous and asynchronous parallelism, inheritance, GC, the concept of "purely functional" and the laziness abstractions that make it work, the menagerie of public-key-cipher-related tricks, COME-FROM...
William Newman on June 7, 2008 1:35 PMReally should include reference to this book:
http://www.cs.inf.ethz.ch/~wirth/books/AlgorithmE0/
Steve on June 7, 2008 1:48 PMUmm... Could you define "routines"?
As far as I can tell, sub-programs have been around almost as long as computers. I use to program sub-programs in assembly language. I had them in Fortran and Cobol. Heck, I can't think of any language I had that didn't have some concept of a gosub or function. (Well, APL didn't, but you could never read what you wrote anyway).
To me the big change was the localization of variables. Older languages didn't have *THAT* concept. For example, in the early 1980s and late 1970s, I use to write in a proprietary language called Cadol. Cadol didn't have variables, but registers. Some registers could store alphanumeric data and some numeric data. Basically, all registers are global from boot up until you shut down the machine.
We had sub-routines, but we didn't have local variables. To get around this issue, we divided the registers up into "used to store data" and "used by sub-routines". When you call a subroutine, you'd copy the necessary "used to store data" registers to the "used by sub-routine" registers, call the sub-routine, and then copy the "used by sub-routine" registers back to the "used to store data" registers.
When I learned Pascal back in the mid-1980s, I was awe struck at the concept that functions and procedures had local variables. That was a great revelation and made programming much, much easier to do.
I think Fortran II (1958) was the first language to have procedures, but I don't remember if these procedures had local variable space or not. I don't think it did.
David W. on June 8, 2008 2:10 AMWhile a routine might be the greatest invention in programming, it certainly isn't the greatest invention in Computer Science. If it weren't for Turing's Universal Computing Machine or the Von Neumann Machine, we might not have Computer Science at all.
HaunchesMcGee on June 8, 2008 2:10 AM"According to Maurice Wilkes (mentioned in Dave Smith's comment), there are only two ideas in Computer Science: abstraction and caching."
That's a particularly dumb quote. Abstraction is an extremely important idea, a crucial idea - its various flavours literally define how languages work - whereas caching is an implementation detail used to give greater efficiency to certain classes of program, very useful but hardly in the same ballpark or even the same city as the ballpark of abstraction.
Why is "caching" more important than: hashing; inheritance; data structures (not the same as abstraction, almost the reverse); "graphs" (linked structures); O() analysis?
I just don't see it. Seems like something someone says to be cute, rather than deeply thinking abut it.
Tom Ritchford on June 8, 2008 2:20 AMThe comments to this entry are closed.
Subscribe in a reader
Subscribe via email
|
|
Traffic Stats |