[Programming Language Pragmatics] 06 Control Flow(3)

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

[06 Control Flow(3)] 6.5~6.7

Table of Contents

6.5. Iteration
- 6.5.1 Enumeration-Controlled Loops 

- 6.5.2 Combination Loops

- 6.5.3 Iterators

- 6.5.4 Generators in Icon(패스)

- 6.5.5 Logically Controlled Loops

 

6.6 Recursion 

- 6.6.1 Iteration and Recursion

- 6.6.2 Applicative- and Normal-Order Evaluation

 

6.7 Nondeterminancy

 

6.5. Iteration

Iteration과 recursion 두 메카니즘은 비슷한 연산을 반복적으로 컴퓨터에게 수행시키는 것

절차지향 언어

- Iteration <-> recursion 즉, 한 쪽이 가능하면 다른 한 쪽으로 만드는 것이 가능

- 그러나 recursion보다는 Iteration(효율성 측면)으로 만드는 것이 나음

함수형 언어

- Iteration의 개념이 아예 없는 경우도 있음

- recursion을 더 많이 사용

대부분의 언어에서는  Iteration은 loop의 형태로 구현됨

- loop의 itertation은 일반적으로 side effect를 발생하기 위해 실행됨 : 변수 수정 및 할당

Loops 는 두 가지 종류가 있음

- 얼마나 반복시키냐에 따라 메카니즘이 다르게 결정됨

1) Enumeration-controlled loop

- 유한 집합(finite set) 안의 값을 한 개씩 이용 : 0~10 숫자 중 짝수를 더해라

- 첫 iteration이 시작되기 전에 몇 번의 반복이 일어날지 알 수 있음

 

2) Logically controlled loop

- 횟수가 정해져 있지 않고, 조건이 만족(혹은 만족되지 않을 때까지)될 때까지 반복 : while(true)

 

대부분의 언어는 이 두 가지 종류의 반복문에 대해서 다른 문법을 제공하고 있음

 

6.5.1 Enumeration-Controlled Loops

Enumeration-controlled iteration은 Fortan1의 do loop에서 기원

현대 Fortran version은 아래와 같음

- 변수 i는 loop의 인덱스

- i = 1(초기값), 10(bound), 2(step size)

다른 많은 언어들은 비슷한 기능을 제공함

최신의 언어들을 좀 더 일반적인 finite set을 반복하는데 사용 : 트리의 노드, collection의 element

"for loop"라고 대부분 부름

for loop로 코드 생성 예제

윗 코드보다 더 나은 버전 : jump를 한 번만 씀

이 경우 directional 함 : i가 작->큰데로 증가하고 있기 때문

만약 이 반대의 경우 루프를 반대로 테스트해봐야 함

 

컴파일러가 올바른 선택을 하게 하기 위해서, 많은 언어들이 그들의 연산 순서의 generality에 제한을 둠

- 흔히, step은 compile-time constant(상수값으로 정해져있어야 함)로 구성되어 있어야 함

- Ada에서는 +/-1 만 step에서 허용

- 몇몇의 언어들(Ada,Pascal을 포함한)에서는 "backward"라는 키워드를 필요로 함

Semantic Complications

1. enumeration mechanism을 사용 시, loop 중간에 들어가거나 나갈 수 있는가?

2. enumeration controlled loop에서 end-of-loop bound를 계산하는데 사용되는 변수를 body에서 수정하게 된다면?

3. index variable을 수정하게 된다면( for(i = 0; ..) 에서 i에 해당하는 변수) 어떤  일이 일어나는가?

4. 반복문이 종료된 후 index variable를 사용하는 것이 의미가 있는가?

 

질문 (1), (2)에 대한 답변

- 많은 언어들이 break/exit statement를 사용해 for loop를 일찍 빠져나가는 것을 허용

- Fortran IV에서는 loop안으로 들어가는 것을 goto를 이용해 jump를 가능하게 했으나, 이후 language flaw로 판단하여 Fortean77과 이후 많은 언어들에서 이러한 jump를 금지시킴

- 비슷하게, 많은 언어들에서(단, C는 예외) bound를 한 번만 계산하게 되어 있음. 즉, first iteration전에 반복문이 몇번 실행 되는지 계산하고 임시 저장소에 이를 저장하고 따름

 

질문 (3)에 대한 답변

- 이 경우 원래는 1,3,5,7,9 증가임

- 아래와 같이 if i = 3 조건문이 추가 된다면 i = 6이 된 i가 7로 갈 것인지 8로 갈 것인지에 대한 이슈가 있음

- 따라서 많은 언어들에서 loop index를  loop body안에서 수정하는 것을 금지 시킴

   - Fortan의 경우 강제는 아니고, 프로그래머가 알아서 잘 하라고 권고 사항임

   - Pascal의 경우에서는 컴파일러가 체크해 수정하는 것을 강제로 금지시킴

- 만약 break/exit을 사용하여 loop를 빠져 나온 경우라면, 대부분 빠져나온 순간의 index 값을 그래도 유지하려고 함

- 만약 제대로 종료가 되었다면, 일반적으로 반복문의 loop bound를 초과하는 첫번 째 index 값인 경우가 가장 많음

- 불행히도, 몇몇 loop에 있어서 "next" value가 정수의 범위를 넘어갈 경우 overflow가 발생하는데 어떻게 처리?

아래의 예를 보자

단, 이러한 경우가 아닌 경우도 있음: 즉, 모를 수도 있음

-> Algol W, Modula 3 등 많은 언어들에서는 반복문의 헤더 부분(for(int i..))에 index의 선언(int i = 0)을 집어넣는 경우가 있음

     - 이 경우 index는 해당 반복문안에서만 scope를 가지므로 반복문 종료시 자동 소멸

     - 따라서 loop 바깥에서 해당 값에는 더 이상 이슈가 없게 됨(즉 고민 해결!)

6.5.2 Combination Loops

Algol 60에서는 현대의 enumeration, logically controlled loops 둘의 특징을 아울르는 single loop construct를 제공함

해당 언어에서는 프로그래머가 enumberator의 수를 임의로 설정하는 것을 가능하게 함

- single value

- 현대 enumeration controlled loop에서 사용하는 것과 비슷한 값의 범위

- 종료 조건식과 함께 쓰는 표현식

 

해당 형태를 Combination Loops라고 하는데, 이는 C언어와 계승언어들(C++, JAVA)등에서 더 간단한 형태로 구현 가능

C loops는 logically controlled 됨. 그러나 enumeration하기는 쉽게 디자인 됨

Modula-2 예

이 경우 C를 사용할 경우 더 간단!

C 언어에서는 for<->while 루프 쌍방 호환 가능(해당 언어에서는 두 루프가 동급)!

- 또한, overflow에 있어서는 프로그래머에게 전적으로 맡기는 형태

- index, 종료 조건 변수들을 바꾸는 것도 가능(결국 Logically controlled에 해당하므로 : 조건이 만족되거나/만족되지 않을 경우 종료)

- for 문 헤더 안의 clause 세개 다 null이 올수 있음 (for ( ; ; ))

- clause는 comma-separated expression의 나열로 구성될 수 있음 (for(a = 3, b =4; ; )

- 또한 while문과 비교하였을 때 장점은, 좀 더 명확하고 콤팩트하게 표현할 수 있음

   - for문은 while문과 다르게 flow control문이 모두 헤더에 있음

   - while 문은 flow control문이 loop body 전체에 있을 수 있음

- 또한 C언어에서의 for loop는 값을 명시해주므로 end of the loop 후에 index 값의 모호성을 제거해준다

   - 그러나, index variable은 여전히 loop body안에 만드는 것이 편리하긴 함

6.5.3 Iterators

- 일반적으로 우리는, 잘 정의된 set, collection, container 클래스의 인스턴스 등이 반복되기를 바람

- Clu 언어가 처음으로 iterator개념을 제공, 추후 파이썬, Ruby, C#에서 제공

- Euclid, 몇몇의 최근 언어들 특히 C++, Java, Ada2012 등은 iterator object를 위한 스탠다드 인터페이스를 정의

 

 True Iterator

1) Clu, Python, Ruby, C#은 iterator을 제공해주는 container abstraction을 허용

2) iterator가 yield statement(반복문 사용시 상태 기억)를 사용

3) For loop는 iterator에 대한 함수 콜을 허용

 

Modular-2 Fragment

위의 코드가 파이썬 사용시 아래와 같이 구현

- iterator는 first index가 무엇이 될 지 계산

- yield statement를 실행하여 main program으로 리턴

- 더 이상 iterator에 남아있는 요소가 없을 경우 loop를 종료

 

iteration mechnism은 "decouple(분리)"시키는 역할을 함

- 알고리즘과 코드로부터 enumerate element를 사용하는 알고리즘을 분리

range iterator는 파이썬에서 이미 정의되어 있음

 

더 상세한 예를 보기 위해서는, 아래와 같이 이진트리에서 저장된 값의 preorder enumeration을 고려해보자

- yield keyword 사용시, 해당 함수를 재호출하여도 마지막 호출 시 접근 한 원소를 기억함

- return을 사용할 경우 단순히 함수 종료, 가장 최근에 접근한 요소에 대해 기억할 수 없음

 

Iterator Objects

Iteration은 for loop의 특별한 형태와 loop를 위한 enumerate value를 하는 메카니즘 둘다를 포함한다

Euclid, C++, Java, Ada 2012는 파이썬에서 보이는 enumeration-controlled loops을 흉내내는 기능을 제공한다

- yield statement X

- 알고리즘과 별개로 enumerate value를 제공하는 기능 X

- iterator는 객체지향 관점에서의 객체로 나타남, 따라서 초기화, 다음 인덱스 생성 등을 구현해 놓은 클래스일 뿐

- 각각의 함수들이 호출되는 사이에 iterator는 객체의 데이터 멤버가 어떤 값을 가지고  있는지 저장

 

아래와 같이 자바 코드를 작성한다고 해보자

syntatic sugar를 추가한 loop 코드는 아래와 같음

- java iterator는 이렇듯 hasNext(), next() 등 다음 요소가 있는지, 다음 요소의 값을 반환해주는 함수 제공

 

이번에는 아래와 같이 c++ 코드를 작성한다고 해보자

syntatic sugar를 추가한 loop 코드는 아래와 같음

- C++ iterator는 포인터의 특별한 종류로 행동하도록 디자인 됨

 

6.5.5 Logically Controlled Loops

 

- logically controlled loop에서 실행시킬 때  확인해야 될 점은 종료 조건임

- 대부분 종료 조건은 각 반복을 한 번 실행시킬 때마다 확인하게 됨

 

Pre-test loop(while문)

친숙한 while loop의 형태는 Algol-W에서 기원

Post-test loop(do-while문)

- 적어도 한 번 실행은 보장됨

- Pascal에서 만들어지고, Modula에서 보수되었으나 Ada에서 버려진 개념

post-test loop는 아래와 같은데,

while문으로 대체될 수도 있음

Mid-test Loops

- 종료 조건이 루프의 중간에 있음

많은 언어들에서 mid-test 의 경우 특별한 문법 체계를 제공함(아래는 C의 예제)

- 몇몇 언어에서는 추가로 loop-name을 할당하여 exit statement를 사용함

아래의 예제는 Ada로 작성

자바는 C/C++의 break 문의 확장판으로 loop에 추가적으로 label을 붙여 아래와 같이 작성 가능

6.6 Recursion 

- 특별히 추가로 syntax가 필요한 것은 아님

- 서브루틴(paticulary functions)을 제공하는 모든 언어에서는, 함수 자기 자신을 호출하는 것과 *mutual recursion을 허용한다

- recursive algorithm <-> iterative algorithm

*mutual recursion이란?

void g();
void f(){
	g();
}
void g(){
	f();
}

 

6.6.1 Iteration and Recursion

- Fortran 77과 특정 다른 언어들은 recursion을 허용하지 않음 : 함수안의 변수들도 static하게 할당했기 때문에

- 몇몇의 함수형 언어들은 iteration을 허용하지 않음

- 대부분의 현대 언어들은 두 메카니즘(iteration &  recursion) 모두 허용

- 절차형 언어에서는 iteration이 좀 더 자연스럽다 : 변수의 반복된 수정에 기반하므로

- 반대로 함수형 언어에서는 recursion이 좀 더 자연스러움 : 변수를 수정하지 않으므로

 

1~10까지 합을 구하는 것을 iteration을 이용하면 아래와 같은 코드가 나온다

recursion을 사용해서 최대공약수를 구해보자

두 경우에서 서로 방법을 바꿔보면 아래와 같음

summation을 iteration->recursion,

gcd를 recursion->iteration

 

Tail Recursion

- recursion을 사용하는 것보다 iteration을 사용하는 것이 더 효율적이라는 논쟁이 있음

- 단, 이는 iteration의 naive 구현이 recursion의 naive 구현보다 더 효율적이라고 말하는 것이 정확함

   - 이 경우, 지역변수를 위한 런타임 스택과, bookkeeping information때문에 iteration이 더 효율적이라고 말하는 것

- optimizing compiler는 종종 recursive function을 위한 훌륭한 코드를 생성할 수 있음

   - 이를 "tail-recursive function"이라고 함 : iteration보다 뛰어나다기 보다는 iteration과 동등한 속도

 

tail-recursive finction이란?

- 재귀호출을 하는 함수 다음에 또 다른 computation이 없는 경우

- 즉 recursive call에 대한 결과를 바로 리턴함

- 이러한 함수의 경우 스택 공간을 관리 하는 등의 행동이 필요하지 않음

좋은 컴파일러의 경우 recursive gcd function은 다음과 같이 recast 해줌

- 심지어는 tail-recursive가 아닌 함수도 tail-recursive하게 바꿀 수 있다

- 단, 몇몇의 특별한 변형에서는 함수형 언어에 대해서 잘 아는 사용자들만 바꿀 수 있기도 하다

아래는 Scheme으로 작성된 예로, recursive summation function임

프로그래머가 addition부분이 associative함을 깨달았다면 아래와 같이 tail-recursive한 형태로 재작성할 수 있다

- 이 경우 스택공간에 할당하는 등의 행동이 필요 없음

 

6.6.2 Applicative- and Normal-Order Evaluation

- 지금까지는 함수에 인자가 전달된다고 할 때, evaluate하고 전달되었음

- 지금부터는 실제로 해당 값이 전달되는 함수안에서 사용될 때만 evaluate하는 경우를 볼거임

 

Applicative-order evaluation

- 호출 당하기 전에 evaluate됨

normal-order evaluation

- 값이 실제로 사용될 때만 evaluate됨

- 매크로 함수에서 주로 일어나는 사오항

- short-circuit Boolean evaluation, call-by-name parameters, 일부 함수형 언어에서 사용됨

- Algol60에서 normal-order evaluation을 사용자 정의 함수를 위해서 기본으로 사용한적 있음

 

Lazy Evaluation

- 필요할 때 게으르게 evaluate하는 것이므로 normal-order evalutaion에 해당

 - 효율성, 투명성, 명확성을 따졌을 때 사실 applicative-order evaluation이 낫기는 함

: 따라서 일반적으로 대부분의 언어에서 이를 채택

- 단, normal-order evaluation을 사용할 경우 faster code의 방법이 된다.

: applicative-order evaluation은 때때로 런타임 오류를 발생시키기도 함

- normal-order evaluation은 때때로 절대로 필요하지 않은 인자에 대해서는 evaluate를 하지 않음

 

6.7 Nondeterminancy

nondeterministic construct는 일부러 명확하게 제시하지 않는 경우가 있음

->미리 정해놓지 않고 이후에 결정함으로써 효율성 추구

- 예로 표현식의 evaluation하는 방법

- 대부분의 언어에서 서브루틴 인자 혹은 연산자들의 순서를 정해놓지 않음