Programming Paradigms

1. Introduction

A programming paradigm is a general approach to programming or to the solution of problems using a programming language.  Thus programming languages that share similar characteristics are clustered together in the same paradigm.

A programming language is a formal language for some form of problem solving.  It is to be distinguished from design languages such as hardware description languages, and other descriptive languages such as document description languages (e.g. SGML and HTML) or grammars.  A programming language necessarily entails some notion the program running on a computer to perform some process.

A programming paradigm is both a method of problem solving and an approach to programming language design.  A distinction can also be made between a programming language, and a programming environment.  Often programming in language A may be considered much easier than in language B simply because A has a much richer programming environment provided.  This environment has two important aspects.  First, the user interface  editor, compiler, debuggers and other tools provided to help the user develop programs.  Second, the libraries of procedures available.  There is also an issue of reusability and ease of use of library functions.

A distinction can be made between symbolic and non-symbolic (or numerical) programming.  In the early history of computers, it was thought that all one could do was various kinds of calculation, and indeed this was the main use of computers.  Thus languages such as FORTRAN were largely used for performing complex calculations.  In time, characters and strings became data types that could be manipulated within conventional programming languages.  On the other hand symbolic programming languages (such as LISP and PROLOG) were expressly developed to manipulate abstract symbols, and in particular to do list processing.  Any programs which require some form of "understanding", reasoning or complex interpretation need to do symbolic processing and are therefore normally best done using a language such as LISP or PROLOG.  This is why LISP and PROLOG  are the main languages used in AI.

The major paradigms are:

Procedural

Object-oriented

Functional

Logical

Rule-based

Visual

Programming by Demonstration

Other programming paradigms include simulation (e.g. SIMULA) and spreadsheets.

This course will concentrate on just three paradigms:

functional programming in LISP

logic programming in PROLOG

rule-based programming using an expert system shell.

2. Procedural Programming

Procedural programming is by far the most common form of programming.  A program is a series of instructions which operate on variables.  It is also known as imperative programming.  Procedural programming bears a close relation to the Von Neumann form of computer architecture, and early procedural languages were little more complex than assemblers.

Examples of procedural programming languages include FORTRAN, ALGOL, Pascal, C, MODULA2, Ada, BASIC.  Despite their differences they all share the common characteristics of procedural programming.

As a method of design, procedural programming attempts to encapsulate the human problem solving method of carrying out a sequence of operations.  First, one carries out step 1, then step 2, etc.  In addition, there are control structures such as IF-THEN-ELSE in all modern procedural languages.  Variables play a central role in programs, and their scope is an important notion in block structured languages.

Advantages of procedural programming include its relative simplicity, and ease of implementation of compilers and interpreters.  Procedural languages were important in the history of computers due to their low memory utilization.  Dijkstra believed that the introduction of microcomputers set back the development of computer science.  This was in part due to the fact that the small memory microcomputers could only run languages like BASIC with 8Kbyte interpreters, and that languages that were run on main frame and minicomputers (such as LISP) that needed larger memory could not be implemented on the micros.  All this has now changed with larger memory micros, but history has nevertheless affected the marketplace and people's perceptions of programming languages.

Disadvantages of procedural programming include the difficulties of reasoning about programs and to some degree difficulty of parallelization.  Procedural programming tends to be relatively low level compared to some other paradigms, and as a result can be very much less productive.

3. Object Oriented Programming

Object oriented programming was introduced by Xerox with the language Smalltalk.  This was intended to be a solution to the software crisis by providing an end-user programming language.  However, Smalltalk has a complex syntax and has not found to be easy to use, and certainly is not realistic for end-users.

At the same time as Smalltalk was developed another part of Xerox developed an object system within LISP, known as LOOPS.  This was the basis for the more recent CLOS (Common LISP Object System).

The most widely used object oriented language is C++ which provides object extensions to C, but this is rapidly being overtaken by Java.

Object oriented programming is characterized by the defining of classes of objects, and their properties.  Inheritance of properties is one way of reducing the amount of programming, and provision of class libraries in the programming environment can also reduce the effort required.

Object oriented programming has proved to be particularly successful in the design of user interlaces.

4. Functional Programming

Functional programming is based upon the notion of a program as a function in a similar sense to its usage in mathematics.  Programs are designed by the composition of functions.

The earliest functional language is LISP which was developed by John McArthy at MIT in the late 1950s.  This was based upon the lambda calculus.  However, early in the development of LISP non-functional elements were introduced, and it is possible to design programs in LISP in a procedural style.  LISP stands for LIST Processing, and it is the main language used for list processing applications.

Among other interesting qualities of LISP is the ability to compile functions at run time.  LISP programs are themselves data structures which can be manipulated by LISP, and therefore it is straightforward to write programs which change themselves as they run.  It is also possible to design and compile programs top down without any need for lower level functions to be designed earlier.  Since the modification of the design of a single function has no side effects on other functions, this makes modular programming straightforward.  LISP is also widely used to design new programming languages.

Due to LISP's pre-eminence in the development of AI programs, it has always had sophisticated programming environments.  Symbolics Inc. developed a range of computers whose CPUs were specifically designed to execute LISP efficiently, and their systems had a button on the keyboard marked DWIM (Do What I Mean).  Thus a user can expect the LISP system to in some sense understand his intentions, and this shows something of the possible sophistication.  LISP systems were also one of the first to develop interface editors that allowed a drawing type of interface, and automatic construction of code.

Other functional languages include SCHEME, HOPE and ML.

The major advantages of functional programming are that programs can be easy to understand and to formally reason about, and that functions are very reusable.  However, as with other languages it is also possible to design functional programs that are incomprehensible!  It is possible to develop and maintain very large programs consisting of thousands of functions, because functions have no side effects and it is therefore straightforward to fully test functions and the resulting systems.

The major disadvantage of functional programming is the difficulty of doing input-output since this is inherently nonfunctional.  There are also other aspects of problem solving that cannot easily or sensibly be performed in a functional manner.  Nevertheless large programs can be developed with about 80% of the code being designed purely functionally.

5. Logic Programming

Logic programming is usually equated with PROLOG programming, although in fact there are other logic programming languages available.  Nevertheless, due to the widespread usage of PROLOG it is natural that it has become almost interchangeable with logic programming.

Logic programming adopts a different approach to problem solving to both procedural programming and functional programming.  In essence, logic programming requires a logical declarative description of the nature of the problem.  How the program is to execute is not something the designer needs to worry about, and this is left to the PROLOG inference engine to deal with.  As a result this raises the level of abstraction considerably as the program contains no explicit control information.

A PROLOG program consists of facts and rules.  Running a program consists of asking a query about a fact.

Advantages of logic programming include the development of concise solutions to problems, and the ability to reason about the programs.  

Disadvantages of PROLOG programming include slowness of execution, the difficulties encountered in learning complex PROLOG programming.  Some people would add the difficulties in understanding complex PROLOG programs and the problems in debugging large PROLOG programs.  However, with careful design it should be possible to design PROLOG programs so that they can be understood purely declaratively.  It should not therefore be necessary for the reader to attempt to work out how the execution of the program will proceed, which is known as the procedural semantics.  Nevertheless many PROLOG programs cannot be understood without consideration of the procedural semantics.

6. Rule-based Programming

Rule based programming is also known as IF-THEN programming and as expert system design.  It shares many similarities with logic based programming, and in principle is simply a variant of it.  Nevertheless, practical rule-based systems are very different in their design and usage to PROLOG.

Rule-based programming has its origins in the very first electronic computer, the British Colossus developed at Bletchley Park by Alan Turing and his research team to decode the German submarine messages.  Rule based systems are also known sometimes as Post production systems and Post was probably the first developer of the idea.

Like logic programming the designer need not worry about the execution details of the program.  These are left to the inference engine of the expert system to sort out.  Thus this raises the level of abstraction of the programming.

Part of the development of rule-based programming methods has come from attempting to model the problem solving behaviour of human experts.  The idea has been that if the expert's thinking can be suitably captured and conceptualized in the expert system, then it will be both easy to design such systems, and to use them to perform the task correctly.  Expertise is primarily encapsulated in the notion of IF-THEN rules.

There appear to be two schools of thought in the design of expert systems.  The first attempts to study the human expert by means of interviews and the recording of problem solving activity known as protocol analysis.  This ultimately results in a set of rules which reflect the actual experience of the expert in solving problems.  The second approach adopts a more formal analysis of the task and produces a suitable behaviour tree or graph to characterize the possible states in problem solving.  The first approach is therefore more likely to correspond to the actual human experience, but is not necessarily very reliable, whist the second should be reliable but may not correspond to how people solve problems.

Rule-based systems are often used in the development of systems where at the outset of the work there is no clear idea about exactly how the task is performed.  But by detailed analysis of the expert's behaviour in solving problems and much testing it is possible to reveal the underlying logic in the expert's behaviour.  It is partly because rule-based systems are excellent at rapid prototyping that they are used in this way.  Arguments that the development of rule-based systems is very slow should consider the fact that this is due to the initial ignorance of the task domain, and that if the development was done in say a procedural language the development time would be even longer.

In recent years Schank and others have argued that experts do not solve problems using rules but using cases.  Schank makes a convincing argument, for example, in relation to medical and legal reasoning.  This has led to the development of Case Based Reasoning systems.

A major advantage of rule-based programming is that prototypes can often be developed very quickly.  Some rule-based languages are also easy to learn.

The main disadvantages of rule-based systems include slowness of execution and the difficulties of debugging.  More advanced rule-based systems include the ability to automatically generate procedural code (typically in C) which performs the same function as the expert system.  This usually solves the execution speed problem.

7. Data base query languages

Data base query languages allow the development of applications on databases.  Languages include DBASE, ORACLE, ACCESS, PARADOX.

The major advantages are the ease of use.

Disadvantages are execution speed and in some cases limited processing capabilities.  Naturally, they are limited to applications which involve the querying of databases.

8. Visual Programming

There are two different kinds of visual programming.  The first and more common is properly a visual programming environment that is an adjunct to an existing programming paradigm.  Examples include Visual BASIC and Visual C.  The second kind of visual programming sees program construction as a visual task similar to the solving of jig saw puzzles.  The user manipulates program shapes in a graphical interface.

9. Script based programming

Script based programming uses a direct representation of user's actions as a script.  Thus the programming language is designed in a more expressive manner to other programming languages.  Furthermore, a program is constructed to correspond directly to the operations that a user would execute.  Thus programs can often be constructed by means of recording the sequence of actions done by the user.  However, such recordings are literal and involve no attempt at generalization (unlike programming by demonstration).  Examples include HyperTalk, the scripting language of HyperCard, and its derivatives in other systems.  Another example would be AppleScript which works at the level of the operating system and provides a lingua franca for applications to communicate with one another.

10. Programming by Demonstration

Programming by Demonstration (PBD) is the most recent approach to programming and is largely only used at present within research laboratories and in limited applications such as drawing.  The essential notion is that the user demonstrates a program to the system by working through one or more examples.  The system then generalizes the user's sequence of actions to produce a general program.  One of the best known such systems is Cypher's EAGER system which can automatically detect repetitions in user's actions and build a program to perform them in the future.

11. Conclusion

All programming languages can implement a Turing machine.  Therefore as a result of the Church-Turing thesis any problem that can be solved using one programming language can also be solved using any other programming language.  However, there will be huge variations in the sizes of these programs, how long they take to develop, how reliably accurate they are, and in their execution speeds.  Designing a program to perform the calculus of differentiation is a short program in LISP or PROLOG, but very much more complex in other languages.  Likewise it is not often wise to develop data base applications in LISP, although if the system needs some form of reasoning they are sometimes developed in PROLOG.

The history of computing is in part the history of programming paradigms.  Procedural programming has a large cultural basis due to its historical importance, but with the need for greater productivity, the need for program reliability and the possibilities of parallelization, it may start to decline as the preferred approach to problem solving.  Specialized systems with ever more advanced environments will provide powerful and quick approaches to programming in niche areas.  Inevitably paradigms which are easy to use, highly reliable, and very productive will start to become more widely used.  No doubt there will be new paradigms developed in the future, and in time Xerox's dream of the end user doing his own programming will be realized.