[프로그래밍 언어론] Sequence Control (9)

 

[8] Sequence Control

Classifying Sequence Controls
- Sequence Control : 수행 순서 제어
- Data Control : 서브프로그램 사이의 데이터 흐름 제어

@Sequence Control : 제어 대상 크기(granularity)에 따른 분류
- Expressions
- Statements
- Subprograms

@Sequence Control : 표현 여부에 따른 분류
- Implicit
- Explicit

Tree Reprensentation of a Expression
- Tree Representation : 표현식을 나타내는 기본적인 방법
- 연산자를 서브트리의 루트에, 피연산자를 하위 노드로 나타낸다. (function composition)
- 계산 의존성을 나타내는 것이지, 서브트리의 계산 순서는 명확하지 않다.

Expression Syntax
- Infix : 연산자가 피연산자들 사이에 위치
- Prefix : 연산자가 피연산자들 앞에 위치 (일반적인 함수 호출 표기)
- Postfix : 연산자가 피연산자들 뒤에 위치 (트리 표기에서의 순회 순서와 일치)
- Prefix와 postfix는 계산 순서가 명확하게 들어난다.
- Postfix가 가장 많이 쓰인다. (Stack을 이용한 계산에 적합)

Precedence and Associativity
- Infix 표기법의 모호함을 해결하는 방법 : 괄호
- Precedence(우선순위) : 인접한 다른 연산자 사이의 피연산자가 어느 연산자의 피연산자인지 결정하기 위한 순위
- Associativity(결합방향) : 인접한, 같은 우선순위의 연산자 사이의 피연산자가 어느 연산자의 피연산자인지 결정하기 위한 순위

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
- 인수를 이용하여 결과 값을 계산하는 것 외에 수행하는 다른 연산
- 비지역변수 변경, 입출력, manual allocation of variables등

@Side Effect 예제
int x = 3;
int y = ++x * x++;
- Side effect를 허용하지 못하도록 강제하거나
- 피연산자 계산 순서를 정확히 정의해야한다.

Short-Circuit Boolean Expression
- 일부 논리 연산자의 경우, 좌측 피연산자의 계산 결과에 따라 우측 피연산자의 계산 여부를 결정할 수 있다.
- Lazy evaluation의 특수한 형태

@Short-Circuit Boolean Expression 예제
if((a == 0) || (b/a > c)) { ... }
- 두 버전의 논리 연산자를 제공할 수 있다. (Ada)
- And then, or else : short-circuit 연산자 (side effect 존재)
- And, or : short-circuit evaliation을 하지 않는 연산자

Basic Statements
- Assignment Statement : aggregation에 대한 assignment를 지원할 수도 있다.
- 지원한다면, 원소의 evaluation 및 assignment의 순서가 중요하다.
- I/O Statement : 파일 또는 console의 I/O에 대한 assignment로 볼 수 있다.

Statement Sequence Control
- Explicit Sequence Control : 기계어로 부터 유래됐다.
- Structured Program Theorem : goto-less programming

@Explicit Sequence Control
- goto, break, continue
- Goto에 의존하면, Single entry, single exit 구조를 지킬 수 없다.
- 문장 순서가 수행 순서와 무관해진다.

@Structured Programs
- Composition(sequence) : 놓인 순서대로 수행
- Alternation (selection) : 둘 이상의 문장에 대해 하나만 선택
- Iteration (repetition) : 특정 문장을 0회 이상 반복
- 문장 순서가 바로 수행 순서가 된다.

Sequence Structure
- 일련의 문장을 차례로 수행
- Compound Statement : 여러 문장을 한 문장처럼 취급
- Block (복합문의 일종, 시작 부분에 선언문이 올 수 있다)

Selection Structure
- Single Branch : if-then
- Two-Branch : if-then-else
- Dangling Else Problem : 이 else가 누구 else냐
- 가장 가까운, 짝이 없는 if와 match 또는 end-if를 강제

Multiple Selection
- Case Statement
- Multiple Selection Implementation : Jump table + Alternatives for CASE statement

Repetition Structure
- Simple Repetition : perform statement K times
- Counter-Controlled Reprtition : for i = 1 step 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;

Prime Programs
- 제어 구조와 관련한 일관적 이론 수립을 위함
- 기본 구성요소 : function, decision, join
- Proper program

Types of Nodes
- Function node
- Predicate node
- Join node

Proper Program
- 1 entry arc
- 1 exit arc
- 입구로 부터 모든 노드로 경로가 있고, 모든 노드에서 출구로 경로가 있다.

Prime Program
- 두 개 이상의 노드로 이루어진 proper subprogram을 포함하고 있지 않은 proper program
- Function node가 일렬로 늘어선 경우는 하나의 prime으로 취급

Composite Program
- Proper program that is not prime program

Prime Decomposition
- 모든 proper program은 prime program의 계층으로 구별 가능하다 (unique)
- Proper program은 replacement function으로 대체할 수 있다.
- Function node가 일렬로 늘어선 경우는 제외

Analogy
- Composite Number and Prime Number
- Composite number는 prime number의 곱으로 구성
- Composite Program and Prime Program
- Composite program은 prime program을 조합하여 구성