사람이 대화를 할 때도 뜻이 제대로 전달되기 위해서는 '순서'가 중요하다.
프로그래밍 언어에서는 이를 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 노드로 간주할 수 있음
'Computer Science > 프로그래밍언어론' 카테고리의 다른 글
기말 시험 준비 (0) | 2023.06.15 |
---|---|
Chapter9 Subprogram Control (0) | 2023.06.15 |
Chapter7 Inheritance (0) | 2023.06.13 |
Chapter6 Encapsulation (0) | 2023.06.13 |
Chapter5-2 Structured Data Types (0) | 2023.06.12 |