[PLT/프로그래밍언어론] 06. Control Structure

 

06. Control Structure

#PLT

제어 구조

표현식

• 표현식(Expression)은 평가가 완료되면 값을 생성하거나 정의되지 않음을 생성하는 구문적 단위입니다(완료되지 않는 경우).
• 표현식은 모든 프로그래밍 언어의 기본 구성 요소 중 하나입니다.
• 함수형 언어처럼 문(statement)이 없는 언어도 있지만, 표현식은 모든 언어에 존재합니다.

표현 방식

• 연산자와 피연산자로 표현합니다.
  • 예: x + y, b - 1, f(3) >= 0
• 전위(prefix), 중위(infix), 후위(postfix) 표기법이 있습니다.
• 연산자의 위치에 따라 다음과 같은 구문이 있습니다:
  • <prefix> ::= <op><prefix><prefix>|...
  • <infix> ::= <infix><op><infix>|...
  • <postfix> ::= <postfix><postfix><op>|...

표기법

• 수학적 식을 예로 들어보겠습니다: a + b * c + d
• 중위 표기법에서는 (a + b) * (c + d)와 같은 방식으로 연산합니다.
• 전위 표기법(또는 prefix Polish 표기법): * + a b + c d
  • Cambridge Polish 표기법으로, 연산자를 괄호 안에 넣는 방식도 있습니다: (* (+ a b) (+ c d))
• 후위 표기법:
  • a b + c d + *

의미론

• 표현식의 의미론(또는 평가 방법)은 표기법에 따라 달라질 수 있습니다.
• 예를 들어, 괄호가 없는 중위 표현식은 평가 과정에서 모호함을 초래할 수 있습니다.
  • a + b * c + d
  • a + (b * c) + d? 또는 (a + b) * (b + c)?
• 중위 표기법에서는 연산자의 우선순위(Precedence)와 결합법칙(Associativity)을 고려해야 합니다.

우선순위

• 연산자의 우선순위는 어떤 연산자를 먼저 계산해야 할지를 결정합니다.
• 이러한 우선순위는 표현식의 평가가 우리의 직관에 맞도록 정의해야 합니다.
  • 1 + 2 * 3의 값이 7이 되기를 원하지, 9가 되기를 원하지는 않습니다.
  • 1 + (2 * 3) = 7 vs. (1 + 2) * 3 = 9
• 이러한 경우를 방지하기 위해 우선순위 규칙이 필요합니다.

결합법칙

• 그러나 우선순위만으로는 표현식을 올바르게 평가할 수 없습니다.
• 연산자의 결합법칙(Associativity) 또한 고려해야 합니다. 이는 연산자가 피연산자와 어떻게 결합하는지를 알려줍니다.
  • 예: 10 - 5 - 3
  • (10 - 5) - 3 = 2 vs. 10 - (5 - 3) = 8
• 대부분의 산술 연산자는 왼쪽에서 오른쪽으로 결합하지만, 예외적으로 거듭제곱 연산 같은 경우가 있습니다.
  • 예: 5^3^2 ➞ 5^(3^2) vs. (5^3)^2

우선순위와 결합법칙

• 대부분의 프로그래밍 언어는 직관적인 우선순위와 결합법칙을 가지고 있습니다.
• 코드를 작성할 때 이를 주의 깊게 고려해야 합니다.
• 의심이 가면 괄호를 사용하여 의도를 명확하게 해야 합니다.
  • 예: (1 + 2) * 3, (10 - 5) - 3, (5^3)^2
• 괄호를 잘 사용하면 코드의 가독성이 높아집니다.

전위 표기법

• 중위 표기법과 달리, 전위 표기법(prefix notation)은 연산자의 피연산자 수(arity)를 알고 있다면 모호함이 없습니다.
• 우리는 스택과 카운터를 이용하여 접두 표현식을 평가하는 간단한 알고리즘을 생각할 수 있습니다.
  • 예: * + a 2 + b c
  • 변수 a = 1, b = 2, c = 3

Counter는 operands의 수를 체크하기 위해 필요하다.

전위 표기법의 평가 방법

• 카운터 C의 초기값은 0입니다.
• 각 기호를 스택에 푸시(push)합니다.
• 연산자를 만나면 C 값을 연산자의 피연산자 수(arity)로 업데이트합니다.
• 피연산자 기호를 만나면 C 값을 감소시킵니다.
• 만약 C = 0이 되면, 연산자를 적용하여 결과값을 스택에 저장하고, 계산된 기호들을 삭제합니다.
• 새 연산자를 위해 C를 업데이트합니다.

 

 

후위 표기법

• 후위 표기법(postfix notation)은 더 간단합니다.
• 왼쪽에서 오른쪽으로 기호를 읽으면서, 연산자를 만날 때마다 앞의 기호에 연산을 적용합니다.
  • 예: a b + c d + *에서 a = 1, b = 2, c = 3, d = 4
  • 계산 과정: a b + c d + * ➞ 3 c d + * ➞ 3 7 * ➞ 21

구문 트리 사용

• 표현식을 구문 트리(Syntax Tree)로 분석하고, 다른 순서로 트리를 순회할 수 있습니다.
• 비단말 노드는 연산자이고, 단말 노드는 피연산자입니다.
  • 예: a + b * c + d
  • 중위, 전위, 후위 순회를 할 수 있습니다.

In-order는 모호하지만, Pre-order와 Post-order는 명확하다.

표현식 평가

• 수학적으로는 a - b + c와 a + c - b는 동일한 결과를 가지지만, 프로그래밍 언어에서는 부분 표현식 평가 순서가 결과에 영향을 미칠 수 있습니다.
• 따라서 우리는 부분 표현식 평가 순서를 신중히 고려해야 합니다.
• 우리가 조심해야할 여러 이유가 존재한다.

부작용

• 명령형 언어에서는 평가 자체가 변수의 값을 변경할 수 있습니다. 이를 부작용(side effect)이라고 합니다.
  • 예: (a + b++) * (c + b--)
  • (a + f(b)) * (c + f(d))
    • 함수에서 전역변수를 바꾸는 것 같은 영향
  • 프로그램의 상태를 변경하는 코드 구성 요소가 부작용을 갖는다고 말할 수 있습니다.

유한 산술(Finite Arithmetic)

• 컴퓨터에서 숫자는 유한한 범위 내에서만 표현됩니다.
  • 예를 들어, C 언어에서는 short, int, long 등의 정수형 자료형이 다양한 범위의 정수를 표현할 수 있습니다.

• 만약 연산 결과가 범위를 초과하면 오버플로나 언더플로가 발생합니다.
  • a-b+c (a-b)+c vs (a+c)-b, a> b > c
  • a가 int타입 최댓값을 갖는다면 (a-b)는 괜찮지만, (a+c)는 OF발생

정의되지 않은 피연산자

• 연산자 적용에는 두 가지 전략이 있습니다: 조급한 계산법(eager evaluation)와 느긋한 계산법(lazy evaluation).
  • 조급한 계산법은 모든 부분 표현식을 먼저 계산한 후 연산을 적용합니다.
  • 느긋한 계산법는 나중에 부분 표현식의 평가를 결정합니다.
• 예: a == 0 ? b : b/a
  • 조급한 계산법에서는 먼저 모든 피연산자를 평가하려 하기 때문에 b/a에서 0으로 나누는 오류가 발생할 수 있습니다.
  • 그러나 조건에 따라 필요한 부분만 평가하면 문제가 발생하지 않습니다.
    • a == 0, then b or a!=0 then b/a

단락 평가

lazy evalutiona의 대표적 예시

• 단락 평가(short-circuiting)는 불필요한 부분 표현식을 평가하지 않도록 하는 기법입니다.
  • 예: if (str != null && str.length() > 0)
  • 첫 번째 조건이 만족되지 않으면, 두 번째 조건을 평가할 필요가 없습니다.
  • 반대로, 먼저 str.length()를 평가하면 문제가 발생할 수 있습니다.

---

코드 최적화

• 부분 표현식 평가 순서는 코드 최적화 관점에서 평가 효율성에 영향을 줄 수 있습니다.
  • 예: a = array[i]; b = a*a + c/d;
  • a는 메모리에서 값을 읽어야 하므로, c/d를 먼저 평가하는 것이 더 효율적일 수 있습니다.
  • 컴파일러가 최적화할 때 이런 것들을 고려한다.

문 (Statement)

• 문(statement)은 평가 시 반드시 값을 반환하지는 않지만, 부작용을 일으킬 수 있는 구문적 단위입니다.
• 모든 프로그래밍 언어에서 문이 존재하는 것은 아니지만, 일반적으로 명령형 언어(Imperative Language)에서 사용됩니다.
• 문을 실행(또는 평가)함으로써 프로그램의 상태를 계속 변경할 수 있습니다.
  • 예: print("Hello World!")

정의의 모호함

• 우리는 평가라는 용어를 사용했지만, 이는 정확하게 정의되지 않았습니다. 각 언어에서 표현식과 문의 역할이 다를 수 있기 때문입니다.
• 예를 들어, 어떤 언어에서는 표현식이 부작용을 가질 수 있고, 문이 값을 반환할 수 있습니다.
  • 예: C에서 할당문은 변수의 값을 변경하는 동시에 그 값을 반환합니다.
  • a = b = c;
• 주요 차이점은 평가 전에 상태가 고정되어 있는지 여부에 있습니다:
  • 표현식 평가의 결과는 값입니다.
  • 문 평가의 결과는 상태의 변화입니다.

변수의 개념

• 프로그래밍 언어에서 변수에는 두 가지 모델이 있습니다:
  • 수정 가능한 변수(Modifiable Variable): 값이 저장되는 컨테이너나 위치로 간주됩니다. 이 값은 할당문을 통해 수정될 수 있습니다.
  • 참조 모델(Reference Model): 변수는 메모리에 저장된 값에 대한 참조로 간주되며, 값을 담고 있는 것이 아닙니다.

• 수정 가능한 변수 모델에서는 변수 자체가 하나의 컨테이너입니다.
• 반면, 참조 모델에서는 변수는 단지 메모리 위치에 대한 참조일 뿐입니다.
• 이것은 변수의 개념일 뿐이며, 각 언어에서 구현 방식은 다를 수 있습니다.

할당

• 할당(Assignment)은 수정 가능한 변수에 연결된 값을 변경하는 문입니다.
  • 예:

    <assign> ::= <expr1><opAssign><expr2>
    

  • 에는 l-value를 사용하고, 에는 r-value를 사용합니다.
  • 예: x = 3; x = x + 1;
    • 왼쪽에서는 x의 l-value(변수의 위치)를 사용하고, 오른쪽에서는 x의 r-value(값 3)를 사용합니다.
• 참조 모델에서 할당이 어떻게 작동할까요?
  • 예: x = y
    • 이는 y의 값을 x에 복사한다는 의미가 아닙니다.
    • 대신, 이제 x와 y는 동일한 객체를 가리키는 두 개의 참조가 됩니다.
    • y를 수정하면 x를 통해서도 그 변화를 볼 수 있습니다.
    • 이것은 포인터 변수와 유사하지만, 참조 모델에서는 할당문을 통해서만 간접적으로 값을 수정할 수 있습니다.
    • 예: 자바(Java)에서 클래스의 변수는 참조 모델을 사용합니다.
      • 예:

        City c = new City("Seoul");
        

제어 흐름과 재귀

제어 흐름

• 프로그래밍 언어에는 여러 종류의 제어 흐름(Control Flow)가 있습니다:
  • 순차(Sequence): 문이 순서대로 실행됩니다.
  • 선택(Selection): 조건에 따라 문이 선택적으로 실행됩니다.
  • 반복(Iteration): 문이 반복적으로 실행됩니다.

순차 제어문

• 순차적 실행과 복합문:
  • 문장의 순서는 주로 세미콜론(;)으로 구분됩니다.
    • 예: S1 ; S2 ➞ S1이 종료된 후 S2가 실행됩니다.
  • 여러 문장을 그룹으로 묶어 복합문(Composite Statement)으로 만들 수 있습니다.
    • 보통 {}로 코드 블록을 만듭니다.

Goto 문

Unconditional jump

• 어셈블리어의 점프 명령과 유사한 명령문입니다.
  • goto Label
  • 프로그램 흐름을 Label로 즉시 점프합니다.
  • 이 문장을 조심해서 사용하지 않으면 "스파게티 코드"를 만들 수 있습니다.

스파게티 코드

• goto 문이 코드의 임의의 위치로 점프할 경우:
  • 프로그램의 실행 흐름을 추적하는 것이 매우 어렵습니다.
  • 점프 명령으로 연결된 코드 흐름을 시각화하면, 접시 속 스파게티처럼 얽힌 모습이 될 수 있습니다.

Goto 문 사용의 쇠퇴

• 현대 프로그래밍 언어에서는 goto 문이 더 이상 인기가 없습니다.
• goto 문은 특별한 경우를 제외하고는 사용하지 않는 것이 좋습니다.
• 대부분의 경우, return, break, continue와 같은 문으로 비슷한 동작을 구현할 수 있습니다.
• goto 문은 프로그래밍 언어의 발전 역사를 이해하는 데에 역사적 가치가 있지만, 이 강의에서는 세부 사항을 생략하겠습니다.

조건문

• 주어진 불리언 표현식을 평가하고, 그 값에 따라 문을 실행합니다.
  • 주로 다음과 같은 형식을 가집니다:
    • if <bool_expr> then C1 else C2
• 중첩된 조건문 처리:
  • if <bool_expr> then C1 else C2 endif
    • Using terminator

• if <bool_expr1> then C1 else if <bool_expr2> then C2 ... else Cn
  • Using else if for nested ones.

조건문 - Case 문

• Case 문 (또는 switch-case 문):
  • 여러 개의 분기를 처리합니다.
  • 표현식의 평가 결과에 따라 분기가 결정됩니다.
  • 각 은 constant value 또는 constant value들의 집합을 나타냅니다.
  • 분기가 많을 때는 if-else 문보다 효율적입니다.
  • 예:

    switch(<expr>) { 
        case <label1>: 
            S1;
            break; 
        case <label2>: 
            S2;
            break;
        ...
    }
    

Case 문 구현

• Case 문은 점프 테이블을 이용해 구현할 수 있습니다.
  • 점프 테이블은 각 분기를 위한 점프 명령을 포함합니다.
  • 의 값을 평가한 후, 점프 테이블에서 적절한 분기로 점프할 수 있는 오프셋을 얻습니다.

• 점프 끝 (break)이 없는 경우, 실행은 다음 분기로 이어집니다.
• 값의 범위가 넓으면 큰 점프 테이블이 필요할 수 있습니다.
  • 예: 0과 1000 두 개의 case만 있을 경우, 1~999에 해당하는 빈 공간이 필요할 수 있습니다.
  • 점프 주소는 해시 기법 등을 통해 계산할 수 있습니다.

점프 테이블은 컴파일 타임에 만들어지기 때문에 이 상수 값이어야 한다.

if문을 쓰면 n번을 거쳐야 하지만, switch-case를 쓰면 점프테이블로 가서 state로 이동하는 2step만 필요하다.

반복문

• 반복문(Iteration Statements)은 두 가지 주요 범주로 나눌 수 있습니다:
  • 무한 반복(Unbounded Iteration):
    • 보통 while 문으로 구현됩니다.
  • 유한 반복(Bounded Iteration):
    • 보통 for 문으로 구현됩니다.
• 반복문을 사용하면 언어가 튜링 완전성(Turing Completeness)을 가질 수 있습니다.
  • 즉, 모든 계산 가능한 알고리즘을 이 언어로 작성할 수 있습니다.

무한 반복(Unbounded Iteration)

• 무한 반복은 두 가지 요소로 구현됩니다:
  • 반복 조건과 반복 본문.
  • 예: while <bool_expr> do <statement>
  • 조건이 참으로 평가되는 동안 반복 본문이 실행됩니다.

유한 반복(Bounded Iteration)

• 유한 반복은 더 복잡한 구성 요소로 구현됩니다:

for i = <start> to <end> by step // step ex) i++, i+=2
do
	<statement> // <- body

• 변수 i는 인덱스, 카운터 또는 제어 변수입니다.
• i는 에 의해 수정되며, 은 0이 아닌 정수 상수입니다.
• 와 는 범위를 나타내는 표현식입니다.

유한 반복 vs 무한 반복

• "순수"한 유한 반복문은 많이 보이지 않습니다.
• 유한 반복에서는 반복을 시작할 때 반복 횟수를 알 수 있습니다.
• 그러나 무한 반복에서는 그렇지 않습니다.
  • 예: C에서 for 문은 순수한 유한 반복문이 아닙니다.

    for (int i = 0; i < n; i++) {
      ...
      n += 1;
    }
    

  • 반복문 body에서 조건을 업데이트할 수 있습니다.
  • 자바에서는 런타임 에러

    for (string s : strings) {
    	list.add(~~); // 리스트의 길이가 달라짐. 런타임 에러
    }
    

재귀

• 함수나 프로시저가 본문에서 자기 자신을 호출하는 경우, 이를 재귀적이라고 합니다.
• 재귀는 튜링 완전성을 얻는 또 다른 메커니즘입니다.
• 수학에서 재귀는 귀납적 정의로도 자주 나타납니다.
  • 예: 팩토리얼 함수

    
    factorial(n) =  1                       if n == 1
                   n * factorial(n-1)   otherwise (else)
    

프로그래밍 언어에서의 재귀

• 재귀는 반복에 비해 비효율적이라고 간주됩니다.
  • 함수가 자기 자신을 계속해서 호출하기 때문입니다.
  • 각 호출마다 새로운 활성 레코드(Activation Record)가 스택에 푸시되며, 여기에는 매개변수와 반환 값이 저장됩니다.
  • 예:

    int fact(int n) {
      if (n == 1) return 1;
      else return n * fact(n - 1);
    }
    

알고리즘이 지수적으로 증가하는 형태가 되버릴 수 있음

꼬리 재귀(Tail Recursion)

• 꼬리 재귀에서는 각 재귀 호출의 활성 레코드를 공유하여 효율성을 높일 수 있습니다.
  • 반환 값을 기다릴 필요 없이 재귀 호출의 반환 값만 반환하기 때문입니다.
  • 중간 결과를 저장하기 위해 새로운 변수를 도입할 수 있습니다.

• 꼬리 재귀는 추가 계산이 없기 때문에, 각 재귀 호출은 동일한 활성 레코드를 공유할 수 있습니다.
  • 재귀 호출은 동일한 코드를 수행하므로, 활성 레코드에 저장된 항목도 동일해야 합니다.
  • 각 재귀 호출마다 값을 업데이트하면 됩니다.
  • 예:

    int fact(int n, int acc) {
      if (n == 1) return acc;
      else return fact(n - 1, n * acc);
    }
    

절대 n에 비례해서 지수적으로 증가하지 않는다.

참고 : tail recursion 최적화는 컴파일러가 감지해서 알아서 해준다.

파이썬은 tail recursion을 지원하지 않으므로 주의해야 한다.

예시: 피보나치 수열 tail recursion

import time
#fib
start_time = time.time()
def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)
print("result of fib(40) : ", fib(40))
end_time = time.time()
print("fib(40) execution time = ", {end_time - start_time})
# fib_tr
start_time = time.time()
def fib_tr(n, pp, p):
    if n == 1:
        return p
    else:
        return fib_tr(n - 1, p, pp + p)

print("result of fib_tr(40) : ", fib_tr(40, 0, 1))
end_time = time.time() 
print("fib_tr(40) execution time = ", {end_time - start_time})

요약

• 표현식과 그 평가
• 문(statement)
• 제어 흐름 - 조건문, 반복문
• 꼬리 재귀