CIS504 Programming Languages

<< back to courseware demo page - This online lecture is for demonstration purposes

The lecure is to be used only in conjunction with the required text for this course:
"Programming Languages, Principles and Practice", 2nd Edition, by Kenneth C Louden, Books/Cole-Thomson Learning. The copyright of the material and illustrations is held by Kenneth C. Louder.

Lesson 1:
Language Abstraction and
Computational Paradigms

How we communicate influences how we think, and vice versa. Similarly, how we program computers influences how we think about them, and vice versa. Over the last several decades a great deal of experience has been accumulated in the design and use of programming languages. Although there are sti11 aspects of the design of programming languages that are not well understood, the basic principles and concepts now belong to the fundamental body of knowledge of computer science. A study of these principles is as essential to the programmer and computer scientist as the knowledge of a particular programming language such as C or Java. Without this knowledge it is impossible to gain the needed perspective and insight into the effect programming languages and their design have on the way we communicate with computers and the ways we think about computers and computation.

It is the goal of this text to introduce the major principles and concepts underlying all programming languages without concentrating on one particular language. Specific languages are used as examples and illustrations, These languages include C, Java, C++, FORTRAN, Ada, LISP, Prolog. It is not necessary for the reader to be familiar with all these languages, or even any of them, to understand the concepts being illustrated. At most the reader is required to be experienced in only one programming language and to have some general knowledge of data structures, algorithms, and computational processes.

In this chapter we will introduce the basic notions of programming languages and outline some of the basic concepts. We will also briefly discuss the role of language translators. However, the techniques used in building language translators will not be discussed in detail in this book.
 

1.1 What is a Programming Language?

A definition often advanced for a programming language is "a notation for communicating to a computer what we want it to do."

But this definition is inadequate, Before the 1940s computers were programmed by being "hard-wired": switches were set by the programmer to connect the internal wiring of a computer to perform the requested tasks. This effectively communicated to the computer what computations were desired, yet switch settings can hardly be called a programming language.

A major advance in computer design occurred in the 1940s, when John von Neumann had the idea that a computer should not be "hard-wired" to do particular things, but that a series of codes stored as data would determine the actions taken by a central processing unit. Soon programmers realized that it would be a tremendous help to attach symbols to the instruction codes, as well as to memory locations, and assembly language was born, with instructions such as

But assembly language, because of its machine dependence, low level of abstraction, and difficulty in being written and understood, is also not what we usually think of as a programming language and will not be studied further in this text. (Sometimes, assembly language is referred to as a low-level language to distinguish it from the high-level languages, which are the subject of this text. ) Indeed, programmers soon realized that a higher level of abstraction would improve their ability to write concise, understandable instructions that could be used with little change from machine to machine. Certain standard constructions, such as assignment, loops, and selections or choices, were constantly being used and had nothing to do with the particular machine; these constructions should be expressible in simple standard phrases that could be translated into machine-usable form, such as the Pascal for the previous assembly language instructions (indicating assignment of the value 2 to the location with name X)

Programs thus became relatively machine independent, but the language still reflected the underlying architecture of the von Neumann model of a machine: an area of memory where both programs and data are stored and a separate central processing unit that sequentially executes instructions fetched from memory.
Most modem programming languages still retain the flavor of this processor model of computation. With increasing abstraction, and with the development of new architectures, particularly parallel processors, came the realization that programming languages need not be based on any particular model of computation or machine, but need only describe computation or processing in general. This leads us to state the following definition.

---

Definition: A programming language is a notational system for describing computation in machine-readable and human-readable form.

---

We wi11 discuss the three key concepts in this definition.

Computation. Computation is usually defined formally using the mathematical concept of a Turing machine, which is a kind of computer whose operation is simple enough to be described with great precision. Such a machine needs also to be powerful enough to perform any computation that a computer can, and Turing machines are known to be able to carry out any computation that current computers are capable of (though certainly not as efficiently). In fact, the generally accepted Church’s thesis states that it is not possible to build a machine that is inherently more powerful than a Turing machine.

Our own view of computation in this text is less forma1. We will think of computation as any process that can be carried out by a computer. Note, however, that computation does not mean simply mathematical calculation, such as the computation of the product of two numbers or the logarithm of a number, Computation instead includes alt kinds of computer operations, including data manipulation, text processing, and information storage and retrieva1. In this sense, computation is used as a synonym for processing of any kind on a computer. Sometimes a programming 1anguage will be designed with a particular kind of processing in mind, such as report generation, graphics, or database maintenance. Although such special-purpose languages may be able to express more genera1 kinds of computations, in this text we will concentrate on the general purpose languages that are designed to be used for general processing and not for particular purposes.

Machine readability. For a language to be machine-readable, it must have a simple enough structure to a11ow for efficient translation. This is not something that depends on the notion of any particular machine, but is a general requirement that can be stated precisely in terms of definiteness and complexity of translation. First, there must be an algorithm to translate a language, that is, a step-by-step process that is unambiguous and finite. Second, the algorithm cannot have too great a complexity: most programming languages can be translated in time that is proportional to the size of the program. Otherwise, a computer might spend more time on the translation process than on the actual computation being described. Usually, machine readability is ensured by restricting the structure of a programming language to that of the so-called context-free languages, which are studied in Chapter 4, and by insisting that all translation be based on this structure.

Human readability. Unlike machine readability, this is a much less precise notion, and it is also less understood. It requires that a programming language provide abstractions of the actions of computers that are easy to understand, even by persons not completely familiar with the underlying details of the machine. One consequence of this is that programming languages tend to resemble natural languages (like English or Chinese), at least superficially. This way, a programmer can rely on his or her natural understanding to gain immediate insight into the computation being described. (Of course, this can lead to serious misunderstandings as well. )

Human readability acquires a new dimension as the size of a program increases. (Some programs are now as large as the largest novels.) The readability of large programs requires suitable mechanisms for reducing the amount of detail required to understand the program as a whole. For example, in a large program we would want to localize the effect a small change in one part of the program would have – it should not require major changes to the entire program. This requires the collection of local information in one place and the prevention of this information from being used indiscriminately throughout the program. The development of such abstraction mechanisms has been one of the important advances in programming language design over the past two decades, and we will study such mechanisms in detail in later Chapters.

Large programs also often require the use of large groups of programmers, who simultaneously write separate parts of the programs. This substantially changes the view that must be taken of a programming language. A programming language is no longer a way of describing computation, but it becomes part of a software development environment that promotes and enforces a software design methodology. Software development environments not only contain facilities for writing and translating programs in one or more programming languages, but also have facilities for manipulating program files, keeping records of changes, and performing debugging, testing, and analysis. Programming languages thus become part of the study of software engineering. Our view of programming languages, however, will be focused on the languages themselves rather than on their place as part of such a software development environment. A software engineering text can more adequately treat the design issues involved in integrating a programming language into a software development environment.
 

1.2  Abstractions in Programming languages

We have noted the essential role that abstraction plays in providing human readability of programs. In this section we briefly describe common abstractions that programming languages provide to express computation and give an indication of where they are studied in more detail in subsequent chapters. Programming language abstractions fall into two general categories: data abstraction and control abstraction. Data abstractions abstract properties of the data, such as character strings, numbers, or search trees, which is the subject of computation. Control abstractions abstract properties of the transfer of control, that is, the modification of the execution path of a program based on the situation at hand. Examples of control abstractions are loops, conditional statements, and procedure calls.

Abstractions also fall into levels, which can be viewed as measures of the amount of information contained in the abstraction. Basic abstractions collect together the most localized machine information. Structured abstractions collect more global information about the structure of the program. Unit abstractions collect information about entire pieces of a program.

In the following paragraphs we classify common abstractions according to the levels of abstraction, for both data abstraction and control abstraction.

1.2.1 Data Abstractions

Basic abstractions. Basic data abstractions in programming languages abstract the internal representation of common data values in a computer. For example, integer data values are often stored in a computer using a two’s complement representation, and standard operations such as addition and multiplication are provided. Similarly, a real, or floating-point, data value is usually provided. Locations in computer memory that contain data values are abstracted by giving them names and are called variables. The kind of data value is also given a name and is called a data type. Data types of basic data values are usually given the names of their corresponding mathematical values, such as integer and real. Variables are given names and data types using a declaration, such as the Pascal

var x: integer;

or the equivalent C declaration

int x;

In this example, x is established as the name of a variable and is given the data type integer.

Structured abstractions. The data structure is the principal method for abstracting collections of data values that are related. For example, an employee record may consist of a name, address, phone number, and salary, each of which may be a different data type, but together represent the record as a whole. Another example is that of a group of items, all of which have the same data type and which need to be kept together for purposes of sorting or searching. A typical data structure provided by programming languages is the array, which collects data into a sequence of individually indexed items. Variables can be given a data structure in a declaration, as in the C

int a[10];

or the FORTRAN

INTEGER a(10)

which establish the variable a as containing an array of ten integer values. Data structures can also be viewed as new data types that are not internal, but are constructed by the programmer as needed. In many languages these types can also be given type names, just as the basic types, and this is done in a type declaration, such as the C

typedef int Intarray[10];

Such data types are called structured types.

Unit abstractions. In a large program, it is useful and even necessary to collect all the information needed for the creation and use of a data type into one location and to restrict the access to the details of the data type. This ensures that changes in the structure of the data type do not affect large areas of the program and that programmers need not keep all the details of a data type in mind at all times, A programming language mechanism that provides this is called a data encapsulation or, more commonly, an abstract data type mechanism.

1.2.2 Control Abstractions

Basic abstractions. Typical basic control abstractions are those statements in a language that combine a few machine instructions into a more understandable abstract statement. We have already mentioned the assignment statement as a typical instruction that abstracts the computation and storage of a value into the location given by a variable, as for example,

x=x+3

This assignment statement represents the fetching of the value of the variable x, adding the integer 3 to it, and storing it again in the location of x. .

Another typical basic control statement is the goto statement, which abstracts the jump operation of a computer or the transfer of control to a statement elsewhere in a program, such as the FORTRAN

  GOTO 10
C this part skipped
  ..........
  ..........
C control goes here
10 CONTINUE

Goto statements today are considered too close to the actual operation of a computer to be a useful abstraction mechanism (except in special situations), so most modem languages provide only very limited forms of this statement.

Structured abstractions. Structured control abstractions divide a pro-gram into groups of instructions that are nested within tests that govern their execution. Typical examples are selection statements, such as the if-statement of many languages, the case-statement of Pascal, and the switch-statement of C. For example, in the following Pascal code,

if x > 0.0 then

else

    begin

the three statements within the first begin-end pair are executed if x > 0, and the single statement within the second begin-end pair otherwise.

One advantage of structured control structures is that they can be nested within other control structures, usually to any desired depth, as in the following Pascal code (which is a modification of the foregoing example):

if x> 0.0 then

else

Structured looping mechanisms come in many forms, including the while, and for loops of C, the repeat loops of Pascal, and the loop-exit mechanism of Modula-2. For example, the following program fragments, first in C and then Modula-2, both compute x to be the greatest common divisor of u and v using Euclid’s algorithm (for example, the greatest common divisor of 8 and 20 is 4, and the greatest common divisor of 3 and 11 is 1):

/* C example */
x=u; y=v;
while (y>0)
{ t= y;
  y=x % y; /* the integer mod operation in C */
x=t;}

A further, powerful mechanism for structuring control is the procedure, sometimes also called a subprogram or subroutine. This allows a programmer to consider a sequence of actions as a single action and to control the interaction of these actions with other parts of the program. Procedure abstraction involves two things. First, a procedure must be defined by giving it a name and associating with it the actions that are to be performed. This is called procedure declaration, and it is similar to variable and type declaration, mentioned earlier. Second, the procedure must actually be called at the point where the actions are to be performed. This is sometimes also referred to as procedure invocation or procedure activation.

As an example, consider the sample code fragment that computes the greatest common divisor of integers u and v. We can make this into a procedure in Ada with the following procedure declaration:

procedure gcd (u,v: in integer; ;  x: out integer) is
  y, t, z: integer;
begin
    z := u;
    y := v;
    loop
     t ::= y;
    y := z mod  y;
    z := t
    end loop;
   x := z;
end gcd

In this declaration, u, v, and x have become parameters to the procedure, that is, things that can change from call to call. This procedure can now be called by simply naming it and supplying appropriate actual parameters or arguments, as in

which gives d the value 2. (The parameter x is given the VAR label to indicate that its value is computed by the procedure itself and will change the value of the corresponding actual parameter of the caller.)

In FORTRAN, by contrast, a procedure is declared as a subroutine,

and is called using an explicit call-statement:

CALL gcd(a,b,d)

Procedure call is a more complex mechanism than selection or looping, since it requires the storing of information about the condition of the program at the point of the call and the way the called procedure operates. Such information is stored in a runtime environment.

Unit abstractions. Control can also be abstracted to include a collection of procedures that provide logically related services to other parts of a program and that form a unit, or standalone, part of the program. For example, a data management program may require the computation of statistical indices for stored data, such as mean, median, and standard deviation. The procedures that provide these operations can be collected into a program unit that can be translated separately and used by other parts of the program through a carefully controlled interface. This allows the program to be understood as a whole without needing to know the details of the services provided by the unit. Examples of unit abstractions include the module of Modula-2 and the package of Ada. Note that unit abstractions for data and for control are essentially the same.

One kind of control abstraction that does not fit into any one abstraction level is that of parallel programming mechanisms. Many modem computers have several processors or processing elements and are capable of processing different pieces of data simultaneously. A number of programming languages have included mechanisms that allow for the parallel execution of parts of programs, as well as providing for synchronization and communication among such program parts.  Ada provides the task mechanism for parallel execution. Ada’s tasks are essentially a unit abstraction.Other languages provide different levels of parallel abstractions, even down to the statement level.

It is worth noting that almost all abstraction mechanisms are provided for human readability, If a programming language needs to describe only computation, then it needs only enough mechanisms to be able to describe all the computations that a Turing machine can perform, Such a language is called Turing complete. As the following property shows, Turing completeness can be achieved with very few language mechanisms:

---

A programming language is Turing complete provided it has integer variables and arithmetic and sequentially executes statements, which include assignment, selection (if) and loop (while) statements.

---

1.3 Computational Paradigms

Imperative Programming:

Programming languages began by imitating and abstracting the operations of a computer. It is not surprising that the kind of computer for which they were written had a significant effect on their design. In most cases the computer in question was the von Neumann model: a single central processing unit that sequentially executes instructions that operate on values stored in memory. Indeed, the result on Turing completeness of the previous section explicitly referred to sequential execution and the use of variables and assignment. These are typical features of a language based on the von Neumann model: variables represent memory values, and assignment allows the program to operate on these memory values.

A programming language that is characterized by these three properties – the sequential execution of instructions, the use of variables representing memory locations, and the use of assignment to change the values of variables – is called an imperative language, since its primary feature is a sequence of statements that represent commands, or imperatives. Sometimes such languages are also called procedural but this has nothing explicitly to do with the concept of procedures discussed earlier.

Most programming languages today are imperative. But it is not necessary for a programming language to describe computation in this way. Indeed, the requirement that computation be described as a sequence of instructions, each operating on a single piece of data, is sometimes referred to as the von Neumann bottleneck, since it restricts the ability of a language to indicate parallel computation, that is, computation that can be applied to many different pieces of data simultaneously, and non-deterministic computation, or computation that does not depend on order: asynchronous.' Thus it is reasonable to ask if there are ways to describe computation that are less dependent on the von Neumann model of a computer. Indeed there are, and these will be described shortly, Imperative programming languages therefore become only one paradigm, or pattern, for programming languages to follow.

Two alternative paradigms for describing computation come from mathematics. The functional paradigm comes from traditional mathematics and is based on the notion of a function, The logic paradigm is based on symbolic logic, which has been developed primarily in the last century. Each of these will be the subject of a subsequent chapter, but we will discuss them in a little more detail here.
 

Functional programming.

The functional paradigm bases the description of computation on the evaluation of functions or the application of functions to known values. For this reason, functional languages are sometimes called applicative languages.A functional programming language has as its basic mechanism the evaluation of a function, or the function call. This involves, besides the actual evaluation of functions, the passing of values as parameters to functions and the obtaining of the resultant values as returned values from functions. The functional paradigm involves no notion of variable or assignment to variables. Also, repetitive operations are not expressed by loops (which require control variables to terminate) but by recursive functions. Indeed the study of recursive function theory in mathematics has established the following property:

---

A programming language is Turing complete if it has integer values, arithmetic functions on those values, and if it has a mechanism for defining new functions using existing functions, selection, and recursion.

---

It may seem surprising that a programming language can completely do away with variables and loops, but that is exactly what the functional paradigm does, and there may be advantages to doing so. We have already stated one: that the language becomes more independent of the machine model, with the possibility that such languages may be better suited to the machines of the future. Another is that, because functional programs resemble mathematics, it is easier to draw precise conclusions about their behavior. Exactly how this is possible is left to later chapters. We content ourselves here with one example of functional programming.

Note: Parallel and non-deterministic computations are related concepts.

Let us return to the Ada procedure to compute the greatest common divisor of two integers that we gave in the last section. A functional version of this procedure is as follows
 

Note that this code does not use any local variables or loops, but does use recursion (it calls itself with a different set of parameters). Note also the use of the return statement to indicate the value returned by the function.

In an even more functionally oriented programming language, such as LISP, this function would be written as follows (here and throughout the book we use the Scheme dialect of LISP):

A few comments about this Scheme code may be worthwhile.

In LISP, programs are list expressions, that is, sequences of things separated by spaces and surrounded by parentheses, as in (+ 2 3). Programs are run by evaluating them as expressions, and expressions are evaluated by applying the first item in a list, which must be a function, to the rest of the items as arguments. Thus (gcd 8 18) applies the gcd function to parameters 8 and 18. Similarly 2 + 3 is written (+ 2 3), which applies the "+" function to the values 2 and 3.

In the definition of the gcd function we have used the if-then-else function, which is just called "if" – the "then" and "else" are dispensed with. Thus ( i f a b c) means "if a then b else c." Note that the "if" function represents control as we11 as the computation of a value: first a is evaluated and, depending on the result, either b or c is evaluated, with the resulting value becoming the returned value of the function. (This differs from the "if" statement of Pascal, C, or Ada, which does not have a value.)

Finally, LISP does not require a return-statement to indicate the value returned by a function. Simply stating the value itself implies that it is returned by the function.
 

Logic programming.

This language paradigm is based on symbolic logic. In a logic programming 1anguage, a program consists of a set of statements that describe what is true about a desired result, as opposed to giving a particular sequence of statements that must be executed in a fixed order to produce the result. A pure logic programming language has no need for control abstractions such as loops or selection. Control is supplied by the underlying system. All that is needed in a logic program is the statement of the properties of the computation. For this reason, logic programming is sometimes called declarative programming, since properties are declared, but no execution sequence is specified. (Since there is such a removal from the details of machine execution, logic programming languages are sometimes referred to as very-high-level languages.)

In the example of the greatest common divisor, we can state the properties of gcd in a form similar to that of a logic program as follows:

The gcd of u and e is u if v = 0.

The gcd of u and v is the same as the gcd of v and u mod v if e is > 0.

A number of logic programming languages have been developed in the past decade, but only one has become widely used: Prolog. The gcd statements given translate into Prolog as follows:

In Prolog, the form of a program is a sequence of statements, called clauses, which are of the form

Such a clause roughly corresponds to the assertion that a is true if b and c and d are true. Unlike functional programming (and more like imperative programming), Prolog requires values to be represented by variables. How-ever, variables do not represent memory locations as they do in imperative programming, but behave more as names for the results of partial computations, as they do in mathematics.

In the Prolog program, g c d has three parameters instead of two: the third represents the computed value, since g c d itself can only be true or false (that is, it can only succeed or fail). Note also the use of uppercase for variables. This is a standard convention for Prolog.

The first of the two clauses for g c d states that the gcd of U and V is U, provided V is equal to 0. The second clause states that the gcd ot U and V is X, provided V is greater than 0, and that X is the result of the gcd of V and Y, where Y is equal to U mod V, (The "is" clause for Y is somewhat like assignment in an ordinary programming language and gives Y the value of U mod V.)
 

Object-Oriented Programming

Another programming Paradigm is object-oriented programming paradigms. Object-oriented programming, not only as a language paradigm, but also as a methodology for program design, has experienced an explosion in interest and activity, much as structured programming and top-down design did in the early 1970s.

There is one more language paradigm that has gained much attention in recent years: object-oriented programming. It is based on the notion of an object, which can be loosely described as a collection of memory locations together with all the operations that can change the values of these memory locations. The standard simple example of an object is a variable, with operations to assign it a value and to fetch its value. In a sense, object-oriented programming is the opposite of functional programming: it concentrates on memory locations rather than values and functions. It represents computation as the interaction among, or communication between, a group of objects, each of which behaves like its own computer, with its own memory and its own operations. In many object-oriented languages, objects are grouped into classes that represent all the objects with the same properties. Classes are defined using declarations, much as structured types are declared in a language like C or Pascal. Objects are then created as particular examples, or instances, of a class.

In our running example of the greatest common divisor of two integers, the object-oriented view of the gcd is as an object that is created by supplying it with the information on which it depends, namely, the parameters u and e. The object can then be queried for its value, which is the result of computing the greatest common divisor of its initial values.

The language that introduced the notion of class and object was Simula67. A major role was played by Smalltalk in stimulating interest in the object-oriented paradigm, which has grown substantially in recent years. A number of newer languages, especially C++, have now become popular. We will give a solution to the gcd example in Java, however, since it easy to read and understand:

public class IntWithGcd;
{ public  IntWithGcd(int val) { value = val;}
  public int intValue() { return value;}
  public int gcd ( int v)
  { int z = value;
    int y = v;
    while (y != 0)
     { int t = x;
       y = z % y;
       z = t;
      }
      return z;
    }
  private int value;
}

This class can be used by defining an object of the class as follows:

IntWithGcd x;

In this declaration the significance of the keyword "IntWithGcd" is a type  reference. At first there is no actual memory allocated to x; we must create, or instantiate, the object with the following assignment-like statement:

x = new IntWithGcd(8);

Then we can ask x to tell us its value by calling the value procedure, as for example, in

int y = x.gcd(18);

It needs to be stressed that, even though a programming language may exhibit most or all of the properties of one of the four paradigms just discussed, few languages adhere purely to one paradigm, but usually contain features of several paradigms. Indeed, as we saw, we were able to write a functional version of the gcd function in Ada, a language that is considered to be more of an imperative language. Nevertheless, it and most other modem imperative languages permit the definition of recursive functions, a mechanism that is generally considered to be functional. Similarly, the Scheme dialect of LISP, which is considered to be a functional language, does permit variables to be declared and assigned to, which is definitely an imperative feature. Scheme programs can also be written in an object-oriented style that closely approximates the object-oriented paradigm. Thus we can refer to a programming style as following one (or more) of the paradigms. In a language that permits the expres-sion of several different paradigms, which one is used depends on the kind of computation desired and the requirements of the development environment.
 

Event-Driven Visual Programming

All the paradigms we’ve examined so far – imperative, object-oriented, functional, and logic programming – are based on a fundamental model of computation in which the program design predetermines what will occur when the program is run.
Our imperative programming minds visualize a process in which the program controls the sequence of steps that occur at run time, and the input data play a relatively passive role in regulating how those steps are carried out. Moreover, in designing such a program, we visualize a process that will always terminate once its steps are completed. The event-driven programming paradigm turns this world inside out. Event-driven programs do not predict the control sequence that will occur; they are written to run reasonably to any particular sequence of events that may occur once execution begins, In this model, the input data govern the particular sequence of control that is actually carried out by the program. Moreover, execution of an event-driven program does not typically terminate; such a program is designed to run for an arbitrary period of time, often indefinitely.

The most widespread example of an event-driven program is the GUI mouse- and, windows-driven user interface found on most desktop and laptop computers in use today. Event-driven programs also drive web-based applications. For example, an-online student registration system must be prepared to interact with a student no matter what her next action is: adding a course, dropping a course, determining the classroom where a course meets, and so forth. An online airline reservation system, similarly, must be prepared to respond to various sequences of user events, like changing the date of travel, the destination city, or the seating preference.

However, the event-driven programming paradigm has been in use much longer than the Web; it has only recently become prominent in the eyes of programmers because of the Web. Before the Web (if we can imagine such a time!), event-driven programs were found embedded in a variety of vehicles and devices, such as airplanes and ' home security systems. In these environments, the events that trigger programmed responses include a change in direction, wind speed, or temperature; by their nature them events also do not occur in any particular or predictable order.

To provide effective support for event-driven programming, some languages have developed some basic terminology and principles of design. Most recently, these principles have appeared in Java, though other languages like Visual Basic and Tcl/Tk also support event-driven programming.
 

 

---

<< TOP