The primary motivation for a PL is to provide a good notation for problem solving. A good notation serves two purposes. (1) EXPRESIVENESS: The structure of data in a program can be reflected *implicitly* in the way statements are arranged or it can be declared *explicitly*. A language that can declare more kinds of things explicitly is more expressive. Consider the problem of the fourth assignment. If the application uses units, it has to be handled implicitly if any of the standard languages is used. In the new language, information about units is made explicit by declarations. Making information more explicit serves many purposes. It improves program readability. It also makes the following possible. (2) ERROR CHECKING BY COMPILER: If more and more information is made available to the compiler it can check for errors by ensuring *consistency* of information. ------------------------------------------------------------------- What does a program do? A program manipulates data values. +-----------+ input ->| PROGRAM |-> output (value) +-----------+ (value) So a program has following aspects: program = data + operations + control For example, a program can add (OPERATION) the scores (DATA) of the students of a course to find the average. For this some kind of looping (CONTROL) is required. Observation: Not all operations are valid for all values. For example, operation addition is not valid for the name of a person. So values for which a set of operations is valid are grouped together into a TYPE. So VALUE + OPERATION = TYPE Most PLs have several builtin types: integers, reals, etc. The builtin operations are: addition, etc. A given problem may require handling its own set of data values. So most PLs provide a facility to create problem specific data values ("structs") and operations ("functions") on them. VARIABLES AND DECLARATIONS: The fundamental constructs in imperative languages are variables and assignment. Variables have types and values associated with them. A variable can be thought of as a placeholder or a "box" in which values are stored. The type of values stored determines the type of the variable. Variables are introduced to compilers through declarations. Typical declarations are shown below: var value: integer; (* Pascal *) int value; // C, Java A declaration makes the compiler take note of the name (value) and its attribute (integer). The compiler also creates a reference for the variable. The question now is whether storage is allocated for the variable or not. Some languages allocate storage at compile time whereas others allocate storage at runtime. An issue related to declarations is that of initialization. In some languages, declared variables are automatically and appropriately initialized. Some languages (Java, for example) complain if a variable is used before it is initialized. Most of the languages provide some facility for initialization at the time of declaration. int x = 10; // C We need some terminology to discuss some issues. A declaration is called a binding occurrence. All the other occurrences are said to be applied or bound occurrences. For example, in the code below float x, y; // binding occurrence x = 0.7; // bound occurrence of x y = sin(x); // bound occurrences of x and y EXPRESSIONS AND STATEMENTS: Computation proceeds by manipulating values. Expressions specify computation of new values. Expressions are composed of operands (constants and variables), operators, and possibly function calls. Evaluation proceeds by substituting values for operands and by performing the operations. The values associated with the variables in a program is called the environment of the program. Evaluation of an expression should only produce a value and not change the environment. This requirement is called referential transparency. The following C expression is not referentially transparent. a[i++] + c // not referentially transparent Note that expressions are not expected to change the state of computation. Statements change the state of computation. An example of a statement is the assignment statement. a = b + c; // statement in C Many PLs provide a notation to group statements, called compound statements. The following illustrates compound statements in Pascal and C. begin y := x; x := 0 end (* Pascal *) { y = x; x = 0; } // C BLOCK STRUCTURING: Compound statements represent a collection of related computations. These computations might need some temporary variables. So it makes sense to allow declarations inside compound statements. { float temp; temp = x; x = y; y = temp; } The term block refers to a construct that can contain declarations, including procedure declarations. Not all languages allow procedure declarations inside blocks. ------------------------------------------------------------------- CONTROL STRUCTURES In a typical program, values are referenced by variables and are manipulated by operators and functions. Various control structures are possible: if-then-else, while loops, for loops, recursion, and exceptions. Recursion is rarely used in real world programs. But it is a powerful abstraction technique. Exceptions make error checking less cluttered. try { for (int i=0; i < n; i++) a[i] += b[i]; } catch (IndexOutOfBoundsExecption e) { // handle exception throw new IncompatibleArraysException(); // pass the buck } We can think of exceptions as a mechanism that provides a separate channel for error checking. normal code error handling code | | | --- throw ----->| | | | | Both parts are interleaved in the program text, but are distinguished by the keywords "try" and "catch". Logic languages lack explicit control structures. The system uses depth first search to find the solution based on the facts and rules provided by the programmer. (This is only partially true. The ordering of facts and rules influences search. Logic languages also have nonlogical constructs like cut, fail, etc.) ------------------------------------------------------------------- ABSTRACTION As program size increases, the need for abstraction is felt. As program development becomes a group activity, abstraction is indispensable. Different languages support abstraction to different extents. Note that functions and procedures, supported in all languages, are abstractions of expressions. Other abstraction supported in most languages is the notion of a block: a group of statements which are treated as a single unit and in which variables can be defined. Abstract data types (ADTs) are the next step in abstraction. An ADT is a collection of type declarations and associated operations (functions). ADTs can make certain aspects of their definitions "private" - visible only to the implementer and not to the user of the ADT. Typically all data is hidden and access to data is effected through functions. Formally, an ADT consists of a specification, a set of constraints, and one or more implementations. package rectangle is -- specification part type rect is private; -- hidden from the user procedure setRect(w, h: in float; r: in out rect); function rectangleArea(r: in rect) return float; private -- should be hidden from the user, but not because of -- compilation efficiency type rect is record width, height: float; end record; end rectangle; package body rectangle is -- implementation part, hidden from the user procedure setRect(w, h: in float; r: in out rect) is begin ... // check for error conditions end function rectangleArea(r: in rect) return float is begin .... // no need to check for exceptions end rectangleArea; end rectangle; With increasing software development costs, there is a need for software reuse. Object-oriented programming has two key features which aid software reuse: inheritance and polymorphism. Inheritance enables addition of new functionality while reusing of basic functionality. Polymorphism refers to identifying the object type at runtime and using the appropriate method. Polymorphism requires runtime support. Consider the following example. class Shape { // old code void draw() { /* ... */ } } class GraphicsEngine { // old code void render(Shape s) { s.draw(); } } class Circle extends Shape { // new code void draw() { /* ... */ } // new functionality } Circle c; g.render(c); // old code can be reused ------------------------------------------------------------------- CONCURRENCY There is an increasing need for programs to handle many tasks at a time. Threads implement one form of concurrency. When threads cooperate to in problem solving, they should share data. This sharing can be done either through shared variables or through message passing. If threads communicate through shared variable, mutual exclusion of accesses is required to ensure consistency of its value. Monitors are one mechanism ensure mutual exclusion. Associated with each monitor is a queue of tasks waiting for a events associated with the monitor. The task using the monitor can signal events. Improper use of monitors can result in deadlocks. Another form of communication between threads is message passing. Message passing can be used even if the threads are running on different machines. The overhead associated with message passing is the copying of values from the source to the destination. RMI of Java can be thought of as a form of message passing. ------------------------------------------------------------------- NAME SCOPE & BINDING static scope free variable refers to the closest enclosing declaration local variables can be renamed without affecting the result. dynamic scope free variable refers to the most recent binding renaming of local variables might change the result. (* Pascal allows nested procedure definitions *) procedure P; int i=0; procedure R; begin print(i); (* which i? *) end; procedure Q; int i=5; begin R; end; begin Q; R; end; VARIABLE LIFETIMES global persistent local (automatic) dynamic int a; // global void foo() { static int count; // persistent float f, *a; // local a = new float; // dynamic f = a; // free variable } RUNTIME SYSTEM stack allocation static and dynamic links for nested procedure declarations static link is needed implement static scope rule PARAMETER PASSING call by value good for functions call by reference good for procedures, for passing huge objects like arrays call by name (call by macro) delayed evaluation of parameters, useful for "if-then-else" type of functions call by value-result making "in", "out", "in out" parameters explicit and using "copy in/copy out" semantics unification In Prolog, arguments to predicates do not have the input-output distinction. Consider the rule "dessert(X) :- sweet(X)". The predicate "dessert" can be "called" with both a constant like "icecream" or a variable, like "Z". In the first case, the new goal to be proved is "sweet(icecream)". In the second case, the new goal to be proved is "sweet(Z)". When a constant like "icecream" is passed, it is passed by reference. Modification of values is prohibited. ==================================================================== PARADIGMS Using the above ideas, programming can be organized in different ways. Consider the example where on models the number of persons in a room. If a new person enters a room, the systems should update its state to account for this fact. IMPERATIVE: Computation proceeds by manipulating values in fixed locations ("boxes") and storing the new values back in the original locations. In imperative programming, one defines a variable called "numPersons". If a new person enters the room, this variable is incremented, as in "numPersons++". FUNCTIONAL: Computation proceeds by creating new values and locations to store them. So the value held by a location is never changed. Ideally, there are no variables. There is an expression for the number of persons already present in the room. We create a new expression which adds 1 to this and returns the incremented value. A pure functional program might look like fun addPerson(e) = (plus 1 e); where "e" is a recursive data type and "plus" is the tag. A value in this representation looks like (plus 1 (plus 1 (plus 1 (plus 1 0)))) which reflects the fact that initially there was no one and four people entered, one at a time. (This expression can be evaluated to 4 at any time.) Note that old values are not destroyed; only new values are created. Pure functional style is as elegant as it is inefficient. So modern languages retain only the spirit of functional programming. An important feature of functional languages is that functions are also values. So it is possible to return functions as results, etc. So functions are said to be {\em first class}. LOGIC: Logic programming is like functional programming in the sense that values are only created, never destroyed. For example, there is a predicate or relation called "addPerson(X, Y)" where "X" is the number of persons before and "Y" is the number of persons after an entry. The definition of this relation looks like addPerson(X, Y) :- Y = X+1; The fact that this is a relation and not a function can be seen from the following behavior. If we use "addPerson(3, Y)", "Y" gets a value 4. If we use "addPerson(3, 4)", the evaluation is "true". If we use "addPerson(3, 5)", the evaluation is "false". If we use "addPerson(X, 5)", "X" gets the value 4. So the same relation is used by the system differently in different contexts. OBJECT-ORIENTED: In OOP, the values are autonomous. Computation proceeds by sending messages to values asking them to change their state. Here there is an object called "numPersons" and if a new person enters the room, a message is sent to it, like "numPersons.addPerson()". Then the object changes its state in response to the message. Again this is pure OOP: there is no central control. But most of the practical OOPLs have the notion of a central control flow. There is also the notion of inheritance. The following lists some of the key ideas in these paradigms. IMPERATIVE (C) changing the values of variables FUNCTIONAL (ML) expression evaluations producing new values recursion higher order functions lazy evaluation (not supported by ML) OOP (Java) data abstraction autonomous objects, constructors, destructors message passing (not implemented in Java for normal methods) inheritance polymorphism LOGIC (Prolog) declarative program, implicit control (DFS and backtracking) relations: no input-output distinction unification (pattern matching) variable bindings to express constraints/relations between predicates dessert(X) :- sweet(X), calorie(X, Y), Y < 2. /* X is a dessert is X is sweet and if its calorie content is less than 2 */ SCRIPTING (Perl) no type declarations runtime type checking high-level constructs like pattern matching, associative arrays C++ is a complex language supporting many programming styles. The conflicting notions in the design of C++ are compatibility with C efficient compilation & object code support for OOP, exceptions, generic types The consequences are reflected in allocation strategies for objects (stack, heap) object-based and object-oriented styles complex exception handling unreliable generic types Java is a language designed from the scratch to support OOP. The core language is simple. The main disadvantage of Java now is its slow execution speed. New languages evolve in response to new applications. Applications which might inspire development of new paradigms in the near future are: networking, security, and multimedia.