Taxonomies of Programming Language Paradigms

4Taxonomies of Programming Language Paradigms

4.1Jean E. Sammet Taxonomy (Encyclopedia of Computer Science, 3^rd ed, 1993, “Programming Languages”, pp. 1123ff)

4.1.1Procedure Orientation

4.1.1.1Procedure-Oriented

4.1.1.2Nonprocedural

Furthermore, there can be an ordered sequence of steps, each of which is “somewhat nonprocedural”, or a set of executable operations whose sequence is not specified by the user. Both cases contribute to more “nonproceduralness”.

Thus, before the existence of such languages as Fortran, the statement could be considered nonprocedural because it could not be written as one executable unit and translated by any system. [Some writers would still consider an expression such as this, apart from its use in a statement, to be a nonprocedural feature of a procedural programming language.] In 1992, the sentences calculate the square root of the prime numbers from 7 to 91 and print in three columns and print all the salary checks are nonprocedural because there is no compiler available that can accept these statements and translate them; the user [programmer] must supply the specific steps required. As compilers are developed to cope with increasingly complex sentences, the nature of the term changes. Thus, what is considered nonprocedural today may well be procedural tomorrow. [This is, again, a rather idiosyncratic concept of nonprocedural classification.]

The best example of a currently available nonprocedural language is Prolog;

4.1.1.2.1other nonprocedural systems (not really languages)

4.1.1.2.1.1report generators (RPG)

4.1.1.2.1.2sort generators

4.1.1.3Burton M. Leavenworth & Jean E. Sammet Taxonomy for Nonprocedural Languages & Systems (Encyclopedia of Computer Science, 3^rd ed, 1993, “Nonprocedural Languages”, pp. 934ff)

4.1.1.3.1Some of the descriptive terms that have often been applied to the word “language” to convey essentially the same concept:

4.1.1.3.1.1nonprocedural

4.1.1.3.1.2very high level

4.1.1.3.1.3less procedural

4.1.1.3.1.4goal-oriented

4.1.1.3.1.5problem-oriented

4.1.1.3.1.6pattern-directed

4.1.1.3.1.7declarative

4.1.1.3.1.8functional / Functional (= Applicative) Programming (David S. Wise, Encyclopedia of Computer Science, 3^rd ed, 1993, pp. 573ff)

4.1.1.3.1.8.1Dataflow: Languages (Vason P. Srini, Encyclopedia of Computer Science, 3^rd ed, 1993, pp. 418-9)

a functional programming language in which a variable may be assigned a value once and only once throughout a program.

There are programming languages, such as Prolog, that also use single assignment to a variable, but are not dataflow languages.

If the same variable name is used on the left side of an assignment statement in more than one place in a dataflow language program, the second and other appearances of the variable are treated as new variables.

Many of the constructs found in block-structured languages, such as Pascal and C, are usually supported in a dataflow language also.

Data structures, such as lists, records, and arrays, are also supported along with operations on them. The single assignment rule complicates modification to an element of a list or an array. Copying entire lists or arrays when only a single element needs to be modified is expensive. Parallel data structuring mechanisms have been devised to avoid the copying.

4.1.1.3.1.9Logic Programming (Robert Kowalski, Encyclopedia of Computer Science, 3^rd ed, 1993, “Programming Languages”, pp. 778ff; “…: Languages”, Keith L. Clark, pp. 783ff)

can be regarded as the special case of a logic program where all statements have the form of conclusions without any conditions, variables, or function symbols. [I believe that this applies to the expression of the database itself, rather than languages, such as SQL, which manipulate the database.]

4.1.1.3.1.9.2deductive database

can be regarded as a logic program that does not contain function symbols

4.1.1.3.1.9.3Delaying Calls & Coroutining [beyond Prolog]

More modes of use of the Horn clauses of a logic program are retained if the query evaluator can delay the evaluation of some call if certain arguments are unbound. One use of this is dynamic reordering of the calls of clauses. It also allows dataflow coroutining, where the transfers between calls is triggered by the binding of shared variables. Some successors of Prolog (e.g. Nu-Prolog & Prolog II) allow such delaying of calls.

4.1.1.3.1.9.4Parallelism

As noted earlier, logic programming offers many opportunities for parallelism. Several concurrent logic programming languages and parallel implementations of logic programming have been developed.

An obvious way to parallelize Prolog is to allow for parallel search of the tree of alternative evaluation paths. This is called or-parallelism. Or-parallel versions of Prolog have been implemented on multiprocessor machines. One such language, Aurora Prolog, has the useful feature that it will run existing Prolog applications, often with considerable speed-up.

In some or-parallel implementations, independent calls are also evaluated in parallel. These are adjacent calls, the first of which is just about to be evaluated, that share no unbound variable.

Allowing the parallel evaluation of calls that share variables is a much more radical step. If this is coupled with delaying of calls when certain variables are unbound, it allows concurrent dataflow programming, the parallelization of dataflow coroutining. Concurrent Prolog, GHC, Parlog, and Strand are concurrent dataflow LP languages. …

4.1.1.3.1.9.5Constraints

It is possible to improve efficiency significantly by manipulating certain conditions as constraints. Several logic programming languages incorporating constraints have been developed.

4.1.1.3.1.9.6Constraint Logic Programming Languages

Even more generality of use is retained by having primitives that automatically delay and are capable of being called and solved for more than one mode of use. An example is a primitive to solve simple equations such as , which delays if X and Y were both unbound, but which will solve the equation as soon as either becomes bound. The constraint logic programming languages, such as Prolog III, Chip, and CLP(R) do this. At some implementation cost, they actually do much more. …

4.1.1.3.1.9.7Objects

An important area of research has been the development of systems that combine logic programming and object-oriented programming or object-oriented knowledge representation. One such approach is based on an interpretation of objects as processes in concurrent logic programming languages.

4.1.1.3.1.9.8Metaprogramming

This is a common and powerful logic programming technique for implementing more powerful theorem-provers (sometimes called “inference engines”).

4.1.1.3.1.9.9Types, functions, metalogic, higher-order logic, non-classical logic, integrity checking and abduction

Many proposals have been made to extend or modify logic programming by incorporating these features.

4.1.1.3.1.10relational

4.1.1.3.1.11problem statement

4.1.1.3.1.12problem definition

4.1.1.3.1.13problem description

4.1.1.3.1.14specification

4.1.1.3.1.15result specification

4.1.1.3.1.16task description

4.1.1.3.2Features of Nonprocedural Languages

4.1.1.3.2.1Associative Referencing

4.1.1.3.2.2Aggregate Operators

4.1.1.3.2.3Elimination of Arbitrary Sequencing

4.1.1.3.3Database Languages

4.1.1.3.4Other Systems Related to Nonprocedural Languages

4.1.1.3.4.1Report Program Generators (RPGs)

4.1.1.3.4.2Spreadsheets

4.1.1.3.4.3Fourth-Generation Languages (4GLs)

4.1.2Domains of Application

4.1.2.1[Machine-oriented: Machine and Assembly/Assembler Languages]

4.1.2.2Problem-oriented

4.1.2.3Application-oriented

For example, Fortran is primarily useful for numerical scientific problems,

whereas Cobol is best suited for business data processing.

On the other hand, PL/I and Ada are useful in both those application areas, and therefore have a wider area of application.

4.1.2.3.1General Purpose

4.1.2.3.2Application areas sufficiently wide and important to justify particular consideration:

4.1.2.3.2.1numerical and nonnumerical (i.e. formal algebraic) scientific applications

4.1.2.3.2.2business data processing

4.1.2.3.2.3string and list processing

4.1.2.3.3Special-Application-Oriented

4.1.2.3.4Special-purpose language

4.1.3Problem-defining = Specification Language