The evolution of programming languages - USF Computer Science 652 - Programming Languages

Because programming languages are at the core of how we communicate with machines, it is important that programmers understand a little bit about the history and evolution of programming languages. This helps to evaluate which languages to use for a project and also to develop new little languages.

From hardware-based languages towards higher-level abstractions

Programming languages control the behavior of computers and our first languages had elements that directly corresponded to the available hardware elements: just static memory and function calls (program counter register changes) without recursion. I guess you could say we started with pure machine code without even assemblers then moved to assemblers and onto higher-level languages. Why did we move away from machine code? machine code is very specific to a machine and not portable. More importantly, machine code is extremely tedious to write.

Even the first high-level languages were pretty close to the hardware. Example: Fortran ~1957 John Backus at IBM had a bunch of data and functions that operated on that static data. COBOL about the same time and, while the application was different, had same same high correlation to machine hardware. No hardware stacks, no recursive method calls and no local variables. no dynamic memory allocation.

Many programmers resist the change from lower to higher level languages citing concerns of efficiency. It was that way in the 1950s and it is still true today as people consider working with Python or Ruby instead of Java.

Amazingly, about the same time that FORTRAN was coming out we get a totally different approach: LISP ~1959 John McCarthy at MIT. LISP was more about expression of algorithms and encoding problems as a set of expressions.

Had recursion long before we had hardware stacks support for it.
Used recursion instead of loops.
side effect free execution; you are always just applying a function to an argument list and getting a result. I.e., there is no assignment statement.
had dynamic memory allocation and garbage collection.
by 1962, there was even an incremental compiler similar in concept to the Java HotSpot on-the-fly compiler.

Amazing for its time! Used for AI, list processing. Later, PROLOG in early 1970s for handling logical processes and making deductions.

During the early 60s we get a new crop of languages such as ALGOL60 (pascal programmers would recognize this) and BASIC 1964. Staying in that vein of imperative languages we get Pascal 1971 for structured programming. C early 1970s.

Moving towards object or to programming, we get Simula67, the first language to use the word "class". had objects and classes, subclasses and virtual procedures. See How object-oriented programming started. Alan Kay brings us Smalltalk in 1970s.

Hardware support for programming languages

Alan Kay: "it took years to get even rudimentary stack mechanisms into CPUs. Most machines still have no support for dynamic allocation and garbage collection and so forth."

Eventually we will need support for recording every side effect in order to get software transactional memory and other stuff.

Programming language abstraction categories

Paraphrasing Conception, evolution, and application of functional programming languages by Paul Hudak with a few thoughts of my own:

imperative programming languages: one focuses on altering state, i.e. side effects, by executing commands. there is a notion of sequence. there is a tight relationship between the CPUs program counter and flow through the program. most languages in use today are imperative. here is the quintessential imperative statement:
```
x = y;
```
it is a statement with side effects. Control assumed to flow to the statement following it.
declarative languages: have no implicit state. you don't worry so much about how something is computed, focusing instead on terms and expressions that encode rules are computations you would like to express. looping is done with recursion rather than loops. PROLOG is a good example of a declarative language; basic model is a set of relations. Sort of the data flow model. Variables of expressions are filled in when they are available. A dataflow computer is a set of functional units with data dependencies.

functional programming languages: all about evaluating expressions and are a kind of declarative language. LISP is the most famous and has been in use for 50 years. LISP says what not how. Instead of the assignment or branch statement like in an imperative language, the key model of computation is based upon the function. The result of a computation is the value of the program; you do not look in a memory location for the result like you would with an imperative language. Functions are treated as first-class objects, so you can pass them around like any other object. so-called "higher-order functions." higher order functions provide greater separation because they can serve as loop to tie to existing modules together. this is sort of like passing a code snippet to the sort mechanism so that it knows how to sort any kind of element without having to modify that element with an equals() method. Functional languages also typically have very powerful pattern matching mechanisms and lazy evaluation. pattern matching is like method overloading except based upon the structure of the incoming data element rather than simply its type. Without side effects, threading and parallel processing is trivial.

Imagine taking Java to LISP (imperative to functional): remove assignments and any other side effect inducing operations. As Hudak points out, however, unless that language is Python or Ruby the language is not particularly useful because most imperative languages lack any sort of nice functional programming elements.

Memory systems

static, global data. Fortran and COBOL
locals and recursion. Waited for introduction of hardware stack with the exception of LISP as far as I know. Note that CDC6000 machine on which I programmed had no hardware stack. You made a function call by storing a jump instruction to the return address at the first word(s) of the function you are calling. To return was to jump to the first instruction of the function. Weird.
dynamic memory allocation
garbage collection
lazy evaluation means you don't have to care about the order in which subexpressions are evaluated. lazy evaluation
software transactional memories: like transactions for a database. You can unroll a whole series of memory changes. Can be used to allow optimistic parallel processing and then roll back upon race or collision. As computers get faster and bigger and more parallel, we can literally record every single change made by a program.

Type systems

The following terms and definitions are pretty good ones I think, but there seems to be no consensus on their usage. Stick with the following.

static typing. Pascal, C, C++, Java. The type of every variable must be specified/known at compile time. Helps reduce errors and often helps in efficiency, is pretty annoying. Often leads to lots of typecasts.
dynamic typing. Python, Ruby, LISP. Typically you do not specify types of variables; run-time checks verify that the appropriate types are used. For example, in a dynamically typed language you can say x.close() even if you know that x is an integer; at run time it will throw an exception.
weak typing. Most languages have a few innocuous cases of weak typing such as char, int, and sometimes float being somewhat interchangeable. Some languages are pretty loose with types such as Perl and BASIC. You can, for example, add to strings that have numbers in them and store into an integer.
strong typing. Most commonly-used languages are strongly typed I would say. Basically means "type safety" or data elements of unknown type and tend not to float automatically to other types; i.e., very little implicit conversion of types or least very few ways to cheat the system. See http://en.wikipedia.org/wiki/Strong_typing.
untyped: assembly language. explicit conversion is required and there is no type checking at compile time or runtime.

See Comparison of programming languages for list of their type systems.

I recently started working on the concept of MANTRA:Type annotations. The basic idea is, instead of saying:

# a is an int and f returns a list with ...
f(a):
	...

say

list f(int a):
	...

It has the readability advantages of a statically typed program, but with the ease of development of a dynamically typed program.

Subprograms and modular, structured programming

Fortran and COBOL had no separate modules. Languages like ALGOL, Simula, Pascal, Modula, Ada, etc. started to introduce mechanisms for organizing code.

Simula and Smalltalk had dynamic (late) binding, which in the object-oriented world we call polymorphism. Method calls differ from function calls in that within method you do not know precisely which code it will actually execute. A method refers to multiple implementations. A receiving object decides how to respond to a message. By subclassing, we can override a method and alter which method is executed.

You will hear the term vtable (an array of pointers to functions), which is how C++ elements it's virtual method calls. Java starts out doing a full method lookup using reflection and then flips the byte code instruction to be a faster lookup using a vtable.

See Implementing Polymorphism.

Miscellaneous

You should know about Xerox PARC (Palo Alto research Center) whence: laser printer, windowing systems, smalltalk. cedar/mesa project that I believe introduced exceptions and also the concept of a monitor from which Java's threat mechanism was derived.

You can see that all current concepts have been around for a very long time. The software industry seems incredibly inertial.