NOTES ON SEQUENCE CONTROL

Programming Language
SEQUENCE CONTROL


Contents

n Introduction
n Sequence Control Structures
n Sequencing with Arithmetic Expressions
n Sequencing with Non-Arithmetic Expressions
n Sequence Control between Statements

Introduction

n Program control involves
n Sequence control
n control of the order of execution of the operations

n Data control
n control of transmission of data among subprograms of a program


Sequence Control Structures

n Structures used in expressions
n precedence rules and parenthesis
n Structures used between group of statements
n conditional and iteration statements
n structures used between subprograms
n subprogram calls

n Implicit control vs. explicit control
n Implicit control
n defined by the language and not modified until user redefine it
n Explicit control
n programmer uses to redefine implicit control sequence (parenthesis)


Sequencing with arithmetic expressions(1/5)

n Prefix Notation
n Operators come first, then the operands
n e.g. (a + b) * (c - a) => * + a b - c a
n No ambiguity and no parenthesis needed
n Number of arguments for an operator must be known a priori
n Relatively easy to decode using stack mechanism
n Postfix notation
n An operator follows its operands
n e.g. (a+b) *(c-a) => a b + c a - *
n No ambiguity and no parenthesis needed
n Relatively easy to decode using stack mechanism

Sequencing with arithmetic expressions(2/5)

n Infix notation
n Only suitable for binary operations (Thus used with prefix)

n For more than one infix operator, it is inherently ambiguous

n Parenthesis is used to explicitly annotate the order

Sequencing with arithmetic expressions(3/5)

n Implicit control rules
n Hierarchy of operations (precedence) e.g. Ada
n **, abs, not : Exponential absolute negation
n * / mod : Multiplication, division,
n + - : Unary addition and subtraction
n + - & : Binary addition and subtraction
n = < > : Relational
n and or xor : Boolean operatins
n Table 6.2 pp245
n Associative
n left-right associativity (+, -, others)
n right-left associativity (exponential)

Sequencing with arithmetic expressions(4/5)

n Issues in Evaluating Expressions
n Uniform Evaluation rules (eager and lazy)
n Eager
n evaluate the operands as soon as they appear (parallel processing SNOBOL)
n Lazy Evaluation
n Delay evaluation of operands as late as possible (LISP)

foo( x )
{ ...
if ( a > 0 )
a = x;
else a = a + 1;
}

foo( b/a );

Sequencing with arithmetic expressions(5/5)

n Issues in Evaluating Expressions
n Side effects
n a * foo(x) + a; say a= 1; foo(x) generates 3
n if each term is evaluated 1 * 3 + 2 = 5
n if a is evaluated only once 1 * 3 + 1 = 4
n if evaluate foo(x) first 2 * 3 + 2 = 8
n Error Condition
n No solution other than exceptional statements
n Short-circuit expression
n Use the characteristics of “and” or “or” operation

a b - a is true b is not evaluated
a && b - a is false b is not evaluated
e.g.
b = 9;
if ( a = 4 b = 3 )
printf (" a = %d b = %d\n");

Sequencing with Non-arithmetic expressions(1/3)

n Pattern Matching
n Pattern matching operation
n An operation matches and assigns a set of variables to a predefined template

e.g. (palindromes)
A -> 0A0 1A1 0 1
matches 00100 -> 00A00 -> 0A0 -> A
applied term rewriting 00A00 is a term rewrite of 00100

n term rewriting
n A restricted form of pattern match

e.g. Given string a1a2a3a4 and α -> β.
if α = a3 then a1a2βa4
we say a1a2βa4 is term rewrite of a1a2a3a4

e.g.) in ML
fun fact(1) = 1
fact(N:int) = N * fact(N - 1);
fun length( nil ) = 0
length( a :: y) = 1 + length( y )

Sequencing with Non-arithmetic expressions(2/3)

n Pattern Matching (continued)
n Unification and substitution
n In Prolog, Database consists of facts and rules
n Substitution
n replacement of a string to another one
n Unification
n A pattern match to determine if the query has a valid substitution consistent with the rules and facts in the database


Fact : ParentOf( Ann, John) ParentOf( Sam, Ann)
Fact : ParentOf( Tom, John)
Query : ParentOf( x, John)
Þ X = Ann, x = Tom
Rule : GrandOarentOf( X,Y) :- ParentOf(X,Z), ParentOf(Z,Y)
then query : GrandParentOf (x,John) => x = sam

Sequencing with Non-arithmetic expressions(3/3)

n Backtracking
n Backup to the previous subgoal that matched and try another possible goal for it to match when current subgoal is failed

Sequence Control Between Statements (1/9)

n Basic statements
n Statements that apply operations to data objects
n Considered as a unit of step
n e.g. : assignment operations, subprogram calls, input/output statements
n Statement Level Sequence Control
n Composition
n Statements may be placed in a textual sequence and be executed in order
n Alternation
n Two Sequences may form alternatives and either one is executed
n Iteration
n A sequence of statement are executed repeatedly, zero or more times

Sequence Control Between Statements (2/9)

n Explicit Sequence Control (1/3)
n Goto statement (1/2)
n Unconditional goto
n Transfers control to the labeled statement
n Ex) goto NEXT

n Conditional goto
n Transfers control to the labeled statement only if the specified condition holds.
n Ex) if A=0 then goto NEXT



Sequence Control Between Statements (3/9)

n Explicit Sequence Control (2/3)
n Goto statement (2/2)
n Advantages
n Direct hardware support for efficient execution
n Simple and easy use and easy understanding for low level programmers
n May simulate any control structure
n Problems
n Leading unstructured programming (no goto in ML)
n Superfluous any program with goto can be translated into another one w/o goto
n Undefined control with nested structure


Sequence Control Between Statements (4/9)

n Explicit Sequence Control (3/3)
n Break Statement
n Control to move forward to an explicit point at the end of given control structure
n That is, exit the immediately enclosing while, for, or switch statement

While (a > b)
{
A;
…
if ( k > 0 ) break;
B;
…
}



Sequence Control Between Statements (5/9)

n Structured Programming Design
n Structured program is
n A program that contains no GOTOs

n Structured programming emphasizes
n Hierarchical design of program structure with the composition, alternation, and iteration
n Use structured sequence control that represents hierarchical design
n Textual sequences corresponds to the execution sequence
n Unique purpose group of statements then it is copied


Sequence Control Between Statements (6/9)

n Structured Sequence Control (1/4)
n Control statements that only contains one-in one-out control sequences (no goto in ML)
n Compound statement
n A sequence of statements that may be treated as a single unit in construction of large one
n Conditional statement
n Expresses alternation of two or more statements, or optional execution of a single statement
n Ex) IF statement, CASE statement
n If statements are implemented using the usual hardware supported branch and jump instruction
n Case statements are implemented using a jump table to avoid the testing of the same variable
n Jump table : A vector whose components are unconditional jump instructions

Sequence Control Between Statements (7/9)

n Structure Sequence Control (2/4)
n Iteration Statement (1/2)
n Simple repetition
n Repeat a fixed number of times
n Ex) perform BODY K times (COBOL)
n Repetition while condition holds
n Reevaluate the condition each time after BODY
n Ex) While test do BODY
n Repetition while incrementing a counter
n Initial value, final value, and the increment
n Ex) for l := 1 step 2 until 30 do BODY
n Indefinite repetition
n Used when the exit condition is complex and hard to express
n In C, all 4 forms can be written by for statement


Sequence Control Between Statements (8/9)

n Structure Sequence Control (3/4)
n Iteration Statement (2/2)
n Advantages
n Easy to debug, understand, and verify
n Disadvantages
n Multiple exit loops
n Can be replaced with “exit” in ADA or “break” in C., but PASCAL goto must be used in the for loop
n Do-while-do
n The condition is checked in the middle of the loop
n Exceptional conditions
n Unexpected end-of-file, subscript range error, bad data…
n Ex) raise statement in ADA à raise BAD DATA


Sequence Control Between Statements (9/9)

n Structure Sequence Control (4/4)
n Proper program
n Formal model of control structure, as a flow chart which;
n Has a single entry arc
n Has a single exit arc,
n Has a path from the entry arc to each node and from each node to the exit arc
n Prime program
n A proper program that cannot be subdivided into smaller proper programs
n Composite program
n A program that is not a prime
n The Structure theorem
n Bohm and Jacobini (1966)
n Any prime program could be converted into tone using only while and if statements called a well-structured program