Transcript clase2

ICOM 4015
Advanced Programming
Lecture 2
Procedural Abstraction
Reading: LNN Chapter 4, 14
Prof. Bienvenido Velez
FALL 2001
ICOM 4015 - Lecture 2
1
Procedural Abstraction
Topics
• Topic 1
– Functions as abstract contracts
– Parameter passing
– Scoping
• Topic 2
– Functional arguments
• Topic 3
– Top-down modular design
– Stepwise refinement
• Topic 4
– Recursive functions
– Recursion vs. Iteration
• Topic 5
– Further procedural abstraction
– Function overloading and templates
FALL 2001
ICOM 4015 - Lecture 2
2
Procedural Abstraction I
Outline
• Functions as abstract contracts
• Value/Reference parameters
• Procedural Abstraction Defined
• Scope Rules
FALL 2001
ICOM 4015 - Lecture 2
3
Example 0
Finding the roots of ax2 +bx + c
#include <cmath>
//
//
//
//
//
roots(a, b, c, r1, r2) - returns the number of
real roots of ax^2 + bx + c. If two roots exists
they are returned is r1 and r2. If only one root
exists, it is returned in r1. Otherwise the value
of r1 and r2 is undetermined.
WHAT?
int roots(float a, float b, float c, float& r1, float& r2)
{
float d = b * b - 4.0 * a * c;
if (d < 0) {
formal
return 0;
parameters
}
r1 = (-b + sqrt(d)) / (2.0 * a);
if (d == 0) {
HOW?
return 1;
}
r2 = (-b - sqrt(d)) / (2.0 * a);
return 2;
}
roots.cc
definitions
int roots(float a, float b, float c,float& r1, float& r2);
roots.h
declarations
FALL 2001
ICOM 4015 - Lecture 2
4
Procedural Abstraction
• A function should accomplish ONE
well defined and easy to remember
task
• A function establishes a contract
between callers and implementers
• The implementer may select any
implementation that satisfies the
contract.
• The contract should specify WHAT
task the function accomplishes,
NOT HOW it accomplishes it
“HOW” is hidden or abstracted out,
hence the name procedural abstraction
FALL 2001
ICOM 4015 - Lecture 2
5
Scope Rules &
Parameter Passing Mechanisms
#include <iostream>
Global in
Module
// Forward definitions
int f(int& x);
// Global definitions
static int x = 0;
int y = 0;
Global
int main() {
for (int i=0; i < 5; i++)
int arg = x;
int r = f(x);
cout << " f(" << arg <<
cout << " Glob x=" << x
cout << " Glob y=" << y
}
}
int f(int& x) {
int y=0;
static int z=0;
y++;
z+=2;
x = y + z;
cout << " Loc x=" << x;
cout << " Loc y=" << y;
cout << " Loc z=" << z;
return z;
}
{
") -> " << r;
<< endl;
<< endl;
[bvelez@amadeus] ~ >> scope1
Loc x=3 Loc y=1 Loc z=2 f(0) -> 2
Loc x=5 Loc y=1 Loc z=4 f(3) -> 4
Loc x=7 Loc y=1 Loc z=6 f(5) -> 6
Loc x=9 Loc y=1 Loc z=8 f(7) -> 8
Loc x=11 Loc y=1 Loc z=10 f(9) ->
[bvelez@amadeus] ~ >>
FALL 2001
Local to
For Loop
Local to
Block
Local to
Function
Glob x=3 Glob y=0
Glob x=5 Glob y=0
Glob x=7 Glob y=0
Glob x=9 Glob y=0
10 Glob x=11 Glob y=0
ICOM 4015 - Lecture 2
6
Diagramas de Bloques
x:
y:
main:
for:
i:
arg:
r:
f:
x:
y:
z:
FALL 2001
ICOM 4015 - Lecture 2
7
Procedural Abstraction I
Summary of Concepts
• Value parameters – changes remain
local to function. Function works
with a copy of the argument.
• Reference parameters – changes
propagate to argument. Function
works with original argument.
• Procedural abstraction – a function
establishes a contract with its callers
on what it accomplishes, hiding how
it accomplishes it.
FALL 2001
ICOM 4015 - Lecture 2
8
Procedural Abstraction I - Scoping
Summary of Concepts II
• Definition: Scope of a declaration
– region of code where declaration is active
• Scope rules allow better control over
the namespace
• Local namespaces (e.g. functions,
blocks) independent of each other
• Local declarations take precedence
over global declarations
FALL 2001
ICOM 4015 - Lecture 2
9
Procedural Abstraction II
Outline
• Procedural arguments
FALL 2001
ICOM 4015 - Lecture 2
10
Integration
Without Procedural Arguments
#include <iostream>
// Forward definitions
double integrateSqr(double a, double b, double n);
double integrateCube(double a, double b, double n);
int main() {
cout << "Integral of x^2 in [0,1] = "
<< integrateSqr(0.0, 1.0, 10000)
<< endl;
cout << "Integral of x^3 in [0,1] = "
<< integrateCube(0.0, 1.0, 10000)
<< endl;
}
double integrateSqr(double a, double b, double n) {
double delta = (b-a) / double(n);
double sum = 0.0;
for (int i=0; i<n; i++) {
float x = a + delta * i;
sum += x * x * delta;
}
return sum;
}
double integrateCube(double a, double b, double n) {
double delta = (b-a) / double(n);
double sum = 0.0;
for (int i=0; i<n; i++) {
float x = a + delta * i;
sum += x * x * x * delta;
}
return sum;
}
[bvelez@amadeus] ~/icom4015/lec05 >> example2
Integral of x^2 in [0,1] = 0.333283
Integral of x^3 in [0,1] = 0.24995
[bvelez@amadeus] ~/icom4015/lec05 >>
FALL 2001
ICOM 4015 - Lecture 2
11
Example 3 Integration
With Procedural Arguments
#include <iostream>
// Forward definitions
double integrate(double a, double b, double n,
double f(double x));
double cube(double x);
double sqr(double x);
int main() {
cout << "Integral of x^2 in [0,1] = "
<< integrate(0.0, 1.0, 10000, sqr)
<< endl;
cout << "Integral of x^3 in [0,1] = "
<< integrate(0.0, 1.0, 10000, cube)
<< endl;
}
double integrate(double a, double b, double n,
double f(double x)) {
double delta = (b-a) / double(n);
double sum = 0.0;
for (int i=0; i<n; i++) {
sum += f(a + delta * i) * delta;
} return sum;
}
double cube(double x) {
return x * x * x;
}
double sqr(double x) {
return x * x;
}
[bvelez@amadeus] ~/icom4015/lec05 >> example2
Integral of x^2 in [0,1] = 0.333283
Integral of x^3 in [0,1] = 0.24995
FALL 2001
ICOM 4015 - Lecture 2
[bvelez@amadeus] ~/icom4015/lec05 >>
12
Procedural Abstraction II
Functional Arguments
Summary of Concepts
• Functional arguments
– Allow abstraction over processes
and functions
FALL 2001
ICOM 4015 - Lecture 2
13
Procedural Abstraction III
Outline
• Top-down stepwise refinement
FALL 2001
ICOM 4015 - Lecture 2
14
Step 0 - Outline
//
//
//
//
//
top-down.cc
Computes weighted average score of grades. Grades
include two assignments two midterm exams and one final exam.
All grades are input from standard input, but the weights of
each type of grade are hard coded.
// C header files
extern "C" {
}
// Standard C++ header files
#include <iostream>
// My own C++ header files
// Macro definitions
// Forward definitions of auxiliary functions
// Global declarations
// Main function
int main() {
// Read assignment grades
// Read exam grades
// Read final exam grade
// Calculate average
// Print report
return 0;
}
// Auxiliary functions
FALL 2001
ICOM 4015 - Lecture 2
15
Step 1 – Code + Stubs
int main() {
float assignment1, assignment2;
float exam1, exam2;
float finalExam;
readAssignmentGrades(assignment1, assignment2);
readExamGrades(exam1, exam2);
readFinalGrade(finalExam);
float avg;
avg = calculateAverage(assignment1, assignment2,
exam1, exam2,
finalExam);
printReport(assignment1, assignment2,
exam1, exam2,
finalExam,
avg);
return 0;
}
// Auxiliary functions
void readAssignmentGrades(float& assignment1, float& assignment2)
{}
void readExamGrades(float& ex1, float& ex2)
{}
void readFinalGrade(float& final)
{}
float calculateAverage(float assignment1, float assignment2,
float exam1, float exam2,
float finalExam)
{}
void printReport(float assignment1, float assignment2,
float exam1, float exam2,
float finalExam,
float average)
{}
FALL 2001
ICOM 4015 - Lecture 2
16
Step 2 - Refine
// Auxiliary functions
void readAssignmentGrades(float& assignment1, float& assignment2)
{
// Read a float in [0,100] into assignment1
// Read a float in [0,100] into assignment2
}
void readExamGrades(float& ex1, float& ex2)
{
// Read a float in [0,100] into ex1
// Read a float in [0,100] into ex2
}
void readFinalGrade(float& final)
{
// Read a float in [0,100] into final
}
float calculateAverage(float assignment1, float assignment2,
float exam1, float exam2,
float finalExam)
{
// Calculate assignments average
// Calculate exams average
// Calculate weighted average
}
void printReport(float assignment1, float assignment2,
float exam1, float exam2,
float finalExam,
float average)
{
// print assignment grades
// print exam grades
// print final exam grades
// print weighted average
}
FALL 2001
ICOM 4015 - Lecture 2
17
Top-down stepwise
refinement cycle
outline
refine
code
+
stubs
FALL 2001
ICOM 4015 - Lecture 2
18
Procedural Abstraction III
Top-down design – Stepwise Refinement
Summary of Concepts
• Top-Down design / stepwise
refinement
– A cyclic development technique
– Each cycle adds a level of detail
to the code
– We have a functioning (although
incomplete) program after every
iteration of the process
FALL 2001
ICOM 4015 - Lecture 2
19
Procedural Abstraction IV
Outline
• Recursive Functions
– Activation records, call stacks
– Expressiveness of recursion vs.
iteration
– Efficiency concerns
• function call overhead
• duplication of work
• process complexity
FALL 2001
ICOM 4015 - Lecture 2
20
Example 0
Factorials
// factorials.cc
// Implements recursive and interative versions of algorithms for
// computing the factorial (N!) of a number.
// Standard C++ header files
#include <iostream>
// Forward definitions of auxiliary functions
long recFactorial(long n);
long iterFactorial(long n);
int main()
{
long number;
while(true) {
cout << "Please enter a positive number (or negative to end): ";
cin >> number;
if (number < 0) return 0;
cout << "Recursive: " << number << "! = " << recFactorial(number) << endl;
cout << "Iterative: " << number << "! = " << iterFactorial(number) << endl;
}
}
long recFactorial(long n)
{
if (n==0) {
return 1;
}
else {
return (n * recFactorial(n - 1));
}
}
[bvelez@amadeus] ~/icom4015/lec07 >>factorials
Please enter a positive number (or negative to end):
long iterFactorial(long n)
Recursive: 3! = 6
{
Iterative: 3! = 6
long product = 1;
Please enter a positive number (or negative to end):
for (long i=1; i<=n; i++) {Recursive: 4! = 24
product *= i;
Iterative: 4! = 24
}
Please enter a positive number (or negative to end):
return product;
Recursive: 5! = 120
}
Iterative: 5! = 120
Please enter a positive number (or negative to end):
Recursive: 6! = 720
Iterative: 6! = 720
FALL 2001
ICOM 4015 - Lecture 2
21
Please enter a positive number (or negative to end):
[bvelez@amadeus] ~/icom4015/lec07 >>fibonacci
3
4
5
6
-1
Example 1
Fibonacci Numbers
// fibonacci.cc
// Iterative and recursive algorithms for computing Fibonacci numbers
...
// Auxiliary Functions
long recFibonacci(long n)
{
if (n==0) {
return 0;
}
else if (n==1) {
return 1;
}
else {
return (recFibonacci(n-1) + recFibonacci(n-2));
}
}
long iterFibonacci(long n)
{
if (n==0) {
return 0;
}
else if (n==1) {
return 1;
}
long F0 = 0;
long F1 = 1;
long FN;
for (long i=1; i<n; i++) {
FN = F0 + F1; F0 = F1; F1 = FN;
}
return FN;
}
[bvelez@amadeus] ~/icom4015/lec07 >>fibonacci
Please enter a positive number (or negative to
Recursive: F(3) = 2
Iterative: F(3) = 2
Please enter a positive number (or negative to
Recursive: F(4) = 3
Iterative: F(4) = 3
Please enter a positive number (or negative to
FALL 2001
ICOM 4015 - Lecture 2
Recursive: F(8) = 21
Iterative: F(8) = 21
Please enter a positive number (or negative to
end): 3
end): 4
end): 8
end):
22
Example 1
Fibonacci Numbers
// fibonacci.cc
// Iterative and recursive algorithms for computing Fibonacci numbers
// Standard C++ header files
#include <iostream>
// Forward definitions of auxiliary functions
long recFibonacci(long n);
long iterFibonacci(long n);
int main()
{
long number;
while(true) {
cout << "Please enter a positive number (or negative to end): ";
cin >> number;
if (number < 0) return 0;
cout << "Recursive: F(" << number << ") = "
<< recFibonacci(number) << endl;
cout << "Iterative: F(" << number << ") = "
<< iterFibonacci(number) << endl;
}
}
…
…
...
FALL 2001
ICOM 4015 - Lecture 2
23
Procedural Abstraction IV
Iteration vs. Recursion
Summary of Concepts
• Recursion is as expressive as iteration
• Iteration can yield faster code
– less duplication of work
– less function call overhead
• Recursion can yield cleaner code
– may rely on a “smart” optimizing compiler
to minimize call overhead
FALL 2001
ICOM 4015 - Lecture 2
24
Procedural Abstraction V
Outline
• Further procedural abstraction
– Function overloading
– Function templates
FALL 2001
ICOM 4015 - Lecture 2
25
Function Overloading
SQR Function Family
int intSqr (int x)
{
return x * x
}
long longSqr(long x)
{
return x * x;
}
Without
overloading
float floatSqr(float x)
{
return x * x
}
int sqr (int x)
{
return x * x
}
long sqr(long x)
{
return x * x;
}
With
overloading
float sqr(float x)
{
return x * x
}
FALL 2001
ICOM 4015 - Lecture 2
26
Function Templates
SQR Function Family
int sqr (int x)
{
return x * x
}
long sqr(long x)
{
return x * x;
}
With
overloading
float sqr(float x)
{
return x * x
}
template <class T>
T sqr (T x)
{
return x * x
}
FALL 2001
With
templates
ICOM 4015 - Lecture 2
27
SQR’aring different types
// Standard C++ header files
#include <iostream>
#include <iomanip>
// Forward definitions of local auxiliary functions
template <class T> T sqr(T x);
// Main function
int main()
{
cout << "
i"
<< "
sqr(i)"
<< " sqr(float(i))"
<< " sqr(double(i))"
<< endl;
for (int i=0; i<10; i++) {
cout << setw(16) << i
<< setw(16) << sqr(i)
<< setw(16) << sqr(float(i))
<< setw(16) << sqr(double(i))
<< endl;
}
}
// Local auxiliary functions
template <class T>
T sqr(T x) {
return x * x;
}
Templates can reduce code duplication dramatically
FALL 2001
ICOM 4015 - Lecture 2
28
Output
[bvelez@amadeus] ~/icom4015/lec09 >>sqr
i
sqr(i)
sqr(float(i))
0
0
0
1
1
1
2
4
4
3
9
9
4
16
16
5
25
25
6
36
36
7
49
49
8
64
64
9
81
81
[bvelez@amadeus] ~/icom4015/lec09 >>
FALL 2001
ICOM 4015 - Lecture 2
sqr(double(i))
0
1
4
9
16
25
36
49
64
81
29
Anatomy of a Function
Template
T is a
type
parameter
template <class T> function
Inside this function
T represents any type
Templates are C++’s implementation of
Parametric Polymorphism
FALL 2001
ICOM 4015 - Lecture 2
30
Example 2
// Standard C++ header files
#include <iostream>
#include <iomanip>
// Forward definitions of local auxiliary functions
template <class T> void swap(T& a, T& b);
template <class T> void doSwap(T a, T b);
// Main function
int main()
{
cout << "***** doSwap(1,0)" << endl;
doSwap(1,0);
cout << endl << endl << "***** doSwap(1.0/3.0, 2.0/3.0)"
<< endl;
doSwap(1.0/3.0, 2.0/3.0);
cout << endl << endl << "***** doSwap(true, false)" <<
endl;
doSwap("hello", "world");
}
// Local auxiliary functions
template <class T>
void doSwap(T a, T b)
{
T x = a;
T y = b;
cout << "x = " << x << " y = " << y << endl;
swap(x,y); cout << "swap(x,y)" << endl;
cout << "x = " << x << " y = " << y << endl;
swap(x,y); cout << "swap(x,y)" << endl;
cout << "x = " << x << " y = " << y << endl;
}
template <class T>
void swap(T& a, T& b)
{
T temp = a;
a = b;
b =2001
temp;
FALL
ICOM 4015 - Lecture 2
}
Variable declaration
of type T 31
Example 2 Output
[bvelez@amadeus] ~/icom4015/lec09 >>swap
***** doSwap(1,0)
x = 1 y = 0
swap(x,y)
x = 0 y = 1
swap(x,y)
x = 1 y = 0
***** doSwap(1.0/3.0, 2.0/3.0)
x = 0.333333 y = 0.666667
swap(x,y)
x = 0.666667 y = 0.333333
swap(x,y)
x = 0.333333 y = 0.666667
***** doSwap(true, false)
x = hello y = world
swap(x,y)
x = world y = hello
swap(x,y)
x = hello y = world
FALL 2001
ICOM 4015 - Lecture 2
32
Procedural Abstraction V
Function Overloading
Summary of Concepts
• Related functions can be
grouped under a common name
• Overloaded functions may have
different return types, but must
have different parameters.
• The importance of overloading
will become clearer when we
get into classes and objectoriented programming
FALL 2001
ICOM 4015 - Lecture 2
33
Procedural Abstraction V
Function Templates
Summary of Concepts
• Programmer declares one
function parameterized over
some type T
• Compiler instantiates
potentially many functions for
all the different argument types
provided among all function
calls
• Instances must be well typed,
that is, all objects should only
be used according to their types.
FALL 2001
ICOM 4015 - Lecture 2
34