PROGRAMMING LANGAUGES

STUDY GUIDE

MODULE 5

CONTROL FLOWS

SUBTOPIC 1: EXCUTION AND STATEMENT

Control flow:
• Sequencing: order of execution
• Selection (also alternation): generally in the form of if or case statements
• Iteration: loops
• Recursion: expression is defined in terms of (simpler versions of) itself

Expression Evaluation
Precedence, associativity
• C has 15 levels - too many to remember
• Pascal has 3 levels - too few for good semantics
• Fortran has 8
• Ada has 6
• Ada puts and & or at same level
• Lesson: when unsure, use parentheses!

Operators
Category Operator Associativity
Postfix () [] -> . ++ - - Left to right

Unary + - ! ~ ++ - - (type)* & sizeof Right to left

Multiplicative */% Left to right

Additive +- Left to right

Shift << >> Left to right

Relational < <= > >= Left to right

Equality == != Left to right

Category Operator Associativity

Bitwise AND & Left to right

Bitwise XOR ^ Left to right

Bitwise OR | Left to right

Logical AND && Left to right

Logical OR || Left to right

Conditional ?: Right to left

Assignment = += -= *= /= %=>>= <<= &= ^= |= Right to left

Comma , Left to right

Program:
#include <stdio.h>
main() {
int a = 20;
int b = 10;
int c = 15;
int d = 5;
int e;
e = (a + b) * c / d; // ( 30 * 15 ) / 5
printf("Value of (a + b) * c / d is : %d\n", e );
e = ((a + b) * c) / d; // (30 * 15 ) / 5
printf("Value of ((a + b) * c) / d is : %d\n" , e );
e = (a + b) * (c / d); // (30) * (15/5)
printf("Value of (a + b) * (c / d) is : %d\n", e );
e = a + (b * c) / d; // 20 + (150/5)
printf("Value of a + (b * c) / d is : %d\n" , e );
return 0; }

PROGRAM:
public class DemoTest
{ public static void main(String[] args) {
System.out.println(4 + (5 * (6 / 3)));
System.out.println(4 + ((5 * 6) / 3));
System.out.println(1 + 2 - (3 * (4 / 5)));
System.out.println(1 + 2 - ((3 * 4) / 5)); } }
Expression Evaluation
Operator precedence levels in Fortran, Pascal, C, and Ada. The operators from the
figure group most tightly.

Infix, Postfix and Prefix

INFIX: a op b
for example, in C++, a + b really calls operator+(a,b)
- Operators are written in-between their operands. This is the usual way we write expressions.
An expression such as A * ( B + C ) / D is usually taken to mean something like: "First add B and
C together, then multiply the result by A, then divide by D to give the final answer."
The expression A + B * C + D can be rewritten as ((A + (B * C)) + D) to show that the
multiplication happens first, followed by the leftmost addition. A + B + C + D can be written as
(((A + B) + C) + D) since the addition operations associate from left to right.

PREFIX: op a b or op(a,b)
Operators are written before their operands. +XY
Example: standard in most we have seen
Example: / * A + B C D
- operators are evaluated left-to-right. Operators act on the two nearest values on the
right. I have again added (totally unnecessary) brackets to make this clear:
(/ (* A (+ B C) ) D)
 A * ( B + C ) / D equivalent in Infix
In Lisp: (* (+ 1 3) 2)

POSTFIX: a b op
• XY+
• Operators are written after their operands.
• A B C + * D / the postfix equivalent of the infix A * ( B + C ) / D
• Least common - used in Postscript, Forth, and intermediate code of some compilers
• Also appears in C (and its descendants) and Pascal examples, such as ++value in C and
the pointer dereferencing operator (^) in Pascal

Examples:

Infix Expression Prefix Expression Postfix Expression

A+B +AB AB+

A+B*C +A*BC ABC*+

Infix Expression Prefix Expression Postfix Expression

A+B*C+D ++A*BCD ABC*+D+

(A + B) * (C + D) *+AB+CD AB+CD+*

A*B+C*D +*AB*CD AB*CD*+

A+B+C+D +++ABCD AB+C+D+

Expression Evaluation

• Ordering of operand evaluation (generally none)

• Application of arithmetic identities
– Commutativity is assumed to be safe
 - this can be used with the logical AND or the logical OR operations to "short circuit" if a
particular condition is met, so that other possibilities need not be tested.
- For example, with the AND operation, if the first condition is false, then the whole
comparison must return false, so the remaining conditions are not evaluated.

– Associativity (known to be dangerous)

– In programming languages, the associativity of an operator is a property that
determines how operators of the same precedence are grouped in the absence
of parentheses; i.e. in what order each operator is evaluated. This can differ
between programming languages.

• Variables as values vs. variables as references

– value-oriented languages
• C, Pascal, Ada
– reference-oriented languages
• most functional languages (Lisp, Scheme, ML)
• Clu, Smalltalk
– Algol-68 is halfway in-between
– Java deliberately in-between
• built-in types are values
• user-defined types are objects - references

Model

Program:
*Java Examples
int a = 5; Output:
int b = a;
b += 10; a=5
System.out.println("a = " + a); b = 15
System.out.println("b = " + b);
Obj a = new Obj(); Output:
Obj b = a;
b.change(); true
System.out.println(a == b);

*
Java Examples
String a = "hi ";
String b = a;
b += "world";
System.out.println("a = " + a);
System.out.println("b = " + b);
Output
a = hi
b = hi world

Expressions versus Statements

• Most languages distinguish between expressions and statements.

– Expressions always produce a value, and may or may not have a side effect.
• Example: In python, b + c
– Statements are executed solely for their side effects, and return no useful value
 • Example: in Python, mylist.sort()

• Expression-oriented vs. statement-oriented languages

– expression-oriented:
• functional languages (Lisp, Scheme, ML)
• Algol-68
– statement-oriented:
• most imperative languages
• object-oriented programming (OOP) languages such as C#, Visual
Basic, C++, and Java, were designed to primarily support imperative
(procedural) programming
– C halfway in-between (distinguishes)

Assignment Shortcuts

ASSIGNMENT
– statement (or expression) executed for its side effect - key to most programming
languages.
– assignment operators (+=, -=, etc)
• Handy shortcuts
• avoid redundant work (or need for optimization)

Assignment
SAMPLE ASSIGNMENT
variable = expression ;

Multiple Assignment
variable = variable = expression ;

Example:
int number, total;
float start_x, start_y;
...
number = total = 0;
start_x = start_y = 100.0;

Shorthand Assignment

variableX = variableX op expression ;

variableX op= expression;
Example: num = num + 5;
Multiway Assignment
• Some languages (including ML, Perl, Python and Ruby) allow multiway assignment.
– Example: a,b = c,d;
– Defines a tuple; equivalent to a = c; b=d;
• Note that this can simplify things:
– a,b = b,a;

C and Assignments with Expressions

C AND ASSIGNMENTS WITHIN EXPRESSIONS
Combining expressions with assignments can have unfortunate side effects, depending on the
language.
Pathological example: C has no true boolean type (just uses ints or their equivalents), and
allows assignments within expressions.
Example:
if (a =b) {
…
}

Side Effects and Functions

SIDE EFFECTS
• a side effect is some permanent state change caused by execution of function
Sometimes side effects are desired:
• Int rand ();
• Needs to have a side effect, or else the same random number every
time it is called.

Expression Evaluation
Several languages outlaw side effects for functions
• easier to prove things about programs
• closer to Mathematical intuition
• easier to optimize
• (often) easier to understand
But side effects can be nice
• consider rand()

More on Side Effects

• Side effects are a particular problem if they affect state used in other parts of the
expression in which a function call appears
– Example: a - f(b) - c*d. OK?
– Fortran says it's OK to have side effects
• aren't allowed to change other parts of the expression containing the
function call
• Unfortunately, compilers can't check this completely, and most don't at
all
 • Sequencing
SEQUENCING
When one statement occurs before another, in the program text the first statement executes
before the second.
Blocks of code are executed in a sequence.
▪ specifies a linear ordering on statements
- one statement follows another
Statement block
• groups multiple statements together
Examples
• { } in C, C++, and Java
• begin/end in Algol, Pascal, and Modula

The end of Goto

In 1968, Edsger Dijkstra wrote an article condemning the goto statement.

Use of goto is bad programming practice if the same effect can be achieved using different
constructs.
While hotly debated after this, gotos have essentially disappeared from modern programming
language.

The end of Goto

This is the advent of “structured programming”, a model which took off in the 1970’s.
Emphasizes:
▪ Top down design
▪ Modularization of code
▪ Structured types
▪ Descriptive variables
▪ Iteration

• Getting rid of goto was actually fairly easy, since it was usually used in certain ways.
– Goto to jump to end of current subroutine: use return instead
– Goto to escape from the middle of a loop: use exit or break
– Goto to repeat sections of code: loops

Biggest Need For Goto

• Several settings are very useful for gotos, however.
• BIGGEST NEED FOR GOTO
– To end a procedure/loop early (for example, if target value is found).
Solution: break or continue
Another example: exceptions
▪ Goto was generally used as error handling, to exit a section of code without
continuing
▪ Modern languages generally throw and catch exceptions, instead.
 ✓ Adds overhead
✓ But allows more graceful recovery if a section of code is unable to fulfill its
contract.

Sample Program with Goto

int main()
{
int age;
Vote:
printf("you are eligible for voting"); NoVote:
printf("you are not eligible to vote"); printf("Enter you age:");
scanf("%d", &age);
if(age>=18)
goto Vote;
else
goto NoVote;
return 0;
}

Explanation: In the above example, Vote and NoVote are labels. When the input is >= 18, the
goto statement is transferring the control to label – Vote, otherwise it transfers the control to
label-NoVote.

Sample Program Snippet with Goto

10 X = X + 1
20 PRINT X
30 GOTO 10

10 X = X + 1
20 PRINT X
30 IF X < 10 GOTO 10

SUBTOPIC 2: SELECTION AND ITERATION

Selection
Standard if-then-else statement
if ... then ...
else ...
Multi-way if-then-else statement
if ... then ...
elsif ... then ...
elsif ... then ...
...
else ...
Switch statement
switch ... of
case ...: ...
case ...: ...

Selection
Selection: introduced in Algol 60
– sequential if statements
if ... then ... else
if ... then ... elsif ... else
– Lisp variant:
(cond
(C1) (E1)
(C2) (E2)
...
(Cn) (En)
(T) (Et) )

If condition
• If condition then statement else statement
– Nested if statements have a dangling else problem
• If … then if … then … else …
• 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

Evaluation
Short-Circuit Evaluation of Boolean Expressions
(and a b): If a is false, b has no effect on the value of the whole expression.
(or a b): If a is true, b has no effect on the value of the whole expression.

Short-Circuit Evaluation of Boolean Expressions

(and a b): If a is false, b has no effect on the value of the whole expression.
(or a b): If a is true, b has no effect on the value of the whole expression.
Short Circuit
Some languages provide both regular and short-circuit versions of Boolean
operators.
Ada
and vs and then or vs or else
C
while( p != NULL && p->e != val )
p = p->next;

Selection

Code generated w/ short-circuiting (C)

r1 := A
r2 := B
if r1 <= r2 goto L4
r1 := C
r2 := D
if r1 > r2 goto L1
L4: r1 := E
r2 := F
if r1 = r2 goto L2
L1: then_clause
goto L3
L2: else_clause
L3:

Selection: Case/Switch

• The case/switch statement was introduced in Algol to simplify certain if-else

situations.
• Useful when comparing the same integer to a large variety of possibilities:
i := (complex expression)
if i == 1: …
elsif i in 2,7: …
Case (complex expression)
1: …
2-7: …

While it looks nicer, principle reason is code optimization.

Principal motivation: Generate more efficient code.
Code Optimization is a program transformation technique, which tries to improve the code by
making it consume less resources (i.e. CPU, Memory) and deliver high speed.

Code Optimization
do {
item = 10;
value = value + item;
} while(value<100);

In this optimization, the compiler takes in the intermediate code and transforms a part of the
code that does not involve any CPU registers and/or absolute memory locations.

This code involves repeated assignment of the identifier item

Item = 10;
do {
value = value + item;
} while(value<100);

The given code should not only save the CPU cycles, but can be used on any processor.

Iteration

Ability to perform some set of operations repeatedly.

• Loops
• Recursion
In a real sense, this is the most powerful component of programming.
In general, loops are more common in imperative languages, while recursion is more common
in functional languages.

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

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
Enumeration-Controlled Loop

Logically Controlled Loop

while condition do statement
• Advantages of for loop over while loop
– Compactness
– Clarity
– All code affecting flow control is localized in header

C’s for Loop

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

Algol 60’s for Loop

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

• 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

Iteration
Enumeration-controlled: originated in Fortran
– Pascal or Fortran-style for loops
do i = 1, 10, 2
…
enddo
– Changed to standard for loops later, eg Modula-2
FOR i := first TO last BY step DO
…
END

Iteration Code Generation

This allows very efficient code generation:
R1 := first
R2 := step
R3 := step
L1: … --loop body, use R1 for I
R1 := R1 + R2
L2: if R1 <= R2 goto L1

Recursion
RECURSION
• equally powerful to iteration
• mechanical transformations back and forth
• often more intuitive (sometimes less)
• naïve implementation less efficient
• no special syntax required
• fundamental to functional languages like Scheme
Sample Recursion Program
#include <stdio.h>
int sum(int n);
int main()
{
int number, result;
printf("Enter a positive integer: ");
scanf("%d", &number);
result = sum(number);
printf("sum=%d", result); }
int sum(int num) {
if (num!=0)
return num + sum(num-1); // sum() function calls itself
else
return num;
}

Execution:
Initially, the sum() is called from the main() function with number passed as an argument.
Suppose, the value of num is 3 initially. During next function call, 2 is passed to
the sum()function. This process continues until num is equal to 0.
When num is equal to 0, the if condition fails and the else part is executed returning the sum of
integers to the main() function.

Sample Program:

#include <stdio.h>
long int multiplyNumbers(int n);
int main()
{
int n;
printf("Enter a positive integer: ");
scanf("%d", &n);
printf("Factorial of %d = %ld", n, multiplyNumbers(n)); return 0; }
long int multiplyNumbers(int n) {
if (n >= 1) return n*multiplyNumbers(n-1);
else return 1;
}

Recursion: Slower?
• Many criticize that recursion is slower and less efficient than iteration, since you have to
alter the stack when calling a function.
• This is a bit inaccurate. Naively written iteration is probably more efficient than naively
written recursion.
• In particular, if the recursion is tail recursion, the execution on the stack for the
recursive call will occupy the exact same spot as the previous method.
Recursion
• TAIL RECURSION
Tail recursion is a special kind of recursion where the recursive call is the very last thing in the
function.
It's a function that does not do anything at all after recursing.
No computation follows recursive call

int gcd (int a, int b) {

/* assume a, b > 0 */
if (a == b) return a;
else if (a > b) return gcd (a - b,b);
else return gcd (a, b – a); }
– A good compiler will translate this to machine code that runs “in place”,
essentially returning to the start of the function with new a,b values.

Tail Recursion Example

int gcd(int a, int b){
if (a==b) return a;
else if (a > b)
return gcd(a-b, b);
else
return gcd(a, b-a)
}

int gcd(int a, int b){

start:
if (a==b) return a;
else if (a > b) {
a = a-b;
goto start;
} else {
b = b-a;
goto start;
}
}

Recursion
• Even if not initially tail recursive,
simple transformations can often
produce tail-recursive code.
• Known as continuation-passing.