Control Flow

Aaron Bloomfield
CS 415
Fall 2005

1
Side Effects & Idempotent Functions

Side Effects – a function has a side effect if it

influences subsequent computation in any way
other than by returning a value. A side effect
occurs when a function changes the environment
in which it exists

Idempotent – an idempotent function is one that if

called again with the same parameters, will always
give the same result

2
Referentially transparent - Expressions in a
purely functional language are referentially
transparent, their value depends only on the
referencing environment.

Imperative programming – “programming

with side effects”.

3
 Side Effects
• Some Languages (Euclid and Turing) do not
allow side effects in functions which return a
value
– If called repeatedly with the same set of arguments,
will always give the same answer

• Sometimes side effects are desired:

– Int rand ();
• Needs to have a side effect, or else the same random
number every time it is called.

4
 Evaluation of Operands
and Side Effects
int x = 0;
int foo() {
x += 5;
return x;
}

int a = foo() + x + foo();

What is the value of a?

5
Control Flow

(really)

6
 Structured vs. Unstructured
Control Flow
Structured Programming – hot programming trend
in the 1970’s
• Top down design
• Modularization of code
• Structured types
• Descriptive variable names
• Extensive commenting
• After Algol 60, most languages had: if…then…else,
while loops
Don’t need to use gotos!
7
 Types of control flow
• Sequencing
• Selection
• Iteration
• Procedural abstraction
• Recursion
• Concurrency
• Nondeterminacy
8
 Sequencing
When one statement occurs before another in the program
text the first statement executes before the second.

Statement block
• groups multiple statements together
Examples
• { } in C, C++, and Java
• begin/end in Algol, Pascal, and Modula

Basic block (we’ll discuss later when we finish compilers)

• block where the only control flow allowed is sequencing

9
Selection

10
 If Statements
• If condition then statement else statement
– Nested if statements have a dangling else problem
If … then if … then … else …
Which one does the else map to?
• Algol 60
– Doesn’t allow “then if”
• Pascal
– Else associates with closest unmatched then
• Perl
– Has a separate elsif keyword (in addition to else and if)
– “else if” will cause an error

11
 Strict vs short-circuit evaluation of
conditions
strict
– evaluate all operands before applying operators
• Pascal
short-circuit
– skip operand evaluation when possible
– examples
• || and && in C++ and Java
– always use short-circuit evaluation
• then if and or else in Ada
– language supports both strict and short-circuit, programmer
decides: use and, or for strict evaluation

12
 Short circuiting
• C++
p = my_list;
while (p && p->key != val)
p = p->next;
• Pascal
p := my_list;
while (p <> nil) and (p^.key <> val) do
p := p^.next

13
 Short-circuiting
• Perl
– open (FILE, “>filename.ext”) or die (“error!”);

• Can avoid: out-of-bounds/dereferencing NULL

reference errors, division by zero
• Can lead to more efficient code
• Can be problematic when conditions have side
effects.
14
 Case Statements
• Alternative to nested if…then…else blocks
j := … (* potentially complicated expression *)
IF j = 1 THEN clause_A
ELSEIF j IN 2,7 THEN clause_B
ELSEIF j IN 3..5 THEN clause_C
ELSEIF (j = 10) THEN clause_D
ELSE clause_E
END

15
 Implementation of Case Statements
• If…then…else • Case (uses jump table)

16
 Case vs Switch
• Switch is in C, C++, and Java
– Unique syntax
– Use break statements, otherwise statements fall
through to the next case
• Case is used in most other languages
– Can have ranges and lists
– Some languages do not have default clauses
• Pascal

17
 Origin of Case Statements
• Descended from the computed goto of
Fortran

goto (15, 100, 150, 200), J

If J is 1, then it jumps to label 15

If J is 4, then it jumps to label 200
If J is not 1, 2, 3, or 4, then the statement does
nothing

18
Iteration

19
 Iteration
• More prevalent in imperative languages
• Takes the form of loops
– Iteration of loops used for their side effects
• Modification of variables

20
 Loops
• Two (2) kinds of iterative loops

– Enumeration-Controlled Loop
• Executed once for every value in a finite set

– Logically-Controlled Loop
• Execute until some boolean condition
– Depends on value altered in the loop

21
 Enumeration-Controlled Loop
• Early Fortran:
do 10 i = 1, 50, 2
. . .
10: continue
• Equivalent?
10: i = 1
. . .
i = i + 2
if i <= 50 goto 10

22
 Issues #1
• Can the step size/bounds be:
– Positive/negative ?
– An expression ?
– Of type Real ?

23
 Issues #2
• Changes to loop indices or bounds
– Prohibited to varying degrees
– Algol 68, Pascal, Ada, Fortran 77/90
• Prohibit changes to the index within loop
• Evaluate bound once (1) before iteration

24
 Changes to loop indices or bounds

• A statement is said to threaten an index

variable if
– Assigns to it
– Passes it to a subroutine
– Reads it from a file
– Is a structure that contains a statement that
threatens it

25
 Issues #3
• Test terminating condition before first iteration
• EX
for i := first to last by step do
…
end

r1 := first r1 := first
r2 := step r2 := step
r3 := last r3 := last
L1: if r1 > r3 goto L2 L1: …
… r1 := r1 + r2
r1 := r1 + r2 L2: if r1 <= r3 goto L1
goto L1
L2: 26
 Issues #4
• Access to index outside loop
– undefined
• Fortran IV, Pascal
– most recent value
• Fortran 77, Algol 60
– index is a local variable of loop
• Algol 68, Ada

27
 Issues #5
• Jumps
– Restrictions on entering loop from outside
• Algol 60 and Fortran 77 and most of their
descendents prevent the use of gotos to jump into a
loop.
– “exit” or “continue” used for loop escape

28
 Logically Controlled Loops
while condition do statement

• Advantages of for loop over while loop

– Compactness
– Clarity
– All code affecting flow control is localized in
header

29
 Logically-Controlled Loops
• Where to test termination condition?

– Pre-test

– Post-test

– Mid-test

30
 C’s for loop
• C’s for loop
– Logically controlled
• Any enumeration-controlled loop can be written as a
logically-controlled loop

for (i = first; i <= last; i += step) { i = first;

… while (i <= last) {
} …
i += step;
} 31
 C’s for loop
• Places additional responsibility on the
programmer
– Effect of overflow on testing of termination
condition
– Index and variable in termination condition can
be changed
• By body of loop
• By subroutines the loop calls

32
 Combination Loops
• Combination of enumeration and logically
controlled loops
• Algol 60’s for loop

For_stmt -> for id := for_list do stmt

For_list -> enumerator (, enumerator )*
Enumerator -> expr
-> expr step expr until expr
-> expr while condition
33
 Algol 60’s for loop
• Examples: (all equivalent)
for i := 1, 3, 7, 9 do…
for i := 1 step 2 until 10 do …
for i := 1, i + 2 while i < 10 do …

• Problems
– Repeated evaluation of bounds
– Hard to understand

34
Recursion

35
 Recursive Computation
• Decompose problem into smaller problems
by calling itself
• Base case- when the function does not call
itself any longer; no base case, no return
value
• Problem must always get smaller and
approach the base case

36
 Recursive Computation
• No side effects
• Requires no special syntax
• Can be implemented in most programming
languages; need to permit functions to call
themselves or other functions that call them
in return.
• Some languages don’t permit recursion:
Fortran 77
37
 Tracing a Recursive Function
(define sum (lambda(n)
(if (= n 0)
0
(+ n (sum (- n 1))))))

38
 Tracing a Recursive Function
>(trace sum)
#<unspecified> >
>(sum 5)
"CALLED" sum 5
"CALLED" sum 4
"CALLED" sum 3
"CALLED" sum 2
"CALLED" sum 1
"CALLED" sum 0
"RETURNED" sum 0
"RETURNED" sum 1
"RETURNED" sum 3
"RETURNED" sum 6
"RETURNED" sum 10
"RETURNED" sum 15
15

39
 Embedded vs. Tail Recursion
Analogy: You’ve been asked to measure the distance between
Thornton and Little John’s
Embedded:
1. Check to see if you’re there yet
2. If not, take a step, put a mark on a piece of paper to keep
count, restart the problem
3. When you’re there, count up all the marks
Tail:
1. Write down how many steps you’re taken so far as a
running total
2. When you get to Little John’s, the answer is already
there; no counting!
40
 Which is Better?
• Tail.
• Additional computation never follows a recursive
call; the return value is simply whatever the
recursive call returns
• The compiler can reuse space belonging to the
current iteration when it makes the recursive call
• Dynamically allocated stack space is unnecessary

41
 Iteration vs. Recursion
• Any logically controlled iterative algorithm can be
rewritten as a recursive algorithm and vice versa
• Iteration: repeated modification of variables
(imperative languages)
– Uses a repetition structure(for, while)
– Terminates when loop continuation condition fails
• Recursion: does not change variables (functional
languages)
– Uses a selection structure (if, if/else, or
switch/case)
– Terminates when a base case is recognized
42
 Prolog Example
factorial(N, F) := factorial(N, F) := F is
F is the integer the integer Factorial
Factorial of N of N
factorial(N,N,F,F).
factorial (0,1).
factorial(N,F) :-
factorial(N,F) :- factorial(0,N,1,F).
N > 0, factorial(I,N,T,F):-
N1 is N - 1, I < N,
factorial(N1,F1), I1 is I + 1,
T1 is T * I1,
F is N * F1. factorial(I1,N,T1,F).

43
 Tail Recursion Example
int gcd(int a, int b){ int gcd(int a, int b){
if (a==b) return a; start:
else if (a > b) if (a==b) return a;
return gcd(a-b, b); else if (a > b) {
a = a-b;
else
goto start;
return gcd(a, b-a) } else {
} b = b-a;
goto start;
}
}

44
 Which is tail recursive?
(define summation (lambda (f low high)
(if (= low high)
(f low)
(+ (f low) (summation f (+ low 1) high)))))

(define summation (lambda (f low high subtotal)

(if (= low high)
(+ subtotal (f low))
(summation f (+ low 1) high (+ subtotal (f low))))))

45
 Normal vs. Applicative
(define double (lambda (x) (+ x x)))

(double (* 3 4))
>(double 12)
>(+ 12 12)
 24

(double (* 3 4))
 (+ (* 3 4) (* 3 4))
 (+ 12 (* 3 4))
 (+ 12 12)
 24

46