I envision the world of programming languages as a matrix of two possibilities.
imperative functional
(stateful) (stateless)
+----------------+----------------+
procedural |C COBOL | Lisp SASL |
(procedure- |Ada FORTRAN | Scheme Haskell|
oriented) |Basic ALGOL | ML |
+----------------+----------------+
object-oriented |Smalltalk C++ | |
(data-oriented) |Eiffel Java| |
| C# | |
+----------------+----------------+
You may be wondering about the lower right corner - where are the languages there? It's quite possible to design a language, but there doesn't seem to be an efficient alternative to go there. If you try to make an object-oriented, functional language, then you end up with a language that makes extremely heavy use of memory allocation and garbage collection, since the only thing a method can do is construct new objects. (It can't change existing variables, since this would imply state.) This isn't a practical combination of features.
I want to briefly outline two particularly important languages that are a bit different.
Lisp was the first functional language, and it was one of the first programming languages ever. One of the interesting things about it is its structure. Everything in a Lisp program is described as a list. A list would be written ``(a b c d)'' - we enclose a list in parentheses, with the individual elements within the list separated by spaces.
You can nest lists in LISP. For example, ``(a (b c))'' would be a list of two elements, where the second element is itself a list of two elements.
A LISP program is represented as a list.
Here, we define a function by creating a list beginning with the defun word, followed by the function name, followed by a list of the parameter names, followed by the function body. In this case, the function body is an if expression, represented as a list with if as the first element, the condition as the second element, and expressions computing the two possible return values third and fourth. In this case, the condition is itself a list, indicating to determine whether x < y.(defun max (x y) (if (> x y) x y))
LISP is a functional language (with some imperative pieces). Just as significant, however, is its simplistic approach to syntax, which leads it to be particularly useful in programs that manipulate other programs.
Most computer scientists think of there being three major categories of established programming languages - functional, object-oriented, and procedural/imperative. Prolog is in none of these categories: It is called a logical programming language.
The idea of Prolog is that you write the program by giving the program's specifications (using logical predicates), and the language system automatically determines how to accomplish those specifications.
For example, suppose we define a predicate parent(X,Y), which represents whether X is a parent of Y. Such a predicat could be defined exhastively.
But we could also define predicates by explaining their logical connection to other predicates. The following says that A is a grandparent of B if they A is the parent of some person C who is a parent of B.parent(Cheri, Carl). parent(Cecil, Cheri). parent(Fort, Cecil). parent(Dorothy, Cecil). parent(Paul, Dorothy).
(Pronounce ``:-'' as if and ``,'' and and.) The following is a way of describing an ancestor predicate.grandparent(A, B) :- parent(A, C), parent(C, B).
This says that any person X is an ancestor of himself or herself. And it says that A is an ancestor of B if A is the parent of some person C who is an ancestor of B.ancestor(X, X). ancestor(A, B) :- parent(A, C), ancestor(C, B)
Prolog is sophisticated enough to allow the definition of mathematical functions also, although these do not fit well into the paradigm. (Similarly, GUI programs fit poorly into the procedural paradigm, and computational programs don't tend to have much need for the object-oriented paradigm, so this isn't particularly damning.) Its applicability has proven to be limited, however, and people seem to be paying increasingly less attention to the idea. Some researchers are still working toward making the idea more viable, however.