Transcript Programming Paradigms

IT 240
Programming Paradigms
MS Information Technology
Ateneo de Davao
Course Outline
Programming Language Concepts
Survey of Languages and Paradigms
Imperative, Functional, Object-Oriented
Focus: OO Programming
OO Languages (Java and C++)
OO Design (UML)
Design Patterns
Prerequisites and Context
IT 240: One of the six required (core)
courses in the MS IT curriculum
Assumes sufficient exposure (at least two
semesters) to programming
preferably in the C Language
undergraduate courses in data structures
and/or programming languages will be helpful
References
Programming Language Concepts, by
Ghezzi and Jazayeri
Concepts of Programming Languages, by
Sebesta
The C++ Programming Language, by
Stroustrup
Course Requirements
Midterm Exam
Final Exam
Exercises/Projects
Individual Report
25%
25%
30%
20%
Schedule
Session 1: Overview,
Imperative Prog (November)
Session 2: Functional Prog (December)
Midterm
Session 3: OO Programming (January)
Session 4: More OOP, Reports (February)
Final Exam
Schedule This Weekend
Friday Afternoon
Overview, Classification of Languages
Saturday Morning
Evolution from Imperative/Structured
Programming to OO Programming
Saturday Afternoon
Syntax and Semantics, Language Translation
Concepts in Imperative Programming
Revised Schedule This
Weekend
Saturday Afternoon Session 1:
Overview, Classification of Languages
Evolution from Imperative/Structured Programming
to OO Programming
Saturday Afternoon/Evening Session 2:
Syntax and Semantics, Language Translation
Concepts in Imperative Programming
Sunday Morning session
Imperative Programming, continued
Introduction to Java (time permitting)
Session Format
Lecture
discussion of formal definitions, concepts
and cases
Lab
implementation of examples discussed
exercises to be submitted
Objective: gain working knowledge of the
topics discussed
Course Material and
Required Reading
Visit course website regularly:
http://curry.ateneo.net/~jpv/courses.html
will link to a page containing IT 240 material
Read:
Stroustrup book: section on Programming
Paradigms (sec. 1.2, pp. 14-22)
Overview of
Programming Paradigms
IT 240
Definitions
Programming Paradigm
programming “technique” (?)
way of thinking about programming
view of a program
Programming Language
consists of words, symbols, and rules for
writing a program
Programming Paradigms
Imperative Programming
program as a collection of statements and
procedures affecting data (variables)
Object-Oriented Programming
program as a collection of classes for
interacting objects
Functional Programming
program as a collection of (math) functions
Others
Some Languages by
Paradigm
Imperative (also called Structured or
Procedural) Programming
FORTRAN, BASIC, COBOL, Pascal, C
Object-Oriented Programming
SmallTalk, C++, Java
Functional Programming
LISP, ML, Haskell
History of Languages
1950s to 1960s
FORTRAN, COBOL, LISP, BASIC
1960s to 1970s
(ALGOL-based) Pascal and others
1970s to 1980s
Prolog, C, Ada
1980s to 1990s
C++, ML, Perl, Java
Paradigm Change
For example, from Structured to ObjectOriented
Arises from problems encountered in one
paradigm but addressed in another
Case study: from C to C++
Evolution from structured, to modular, to
object-based, to object-oriented programming
Stroustrup book section 1.2
Case Study: Stacks
Stack
last-in, first-out structure
operations: push, pop
Sample uses ?
Stacks are used to support some solution
push and pop are defined and implemented
as functions
the solution consists of code that invoke
these functions
Implementing a Stack
Stack can be implemented as an array
array contains pushed elements
an integer refers to top of the stack
most common implementation
Or as a linked list
using pointers and dynamic allocation
Other implementations
Array Implementation in C
char Store[MAX];
int top = 0;
void push(char x)
{
if (top < MAX)
Store[top++] = x;
else
printf(“full\n”);
}
char pop()
{
if (top > 0)
return Store[--top];
else
printf(“empty\n”);
}
...
Using the Stack
void application()
{
…
push(‘x’);
…
result = pop();
…
}
Procedural Programming
Focus is on writing good functions and
procedures
use the most appropriate implementation
and employ correct efficient algorithms
Stack example (assume array implementation)
one source file
Store and top are global variables
stack and application functions defined at the
same level (file)
Problems
Application can alter implementation
details
can directly manipulate top and Store from
application()
integrity of stack not ensured
Stack code and application code are not
separated
Encapsulation and
Modular Programming
Focus is on writing good modules
hide implementation details from user
provide an interface
Stack example
stack.h contains prototypes for push, pop
stack.c contains stack code, Store and top
declared static (local to stack.c)
application includes stack.h
Benefits from Modules
Application cannot destroy the integrity of
the stack
Stack implementation can change without
affecting application source
Question: what happens if we need more
than one stack?
Multiple Stacks
Strategy 1 (use structs)
in stack.h, define a stack structure that
contains Store and top; push, pop now have
an extra parameter that specifies which stack
application code defines stack variables
Strategy 2 (use handles)
implement multiple data structures in stack.c
use an integer (the handle) to specify “stack
number”
Modules and
Multiple Stacks
Disadvantage of strategy 1:
implementation (data) is exposed
back to original problem on stack integrity
Disadvantage of strategy 2:
stack module will be unnecessarily complex
handle is artificial (what if an arbitrary
integer is passed?)
Abstract Data Types and
Object-based Programming
Focus is on writing good classes (or
types) that define operations on objects of
the class
class defined like a module (encapsulation
enforced) but multiple instances now possible
user-defined type
Stack example (C++)
stack.h and stack.cpp define a stack class
Object-Oriented
Programming
Incorporates both encapsulation and
inheritance through the class concept
Focus is on writing good classes and on
code reuse
Examples
Shape, Circle, and Rectangle in a drawing
program
Employee, Faculty, Staff in a university
personnel system
Lab Exercises (Set 1)
Modular Programming
create a stack module
Multiple stacks
create a multiple-stack module using
structs
create a multiple-stack module using handles
Object-based Programming
create a stack class in C++
Syntax and Semantics
IT 240
Outline
Language Definition
syntactic vs semantic rules
Translation & Language Processing
Compilation
stages
handout
Language Definition
Syntax
set of rules that define form
BNF Grammar or syntax diagram
Semantics
specify meaning of well-formed programs
formal semantics: pre- and post- conditions
Specifying Syntax
Lexical Rules
rules for determining tokens
tokens: syntactic units (e.g., number,
identifier, semicolon, equals)
Syntactic Rules
Grammar: set of productions
productions: terminals (tokens) and
nonterminals
Semantics
Given a language construct
what is required for that (well-formed)
construct to execute?
what happens upon execution?
Example: assignment statement
tokens present? syntax? semantics?
Language Translation
Interpreters
processes instructions on the fly
Compilers
produces object code for execution
Intermediate code
e.g., pcode or the Java Virtual Machine
Compilation Stages
Lexical Analysis
Parsing (Syntax Analysis)
Code Generation
Code Optimization
* Symbol Table Management
Handout
For the sample program, simulate
compilation and describe effect for each
compilation stage
Lab exercise (Set 2)
Simple exercise on Lexical Analysis,
Parsing, and Symbol table management
Parser for variable declarations (C & Pascal)
Output: list of variables per data type
Imperative Programming
IT 240
Imperative Programming
Variables, assignment, sequencing,
iteration, procedures as units
State-based, assignment-oriented
Global variables, side effects
Program units: Data (Variables) and
Computation (Statements and Routines)
Data and Computation
Binding
Data
Variables
Data types
Computation
Assignments and expressions
Control structures
Subprograms / routines
Binding
Program units/entities have attributes
e.g., a variable has a name, a statement has
associated actions
Binding
setting the value of an attribute
Binding time
when binding occurs
Binding Time
Language definition time
Language implementation time
Compile-time
Execution-time
Examples?
Variable
A named location in memory that can
hold a value
Formally, a 5-tuple:
name
scope
type
l-value
r-value
Name and Scope
Declaration
Identifier rules and significant characters
Scope
range of instructions over which variable
name is known
namespaces
Blocks (as in Pascal or C)
Static vs dynamic scope binding
Type
Consists of
Set of values
Operations
Built-in/Primitive vs User-defined types
binding?
Implicit declarations
e.g., FORTRAN and first letter of a variable and first
assignment in BASIC or Foxpro
Dynamic typing
Why Use Data Types?
Purpose: classification and protection
note that all data are ultimately represented
as bit-strings
Advantages:
abstraction
compile-time checking and resolution
explicit specification
Complex Data Types
User-defined enumeration types
Composite types
Aggregations
cartesian product (records or structures)
mapping (arrays)
unions
L-value and r-value
l-value: address/location
lifetime
memory allocation
r-value: contents/encoded value
initialization
constants
* binding
Pointers
Attributes
Allocation and de-allocation
Operators
referencing (address-of)
de-referencing
Unnamed Variables
e.g., Pascal
Control:
Statements and Routines
Expressions and statements
Conditional execution
Iteration
Routines
Parameter Passing
Modules and Program Structure
Expressions and
Statements
Operands: variables, literals
Operators
Unary, binary, and others (functions?)
Value returned vs effect
Precedence
Statements
The semicolon: C (terminator) vs Pascal (separator)
Blocks: C { } vs Pascal (begin-end)
Control structures: decision, iteration, routines
Conditional Execution
Conditions and boolean values
Relationship of conditions and int in C
Not adopted in Java
Short-cutting
If-statements and dangling else
The switch statement
Restrictions
The break; statement
Iteration
For statement
Loop control variable
The while loop
while vs do-while
do-while versus repeat-until
Iteration using goto
Routines
Program unit; sequence of instructions
Also a 5-tuple:
name
scope
type
l-value
r-value
About Routines
Functions vs procedures
(methods?)
Parameter Passing
By value
By reference
Others?
Activation Records
Recursion
Modules and
Program Structure
Programming in the Large
need to compose program through units
Modules
program units that interact with each
another
Encapsulation
information hiding
independent modules with interfaces
Modularity
Interface and Implementation
Compilation
Independent
Separate
Libraries