CSE 216
PROGRAMMING ABSTRACTIONS Dr. Ritwik Banerjee Computer Science, Stony Brook University
Overview of topics
Programming paradigms
Functional programming
Object-oriented design and programming
Cross-cutting concepts
Parallel Programming
scopes
bindings parameter passing type systems
recursion
higher-order procedures streams and lazy evaluation
abstraction and encapsulation class hierarchy
polymorphism and inheritance object-oriented design principles
multi-paradigm programming unit testing
integration testing
multithreading
© 2019 Ritwik Banerjee
Abstraction
• Mostprogramminglanguagesarehigh-level languages, where the phrase “high-level” indicates a higher degree of abstraction.
• Thesecondwordofthiscourse’sname– abstraction – is among the most important ideas in programming.
• Itreferstothedegreetowhichthelanguage’s features are separated away from the details of a particular computer’s architecture and/or implementation at lower levels.
Java, Python, Ruby
C, Fortran, Pascal
Assembly Language
Machine Language
Hardware
© 2019 Ritwik Banerjee
Programming Paradigms
“An example that serves as pattern or model.”
~ The American Heritage Dictionary of the English Language
• We can think of a paradigm as a ‘school of thought’ in the world of programming.
• Programming paradigms are a way to classify languages based on their features.
It’s a fuzzy classification – a language may belong to multiple paradigms.
A particular programming language may make it very easy to write in one paradigm, but not in another.
© 2019 Ritwik Banerjee
Most programming languages support multiple paradigms, even though they may stress on one paradigm more than others.
PROGRAMMING PARADIGMS
Imperative
Declarative
Constraint
Procedural
Object- Oriented
Functional
Logic
Dataflow
Reactive
COBOL FORTRAN C
Smalltalk Java OCaML
Haskell Scheme ML
Prolog
Mathematica Prolog
Imperative Programming
Think of imperative programming as a “recipe”, where each step is an instruction about how to perform the next action, and the next action depends on the current “state” of your kitchen!
With the exception of reconfigurable computing (e.g., FPGAs), the hardware implementation of all computers is imperative, i.e., “what” to do is described in terms of “how” to do it.
This is because the hardware is designed to execute machine code, which is written in imperative style.
(Relatively) higher- level imperative languages like C are abstractions of assembly language, but they follow the same paradigm.
© 2019 Ritwik Banerjee
Imperative Programming
• Astatementisasyntacticunitofanimperative programming language that expresses some action to be carried out.
The program as a whole in such a language thus becomes a sequence of statements.
assert(x == 7); x = 2 + 3;
2 + 3;
puts(“hello world”); goto label;
return 0;
/* assertion statement; programmer assumes the value of x to be 7 after this line */
/* assignment statement */
/* has no effect; smart compilers will discard
this line */
/* a function call */ /* a goto statement */ /* a return statement */
x = sqrt(2); /* an assignment statement containing a function call */
Simple Statements
© 2019 Ritwik Banerjee
Imperative Programming
• Anassignmentstatementperformsanoperationon information located in memory and stores the results in memory for later use.
Higher-level imperative languages permit evaluation of complex expressions that may consist of a combination of arithmetic operations and function evaluations.
assert(x == 7); x = 2 + 3;
2 + 3;
puts(“hello world”); goto label;
return 0;
/* assertion statement; programmer assumes the value of x to be 7 after this line */
/* assignment statement */
/* has no effect; smart compilers will discard
this line */
/* a function call */ /* a goto statement */ /* a return statement */
x = sqrt(2); /* an assignment statement containing a function call */
Simple Statements
© 2019 Ritwik Banerjee
Imperative Programming
• Aconditionalstatementallowsasequenceofstatements(knownasablock
or a code block) to be executed only if some condition is met.
• Otherwise,thestatementsareskippedandtheexecutionsequencecontinues from the statement following them.
if (happy) { smile();
} else if (sad) { frown();
} else { stoic();
}
switch (i % 2) case 0:
type =
break; default:
type =
break; }
{ EVEN;
ODD;
/* equiv. to case 1 */
© 2019 Ritwik Banerjee
Compound Statements
Imperative Programming
• Loopingstatementsallowablocktobeexecutedmultipletimes.
• Loopscanexecuteablockapredefinednumberoftimes,ortheycanexecute them repeatedly until some condition changes.
while ((c = getchar()) != EOF) { putchar(c);
}
do {
computation(i);
++i;
} while (i < 10);
for (i = 1; i < n; i *= 2) { printf("%d\n", i);
}
© 2019 Ritwik Banerjee
Compound Statements
Procedural Programming
A type of imperative programming based on the concept of procedure calls (COBOL, Fortran, C, Pascal).
Procedures (a.k.a. routines, subroutines, or functions), simply contain a series of computational steps to be carried out.
• That is, they define “how” to do what they are being asked to do. They explicitly refer to the underlying state (i.e., variables and their values), and are therefore within the ambit of imperative programming.
• Any procedure might be called at any point during a program’s execution. The call may come from other procedures or even itself.
© 2019 Ritwik Banerjee
Object Oriented Programming
A paradigm based on the concept of objects, which may contain
• data in the form of fields, sometimes called attributes, and
• code in the form of procedures, a.k.a. methods.
An object’s procedures can access and often modify the data of the object with which they are associated (using this or self).
In OOP, programs are designed by making them out of objects that interact with one another.
• Most OOP languages are class-based, i.e., objects are instances of classes (usually, this determines their type).
© 2019 Ritwik Banerjee
Object Oriented programming
They have features carried over from older non-OOP languages.
• Variables that can store information formatted in a small number of built-in data types like integers and characters.
• This may include data structures like strings, lists, and hash tables. These structures are either built-in, or result from combining built-in structures using internal pointers.
• Procedures that take input, generate output, and may manipulate data.
• For ease of organization, procedures and variables are usually grouped into files and modules with namespaces.
• This is called modular programming. It is a software design principle, not a programming paradigm.
© 2019 Ritwik Banerjee
Objects and Classes
A class comprises the definitions for the data format and available procedures for a given type of object.
An object is an instance of a class.
Source: Pluke [CC0], from Wikimedia Commons
In class-based OOP languages, classes are defined beforehand and
the objects are instantiated based on the classes.
Given an object, a programmer can safely assume all the properties of the class to which the object belongs.
Object-Oriented Programming
Prototype-based programming
• Alsoknownasinstance-basedorclassless (as opposed to ‘class-based’) programming.
• Here,objectsaretheprimaryentities. Classes don’t even exist!
• Everyobjecthasone,andonlyone, prototype.
New objects are created using a pre-existing object as their prototype.
• Aprogrammermaythinkoftwodifferent objects (say, apple and orange) as types of fruit (if the fruit object exists). In this case, both objects have fruit as their prototype.
Thus, the idea of a fruit class is implicitly present in the prototype object.
The attributes and methods of the prototype are delegated to all objects defined by it.
Object-Oriented Programming
Dispatching and message passing
• Itistheresponsibilityoftheobject(andnot any external code) to select the procedure to execute in response to a method call.
This is typically done at runtime by looking up the method in a table associated with the object.
This is known as dynamic dispatch.
It is different from abstract data type (ADT) you studied in CSE 214. In ADT, you have a fixed implementation of the operations for all instances.
If the choice of the procedure depends on more than one attribute of the object, it is called multiple dispatch.
• Themethodcallisalsosometimescalled message passing because people think of it as a message being passed to the object for dispatch.
Object-Oriented Programming
Object-Oriented Programming
Encapsulation
OOP languages usually provide ways to do the following:
a) restrict access to some of the object’s components (attributes and/or methods)
b) bundle the data with the methods operating on that data
• Either(a)or(b)oracombinationof the two is known as encapsulation.
• Often,(a)justbyitselfisknownas information hiding.
What could happen if name is not private?
public class Person { private String name;
public Person(String name) { this.name = name; } public String getName() { return name; }
}
© 2019 Ritwik Banerjee
Object-Oriented Programming
Polymorphism is a concept that refers to the ability of an entity to take on multiple forms.
class Animal {
public void move() { /* no implementation */ }
}
class Horse extends Animal { public void move() { gallop(); }
}
class Bird extends Animal { public void move() { fly(); }
}
class AnimalPolymorphism {
public static void main(String[] args) {
Animal a1 = new Animal(); Animal a2 = new Bird(); Animal a3 = new Horse();
a1.move(); a2.move(); a3.move();
} }
© 2019 Ritwik Banerjee
Object-Oriented Programming
Inheritance is the mechanism of basing an object (or class) upon another object (or class) retaining similar implementation.
• In some OOP languages, subclasses inherit the features of one superclass. This is known as single inheritance.
• If one class can have more than one superclass and inherit features from multiple parent classes, it is known as multiple inheritance.
© 2019 Ritwik Banerjee
Comparison
PROCEDURAL
• Focusisonbreakingdownaprogram into a collection of variables, data structures, and subroutines.
• Reliesheavilyonblocksandscope.
• Usesreservedtermslikeif,while,for, etc. to implement the order in which a program’s instructions are executed and evaluated.
OBJECT-ORIENTED
• Focusisonbreakingdownaprogram into objects that expose some specific behavior (through methods) and data (through attributes) using interfaces.
© 2019 Ritwik Banerjee
Declarative Programming
In declarative programming, we describe the logic of the program without specifying the order in which a program’s instructions are executed and evaluated.
Commonly, we say that declarative programming is about “what” to do, without specifying “how” to do it.
Of course, the computer needs
to be told how to do something at some point!
• But with declarative programming, those details are left to the language’s implementation.
• There is a decoupling of ‘what’ and ‘how’, which makes life easier for the developer.
• In that sense, they are “higher level” languages.
© 2019 Ritwik Banerjee
Declarative Programming
Describes what a computation must do
Database Query Languages. (e.g., SQL – used in relational database management)
Has a clear correspondence with mathematical logic
Logic Programming (e.g., Prolog – used in various AI applications for logical reasoning)
No “side effects”
Functional Programming (e.g., Haskell – used in financial computing, AI, and process automation)
© 2019 Ritwik Banerjee
A comparison in the real world
I am right outside the main entrance of the New CS Bldg. How do I get to your office from here?
Imperative Declarative
1. Take the first right turn, walk to the end of the corridor, and take the flight of stairs to the second floor. Then turn left, cross 5 doors on your right. The 6th door is my office.
2. Take the first flight of stairs after room 120 on your left. Exit the stairs on the second floor and ... .
• My office is Room 206.
© 2019 Ritwik Banerjee
Logic and/or constraint- based programming
• Basedonpredicatelogicandanaxiomaticwayof finding solutions.
• Thegoalisoftentofindspecificrelationshipsthatare true, starting with basic relations that are always true. Such a basic truth is called an axiom.
• Perhapsthebestknownlogicprogramminglanguage is Prolog.
• Theselanguagesareoftenusedtomodelconstraints. For example,
find the value of an integer variable x under the constraint that it is different from the value of another integer variable y and that it must be a strictly positive integer
© 2019 Ritwik Banerjee
Dataflow Programming
• Computationismodeledasa‘flowofinformation’– as a directed graph – between different operations.
• Explicitlydefinedinputandoutputconnectthe operations.
In that sense, dataflow programming shares some features of functional programming.
Each operation can be though of as a ‘black box’ function.
A traditional sequential program is like a worker moving around between tasks in a specific order called the control flow.
A dataflow program is like an assembly line where a worker carries out a task whenever all the inputs are available. Other workers may, in parallel, carry out other tasks as long as they don’t hinder each other.
This paradigm is often very useful in parallel programming.
© 2019 Ritwik Banerjee
Reactive Programming
• A declarative, dataflow programming paradigm where it becomes very easy to propagate changes in data.
• As an overly simplistic idea, consider a statement such as x = y + z
In traditional imperative programming, the x is assigned the sum of the values of y and z. If the value(s) of y and/or z changes later, the value of x is not affected.
In reactive programming, the value of x is automatically updated whenever y and/or z change.
• Reactive programming is extremely useful in interactive applications, and is often used in the model-view-controller (MVC) architecture.
Not within the scope of our syllabus
© 2019 Ritwik Banerjee
Functional Programming
1
Based on recursive definitions.
•They are inspired by a computational model called lambda calculus, developed by Alonzo Church in the 1930s.
2
A program is viewed as a mathematical function that transforms an input to an output. It is often defined in terms of simpler functions.
•We will see many examples of functional programming in multiple languages (e.g., Java, Python, OCaML).
© 2019 Ritwik Banerjee
One Problem. One pseudocode. Three paradigms.
Implementing the greatest common divisor (GCD) solution in different paradigms and different languages.
The pseudocode
function gcd(a, b) while a ≠ b
if a > b
a := a − b;
else
b := b − a; return a;
© 2019 Ritwik Banerjee
Three paradigms
1. Imperative programming in C
To compute the gcd of a and b:
1. check if a and b are equal
2. if they are, then print a and stop
3. otherwise, replace the larger number by their difference and repeat steps 1 and 2
© 2019 Ritwik Banerjee
Three paradigms
2. Functional programming in ML
To compute the gcd of a and b:
1. check if a and b are equal
2. if they are, then print a and stop
3. otherwise, replace a by the absolute value of their difference and recursively compute the gcd of this new pair
© 2019 Ritwik Banerjee
Three paradigms
3. Logic programming in Prolog
The proposition gcd(a,b,g) is true if
1) a, b, and g are all equal, or
2) a > b and there exists a number c such that c is a-b and gcd(a,b,g) is true, or
3) b > a and there exists a number c such that c is b-a and gcd(a,b,g) is true.
To compute the greatest common divisor of a and b, search for a number g for which the above rules prove that gcd(a,b,g) is true.
© 2019 Ritwik Banerjee