Chapter8 Sequence Control

사람이 대화를 할 때도 뜻이 제대로 전달되기 위해서는 '순서'가 중요하다.
프로그래밍 언어에서는 이를 Sequence Control(flow control)이라고 한다.

 

 

Classifying Sequence Controls

Control 분류

• Sequence Control(Flow Control): 수행 순서 제어
• Data Control: 서브프로그램 사이의 데이터 흐름 제어

제어 대상 크기(granularity)에 따른 Sequence Control 분류

• Expressions: 표현 식 계산 제어
• Statements: 문장 수행 제어
• Subprograms: 서브 프로그램 사이의 흐름 제어
• cf) Declaerative Programming: 추론 과정 제어 (여기서 다루지는 않음)

표현 여부에 따른 Sequence Control 분류

• Implicit: 별도로 나타내지 않아도 기본적으로 정해져 있는 흐름 제어
• Explicit: 기본 흐름을 변경하기 위한 제어

 

 

Tree Representation of an Expression

Tree Representation

• 표현식을 나타내는 기본적인 방법
• functional composition: 연산자(operation or function)를 서브트리의 루트에, 피연산자를 하위 노드에 나타냄

Tree Representation의 예

 

Postfix

Expression Syntax

• infix: 연산자가 피연산자의 사이에 위치(2항 연산에 적합)
• prefix (Polish prefix): 연산자가 피연산자들의 앞에 위치 (바로 앞 예, Cambridge Polish notation), 일반적인 함수 호출 표기
• postfix (reverse Polish): 연산자가 피연산자들의 뒤에 위치
• 참고
  • 위 표기법 구문은 트리 표기에서의 순회 순서와 일치
  • prefix와 postfix는 계산 순서가 명확하게 드러남

 

Expression Semantics

• postfix가 가장 많이 쓰임 <- Stack을 이용한 계산에 적합
• postfix evaluation의 예: 2 3 4 + 5 * +
• 컴파일러의 코드 생성에도 유리

 

 

Precedence and Associativity(우선 순위와 연관성)

Infix 표기법의 모호함을 해결하는 방법

• 매번 괄호를 쓴다. -> 너무 번거로움
• 우선순위, 결합방향을 정한다. -> 정하지 않은 연산자 사이에는 해결되지 않은 상태로 남아 있을 수 있음

우선순위와 연관성

• Precedence(우선순위): 인접한 다른 연산자 사이의 피연산자가 어느 연산자의 피연산자인지 결정하기 위한 순위
• Associativity(결합방향): 인접한, 같은 우선순위의 연산자 사이의 피연자가 어느 연산자의 피연산자인지 결정하기 위한 순위

Language Examples

• C: 복잡한 우선순위와 결합방향을 정의
• APL: 우선순위는 없고 항상 right-to-left 결합
• Forth: Postfix 표기사용

참고) C에서 연산 우선순위

 

Evaluation Order(평가 순서)

Eager Evaluation

• 피연산자의 값을 먼저 구하고 함수를 적용
• eval-apply evaluation model

Lazy Evaluation

• 함수의 정의에 따라 필요한 경우에만 피연산자의 값을 구함
• push-enter evaluation model
• 예)

인수 전달 방법과의 유사성

• eager evaluation ~= pass by value
• lazy evaluation ~= pass by name

 

 

Side Effects

Side Effect란?

• 인수를 이용하여 결과 값을 계산하는 것 외에 수행하는 다른 연산
• 비지역변수 변경, 입출력 연산, manual allocation of varialbles

예)

 

Short-Circuit Boolean Expression

Short-Circuit Expression이란?

• 일부 논리 연산자의 경우(논리합,논리곱) 좌측 피연산자의 계산 결과에 따라 우측 피연산자의 계산 여부를 결정할 수 있음
• 예: if ((a==0)||(b/a>c)){...}
• lazy evaluation의 특수한 형태(eager evaluation에 어긋남)

Short-Circuit Evaluation에 따른 진리표

두 버전의 논리 연산자를 제공(Ada)

• and then, or else: short-cutcuit 연산자
• and, or: short-circuit evaluation을 하지 않는 연산자

 

Basic Statements

Assignment Statement

• assignment를 operator로 간주하는 언어도 있음
  -> cascading assignment 가능
  a = b= 1
• aggregation에 대한 assignment(예: 배열, record)를 지원할 수도 있음 -> 원소의 evaluation 및 assignment 순서가 중요
  {a,b} = {b,a} //record assignment가 가능하다면..
  {i,j} = {2,a[i]} // 파이썬의 경우에는 연산도중 i가 변하지 않는다. 해당 라인코드시작할 때부터 끝날때까지 i는 처음값 그대로다.

I/O Statement

• 파일 또는 console I/O에 대한 assignment로 볼 수도 있음
• 라이브러리를 통해 지원하는 것이 최근 추세임

 

Statement Sequence Control

Explicit Sequence Control

• 기계어로부터 유래됨
• goto: unconditional goto, conditional goto
• break, continue: loop 반복 제어

Structured Program Theorem

• 다음 세 가지 제어 구조는 계산 가능한 기능을 표현하기에 충분하다.
  • Composition(sequence): 놓인 순서대로 수행
  • Alternation(selection): 둘 이상의 문장에 대해 하나만 선택
  • Iteration(repetition): 특정 문장을 0회 이상 반복

 

Structured Programming

Goto에 의존하면

• 프로그램 계층 구조를 알아볼 수 없다 -> one-in, one-out 구조 필요
• 문장 순서가 수행 순서와 무관하다 -> 스파게티 코드 유발
• 특정 문장 그룹이 여러 용도로 사용될 수 있다 ->  이해하기 어려움

Structured Programming

• 프로그램 설계를 계층적으로
• structured 제어 구조만 사용(3가지 기본구조)
• 문장 순서가 바로 수행 순서가 되도록
• 어떤 문장 그룹은 하나의 목적으로 사용되도록
• -> goto-less programming

 

스파게티 코드

과거 goto문이 유해한가에 대한 논쟁이 있었지만 최근에는 일반적으로 사용하지 않는다.

 

 

Sequence Structure

일련의 문장을 차례로 수행

 

Compound Statement

• 여러 문장을 한 문장처럼 취급
  begin
      statement1;
      statement2;
  end;

 

 Block

• 복합문의 일종
• 시작 부분에 선언문이 올 수 있음

 

 

Selection Structure

Single Branch

• if expression then statement1

Two-Branch

• if expression then statement1 else statement2

 

Dangling Else Problem

• 이 "else"가 누구 else냐?
  if expr1 then tif expr2 then statement1 else statement2
  
  • 해결방법1: 가장 가까운, 앞쪽, 짝없는 if
  • 해결방법 2: end-if을 강제

Multiple Selection

Case Statement

Jump Table Implementation

 

 

Repetition Structure

Simple Repetition

• perform statement K times

Counter-Controlled Repetition

• for I := 1 step 2 until 30 do body

Sentinel-Controlled Repetition

• while test do body
  repeat body until test

Data-Based Repetition

• foreach X in dataContainer do body

Indefinite Repetition (infinite loop)

• loop body end loop; (body에서 별도의 loop 탈출 문장 사용)
  cf. do-while-do

 

dowhiledo

Indefinite Repetiton의 변형된 형태

 

 

 

Prime Programs

• 제어구조와 관련한 일관적 이론 수립을 위헤서 고안
• Roy Maddux가 1975년에 제시
• Approach
  • 흐름도를 이루는 기본 구성요소: function, decision, join
  • 프로그램 분류: prime program, composite program
  • 우리가 추구해야 할 방향: proper program

노드의 종류

Proper Programs

Proper program: 제어 흐름이 다음과 같은 프로그램

• 입구가 하나
• 출구가 하나
• 입구로부터 모든 노드로 경로가 있고, 모든 노드에서 출구로 경로가 있음

Prime Program

• 두개 이상의 노드로 이루어진 proper subprogram을 포함하고 있지 않은 proper program 
• 단, function node가 일렬로 늘어선 경우는 하나의 prime으로 취급
• 그 안에서 프라임 서브프로그램을 추출하기 위해 2개의 아크를 자를 수 없다.
• sunprogram을 구분하기 위해선 해당 자리에 function노드를 하나 넣어보면 된다.(입력,출력 부분이 각각 1개여야함)

Composite Program

• prime program이 아닌 proper program

 

Prime Program의 종류

 

Prime Decomposition

• 모든 proper program은 prime program의 계층으로 유일하게 구별가능(단, function node가 일렬로 늘어서, 특별한 경우는 제외)

 

Analogy(유사)

Composite Number and Prime Number

• composite number은 prime number의 곱으로 구성됨
• prime number은 2이상의 수로서 1과 자신 외에는 약수가 없는 수

Composite Program and Prime Program

• composite program은 prime program을 조합하여 구성됨
• prime program은 function 노드를 제외한 둘이상의 노드로 구성된 프로그램
• function 노드가 일렬로 늘어선 형태는 하나의 function 노드로 간주할 수 있음

 

 

---