제어흐름 - 구조적 흐름과 선택

goto를 포기하는 것은 소프트웨어 공학에서 구조화 프로그래밍이라는 큰 혁명의 일부이다. 1990년대에 객체지향 프로그래밍이 그랬던 것처럼 구조화 프로그래밍은 1970년대의 강력한 트렌드였다.

구조화 프로그래밍은 하향 설계 (점차적인 세분화), 모듀롸된 코드, 구조화된 타입, 변수 및 상수 이름을 잘 붙이는 것, 설명문을 충분히 넣어주는 것 등을 포함한다. 개발자는 구조화 프로그래밍을 통해 서브루틴 내에서 거의 대부분의 잘 설계된 순차적 알고리즘이 순차, 선택, 반복만으로 구현될 수 있음을 보였다.

레이블 대신 구조화된 언어에서는 구문적으로 중첩된 구조물의 끝으로 분기 제어가 이동하도록 하는 방법을 쓴다.

다단계 return

단번에 여러번의 서브루틴 호출에서 리턴시킨다.
비지역 goto가 발생하면 언어 구현은 서브루틴 호출 정보의 실행시간 스택이 복구되도록 보장해야 한다. 이러한 복구는 되감기(unwinding)이라고 불린다.

스택프레임해지 + 추가연산 진행

선택

선택은 If condition에 대하여 알아보자.

언어마다 구문의 세부적인 면은 조금씩 다르다. 알골 60과 파스칼은 then과
else 절이 모두 오직 하나의 문장만 포함할 수 있게 하였다. 물론 여기서 하나의
문장이란 begin ... end로 둘러싸인 복합문이 될 수 있다. 문법적인 모호성을 피하기 위해 알골 60은 then 다음에 복합문이 아닌 단일 문장이 오는 경우는 if 문이 될 수 없다고 정하였다. 파스칼은 "모호성 해결 규칙“을 통해 이러한 문제를
해결하였다. 즉 항상 else는 가장 가까운 매치되지 않은 then과 매치된다는 것이다. 알골 68과 포트란 77과 기타 현대적 언어들은 이러한 모호성을 피하기 위해
별도의 종료 키워드를 두어서 then이나 else 뒤에 나오는 문장 리스트의 끝을 나타내도록 하였다.

 

Dangling else

 

if가 반복되면서 else의 위치를 놓치는 문제이다.
이를 해겨하지 위해 elsif나 elif같은 키워드를 도입하여 해결하였다.

 

단축계산

 

if else문의 조건부는 진위값을 가지는 조건식인데, 그 조건식의 결과값을 계한해서 결과를 레지스터에 넣을 필요는 없다.

선택문에서 진위 수식의 목적은 그 식의 결과값을 계산하는 것이 아니라 그를 통해 다양한 곳으로 분기하도록 하는 것이다. 이러한 관찰은 점프 코드라고 하는 특별히 효율적인 코드의 생성을 가능하게 한다.

단축 계산 수식의 값이 필요한 경우라면 점프 코드의 효율성을 살리면서도 그것을 생성하는 것도 가능하다.

found_it = (p != null and p.key = val);

다음과 같은 코드가 생성될 수 있다.

r1 := p
if r1 = 0 goto L1
r2 := r1→key
if r2 = val goto L1
r1 := 1
goto L2
L1: r1 := 0
L2: found it := r1

첫 goto L1문장이 그냥 gotoL2로 바뀔 수 있다. r1이 이 경우 이미 0을 가지고 있기 때문이다.
컴파일러의 코드 개선단계에서도 이를 알 수 있고 변경할 수 있다.

 

Case/Switch

 

Case는 같은 정수 수직의 값에 의해 결정되는 여러 개의 선택조건.
컴파일 시간 상수로 비교한다.

주어진 수식을 모든 가능한 값들에 대해 차례로 검사하는 대신 case문은 하나의 단일 명령문으로 점프할 주소를 계산할 수 있게 하려는 것이다. case문의 점프테이블의 형식은 다음과 같다.

 

레이블 T의 코드는 주소의 표이고 이를 점프테이블이라고 부른다.
case문의 레이블에 나타나는 것들 중 최소에서 최대 값 사이의 정수에 대해 하나씩 항을 가지고, 다 나타낼 수 없으면 else분기를 계산한다. 그런다음 테이블에서 해당 항을 가져와스 그 주소로 이동한다.

 

선형의 점프 테이블은 매우 빠르다. 또한 case 문의 레이블 값이 밀집되고 그리넓은 범위에 퍼져 있지 않다면 공간적으로도 효율적이다.

 

그러나 만약 그 값들이 밀집되지 않고 넓은 범위에 퍼져 있다면 테이블 자체가 엄청나게 많은 공간을 사용하게 된다. 분기할 주소를 계산하는 다른 방법으로는 순차 검사, 해싱, 이진 검색 등이 있다. 순차 검색은 if ... then ... else 문과 마찬가지로 case 문의 레이블 수가 작다면 선택할 수 있다. 소요 시간은 n이 레이블의 개수일 때 O(n)이다.

 

해시 테이블은 값의 범위는 큰데 빠진 값이 많은 경우 적합하다. 해시 함수가 잘만 만들어진다면 O(1) 시간이 걸린다. 그러나 해시테이블은 각 테스트 수식의 가능한 값에 대해 별도의 항을 가져야 하며 값의 범위가 큰 경우 사용하기 어렵다. 이진 검색은 큰 범위에도 적용 가능하다. 수행 시간은 O(log n)이며 상대적으로 작은 상수항을 가진다.