06. Control Flow - (2)

6.1.4 Ordering within Expressions

우선순위, 결합법칙 적용 시, 값을 언제 가지고 올 것인가?

• f(a, g(b), h(c)) : 어떤 인자 순으로 처리되는 지 순서를 알 수 없다.

순서가 중요한 이유?

• Side effects a - f(b) - c *d : 연산의 경우, f()함수 실행시 다른 변수의 값을 변경할 수도 있다.
  
• Code improvement 최적화 관련해서 register 할당, instruction scheduling에 영향 미침

1. a*b+f(c) 의 경우 - a, b의 값 레지스터에 저장, f 함수 실행하면서 이미 할당했던 레디스터를 사용할 수도 있다. → 차라리 f 함수 먼저 실행
2. 

→ a 가 좀 더 시간이 걸린다 (d는 메모리에서 바로 가져오지만 a는 특정 연산이 필요하기 때문) → d*3을 먼저 계산하는 것이 좋다.

→ 즉, 정해진 순서가 있다면 속도가 느려질 수 있으므로 접근성이 좋은 변수 먼저 접근하도록 하도록 해서 순서를 정해두지 않는다.

• 대부분의 언어들은 코드 최적화로 인해서 순서를 정해두지 않는다.
• 자바, C#은 예외적으로 순서 정해둠 (왼 → 오)
• 강제적인 순서가 없다면 컴파일러가 빠른 코드를 선택할 수 있는 결정권을 준다.

Applying Mathematical Identities

• 컴파일러가 코드 최적화를 위해 연산자와 관련된 표현식을 재배열하는 것을 허용한다.

• 수학에서는 결합, 분배, 교환 법칙은 모두 가능하지만 컴퓨터 연산에선 다 가능한 것은 아니다 (범위 정해져있기 때문에 범위를 벗어날 수 있다.)
• 파스칼을 포함한 파스칼 계승 대부분의 언어는 dynamic sematic을 제공한다. = 오버플로우 발생하는지 실행 중에 확인한다.
  • 일부 구현체에서는 sematic check 무시한다. -> runtime overhead 발생할 수 있다.
    • C, C++: 구현한 사람 알아서 → int : short보단 크고 Long보단 작다
    • 자바: 타입의 범위가 명확하게 정의되어 있음 → int: 32bit
    • C#: checked/unchecked 키워드로 선택가능
    • Scheme, Common Lisp, Python: 정수에 큰 제한을 두지 않는다.
  • 오버플로우 뿐만 아니라, 저장 공간으로 인해서 오류 발생 (0을 기대했는데, 0.00001이 나오는 정확도 떨어지는 문제) → 즉, 무작정 순서를 바꿔서는 안된다.

6.1.5 Short-Circuit Evaluation

: Boolean expression: 코드 최적화, 가독성 향상

1. (a<b) && (b<c) : 앞의 값으로 인해 전체 결과를 유추할 수 있으면 뒤의 연산은 하지 않을 수 있다. 즉, 코드 최적화 가능
   • C언어 지원, Pascal 지원하지 않음 첫 번째 연산 후, 두 번째 연산도 진행하므로 오류가 발생할 수 있다.
     
2. if (i >= 0 && i < MAX && A[i] > foo): 범위 확인

But short circuiting 이 적합하지 않은 상황 존재

: Side effect로 인해 꼭 연산이 진행되어야하는 경우 존재

Ada에서는 두 가지 버전을 제공한다.

• regular Boolean operators: and, or
• short-circuit versions: and then, or else

6.2 Structured and Unstructured Flow

goto statement

• 거의 사용하지 않는다.
• break, continue 와 같은 키워드가 유사 기능
• structured programming 에서는 많이 사용
  • top-down design
  • c언어
• sequencing, selection, iteration을 통해 goto 없이 사용
• label 을 통해서 이동
• 조건문, 반복문 내에서 사용하듯 제한된 영역에서 사용하도록 한다.

6.2.1 Structured Alternatives to goto

써도 좋을 경우?

• 함수 안에 함수 존재
• C언어: 이중 루프 사용시 전체를 빠져나가고 싶을 때
• Java: 키워드만 존재함

6.3 Sequencing

imperative programming 에서 중요한 concept

• 절차지향 언어에서 begin end 나 코드블럭 {}을 이용해 compound statement를 만든다. → 한 문장을 예상하지만 코드블럭이 들어갈 수 있도록 해줌.
  

절차지향에서 side effect의 certain kind의 값을 사용할지 논쟁이 존재한다.

• Euclid, Turing 언어에서 함수는 side effect가 발생하지 못하도록 한다 (전역 변수 수정 등 못함, 결과만을 반환)
  • idempotent 하게 만든다. : 입력이 들어가면 항상 출력이 같아야 한다.
  • 반복적 호출 가능, 일정한 값 반환
• rand는 seed number을 변경해야하므로 side effect가 바람직한 경우도 있다.
• Ada에서는 static, 전역 변수 변경은 허용하고, 파라미터를 함수 안에서 수정하는 것은 허용하지 않는다.

6.4 Selection

• Algol 60, Pascal 의 경우, then else 뒤에 single statement 가능, compount statement 사용
• Algol 60: then 다음 if 불가능
• Pascal: else와 가장 가까운 then과 연결
  • 모호한 경우 존재, end 키워드로 마무리
• elsif, elif 키워드 사용함

6.4.1 Short-Circuited Conditions

• 만약 boolean 의 경우, register에 넣지 않고 branch 분기함
  • 값 계산하고 레지스터 넣고, t/f 인지 확인하는 과정이 필요없음
• 어디로 jump할 것인지 확인

6.4.2 Case/Switch Statements

• if...then...else 의 특별한 버전

• 코드가 더 간결하고 효율적이다.
  

• 코드가 어디로 가야하는지 계산부터 함

  • 배열처럼 인덱스를 만들어두고 계산 결과에 맞게 이동하도록 한다.
  • 메모리는 더 크게 사용하지만 속도는 향상시킬 수 있다.

6.5 Iteration

• Imperative languages: 재귀보단 반복을 많이 쓴다.
• side effect를 발생하기 위해서 실행된다.

Enumeration-controlled loop

• 유한 집합: 한개의 요소 실행
• 첫 iteration이 시작되기 전에 몇 번의 반복이 일어나는지 알 수 있다.

Logically controlled loop

• 횟수가 정해져 있지 않고, 조건이 만족될 때까지 반복한다.
• boolean에 의해서 제어

6.5.1 Enumeration-Controlled Loops

• python의 range
  

do i = 1, 10, 2 
...
enddo

• 대부분의 현대 언어들은 컬렉션의 요소에 접근할 수 있도록 한다 (for each)

• r1이 r3보다 크면 반복문 빠져나간다.
• 아니면 r2만큼 증가, 증가 후 다시 반복

• goto를 한번만 사용할 수도
• 컴파일러가 옳은 선택을 하기 위해서 연산 순서의 일반화에 제한을 둔다.
  • step에 변수가 아닌 상수값으로 지정
  • Ada +-1만 가능
  • 키워드를 다르게 넣어서 -1 연산을 함

Semantic Complications

• number of iterations 예상 가능하는 데에 의존적이다.
• 예측 가능 vs 예측 불가
  • enumeration을 중점으로 생각한다면 예측 가능이 유용
  • 중간에 값이 바뀐다면? for (int i = 0 ; i<10 ; i++) i++;

Problem

(1) 반복문 실행 중 들어갈 수 있는가? → goto 사용
(2) bound를 수정한다면?
(3) loop body에서 인덱스 수정하는 경우?
(4) 반복문이 종료된 후 index 사용하는 것이 의미 있는가?

Solution

(1), (2)

break 를 이용해서 for loop를 나갈 수 있다.(일반적) goto 로 들어갈 수 있다

bound 한 번 계산, 임시 저장 → 중간에 바꾸더라도 영향미치지 않음

(3)

index 변경 대부분 허용하지 않는다.

• Fortan: 프로그래머가 알아서 하도록
• Pascal: 컴파일러가 강제 금지

(4)

break, exit를 사용해서 나온 경우는 빠져나온 순간의 index

제대로 종료되었다면, loop bound를 초과하는 첫번째 index

• 다음 값이 overflow 발생한다면?
  • 루프의 시작 부분에 index의 선언을 하도록 한다 → scope 종료 자동 소멸 for (int i ) ~~
    

6.5.2 Combination Loops

Algol 60: 현대의 enumeration, logically controlled loops 둘의 특징을 아우름.

//for
for (i = first; i <= last; i+= step){
}

//while
{ 
	i = first;
	while (i <= last) {
	        ...
		i += step; 
	}
}

• C언어에서의 for 은 While과 유사
• overflow에 대해서는 프로그래머에게 달려있음
• 반복문 내에 i 변경 가능
• for( ; ; ) 가능
• comma 허용 - for(int i=0, j=1; i<10; i++,j++)
• c언어의 for이 while 보다 더 명확, 단순
• for 은 모두 header에 존재 → 가독성 좋음
• 인덱스 선언을 for 내에 함으로써 모호성 제거

6.5.3 Iterators

• for i in range(5) → [0,1,2,3,4]
  • 순서를 가지고 있는 요소들을 하나씩 가지고 온다.
• python: range object 사용/ java: interface 있어야 사용 가능

True Iterator

• interface를 사용하지 않고 언어에 녹아들어가있는 경우
• Clu, Python, Ruby, C#
• yield statement: 반복문 사용시 상태 기억함
• For loop

for i in range(first, last, step):
	...

• iterator는 이미 결정된 요소들을 실행한다.
• 첫 번째 idx 먼저 계산 → main program에 yield statement로 return한다.
• 더 이상 iterator에 남아있는 요소가 없다면 loop를 종료한다.

Decouple

• 알고리즘과 코드를 분리한다.
• ex) collection : tree or list → 자료구조와 상관없이 iterator를 적용한다.
• return: return을 한다면 이전 상태는 날라감
• yield: 현재 어디까지 왔는지 상태 저장해둠

Iterator Objects

• Iteration 은 for each와 같은 special form, loop를 위한 enumerate value를 하는 메카니즘 모두를 포함한다.
• 유클리드, C++, Java, Ada 2012

  • yield 가 없음

  • 초기화 (생성자), 다음 인덱스 생성(hasNext(), next()) 등을 구현해둔 클래스

  • 함수 호출될 시, 객체의 데이터 멤버가 어떤 값을 가지고 있는지 저장한다. (Stack)

    BinTree<Integer> myTree = ... ...
    for (Integer i : myTree) { //syntax sugar
        System.out.println(i);
    }

6.5.5 Logically Controlled Loops

: 조건에 의해 반복문 실행

• 반복문 종료 조건이 어디에 위치해야 하는가?
• 대부분 종료 조건은 반복을 실행할 때마다 확인

Pre-test loop

while condition do statement

Post-test loop

do { //적어도 한 번 보장
	line = read_line(stdin);
} while (line[0] != '$'); //c언어에서는 조건문 동안

Mid-test Loops

for (; ;) { 
	line = read_line(stdin); 
	if (all_blanks(line)) break; //중간에 멈춤
	consume_line(line);
}

6.6 Recursion

• recursive ↔ iterative
  • 변환 가능하다.

6.6.1 Iteration and Recursion

• Fortan 77과 같은 언어는 recursion을 허용하지 않았다.
  • 스택을 사용하지 않는 언어일 경우
• 함수형 언어는 iteration을 허용하지 않았다.
• 절차형 언어: iteration이 더 natural, 변수를 반복적으로 수정하는 것에 익숙함 (side effect)
• 함수형 언어: recursion이 더 자연스러움

Tail Recusion

• recursion 보다 iteration을 사용하는 것이 더 효율적이라는 논쟁이 있음
• 알고리즘을 대충 구현했을 때 iteration이 recursion보다 효율적이다.
  • 함수를 새로 호출할때, 가지고 있던 레지스터 내용을 메모리에 옮기고 새로운 내용을 추가하고 등등 과정을 거친다면 효율성이 떨어진다.
• 최적화 컴파일러는 recursive function을 iteration과 동등한 효율성을 낼 수 있다.

Tail-Recusive function

• 재귀호출을 한 후 다른 computation이 없는 경우 (return 값이 최종 결과인 경우), 최적화 가능
  • tail recursive 하지 않는 함수도 tail recursive하게 바꿀 수 있음
  • 실행시점에 동적 할당된 스택 공간이 필요없이, 사용중인 공간을 재사용하면 된다.

6.6.2 Applicative- and Normal-Order Evaluation

• 함수에 argument가 전달될 때, 먼저 evaluate 된다고 암묵적으로 가정했다. f(2,3,g(a)) : g(a)의 값을 아는 상태로 넘긴다.
  • 그냥 g(a) 그대로 전달해도 되진 않을까?
• Applicative-order evaluation: 전부 다 호출하기 전에 evaluate
  • 런타임 에러 발생
• Normal-order evaluation: 값이 필요할때 evaluate
  • ex) 매크로 함수에서 치환하듯
  • short-circuit Boolean evaluation, call-by-name parameters
  • Algol60에서는 default로 사용했다
  • 빠른 코드로 연결
  • 아예 필요 없으면 evaluate 하지 않음
• Lazy Evaluation: normal-order evaluation에 해당
  • 효율성, 명확성 관점에서 applicative-order가 낫고 이 방식을 사용

6.7 Nondeterminacy

• 의도적으로 명확하게 정의하지 않는 경우

• f(a) + g(b) 의 경우 어떤 함수가 먼저 evaluate 하지 않음

  → 컴파일러가 최적화하기 위해서