About Me

My Photo
I am a kind of person who is looking forward to build a progressive career in a challenging environment and to present myself with best of my innovative ideas and technical skills. I have completed B.Tech in COMPUTER SCIENCE & ENGINEERING with “Honours” from College Of Engineering Roorkee (COER), Roorkee, affiliated to Uttar Pradesh Technical University,Lucknow. M.Tech from UTU, Dehradun. Ph.D pursuing from AMITY UNIVERSITY, NOIDA. My research areas are Data Mining and Data Analytics. Software Engineering, Artificial Intelligence.

Tuesday, September 15, 2009

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

3 comments:

  1. hi anu , its a nice piece of work.
    it will be very beneficial for students..

    ReplyDelete
  2. Hi sir,
    great work done by you. it will b very beneficial for us thank you sir.

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete