[Programming Language Pragmatics] 06 Control Flow(2)

(해당 강의노트는 Michael L. Scott의 [Programming Language Pragmatics: 4th edition] 책을 기반으로 작성되었습니다)

[06 Control Flow(2)] 6.1.3~6.3

Table of Contents

6.1. Expression Evaluation
- 6.1.3 Initialization

- 6.1.4 Ordering within Expressions

- 6.1.5 Short-Circuit Evaluation

 

6.2 Structured and Unstructured Flow

- 6.2.1 Structured Alternatives to goto

- 6.2.2 Continuations(수업에서 다루지 않음)

 

6.3 Sequencing

 

6.4 Selection

- 6.4.1 Short-Circuited Conditions

- 6.4.2 Case/Switch Statements

 

6.1.3 Initialization

- 절차지향 언어에서는 변수를 선언하면서 초기값을 항상 제공하는 것은 아님

- 이러한 초기 값들이 왜 유용한지에 대한 이유들

   1. 초기화를 하지 않는 상태에서 변수를 사용할 경우 에러(문제)가 발생할 확률이 높아짐

   2. 함수 안의 스태틱 변수는 초기값이 유용하게 사용되기 때문에 필요함

   3. 모든 정적할당 변수(스태틱 변수, 전역변수)들을 위해, 선언시 구체화된 초기 값은 런타임 때 컴파일러에 의해 전역 메모리에 우선 할당될 수 있음 (이는 런타임 시 초기 값을 할당하는 비용을 줄일 수 있음)

- 대부분의 언어들은 초기값을 지정할 수 있는 방법을 제공함 : built-in type

      - 더 complete, orthogonal(일관성)한 접근 방법이란?

     : 기본 타입인 정수형 실수형의 초기값 지정 방법을 제공한다면 aggregate(struct, union)에 대해서도 해당 방법을 제공해야 한다

- 초기화시 시간이 절약될 수 있는데 이는 정적 할당 변수들만 해당

: 런타임 시 스택 혹은 힙에 할당된 변수들은 런타임 때 반드시 초기화되어야 한다

- 초기화를 하지 않았을 경우에 생기는 문제점 (단순히 선언 시에만 문제점이 생기는 것이 아님)

1. 힙에 할당된 변수를 deallocation했을 때

: 아래와 같은 코드에서 p를 가리키고 있던 newp는 dangling pointer(허상 포인터)가 됨

int* p = (int *)malloc(sizeof(int) * 10);
int* newp = p;
free(p);

2. 초기값이 제대로 지정되지 않은 경우 union에서 적절하지 않은 접근이 일어날 수 있음

typedef struct {
    int type; /* 0: int, 1: float, 2: double */
    union {
   	int intValue;
    	float floatValue;
    	double doubleValue;
    } Value;
} UNION;

UNION u;
u.type = 0;
u.intValue = 3;
u.type = 2;
printf("doubleValue = %lf\n", doubleValue);

 

- 언어에 따라서는 초기값을 지정해주지 않을 경우 디폴트 값을 자동으로 지정해준다

   1. In C, 전역변수의 경우 초기값을 지정해주지 않아도 디폴트 값으로 0이 저장됨

   2. 자바, C#에서는 클래스 안의 멤버에서 디폴트 값을 지정

   3. 대부분의 스크립트 언어에서는 보통 디폴트 값을 초기값으로 지정해준다

 

 

Dynamic Checks

- 디폴트 값으로 초기화 값을 지정해주는 대신에, 언어에 따라서는 초기화 시키지 않은 변수에 대해서 semantic error를 발생시키기도 함

- 또한 해당 에러를 런타임에서 catch할 수 있음

- 해당 방법의 장점은? 디폴트 값으로 인해 종종 일어나는 오류를 방지할 수 있음 

-  적절한 하드웨어 지원이 있다는 가정하에 초기화되지 않은 변수를 체크하는 것은 디폴트 값을 지정해주는 비용과 비슷하다

    예1: IEEE 기반의 컴파일러에서 부동 소수점 계산시 초기화가 되어 있지 않을 경우 NaN(Not a Number) value임을 알려줌

    예2: NaN value 사용 시 하드웨어에서 이를 감지하고 semantic error message 발생

- 단 하드웨어 지원이 적절치 않은 경우, 비용이 증가하고 오버헤드가 발생할 수 있음

 

Definite Assignment

함수의 지역변수들을 위해, Java와 C#은 초기화되지 않은 변수의 사용을 preclude하는 definite assignment의 notion을 정의해준다

- 표현식의 control path의 모든 가능성은 반드시 해당 표현식 안의 모든 변수에 값을 할당해주어야 한다

- 이를 conservative rule(보수적인 룰)라고 함 : 단 이를 항상 catch 할 수 있는 것은 아님

- 코드 예

: 아래의 경우 j > 0 일 때 i에 2가 저장이 되고 이 경우에만 i값을 출력시키나 컴파일러의 경우 이를 캐치하지 못하고 오류를 발생시킴

public void static main(String[] args){
	int i;
	int j = 3;
…
	if (j > 0) 
    	i = 2;

…            // no assignments to j in here
	if (j > 0) 
   	// error: "i might not have been initialized"
    	System.out.println(i);
}

 

Constructors : 생성자

많은 객체지향 언어들에서(Java, C# 등)는 동적으로 할당된 변수들이 자동적으로 초기화되는 define type을 프로그래머에게 허용함

(심지어는 선언안에서 초기값이 구체적으로 없을 때도 가능)

 

c++에서 주의할 점 : initialization(초기화) 와 assignment(할당)을 주의깊게 구분하는 점

- initialization은 변수의 타입을 위해 생성자 함수를 호출하는 것으로 해석됨

ex1 : ) Atype a = new Atype(); 

ex2 :) Btype b = new Btype(3); // with the initial value as an argument

- 자동형변환(coercion)이 부재할 경우, 할당은 타입의 할당 연산자를 호출하는 것으로 해석한다

    - 만약 정의되어 있지 않을 경우, 오른쪽 값에서 왼쪽값으로의 단순히 bit-wise copy가 일어나는 것으로 해석

- 초기화와 할당의 구분은 사용자 정의 추상 데이터 타입을 위해서 특히 중요하다.

 

반대로 자바와 C#의 경우에는 이를 구분하지 않음

- 초기 값은 선언 시 주어질 수 있는데, 이는 immediate subsequent assignmet와 같다고 볼 수 있다.

- 자바는 참조 모델을 모든 사용자 정의 객체 타입의 변수와 자동 저장 reclamation을 위해 사용한다

   - 따라서 할당은 절대로 값을 카피하는 형태로 일어나지 않는다

- C#은 프로그래머가 원할 때 value model을 구체화하는 것을 허용하나 자바는 반대로 mirror의 형태로 지원

 

 

6.1.4 Ordering within Expressions

precedence와 associativity rule은 표현식 내에서 적용된 이진 infix 연산자의 순서를 정의함

- 단,  평가된 주어진 연산자의 피연산자의 순서를 구체화하는 것은 아님

- a - f(b) - c * d

- 위의 식에서와 같이 c * d  이후의 연산 순서를 알지 못함

 

여러 개의 인자를 받는 함수 호출에서도 비슷하게 일어남

 - f(a, g(b), h(c))

- 어떤 인자 순으로 처리될 지 우리는 순서를 알지 못함

 

순서가 왜 중요한 지에 대한 두 가지 이유가 있음

1st. Side effects

- 기대하지 않는 effect 가 발생하는 경우 이를 모두 side effect라고 함

 

2nd. Code improvement

- 서브 표현식의 평가의 순서는 레지스터 할당과 명령 스케줄링 모두에서 영향을 미친다

- code improvement의 중요성 때문에 대부분의 언어가 피연산자와 인자의 연산 순서를 정의해놓지 않음

- 단, 자바와 C#은 예외적으로 순서를 정해 놓음 : left-to-right

- 강제적인 순서의 부재는 컴파일러가 더 빠른 코드로 선택할 수 있는 결정권을 준다 

- code 예

: 메모리에 있는  보다 d가 접근속도가 빠르기 때문에 d*3을 먼저 계산하는 것이 좋음

즉, 정해진 순서가 있을 경우 속도가 늦어짐 -> 따라서 명령 스케줄링에 따라 접근성이 더 좋은 변수 먼저 계산하도록 해야함

a := B[i];
c := a * 2 + d * 3;

 

Mathematical Identities 적용

- 몇몇 언어 구현에서는 컴파일러가 연산자와 관련된 표현식을 재배열하는 것을 허용함

   - mathematical abstraction은 빠른 코드를 생성하기 위해서 commutative(교환), asscociative(결합), distributive(분배)을 포함

 

- 아래의 Fortran fragment를 생각해보자

a = b + c
d = c + e + b

- 몇몇 컴파일러는 이를 아래와 같이 재배열한다

a = b + c
d = b + c + e 

- 컴파일러들은 첫 번째와 두 번째 문장안에서 흔히 사용되는 서브 표현식들을 인식하고, 아래와 같이 동일한 연산을 수행하는 코드를 생성할 수 있다

a = b + c
d = a + e

- 불행히도, 수학적 연산에서는 결합, 분배, 교환 법칙이 모두 가능하나 컴퓨터 연산에서는 다 가능하지는 않다

: 컴퓨터는 숫자에서 범위가 정해져 있기 때문 (int 4byte, double 8byte ...)

 

 

파스칼을 포함한 대부분의 파스칼 계승 언어들은 산술 overflow을 감지를 확인하기 위해서 dynamic sematic을 제공한다

반대로 몇몇 언어들에서는 run-time overhead를 체크해주지 않음

언어 release 순 : C < C++ < JAVA < C#

- C, C++에서는 산술 오버플로우의 효과를 완전히 구현자의 의존해서 확인해야 함

(컴파일러마다 int, float 의 크기가 다름; int < float 만 정해져있고 크기는 정해지지 않음)

- 자바에서도 오버플로우 체크해주지 않음 : 단, C언어와 다르게 타입별 사이즈가 구체적으로 정해져 있음

- C#에서는, 오버플로우 체크를 checked/unchecked 키워드를 통해 선택할 수 있음(defualt는 unchecked)

- Shceme, Common Lisp나 스크립트 언어들은 정수의 크기 범위가 정해져 있지 않음(infinite 가능). 즉, overflow가 아예 발생하지 않을 수 있음

- 오버플로우가 아니라고 하더라도, 다른 문제가 발생할 수 있음 : 타입의 범위가 무한에 가깝게 크다고하여도 부동 소수점 연산의 limited precision은 같은 식에 있어서 다른 값을 도출해내는 정확도의 문제를 일으킬 수 있음(0.1 을 0.098, 0.099 정확도 차이) 

 

6.1.5 Short-Circuit Evaluation

Boolean expression은 코드와 가독성 향상을 위해 특별하고 중요한 기회를 제공한다.

(a < b) && (b < c) 표현식을 생각해보자

- 만약 a 가 b보다 크다면? (b < c) 뒤에 식을 볼 필요도 없다

- 마찬가지로, (a > b) || (b > c)의 표현식에서도 a가 b보다 크다면 (b > c)뒤에 식을 보지 않아도 됨

 

위의 예처럼 이러한 역할을 컴파일러가 수행하는데 이를 [short-circuit evaluation]이라고 한다

short-circuit evaluation이 유용하게 쓰이는 예시

if ( very_unlikely_condition && very_expensive_function()) ....

일 경우 일어날 가능성이 희박한 조건을 앞에 두고, 연산량이 큰 함수를 뒤에 둠으로써 short-circuit evaluation을 통해 코드 효율성을 높인다

 

Short-Circuit은 Boolean 표현식의 semantic을 변경할 수 있다.

C언어에서는 아래와 같은 코드로 리스트에서 요소를 찾을 수 있다.

p = my_list;

while( p && p->key != val) // p!= NULL 이어야 다음 조건문 확인
	p = p->next;

 

pascal은 short-circuit이 없음(에러 코드)

p := my_list;
while (p <> nil) and(p^.key <> val) do (* ouch! *)
    p := p^.next; 

 

위에 코드를 올바르게 고친 버전(short-circuit을 지원하지 않으므로 코드가 굉장히 복잡해짐)

- 따라서 이후 언어들은 short-circuit을 지원하는 방식으로 바뀌게 됨

p := my_list;
still_searching := true;
while still_searching do 
    if p = nil then
        still_searching := false
    else if p^.key = val then
        still_searching := false
    else
        p := p^.next

short-circuit evaluation은 또한 out-of bound subscript를 피하기 위해서도 사용됨

const int MAX = 10;
int A[MAX]; /* indices from 0 to 9 */
…
if (i >= 0 && i < MAX && A[i] > foo) …

0으로 나눈 경우 :

if (d == 0 || n / d < threshold) …

 

short circuiting이 적합하지 않은 상황 역시 있음

- 몇몇 언어들은 regular 와 short-circuit boolean 연산자를 둘 다 포함한다 (예: Ada)

   regular Boolean operators: and, or

   short-circuit versions : and then, or else

 

6.2 Structured and Unstructured Flow

goto statement

- 예전에는 많이 썼는데 최근에서는 goto문을 쓰지 않으므로 패스

- 60/70년대 이후 언어 부터 structured programming(C언어 등)이 등장하여 goto가 필요없어지게 되며 중요성 하락

 

Structure programming emphasizes

- top-down 디자인

- 코드의 모듈화

- 구체화된 타입

- descriptive variable 과 constant names

- extensive commenting conventions

6.2.1 Structured Alternatives to goto

예로 Mutilevel Returns이 있음

function search(key: string) : string;
var rtn : string;
…
  procedure search_file(fname : string);
  …
  begin
    …
    for … (* iterate over lines *)
      …
      if found(key, line) then begin
        rtn := line;
        goto 100; // goto문 어쩔 수 없이 사용
      end;
      …
  end;
…
begin (* search *)
  …
  for … (* iterate over files *)
    …
    search_file(fname);
    …
100: return rtn;
end;

C/C++계열에서도 goto 문을 통해 코드를 줄일 수 있음(자바에서는 아예 goto 키워드를 삭제, 대신 break문에 레이블 추가 가능)

while(){
	while(){
    	//break; 할 경우 in-loop만 빠져나옴
        //goto 를 사용하여 한 줄 코드로 out-loop까지 빠져나올 수 있음
    }
}

 

 

6.3 Sequencing

- Sequencing(순차 실행)은 절차지향 프로그래밍의 핵심임

- 할당에 있어서 side effect가 일어날 수 있음 

- 대부분의 절차 지향 언어에서는 begin...end나 {}중괄호를 이용해서 compound statement를 만들 수 있음

  (compound statement : 원래는 한줄씩이 코드인데 {}등을 이용해서 한 코드 블럭 취급하는 것)

 

절차지향 언어에서는, side effect의 certain kind의 값을 사용할지/말지에 대한 논쟁이 있음

- Euclid, Turing 언어에서는 함수 안에서 side effect가 발생하지 않도록 아예 제한을 둠

: 값을 반환하는 함수에서 side effect를 발생하지 않도록 함, 예로 전역변수 수정이 함수내에서 불가능 즉, 독립적으로 함수를 수행하도록.

 

- side effect를 사용할 때 높은 효율을 보이는 코드

: random number 생성하는 코드의 경우 rand는 호출 시마다 다른 값을 리턴해야 하므로 side effect가 필요함, 

(우회해서 side effect를 사용하지 않고도 코드를 짤 수 있기는 하지만 아래처럼 차라리 rand()함수를 써서(side effect사용)하는게 더 유용)

void label_name(char* s) {
    static short int n;
    sprint(s, "L%d\n", ++h);
}

procedure srand(seed : integer)
  -- initialize internal tables
  -- the pseudorandom generator will return a different 
  -- sequence of values for each different value of seed

function rand() : integer
  -- no arguments; returns a new "random" number

- Ada는 둘 다 허용 함

   1) static, global variable 사용은 허용

   2) 그러나 파라미터를 함수안에서 수정하는 것을 불가

 

6.4 Selection

대부분의 절차 지향언어에서의 selection statement은  Algo60에 영향을 받아 if...then...else로 만들어짐

 

Algol60, Pascal에서는 then caluse와 else caluse 둘 다 뒤에는 single statement만 가능하게 함

: compount statement를 사용하면 여러개의 statement를 포함시키는게 가능함

 

Algol 60은 then clause다음에 또 다른 if문 시작이 불가능하게 되어 있음

 

Pascal에서는 위에서와 같이 제한된 조건을 해결함

: disambiguating rule로, else문이 가장 가까운 then clause와 연결

 

이러한 모호성을 막기 위해서 terminating keyword를 쓰는 방법도 있음

: if()를 쓰고 나서 끝낼 경우 end()키워드로 마무리

단 이 경우, if()문을 쓸 때마다 end()를 써야하므로 코드가 길어짐, 중복성 증가 -> if...elif....else로 간결하게 작성하도록 바뀜

 

6.4.1 Short-Circuited Conditions

Short-Circuited Conditions은 효율적인 코드 작성을 가능하게 함

아래와 같은 코드를 작성한다고 가정해보자

if ((A > B) and (C > D)) or (E != F) then
    then_clause
else
    else_clause

short-circuit evaluation을 사용하지 않은 언어의 예(어셈블리어)

short-circuit evaluation을 사용한 언어의 예

 

6.4.2 Case/Switch Statements

Algol W에서 만들어진  case statement는 if...then...else의 스페셜 버전이라고 생각하면 됨

주로 compile-time 비교를 위해 사용됨

if 문보다 case 문을 사용할 경우 코드를 더 간결히, 효율적으로 사용 가능

 

Target code(if statements) vs. Case Statements

 This code replaces the last three lines of Figure 6.3( 어셈블리어)