ch8. Statement-Level Control Structure

▷ Introduction

    - R&D on control statements during 1960-70

    - all algorithm that can be expressed by flow char can be coded in a PL

      with only two control statements

> choosing between two control flow paths

> logically controlled iteration

    - Unconditional branch statement is superfluous

    - tradeoff between writability and readability

    - Question : what is the best collection of control statements to provide 

    the required capabilities and the desired writability

▷ Compound Statements

     ♤ ALGOL60 introduced the first statement collection structure of the form 

       :  

begin

<Statement 1>;

. . .

<Statement n>;

end

     ♤ it allows a collection of statements to be abstracted to a single statement : block

     ♤ Design issue : 

whether the control structure can have multiple entries? 

(block에 여러방법으로 접근 가능?)

▷ Selection Statements

   : Provides the means of choosing between two or more execution path in a program

   ♠ two-way selection statements : if stmt

♤ Design issue

   - what is the form and types of the expression that controls the selection?

   - can a single statement, a sequence of statements, or a compound 

     statement be selected?

   - How should the meaning of selectors nested in then clause of other

     selectors be specified?                                        (ambiguous)

♤ Example    

    > FORTRAN

- IF( <boolean expression>) <statement>

- usually GOTO statement

    > ALGOL 60

- single/compound statement

 ♤ Nesting selectors

      <if_stmt> -> if(<expr>) <stmt>

     |  if(<expr>) <stmt> else < stmt>

- if에 대한 else의 모호함

  해결방법 : else 추가 (if마다) / 

     :중괄호 / 

     : compiler가 어떻게 처리하는지 프로그래머가 알고 쓰기

◈ C, Pascal 

   - semantic rule

◈ ALGOL 60

   - if statement is not allowed to be nested directly in a then clause, 

     instead, it must be placed in a compound statement

◈ Ada

   - special word end if 

♠ Multiple selection statements : case stmt

   ♤ the multiple selection constructs allows the selection of one of any number of

      statements or statement groups

   

   ♤ Design issue

      - what is the form and type of the expression that control the selection?

      - may a single statement, a sequence of statement or a compound statement 

        be selected?

      - is the entire construct encapsulated in a syntactic structure

      - is execution flow through the structure restricted to include just a single

        selectable segment?

      - how should unrepresented selector expression values be handled, if at all?

   ♤ Early multiple selectors

      > FORTRAN

- three way selector

IF (<arithmatic_expression>) N1, N2, N3

       <    =    >   (세가지 경우)

- computed GO TO

   ♤ Modern multiple selector

       > general form of Hoare's multiple selector

case <integer_expression> of

begin

<Stmt 1>;

. . .

<Stmt n>;

end

       > Pascal case statement

case <expression> of

<constant 1> : <stmt 1>;

 . . .

<constant n> : <stmt n>;

end

   ♤ examples

- Pascal case

- C switch

- If-else if

▷ Iterative Statements    

    : causes a statement or collection of statements to be executed zero or more times

      ♠ Design issues

- how is the iteration controlled?

- where should the control mechanism appear in the loop?

 

      ♠ Counter-controlled Loops

: loop variable and loop parameter

♤ design issues

  - loop variable의 type과 scope?

  - loop가 끝난 시점에서의 loop variable의 값은?

  - loop variable 또는 loop parameter가 loop내에서 변경가능? 

     변경하게되면 loop control에 영항을 미칠것인가?

  - loop의 시작과 끝중에 어디에서 완료여부를 확인할 것인가?

  - loop parameter는 한번만 evaluated 하는지, 매번 반복할 때마다 evaluated 하는지?

♤ FORTRAN IV DO

      DO lable_variable = initial, terminal [, stepsize ]

- initial, terminal, stepsize : unsigned int 

- loop variable type : int

- its scope : that of the program unit

- the value of the loop variable : most recently assigned value

- the loop variable and loop parameters can not be changed

- loop parameter evaluation : once

- post loop construct 

▣ problems

  - exit : go to outside the loop

  - reenterence : go to inside the loop 

~ cannot detect illegal reenterance

~ C에서는 reenterance 허용안함 : readability,reliability가 나빠지니까

♤ FORTRAN 77 and 90 DO

     ▣ Operational semantics

- Similar to that of FORTRAN V but

- the loop variable : integer, real, or double

- the loop parameters : expression, positive, negative values

- pretest : evaluated at the beginning of the execution of the DO

♤ The ALGOL60 for statement

     ▣ For statement (EBNF)

<for_stmt> -> for<var> := <list_element> {, <list_element>} do <stmt>

<list_element> -> <expr>

      |  <expr> step <expr> until <expr>

      |  <expr> while <boolean_expr>

 

     ▣ Examples  (complex)

for index := 1, 4, 13, 41

step 2 until 47,

3*index while index < 1000, 34, 2, -24 do

sum := sum + index

     ▣ Design Choice

- the loop variable : integer or real

- scope : that of its declaration

- loop variable at completion : most recently assigned value

- loop parameters can be changed in the loop body

- illegal to branch into the loop body

- pretest loop

- the loop parameter are evaluated for every iteration

♤ The Pascal for Statement

     ▣ model of simplicity

for <variable> := <initial_value>(to|downto)<final_value> do <statement>

     ▣ Design Choice

- the loop variable : ordinal type

- scope : the scope of its declaration

- at the normal loop termination, the loop variable is undefined

- the loop variable may not be changed in the loop

- pretest

♤ The Ada for statement

     ▣ 

for <variable> in[reverse] <discrete_range> loop

 . . .

end loop

- pretest loop

- discrete_range : subrange of an iteger or enumeration

- the scope of the loop variable : 

    implicitly declared at the for statement and implicitly undeclared after 

    loop termination

     ▣ Example

COUNT : FLOAT := 1.35;

for COUNT in 1..10 loop

  SUM := SUM + COUNT

end loop

     ▣ Design choice

- loop variable cannot be assigned a value in the loop body

- variable can be changed in the loop, but because the range is evaluated only once these changes do not affect loop control

- illegal to branch into  the for loop body

♤ The for Statement of C and C++ 

for( <expr opt> ; <expr opt> ; <expr opt> )

<statement>

     ▣ Design choice (★)

- no explicit loop variable or loop parameter

- all involved variables can be changed in the loop body

- the expressions are evaluated in the order of operational semantics

- legal to branch into a C for loop body

      ♠ Logically Controlled loop

♤ the repetition control is based on a boolean expression rather than a counter

♤ Logically controlled loop is more general than counter controlled loop

♤ That is, every counting loop can be built with logical loop, 

   but the reverse is not true

♤ Note, selection and logical loops are essential

♤ Design Issue : simple

  - should the control be pretest or posttest?

  - should the logically controlled loop be a special form of a counting lop 

    or a separate statement?

♤ examples...

♤ In C, it is legal to branch into both a while and do loop bodies

♤ FORTRAN77,90 have neither a pretest nor a posttest logical loop

♤ Ada has a pretest logical loop but no posttest version of the logical loop

      ♠ User-Located Loop Control Mechanisms // user가 loop control

- In some situation, it is convenient to choose a location for loop control other that the top or bottom of the loop

▣ Design choice 

  - should the conditional mechanism be an integral part of the exit?

  - should the mechanism be allowed to appear in a controlled loop or only 

    in one without any other control

  - should only one loop body be exited, or can enclosing loops also be exited?

♤ The form of the Ada infinite loop

loop

 . . . 

end loop

♤ Ada exit

exit [ <loop_variable>][when<condition>]

      ♠ User-Defined Control

♤ example

 for ( ptr = root ; ptr ; traverse(ptr)) 

{

 . . .

}

▷ Unconditional Branching

♤ Problems

    - the most powerful statement for flow control

> great flexibility

    - most dangerous

> restricted goto 

♤ Label from

  - ALGOL60, C, Ada : identifier form ( 변수명인지 오해할 소지 있음)

  - FORTRAN, Pascal : unsigned integer 

♤ Restrictions on branches

♤ the target of a Pascal goto

▷ Guarded Commands

      ♤ non deterministic selection or repetition

      ♤ Dijkstra's selection construct

if <boolean_expression> -> <statement>

[] <boolean_expression> -> <statement>

. . . . . 

[] <boolean_expression> -> <statement>

fi

      ♤ the order of execution is irrelevant

      ♤  Dijkstra's loop structure

do <boolean_expression> -> <statement>

[] <boolean_expression> -> <statement>

. . . . . 

[] <boolean_expression> -> <statement>

od

▷ Conclusions

     - statement level flow controller

: assignment statement... 

: else...

※ Node Splitting : GOTO를 없애는 기법