Transcript Constructs for Data Organization and Program Control, Scope

Constructs for Data
Organization and Program
Control, Scope, Binding, and
Parameter Passing.
Expression Evaluation
Constructs for Data Organization
 Data Structures: Used to implement a
collection of objects.




Arrays
Linked Lists
Stacks
Recursion
Recall: Asymptotic Analysis –
Big (O)
 As a programmer, you often have a choice
of data structures and algorithms.
Choosing involves two factors
 Time Complexity: how much time
 Space Complexity: how much storage
 Big Oh relates to an upper bound on
complexity meaning the worst amount of
time/space an algorithm could take.
Continue: Data Organization
 Sorted List
 Array vs.
Linked List
Implementation
Operation
Array
Linked List
Create empty list
O(1)
O(1)
Delete all list elements
O(1)
O(n)
Compute Length
O(1)
O(n)
Search for item
O(log n)
O(n)
Access kth element in
list
O(1)
O(n)
Access next list element O(1)
O(1)
Access previous list
element
O(1)
O(n)
Insert/delete accessed
item
O(n)
O(1)
Data Organization Algorithms
Binary Search
O(log n)
Trees
Hight = floor( log2n )
Add & Delete O(logn)
Queues
Add=Delete=O(1)
Priority Queues
O(logn) For tree structure;
however O(n) if the tree is
unballanced
Heaps ; based on the notion of a Time for Extract Max
complete tree
=Insert=O(logn) ;
Bubble, Selection, Insertion
Sorts
O(n2) only suitable for small
problems
Red-Black Trees
O(log n)
Program Control
 Aspects of the language that control which
program statements get executed, and in
what order. Control Statements do not
evaluate to a numeric value.
 Examples




If Statements
While Statements
For Statements
Break Statement
Scope
 The scope of an identifier is the region of a
program source within which it represents
a certain thing (int, object, etc.). This
usually extends from the place where it is
declared to the end of the smallest
enclosing block (begin/end or
procedure/function body).
Examples of Scope
 Lexical Scope( or static scope): scope of
an identifier is fixed at compile time to
some region in the source code containing
the identifiers declaration. This means
that an identifier is only accessible within
that region.
Int foo( )
{
int a;
a=3
return a;
}
Dynamic Scope:
 An identifier can be referred to, not only in
the block where it is declared, but also in
any function or procedure called from
within that block, even if the called
procedure is declared outside the block.
Global Variable.
Int a;
Int Foo2()
main Foo()
{
{
int b;
a=5;
b=foo2() }
return a;
}
Static/Dynamic Binding
 Static Binding (AKA Early Binding): The
compiler uses the type of variables to do
the binding at the compile time
 Dynamic Binding(AKA Late Binding): the
decision is made at run time based on the
type of the actual values
Main Binding Techniques
 Early (static) binding, is the binding of functions in a program at
compile time
The program knows the type of the data for each
function called. For example:
AddRealNums (x, y) x & y are of type real
 Late (dynamic) binding of the message selector to the appropriate
method at run time
The programmer doesn’t know the specific method
that will be used
AddNumber(x, y) x & y are number objects
Shape Class Example
 A display list in a graphic application.
 List Elements:
Object of subclasses of class shape
Triangles, rectangles etc.
 We want the list to contain elements of type Shape, but
each should be capable of preserving its own special
properties.
 If we loop over the list and send each element in it a
draw message, the element should respond according to
its dynamic type.
Static vs. Dynamic Binding
 Static binding: binding based on static type
More efficient
Less flexible
 Dynamic Binding:
More flexible
Less efficient
Parameter Passing Mechanisms
 Call-by-value
 Call-by-reference
 Copy-restore
 Call-by-name
 Functions as Parameters
Term and Definitions
 Formal Parameter: specified (together with type) when




procedure is declared (AKA formals)
Actual Parameters: values which are passed to a
procedure at call site (AKA actuals).
L-value: storage location represented by an expression
(e.g. a register, a memory location, etc.)
R-value: value contained at the storage location
L- and r refer to the “left” and “right” side of an
assignment. Int factorial ( int n)
Formal
{
if (n == 0) return 1;
else return n * factorial (n – 1 );
}
…
Factorial ( 42 );
Actuals
Call-by-value
 A formal is treated the same as a local (i.e. storage is
allocated on the stack or in a register)
 The caller evaluates the actuals and passes the result to
the callee
 Operations on the formals do not affect values in the
stack frame of the caller, so the following will not work:
Void swap (int a, int b) {
int temp;
temp = a; a = b; b = temp;
}
Call-by-reference
 Also known as: call-by-address, call-by-location
 The location of the actual is passed, rather then its
value:
if the actual is a variable (i.e. corresponds to an
assignable location in memory) its address is
passed
if the actual is an expression, the expression is
evaluated to a temporary location and the address of
that location is passed ( the compiler will warn you
since this is not what you usually want)
 Operation on the formals do affect the values in the
caller, so procedure swap now works:
Void swap (int& a, int& b) {
int temp;
temp = a; a = b; b = temp;
}
Copy-restore
 Also known as: copy-in copy-out, value-result
 Combination of call-by-value and call-by-reference:
 The actuals are evaluated before the call
 The expression having only r-values,
 The expression having l-values are passed by reference
Call-by-Name
 The evaluation of actuals is delayed until their use in
callee
 Can be implemented by using parameterless evaluation
procedures (sometimes called thunks) that are created
for each actual:
Void foo( int a, int b )
{
…a…b…
}
…
Foo ( 1+2, 3 ) ;
…
Int thunk_1( ) {
return 1 + 2
}
Int thunk_2( ) {
return 3;
}
Void foo( proc f, proc g) {
… p() … q() …
}
…
Foo (thunk_1, thunk_2);
…
Functions as Parameters
 A parameter to a function may be a function
itself. Such a parameter is declared by writing
the name of the function’s return type (or void),
then the name of the parameter, and finally a
pair of parentheses(). Inside the parentheses is
a list of the parameter types that the function
needs.
Function parameter
Void apply ( void f( int& ), int data [ ], size_t n )
{
size_t i ;
for ( i = 0; i < n; ++ i)
f ( data [ i ] );
}
Resources





Introduction to Algorithms - Cormen
Data Structures and other objects using C++ - Savitch
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/ds_ToC.html
http://www.cs.cornell.com
http://www.csd.uu.se/kurs/oop/ht98/Lectures/D5/html/Dynamic_Bindi
ng/sld019.htm
 Applying Data Structures 2nd ed – T.G. Lewis
 Compilers Construction ( Principles and Practice) - Louden