c
 c 


 

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
Data base query languages
Visual
Scripts
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.

c
 c
 

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.
xamples 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-THN-LS 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 utilisation. 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 parallelisation. Procedural programming tends to be relatively low level
compared to some other paradigms, and as a result can be very much less productive.

Ö   c
 

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

 
c
 

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 SCHM, HOP 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 non functional. 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.


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

 c
 

Rule based programming is also known as IF-THN 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 conceptualised in the expert system, then it will be both easy to design such
systems, and to use them to perform the task correctly. xpertise is primarily encapsulated in the
notion of IF-THN 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 characterise 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.

ý    

Data base query languages allow the development of applications on databases. Languages include
DBAS, ORACL, ACCSS, 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.

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

Ë! "  "
 

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 generalisation
(unlike programming by demonstration). xamples 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.

#c
 
  

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 generalises the user's sequence of actions to produce a general
program. One of the best known such systems is Cypher's AGR system which can automatically
detect repetitions in user's actions and build a program to perform them in the future.

$
 

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 parallelisation, it may start to decline as the
preferred approach to problem solving. Specialised 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 realised.

In this changing world an understanding of programming paradigms makes it easier for the
developer both to use an appropriate approach to problem solving and to adapt more easily to the
usage of new tools.
?