ITC 305-Paradigms and Computer Programming

Fundamental

Chapter -01 Introduction to different programming paradigms.

Names, Scopes, and Bindings, Scope Rules, Storage Management.

Type Systems, Type Checking, Equality Testing and Assignment.

Subroutine and Control Abstraction: Stack Layout, Calling sequence, parameter passing

Generic subroutines and modules. Exception handling, Coroutines and Events.

 Introduction to different Programming paradigms

Paradigm:
- style or way of programming
- way of thinking
- method to solve some problems or do some task
Programming paradigm:
- way to classify programming languages based on their features
- method to solve a problem using some tools and techniques
- blueprint to do something

2
 Types Programming paradigm

Programming
Paradigm

Imperative Declarative
Programming Programming
Paradigm Paradigm

1.Procedural Programming Paradigm 1.Logical Programming Paradigm

2. Object Oriented Programming Paradigm 2.Functional Programming Paradigm
3.Parallel Processing Approach
3.Database Processing Approach
3
 Difference between Imperative & Declarative
Programming paradigms
Imperative Programming Declarative Programming
paradigms paradigms

How a program works what a program does

1.What are the steps involved in the

1. What will be output.
particular program to achieve our goal.
2. Allows compiler to make decisions.
2. User makes decisions and commands
3. Order of execution is low
to compiler.
importance
3. Order of execution is important.
4. Example:
4. Example:
Python,HASKELL, SCALA,
C, C++, C#, Ruby, FORTRAN,
PROLOG,SQL,XSLT
JAVA, COBAL,ADA,JAVA SCRIPT

4
Example Program:( Imperative)
C Program
Adding 2 numbers: #include <stdio.h>
C++ Program int main() {
int main()
{ int number1, number2, sum;
int num1, num2, add;
cout<<"Enter Two Numbers: "; printf("Enter two integers: ");
scanf("%d %d", &number1, &number2);
cin>>num1>>num2;
add = num1+num2;
// calculate the sum
cout<<"\nResult = "<<add; sum = number1 + number2;
cout<<endl;
return 0; printf("%d + %d = %d", number1, number2,
} sum);
Example :(Declarative) return 0;
}
Information of all the users who lives in Thane:

SELECT * FROM users WHERE city = ‘Thane’;

5
Imperative programming paradigm:
- is a programming paradigm that uses statements which changes a
program’s state.

Declarative programming paradigm:

-is a programming paradigm that expresses the logic of a
computation without describing its control flow.

6
Imperative Programming Paradigm:
Advantages:
1.Easy to implement
2.Low memory utilization
3.Contains variable and iterations

Drawbacks:
1.Complex programs cannot be solved
2.Less efficient & less productive

7
Procedural programming paradigm –
● This paradigm emphasizes on procedure in terms of under lying machine
model. There is no difference in between procedural and imperative
approach.

Parallel Processing:
- Is the processing of program instructions by dividing them among multiple
processors.
- Parallel processing system consists of many number of processor with the
objective of running a program in less time by dividing them.
- It seems to be like Divide and conquer.
Eg: C/C++

8
Object Oriented Programming Paradigm:
- It revolves around class and object.
- Program is written as a collection of classes and objects.
- Main focus is on data not on procedures.
- Data immutable
- Data and functions are bound in one entity called as class.
Features:
1.Data abstraction
2. Encapsulation
3. Inheritance
4. Polymorphism
5. Easily debugged and modify
6.Handling errors
Eg:
C++,JAVA, Python,Ruby
9
Database Programming Approach:
- It is based on data and its movements.
- Program statements are defined by data rather than coding a series of steps.
- It’s a heart of the database information system and provides file creation, data
entry, update,query and reporting files.
- Mostly developed for DB applications
Eg: SQL

10
Functional Programming Paradigm:
- Computations are expressed in functions.
- Key principal of this paradigm is the execution of series of mathematical
functions.
- It supports functional approach to problem solving.
Eg: Haskell, scala, javascript
Features:
- Reusability of function
- Large numbers of functions are maintained.
Drawback:
-consumes large amount of time and memory.

11
Logical Programming Paradigm:
- It includes logic statements that expresses facts and rules about the program.
- No step by step instruction
- Make use of TRUE and FALSE statements
- Computation are expressed in mathematical logic
Eg: PROLOG, ALF
Drawbacks:
1. Slow execution
2. Cannot solve most of the complex problems

12
Naming & Binding
 Name
▪ Name
▪ Binding
▪ Diff. classes of binding time

Name:
String of characters used to identify some entity in a program.
- Many different kinds of things can be named for example-
- Variables,constants,functions/procedure,classes,labels,packages
- Usually name can have a maximum of 31 characters.
- Compiler examples:
○ FORTRAN 95- 31 chars
○ C89 no length limitation
○ C99 allows first 63 characters
○ Some compilers allow up to 247 characters.

14
 Generic rule for naming:
1. It should be begin with a letter followed by a string of letters or digits or
underscore(_)
2. Keywords or reserve words cannot be used.
Eg. Int, char, float, if else,….
3. White spaces are not allowed
4. Commas, special characters other than underscore cannot be used.

Design issues:
1. Are the names are case sensitive ? AGE, age, Age
2. Are able to use reserve words or keywords?
- Best solution is make the language case sensitive and the keywords and reserve
words cannot be used in naming the variable.

15
 Binding
• A binding is an association of a element and its property(datatype)
• Association of a variable name with its value.
• Int age=25;
• Variable name age is associated with the memory address 1000 to 1003.
• Value 25 is associated with the name age.
• These are called binding.

Binding time:
- is the time at which a binding is created or the time at which the association between the
name and an entity is created is called as binding time.
16
 Different classes of binding time
The following list is ordered from early binding to late binding

1. Language Design time:

- The syntax and semantics of a language is set at the language design time.
- The language designer should define what are all the control constraints to be
followed
- How the controls should be executed
- How the variable declaration are written
- Whether static/dynamic scoping is used in the new programming language or not.
- The designer bind keywords to their meaning.
2. Language Implementation Time:
- The binding that will takes place during implementation can be the exception
handling during run time, arithmetic overflow like divide by zero are dynamically
17
allocated.
 - The precision( no.of bits) to be needed in the result of a particular operation are also
defined in the implementation time.
3. Program Writing Time:
- Programmers choose the algorithms, data structures and name.
4. Compiler time:
- During the compiler time the binding of various names with object methods etc. will takes
place.
- eg., for a static variable a stack is allocated,
for dynamic variable a heap memory is allocated.
5. Link Time:
- It chooses the overall layout of the modules with respect to one another and resolves inter
module references.
- A program is not at all complete until all the modules in the program are joined together
by a linker.
18
6. Load Time:
- Process of loading the program from the secondary memory to the main memory with
the help of OS.
- During this process the virtual address translates into physical address.
7. Run Time:
- also called as dynamic binding time.
- the type of a variable cannot be determined until the user inputs the value.
- once the values are assigned and the program runs and produces output.

19
Types of Binding :

Static binding
Binding performed prior to run time.

Dynamic binding
Binding performed during to run time.

20
Scope
-A scope is the context within a computer program in which a variable
name or other identifier is valid and can be used.

- the part of the program in which the binding is active.

- the lifetime of the binding of a name to an object.
- two types of scope:
1.static scope- scoping follows the structure the program
C is said to be statically scoped
2.dynamic scope- where scoping follow the execution path.Their binding
depends on the flow of execution at runtime.

21
 Static Vs Dynamic Scoping
● Static Scoping:
● Static scoping is also called lexical scoping. In this scoping, a variable always refers to its
top-level environment. This is a property of the program text and is unrelated to the
run-time call stack. Static scoping also makes it much easier to make a modular code as a
programmer can figure out the scope just by looking at the code. In contrast, dynamic scope
requires the programmer to anticipate all possible dynamic contexts.
● In most programming languages including C, C++, and Java, variables are always statically
(or lexically) scoped i.e., binding of a variable can be determined by program text and is
independent of the run-time function call stack.

22
Dynamic Scoping:

● With dynamic scope, a global identifier refers to the identifier associated with the most recent environment
and is uncommon in modern languages. In technical terms, this means that each identifier has a global stack
of bindings and the occurrence of an identifier is searched in the most recent binding.
● In simpler terms, in dynamic scoping, the compiler first searches the current block and then successively all
the calling functions.
● Dynamic scoping does not care about how the code is written, but instead how it executes. Each time a new
function is executed, a new scope is pushed onto the stack.
● Perl supports both dynamic and static scoping. Perl’s keyword “my” defines a statically scoped local
variable, while the keyword “local” defines a dynamically scoped local variable.

23
Static Scoping Dynamic Scoping

Static scoping which is also known as lexical scoping in Dynamic scoping is a useful substitute for global
which an object is searched on the base of the text of the objects.
program.

The bindings between the object and the name of the object The bindings between the object and the name of the
are taken into consideration at compile time instead of run object are taken into consideration at run time.
time.

Static or lexical scoping describes the meaning from the A sequence is determined the dynamic scope of a
name itself that is ‘LEXICAL’ which means text. variable which is called during program execution.

Here, the object is searched in the local function and then Here, the object is searched in the local function first
in the function in which that function was defined and so and then in the function that called the function and
on. so on.
24
 Scope Rules
• The region of program text where a binding is active is called the scope
of the binding.
○ Static
○ Nested subroutine
○ Declaration order
○ Dynamic
○ Modules

25
 Static Scope Rule
• Scope of a variable or method is determined at compile time.

Int A=10;

Stack Frame
A B C C
Static link
D
D Static link
B
Static link
E
E
Static link
A

26
• Scoping is a active textual region / active binding time in a program referencing
environment.
– So, C and D are the actual region till the execution of the subroutine B .
– E has the actual execution region inside the subroutine A.
• The scope of the local variable is limited to the subroutine in which it appears.
• The scope rules are designed so that we can only refer to variables that are alive.
The variable must have been stored in the frame of a subroutine.
• Each frame on the stack contains a static link pointing to the frame of the static
parent.
• Subroutine C and D are nested in B (B is static parent of C and D), B in A and E in
A.

27
 Nested Subroutine Scope(Nested Scope)
• Calling a function inside another function
Function1 (int a, int b)
{
int square (int z)
{
return z*z;
}
return square (a) + square (b);
}
• The nested function’s name is local to the block where it is defined.
• Here the defined nested function is square and it calls twice.
• The nested function can access all the variables of the containing function that are visible at the
point of its definition. This is called as lexical scoping.

28
 Declaration Order Scope

• Whether we can use variables in a program before declaring?

• Early languages Algol, lisp – its mandatory to appear all the
declaration in the beginning.
• Pascal – names must be declared before it is used.
• Simplest approach (No declaration order) – Modula-3
• Most of the programming languages like C, C++ , Java – variable
should be declared before it is used for the first time.

29
 Dynamic Scope
• In a language with dynamic scoping, the bindings between names and
objects depend on the flow of control at run time, and in particular on
the order in which subroutines are called.
• Scope cannot be determined until run time ,typically by following stack
frames until a matching declaration is found.
• Each time a subroutine is called , its local variables are pushed on a stack
with their name-to-object binding.
• When a reference to variable is made, the stack is searched top-down for the
variable’s name-to-object binding.
• After the subroutine returns, the binding of the local variable are popped from
the stack.

30
Example

Void swap(int n1, int n2)

{
int temp;
temp=n1;
n1=n2;
N1 10
n2=temp; N2 20
} Temp
Int main()
n1 10
{ N2 20
int n1=10;
int n2=20;
Swap(n1,n2);
Printf(“- - - - “);
} 31
 Storage Management
• Lifetimes
- The term lifetime refers to the interval between creation and destruction.
- Objects lifetime generally mean one of the three primary mechanisms for
allocating storage.they are used to manage the object’s space in memory.

● Types:
1. Static allocation
2. Stack based allocation
3. Heap based allocation

32
 Static Allocation
• Static objects maintain the same(virtual) address throughout program execution.
• Program code is statically allocated in most implementations of imperative
languages.
• Statically allocated variables are history sensitive.
– Global variables
– Static local variable in c Function retain its value even after function returns.
• Advantage:
– Fast access due to absolute addressing of object.
– Faster execution.
• Disadvantage:
– Does not work for local variables in recursive functions.

33
 Temporaries
(for immediate values) Intermediate values

Local variables

Book keeping
(registers) Reference to stack frame,
debugging information
Return address

Arguments

34
 Stack Based Allocation

• It is followed during the execution of subroutine call or a function

call.
• Whenever a function call is initiated a stack frame will be created on
the top of the previously created stack frame.
• Stack grows downwards.
• Whenever the particular subroutine completes its execution , stack
frame will be cleared and the control will given to the main program.

35
• Each instance of a subroutine at run time has its own frame (also called an activation record) on the stack, containing
arguments and return values, local variables, temporaries, and bookkeeping information.

• Compiler generates subroutine calling reference to set up frame, call the routine and to destroy the frame afterwards.

• The frame pointer (fp) points to the frame of the currently active subroutine at run time (always topmost frame on
stack).
• Stack ponter (sp) points to free space on stack.

36
 Heap Based Allocation
• A heap is a region of storage in which subblocks can be allocated and deallocated at arbitrary times.
• Heaps are required for the dynamically allocated pieces of linked data structures, and for objects like fully
general character strings, lists, and sets, whose size may change as a result of an assignment statement or
other update operation.
• Speed and space are the most design constraints of heap.
• Space concerns includes internal and external fragmentation issues
• Internal fragmentation:
- occurs when a storage-management algorithm allocates a block that is larger than required to hold a
given object; the extra space is then unused.

• External fragmentation:
- occurs when the blocks that have been assigned to active objects are scattered through the heap in
such a way that the remaining, unused space is composed of multiple blocks: there may be quite a lot
of free space, but no one piece of it may be large enough to satisfy some future request.

37
Example:
Internal Fragmentation: - due to excessive allocation of memory

M1🡪 0.5 GB
M2 🡪 1.5GB
M3 🡪 2.5GB

1 GB 1GB 1GB 1GB 1GB

1 GB 1 GB 1 GB 1 GB 1 GB
M1 M2
0.5 GB 1.5GB

Un used Un used 38
External Fragmentation:

- due to scattered storage of files

1 GB 1 GB 1 GB 1 GB 1 GB

M11 GB 1GB M2
1GB 1GB 1GB
0.5 GB 1.5GB

39
 Type system & Type checking
Type System:
▪ Computer hardware can interpret the bytes of data in memory in different ways.
▪ Type system consists of,
▪ A mechanism to define types and associate them with certain constructs.

▪ A set of rules for type equivalence , type compatibility and type inference.

40
 Type checking
• Type checking is the process of ensuring that a program obeys the language’s type compatibility rules.
• A violation of the rules is known as a type clash.
• Whenever a language allows a value of one type to be used in a context that expects another, the language
implementation must perform an automatic, implicit conversion to the expected type. This conversion is
called a type coercion.
– Implicit conversion of one data type to another datatype by the compiler to perform a particular
operation is called coercion.
– Explicit conversion done by the programmer is called type casting.
• Type error is the application of an operator to an operand of an appropriate type.
– Eg.
char a,b,c; c=a+b; //type error

41
• Type conversion:
– Implicit 🡪 Type coercion
• conversion is done by compiler
– Explicit 🡪 Type casting
• conversion is done programmer
Type coercion(Implicit):
Example:
double d;
int i;
if(d>i) d=i;
Type casting( Explicit):
Example:
double d1=3.1;
double d2=3.2;
double d3=3.3;
int result=(int)d1+(int)d2+(int)d3; //result=9
42
 Categories of type checking

1. Strongly typed
2. Weakly typed
3. Statically typed
4. Dynamically typed

Strongly Typed:
- Follows strict rules for datatypes
- it checks the types of a variables before performing an operation on it.
- variable are necessarily bound a particular data type.
- Eg. Python, java

43
Weakly Typed:
- No strict rules for data types
- Variables are not bound to a specific datatype.
- Eg. PHP, C
Statically Typed:
- it is strongly typed and type checking can be performed at compile time.
- variables need to be defined before they are used.
-explicit declaration or initialization is required.
-Eg. C,C++,Java
Dynamically Typed:
- It is a form of late binding, type checking is performed in run time.
-do not required the explicit declaration before they are used. i.e; we can use the
variables directly in a expression.
- Eg. Python,Lisp, Small,Perl, Ruby,, PHP, JavaScript.

44
 Equality Testing & Assignment
Assignment:
- ‘=‘ is an assignment operator.
- Assign the value on the right to the variable on the left.
- eg. A=10;
Equality:
- ‘==‘ is a relational/ comparison .
- checks whether the given operands are equal or not.
Equality Testing & Assignment:
• For simple, primitive data types such as integers, floating-point numbers, or characters, equality testing an
straightforward operations, (bit-wise comparison or copy).
• For more complicated or abstract data types – both semantic and implementation has to be considered.

45
• Consider for example
– the problem of comparing two character strings. Should the expression s = t determine whether s and t
• are aliases for one another?
• occupy storage that is bit-wise identical over its full length?
• contain the same sequence of characters?
• would appear the same if printed?
• in the presence of references, should expressions be considered equal only if they refer to the same
object, or also if the objects to which they refer are in some sense equal?
• The first option (refer to the same object) is known as a shallow comparison.
• The second (refer to equal objects) is called a deep comparison.
• For complicated data structures (e.g., lists or graphs) a deep comparison may require recursive
traversal.

46
• In imperative programming languages assignment operations may also be deep or
shallow.
• Under a reference model of variables, a shallow assignment a := b will make a refer
to the object to which b refers.
• A deep assignment will create a copy of the object to which b refers, and
make a refer to the copy.
• Under a value model of variables, a shallow assignment will copy the value
of b into a, but if that value is a pointer (or a record containing pointers), then the
objects to which the pointer(s) refer will not be copied.
• Most programming languages employ both shallow comparisons and
shallow assignment.
47
• A few (notably Python and the various dialects of Lisp) provide more than one
option for comparison. Scheme, for example, has three equality-testing
• functions:
• (eq? a b) (eqv? a b) (equal? a b)
• ;do a and b refer to the same object?
• ;are a and b provably semantically equivalent?
• ;do a and b have the same recursive structure?

48
Subroutines and Control Abstraction
• Function: subroutine that returns a value
• Procedure: subroutine that does not return a value
• Functions /subroutines are made up of sequence of instructions that can receive data, process the
data and return a value.
• Functions performs specific task, it has a name, parameters and a return type.
• Function definition:
Return_type fn_name(arg_list);
Eg: int sum(int);

• Formal Arguments:
The arguments present in the function definition

• Actual Arguments:
- The arguments present in the function call statement.
- These arguments are passed to the formal srguments.
- Parameter passing
Function Overloading:
- process of calling several functions with the same name.
Generic subroutine:
- is one whose computation can be done on different types in different calls
Eg:
templates in C++, generic class in Java
General subprogram characteristics:
• Each sub program has a single entry point.
• The calling program is suspended during the execution of the called sub program,
which implies that there is only one subprogram in execution at any given time.
• Control always return to the caller when the sub program execution terminates.

51
 Sub routine Execution
#include<stdio.h>
int add (int n1, int n2) Stack Frame
{
int s; n1 4
s=n1+n2; Add() n2 5
return s;
s 9
}
void main() num1 4

{ Main() num2 5
int num1,num2,sum=0;
printf(“%d%d”,&num1,&num2); sum 0

sum=add(num1,num2);
printf(“sum=%d”,sum);
}
52
Stack Layout:
• Storage consumed by local variables & parameters can be allocated on
a stack.
• Activation record/ stack frame may contains arguments, its return
address book keeping information local variables & temporaries.
• On return from the subroutine to the main program the stack frame is
popped from the stack.
• The frame pointer (fp) points to a location near the bottom of the
frame
• The stack pointer (sp) points to the first unused location on the stack
• Each stack frame contains a reference to the frame of lexically
surrounding subroutine . This reference is called static link
• The saved value of the frame pointer will be restored on subroutine
return is called dynamic linking

53
 Subroutine Calling Sequence
Every function has three components:
1. Function Prologue
2. Function Body
3. Function Epilogue
Function Prologue:
It is a part of a function, it does all work needed to start up the function.
It begins by reserving space for all local variables and other values on the run time stack.
Function Body:
It’s a implementation part, where all the required works will accomplished.
Function Epilogue:
Clean up the stack frame just before the function is done,and returns to the caller.
- The function prologue will initiate the function execution, the function body will implement the function
and the function epilogue end up the ececution.

54
 • The caller actions are,
1. Create an activation record
2. Save the execution status of the current program unit.
3. computes and pass the parameters.
4. Pass the return address to the called function
5. Transfer control to the called.
• In its prologue, the callee
1. Save the old FP in the stack as the dynamic link & create the new value.
2. Allocate local variables
After the subroutine has completed, the epilogue
1. moves the return value (if any) into a register or a reserved location in the stack
2. restores callee-saves registers if needed
3. restores the fp and the sp 4. jumps back to the return address
Finally, the caller
1. moves the return value to wherever it is needed
2. restores caller-saves registers if needed

55
 In-Line Expansion

• Allows certain subroutines to be expanded in-line at the point of call

• Avoids several overheads (space allocation, branch delays, maintaining static
chain or display, saving and restoring registers)
- Inline function should be defined before the main function
 Implementations of In-line Expansion

• C++ uses keyword inline:

inline int max( … ) { … }

• Ada:
pragma inline (function_name);

• Pragmas make suggestions to the compiler. Compiler can

ignore suggestion.
 Exceptions

• Exceptions are an unexpected or unusual condition that arises

during program execution.
• Most common are various sorts of run-time errors (ex. encountering
the end of a file before reading a requested value)
 Exception Handling
1) Perform some operation that allows the program to recover from the exception and continue
executing.
2)If recovery isn’t possible, handler can print helpful message before termination
3)When exception occurs in block of code but can’t be handled locally, it is important to declare local
handler to clean up resources and then re-raise the exception to propagate back up.
• C++

– Try block
General Form:
– Throw block Try
{
– Catch block If(something_unexpected)
Throw exception;
----
---
}
Catch(type arg)
{

}
 Defining Exceptions

• Ada
declare empty_queue : exception;
• Modula-3
EXCEPTION empty_queue;
• C++ and Java
class empty_queue{};
 Coroutines

• Coroutines are execution contexts that exist concurrently, but execute one at a time, and
each other explicitly, by name.
• They can implement iterators and threads.
 Transfer

• To go from one coroutine to another the run-time system must change the PC, stack,
and register contents. This is handled in the transfer operation.