32 반복 — 루프와 불변식
먼저 알아야 할 것
돌아보기
4장에서 “단순한 걸음이라도 1초에 수십억 번이면 어떤 복잡한 일이든 지을 수 있다”고 했다. 그런데 31장까지의 우리 프로그램은 위에서 아래로 한 번 흐르고 끝난다 — 수십억 번의 걸음은 어디서 나오는 것인가?
답. 같은 문장들을 다시 실행하는 장치에서 나온다. 조건이 참인 동안 블록으로 되돌아가는 것 — 루프다. 분기가 흐름을 가르는 장치였다면 루프는 흐름을 감아올리는 장치이고, 이 둘을 갖추는 순간 C는 계산 가능한 모든 것을 적을 수 있는 언어가 된다(이론적으로도 그렇다 — 4장의 계산 모델이 요구하는 전부가 “순차, 분기, 반복”이다).
이 장의 필요성과 맥락
while 의 괄호 안을 설명할 수 없다. 그리고 여기서 익히는 불변식은 뒤에 나올 거의 모든 배열 순회의 사고 도구가 된다.이 장이 끝나면
while, for, do-while)와 새 연산자들(++, +=), 루프를 옳게 읽고 쓰는 생각의 틀(불변식)까지. 그리고 12장에서 예약해 둔 재회 — Duff’s device — 를 드디어 만난다.이 장에서 답할 질문
- 조건이 영영 거짓이 안 되면 어떻게 되는가?
32.1 루프 3형제
while — 가장 원초적인 형태다. “조건이 참인 동안, 블록을 반복하라”:
while (조건) {
반복할 문장들
}조건을 먼저 검사하므로, 처음부터 거짓이면 한 번도 돌지 않는다.
for — 반복의 살림살이(시작·조건·갱신)를 한 줄에 모은 형태다. 시연으로 본다 — 1부터 100까지의 합이다:
examples/ch32/sum.c
#include <stdio.h>
int main(void)
{
int sum = 0;
for (int i = 1; i <= 100; i += 1) {
sum += i; /* 불변식: sum == 1 + 2 + ... + (i - 1)... 갱신 후엔 ...+ i */
}
printf("sum of 1..100 = %d\n", sum);
return 0;
}
실행 결과
sum of 1..100 = 5050
for (int i = 1; i <= 100; i += 1)을 세 칸으로 읽는다 — 시작(int i = 1: 루프 변수를 만들고), 조건(i <= 100: 돌기 전마다 검사), 갱신(i += 1: 한 바퀴 끝날 때마다 실행). 새 연산자 +=는 23장 대입의 줄임꼴로 i = i + 1과 같고, 더 줄인 i++(증가 연산자)도 같은 일을 한다 — 관용적으로 for (...; i++) 꼴을 가장 많이 보게 된다. (++에는 앞에 붙는 꼴과 뒤에 붙는 꼴, 그리고 수식 안에서의 미묘한 사정이 있는데 — 다음 장의 시퀀스 포인트 이야기와 함께 다룬다.)
do-while — 블록을 먼저 한 번 실행하고 조건을 검사하는 형태다 (do { ... } while (조건);). “최소 한 번은 해야 하는 일”(메뉴를 먼저 보여 주고 반복 여부를 묻는 류)에 쓰이고, 셋 중 등장 빈도가 가장 낮다.
수학. 루프 불변식 — 반복을 증명하는 눈
루프를 “옳게” 읽는 도구가 하나 있다 — 불변식(invariant): 매 바퀴의 같은 지점에서 항상 성립하는 명제다. 시연의 루프라면, 몸통에 들어설 때마다
이 성립한다(첫 바퀴에는 빈 합 = 0). 몸통이 sum += i를 하면 등식의 오른쪽이 까지 자라고, 갱신이 를 올리면 다시 같은 꼴이 된다 — 불변식이 유지된다. 루프가 끝나는 순간은 이므로, 불변식에 대입하면 sum = 1 + … + 100. 즉 [불변식 + 종료 조건 = 루프의 정확성 증명]이다. 매번 이렇게 적진 않더라도, “이 루프에서 변하지 않는 사실이 무엇인가”를 묻는 습관은 루프 버그의 대부분 — 하나 모자라게/많게 도는 off-by-one — 을 잡아 주는 눈이 된다. 계약 으로서의 코드라는 관점(51장)의 첫 연습이기도 하다.
문. 조건이 영영 거짓이 안 되면 어떻게 되는가?
답. 무한 루프다 — 프로그램이 그 자리를 영원히 돈다. 대개는 갱신을 잊은 버그의 결과지만, 의도적인 무한 루프(while (true))도 어엿한 관용구다 — 서버처럼 “끝나지 않는 것이 정상”인 프로그램의 뼈대가 그것이고, 안에서 조건을 보아 break(루프 탈출 — switch의 그 break와 같은 낱말이다)로 나온다. 위험한 것은 무한 루프 자체가 아니라 의도치 않은 무한 루프다.
32.2 재회 — Duff’s device
12장에서 예약한 전설을 만날 시간이다. 이제 우리는 switch의 폴스루 (31장)와 루프(이 장)를 모두 알고 있다.
1983년, 루카스필름의 Tom Duff는 데이터를 장치로 복사하는 루프가 너무 느려 고심하고 있었다. 한 바퀴마다 드는 살림 비용(조건 검사·갱신)을 줄이려 여덟 개씩 묶어 처리(언롤링)하되 — 개수가 8의 배수가 아닐 때의 나머지 처리를, 그는 아무도 상상 못 한 방법으로 해결했다:
switch (count % 8) {
case 0: do { *to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
} while ((count -= 8) > 0);
}(*to, *from++ 부분은 35장의 포인터 문법이라 아직 겉모양만 보면 된다 — 핵심은 구조다.) 읽는 법: switch가 루프의 한복판으로 건너 뛴다. case는 이름표일 뿐이라는 31장의 사실을 기억하면 — 이름표가 do-while의 몸통 안에 찍혀 있어도 문법 위반이 아니다. 첫 진입은 나머지 개수만큼만 처리하는 지점으로 뛰어들고, 이후는 do-while이 여덟 줄짜리 몸통을 통째로 돈다. 나머지 처리와 언롤링이 한 몸이 된 것이다.
Duff 자신도 “발견하고 나서 자부심과 혐오감이 뒤섞였다”는 소감을 남긴 이 코드는, 합법과 기괴함의 경계에서 C 문법의 유연함(어쩌면 헐거움)을 보여 주는 기념비다. 그리고 오늘의 교훈은 12장에서 예고한 그대로다 — 이 곡예는 이제 사람의 일이 아니다. 현대 컴파일러는 평범하게 쓴 루프를 알아서 언롤링한다(13장의 편집자). Duff’s device는 박물관의 걸작으로 감상하고, 우리의 루프는 시연의 for처럼 평범하고 읽기 쉽게 쓰는 것 — 그것이 모던 C다.
반복까지 갖추며 흐름의 도구가 완성됐다 — 순차(19장), 분기(31장), 반복(32장). 다음 장은 제6부의 마무리로, 함수라는 장치의 의미를 파고든다 — 값은 어떻게 건너가는가, 부수효과란 정확히 무엇인가, 그리고 20장에서 심어 둔 씨앗(평가 순서)의 정식 답까지.
(루프의 기법 — 중첩과 순회 순서, 여러 겹을 한 번에 벗는 법, 매크로를 한 문장으로 만드는 do { } while (0) — 은 배열을 배운 뒤라야 쓸 수 있어서 41장에 모아 두었다.)