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

hi anu , its a nice piece of work.

ReplyDeleteit will be very beneficial for students..

Hi sir,

ReplyDeletegreat work done by you. it will b very beneficial for us thank you sir.

This comment has been removed by the author.

ReplyDelete