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

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>

This is possibly the dumbest question you could ask. Next you'll be asking what the greatest variety of fruit is, or what the greatest instrument in the orchestra is. You're attempting to judge on a linear scale what is inherently not linear. C'mon Jeff, do better.

> 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

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

By 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 Plankakül 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.

>>> How 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. ;)

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

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

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

Oh ye, and instructions themselves can be considered routines, its just that they are wired.. very meta (and depends how far you want to go ;))

http://en.wikipedia.org/wiki/A-0_programming_language

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

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

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

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

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

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

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

You'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).

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

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

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

Not 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

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

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

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.

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

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

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

"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

It dawned on me a couple of months ago that the very essence of programming is the routine. It isn't classes, design patterns or other window dressing but the routine. I think the industry has to realise that the routine is the basis of programming, not the class.

I hold the (admittedly unconventional) view that object orientated programming is actually hurting the industry. Object orientated thinking causes you to overly obsesses over the object model and focus less on the computation you're trying to perform.

Take refactoring, for example. Refactoring is the art of solving meta-problems in your code whose solution is orthogonal to the actual problem you're solving. The aim of course is to improve maintainability but is the cost benefit really there, or do developers just like having pretty object models? Is a refactored code-base really *that* much easier to maintain? To be worth the money, it'd have to be 50% or more faster to develop against. I have a hard time believing this could be the case.

Moreover, it is exceedingly hard to design a good object model. Every application I've worked on has had deficiencies in its object model, that become apparently only in the very late stages of construction.

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.

However, this does not make its contribution entirely worthless. Studies *do* show that object orientated programs are easier to understand than their procedural counterparts.

However, I get the feeling that a lot of the issues you run in to with object orientated thinking is a result of the failure of the failure to appreciate the power of the higher-order function.

With proper namespacing and aggressive use of higher-order functions, I think you can have more maintainable, more flexible programs without resorting to object orientated design.

When I've worked in that style on my private work, I've found that I focus on solving the problem and not trying to correctly factor the program.

Does anybody out there agree with me or am I just a raving lunatic?

Simon

Jeff,

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.

Jeff,

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.

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

You'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).

We'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_.

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

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

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

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

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

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

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

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

Really should include reference to this book:

http://www.cs.inf.ethz.ch/~wirth/books/AlgorithmE0/

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.

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

@Matt Johnson-

Applying the Atwood scale to a non-linear space, it would be the grape, and the oboe, respectively.

oops, that was Simon Wright

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

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

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

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

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

I have a better question: Why does every code monkey consider himself qualified to comment authoratively on matters of computer science?

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.

http://en.wikipedia.org/wiki/Turing_Award

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

Ups, my mistake, I wanted to write the "data structure", not the "data type"

Sorry

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

I think Binary Arithmetic is the most important part of computer science (outside of hardware).

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

Come on people... the greatest invention in computer science (so far) is easy to answer. It's the Mouse.

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

It the internets - guyz!

I wouldn't vote for the routine. I'd vote for the concept of putting code and data in the same memory.

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

Flexible/"pluggable" regular expression parsing is the most important invention in computer science. Without it, there wouldn't be many of the things we take for granted.

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

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

Logic, because you can't solve problems without it, followed by memory, to bypass the effort required to re-solve those problems.

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

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

I said the internet :(

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

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

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

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

I think that XBase, starting with dBase II in 1983 and later Clipper and FoxPro, deserve a very important place in this list. It's power, simplicity and interpreted style have done the path to many improvementes in modern languages like .NET
Even today XBase is still alive and kicking.

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

But it uses routines: Just look for "jp" (jump) and "ret" (return).

Asm is by ways more readable than pure machine-code ;-)

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

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

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

Is "logic", or similar concepts, an invention?

The Internet, obviously.

"Actually, 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?"

"He [Dijkstra] 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."

Data Types and Structures (OOP) are neat and all, but seriously the greatest achievement in C.S. has to got to be that we're constantly learning new ways to deal and manage computer power. That we're actually admitting to ourselves our own limits in respect to computers.

The stored-program computer (a.k.a. the von Neumann architecture) and code as data.

http://blog.uncommons.org/2008/06/08/great-innovations-in-computing/

As well as making computers much more flexible, it made it possible to write programs that write programs (e.g. compilers).

The stack.

It's the simplest data structure, and yet the most useful, so essential that its handling is now engraved in the silicon. In fact a pure "Von Neumann" architecture isn't really usable without a stack, while you could build languages such as Forth and computers such as the HP "reversed polish notation" calculators around a stack.

The pointer.

I vote for compilers

I think saying that those languages are so young is misleading. The rate of increase of inventions and such has become faster over previous years. For languages from the 70s, for example, 10 years was not that much time because the main users of these languages were small groups of researchers.

However, for languages from today 10 years is a much longer time. The speed of development of languages has increased so much more today. This is due to the Internet and other factors such as open source software which allow for the average person, not just researchers, to contribute to development.

The routine??? hahaah you truly are stupid.

routine is just a form of abstraction, and abstraction is at the heart of computer science. The real inventions are lambda calculus and model checking and automatons.

Seriouzly you're stupid

Tjerk:

Depends how you define "invention in computer science". Is abstraction really an invention, per se? I would say that regardless, it is certainly not an invention in computer science. Abstraction FAR predates computer science, even under the "computers have nothing to do with computer science" definitions.*

Even accepting that abstraction is greater and the routine is just a manifestation of same, that does not stop it from being an invention -- an invention I would still argue is a lot greater than the others you list among many dimensions of "greatness".

* This goes for "logic" and a bunch of other suggestions too. We needed these "inventions" for fire and a bunch of other inventions that came far before comsci or anything else related.

What about lisp and smalltalk? They're just as modern as any modern programming language and they were invented in 1958 and 1969 respectively.

I think you are all wrong. For inventions that changed the world, you just can't beat the CMOS chip. (I know it's clunky now) What CMOS enabled us to do is learn a programming language and port it from one machine to another that is designed very differently. CMOS made it possible for the PC Clones to be usable, for the PC market to grow, for us to have systems to work on. I'd like to think CMOS is the precursor to all modern programming. Maybe I am biased.

re Phil on June 7, 2008 09:39 PM's comments about stack vs BALR

If I recall, many small machine architectures in the 1960's & 1970's (1130, some microprocessors) did not put subroutine or function parameters in registers, stacks, nor did they point to them from registers other than the return address register. Self modifying code was OK. The parameter values were placed into memory following the call instruction. In architectures where the caller set the return address, it set it to just after the last parameter. In architectures where the HW stored a return address with a value just past the call instruction, the subroutine/function had to add enough to that return address to point to the instruction after the last parameter. Either way, if there was a variable number of parameters and/or variable length parameters, the exercise got to be fun.

re David W. on June 8, 2008 01:10 AM question: Did Fortran II have local variables?
YES. Function and Subroutine variables were local. So were their names. The same variable names could be used in independently in each routine.
If you wanted them to be global, you had to put them in COMMON
see http://en.wikipedia.org/wiki/Fortran

re: Dr. Goulu on June 8, 2008 05:07 AM "In fact a pure "Von Neumann" architecture isn't really usable without a stack..."
Tell that to the mainframe folks. IBM mainframes do not have PUSH and POP instructions.
In z/Architecture Principles of Operation , SA22-7832-06
https://www-01.ibm.com/servers/resourcelink/lib03010.nsf/B9DE5F05A9D57819852571C500428F9A/$File/SA22-7832-06.pdf
, the words "push" and "pop" do not appear. "Stack" appears 983 times, but usually referring to the program linkage [traceback] stack.

David

I'd say the single greatest invention in computer science is the concept of treating data in memory as instructions. Such data has come to be called "software". The earliest computers had no such concept. To change the problem the computer was to solve, you had to mount a different plugboard. The invention of software is usually attributed to mathematician John von Neumann.

Guess what? If there were no routines we could still program computers to do our bidding. The routine is a great artifact for human comprehension but its hardly necessary.

Surely greater inventions include the algorithm, the the stored program, or (more fundamentally) the function (in the mathematical sense)? Or stored state?

I guess when you have a popular blog you feel compelled to say something periodically even when you have nothing to say.

0 - Zero

http://en.wikipedia.org/wiki/0_(number)

The human brain...
Without it, nothing else matters.

I would have gone with binary. It might actually be the first application of computer science to solve the fundamental programming difficulty with electronics. Binary makes it possible!

The greatest invention ever in computing is: copy/paste.
Clearly.

I came here to opine that compilers are the greatest invention in computer science but everyone beat me to it. Although I sometimes miss programming in 6502 Assembly...

What about C#? Published in 2000 I think.

I think the compiler, not the asembler. We had cpu, we had patch cords
and machine lang/asm but what really changed it all the the compiler it made the computer language possible.

as any husband will tell you the longest routine ever written is the private why_you_are_wrong() routine... invented by women a long time ago, it is still being wrtitten, and takes an infinite number of arguments. Furthermore, it only ever has one result... a string - 'Yes, Dear'

As to who invented the routine, or at least the idea, I believe that is credited to Ada Lovelace, for use on Babbage's Analytical Engine (the original vaporware in our field). Something like that was also used on Jacquard (sp?) Looms, which led to the invention of Paisley patterns, for instance, which were too difficult to do on manual looms.

Gee, does no one cover the invention of programming, anymore? It was just a couple of days of non-tested material, but it did give a nice historical basis for things.

My first thought was the local variable. Reducing the scope of a piece of information so simplifies maintenance that it makes everything else possible. This reduction in scope is what allows one to make a large system and actually be able to use it.

Without the local variable, the subroutine only adds reusability of code, which is only half of its purpose.

OOP is just extending scope control to code as well as data.

@Will

Although most APL was interpreted, there have been some compilers for it and the derivative J language. Most of the compilers used some intermediate source (C/C++) rather than a direct executable compilation.

http://en.wikipedia.org/wiki/APL_(programming_language)#Compilation
http://www.chilton.com/~jimw/apl85.html

However, my APL example was truely misplaced, since my initial APL experience in college was interpreted. This specialty language was not compiler enabled. I appologize.

The best invention IMHO is something that no-one takes the trouble to learn about; Prolog. Obscure it may be, trivialized, certainly, but hugely powerful depending on the task.

Invented in the late 1970's, it is not at all procedural, but rather rules based. The small example as given above would be written like:

------------------------------------------
print_centered(X) :- atomic(X),
sformat(String, '~w', [X]), string_length(String, Len),
Center is (80 - Len)/2, !, print_indented(Center, String).

print_indented(SLen, S) :- SLen =< 0, !, write(S), nl.
print_indented(SLen, S) :- write(' '), !, print_indented(SLen - 1, S).
------------------------------------------

The nice thing is that you can use the above to print not just strings, but also integers or floating point numbers. Just three rules to print just about anything as centered. Something you want to print centered that it can't handle? Just add a rule to deal with it!

Reads like English too: (from top)
print_centered(X) if X is atomic and format X as a String and the length of the String is Len and the Center is (80 - Len) / 2 and succeed if and only if print_indented(Center, String) etc. etc.

Its really very default to keep track the single Programming language, Because day by day the new programming language are getting introduced , So developers need to update their skills in new domain in order to become a successful developer. These are the language i learnt up to now

1) C
2) c++
3) java
4) PHP
5) Javascript
6) Ajax
7) Adobe AIR

I'd argue for the debugger being the single greatest invention.

Does no one ever read any further than the title and first sentence of Jeff's posts?

The point of his post, as I interpret it, was not to prompt a lengthy discussion whether the the routine was in fact the greatest invention in Computer Science (which is a quote from Steve McConnell, not some random assertion Jeff just came up with).

The point was to make you think about what an important concept a routine represents, how fundamental it is to programming and how we still manage to misuse and abuse this simple building block by not thinking enough about the basics.

Windowed GUI Interface & Mouse - My parents would never use a command line and neither would 98% of other users. That with the advent of the "personal" computer certainly made computers more mainstream.

Certainly the routine was an important advancement in programming.

Amen, brother!

IMHO, competent use of this feature has become increasingly uncommon. Part of the reason, I think, is that modern editors and IDE's have made "copy-paste" programming far too easy. Combine this with short attention spans (also an increasingly common phenomenon), and you have a big mess. In one case, a coworker put together a unit-test program that had approx ~1200 occurrences of the (almost) exact same code sequence, each one blithely pasted from the previous. Makes you wonder...

For those of you wondering about how to create good routines, there is still no better guide than the following:

Reliable Software Through Composite Design (Paperback)
by Glenford J. Myers (Author)

(Yes, the mention of tapes, etc. makes it sound a little dated. But this is the seminal work in terms of defining coupling, cohesion, and all the other things that go into making good routines. Plus, you can get it real cheap).

Jeff - this post definitely highlights the need for a post on "What does Computer Science mean to you?". I would LOVE to read the comments on such a topic.

Several people here assume CS is theoretical and claim turing machines / lambda calculus are the most important inventions. Likewise, several people including you see CS as more about programming, and say routines are the most important. Some have blurred the distinction between CS and computer engineering and state that the microprocessor is the most important invention. But the ones that make me cringe the most, are those who treat CS as purely user/business oriented and say the mouse was the most important invention.

@higgs: "You can't write code (at least useful code) without jz or jnz" -- You should examine both OISC (for laughs) and "The Program Counter Security Model" (for an arguably important real-world application of straight-line code).

@Hoffmann: You should check out any RISC processor, and then benchmark your code with and without the needless pre-optimizations, and then shut up.

@Jeff Atwood: Didn't you mention the blog post "Design Patterns of 1972" last year? It's certainly required reading for anyone interested in today's post.
http://blog.plover.com/prog/design-patterns.html

(My "greatest inventions of CS" nominees: The compiler; the subroutine; the pointer; the hash table; type theory; Union-Find.)

The question of this article is a bit silly. There have been many important, paradigm-shifting inventions in the short history of CS and the subroutine is merely one of them.

As other commenters have pointed out, there are a number of inventions that you could put right next to the subroutine on a list of the X most important developments in computer science. I don't think any 1 thing would take the cake.

-Variable Scoping
-Compilers
-Interpreted Languages (Java and .Net)
-Data Structures (classes)
-Standardized GUI Elements (small-w windows)
-Subroutines
-The Mouse

... I'm sure that I'm missing half a dozen important ones, and I'm deliberately leaving off stuff like the microchip (why not the vacuum tube?)

Personally, my favorite invention is interpreted languages. To me, interpreted languages are like icing on the cake (which is the compiler).

Esotericly, a routine goes back to before 1725. The Jacquard Loom used stringed together cards that repeated a pattern. But The wikipedi states it's partially based on a paper tape loom from 1725. The wikipedi does mention it was based on a music organ. So a wheel or paper roll of a music box is a repeating set of instructions, is it a routine?

There are also very old brass machines (some toys) that also can be said to be programmed (cams and wheels) to repeat a performance several times. So whats a routine?

Maybe if I say "binary numeral system" over and over again people will agree with me.

How about "digital"? :O

From Wikipedia: "Owing to its straightforward implementation in digital electronic circuitry using logic gates, the binary system is used internally by all modern computers."

ALL MODERN COMPUTERS. Bam! None of this other stuff is used in ALL modern computers. You specialists, all with your specialist ideas.

(Don't take me too seriously, just enjoying the discussion here) :)

Public key cryptography, or cryptography in general must surely rank as one of the most important inventions for Computer Science. It has made online commerce possible and even easy. In order for technology to survive it must be economically feasible. Without secure transactions over the Internet, I'm sure that it wouldn't have grown to where it is today.

One can actually make a pretty good case for subroutines being #1, as it demonstrates what makes human reasoning what it is -- the ability to imagine an abstract concept, give it a name, and then refer to it by that name going forward. That's basically what language is all about, no?

OK. I'm going with one other poster here and say "the algorithm", and if I have to choose one then it would be the "sorting algorithm". The routine is just the mechanics of implementing something, but "what to do" is way more important!

I don't even consider "the routine" to be an invention.
It's as simple as GOSUB. As simple as CALL. As simple as PUSH IP, JMP XXXX (and then POP IP).

I mean come on. Sequentially ordered instructions -> the "JMP" instruction to redirect flow -> a "RET" instruction to return from whence we came. Pretty obvious, even if hindsight IS 20/20.

If you're going to allow "the subroutine" to be an invention, why not "code"? Why not "variables"?

You said: 'It is, after all, the single greatest invention in computer science.'

While the routine was a great milestone on the journey that exploits abstraction to improve software development, the next invention, which built on top of the routine, also brought about a revolution: the polymorphic message send, also known as 'dynamic dispatch', took the idea of calling a routine whose location (provider) is specified at compile-time, and extended it to allow programmers to invoke a routine with a signature that is specified at compile-time, but whose location (provider) is specified at run-time. Object Oriented programming allows an object to send a message to another object which is only known by the fact that it provides a method implementing that message. The resulting flexibility, 'one message, many methods', gave us a way of realising the <A HREF="http://en.wikipedia.org/wiki/Open_Closed_Principle">Open-Closed principle</A>.

@all:

Maybe we should divide the inventions in CS (as broadly spoken as possible) between pure CS abstractions (data structures, compilers, languages,...) and engineering solutions to CS problems or simply enablers (transistor, CMOS, networks (those would fit into abstractions too), mouse, GUI,...)

???

It seems that the concept at least of routines existed in the earlier posted PacMan code - unless this is a recent rewrite.

;; Indirect Lookup table for 2c5e routine (0x48 entries)
36a5 1337 ; 0 HIGH SCORE

I also like the next line :)

don't call and ret count as a routine? isn't therefore the concept of a routine even older than programming languages themselves? what about doing it by hand? pushing an address, jumping then jumping back when done?

Personally i think the jump from assembler mnemonics to a language with grammar was the biggest development in programming... its a highly non-trivial conceptual leap, where as routines seem like a natural side-effect of a person writing code... I think most coders, not necessarily even a good programmer, would invent them as needed and probably there are multiple "inventors" of the routine.

In essence its just an elaborate parallel to things like headed paper or mail merged letters... people recycle everything that costs them something to make, whenever they can. Laziness is a big driving force for invention. :)

"What do you think the single greatest invention in computer science is?"

Honestly I just don't care. There is no satisfying answer and thinking about [with dark, booming voice] THE SINGLE GREATEST INVENTION IN CS doesn't make me a better programmer. It isn't important. Every invention (OOP, subroutine and so on) has advantages and disadvantages. You must which one is best suited for your current problem while avoiding falling into the old trap "If you have a hammer, every problem looks like nail."

"How long should this routine be? How long is too long?"
If the routine is longer than a screen page, it's too long.

"How short is too short?"
Maybe if the routine name is longer than the code it contains?

"When is code "too simple" to be in a routine?"
Wrong question. Are you writing the same three stupid lines of codes over and over again? Put them into a routine and call it several times instead.

"What's a good name for this routine?"
Okay that's a hard one. My general rule of thumb: routines called more frequently get shorter names. Yes I'm lazy. But hey I can always refactor it later.

"How will I know if the code in this routine succeeded? Should it return a success or error code? How will exceptions, problems, and error conditions be handled?"
If it encounters a problem, let it throw an exception. If things go wrong - and they will - at least you know where the error occured first. It's dangerous if you application seems to run flawlessly but internally has faulty data.

Just some suggestions

@zorkis:

Ah finally someone who read beyond the first line of the article.

&bull; "How long should this routine be? How long is too long?"
"If the routine is longer than a screen page, it's too long."

Hmm.. can't say I agree with that one. Too vague for a start. How big is a screen page exactly? Are we talking a 24x80 character xterm or 9-point text on a 2560x1600 pixel WQXGA screen?

The usual suggestion is between 50 and 100 lines. But an arbitrary limit seems too, well, arbitrary. Routines should exhibit strong cohesion. As long as the body of the routine is only concerned with a achieving a single goal then longer may be appropriate - though even then I would typically try break that down into logical 'steps' and create private routines for each step.

&bull; "How short is too short?"

I don't think there is a simple answer for that one. It may be entirely valid to have a method that does nothing at all, especially when using interfaces and polymorphism.

&bull; "If it encounters a problem, let it throw an exception."

I would say "If it encounters a [unexpected] problem [that cannot be handled internally], let it throw an exception."

I wouldn't be pleased if a FindInArray() routine threw an exception when it couldn't find the item, or if a Set.Add() threw when I tried an object that was already there. These are both expected 'problems' and their status should be conveyed without using exceptions.

Likewise if I call File.Delete() and file cannot be found then (arguably) that problem can be handled internally and the method can return success.

I'm a little surprised that the arguments around the greatest invention reolve around languages, subroutines, compilers, and microprocessors. As a programmer I agree that many of the things mentioned here have made huge strides in computing, but I don't any of these things would be possible without the sharing of information via the internet (otherwise I would have never read this post).

I reckon the greatest invention in computer science is the GUI. This has enabled non computer gurus the world over to actually use the things, giving us programmers something to do.

6502 handled the push and pop automatically in the CPU. It was that important, even in the '70's.

$02D8 LDA $41
$02DA JSR $FFD2 -- Someone will recognize what that really does.

$FFD2 NOP
$FFD3 RTS

Congrats on being dugg!

http://digg.com/programming/The_Greatest_Invention_in_Computer_Science

@Suresh:
Neither Ajax nor Adobe AIR is a programming language, so it looks like you stopped at JavaScript. ;-)

From the post: "Good programmers -- regardless of whatever language they happen to be working in -- understand the importance of crafting each routine with the utmost care."

What a blithe thing to say. Not all good programmers have the resources (= time) to craft each routine with the utmost care every time it needs to change. If you are working in a decent language (I use Python and JS, there are others) then not every routine has to be perfect the first time. Often they are, but I find that my routines often break the 2nd or third time I change them, but it usually doesn't take very long to fix them if you have exception tracebacks (Python has them by default, you can get them in JS with custom code). Just because Steve McConnell says it doesn't make it true.

@David: "Not all good programmers have the resources (= time) to craft... it usually doesn't take very long to fix them if you have exception tracebacks"

There are plenty of studies that cover the relative expense of fixing bugs at different times in the development cycle and I think pretty much all of them agree that spending extra time getting the code right to start with is still cheaper than debugging later. So the argument that you don't have time doesn't really work.

Besides, if you rely purely on "exception tracebacks" to find your errors then what about the logic errors that don't cause exceptions? And how do you even ensure you have found all your possible exceptions? Just fixing the exceptions that appear when you run it sounds like a recipe for producing code that "usually works".

> "(I use Python and JS, there are others)"

Aaaah.. well that explains it. He did say GOOD programmers :p

Jeff, do you even have a bachelor's degree in computer science? HOW can you ask this question and then write an entire post on just programming languages?

Aaaargh.

I disagree with most of the article.

I wouldn´t use routines until they are adopted by a significant number of programmers and know for sure they are a good coding practice.

Er, last comment should've read
Sebastian on June 12, 1948 02:19 PM

Isaac Z. Schlueter basically hit it.

The answer is the invention of formal proofs in geometry by Pythagoras. After "writing" my first FORTRAN program on punch cards I was struck by the similarity it had to the geometry proofs I did in 9th grade. Recall the way a proof in geometry unfolds in your mind and on paper or papyrus. The abstraction and use of formal language in a sequence of the clearest logic. How is it different in any way from what a coder produces ?

Do you recall that in the greek Olympics, Geometry-Proof-Skill was an event?

The question posed here is an historical question, in essence, and we are all the children of pythagoras, euclid, thales and aristotle.

You have to give Babbage an honorable mention though. The audacity to create a machine out of wood, metal, cloth and paper that could do complex calculations ? That was thought to be pretty much insane at the time.

cheers

@Kevin Z: Most of the inventions mentioned here (with the exception of a few not particularly revolutionary languages) were indeed possible, and actually existed long before the Internet.

@AL Pareigis (and others): None of the descriptions here of the early card-programmed mechanical machines mention anything that worked like a routine (callable from various points in a main sequence, often with parameters) - the most advanced structure seems to be the loop.

The invention of the Turing Machine by far is the most important invention of Computer Science.

Well,

While I thought this when I first read it I am glad that I am not alone in the idea of the compiler being the most important "invention" in computer science. While they could not be made without the use of routines, what's more important as a field wide invention the nuts and bolts or the final project? Personally I say the final project.

I noticed some were saying that wired routines (like in chip sets), may be the most important, but I would put that in the "computer itself" category as it is hardware.

Just my opnion, but then again that is what blogs and comments on blogs are for right?

These individuals must have been contributors to: "The Greatest Invention in Computer Science" both in hardware or software:

Computer Hall of Fame
http://www.computer-museum.org/hof/

It includes Grace Hopper. But I'm surprised it didn't include Donald Knuth - "The Art of Computer Programming", TeX.

http://en.wikipedia.org/wiki/Donald_Knuth

The AS400 (Silverlake project) and ReXX (Michael Cowlishaw) are pretty cool.

When I first read the question, I thought about OOP.

I thought about structured programming too, but what I like about the OOP concept is something that is a connection with CS with the real world. Routine is pure CS, but OOP took programming to other level, more connected with how things are in reality, under a human conception, obviously.

I kind of like when programmers demonstrate they can look away from their computers and make associations. Routine is just a way of doing the same things, but better. OOP involves a philosophy behind.

But... it's just a matter of my likes, of what one thinks it's more important. Definitely the routine paved the way for a sustainable work... but, hey, what about the variable?

<h6>hi</h6>

I agree OOP is the next big leap after routines & structured programming.

Exception handling is also a big leap (but not when used for validation errors! or as a method to pass back an alternative return type).
IBM had simple exceptions in PL/I a long time ago. It took ages for that to be superceded with the current model I first saw in Delphi.

'Intelligent' IDE's that OOP makes possible are a massive leap too.

> OOP involves a philosophy behind.
Loose data coupling and data hiding were around long before OOP. All OOP allows is a new way of sharing code/data which makes practical an extra level of indirection/abstraction allowing more complex taskes to be programmed. sadly it can lead to a lot of unnecessary fiddliness coz it gets used so badly so often!

In the early 1980's I worked on a very old PL/I or COBOL program (I can't remember which language). At 1st it looked horrible with GOTO's everywhere. Then I realised it was using label variables to branch to code that would branch back to the line after the invoking line.
The programmer had implemented routines and was doing structured programming before the language had a call statement - or else he was a structured assembler programmer who didn't know about the call statement!

>I hold the (admittedly unconventional) view that object orientated programming is actually hurting the industry. Object orientated thinking causes you to overly obsesses over the object model and focus less on the computation you're trying to perform.

> Does anybody out there agree with me or am I just a raving lunatic?
Nope - you are the prophet that seems like a lunatic to the herd!

I have long had misgivings about OO in business programming - the over-use of objects and 'design patterns' and abstractions that make life harder not easier.
Business programming has become technical and complex partly due to the horrendous coding required (or used for flashness) for browser interfaces and partly coz of OO. I read ages ago some guru saying if you look at the design mess of large COBOL applications you wonder what these guys will do with OO! My brother used to say of C++ 'you just can't use average programmers'. But business computing wants de-skilled programming - coz they are cheap and fast to train. it also wants 'shallow' logic - that can be understood by average programmers quickly.

I believe if dates and times were stored as char strings (in ISO format?) and manipulated with stateless static methods dates would be a doodle. A date is data not an object. But look at java calenders!
The object paradigm is rather irrelevant in most business processing. You can't have 1 customer object owning all customer data and operations.
I tried implementing an object model for financial transactions and it made it far more complicated.

The unit of code for much business processing is the transaction which operates on a data store. When all code for a transaction is together and uses subroutines it is easy to follow. When it is scattered thru an object hierarchy and across xml/object/data store layers it is harder to follow. People have object models where things look like they are peers when one is a slave/service to the other.
The static stateless method (subroutine) that changes parameters is the simplest logical structure hence the best to use. My systems would have maybe less than 50% of code inside objects.

So I am another lunatic.
PS OO is great for GUI widgets for sure! And for some frameworks if designed well - if the logic is kept 'shallow' and simple.

Agree with Johan Pretorius! I think practically speaking it is GUI [remember it is also the precursor to Web GUI].

Without GUI there wouldn't have been the explosive growth in CS we see now. Most of us would have been probably jobless as well.

Try to imagine normal clerks trying to accomplish their tasks, say reservation by typing
RESERVE fakrudeen male ... 40 more parameters!
It is when we compare inventions on the same vein as routine, language, assembler etc.

If we say in pure computer science terms, it has to be turing's computability papers [some problems are never computable etc.] followed by lambda calculus [lisp/scheme - precursor to all other languages] followed by finite automata theory which gave rise to regex [state machine], grammars [CFG etc.] etc. [precursor to compilers]

routine doesn't even come close as a great invention in my thinking. Then what about high level languages? Microprocessors? OOP and all other acronyms?

Right on, Warren! Copypasta is king.

Followed by spam, and CAPTCHA (the thing below what I'm typing!)