Sequence Control

• Control?
  • Sequence Control, Flow Control: 수행 순서 제어
    • implicit
    • explicit
  • Data Control: 데이터 흐름 제어
• Classifying Sequence Controls
  • Expression Level
  • Statement Level
  • Subprogram Level
    • Subprogram Control에서 다룸

Expression Level

Tree Representation

: 표현식을 나타내는 기본적인 방법

• Functional Composition
  • 연산자(operator or function)를 서브트리의 루트에
  • 피연산자를 연산자의 하위 노드에!
• 트리 표기는 계산의 의존성을 나타낼 뿐, 좌측 서브트리와 우측 서브트리의 계산 순서는 명확하지 않다!!!

Expression Syntax

• Infix: 연산자가 피연산자 사이에 위치 (이항 연산에 적합)
  • 계산 순서가 모호할 수 있다
    • infix의 모호함을 해결하는 방법:
      • 매번 괄호를 써 준다
      • 우선순위와 결합방향을 정한다
  • (a + b)
• Prefix: 연산자가 피연산자들의 앞에 위치
  • 일반적인 함수 호출 표기
  • (+ a b), add(a, b)
• Postfix: 연산자가 피연산자들의 뒤에 위치
  • 스택을 활용한 계산에 적합하기 때문에, 가장 많이 사용되는 방식!
  • 컴파일러의 코드 생성에도 유리하다
  • (a b +)

Precedence

• 우선순위
• 인접한 다른 연산자들 사이의 피연산자가 어떤 연산자의 피연산자인지를 결정

Associativity

• 결합 방향
• 인접한 같은 우선순위인 연산자들 사이의 피연산자가 어떤 연산자의 피연산자인지를 결정

"모호함을 어떻게 해결할것인가"는 언어의 선택:

C: 모든 연산자의 우선순위와 결합방향을 사전에 정의
APL: 우선순위가 없음(모두 동일한 우선순위), 항상 right-to-left 결합
Forth: Postfix 방식을 사용

Evaluation Order

Eager Evaluation

• 피연산자의 값을 (무조건) 먼저 구하고 -> 연산자(operator or function)를 적용
• eval-apply evaluation model
• pass by value 인수 전달 방식과 유사성이 있다

Lazy Evaluation

• 연산자(operator or function)의 정의에 따라, 필요할 경우에만 피연산자의 값을 계산함
• push-enter evaluation model
• pass by name 인수 전달 방식(Thunk)과 유사성이 있다

Side Effect

: 실인수(Arguments)를 이용하여 결과값을 계산하는 것 외에 수행하는 다른 연산

• 비지역변수(non-local) 변경
• 입출력(I/O) 연산 - 파일 또는 콘솔I/O에 대한 Assignment!!
• Manual Memory Allocation - malloc, new, ...

int x = 3;
int y = ++x * x++; // 20

• 피연산자를 계산할 때, side effect가 발생한다면 결과값 예측이 어려워진다!
  • sol 1: 피연산자들의 계산 순서를 정확히 정의
  • sol 2: Side Effect를 사용하지 않도록 강제

Short-Circuit Evaluation

• 논리합 or 논리곱 연산자의 경우, 좌측 피연산자의 계산 결과에 따라서 우측 피연산자의 계산 여부를 결정할 수 있다!
• Lazy Evaluation의 특수한 형태로도 볼 수 있다

if (1 || /* */) // 뒤에 오는 Expression과 무관하게 조건을 만족시킴
if (0 && /* */) // 뒤에 오는 Expression과 무관하게 조건을 만족시키지 못함

• Ada의 경우, short-circuit evaluation이 적용되는 연산자와 적용되지 않는 연산자를 모두 제공
  • and then, or else - short circuit eval 버전
  • and, or - 무조건 eager eval 버전

Statement Level

Assignment Statement

• Assignment를 operator로 간주하는 언어도 있다 (C++)
  • -> cascading assignment 가능
  • a = b = 3;
• 언어에 따라 배열, Record와 같은 Aggregation에 대한 assignment를 지원할 수도 있다

I/O Statement

• 파일 또는 콘솔 I/O에 대한 Assignment로 볼 수도 있다!
• 대부분의 경우, 언어 라이브러리를 통해 지원된다

Explicit Sequence Control

• 기계어(Machine Code)로부터 유래됨!
  • goto
  • break, continue

Proper Program Theory

: 프로그램의 실행 흐름을 어떻게 가져가야 할 것인가? 어떤 프로그램이 "제대로 된" 프로그램인가?

Flowchart Nodes

: 어떤 Flowchart도 아래 세 타입의 노드와 간선들(arcs)로 표현될 수 있다

• Function Node
• Decision Node
• Join Node

Proper Program

• 입구가 하나 (1 entry arc)
• 출구도 하나 (1 exit arc)
• 입구로부터 모든 노드로 향하는 경로가 있고, 모든 노드에서 출구로 향하는 경로가 존재

Prime Program

• Proper Program이면서, 두개 이상의 노드를 가지는 Proper Subprogram을 분리해낼 수 없는 프로그램
  • A proper program which has no embedded proper subprogram of greater than 1 node
  • cannot cut 2 arcs to extract a prime subprogram in it

Composite Program

• Proper Program이지만 Prime Program은 아닌 프로그램
  • 즉, Proper Subprogram을 분리해낼 수 있는 Proper Program

Prime Decomposition

• 모든 Proper Program은 Prime Program들의 계층으로 분해될 수 있으며, 각각의 분해는 유일(Unique)하다
  • Every proper program can be decomposed into a hierarchical set of prime subprograms
  • This decomposition is unique, except for special case of linear sequence of functional nodes
  • 예외: function node 여러개가 이어져 있는 경우는 분해가 유일하지 않을 수 있다
• 4개 이하의 노드로 표현될 수 있는 가장 기본적인 Prime Program들은 일반적으로 프로그래밍 언어에서 사용되는 제어 구조와 일치함
  • The Prime Decomposition shows that primes up to 4 nodes are the useful programming language control structures.

Issue: Does this limit what programs can be written?

• Proper Program이 좋은 건 알겠는데, 작성 가능한 프로그램의 범위를 제한하는건 아닐까 하는 우려가 있었음
• -> 구조적 프로그램 정리가 해결

Structured Program Theorem

: 순차, 선택, 반복 세 가지 구조만으로 "모든" 계산 가능한 함수를 작성할 수 있다!

이론적으로, 계산 가능한 모든 종류의 프로그램을 작성할 수 있음이 증명됨
: Böhm-Jacopini Theorem (1966) | 구조적 프로그램 정리

• 프로그램: 튜링 머신으로 계산 가능한 함수
• 함수가 계산 가능하다:
  • 그 함수에 대응하는 알고리즘이 존재하며,
  • 그 알고리즘이 유한한 시간 내에 그 함수의 값을 계산할 수 있다

Structured Programming

: 3가지 기본 제어구조(순차, 선택, 반복)만을 사용해 프로그램을 설계!

• 프로그램 설계를 계층적으로
• 문장 순서가 곧 수행 순서가 되도록
  • GOTO에 의존하게 되면:
    • 프로그램 계층 구조를 알아보기 힘들어진다
    • 문장 순서가 수행 순서와 무관해진다
      • spaghetti code를 유발함
        ( 제어 구조가 스파게티처럼 꼬여있어서 이해하기 어려운 코드 )
• 특정 문장 그룹이 여러 용도로 사용될 수 있다
  • 이해하기 어려워짐
• GOTO-less programming

Sequence | Composition | 순차

: 문장(Statement)들이 놓인 순서대로 수행

• 복합문(Compound Statement): 여러 문장을 한 문장처럼 취급
  • begin, end
  • 블럭(Block)
    • 복합문의 일종
    • { stmt1; stmt2; ... }

Selection | Alternation | 선택

: 둘 이상의 문장들 중, 하나만 선택하여 수행

• Single Branch: if expr then stmt1
• Double Branch: if expr then stmt1 else stmt2
• Multiple Selection
  • case statement
    • switch - case
    • case - when
  • Jump Table을 통해 효율적으로 구현할 수 있다!
• Dangling Else Problem
  • else의 짝이 어떤 if인지가 모호해질 수 있다
    • sol 1: 가장 가까운, 짝 없는 if
    • sol 2: endif 구문을 강제

Repetition | Iteration | 반복

: 특정 문장을 0회 이상 반복해서 수행

• Simple Repetition
  • perform stmt K times
• Counter-Controlled Repetition
  • control variable을 활용 (counter)
  • for I := 1 step 2 until 30 do body
• Sentinel-Controlled Repetition
  • 임의의 조건을 검사
  • while condition do body
  • repeat body until condition
• Data-Based Repetition
  • foreach X in container do body
• Infinite Repetition
  • loop body
    • body에서 end loop같은 별도의 탈출 문장을 사용해야함

some notes

• 순차, 선택, 반복 세 가지 제어구조만으로 모든 프로그램을 표현할 수 있다는 것 뿐, 그렇게 표현하는 것이 최선이라는 것은 아님
  • 이론적인 가능성의 증명일 뿐이지, 변환 방법론은 아니다
  • 어떻게 지저분한 코드를 논리적으로 재해석하고 재설계할것인가 하는 문제를 해결해주는 것은 아님
• 또한, 스파게티 코드를 구조적 코드로 바꿀 경우 원래의 코드보다 비효율적이고 이해하기 어려운 코드가 될 수도 있다
• 주어진 상황에 맞는 최고의 알고리즘을 선택하는 것은 결국 프로그래머의 몫이다!