lOMoARcPSD|53449593

PPL Notes unit 1 and 2

Computer Engineering (Savitribai Phule Pune University)

Scan to open on Studocu

Studocu is not sponsored or endorsed by any college or university

Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

PRINCIPLES OF PROGRAMMING LANGUAGE

UNIT-I
1. Reasons for studying
2. Concepts of programming languages
3. Programming domains
4. Language Evaluation Criteria
5. Influences on Language design
6. Language categories
7. Programming Paradigms – Imperative, Object Oriented, functional Programming, and Logic
Programming.
8. Programming Language Implementation – Compilation and Virtual Machines
9. Programming environments.

UNIT-II
1. Elementary Data Types: Primitive data Types, Character String types, User Defined Ordinal Types, Array
types, Associative Arrays, Record Types, Union Types, Pointer and reference Type.
2. Expression and Assignment Statements: Arithmetic expression, Overloaded Operators, Type conversions,
Relational and Boolean Expressions, Short Circuit Evaluation, Assignment Statements, Mixed mode
Assignment.
3. Statement level Control Statements: Selection Statements, Iterative Statements, Unconditional Branching.
4. Subprograms: Fundamentals of Sub Programs, Design Issues for Subprograms, Local referencing
Environments, Parameter passing methods.
5. Abstract Data Types and Encapsulation Construct: Design issues for Abstraction, Parameterized Abstract
Data types, Encapsulation Constructs, Naming Encapsulations

1 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

UNIT – I
PRELIMINARY CONCEPTS

Reasons for Studying Concepts of Programming Languages

• Increased ability to express ideas.

• It is believed that the depth at which we think is influenced by the expressive
power of the language in which we communicate our thoughts. It is difficult for
people to conceptualize structures they can’t describe, verbally or in writing.
• Language in which they develop S/W places limits on the kinds of control
structures, data structures, and abstractions they can use.
• Awareness of a wider variety of P/L features can reduce such limitations in S/W
development.

• Can language constructs be simulated in other languages that do not

support those constructs directly?
• Improved background for choosing appropriate languages
• Many programmers, when given a choice of languages for a new project, continue
to use the language with which they are most familiar, even if it is poorly suited to
new projects.
• If these programmers were familiar with other languages available, they would
be in a better position to make informed language choices.
• Greater ability to learn new languages
• Programming languages are still in a state of continuous evolution, which
means continuous learning is essential.
• Programmers who understand the concept of OO programming will have
easier time learning Java.

• Once a thorough understanding of the fundamental concepts of languages is

acquired, it becomes easier to see how concepts are incorporated into the design
of the language being learned.
• Understand significance of implementation
• Understanding of implementation issues leads to an understanding of why
languages are designed the way they are.
• This in turn leads to the ability to use a language more intelligently, as it was
designed to be used.

2 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

• Ability to design new languages

• The more languages you gain knowledge of, the better understanding of
programming languages concepts you understand.
• Overall advancement of computing
• In some cases, a language became widely used, at least in part, b/c those in
positions to choose languages were not sufficiently familiar with P/L concepts.
• Many believe that ALGOL 60 was a better language than Fortran; however,
Fortran was most widely used. It is attributed to the fact that the programmers
and managers didn’t understand the conceptual design of ALGOL 60.
• Do you think IBM has something to do with it?

Programming Domains
• Scientific applications
– In the early 40s computers were invented for scientific applications.
– The applications require large number of floating-point computations.
– Fortran was the first language developed scientific applications.
– ALGOL 60 was intended for the same use.
• Business applications
– The first successful language for business was COBOL.
– Produce reports, use decimal arithmetic numbers and characters.
– The arrival of PCs started new ways for businesses to use computers.
– Spreadsheets and database systems were developed for business.

• Artificial intelligence
– Symbolic rather than numeric computations are manipulated.
– Symbolic computation is more suitably done with linked lists than arrays.
– LISP was the first widely used AI programming language.
• Systems programming
– The O/S and all of the programming supports tools are collectively known as its
system software.
– Need efficiency because of continuous use.
• Scripting languages
– Put a list of commands, called a script, in a file to be executed.
– PHP is a scripting language used on Web server systems. Its code is embedded in
HTML documents. The code is interpreted on the server before the document is

3 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

sent to a requesting browser.

– Special-purpose languages

Language Evaluation Criteria

Readability
• Software development was largely thought of in term of writing code “LOC”.
• Language constructs were designed more from the point of view of the computer than the users.
• Because ease of maintenance is determined in large part by the readability of programs,
readability became an important measure of the quality of programs and programming
languages. The result is a crossover from focus on machine orientation to focus on human
orientation.
• The most important criterion “ease of use”
• Overall simplicity “Strongly affects readability”
– Too many features make the language difficult to learn. Programmers tend to
learn a subset of the language and ignore its other features. “ALGOL 60”
– Multiplicity of features is also a complicating characteristic “having more than
one way to accomplish a particular operation.”
– Ex “Java”:
count = count + 1
count

+= 1

count

++

++count

– Although the last two statements have slightly different meaning from each
other and from the others, all four have the same meaning when used as stand-
alone expressions.
– Operator overloading where a single operator symbol has more than one meaning.
– Although this is a useful feature, it can lead to reduced readability if users are
allowed to create their own overloading and do not do it sensibly.

• Orthogonality

4 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

– Makes the language easy to learn and read.

– Meaning is context independent. Pointers should be able to point to any type of
variable or data structure. The lack of orthogonality leads to exceptions to the
rules of the language.
– A relatively small set of primitive constructs can be combined in a
relatively small number of ways to build the control and data structures of
the language.
– Every possible combination is legal and meaningful.
– Ex: page 11 in book.
– The more orthogonal the design of a language, the fewer exceptions the
language rules require.
– The most orthogonal programming language is ALGOL 68. Every language
construct has a type, and there are no restrictions on those types.
– This form of orthogonality leads to unnecessary complexity.

• Control Statements
– It became widely recognized that indiscriminate use of goto statements severely
reduced program readability.
– Ex: Consider the following nested loops
written in C while (incr < 20)
{
while (sum <= 100
{
sum += incr;
}
incr++;

}if C didn’t have a loop construct, this would be written as follows:

loop1:

if (incr >= 20) go to

out; loop2:

if (sum > 100) go to

next; sum += incr;

go to

5 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

loop2; next:

incr++;

go to loop1:

out:

– Basic and Fortran in the early 70s lacked the control statements that allow
strong restrictions on the use of gotos, so writing highly readable programs in
those languages was difficult.
– Since then, languages have included sufficient control structures.
– The control statement design of a language is now a less important factor in
readability than it was in the past.

• Data Types and Structures

– The presence of adequate facilities for defining data types and data
structures in a language is another significant aid to reliability.
– Ex: Boolean type.
timeout = 1 or timeout = true

 Syntax Considerations
– The syntax of the elements of a language has a significant effect on readability.
– The following are examples of syntactic design choices that affect readability:
• Identifier forms: Restricting identifiers to very short lengths detracts from
readability. ANSI BASIC (1978) an identifier could consist only of a
single letter of a single letter followed by a single digit.
• Special Words: Program appearance and thus program readability are
strongly influenced by the forms of a language’s special words. Ex: while,
class, for. C uses braces for pairing control structures. It is difficult to
determine which group is being ended. Fortran 95 allows programmers to
use special names as legal variable names.
• Form and Meaning: Designing statements so that their appearance
at least partially indicates their purpose is an obvious aid to
readability.
• Semantic should follow directly from syntax, or form.
• Ex: In C the use of static depends on the context of its appearance.

6 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

If used as a variable inside a function, it means the variable is created at

compile time.

If used on the definition of a variable that is outside all functions, it means

the variable is visible only in the file in which its definition appears.

Writability
 It is a measure of how easily a language can be used to create programs for a chosen
problem domain.
 Most of the language characteristics that affect readability also affect writability.
• Simplicity and orthogonality
– A smaller number of primitive constructs and a consistent set of rules for
combining them is much better than simply having a large number of primitives.
• Support for abstraction
– Abstraction means the ability to define and then use complicated structures or
operations in ways that allow many of the details to be ignored.
– A process abstraction is the use of a subprogram to implement a sort algorithm
that is required several times in a program instead of replicating it in all places
where it is needed.
• Expressivity
– It means that a language has relatively convenient, rather than cumbersome,
ways of specifying computations.

– Ex: ++count ⇔ count = count + 1 // more convenient and shorter

Reliability
 A program is said to be reliable if it performs to its specifications under all conditions.
• Type checking: is simply testing for type errors in a given program, either by the
compiler or during program execution.
– The earlier errors are detected, the less expensive it is to make the required
repairs. Java requires type checking of nearly all variables and expressions at
compile time.
• Exception handling: the ability to intercept run-time errors, take corrective measures,
and then continue is a great aid to reliability.
• Aliasing: it is having two or more distinct referencing methods, or names, for the same
memory cell.
– It is now widely accepted that aliasing is a dangerous feature in a language.

7 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

• Readability and writability: Both readability and writability influence reliability.

•
Cost
– Categories
– Training programmers to use language
– Writing programs “Writability”
– Compiling programs
– Executing programs
– Language implementation system “Free compilers is the key, success of Java”
– Reliability, does the software fail?
– Maintaining programs: Maintenance costs can be as high as two to four times
as much as development costs.
– Portability “standardization of the language” ,Generality (the applicability to
a wide range of applications)

Influences on Language Design

Computer architecture: Von Neumann
• We use imperative languages, at least in part, because we use von Neumann machines
– Data and programs stored in same memory
– Memory is separate from CPU
– Instructions and data are piped from memory to CPU
– Results of operations in the CPU must be moved back to memory
– Basis for imperative languages
• Variables model memory cells
• Assignment statements model piping
• Iteration is efficient

8 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

Programming methodologies
• 1950s and early 1960s: Simple applications; worry about machine efficiency
• Late 1960s: People efficiency became important; readability, better control structures
– Structured programming
– Top-down design and step-wise refinement
• Late 1970s: Process-oriented to data-oriented
– data abstraction
• Middle 1980s: Object-oriented programming

Language Categories
• Imperative
– Central features are variables, assignment statements, and iteration
– C, Pascal
• Functional
– Main means of making computations is by applying functions to given parameters
– LISP, Scheme
• Logic
– Rule-based
– Rules are specified in no special order
– Prolog
• Object-oriented
– Encapsulate data objects with processing

9 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

– Inheritance and dynamic type binding

– Grew out of imperative languages
– C++, Java

Programming Environments
• The collection of tools used in software development
• UNIX
– An older operating system and tool collection
• Borland JBuilder
– An integrated development environment for Java
• Microsoft Visual Studio.NET
– A large, complex visual environment
– Used to program in C#, Visual BASIC.NET, Jscript, J#, or C++
 Genealogy of common high-level programming languages

Syntax and Semantics

Syntax - the form or structure of the expressions, statements, and program units

Semantics - the meaning of the expressions, statements, and program units

Who must use language definitions?
1. Other language designers

2. Implementors

3. Programmers (the users of the language)

A sentence is a string of characters over some

alphabet A language is a set of sentences
A lexeme is the lowest level syntactic unit of a language (e.g., *, sum,
begin) A token is a category of lexemes (e.g., identifier)
Formal approaches to describing syntax:
1. Recognizers - used in compilers
2. Generators - what we'll study

Functional Programming

Q Describe Functional Programming. Enlist its features. Also list the commonly used functional

10 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

programming languages. (April 22) [6]

Q. Comparisons between functional programming and logic programming. (oct 22) [5]

 Try to bind everything in pure mathematical functions style.

 Declarative type of programming style.
 main focus is on “what to solve” in contrast to an imperative style where the main focus is
“how to solve”.
 It uses expressions instead of statements.
 An expression is evaluated to produce a value whereas a statement is executed to assign
variables.
Functional Programming – Characteristics
The most prominent characteristics of functional programming are as follows −
 Functional programming languages are designed on the concept of mathematical functions that
use conditional expressions and recursion to perform computation.
 Functional programming supports higher-order functions and lazy evaluation features.
 Functional programming languages don’t support flow Controls like loop statements and
conditional statements like If-Else and Switch Statements. They directly use the functions and
functional calls.
 Like OOP, functional programming languages support popular concepts such as Abstraction,
Encapsulation, Inheritance, and Polymorphism.
Some of the popular functional programming languages include: Lisp, Python, Erlang, Haskell,
Clojure, etc.

Logical Programming

Q. Describe Logical Programming. Enlist its features. Also list the commonly used Logical
programming languages. (April 23) (April 22) [6]
Q. Comparisons between functional programming and logic programming. (oct 22) [5]
Answer: Logic programming is a computer programming paradigm where program statements
express facts and rules about problems within a system of formal logic.

Features of Logical Programming

 Logical programming can be used to express knowledge in a way that does not depend on the.
 It enables knowledge to be separated from use, i.e. the machine architecture can be changed.
 It can be altered and extended in natural ways to support special forms of knowledge, such.

List of Logic Programming

 Absys
 ALF (algebraic logic functional programming language).
 Prolog
 Prolog++

11 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

UNIT-II

DATA TYPES
Data type Definition:

– collection of data objects

– a set of predefined operations

• descriptor : collection of attributes for a variable

• object : instance of a user-defined (abstract data) type

Data Types:

• Primitive

– not defined in terms of other data types

– defined in the language

– often reflect the hardware

• Structured

– built out of other types

Integer Types:

- Usually based on hardware

- May have several ranges

– Java’s signed integer sizes: byte, short, int, long

– C/C++ have unsigned versions of the same types

– Scripting languages often just have one integer type

– Python has an integer type and a long integer which can get as big as it needs to.

1. Representing Integers:

– Can convert positive integers to base

– How do you handle negative numbers with only 0s and 1s?
– Sign bit

– Ones complement

12 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

– Twos complement - this is the one that is used

– Representing negative integers.

Representing negative integers:

• Sign bit

• Ones complement

Twos Complement:

• To get the binary representation, take the complement and add 1

Floating Point Types:

• Model real numbers

only an approximation due to round-off error

• For scientific use support at least two floating-point types (e.g., float and double;
sometimes more)
• The float type is the standard size, usually being stored in four bytes of memory.
• The double type is provided for situations where larger fractional parts and/or a larger range
of exponents is needed
• Floating-point values are represented as fractions and exponents, a form that is borrowed from
scientific notation
• The collection of values that can be represented by a floating-point type is defined in terms of
precision and range

• Precision is the accuracy of the fractional part of a value, measured as the number of bits

• Range is a combination of the range of fractions and, more important, the range of exponents.

• Usually based on hardware

• IEEE Floating-Point Standard 754

13 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

– 32 and 64 bit standards

Representing Real Numbers:

• We can convert the decimal number to base 2 just as we did for integers

• How do we represent the decimal point?

– fixed number of bits for the whole and fractional parts severely limits the range of
values we can represent

• Use a representation similar to scientific notation

IEEE Floating Point Representation:

• Normalize the number

– one bit before decimal point

• Use one bit to represent the sign (1 for negative)

• Use a fixed number of bits for the exponent which is offset to allow for negative exponents

– Exponent = exponent + offset

• (-1)sign 1.Fraction x 2Exponent

Floating Point Types:

• C, C++ and Java have two floating point types

– float

– double

• Most scripting languages have one floating point type

– Python's floating point type is equivalent to a C double

• Some scripting languages only have one kind of number which is a floating point type

14 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

Fixed Point Types (Decimal) :

• For business applications (money) round-off errors are not acceptable

– Essential to COBOL

– .NET languages have a decimal data type

• Store a fixed number of decimal digits

• Operations generally have to be defined in software

• Advantage: accuracy

• Disadvantages: limited range, wastes memory

C# decimal Type:

• 128-bit representation

• Range: 1.0x10-28 to 7.9x1028

• Precision: representation is exact to 28 or 29 decimal places (depending on size of number)

– no roundoff error

Other Primitive Data Types:

• Boolean

– Range of values: two elements, one for “true” and one for “false”

– Could be implemented as bits, but often as bytes

– Boolean types are often used to represent switches or flags in programs.

– A Boolean value could be represented by a single bit, but because a single bit of
memory cannot be accessed efficiently on many machines, they are often stored in the
smallest efficiently addressable cell of memory, typically a byte.

• Character

– Stored as numeric codings

– Most commonly used coding: ASCII

– An alternative, 16-bit coding: Unicode

• Complex (Fortran, Scheme, Python)

• Rational (Scheme)

15 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

Character Strings :

• Values are sequences of characters

• Character string constants are used to label output, and the input and output of all kinds of data
are often done in terms of strings.

• Operations:
– Assignment and copying
– Comparison (=, >, etc.)
– Concatenation
– Substring reference
– Pattern matching
- A substring reference is a reference to a substring of a given string. Substring references are discussed
in the more general context of arrays, where the substring references are called slices.

- In general, both assignment and comparison operations on character strings are

complicated by the possibility of string operands of different lengths.

• Design issues:

– Is it a primitive type or just a special kind of array?

– Should the length of strings be static or dynamic?

Character String Implementations:

• C and C++

– Not primitive

– Use char arrays to store character

– Use char arrays and a library of functions that provide operations

– Eg.: char Mystring[]=”Exam”; OR

Char Mystring[4]={‘E’,’x’,’a’,’m’};

• SNOBOL4 (a string manipulation language)

– Primitive

– Many operations, including elaborate pattern matching

• Java

– Supported by String class

– Eg- String s=”Exam”; //constant

16 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

String s1= new String(“Exam”);

StringBuffer s2= new StringBuffer(“Exam”);

String Length Options

• Static: COBOL, Java’s String class

– The length is constant.

• Limited Dynamic Length: C and C++

– It has fixed maximum length

– a special character is used to indicate

the end of a string’s characters

• Dynamic (no maximum): SNOBOL4, Perl,

JavaScript

– It has varying length with no

maximum.

• Ada supports all three string length options

String Implementation

• Static length: compile-time descriptor

• Limited dynamic length: may need run-time descriptor

– not in C and C++

• Dynamic length: needs run-time descriptor;

– Require more complex storage management.

– allocation/deallocation is main implementation issue

– the string length is not fixed hence storage may grow or shrink dynamically.

User-Defined Ordinal Types:

• Ordinal type : range of possible values corresponds to set of positive integers

• These data types are defined by the programmer with the help if primitive data type.

• Primitive ordinal types

17 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

– integer
– char
– boolean

• User-defined ordinal types

– enumeration types
– subrange types

Enumeration Types:

• All possible values, which are named constants, are provided in the definition

• A way of defining and grouping collections of named constants, which are called enumeration constants.

C example:

Enum days {Mon, Tue, wed, Thu, Fri, sat, sun};

• Design issues

– duplication of names

– coercion rules

Enums in C (and C++):

• To define an enumerated type in C

Ex:

- Enum weekday {Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday};

Enum weekday today = Tuesday;

• Use typedef to give the type a name

typedef enum weekday {Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday}
weekday;

Weekday today = Tuesday;

• By default, values are consecutive starting from 0.

– You can explicitly assign values

Enum months {January=1, February,};

Enumerations in Java 1.5:

• An enum is a new class which extends java.lang.Enum and implements Comparable

– Get type safety and compile-time checking

18 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

– Implicitly public, static and final

– Can use either == or equals to compare

– toString and valueOf are overridden to make input and output easier

Java enum Example:

• Defining an enum type

Enum Season {WINTER, SPRING, SUMMER, FALL};

• Declaring an enum variable

Season season = Season. WINTER;

• to String gives you the string representation of the name

System.out.println (season);

// prints WINTER

• valueOf lets you convert a String to an enum

Season = valueOf (“SPRING”);

Sub range Types:

• A contiguous subsequence of an ordinal type

Example:

• Ada’s design:

Type Days is (Mon, Tue, wed, Thu, Fri, sat, sun);

Subtype Weekdays is Days range Mon..Fri;

Subtype Index is Integer range 1..100;

Day1: Days;

Day2: Weekday;

Day2:= Day1;

Evaluation

Subrange types enhance readability by making it clear to readers that variables of subtypes can store only
certain ranges of values. Reliability is increased with subrange types, because assigning a value to a
subrange variable that is outside the specified range is detected as an error, either by the compiler (in the

19 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

case of the assigned value being a literal value) or by the run-time system (in the case of a variable or
expression). It is odd that no contemporary language except Ada has subrange types.

Implementation of User-Defined Ordinal Types

• Enumeration types are implemented as integers

• Subrange types are implemented like the parent types

– code inserted (by the compiler) to restrict assignments to subrange variables

Arrays and Indices

• Specific elements of an array are referenced by means of a two-level syntactic mechanism, where
the first part is the aggregate name, and the second part is a possibly dynamic selector consisting
of one or more items known as subscripts or indices.
• If all of the subscripts in a reference are constants, the selector is static; otherwise, it is
dynamic. The selection operation can be thought of as a mapping from the array name and the
set of

subscript values to an element in the aggregate. Indeed, arrays are sometimes called finite
mappings. Symbolically, this mapping can be shown as
 array_name(subscript_value_list) → element
Subscript Bindings and Array Categories
• The binding of the subscript type to an array variable is usually static, but the subscript value
ranges are sometimes dynamically bound.
• There are five categories of arrays, based on the binding to subscript ranges, the binding to
storage, and from where the storage is allocated.
• A static array is one in which the subscript ranges are statically bound and storage allocation
is static (done before run time).
 The advantage of static arrays is efficiency: No dynamic allocation or deallocation
is required.
 The disadvantage is that the storage for the array is fixed for the entire execution time
of the program.
• A fixed stack-dynamic array is one in which the subscript ranges are statically bound, but
the allocation is done at declaration elaboration time during execution.
 The advantage of fixed stack-dynamic arrays over static arrays is space efficiency
 The disadvantage is the required allocation and deallocation time
• A stack-dynamic array is one in which both the subscript ranges and the storage allocation

20 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

are dynamically bound at elaboration time. Once the subscript ranges are bound and the storage
is allocated, however, they remain fixed during the lifetime of the variable.
 The advantage of stack-dynamic arrays over static and fixed stack-dynamic arrays is
flexibility
• A fixed heap-dynamic array is similar to a fixed stack-dynamic array, in that the subscript ranges
and the storage binding are both fixed after storage is allocated
 The advantage of fixed heap-dynamic arrays is flexibility—the array’s size always fits
the problem.
 The disadvantage is allocation time from the heap, which is longer than allocation
time from the stack.
• A heap-dynamic array is one in which the binding of subscript ranges and storage allocation
is dynamic and can change any number of times during the array’s lifetime.
 The advantage of heap-dynamic arrays over the others is flexibility:
 The disadvantage is that allocation and deallocation take longer and may happen many
times during execution of the program.

Array Initialization
Some languages provide the means to initialize arrays at the time their storage is allocated.
An array aggregate for a single-dimensioned array is a list of literals delimited by parentheses and slashes.
For example, we could have
Integer, Dimension (3) :: List = (/0, 5, 5/)
In the C declaration
int list [] = {4, 5, 7, 83};
These arrays can be initialized to string constants, as in
char name [] = "freddie";
Arrays of strings in C and C++ can also be initialized with string literals. In this case, the array is one of
pointers to characters.
For example,
char *names [] = {"Bob", "Jake" ,"Darcie"};
In Java, similar syntax is used to define and initialize an array of references to String
objects. For example,
String[] names = ["Bob", "Jake", "Darcie"];
Ada provides two mechanisms for initializing arrays in the declaration statement: by listing them in the
order in which they are to be stored, or by directly assigning them to an index position using the =>
operator, which in Ada is called an arrow.
For example, consider the following:

21 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

List : array (1.5) of Integer := (1, 3, 5, 7, 9);

Bunch : array (1.5) of Integer := (1 => 17, 3 => 34,
others => 0);

Rectangular and Jagged Arrays

A rectangular array is a multi dimensioned array in which all of the rows have the same number of
elements and all of the columns have the same number of elements. Rectangular arrays model rectangular
tables exactly.
A jagged array is one in which the lengths of the rows need not be the same.
For example, a jagged matrix may consist of three rows, one with 5 elements, one with 7 elements, and
one with 12 elements. This also applies to the columns and higher dimensions. So, if there is a third
dimension (layers), each layer can have a different number of elements. Jagged arrays are made possible

when multi dimensioned arrays are actually arrays of arrays. For example, a matrix would appear as an
array of single-dimensioned arrays.
For example,
myArray[3][7]
Slices
A slice of an array is some substructure of that array.
For example, if A is a matrix, then the first row of A is one possible slice, as are the last row and the first
column. It is important to realize that a slice is not a new data type. Rather ,it is a mechanism for
referencing part of an array as a unit.
Evaluation
Arrays have been included in virtually all programming languages
Implementation of Array Types

Implementing arrays requires considerably more compile-time effort than does implementing primitive
types. The code to allow accessing of array elements must be generated at compile time. At run time, this
code must be executed to produce element addresses. There is no way to pre compute the address to be
accessed by a reference such as
list [k]
A single-dimensioned array is implemented as a list of adjacent memory cells. Suppose the array list is
defined to have a subscript range lower bound of 0. The access function for list is often of the form
address
( list [k] ) = address (list [0] ) + k * element_size where the first operand of the addition is the
constant part of the access function, and the second is the variable part .

22 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

If the element type is statically bound and the array is statically bound to storage, then the value of the
constant part can be computed before run time. However, the addition and multiplication operations must
be done at run time.
The generalization of this access function for an arbitrary lower bound is address (list[k]) = address
( list [lower_bound]) + ( (k - lower_bound) * element_size)
Associative Arrays

An associative array is an unordered collection of data elements that are indexed by an equal number of
values called keys. In the case of non-associative arrays, the indices never need to be stored (because of
their regularity). In an associative array, however, the user-defined keys must be stored in the structure.
So each element of an associative array is in fact a pair of entities, a key and a value. We use Perl’s
design of associative arrays to illustrate this data structure. Associative arrays are also supported directly
by

23 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

Python, Ruby, and Lua and by the standard class libraries of Java, C++, C#, and F#. The only design issue
that is specific for associative arrays is the form of references to their elements.
Structure and Operations

In Perl, associative arrays are called hashes, because in the implementation their elements are stored and
retrieved with hash functions. The namespace for Perl hashes is distinct: Every hash variable name must
begin with a percent sign (%). Each hash element consists of two parts: a key, which is a string, and a
value, which is a scalar (number, string, or reference). Hashes can be set to literal values with the
assignment statement, as in
%salaries = ("Gary" => 75000, "Perry" => 57000,
"Mary" => 55750, "Cedric" => 47850);
Recall that scalar variable names begin with dollar signs
($). For example,
$salaries {"Perry"} = 58850;
A new element is added using the same assignment statement form. An element can be removed from the
hash with the delete operator, as in
Delete $salaries{"Gary"};

Record Types
A record is an aggregate of data elements in which the individual elements are identified by names and
accessed through offsets from the beginning of the structure. There is frequently a need in programs to
model a collection of data in which the individual elements are not of the same type or size. For example,
information about a college student might include name, student number, grade point average, and so
forth. A data type for such a collection might use a character string for the name, an integer for the student
number, a floating point for the grade point average, and so forth. Records are designed for this kind of
need.
The following design issues are specific to records:
• What is the syntactic form of references to fields?
• Are elliptical references allowed?
Definitions of Records
The fundamental difference between a record and an array is that record elements, or fields, are not
referenced by indices. Instead, the fields are named with identifiers, and references to the fields are made
using these identifiers The COBOL form of a record declaration, which is part of the data division of a
COBOL program, is illustrated in the following example:
01 EMPLOYEE-RECORD.
02 EMPLOYEE-NAME.

24 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

05 FIRST PICTURE IS X(20).

05 MIDDLE PICTURE IS X(10).
05 LAST PICTURE IS X(20).
02 HOURLY-RATE PICTURE IS 99V99.
The EMPLOYEE-RECORD record consists of the EMPLOYEE-NAME record and the HOURLY-RATE
field. The numerals 01, 02, and 05 that begin the lines of the record declaration are level numbers, which
indicate by their relative values the hierarchical structure of the record

Implementation of Record Types

The fields of records are stored in adjacent memory locations. But because the sizes of the fields are not
necessarily the same, the access method used for arrays is not used for records. Instead, the offset
address, relative to the beginning of the record, is associated with each field. Field accesses are all
handled using these offsets. The compile-time descriptor for a record has the general form shown in
Figure 6.7. Run-time descriptors for records are unnecessary

25 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

Union Types
A union is a type whose variables may store different type values at different times during program
execution. As an example of the need for a union type, consider a table of constants for a compiler, which
is used to store the constants found in a program being compiled. One field of each table entry is for the
value of the constant. Suppose that for a particular language being compiled, the types of constants were
integer, floating point, and Boolean. In terms of table management, it would be convenient if the same
location, a table field, could store a value of any of these three types. Then all constant values could be
addressed in the same way. The type of such a location is, in a sense, the union of the three value types it
can store.
Design Issues
The problem of type checking union types, leads to one major design issue. The other fundamental
question is how to syntactically represent a union. In some designs, unions are confined to be parts
of record structures, but in others they are not. So, the primary design issues that are particular to union
types are the following:
• Should type checking be required? Note that any such type checking must be dynamic.
• Should unions be embedded in records?

Ada Union Types

The Ada design for discriminated unions, which is based on that of its predecessor language, Pascal,
allows the user to specify variables of a variant record type that will store only one of the possible type
values in the variant. In this way, the user can tell the system when the type checking can be static. Such
a restricted variable is called a constrained variant variable.
Implementation of Union Types

Unions are implemented by simply using the same address for every possible variant. Sufficient storage
for the largest variant is allocated. The tag of a discriminated union is stored with the variant in a record
like structure. At compile time, the complete description of each variant must be stored. This can be done
by associating a case table with the tag entry in the descriptor. The case table has an entry for each
variant, which points to a descriptor for that particular variant. To illustrate this arrangement, consider
the following Ada example:
type Node (Tag : Boolean) is
record

case Tag is
when True => Count : Integer;
when False => Sum : Float;

26 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

end case;
end record;
The descriptor for this type could have the form shown in Figure

Pointer and Reference Types

• A pointer is a variable whose value is an address

– range of values that consists of memory addresses plus a special value, nil

• Provide the power of indirect addressing

• Provide a way to manage dynamic memory

• A pointer can be used to access a location in the area where storage is

dynamically created (usually called a heap)

• Generally represented as a single number

Pointer Operations:

• Two fundamental operations: assignment and dereferencing

• Assignment is used to set a pointer variable’s value to some useful address

• Dereferencing yields the value stored at the location represented by the pointer’s value

– Dereferencing can be explicit or implicit

– C++ uses an explicit operation via *

j = *ptr

Pointer Operations Illustrated:

27 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

Dereferencing a pointer assignment

Pointer Problems:

Pointers in C and C++:

• Extremely flexible but must be used with care

28 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

• Pointers can point at any variable regardless of when it was allocated

• Used for dynamic storage management and addressing

• Pointer arithmetic is possible

• Explicit dereferencing and address-of operators

• Domain type need not be fixed (void *)

• void * can point to any type and can be type checked (cannot be de-referenced)

Pointer Arithmetic in C and C++:

Float stuff[100];

Float *p;

p = stuff;

*(p+5) is equivalent to stuff [5] and p[5]

*(p+i) is equivalent to stuff[i] and p[i]

Reference Types:

• C++ includes a special kind of pointer type called a reference type that is used primarily for
formal parameters

– Advantages of both pass-by-reference and pass-by-value

• Java extends C++’s reference variables and allows them to replace pointers entirely

– References refer to call instances

• C# includes both the references of Java and the pointers of C++

Evaluation of Pointers:

• Dangling pointers and dangling objects are problems as is heap management

• Pointers are like goto's--they widen the range of cells that can be accessed by a variable

• Pointers or references are necessary for dynamic data structures--so we can't design a language
without them

Introduction to Names and variables:

• Imperative languages are abstractions of von Neumann architecture

• A machine consists of

– Memory - stores both data and instructions

29 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

– Processor - can modify the contents of memory

• Variables are used as an abstraction for memory cells

– For primitive types correspondence is direct

– For structured types (objects, arrays) things are more

complicated

Names:

• Why do we need names?

– need a way to refer to variables, functions, user-defined types, labeled statements, …

• Design issues for names:

– Maximum length?

– What characters are allowed?

– Are names case sensitive?

• C, C++, and Java names are case sensitive

• this is not true of other languages

– Are special words reserved words or keywords?

Length of Names:

• If too short, they cannot be connotative

• Language examples:

– FORTRAN I: maximum 6

– COBOL: maximum 30

– FORTRAN 90 and ANSI C: maximum 31

– Ada and Java: no limit, and all are significant

– C++: no limit, but implementers often impose one

Keywords Vs Reserved Words:

• Words that have a special meaning in the language

• A keyword is a word that is special only in certain contexts, e.g., in Fortran

• Real VarName (Real is a data type followed with a name, therefore Real is

30 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

a keyword)

• Real = 3.4 (Real is a variable)

• A reserved word is a special word that cannot be used as a user-defined name

– most reserved words are also keywords

31 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

Variables:

• A variable is an abstraction of a memory cell

• Variables can be characterized as a sextuple of attributes:

– Name

– Address

– Value

– Type

– Lifetime

– Scope

Variable Attributes:

• Name - not all variables have them

• Address - the memory address with which it is associated (l-value)

• Type - allowed range of values of variables and the set of defined operations

Value - the contents of the location with which the variable is associated (r-value

The Concept of Binding:

• A binding is an association, such as between an attribute and an entity, or between an operation

and a symbol

– entity could be a variable or a function or even a class

• Binding time is the time at which a binding takes place.

Possible Binding Times:

• Language design time -- bind operator symbols to operations

• Language implementation time-- bind floating point type to a representation

• Compile time -- bind a variable to a type in C or Java

• Load time -- bind a FORTRAN 77 variable to a memory cell (or a C static variable)
• Runtime -- bind a nonstatic local variable to a memory cell

Static and Dynamic Binding:

32 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

• A binding is static if it first occurs before run time and remains unchanged throughout
program execution.

• A binding is dynamic if it first occurs during execution or can change during execution of the
program

Type Binding:

• How is a type specified?

– An explicit declaration is a program statement used for declaring the types of variables

– An implicit declaration is a default mechanism for specifying types of variables (the first
appearance of the variable in the program )

• When does the binding take place?

• If static, the type may be specified by either an explicit or an implicit declaration

Type Checking

• Generalize the concept of operands and operators to include subprograms and assignments

• Type checking is the activity of ensuring that the operands of an operator are of compatible types

Compatible type :

It is one that is either legal for the operator, or is allowed under language rules to be
implicitly converted, by compiler- generated code, to a legal type

• A type error is the application of an operator to an operand of an inappropriate type

When is type checking done?

• If all type bindings are static, nearly all type checking can be static (done at compile time)

• If type bindings are dynamic, type checking must be dynamic (done at run time)

• A programming language is strongly typed if type errors are always detected

– Advantage: allows the detection of misuse of variables that result in type errors

How strongly typed?

– FORTRAN 77 is not: parameters, EQUIVALENCE

– Pascal has variant records

33 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

– C and C++

• parameter type checking can be avoided

• unions are not type checked

– Ada is almost

• UNCHECKED CONVERSION is loophole

– Java is similar

Strong Typing:
 Advantage of strong typing: allows the detection of the misuses of variables that result in type
errors
 Language examples:
 FORTRAN 77 is not: parameters, EQUIVALENCE
 Pascal is not: variant records
 C and C++ are not: parameter type checking can be avoided; unions are not
type checked
 Ada is, almost (UNCHECKED CONVERSION is loophole)
(Java is similar)
 Coercion rules strongly affect strong typing--they can weaken it considerably (C+ versus Ada)
 Although Java has just half the assignment coercions of C++, its strong typing is
still far less effective than that of Ada

Type Compatibility
 Our concern is primarily for structured types
 Def: Name type compatibility means the two variables have compatible types if
they are in either the same declaration or in declarations that use the same type
name

 Easy to implement but highly restrictive:

 Subranges of integer types are not compatible with integer types
 Formal parameters must be the same type as their corresponding actual
parameters (Pascal)
 Structure type compatibility means that two variables have compatible types if
their types have identical structures
 More flexible, but harder to implement
 Consider the problem of two structured types:

34 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

Are two record types compatible if they are structurally the same but use
different field names?
 Are two array types compatible if they are the same except that the
subscripts are different?
(e.g. [1..10] and [0..9])
 Are two enumeration types compatible if their components are
spelled differently?
 With structural type compatibility, you cannot differentiate between types
of the same structure (e.g. different units of speed, both float)

Named Constants
⚫ Def: A named constant is a variable that is bound to a value only when it is
bound to storage
⚫ Advantages: readability and modifiability
⚫ Used to parameterize programs
 The binding of values to named constants can be either static (called
manifest constants) or dynamic
 Languages:
 Pascal: literals only
 FORTRAN 90: constant-valued expressions
 Ada, C++, and Java: expressions of any kind
Variable Initialization
 Def: The binding of a variable to a value at the time it is bound to storage is
called initialization
 Initialization is often done on the declaration statement
e.g., Java
int sum = 0;

Coercion:

• The automatic conversion between types is called coercion.

• Coercion rules they can weaken typing considerably

– C and C++ allow both widening and narrowing coercions

– Java allows only widening coercions

• Java's strong typing is still far less effective than that of Ada

35 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

Dynamic Type Binding:

• Dynamic Type Binding (Perl, JavaScript and PHP, Scheme)

• Specified through an assignment statement e.g., JavaScript

List = [2, 4.33, 6, 8];

List = 17.3;

• This provides a lot of flexibility

• But …

– How do you do any type checking?

Storage Bindings & Lifetime:

• The lifetime of a variable is the time during which it is bound to a particular memory cell

– Allocation - getting a cell from some pool of available cells

– Deallocation - putting a cell back into the pool

• Depending on the language, allocation can be either controlled by the programmer or done
automatically

Categories of Variables by Lifetimes:

• Static--lifetime is same as that of the program

• Stack-dynamic--lifetime is duration of subprogram

• Explicit heap-dynamic -- Allocated and deallocated by explicit directives, specified by the
programmer, which take effect during execution

• Implicit heap-dynamic--Allocation and deallocation caused by assignment statements

Variable Scope:

• The scope of a variable is the range of statements over which it is visible

• The nonlocal variables of a program unit are those that are visible but not declared there

• The scope rules of a language determine how references to names are associated with variables

• Scope and lifetime are sometimes closely related, but are different concepts

Static Scope:

• The scope of a variable can be determined from the program text

• To connect a name reference to a variable, you (or the compiler) must find the declaration

36 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

• Search process: search declarations, first locally, then in increasingly larger enclosing scopes,
until one is found for the given name Enclosing static scopes (to a specific scope) are called its
static ancestors; the nearest static ancestor is called a static parent

Scope and Shadowed Variables:

• Variables can be hidden from a unit by having a "closer" variable with the same name

• C++, Java and Ada allow access to some of these "hidden" variables

– In Ada: unit.name

– In C++: class_name::name or ::name for globals

– In Java: this.name for variables declared at class level

Static Scoping and Nested Functions:

• Assume MAIN calls A and B

A calls C and D

B calls A and E

Nested Functions and Maintainability:

• Suppose the spec is changed so that D must now access some data in B

• Solutions:

– Put D in B (but then C can no longer call it and D cannot access A's variables)

– Move the data from B that D needs to MAIN (but then all procedures can access them)

• Same problem for procedure access

Dynamic Scope:

• Based on calling sequences of program units, not their textual layout (temporal versus spatial)

• References to variables are connected to declarations by searching back through the chain
of subprogram calls that forced execution to this point

• This is easy to implement but it makes programs hard to follow

• Used in APL, SNOBOL, early versions of LISP

– Perl allows you to use dynamic scope for selected variablesScope

• Static scoping

37 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

– Reference to x is to MAIN's x

• Dynamic scoping

– Reference to x is to SUB1's x

• Evaluation of Dynamic Scoping:

– Advantage: convenience

– Disadvantage: poor readability

Referencing Environments:

• The referencing environment of a statement is the collection of all names that are visible in the
statement
• In a static-scoped language, it is the local variables plus all of the visible variables in all of the
enclosing scopes

– In a dynamic-scoped language, the referencing environment is the local variables plus

all visible variables in all active subprograms subprogram is active if its execution has
begun but has not yet terminate

Expressions and

Statements Arithmetic

Expressions:

• Arithmetic evaluation was one of the motivations for computers

• In programming languages, arithmetic expressions consist of operators, operands,

parentheses, and function calls.

• An operator can be unary, meaning it has a single operand, binary, meaning it has two operands,
or ternary, meaning it has three operands.

• In most programming languages, binary operators are infix, which means they appear between
their operands.

• One exception is Perl, which has some operators that are prefix, which means they precede their
operands.

• The purpose of an arithmetic expression is to specify an arithmetic computation

• An implementation of such a computation must cause two actions: fetching the operands,
usually from memory, and executing arithmetic operations on those operands.

• Arithmetic expressions consist of

38 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

– operators
– operands
– parentheses
– function calls

Issues for Arithmetic Expressions:

• operator precedence rules
• operator associatively rules
• order of operand evaluation
• operand evaluation side effects
• operator overloading
• mode mixing expressions
Operators:

A unary operator has one operand

– unary -, !
• A binary operator has two operands
– +, -, *, /, %

• A ternary operator has three operands - ?:

Conditional Expressions:

• a ternary operator in C-based languages (e.g., C, C++)

• An example:
average = (count == 0)? 0 : sum / count

• Evaluates as if written like

if (count == 0) average = 0

else average = sum /count

Operator Precedence Rules:

• Precedence rules define the order in which “adjacent” operators of different precedence levels
are evaluated
• Typical precedence levels
– parentheses
– unary operators
– ** (if the language supports it)
– *, /

+, -

Operator Associativity Rules:

39 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

• Associativity rules define the order in which adjacent operators with the same precedence
level are evaluated

• Typical associativity rules

– Left to right for arithmetic operators
– exponentiation (** or ^) is right to left
– Sometimes unary operators associate right to left (e.g., in FORTRAN)
• APL is different; all operators have equal precedence and all operators associate right to left
• Precedence and associativity rules can be overriden with parentheses

Operand Evaluation Order:

1. Variables: fetch the value from memory

2. Constants: sometimes a fetch from memory; sometimes the constant is in the machine
language instruction

3. Parenthesized expressions: evaluate all operands and operators first

Potentials for Side Effects:

• Functional side effects: when a function changes a two-way parameter or a non-local variable
• Problem with functional side effects:
– When a function referenced in an expression alters another operand of the expression;
e.g., for a parameter change:

a = 10;
/* assume that fun changes its parameter */

b = a + fun(a);

Functional Side Effects:

• Two possible solutions to the problem

1. Write the language definition to disallow functional side effects

• No two-way parameters in functions

• No non-local references in functions
• Advantage: it works!
• Disadvantage: inflexibility of two-way parameters and non-local references
2. Write the language definition to demand that operand evaluation order be fixed

• Disadvantage: limits some compiler optimizations

Overloaded Operators:

40 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

• Use of an operator for more than one purpose is called operator overloading
• Some are common (e.g., + for int and float)
• Some are potential trouble (e.g., * in C and C++)
– Loss of compiler error detection (omission of an operand should be a detectable error)
– Some loss of readability
– Can be avoided by introduction of new symbols (e.g., Pascal’s div for integer division)

Type Conversions

• A narrowing conversion converts an object to a type that does not include all of the values of the
original type

– e.g., float to int

• A widening conversion converts an object to a type that can include at least approximations to
all of the values of the original type

– e.g., int to float

Coercion:

• A mixed-mode expression is one that has operands of different types

• A coercion is an implicit type conversion
• Disadvantage of coercions:
– They decrease in the type error detection ability of the compiler
• In most languages, widening conversions are allowed to happen implicitly
• In Ada, there are virtually no coercions in expressions
Casting:

• Explicit Type Conversions

• Called casting in C-based language
• Examples
– C: (int) angle

– Ada: Float (sum)

Note that Ada’s syntax is similar to function calls

Errors in Expressions:

• Causes
– Inherent limitations of arithmetic e.g., division by zero, round-off errors
– Limitations of computer arithmetic e.g. overflow

41 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

• Often ignored by the run-time system

Relational Operators:

• Use operands of various types

• Evaluate to some Boolean representation
• Operator symbols used vary somewhat among languages (!=, /=, .NE., <>, #)
Boolean Operators:

• Operands are Boolean and the result is Boolean

• Example operators
FORTRAN 77 FORTRAN 90 C Ada

AND .and && and

.OR .or || or
.NOT .not ! not

No Boolean Type in C:

• C has no Boolean type

– it uses int type with 0 for false and nonzero for true
• Consequence
– a < b < c is a legal expression
– the result is not what you might expect:
• Left operator is evaluated, producing 0 or 1
• This result is then compared with the third operand (i.e., c)
Precedence of C-based operators:

postfix ++, --

unary +, -, prefix ++, --, !

*,/,%

binary +,

<, >, <=, >=

=, !=

&&

42 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

||

Short Circuit Evaluation:

• Result is determined without evaluating all of the operands and/or operators

– Example: (13*a) * (b/13–1)

If a is zero, there is no need to evaluate (b/13-1)

• Usually used for logical operators

• Problem with non-short-circuit evaluation
While (index <= length) && (LIST[index] != value)

Index++;

– When index=length, LIST [index] will cause an indexing problem (assuming LIST has
length -1 elements)

Mixed-Mode Assignment:

Assignment statements can also be mixed-mode, for example

int a, b;

float c;

c = a / b;

• In Java, only widening assignment coercions are done

• In Ada, there is no assignment coercion

Assignment Statements:

• The general syntax

<target_var> <assign_operator> <expression>

• The assignment operator

= FORTRAN, BASIC, PL/I, C, C++, Java

:= ALGOLs, Pascal, Ada

• = can be bad when it is overloaded for the relational operator for equality
Compound Assignment:

• A shorthand method of specifying a commonly needed form of assignment

• Introduced in ALGOL; adopted by C

43 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

• Example
a=a+b

is written as

a += b

Unary Assignment Operators:

• Unary assignment operators in C-based languages combine increment and decrement operations
with assignment

– These have side effects

• Examples
sum = ++count (count incremented, added to sum)

sum = count++ (count added to sum, incremented)

Count++ (count incremented)

-count++ (count incremented then negated - right-associative)

Assignment as an Expression:

• In C, C++, and Java, the assignment statement produces a result and can be used as operands
• An example:
While ((ch = get char ())!= EOF){…}

ch = get char() is carried out; the result (assigned to ch) is used in the condition for the while
statement

Control Statements: Evolution

• FORTRAN I control statements were based directly on IBM 704 hardware
• Much research and argument in the 1960s about the issue
One important result: It was proven that all algorithms represented by flowcharts can be coded
with only two-way selection and pretest logical loops

Control Structure

• A control structure is a control statement and the statements whose

execution it controls
• Design question
–Should a control structure have multiple entries?

44 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

Selection Statements

• A selection statement provides the means of choosing between two or more paths of execution
• Two general categories:
–Two-way selectors
–Multiple-way selectors

Two-Way Selection Statements

• General form:
If control_expression
then clause
else clause
• Design Issues:
–What is the form and type of the control expression?
–How are the then and else clauses specified?
–How should the meaning of nested selectors be specified?

The Control Expression

• If the then reserved word or some other syntactic marker is not used to introduce the then clause, the
control expression is placed in parentheses
• In C89, C99, Python, and C++, the control expression can be arithmetic
• In languages such as Ada, Java, Ruby, and C#, the control expression must be Boolean

Clause Form
• In many contemporary languages, the then and else clauses can be single statements or
compound statements
• In Perl, all clauses must be delimited by braces (they must be compound)

• In Fortran 95, Ada, and Ruby, clauses are statement sequences

• Python uses indentation to define clauses
if x > y :
x=y
print "case 1"

Nesting Selectors

45 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

• Java example
if ( sum == 0)
if ( count == 0)
result = 0;
else result = 1;
• Which if gets the else?
• Java's static semantics rule: else matches with the nearest if
Nesting Selectors (continued)
• To force an alternative semantics, compound statements may be
used: if (sum == 0) {
if (count == 0)
result = 0;
}
else result = 1;
• The above solution is used in C, C++, and C#
• Perl requires that all then and else clauses to be compound
• Statement sequences as clauses:
Ruby if sum == 0 then
if count == 0 then
result = 0
else
result = 1
end
end

•Python
if sum == 0 :
if count == 0 :
result = 0
else :
result = 1

Multiple-Way Selection Statements

• Allow the selection of one of any number of statements or statement groups

Design Issues:
• What is the form and type of the control expression?

46 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

• How are the selectable segments specified?

• Is execution flow through the structure restricted to include just a single selectable segment?
• How are case values specified?
• What is done about unrepresented expression values?

Multiple-Way Selection: Examples

• C, C++, and Java
switch (expression)
{
case const_expr_1: stmt_1;
…
case const_expr_n: stmt_n;
[default: stmt_n+1]
}
• Design choices for C‘s switch statement
• Control expression can be only an integer type
• Selectable segments can be statement sequences, blocks, or compound statements
• Any number of segments can be executed in one execution of the construct (there is no implicit
branch at the end of selectable segments)
• default clause is for unrepresented values (if there is no default, the whole statement does nothing)

Multiple-Way Selection: Examples

• C#
- Differs from C in that it has a static semantics rule that disallows the implicit execution of
more than one segment
- Each selectable segment must end with an unconditional branch (goto or break)
• Ada
case expression is
when choice list => stmt_sequence;

…
when choice list => stmt_sequence;
when others => stmt_sequence;]
end case;
• More reliable than C‘s switch (once a stmt_sequence execution is completed, control is passed to
the first statement after the case statement
• Ada design choices:

47 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

1. Expression can be any ordinal type

2. Segments can be single or compound
3. Only one segment can be executed per execution of the construct
4. Unrepresented values are not allowed
• Constant List Forms:
1. A list of constants
2. Can include:
- Subranges
- Boolean OR operators (|)

Multiple-Way Selection Using if

• Multiple Selectors can appear as direct extensions to two-way selectors, using else-if clauses, for
example in Python:
if count < 10 :
bag1 = True
elsif count < 100 :
bag2 = True
elif count < 1000 :
bag3 = True

Iterative Statements

• The repeated execution of a statement or compound statement is accomplished either by iteration or

recursion
• General design issues for iteration control statements:
1. How is iteration controlled?
2. Where is the control mechanism in the loop?

Counter-Controlled Loops

• A counting iterative statement has a loop variable, and a means of specifying the initial and
terminal, and stepsize values

• Design Issues:
• What are the type and scope of the loop variable?
• What is the value of the loop variable at loop termination?
• Should it be legal for the loop variable or loop parameters to be changed in the loop body, and if so,
does the change affect loop control?
• Should the loop parameters be evaluated only once, or once for every iteration?

48 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

Iterative Statements: Examples

• FORTRAN 95 syntax
DO label var = start, finish [, stepsize]
• Stepsize can be any value but zero
• Parameters can be expressions
• Design choices:
1. Loop variable must be INTEGER
2. Loop variable always has its last value
3. The loop variable cannot be changed in the loop, but the parameters can; because they are evaluated
only once, it does not affect loop control
4. Loop parameters are evaluated only once
•FORTRAN 95 : a second form:
[name:] Do variable = initial, terminal [,stepsize]
…
End Do [name]
- Cannot branch into either of Fortran‘s Do statements
• Ada
for var in [reverse] discrete_range loop ...
end loop

• Design choices:
- Type of the loop variable is that of the discrete range (A discrete range is a sub-range of an integer or
enumeration type).
- Loop variable does not exist outside the loop
- The loop variable cannot be changed in the loop, but the discrete range can; it does not affect
loop control
- The discrete range is evaluated just once
• Cannot branch into the loop body
• C-based languages
for ([expr_1] ; [expr_2] ; [expr_3]) statement

- The expressions can be whole statements, or even statement sequences, with the statements separated by
commas
–The value of a multiple-statement expression is the value of the last statement in the expression
–If the second expression is absent, it is an infinite loop

49 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

• Design choices:
- There is no explicit loop variable
- Everything can be changed in the loop
- The first expression is evaluated once, but the other two are evaluated with each iteration
•C++ differs from C in two ways:
•The control expression can also be Boolean
•The initial expression can include variable definitions (scope is from the definition to the end of the loop
body)
•Java and C#
–Differs from C++ in that the control expression must be Boolean
Iterative Statements: Logically-Controlled Loops
•Repetition control is based on a Boolean expression
•Design issues:
–Pretest or posttest?
–Should the logically controlled loop be a special case of the counting loop statement or a separate
statement?

Iterative Statements: Logically-Controlled Loops: Examples

•C and C++ have both pretest and posttest forms, in which the control
expression can be arithmetic:
while (ctrl_expr) do
loop body loop body
while (ctrl_expr)
•Java is like C and C++, except the control expression must be Boolean (and the body can only be entered
at the beginning -- Java has no goto
Iterative Statements: Logically-Controlled Loops: Examples
•Ada has a pretest version, but no posttest

•FORTRAN 95 has neither

•Perl and Ruby have two pretest logical loops, while and until. Perl also has two posttest loops
Iterative Statements: User-Located Loop Control Mechanisms
• Sometimes it is convenient for the programmers to decide a location for loop control (other than top
or bottom of the loop)
•Simple design for single loops (e.g., break)
•Design issues for nested loops
•Should the conditional be part of the exit?

50 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

•Should control be transferable out of more than one loop?

Iterative Statements: User-Located Loop Control Mechanisms break and continue
•C , C++, Python, Ruby, and C# have unconditional unlabeled exits (break)
•Java and Perl have unconditional labeled exits (break in Java, last in Perl)
•C, C++, and Python have an unlabeled control statement, continue, that skips the remainder of the
current iteration, but does not exit the loop
•Java and Perl have labeled versions of continue
Iterative Statements: Iteration Based on Data Structures
•Number of elements of in a data structure control loop iteration
•Control mechanism is a call to an iterator function that returns the next element in some chosen order, if
there is one; else loop is terminate
•C's for can be used to build a user-defined iterator:
for (p=root; p==NULL; traverse(p)){
}
•C#‘s foreach statement iterates on the elements of arrays and other
collections:
Strings[] = strList = {"Bob", "Carol", "Ted"};
foreach (Strings name in strList)
Console.WriteLine ("Name: {0}", name);
- The notation {0} indicates the position in the string to be displayed
•Perl has a built-in iterator for arrays and hashes, foreach
Unconditional Branching

•Transfers execution control to a specified place in the program

•Represented one of the most heated debates in 1960‘s and 1970‘s
•Well-known mechanism: goto statement
•Major concern: Readability
•Some languages do not support goto statement (e.g., Java)
•C# offers goto statement (can be used in switch statements)
•Loop exit statements are restricted and somewhat camouflaged goto‘s
Guarded Commands
•Designed by Dijkstra
•Purpose: to support a new programming methodology that supported
verification (correctness) during development
•Basis for two linguistic mechanisms for concurrent programming (in CSP and
Ada)

51 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

• Basic Idea: if the order of evaluation is not important, the program

should not specify one

Selection Guarded Command

•Form
if <Boolean exp> -> <statement>
[] <Boolean exp> -> <statement>
...
[] <Boolean exp> -> <statement>
if
•Semantics: when construct is reached,
–Evaluate all Boolean expressions
–If more than one are true, choose one non-deterministically
–If none are true, it is a runtime error
Selection Guarded Command: Illustrated
Loop Guarded Command

• Form
do <Boolean> -> <statement>
[] <Boolean> -> <statement>
...
[] <Boolean> -> <statement>
od
•Semantics: for each iteration
–Evaluate all Boolean expressions
–If more than one are true, choose one non-deterministically; then start loop again
–If none are true, exit loop
Guarded Commands: Rationale
• Connection between control statements and program verification is intimate
•Verification is impossible with goto statements
•Verification is possible with only selection and logical pretest loops
•Verification is relatively simple with only guarded commands

SUB PROGRAMS

Basic Definitions:

52 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

 A subprogram definition is a description of the actions of the subprogram abstraction

 A subprogram call is an explicit request that the subprogram be executed
 A subprogram header is the first line of the definition, including the name, the kind of
 subprogram, and the formal parameters
 The parameter profile of a subprogram is the number, order, and types of its parameters
 The protocol of a subprogram is its parameter profile plus, if it is a function, its return type
 A subprogram declaration provides the protocol, but not the body, of the subprogram
 A formal parameter is a dummy variable listed in the subprogram header and used in
the subprogram
 An actual parameter represents a value or address used in the subprogram
call Statement

Actual/Formal Param

Correspondence Two basic choices:

 Positional
 Keyword
 Sort (List => A, Length => N);
 For named association:
Advantage: order is irrelevant

Disadvantage: user must know the formal

 parameter’s names
Sort (List => A, Length => N);

53 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

For named association:

Advantage: order is irrelevant

Disadvantage: user must know the formal parameter’s names

Default Parameter Values

Example, in Ada:

procedure sort (list : List_Type;

length : Integer := 100);

sort (list => A);

Two Types of Subprograms

 Procedures provide user-defined statements, Functions provide user-defined operators

Design Issues for Subprograms

 What parameter passing methods are provided?

 Are parameter types checked?
 Are local variables static or dynamic?
 What is the referencing environment of a passed subprogram?
 Are parameter types in passed subprograms checked?
 Can subprogram definitions be nested?
 Can subprograms be overloaded?
 Are subprograms allowed to be generic?
 Is separate/independent compilation supported?
 Referencing Environments
 If local variables are stack-dynamic:
 Advantages:
o Support for recursion
o Storage for locals is shared among some subprograms
 Disadvantages:

54 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

o Allocation/deallocation time
o Indirect addressing
o Subprograms cannot be history sensitive
o Static locals are the opposite
Parameters and Parameter Passing:

Semantic Models: in mode, out mode, inout mode

Conceptual Models of Transfer:

o Physically move a value

o Move an access path
Implementation Models:

• Pass-by-value
• Pass-by-result
• Pass-by-value-result
• Pass-by-reference
• Pass-by-name
Models of Parameter Passing

Pass-By-Value
 in mode
 Either by physical move or access path
Disadvantages of access path method: Must write-protect in the called subprogram, Accesses cost
more (indirect addressing)

55 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

Disadvantages of physical move:

Requires more storage
Cost of the moves
Pass-By-Result
 out mode
Local’s value is passed back to the caller
 Physical move is usually used
Disadvantages:

• If value is moved, time and space

• In both cases, order dependence may be a problem

procedure sub1(y: int, z: int);

...

sub1(x, x);

• Value of x in the caller depends on order of assignments at the return

Pass-By-Value-Result

inout mode

Physical move, both ways Also called pass-by-copy

Disadvantages:

Those of pass-by-result

Those of pass-by-value

Pass-By-Reference

inout mode

Pass an access path Also called pass-by-sharing

Advantage: passing process is efficient

Disadvantages:

Slower accesses can allow aliasing: Actual parameter collisions: sub1(x, x); Array element
collisions: sub1(a[i], a[j]); /* if i = j */ Collision between formals and globals Root cause of all of

56 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

these is: The called subprogram is provided wider access to non locals than is necessary

Pass-by-value-result does not allow these aliases (but has other problems!)

Pass-By-Name multiple modes By textual substitution ,Formals are bound to an access method at
the time of the call, but actual binding to a value or address takes place at the time of a reference or
assignment

Purpose: flexibility of late binding

Resulting semantics:

If actual is a scalar variable, it is pass-by-reference

If actual is a constant expression, it is pass-by-value
If actual is an array element, it is like nothing else
If actual is an expression with a reference to a variable that is also accessible in the program, it is also
like nothing else
Pass-By-Name Example 1
procedure sub1(x: int; y: int);
begin
x := 1;
y := 2;
x := 2;
y := 3;
end;
sub1(i, a[i]);

Pass-By-Name Example 2
• Assume k is a global variable
procedure sub1(x: int; y: int; z: int);
begin
k := 1;
y := x;
k := 5;
z := x;
end;
sub1(k+1, j, i);

Disadvantages of Pass-By-Name

• Very inefficient references

• Too tricky; hard to read and understand

Param Passing: Language Examples

FORTRAN, Before 77, pass-by-reference 77—scalar variables are often passed by value result

57 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

ALGOL 60 Pass-by-name is default; pass-by-value is optional

ALGOL W: Pass-by-value-result ,C: Pass-by-value Pascal and Modula-2: Default is pass-by

value;,pass-by-reference is optional

Param Passing: PL Example

C++: Like C, but also allows reference type parameters, which provide the efficiency of pass-by-
reference with in-mode semantics

Ada

All three semantic modes are available If out, it cannot be referenced If in, it cannot be assigned
Java Like C++, except only references

Type Checking Parameters

Now considered very important for reliability

FORTRAN 77 and original C: none

Pascal, Modula-2, FORTRAN 90, Java, and Ada: it is always required

ANSI C and C++: choice is made by the user

Implementing Parameter Passing

ALGOL 60 and most of its descendants use the runtime stack Value—copy it to the stack; references are
indirect to the stack Result—sum, Reference—regardless of form, put the address in the stack

Name:

Run-time resident code segments or subprograms evaluate the address of the parameter Called for each
reference to the formal, these are called thunks Very expensive, compared to reference or value-result

Ada Param Passing Implementations

Simple variables are passed by copy (valueresult) Structured types can be either by copy or reference
This can be a problem, because Aliasing differences (reference allows aliases, but value-result does not)
Procedure termination by error can produce different actual parameter results Programs with such errors
are “erroneous”

Multidimensional Arrays as Params

58 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

If a multidimensional array is passed to a subprogram and the subprogram is separately compiled, the
compiler needs to know the declared size of that array to build the storage mapping function

C and C++

Programmer is required to include the declared sizes of all but the first subscript in the actual parameter ,
This disallows writing flexible subprograms Solution: pass a pointer to the array and the sizes of the
dimensions as other parameters; the user must include the storage mapping function, which is in terms of
the size

More Array Passing Designs

Pascal Not a problem (declared size is part of the array’s type)

Ada

Constrained arrays—like Pascal

Unconstrained arrays—declared size is part of the object declaration Pre-90 FORTRAN , Formal
parameter declarations for arrays can include passed parameters

SUBPROGRAM SUB(MATRIX, ROWS, COLS, RESULT)

INTEGER ROWS, COLS

REAL MATRIX (ROWS, COLS), RESULT

...

END

Design Considerations for Parameter Passing

 Efficiency
 One-way or two-way
 These two are in conflict with one another!
 Good programming => limited access to
 variables, which means one-way whenever possible
 Efficiency => pass by reference is fastest way to pass structures of significant size Also,
functions should not allow reference Parameters
Subprograms As Parameters: Issues

Are parameter types checked?

59 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

Early Pascal and FORTRAN 77 do not Later versions of Pascal, Modula-2, and FORTRAN 90 do Ada
does not allow subprogram parameters C and C++ - pass pointers to functions; parameters can be type
checked

What is the correct referencing?

environment for a subprogram that was sent as a parameter?

Possibilities:

It is that of the subprogram that called it (shallow binding)

It is that of the subprogram that declared it (deep binding)

It is that of the subprogram that passed it (ad hocbinding, never been used)
For static-scoped languages, deep binding is most natural

For dynamic-scoped languages, shallow binding is most natural

Overloading

An overloaded subprogram is one that has the same name as another subprogram in the same referencing
environment C++ and Ada have overloaded subprograms built-in, and users can write their own
overloaded subprograms

Generic Subprograms

1. A generic or polymorphic subprogram is one that takes parameters of different types on different
activations Overloaded subprograms provide ad hoc polymorphism
2. A subprogram that takes a generic parameter that is used in a type expression that describes the
type of the parameters of the subprogram provides parametric polymorphism
3. See Ada generic and C++ template examples in text
4. Independent compilation is compilation of some of the units of a program separately from the rest
of the program, without the benefit of interface information
5. Separate compilation is compilation of some of the units of a program separately from the rest of the
program, using interface information to check the correctness of the interface between the two parts

Language Examples:

• FORTRAN II to FORTRAN 77: independent

60 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

• FORTRAN 90, Ada, Modula-2, C++: separate

• Pascal: allows neither

Functions

Design Issues:

• Are side effects allowed?

• Two-way parameters (Ada does not allow)
• Nonlocal reference (all allow)
• What types of return values are allowed?

61 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

• FORTRAN, Pascal, Modula-2: only simple types

• C: any type except functions and arrays
• Ada: any type (but subprograms are not types)
• C++ and Java: like C, but also allow classes to be returned

Accessing Nonlocal Environments

The nonlocal variables of a subprogram are those that are visible but not declared in the subprogram

Global variables are those that may be visible in all of the subprograms of a program

Methods for Accessing Non locals

FORTRAN COMMON

The only way in pre-90 FORTRANs to access nonlocal variables

Can be used to share data or share storage

Static scoping

External declarations: C

• Subprograms are not nested

• Globals are created by external declarations (they are simply defined outside any function)
• Access is by either implicit or explicit declaration
• Declarations (not definitions) give types to externally defined variables (and say they are
defined elsewhere)
• External modules: Ada and Modula-2:
• Dynamic Scope:

User-Defined Overloaded Operators

Nearly all programming languages have overloaded operators

Users can further overload operators in C++ and Ada not carried over into Java)

Ada Example (where Vector_Type is an array of

Integers): function "*"(a, b : inVector_Type) return Integer

is

62 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

sum : Integer := 0;

begin

for index in a ‘range loop

sum := sum + a(index) * b(index);

end loop;

return sum;

end "*";

Are user-defined overloaded operators good or bad?

Coroutines:

Coroutine is a subprogram that has multiple entries and controls them itself Also called symmetric
control A coroutine call is named a resume. The first resume of a coroutine is to its beginning, but
subsequent calls enter at the point just after the last executed statement in the coroutine. Typically,
coroutines repeatedly resume each other, possibly forever. Coroutines provide quasiconcurrent
execution of program units (the coroutines) Their execution is interleaved, but not overlapped

63 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

Coroutines Illustrated: Possible Execution Controls

Coroutines Illustrated: Possible Execution Controls with Loops

ABSTRACT DATA TYPES

Abstraction:

- The concept of abstraction is fundamental in programming

- Nearly all programming languages support process abstraction with subprograms

- Nearly all programming languages designed since 1980 have supported data abstraction with some
kind of module

Encapsulation:

- Original motivation:

- Large programs have two special needs:

1. Some means of organization, other than simply division into subprograms

2. Some means of partial compilation (compilation units that are smaller than the whole program)

- Obvious solution: a grouping of subprograms that are logically related into a unit that can be
separately compiled

- These are called encapsulations

Examples of Encapsulation Mechanisms:

1. Nested subprograms in some ALGOL-like languages (e.g., Pascal)

64 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

2. FORTRAN 77 and C - Files containing one or more subprograms can be independently compiled

3. FORTRAN 90, C++, Ada (and other contemporary languages) - separately compliable modules

Definitions: An abstract data type is a user-defined datatype that satisfies the following two conditions:

Definition 1: The representation of and operations of objects of the type are defined in a single
syntactic unit; also, other units can create objects of the type.

Definition 2: The representation of objects of the type is hidden from the program units that use
these objects, so the only operations possible are those provided in the type's definition.
Advantage of Restriction 1:

- Same as those for encapsulation: program organization, modifiability (everything

associated with a data structure is together), and separate compilation

Advantage of Restriction 2:

- Reliability--by hiding the data representations, user code cannot directly access
objects of the type. User code cannot depend on the representation, allowing the representation to
be changed without affecting user code.

Built-in types are abstract data types:

EX: int type in C

- The representation is hidden

- Operations are all built-in

- User programs can define objects of int type

- User-defined abstract data types must have the same characteristics as built-in abstract data
types

Language Requirements for Data Abstraction:

1. A syntactic unit in which to encapsulate the type definition.

2. A method of making type names and subprogram headers visible to clients, while hiding
actual definitions.

3. Some primitive operations must be built into the language processor (usually just
assignment and comparisons for equality and inequality)

- Some operations are commonly needed, but must be defined by the type designer

- e.g., iterators, constructors, destructors

65 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

Language Design Issues:

1. Encapsulate a single type, or something more?

2. What types can be abstract?

3. Can abstract types be parameterized?
4. What access controls are provided?

Language Examples:

1. Simula 67

- Provided encapsulation, but no information hiding

2. Ada

- The encapsulation construct is the package

- Packages usually have two parts:

1. Specification package (the interface)

2. Body package (implementation of the entities named in the specification

- Any type can be exported

- Information Hiding
- Hidden types are named in the spec package in, as in:

type NODE_TYPE is private;

- Representation of an exported hidden type is specified in a special invisible (to clients) part
of the spec package (the private clause), as in:

package … is

type NODE_TYPE is private;

type NODE_TYPE is

record

end record;

66 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

…
A spec package can also define unhidden type simply by providing the representation outside a private clause

The reasons for the two-part type definition are:

1. The compiler must be able to see the representation after seeing only the spec package (the
compiler can see the private clause)

2. Clients must see the type name, but not the representation (clients cannot see the private clause)

Parameterized Abstract Data Types

• Parameterized ADTs allow designing an ADT that can store any type elements (among other things)

• Also known as generic classes

• C++, Ada, Java 5.0, and C# 2005 provide support for parameterized ADTs
Parameterized ADTs in Ada
• Ada Generic Packages
–Make the stack type more flexible by making the element type and the size of the stack generic
generic
Max_Size: Positive;
type Elem_Type is private;
package Generic_Stack is
Type Stack_Type is limited private;
function Top(Stk: in out StackType) return Elem_type;
…
end Generic_Stack;
Package Integer_Stack is new Generic_Stack(100,Integer);
Package Float_Stack is new Generic_Stack(100,Float);

Parameterized ADTs in C++

• Classes can be somewhat generic by writing parameterized
constructor functions
class stack {
…
stack (int size)
{ stk_ptr = new int
[size]; max_len = size -
1;
top = -1;

67 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

};
…
}
stack stk(100);
• The stack element type can be parameterized by making the class a template
class template <class Type>
class stack {
private:
Type *stackPtr;
const int maxLen;
int topPtr;
public:
stack() {
stackPtr = new Type[100];
maxLen = 99;
topPtr = -1;
}
…
}

Parameterized Classes in Java 5.0

• Generic parameters must be classes
• Most common generic types are the collection types, such as Linked List and Array List
• Eliminate the need to cast objects that are removed
• Eliminate the problem of having multiple types in a structure
Parameterized Classes in C# 2005
• Similar to those of Java 5.0
• Elements of parameterized structures can be accessed through indexing
• The concept of ADTs and their use in program design was a milestone in the development of
languages
• Two primary features of ADTs are the packaging of data with their associated operations
and information hiding
• Ada provides packages that simulate ADTs
• C++ data abstraction is provided by classes
• java‘s data abstraction is similar to C++
• Ada, C++, Java 5.0, and C# 2005 support parameterized ADTs

68 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)
 lOMoARcPSD|53449593

69 ASMITA S GAIKWAD
Downloaded by Harshad Pakhale (learntech2215@gmail.com)