Originally the first programming paradigm was the macro assembler. The focus was direct control of the logic circuit with the main enhancement being the ability to define a symbol for a group of instructions. You would think this would be an obvious and automatic advancement but it took a surprisingly long time to get established and even today there are plenty of languages (like Java) that do not support macros. Theorists don't like macros because they make a program more opaque, but as a practical matter their convenience is indisputable.

Next there were procedural languages like Fortran and COBOL. This seems to be the most persistently popular paradigm. It seems to me that the standard procedural toolkit (if, loop, goto, set) is crude, but most people don't seem to be bothered by it. Another language in this set is C which gave access to the memory and registers which Fortran had taken away. This and its terse, no unnecessary key strokes, style account for its popularity.

Before C came along however there were great experiments with the symbolic/functional languages like Lisp and ML. These languages definitely represented a new way of doing programming but curiously enough they tended to reiterate the same procedure tendencies in some ways.

A more specialized kind of need was fulfilled by the logic-based languages like Prolog. These languages cannot really be considered general languages though because their usefulness is restricted to certain kinds of problem-solving rather than controlling the computer. They are still an important precedent for the development of programming paradigms.

Another trend was the stack-based languages like Forth. In operation stack-based languages play out like macro systems on steroids. They seem not to be popular because they are so definitional. After building up a 10-layer definition you forget how layer 1 behaves and for anyone who did not write the program it is impossible to figure out what is going on. Nevertheless there are plenty of satellites and other such systems that run on Forth because before the advent of Java VM the easiest way to make a dedicated hardware VM was to have it implement a Forth interpreter.

Other than the above the only historical paradigm worth mentioning is flow-based programming. This idea--reducing programming to handling inputs and outputs--seems to make a lot of sense, but it never took off. This surprises me because if you think about how much awkward (and often buggy) coding procedural programmers must do to manage IO you would think an IO-centric programming language would be successful but it has not happened.

Advancements

There is only one historically significant paradigm enhancement I can think off: object-oriented programming. At first this idea manifested itself as a separate language (Smalltalk) but when the value of objects became obvious they were glommed on to the languages of choice C, Java, VB, whatever, and Smalltalk itself was discarded. Other than this it is hard to think of a major enhancement that has really changed the way people program. Some attempts at visual programming have been made, but they remain just that, attempts. The question is, what advancements can be made?

Looping Constructs: in the procedural languages in particular the looping constructs are particularly ham-handed. For example, there are two constructs, 'for' and 'do/while', both of which do basically the same thing. I can think of at least six fundamentally different kinds of loops yet there is no explicit recognition of this or support for it. Programmers must use the same for/do/while building blocks to implement all the different loop types. Usually they do it wrong if the loop has any complexity at all like multiple exit conditions. An obvious area for advancement would be to refine and enhance the looping constructs.

Parallel Processing: currently different parallel processes are managed with the thread concept. The problem with this is that threads are started and stopped arbitrarily. It would be better if there was a explicit scheduling mechanism so that thread execution was not unordered.

Branch Control: currently there are only two types of branches, call-and-return and goto. It would be a great improvement if we could use multi-point branching. This would allow alternative destinations to be specified when the branch was executed. For example, in the simplest scenario the caller would give a success destination and a failure destination. When the callee completed it would go either to success or failure. The main thing is that it is too restrictive to only be able to return to the place you came from. The caller should be able to specify various alternative places to go under different circumstances.