Tour de IOCCC: 2005/timwi
#include <stdio.h>
#define _ main(
#define _l ___l ___l ___l ___l ___)
#define __l int
#define ___l ___)*(
#define ____l (_l],
#define ____ 1
#define ___ __+_____
#define __ ____+____
#define _____ __+____
#define ______1 *(l__
#define _____1 *__1%(__
#define ____1 )?(
#define ___1 _1&(__
__l __I[____l _I[____l*l__=_I,*l_=__I;__l _ __l _1,__l*__1){__l _l_;
return ___1+ __ ____1 ___1 ____1*__1 = getchar()):__ ____1*__1<____?
____:_____1+___ ____1 _____1+_____ ____1 _____1+____)____1 ___1+___+
____ ____1 _____1 +__)____1 _____1 )____1 *l__)++:_____1+____)-____?
______1 ++) :_____1+_____) -____?__:printf("%d\n",*l__):_____1+____+
___ ____1 *l__) =*(l_++ ):__:___l ____- ____):_____1 +_____)-3?__-2:
____:(___1+____+___ ____1 _____1)____1*l__)-- :_____1+__)?__:______1
--):___l 0))?__:_ _1,__1+____)+____:(___1+____+___ )) &&* l__?_ ___1
+___+___+__),__1+____)?_ ___1+11 )|(___1)?____:__- 2),__1):____-1 :(
_l_=_ ___1 -____+___l ____),__1+____ )) ?_l_+_ ___1 )?_1 :___1+10)|(
___1-____ ____1 __):0),__1+_l_):0):__:_1%(__ ____1 _1/(__)) ?_ scanf
("%i",__1 ____1 _____):(___l _____)-____,__1 +____):_ _____,l_):__;}
지금까지 다양한 종류의 인터프리터가 IOCCC에 출품되었지만 이렇게 간단한 언어를 이렇게 복잡하게 만들어 놓은 것은 또 드물죠.
뭘 하는 프로그램인가?
이 프로그램은 Brainfuck 프로그래밍 언어의 인터프리터입니다. Brainfuck은 단지 여덟개의 명령만으로 구성된 작은 프로그래밍 언어입니다.
이 프로그램의 특징은, 대부분의 Brainfuck 인터프리터가 한 칸에 1바이트짜리 배열을 사용하는 것과는 달리 이 프로그램은 int 크기의 배열을 사용한다는 점입니다. 또한 입출력을 위해 사용되는 .과 , 명령은 문자가 아니라 숫자를 입출력받는 데 사용하죠. 예를 들어,
$ gcc timwi.c -o timwi
$ echo '10 : ,-->+.>+.<<[>[>>+>+<<<-]>[>>+>+<<<-]>[<+>-]>[<<<+>>>-]>[-]<<<<.<-]' | ./timwi
1
1
2
3
5
8
13
21
34
55
본래는 1, 1, 2, 3, ...이 해당하는 문자("\x01\x01\x02\x03..." 식으로)로 나와야 하지만 이 프로그램은 대신 숫자를 출력하도록 되어 있습니다. 마찬가지로 프로그램 앞에 콜론으로 구분된 숫자는 프로그램의 입력으로, 첫번째 ,를 실행하면 1과 0이라는 글자를 따로 읽는 것이 아니라 10이라는 숫자를 바로 한 칸에 저장합니다.
이 프로그램의 더 엽기적인 특징은 일반적인 명령 문자 말고 다른 문자를 쓸 수도 있다는 점입니다.
$ echo '10 : \-AzC.VI.Pxw>8>Jmz+P<PUl&~V>GVYP(P7lV#xaV7]&i(<(qVJV70&8_]Pdx(j(7N' | ./timwi
1
1
2
3
5
8
13
21
34
55
...그러면서도 중간에 있는 공백이나 그런 것들은 잘 무시해 줍니다. 과연 왜 이런 문자들이 지원되는 것일까요?
어떻게 동작하는가?
이 프로그램을 전처리기에 넣어서 돌릴 수는 있지만, 전처리기가 코드 크기를 줄이는(?) 데 사용되었기 때문에 그대로 할 경우 힌트에서 말하는 대로 1 + 1 + 1 + 1 + 1 같은 코드만 넘쳐 나게 됩니다. 따라서 전처리기에 코드를 돌리기 전에 먼저 매크로를 정리하도록 하겠습니다.
매크로 지옥, 연산자 지옥
밑줄로 이루어진 이름들은 보기가 힘드므로 먼저 정리하도록 합시다. 아래에서 저는 __, ___ 등의 문자열(이름 중간에 있는 경우도 포함)을 B, C 등으로 바꿨습니다.
#include <stdio.h>
#define _ main(
#define _l Cl Cl Cl Cl C)
#define Bl int
#define Cl C)*(
#define Dl (_l],
#define D 1
#define C B+E
#define B D+D
#define E B+D
#define F1 *(lB
#define E1 *B1%(B
#define D1 )?(
#define C1 _1&(B
Bl BI[Dl _I[Dl*lB=_I,*l_=BI;Bl _ Bl _1,Bl*B1){Bl _l_;
return C1+ B D1 C1 D1*B1 = getchar()):B D1*B1<D?
D:E1+C D1 E1+E D1 E1+D)D1 C1+C+
D D1 E1 +B)D1 E1 )D1 *lB)++:E1+D)-D?
F1 ++) :E1+E) -D?B:printf("%d\n",*lB):E1+D+
C D1 *lB) =*(l_++ ):B:Cl D- D):E1 +E)-3?B-2:
D:(C1+D+C D1 E1)D1*lB)-- :E1+B)?B:F1
--):Cl 0))?B:_ _1,B1+D)+D:(C1+D+C )) &&* lB?_ C1
+C+C+B),B1+D)?_ C1+11 )|(C1)?D:B- 2),B1):D-1 :(
_l_=_ C1 -D+Cl D),B1+D )) ?_l_+_ C1 )?_1 :C1+10)|(
C1-D D1 B):0),B1+_l_):0):B:_1%(B D1 _1/(B)) ?_ scanf
("%i",B1 D1 E):(Cl E)-D,B1 +D):_ E,l_):B;}
B, C, D, E는 모두 1+1+1... 꼴의 수식으로 평가됩니다. 하지만 바깥에 괄호가 없기 때문에(예를 들어 3*B*4라고 했다면, 이는 3*1+1*4와 같지 3*(1+1)*4와는 다릅니다) 이걸 하나의 숫자로 바꿀 수 있을 지는 좀 의심이 드는군요. 따라서 먼저 다른 매크로를 정리한 뒤 바꿀 수 있는지 결정해 보겠습니다.
아래는 _, Bl, F1, E1, D1, C1을 정리한 뒤의 모습입니다.
#include <stdio.h>
#define _l Cl Cl Cl Cl C)
#define Cl C)*(
#define Dl (_l],
#define D 1
#define C B+E
#define B D+D
#define E B+D
int BI[Dl _I[Dl*lB=_I,*l_=BI;int main( int _1,int*B1){int _l_;
return _1&(B+ B )?( _1&(B )?(*B1 = getchar()):B )?(*B1<D?
D:*B1%(B+C )?( *B1%(B+E )?( *B1%(B+D))?( _1&(B+C+
D )?( *B1%(B +B))?( *B1%(B ))?( *lB)++:*B1%(B+D)-D?
*(lB ++) :*B1%(B+E) -D?B:printf("%d\n",*lB):*B1%(B+D+
C )?( *lB) =*(l_++ ):B:Cl D- D):*B1%(B +E)-3?B-2:
D:(_1&(B+D+C )?( *B1%(B))?(*lB)-- :*B1%(B+B)?B:*(lB
--):Cl 0))?B:main( _1,B1+D)+D:(_1&(B+D+C )) &&* lB?main( _1&(B
+C+C+B),B1+D)?main( _1&(B+11 )|(_1&(B)?D:B- 2),B1):D-1 :(
_l_=main( _1&(B -D+Cl D),B1+D )) ?_l_+main( _1&(B )?_1 :_1&(B+10)|(
_1&(B-D )?( B):0),B1+_l_):0):B:_1%(B )?( _1/(B)) ?main( scanf
("%i",B1 )?( E):(Cl E)-D,B1 +D):main( E,l_):B;}
위의 코드에서 B, C, E가 +가 아닌 다른 연산자와 결합하는 경우가 있는지 확인해 보세요. 아마 문제가 되는 경우는 B-2, B-D+..., B-D, 그리고 Cl E 네 가지 경우 뿐일 것 같습니다만, 앞의 세 가지는 B가 앞쪽에 있으므로 - 연산자를 써도 상관이 없고, 마지막은 Cl의 마지막 글자가 (인 게 확실하므로 무시해도 좋습니다. 따라서 우리는 안전하게 D, C, B, E를 각각 1, 5, 2, 3으로 바꿀 수 있습니다.
#include <stdio.h>
#define _l Cl Cl Cl Cl 5)
#define Cl 5)*(
#define Dl (_l],
int BI[Dl _I[Dl*lB=_I,*l_=BI;int main( int _1,int*B1){int _l_;
return _1&(2+ 2 )?( _1&(2 )?(*B1 = getchar()):2 )?(*B1<1?
1:*B1%(2+5 )?( *B1%(2+3 )?( *B1%(2+1))?( _1&(2+5+
1 )?( *B1%(2 +2))?( *B1%(2 ))?( *lB)++:*B1%(2+1)-1?
*(lB ++) :*B1%(2+3) -1?2:printf("%d\n",*lB):*B1%(2+1+
5 )?( *lB) =*(l_++ ):2:Cl 1- 1):*B1%(2 +3)-3?2-2:
1:(_1&(2+1+5 )?( *B1%(2))?(*lB)-- :*B1%(2+2)?2:*(lB
--):Cl 0))?2:main( _1,B1+1)+1:(_1&(2+1+5 )) &&* lB?main( _1&(2
+5+5+2),B1+1)?main( _1&(2+11 )|(_1&(2)?1:2- 2),B1):1-1 :(
_l_=main( _1&(2 -1+Cl 1),B1+1 )) ?_l_+main( _1&(2 )?_1 :_1&(2+10)|(
_1&(2-1 )?( 2):0),B1+_l_):0):2:_1%(2 )?( _1/(2)) ?main( scanf
("%i",B1 )?( 3):(Cl 3)-1,B1 +1):main( 3,l_):2;}
이제 Cl, _l, Dl을 정리할 준비가 된 것 같습니다. 먼저 _l을 Cl이 확장된 상태로 다시 쓰면,
#define _l 5)*( 5)*( 5)*( 5)*( 5)
이고, 만약 _l 앞에 연산자가 없다면 다음과 같아집니다.
#define _l 3125)
실제로 그럴까요? _l을 쓰는 곳은 단 하나, Dl 매크로 밖에 없으므로 실제로 이렇게 바꿀 수 있음을 알 수 있습니다. 이제 남은 매크로들을 모두 걷어 내면, 다음과 같은 그나마 나은(?) 코드가 나타납니다.
#include <stdio.h>
int BI[(3125)], _I[(3125)],*lB=_I,*l_=BI;int main( int _1,int*B1){int _l_;
return _1&(2+ 2 )?( _1&(2 )?(*B1 = getchar()):2 )?(*B1<1?
1:*B1%(2+5 )?( *B1%(2+3 )?( *B1%(2+1))?( _1&(2+5+
1 )?( *B1%(2 +2))?( *B1%(2 ))?( *lB)++:*B1%(2+1)-1?
*(lB ++) :*B1%(2+3) -1?2:printf("%d\n",*lB):*B1%(2+1+
5 )?( *lB) =*(l_++ ):2:5)*( 1- 1):*B1%(2 +3)-3?2-2:
1:(_1&(2+1+5 )?( *B1%(2))?(*lB)-- :*B1%(2+2)?2:*(lB
--):5)*( 0))?2:main( _1,B1+1)+1:(_1&(2+1+5 )) &&* lB?main( _1&(2
+5+5+2),B1+1)?main( _1&(2+11 )|(_1&(2)?1:2- 2),B1):1-1 :(
_l_=main( _1&(2 -1+5)*( 1),B1+1 )) ?_l_+main( _1&(2 )?_1 :_1&(2+10)|(
_1&(2-1 )?( 2):0),B1+_l_):0):2:_1%(2 )?( _1/(2)) ?main( scanf
("%i",B1 )?( 3):(5)*( 3)-1,B1 +1):main( 3,l_):2;}
그냥 아무 생각 없이 전처리기에 돌리는 것보다는 이게 더 나은 것 같군요. (사실은 Cl, B, C, E의 매크로 정의를 지우고 전처리기에 돌린 다음에 되돌려도 됩니다만... 일부러 아는 길도 돌아 갔습니다.) 이제 들여쓰기를 넣어서 정리하겠습니다.
#include <stdio.h>
int BI[(3125)], _I[(3125)], *lB = _I, *l_ = BI;
int main(int _1, int *B1) {
int _l_;
return _1 & (2+2) ?
(
_1 & (2) ?
(*B1 = getchar()) :
2
) ?
(
*B1 < 1 ?
1 :
*B1 % (2+5) ?
(
*B1 % (2+3) ?
(*B1 % (2+1)) ?
(
_1 & (2+5+1) ?
(*B1 % (2+2)) ?
(*B1 % (2)) ?
(*lB)++ :
*B1 % (2+1) - 1 ?
*(lB++) :
*B1 % (2+3) - 1 ?
2 :
printf("%d\n", *lB) :
*B1 % (2+1+5) ?
(*lB) = *(l_++) :
2 :
5
) * (1-1) :
*B1 % (2+3) - 3 ?
2-2 :
1 :
(
_1 & (2+1+5) ?
(*B1 % (2)) ?
(*lB)-- :
*B1 % (2+2) ?
2 :
*(lB--) :
5
) * (0)
) ?
2 :
main(_1, B1 + 1) + 1 :
(_1 & (2+1+5)) && *lB ?
main(_1 & (2+5+5+2), B1 + 1) ?
main(_1 & (2+11) | (_1 & (2) ? 1 : 2-2), B1) :
1-1 :
(_l_ = main(_1 & (2-1+5) * (1), B1 + 1)) ?
_l_ + main(_1 & (2) ? _1 : _1 & (2+10) | (_1 & (2-1) ? (2) : 0), B1 + _l_) :
0
) :
2 :
_1 % (2) ?
(_1 / (2)) ?
main(scanf("%i", B1) ? (3) : (5)*(3)-1, B1 + 1) :
main(3, l_) :
2;
}
...모조리 삼항 연산자 ?:로 둘러 쌓여 있네요. 1988/litmaath의 악몽이 되살아 나는 것 같습니다. 삼항 연산자는 그래도 if 문으로 바꾸기 쉬우니 그렇게 하도록 하죠. 또한 (2+1+5)와 같이 값이 자명한 상수식도 모두 정리하겠습니다.
#include <stdio.h>
int BI[3125], _I[3125], *lB = _I, *l_ = BI;
int main(int _1, int *B1) {
int _l_;
if (_1 & 4) {
if (
_1 & 2 ?
(*B1 = getchar()) :
2
) {
if (*B1 < 1) {
return 1;
} else {
if (*B1 % 7) {
if (
*B1 % 5 ?
(*B1 % 3) ?
(
_1 & 8 ?
(*B1 % 4) ?
(*B1 % 2) ?
(*lB)++ :
*B1 % 3 - 1 ?
*(lB++) :
*B1 % 5 - 1 ?
2 :
printf("%d\n", *lB) :
*B1 % 8 ?
(*lB) = *(l_++) :
2 :
5
) * 0 :
*B1 % 5 - 3 ?
0 :
1 :
(
_1 & 8 ?
(*B1 % 2) ?
(*lB)-- :
*B1 % 4 ?
2 :
*(lB--) :
5
) * 0
) {
return 2;
} else {
return main(_1, B1 + 1) + 1;
}
} else {
if ((_1 & 8) && *lB) {
if (main(_1 & 14, B1 + 1)) {
return main(_1 & 13 | (_1 & 2 ? 1 : 0), B1);
} else {
return 0;
}
} else {
if ((_l_ = main(_1 & 6 * 1, B1 + 1))) {
return _l_ + main(_1 & 2 ? _1 : _1 & 12 | (_1 & 1 ? 2 : 0), B1 + _l_);
} else {
return 0;
}
}
}
}
} else {
return 2;
}
} else {
if (_1 % 2) {
if (_1 / 2) {
return main(scanf("%i", B1) ? 3 : 14, B1 + 1);
} else {
return main(3, l_);
}
} else {
return 2;
}
}
}
이런, if의 조건으로 삼항 연산자가 있는 경우가 두 군데 있네요. 이런 경우 별도의 문장으로 빼 내기 위해서 조건을 별도의 변수(아래에서는 cond)에 저장하도록 코드를 바꾼 뒤, 이렇게 분리된 문장으로 다시 if 문을 풀어 헤치도록 하겠습니다.
#include <stdio.h>
int BI[3125], _I[3125], *lB = _I, *l_ = BI;
int main(int _1, int *B1) {
int _l_;
int cond;
if (_1 & 4) {
if (_1 & 2) {
*B1 = getchar();
cond = *B1;
} else {
cond = 2;
}
if (cond) {
if (*B1 < 1) {
return 1;
} else {
if (*B1 % 7) {
if (*B1 % 5) {
if (*B1 % 3) {
cond = (
_1 & 8 ?
(*B1 % 4) ?
(*B1 % 2) ?
(*lB)++ :
*B1 % 3 - 1 ?
*(lB++) :
*B1 % 5 - 1 ?
2 :
printf("%d\n", *lB) :
*B1 % 8 ?
(*lB) = *(l_++) :
2 :
5
) * 0;
} else {
if (*B1 % 5 - 3) {
cond = 0;
} else {
cond = 1;
}
}
} else {
cond = (
_1 & 8 ?
(*B1 % 2) ?
(*lB)-- :
*B1 % 4 ?
2 :
*(lB--) :
5
) * 0;
}
if (cond) {
return 2;
} else {
return main(_1, B1 + 1) + 1;
}
} else {
if ((_1 & 8) && *lB) {
if (main(_1 & 14, B1 + 1)) {
return main(_1 & 13 | (_1 & 2 ? 1 : 0), B1);
} else {
return 0;
}
} else {
if ((_l_ = main(_1 & 6 * 1, B1 + 1))) {
return _l_ + main(_1 & 2 ? _1 : _1 & 12 | (_1 & 1 ? 2 : 0), B1 + _l_);
} else {
return 0;
}
}
}
}
} else {
return 2;
}
} else {
if (_1 % 2) {
if (_1 / 2) {
return main(scanf("%i", B1) ? 3 : 14, B1 + 1);
} else {
return main(3, l_);
}
} else {
return 2;
}
}
}
cond = (...) * 0; 꼴로 된 코드는 (...) 안의 내용이 평가는 되지만 결과는 사용되지 않는다는 뜻이 됩니다. 따라서 이 코드는 (...); cond = 0;으로 바꿔도 됩니다.
#include <stdio.h>
int BI[3125], _I[3125], *lB = _I, *l_ = BI;
int main(int _1, int *B1) {
int _l_;
int cond;
if (_1 & 4) {
if (_1 & 2) {
*B1 = getchar();
cond = *B1;
} else {
cond = 2;
}
if (cond) {
if (*B1 < 1) {
return 1;
} else {
if (*B1 % 7) {
if (*B1 % 5) {
if (*B1 % 3) {
if (_1 & 8) {
if (*B1 % 4) {
if (*B1 % 2) {
(*lB)++;
} else {
if (*B1 % 3 - 1) {
*(lB++);
} else {
if (*B1 % 5 - 1) {
2;
} else {
printf("%d\n", *lB);
}
}
}
} else {
if (*B1 % 8) {
(*lB) = *(l_++);
} else {
2;
}
}
} else {
5;
}
cond = 0;
} else {
if (*B1 % 5 - 3) {
cond = 0;
} else {
cond = 1;
}
}
} else {
if (_1 & 8) {
if (*B1 % 2) {
(*lB)--;
} else {
if (*B1 % 4) {
2;
} else {
*(lB--);
}
}
} else {
5;
}
cond = 0;
}
if (cond) {
return 2;
} else {
return main(_1, B1 + 1) + 1;
}
} else {
if ((_1 & 8) && *lB) {
if (main(_1 & 14, B1 + 1)) {
return main(_1 & 13 | (_1 & 2 ? 1 : 0), B1);
} else {
return 0;
}
} else {
if ((_l_ = main(_1 & 6 * 1, B1 + 1))) {
return _l_ + main(_1 & 2 ? _1 : _1 & 12 | (_1 & 1 ? 2 : 0), B1 + _l_);
} else {
return 0;
}
}
}
}
} else {
return 2;
}
} else {
if (_1 % 2) {
if (_1 / 2) {
return main(scanf("%i", B1) ? 3 : 14, B1 + 1);
} else {
return main(3, l_);
}
} else {
return 2;
}
}
}
이제 너무 커진 코드를 설명하기 편하게 하기 위하여 함수를 둘로 나누겠습니다. 나누는 부분은 다름이 아니라 두번째 cond를 설정하는 바로 그 부분입니다.
#include <stdio.h>
int BI[3125], _I[3125], *lB = _I, *l_ = BI;
int determine_cond(int _1, int *B1) {
int cond;
if (*B1 % 5) {
if (*B1 % 3) {
if (_1 & 8) {
if (*B1 % 4) {
if (*B1 % 2) {
(*lB)++;
} else {
if (*B1 % 3 - 1) {
*(lB++);
} else {
if (*B1 % 5 - 1) {
2;
} else {
printf("%d\n", *lB);
}
}
}
} else {
if (*B1 % 8) {
(*lB) = *(l_++);
} else {
2;
}
}
} else {
5;
}
cond = 0;
} else {
if (*B1 % 5 - 3) {
cond = 0;
} else {
cond = 1;
}
}
} else {
if (_1 & 8) {
if (*B1 % 2) {
(*lB)--;
} else {
if (*B1 % 4) {
2;
} else {
*(lB--);
}
}
} else {
5;
}
cond = 0;
}
return cond;
}
int main(int _1, int *B1) {
int _l_;
int cond;
if (_1 & 4) {
if (_1 & 2) {
*B1 = getchar();
cond = *B1;
} else {
cond = 2;
}
if (cond) {
if (*B1 < 1) {
return 1;
} else {
if (*B1 % 7) {
cond = determine_cond(_1, B1);
if (cond) {
return 2;
} else {
return main(_1, B1 + 1) + 1;
}
} else {
if ((_1 & 8) && *lB) {
if (main(_1 & 14, B1 + 1)) {
return main(_1 & 13 | (_1 & 2 ? 1 : 0), B1);
} else {
return 0;
}
} else {
if ((_l_ = main(_1 & 6 * 1, B1 + 1))) {
return _l_ + main(_1 & 2 ? _1 : _1 & 12 | (_1 & 1 ? 2 : 0), B1 + _l_);
} else {
return 0;
}
}
}
}
} else {
return 2;
}
} else {
if (_1 % 2) {
if (_1 / 2) {
return main(scanf("%i", B1) ? 3 : 14, B1 + 1);
} else {
return main(3, l_);
}
} else {
return 2;
}
}
}
명령의 인식
이제 determine_cond를 살펴 봅시다. 이 함수는 무려 열 세가지 코드 경로를 가지고 있는데, 이 중 다섯 개가 단순히 2;와 같은 아무 일도 하지 않는 문장이므로 지워 버려도 되겠습니다. 또한 cond = 1; 대신 바로 return 1;을 해도 되겠고요.
int determine_cond(int _1, int *B1) {
if (*B1 % 5) {
if (*B1 % 3) {
if (_1 & 8) {
if (*B1 % 4) {
if (*B1 % 2) {
(*lB)++;
} else {
if (*B1 % 3 - 1) {
*(lB++);
} else {
if (!(*B1 % 5 - 1)) {
printf("%d\n", *lB);
}
}
}
} else {
if (*B1 % 8) {
(*lB) = *(l_++);
}
}
}
return 0;
} else {
if (*B1 % 5 - 3) {
return 0;
} else {
return 1;
}
}
} else {
if (_1 & 8) {
if (*B1 % 2) {
(*lB)--;
} else {
if (!(*B1 % 4)) {
*(lB--);
}
}
}
return 0;
}
}
수식으로 된 조건식들도 정리해 봅시다. 예를 들어 !(*B1 % 5 - 1)이 조건식에 있을 때는 !(*B1 % 5 - 1) != 0과 같고, 이는 *B1 % 5 - 1 == 0과 동치이며 *B1 % 5 == 1과 동일한 의미가 되지요! 이런 식으로 *B1이 들어 간 모든 조건을 정리하겠습니다.
int determine_cond(int _1, int *B1) {
if (*B1 % 5 != 0) {
if (*B1 % 3 != 0) {
if (_1 & 8) {
if (*B1 % 4 != 0) {
if (*B1 % 2 != 0) {
(*lB)++; /* (1) */
} else {
if (*B1 % 3 != 1) {
*(lB++); /* (2) */
} else {
if (*B1 % 5 == 1) {
printf("%d\n", *lB); /* (3) */
}
}
}
} else {
if (*B1 % 8 != 0) {
(*lB) = *(l_++); /* (4) */
}
}
}
return 0;
} else {
if (*B1 % 5 != 3) {
return 0; /* (5) */
} else {
return 1; /* (6) */
}
}
} else {
if (_1 & 8) {
if (*B1 % 2 != 0) {
(*lB)--; /* (7) */
} else {
if (*B1 % 4 == 0) {
*(lB--); /* (8) */
}
}
}
return 0;
}
}
이제 각 문장에 대해서 *B1이 어떤 결과를 가지는지 확인해 보겠습니다. (볼 수 있듯이 이 프로그램에는, 예를 들어서, '+'에 해당하는 43과 같은 상수가 하나도 나오지 않습니다.) 설명을 간단하게 하기 위해 위의 코드에는 각 코드 경로에 (1)부터 (8)까지의 번호를 붙였습니다.
예를 들어 (8)에 해당하는 코드 경로에 들어간 경우, *B1 % 5 == 0, *B1 % 2 == 0, 그리고 *B1 % 4 == 0 세 개의 조건이 충족되는 것입니다. (_1 & 8도 있습니다만 우리는 *B1만 추적하고 있으니 생략합니다.) 또한 determine_cond를 호출하는 시점에서 *B1 >= 1과 *B1 % 7이라는 두 가지 조건이 덤으로 추가되지요.
이들을 고려하여 실제로 (1)부터 (8)까지 해당하는 *B1의 값을 찾아 보면 다음과 같은 표가 나타납니다.
| 경로 | 조건 | 가능한 *B1의 값 |
|---|---|---|
| (1) | ≠0(mod 7), ≠0(mod 5), ≠0(mod 3), ≠0(mod 4), ≠0(mod 2) | %)+/5;=CGIOSYaegkmqy |
| (2) | ≠0(mod 7), ≠0(mod 5), =2(mod 3), ≠0(mod 4), =0(mod 2) | &>JVz |
| (3) | ≠0(mod 7), =1(mod 5), =1(mod 3), ≠0(mod 4), =0(mod 2) | .j |
| (4) | ≠0(mod 7), ≠0(mod 5), ≠0(mod 3), =0(mod 4), ≠0(mod 8) | ,4DL\t| |
| (6) | ≠0(mod 7), =3(mod 5), =0(mod 3) | !0N]l{ |
| (7) | ≠0(mod 7), =0(mod 5), ≠0(mod 2) | -7AKU_s} |
| (8) | ≠0(mod 7), =0(mod 5), =0(mod 2), =0(mod 4) | (<Pdx |
각 경우에 대해서 +, >, ., ,, ], -, <가 가능한 값 사이에 끼어 있는 게 보이실 겁니다! 이제 이 프로그램이 왜 보통 Brainfuck 명령 이외에 다른 문자도 처리하는 지 알 수 있습니다.
(5)는 표에서 빠졌는데, 이는 (5)는 "아무" 일도 하지 않고 0을 반환하는 경우에 속하며, 이런 코드 경로는 (5) 말고도 더 있기 때문입니다. determine_cond 함수는 *B1 % 7 != 0일 때만 호출되기 때문에 이 경우 중 (1)~(4), (6)~(8)을 모두 제외하면 해당하는 경우를 얻을 수 있겠습니다. 이 경우를 편의상 (5')라고 하겠습니다.
한편 위에서 제가 일곱 개의 명령에 대해서 말했지만 [는 빠져 있습니다. 이 경우는 어디에 속할까요? 바로 *B1 % 7 == 0일 경우입니다! ('['는 ASCII 코드가 91이지요.) 이 경우는 편의상 (9)라고 하겠습니다. 그러면 실제 표는 다음과 같이 됩니다.
| 경로 | 조건 | 가능한 *B1의 값 |
|---|---|---|
| (1) | ≠0(mod 7), ≠0(mod 5), ≠0(mod 3), ≠0(mod 4), ≠0(mod 2) | %)+/5;=CGIOSYaegkmqy |
| (2) | ≠0(mod 7), ≠0(mod 5), =2(mod 3), ≠0(mod 4), =0(mod 2) | &>JVz |
| (3) | ≠0(mod 7), =1(mod 5), =1(mod 3), ≠0(mod 4), =0(mod 2) | .j |
| (4) | ≠0(mod 7), ≠0(mod 5), ≠0(mod 3), =0(mod 4), ≠0(mod 8) | ,4DL\t| |
| (5') | ≠0(mod 7), (1)~(4)나 (6)~(8)에 속하지 않음 | "$'2369:@BEHQRWXZ^`cfhnoruv |
| (6) | ≠0(mod 7), =3(mod 5), =0(mod 3) | !0N]l{ |
| (7) | ≠0(mod 7), =0(mod 5), ≠0(mod 2) | -7AKU_s} |
| (8) | ≠0(mod 7), =0(mod 5), =0(mod 2), =0(mod 4) | (<Pdx |
| (9) | =0(mod 7) | #*18?FMT[bipw~ |
이 표에서는 공백에 대한 내용은 안 나와 있지만 실제로 공백(\x20)과 탭(\t), 그리고 개행 문자(\n)는 (5')에 속합니다. (다만 \r은 아닙니다.) 따라서 이 코드는 알아서 공백도 무시해 주는 역할을 하고 있습니다. 실제로 조건을 하나 하나 나열하는 것은 매우 힘드므로 대신에 배열을 만들어서 체크하는 코드로 고치도록 하겠습니다.
static const int mapping[128] = {
9, 1, 2, 6, 4, 7, 5, 9, 5, 5, 5, 1, 5, 1, 9, 7, 5, 1, 6, 1, 8, 9, 5, 1,
5, 7, 2, 5, 9, 1, 5, 1, 5, 6, 5, 9, 5, 1, 2, 5, 8, 1, 9, 1, 4, 7, 3, 1,
6, 9, 5, 5, 4, 1, 5, 7, 9, 5, 5, 1, 8, 1, 2, 9, 5, 7, 5, 1, 4, 5, 9, 1,
5, 1, 2, 7, 4, 9, 6, 1, 8, 5, 5, 1, 9, 7, 2, 5, 5, 1, 5, 9, 4, 6, 5, 7,
5, 1, 9, 5, 8, 1, 5, 1, 5, 9, 3, 1, 6, 1, 5, 5, 9, 1, 5, 7, 4, 5, 5, 9,
8, 1, 2, 6, 4, 7, 9, 1};
int determine_cond(int _1, int *B1) {
switch (mapping[*B1]) {
case 1: /* (1) */
if (_1 & 8) (*lB)++;
break;
case 2: /* (2) */
if (_1 & 8) *(lB++);
break;
case 3: /* (3) */
if (_1 & 8) printf("%d\n", *lB);
break;
case 4: /* (4) */
if (_1 & 8) (*lB) = *(l_++);
break;
default: /* (5') */
break;
case 6: /* (6) */
return 1;
case 7: /* (7) */
if (_1 & 8) (*lB)--;
break;
case 8: /* (8) */
if (_1 & 8) *(lB--);
break;
case 9: /* (9), 사용하지 않음 */
assert(0);
}
return 0;
}
이제 반대로 생각해 봅시다. 처리해야 할 문자가 주어졌을 때 어떻게 위와 같은 형태로 바꿀 수 있을까요? 예를 들어 +(43), -(45), <(60), >(62), .(46), ,(44), [(91), ](93)이 있다고 가정하면, 이들 문자를 처음 몇 개의 숫자에 대해 나머지를 계산하면 다음과 같이 됩니다.
| (mod 2) | (mod 3) | (mod 4) | (mod 5) | (mod 6) | (mod 7) | (mod 8) | (mod 9) | |
|---|---|---|---|---|---|---|---|---|
| 43 | 1 | 1 | 3 | 3 | 1 | 1 | 3 | 7 |
| 44 | 0 | 2 | 0 | 4 | 2 | 2 | 4 | 8 |
| 45 | 1 | 0 | 1 | 0 | 3 | 3 | 5 | 0 |
| 46 | 0 | 1 | 2 | 1 | 4 | 4 | 6 | 1 |
| 60 | 0 | 0 | 0 | 0 | 0 | 4 | 4 | 6 |
| 62 | 0 | 2 | 2 | 2 | 2 | 6 | 6 | 8 |
| 91 | 1 | 1 | 3 | 1 | 1 | 0 | 3 | 1 |
| 93 | 1 | 0 | 1 | 3 | 3 | 2 | 5 | 3 |
이제 이 테이블을 사용해서 적절한 식을 만들어 내면 됩니다. 이 과정은 사실 퀸-매클러스키 알고리즘과 상당한 유사성이 있는데, 어떻게 하면 최소한의 항만으로 경우의 수를 구분할 수 있는지를 찾는 과정이 바로 최소항을 찾는 과정과 사실상 같습니다.
이 과정은 상당한 노가다가 필요합니다. 예를 들어 위의 표만 가지고, 나머지가 0이냐 0이 아니냐를 가지고 최소항을 찾는다고 하면, 0인 경우를 X로 표시할 때 다음과 같은 표를 얻습니다.
| (mod 2) | (mod 3) | (mod 4) | (mod 5) | (mod 6) | (mod 7) | (mod 8) | (mod 9) | |
|---|---|---|---|---|---|---|---|---|
| 43 | ||||||||
| 44 | X | X | ||||||
| 45 | X | X | X | |||||
| 46 | X | |||||||
| 60 | X | X | X | X | X | |||
| 62 | X | |||||||
| 91 | X | |||||||
| 93 | X |
보다시피 46과 62를 구분할 수 없음을 알 수 있습니다. 이를 구분하기 위해서는 다른 조건을 더 추가해야 합니다. 예를 들어 50보다 작은가 하는 조건을 넣을 수도 있고, 또는 다음과 같이 5로 나눈 나머지가 0이냐를 체크하는 게 아니라 1이냐를 체크해도 되지요.
| (mod 2) | (mod 3) | (mod 4) | 1 (mod 5) | (mod 6) | (mod 7) | (mod 8) | (mod 9) | |
|---|---|---|---|---|---|---|---|---|
| 43 | ||||||||
| 44 | X | X | ||||||
| 45 | X | X | ||||||
| 46 | X | X | ||||||
| 60 | X | X | X | X | ||||
| 62 | X | |||||||
| 91 | X | X | ||||||
| 93 | X |
이제 모든 경우를 서로 구분할 수 있으므로 여기에 따라 적절히 식을 만들어 주면 됩니다. 위의 표를 가지고 시범삼아 만들면 다음과 같이 되겠습니다.
ch % 2 ?
ch % 3 ?
(ch % 7 ? 43 : 91) :
(ch % 9 ? 93 : 45) :
ch % 4 ?
(ch % 5 - 1 ? 62 : 46) :
(ch % 6 ? 44 : 60)
직접 모든 경우에 대해서 테스트해 보시길 바랍니다. 물론 여기에는 공백에 대한 처리가 완전히 빠져 있습니다만 어떻게 해야 할 지는 대략적으로 감이 잡힐 것입니다. 여기와 관련된 수학적 개념으로는 잉여 수 체계(residue number system)가 있으며, 암호학 등에서 여러 가지 방법으로 활용됩니다.
원래 코드로 다시 돌아 와서, 각 경우의 코드와 해당하는 문자를 확인해 보면 각 변수들이 어떤 의미인지 확인할 수 있습니다. 예를 들어 (1)은 +에 해당하는 코드인데, lB가 가리키고 있는 값을 증가시키고 있으므로 lB는 현재 데이터의 포인터를 나타내는 게 자명합니다. (4)는 ,에 해당하는데 l_가 가리키는 값을 현재 칸에 저장한 뒤 증가시키는 것으로 봐서 l_는 입력 버퍼일 거고요. 당연히 B1은 코드 포인터가 되겠습니다. 마지막으로 _1은 다양한 용도로 사용되는 플래그 변수인데, 나중에 살펴 보도록 합니다.
따라서 이 코드는 다음과 같이 바꿀 수 있습니다:
/* 바깥에서 바꿔야 할 이름:
* B1 -> code, lB -> data, l_ -> input, _1 -> flags
*/
int determine_cond(int flags, int *code) {
switch (mapping[*code]) {
case 1:
if (flags & 8) ++*data;
break;
case 2:
if (flags & 8) ++data; /* 현재 값을 참조하지만 사용하지는 않음 */
break;
case 3:
if (flags & 8) printf("%d\n", *data);
break;
case 4:
if (flags & 8) *data = *input++;
break;
default:
break;
case 6:
return 1;
case 7:
if (flags & 8) --*data;
break;
case 8:
if (flags & 8) --data; /* (2)와 동일 */
break;
case 9:
assert(0);
}
return 0;
}
재귀 호출 다림질
이제 main 함수를 정리해 보도록 하겠습니다. 앞에서 변수 이름을 고친 것을 반영하면 다음과 같은 코드가 됩니다.
int main(int flags, int *code) {
int _l_;
int cond;
if (flags & 4) {
if (flags & 2) {
*code = getchar();
cond = *code;
} else {
cond = 2;
}
if (cond) {
if (*code < 1) {
return 1;
} else {
if (*code % 7) {
cond = determine_cond(flags, code);
if (cond) {
return 2;
} else {
return main(flags, code + 1) + 1;
}
} else {
if ((flags & 8) && *data) {
if (main(flags & 14, code + 1)) {
return main(flags & 13 | (flags & 2 ? 1 : 0), code);
} else {
return 0;
}
} else {
if ((_l_ = main(flags & 6 * 1, code + 1))) {
return _l_ + main(flags & 2 ? flags : flags & 12 | (flags & 1 ? 2 : 0), code + _l_);
} else {
return 0;
}
}
}
}
} else {
return 2;
}
} else {
if (flags % 2) {
if (flags / 2) {
return main(scanf("%i", code) ? 3 : 14, code + 1);
} else {
return main(3, input);
}
} else {
return 2;
}
}
}
이 프로그램은 flags 변수에 지대한 영향을 받는데, flags를 사용하는 곳을 보면 이 변수가 4비트로 제한되어 있음을 알 수 있습니다. 또 하나 중요한 점은 flags가 main 함수의 argc 자리에 있고, 프로그램을 실행할 때는 인자가 없어야 하므로 맨 처음에 flags는 항상 1이라는 점입니다.
나중을 위해서 이 함수를 두 개로 분리합니다. 즉 main 함수는 단순히 새로 만들 함수를 호출하는 역할을 하도록 하는 것이지요. 나중에 함수의 인자도 정리할 것이므로 이 쪽이 나을 겁니다.
int recur(int flags, int *code) {
int _l_;
int cond;
if (flags & 4) {
if (flags & 2) {
*code = getchar();
cond = *code;
} else {
cond = 2;
}
if (cond) {
if (*code < 1) {
return 1;
} else {
if (*code % 7) {
cond = determine_cond(flags, code);
if (cond) {
return 2;
} else {
return recur(flags, code + 1) + 1;
}
} else {
if ((flags & 8) && *data) {
if (recur(flags & 14, code + 1)) {
return recur(flags & 13 | (flags & 2 ? 1 : 0), code);
} else {
return 0;
}
} else {
if ((_l_ = recur(flags & 6 * 1, code + 1))) {
return _l_ + recur(flags & 2 ? flags : flags & 12 | (flags & 1 ? 2 : 0), code + _l_);
} else {
return 0;
}
}
}
}
} else {
return 2;
}
} else {
if (flags % 2) {
if (flags / 2) {
return recur(scanf("%i", code) ? 3 : 14, code + 1);
} else {
return recur(3, input);
}
} else {
return 2;
}
}
}
int main(void) {
return recur(1, NULL);
}
main 함수에서 왜 code 포인터에 NULL을 넣었는지 궁금하시다면 앞으로의 설명을 계속 따라 오시길 바랍니다.
이제 flags를 각 비트 별로 분리합니다. 코드에서 flags & 1을 flag0, ..., flags & 8을 flag3으로 바꾸고, flags & 12 같이 두 비트를 함께 쓰는 부분에서는 거기에 맞는 변수를 사용하도록 합니다. 물론 recur 함수의 인자도 여기에 맞춰서 바꿔야 겠지요. 적용되는 코드가 꽤 됩니다만 (특히 determine_cond 함수가 flags를 따로 쓴다는 점에서) 어려운 작업은 아닙니다.
아래 코드에서 저는 단순 텍스트 치환이 아닌 모든 수정에 주석을 달았기 때문에 보기 어렵지는 않을 겁니다. 아, 여기서 "첫번째 비트", "두번째 비트" 등이라고 하는 것은 flags & 1, flags & 2 등입니다.
int recur(int flag0, int flag1, int flag2, int flag3, int *code) {
int _l_;
int cond;
if (flag2) {
if (flag1) {
*code = getchar();
cond = *code;
} else {
cond = 2;
}
if (cond) {
if (*code < 1) {
return 1;
} else {
if (*code % 7) {
/* (flags & 8)만을 사용하므로 flag3에 따라서만 바뀌게 함 */
cond = determine_cond(flag3 ? 8 : 0, code);
if (cond) {
return 2;
} else {
return recur(flag0, flag1, flag2, flag3, code + 1) + 1;
}
} else {
if (flag3 && *data) {
/* (flags & 14)는 최하위 비트를 초기화함 */
if (recur(0, flag1, flag2, flag3, code + 1)) {
/* (flags & 13은 두번째 비트, 즉 flag2를 초기화한다.
* 한편 두번째 비트에 따라 첫번째 비트가 설정될 수도 있는데,
* 첫번째 비트가 설정되는 조건은 원래 첫번째 비트가 설정되어
* 있거나 두번째 비트가 설정되느냐 둘 중 하나이다. */
return recur(flag0 || flag1, 0, flag2, flag3, code);
} else {
return 0;
}
} else {
/* (flags & 6)은 flag1과 flag2만을 남긴다. */
if ((_l_ = recur(0, flag1, flag2, 0, code + 1))) {
/* 두번째 비트가 설정되어 있으면 아무 것도 바뀌지 않는다.
* 아니면 (flags & 12)로 세번째/네번째 비트만 남기고 지운 뒤,
* 첫번째 비트를 두번째 비트로 옮긴다.
* 이 과정은 삼항 연산자(?:)보다는 if로 표현하기 쉽다. */
if (flag1) {
return _l_ + recur(flag0, flag1, flag2, flag3, code + _l_);
} else {
return _l_ + recur(0, flag0, flag2, flag3, code + _l_);
}
} else {
return 0;
}
}
}
}
} else {
return 2;
}
} else {
/* (flags % 2) == (flags & 1) */
if (flag0) {
/* (flags / 2)는 두번째/세번째/네번째 비트 중 하나라도
* 설정하면 참이다. */
if (flag1 || flag2 || flag3) {
/* 이 역시 if 문으로 바꾸는 게 보기 쉽다. */
if (scanf("%i", code)) {
return recur(1, 1, 0, 0, code + 1);
} else {
return recur(0, 1, 1, 1, code + 1);
}
} else {
return recur(1, 1, 0, 0, input);
}
} else {
return 2;
}
}
}
int main(void) {
return recur(1, 0, 0, 0, NULL);
}
if 문의 순서를 바꾸고 정리하면 다음과 같은 코드를 얻을 수 있습니다. 대부분의 수정은 들여쓰기-_-를 줄이기 위한 것입니다만, _l_ 변수에 대입하는 조건문을 별도의 문장으로 떼어 내기도 했습니다.
int recur(int flag0, int flag1, int flag2, int flag3, int *code) {
int _l_;
int cond;
if (!flag2) {
if (flag0) {
if (flag1 || flag2 || flag3) {
if (scanf("%i", code)) {
return recur(1, 1, 0, 0, code + 1);
} else {
return recur(0, 1, 1, 1, code + 1);
}
} else {
return recur(1, 1, 0, 0, input);
}
} else {
return 2;
}
}
if (flag1) {
*code = getchar();
cond = *code;
} else {
cond = 2;
}
if (!cond) return 2;
if (*code < 1) return 1;
if (*code % 7) {
cond = determine_cond(flag3 ? 8 : 0, code);
if (cond) return 2;
return recur(flag0, flag1, flag2, flag3, code + 1) + 1;
} else if (flag3 && *data) {
if (recur(0, flag1, flag2, flag3, code + 1)) {
return recur(flag0 || flag1, 0, flag2, flag3, code);
} else {
return 0;
}
} else {
_l_ = recur(0, flag1, flag2, 0, code + 1);
if (_l_) {
if (flag1) {
return _l_ + recur(flag0, flag1, flag2, flag3, code + _l_);
} else {
return _l_ + recur(0, flag0, flag2, flag3, code + _l_);
}
} else {
return 0;
}
}
}
이제 재귀 호출을 분석할 때입니다. 우선 첫번째 if 문에 있는 flag2는 처음 호출할 때 0으로 설정되어 있는데, 그럼 어디서 바꾸는지 확인해 봐야 겠죠? 직접 확인해 보면 flag2가 0일 때 실행되는 코드 단 한 군데에서만 flag2가 설정되고, 나머지 코드에서는 그대로 유지되는 걸 알 수 있습니다. 그럼 flag2가 설정되었을 때와 설정되지 않았을 때를 나눠서 두 개의 함수를 만들 수도 있겠지요.
int recur_flag2(int flag0, int flag1, int flag2, int flag3, int *code) {
int _l_;
int cond;
assert(flag2);
if (flag1) {
*code = getchar();
cond = *code;
} else {
cond = 2;
}
if (!cond) return 2;
if (*code < 1) return 1;
if (*code % 7) {
cond = determine_cond(flag3 ? 8 : 0, code);
if (cond) return 2;
return recur_flag2(flag0, flag1, flag2, flag3, code + 1) + 1;
} else if (flag3 && *data) {
if (recur_flag2(0, flag1, flag2, flag3, code + 1)) {
return recur_flag2(flag0 || flag1, 0, flag2, flag3, code);
} else {
return 0;
}
} else {
_l_ = recur_flag2(0, flag1, flag2, 0, code + 1);
if (_l_) {
if (flag1) {
return _l_ + recur_flag2(flag0, flag1, flag2, flag3, code + _l_);
} else {
return _l_ + recur_flag2(0, flag0, flag2, flag3, code + _l_);
}
} else {
return 0;
}
}
}
int recur(int flag0, int flag1, int flag2, int flag3, int *code) {
int _l_;
int cond;
assert(!flag2);
if (flag0) {
if (flag1 || flag2 || flag3) {
if (scanf("%i", code)) {
return recur(1, 1, 0, 0, code + 1);
} else {
return recur_flag2(0, 1, 1, 1, code + 1);
}
} else {
return recur(1, 1, 0, 0, input);
}
} else {
return 2;
}
}
이제 recur부터 루프로 바꾸겠습니다. 여기에는 네 가지 코드 경로가 있습니다.
flag0이 거짓이면 2를 반환합니다.flag1,flag2,flag3이 모두 설정되어 있지 않으면flag1을 설정하고input을 넘겨 재귀 호출합니다.flag1,flag2,flag3중 하나라도 설정되어 있으면,- scanf 함수를 호출한 뒤 결과가 참이면 같은 인자에
code만 1 증가시켜 재귀 호출합니다. - 아니면 recur_flag2로 호출이 넘어 갑니다.
- scanf 함수를 호출한 뒤 결과가 참이면 같은 인자에
처음에는 flag0만이 설정되어 있기 때문에 즉각 code에 input이 설정되어 (code에 뭐가 있든 상관이 없겠죠?) 재귀호출할 것이고, 그 다음에는 flag1이 설정되어 scanf를 반복할 것입니다. 그러다가 scanf가 거짓을 반환하면 recur_flag2로 제어권을 넘기는 거죠. 간단한가요?
루프로 바꾸는 건 큰 어려움 없이 가능합니다.
int recur(int flag0, int flag1, int flag2, int flag3, int *code) {
int _l_;
int cond;
assert(!flag2);
/* flag0이 설정되지 않은 경우 애초에 재귀호출을 하지 않는다.
* 하지만 이런 경우는 실제로는 일어나지 않는다. */
assert(flag0);
code = input;
while (scanf("%i", code)) {
++code;
}
return recur_flag2(0, 1, 1, 1, code + 1);
}
이제 recur 함수를 main으로 합치면 다음과 같은 코드가 됩니다.
int main(void) {
int *code = input;
while (scanf("%i", code)) {
++code;
}
return recur_flag2(0, 1, 1, 1, code + 1);
}
이제 recur_flag2를 살펴 볼 차례입니다. 원래 코드는 다음과 같았죠.
int recur_flag2(int flag0, int flag1, int flag2, int flag3, int *code) {
int _l_;
int cond;
assert(flag2);
if (flag1) {
*code = getchar();
cond = *code;
} else {
cond = 2;
}
if (!cond) return 2;
if (*code < 1) return 1;
if (*code % 7) {
cond = determine_cond(flag3 ? 8 : 0, code);
if (cond) return 2;
return recur_flag2(flag0, flag1, flag2, flag3, code + 1) + 1;
} else if (flag3 && *data) {
if (recur_flag2(0, flag1, flag2, flag3, code + 1)) {
return recur_flag2(flag0 || flag1, 0, flag2, flag3, code);
} else {
return 0;
}
} else {
_l_ = recur_flag2(0, flag1, flag2, 0, code + 1);
if (_l_) {
if (flag1) {
return _l_ + recur_flag2(flag0, flag1, flag2, flag3, code + _l_);
} else {
return _l_ + recur_flag2(0, flag0, flag2, flag3, code + _l_);
}
} else {
return 0;
}
}
}
중간에서는 cond가 거짓일 때 2를 반환하는 부분이 있습니다. cond가 0이 될 가능성이 있는 부분은 flag1이 참일 때 getchar를 하는 부분 뿐이므로 if 문을 이 쪽으로 옮겨도 문제는 없겠지요. 그리고 이 쪽으로 if 문을 옮기면 첫번째 cond는 아무 용도에도 쓸모가 없으므로 지워도 됩니다. (변수 선언 자체는 뒤에서도 쓰이므로 지우면 안 됩니다.)
int recur_flag2(int flag0, int flag1, int flag2, int flag3, int *code) {
int _l_;
int cond;
assert(flag2);
if (flag1) {
*code = getchar();
if (!*code) return 2;
}
if (*code < 1) return 1;
if (*code % 7) {
cond = determine_cond(flag3 ? 8 : 0, code);
if (cond) return 2;
return recur_flag2(flag0, flag1, flag2, flag3, code + 1) + 1;
} else if (flag3 && *data) {
if (recur_flag2(0, flag1, flag2, flag3, code + 1)) {
return recur_flag2(flag0 || flag1, 0, flag2, flag3, code);
} else {
return 0;
}
} else {
_l_ = recur_flag2(0, flag1, flag2, 0, code + 1);
if (_l_) {
if (flag1) {
return _l_ + recur_flag2(flag0, flag1, flag2, flag3, code + _l_);
} else {
return _l_ + recur_flag2(0, flag0, flag2, flag3, code + _l_);
}
} else {
return 0;
}
}
}
이제 determine_cond를 이 함수와 합치겠습니다. 이제 flags 대신에 곧바로 flag3을 쓸 수 있겠군요.
int recur_flag2(int flag0, int flag1, int flag2, int flag3, int *code) {
int _l_;
int cond;
assert(flag2);
if (flag1) {
*code = getchar();
if (!*code) return 2;
}
if (*code < 1) return 1;
if (*code % 7) {
cond = 0;
switch (mapping[*code]) {
case 1: if (flag3) ++*data; break;
case 2: if (flag3) ++data; break;
case 3: if (flag3) printf("%d\n", *data); break;
case 4: if (flag3) *data = *input++; break;
default: break;
case 6: cond = 1; break;
case 7: if (flag3) --*data; break;
case 8: if (flag3) --data; break;
case 9: assert(0);
}
if (cond) return 2;
return recur_flag2(flag0, flag1, flag2, flag3, code + 1) + 1;
} else if (flag3 && *data) {
if (recur_flag2(0, flag1, flag2, flag3, code + 1)) {
return recur_flag2(flag0 || flag1, 0, flag2, flag3, code);
} else {
return 0;
}
} else {
_l_ = recur_flag2(0, flag1, flag2, 0, code + 1);
if (_l_) {
if (flag1) {
return _l_ + recur_flag2(flag0, flag1, flag2, flag3, code + _l_);
} else {
return _l_ + recur_flag2(0, flag0, flag2, flag3, code + _l_);
}
} else {
return 0;
}
}
}
이제 이 함수를 어떻게 루프로 바꿀지 고민해 봅시다. 예를 들기 위해서 좀 간단한 다음과 같은 함수를 생각해 보죠.
int sum(int n) {
if (n == 1) return 1;
return sum(n-1) + n;
}
예를 들어 sum(5)를 계산한다 하면, 이는 sum(4) + 5고, 이는 sum(3) + 4 + 5고, ..., 결과적으로 1 + 2 + 3 + 4 + 5로 평가되게 됩니다. 여기까지는 어렵지 않습니다.
문제는 "재귀 후에 숫자가 더해진다"는 것인데, 예를 들어서 반대로 다음과 같은 코드를 생각해 봅시다.
int sum(int n, int prev) {
if (n == 1) return prev+1;
return sum(n-1, prev+n);
}
이 코드는 위와 같은 역할을 하지만 prev 변수가 누산기(accumulator)의 역할을 합니다. 예를 들어 sum(5,0)을 계산하면, 이는 sum(4,0+5)고, 이는 sum(3,0+5+4)고, ..., 결과적으로는 0 + 5 + 4 + 3 + 2 + 1로 같은 값이 됩니다. 이렇게 바뀐 함수는 다음과 같이 루프로 바꿀 수 있습니다.
int sum(int n, int prev) {
while (1) {
if (n == 1) return prev+1;
/* 새 n 값과 prev 값으로 자기 자신을 호출 */
n = n-1;
prev = prev+n;
continue; /* 굳이 필요하지는 않음 */
}
}
이런 식으로 자기 자신을 바로 호출하고 값을 바로 반환하는 경우를 꼬리 재귀(tail recursion)라 하고, 많은 컴파일러들이 이런 경우를 자동으로 인식하여 최적화를 합니다. 재귀를 하면서도 스택을 한 함수 호출만 유지할 수 있기 때문이지요.
하지만 꼬리 재귀가 아닌 것을 꼬리 재귀로 고치는 건 앞에서도 봤듯이 완전 자동화가 힘듭니다. 일단 호출 순서가 바뀌는 게 가장 크지요. 하지만 우리가 가지고 있는 코드에서는 리턴값에 덧셈만 하기 때문에, 정확히 위와 똑같은 방법으로 꼬리 재귀로 고칠 수 있습니다. 먼저 다음과 같이 인자가 하나 더 있는 함수를 만들고,
int recur_flag2_tail(int flag0, int flag1, int flag2, int flag3, int *code, int prev) {
int _l_;
int cond;
assert(flag2);
if (flag1) {
*code = getchar();
if (!*code) return 2;
}
if (*code < 1) return 1;
if (*code % 7) {
cond = 0;
switch (mapping[*code]) {
case 1: if (flag3) ++*data; break;
case 2: if (flag3) ++data; break;
case 3: if (flag3) printf("%d\n", *data); break;
case 4: if (flag3) *data = *input++; break;
default: break;
case 6: cond = 1; break;
case 7: if (flag3) --*data; break;
case 8: if (flag3) --data; break;
case 9: assert(0);
}
if (cond) return 2;
return recur_flag2(flag0, flag1, flag2, flag3, code + 1) + 1;
} else if (flag3 && *data) {
if (recur_flag2(0, flag1, flag2, flag3, code + 1)) {
return recur_flag2(flag0 || flag1, 0, flag2, flag3, code);
} else {
return 0;
}
} else {
_l_ = recur_flag2(0, flag1, flag2, 0, code + 1);
if (_l_) {
if (flag1) {
return _l_ + recur_flag2(flag0, flag1, flag2, flag3, code + _l_);
} else {
return _l_ + recur_flag2(0, flag0, flag2, flag3, code + _l_);
}
} else {
return 0;
}
}
}
int recur_flag2(int flag0, int flag1, int flag2, int flag3, int *code) {
return recur_flag2_tail(flag0, flag1, flag2, flag3, code, 0);
}
...return 문에 있는 함수 호출을 꼬리 재귀에 맞도록 고칩니다. 숫자만 반환할 경우에도 prev와 더해 주어야 합니다.
int recur_flag2_tail(int flag0, int flag1, int flag2, int flag3, int *code, int prev) {
int _l_;
int cond;
assert(flag2);
if (flag1) {
*code = getchar();
if (!*code) return prev + 2;
}
if (*code < 1) return prev + 1;
if (*code % 7) {
cond = 0;
switch (mapping[*code]) {
case 1: if (flag3) ++*data; break;
case 2: if (flag3) ++data; break;
case 3: if (flag3) printf("%d\n", *data); break;
case 4: if (flag3) *data = *input++; break;
default: break;
case 6: cond = 1; break;
case 7: if (flag3) --*data; break;
case 8: if (flag3) --data; break;
case 9: assert(0);
}
if (cond) return prev + 2;
return recur_flag2_tail(flag0, flag1, flag2, flag3, code + 1, prev + 1);
} else if (flag3 && *data) {
if (recur_flag2(0, flag1, flag2, flag3, code + 1)) {
return recur_flag2_tail(flag0 || flag1, 0, flag2, flag3, code, prev);
} else {
return prev;
}
} else {
_l_ = recur_flag2(0, flag1, flag2, 0, code + 1);
if (_l_) {
if (flag1) {
return recur_flag2_tail(flag0, flag1, flag2, flag3, code + _l_, prev + _l_);
} else {
return recur_flag2_tail(0, flag0, flag2, flag3, code + _l_, prev + _l_);
}
} else {
return prev;
}
}
}
int recur_flag2(int flag0, int flag1, int flag2, int flag3, int *code) {
return recur_flag2_tail(flag0, flag1, flag2, flag3, code, 0);
}
이제 recur_flag2_tail 함수는 루프로 고칠 수 있습니다.
int recur_flag2_tail(int flag0, int flag1, int flag2, int flag3, int *code, int prev) {
int _l_;
int cond;
assert(flag2);
while (1) {
if (flag1) {
*code = getchar();
if (!*code) return prev + 2;
}
if (*code < 1) return prev + 1;
if (*code % 7) {
cond = 0;
switch (mapping[*code]) {
case 1: if (flag3) ++*data; break;
case 2: if (flag3) ++data; break;
case 3: if (flag3) printf("%d\n", *data); break;
case 4: if (flag3) *data = *input++; break;
default: break;
case 6: cond = 1; break;
case 7: if (flag3) --*data; break;
case 8: if (flag3) --data; break;
case 9: assert(0);
}
if (cond) return prev + 2;
code += 1;
prev += 1;
continue;
} else if (flag3 && *data) {
if (recur_flag2(0, flag1, flag2, flag3, code + 1)) {
flag0 = flag0 || flag1;
flag1 = 0;
continue;
} else {
return prev;
}
} else {
_l_ = recur_flag2(0, flag1, flag2, 0, code + 1);
if (_l_) {
if (flag1) {
code += _l_;
prev += _l_;
continue;
} else {
flag1 = flag0;
flag0 = 0;
code += _l_;
prev += _l_;
continue;
}
} else {
return prev;
}
}
}
}
코드의 실행
다른 작업을 시작하기 전에 코드를 조금 손 보도록 하겠습니다. 일단 하나는 루프가 끝나기 직전에 시작되는 continue;문을 지우는 것인데, 루프가 끝나기 직전에 재시작해 봐야 아무 것도 안 하는 것과 똑같기 때문이지요.
다른 하나는 if (*code % 7) 조건문을 안쪽의 switch 문으로 합치는 것입니다. (switch 문의 case 9:가 바로 뒷쪽 else 블록이 들어 갈 곳입니다.) switch 문을 합치면서 불필요한 변수, 예를 들어 cond 같은 변수를 없애고, code와 prev를 변화시키는 _l_ 변수가 여기 저기서 나타나므로 하나의 코드로 합치는 작업도 같이 하기 때문에 단순 코드 복사 붙여넣기 수준의 작업은 아닙니다.
마지막으로 recur_flag2 함수를 다른 함수들에 합치고, flag2 변수를 없애 버리도록 하겠습니다. 이제 재귀 함수가 recur_flag2_tail 뿐이므로 이 함수의 이름은 다시 recur로 바꾸겠습니다. (이 함수 이름 재활용 많이 하네요.)
int recur(int flag0, int flag1, int flag3, int *code, int prev) {
int offset; /* 원래 _l_이었음 */
while (1) {
if (flag1) {
*code = getchar();
if (!*code) return prev + 2;
}
if (*code < 1) return prev + 1;
offset = 1;
switch (mapping[*code]) {
case 1: if (flag3) ++*data; break;
case 2: if (flag3) ++data; break;
case 3: if (flag3) printf("%d\n", *data); break;
case 4: if (flag3) *data = *input++; break;
default: break;
case 6: return prev + 2; /* cond가 1인 경우가 이 곳 뿐이므로 합칠 수 있다. */
case 7: if (flag3) --*data; break;
case 8: if (flag3) --data; break;
case 9:
if (flag3 && *data) {
offset = 0;
if (!recur(0, flag1, flag3, code + 1, 0)) return prev;
flag0 = flag0 || flag1;
flag1 = 0;
} else {
/* code += _l_; 등의 코드는 하나로 합쳐졌음. */
offset = recur(0, flag1, 0, code + 1, 0);
if (!offset) return prev;
if (!flag1) {
flag1 = flag0;
flag0 = 0;
}
}
break;
}
code += offset;
prev += offset;
}
}
int main(void) {
int *code = input;
while (scanf("%i", code)) {
++code;
}
return recur(0, 1, 1, code + 1, 0);
}
이제 남은 재귀 호출(네. 루프로 바꾼 거 말고도 또 있습니다!)을 없애 보도록 하겠습니다. 앞에서 flag2를 정리했던 것과 마찬가지 방법으로 flag3을 없앨텐데요, recur을 두 경우에 맞춰 함수 두 개로 나누는 게 포인트라 할 수 있겠습니다. 이게 가능하려면 루프 도중에 flag3이 바뀌는 일이 없어야 하는데 다행히 이 인자는 재귀호출 시에만 바뀌도록 되어 있습니다.
int recur_flag3(int flag0, int flag1, int flag3, int *code, int prev) {
int offset;
assert(flag3);
while (1) {
if (flag1) {
*code = getchar();
if (!*code) return prev + 2;
}
if (*code < 1) return prev + 1;
offset = 1;
switch (mapping[*code]) {
case 1: ++*data; break;
case 2: ++data; break;
case 3: printf("%d\n", *data); break;
case 4: *data = *input++; break;
default: break;
case 6: return prev + 2;
case 7: --*data; break;
case 8: --data; break;
case 9:
if (*data) {
offset = 0;
if (!recur_flag3(0, flag1, flag3, code + 1, 0)) return prev;
flag0 = flag0 || flag1;
flag1 = 0;
} else {
offset = recur_noflag3(0, flag1, 0, code + 1, 0);
if (!offset) return prev;
if (!flag1) {
flag1 = flag0;
flag0 = 0;
}
}
break;
}
code += offset;
prev += offset;
}
}
int recur_noflag3(int flag0, int flag1, int flag3, int *code, int prev) {
int offset;
assert(!flag3);
while (1) {
if (flag1) {
*code = getchar();
if (!*code) return prev + 2;
}
if (*code < 1) return prev + 1;
offset = 1;
switch (mapping[*code]) {
case 1: break;
case 2: break;
case 3: break;
case 4: break;
default: break;
case 6: return prev + 2;
case 7: break;
case 8: break;
case 9:
offset = recur_noflag3(0, flag1, 0, code + 1, 0);
if (!offset) return prev;
if (!flag1) {
flag1 = flag0;
flag0 = 0;
}
break;
}
code += offset;
prev += offset;
}
}
int main(void) {
int *code = input;
while (scanf("%i", code)) {
++code;
}
return recur_flag3(0, 1, 1, code + 1, 0);
}
recur_noflag3이 비교적 간단해진 모습을 볼 수 있습니다. 코드를 보니까 이 함수에서 flag0은 항상 0으로 설정되는 게 확실하고, 따라서 모든 flag0에 대한 참조를 0으로 고칠 수 있습니다. 또한 mapping[*code]가 6일 경우와 9일 경우, 즉 [와 ]에 해당하는 경우만 체크하고 있기 때문에 switch도 줄일 수 있겠죠.
int recur_noflag3(int flag0, int flag1, int flag3, int *code, int prev) {
int offset;
assert(!flag0);
assert(!flag3);
while (1) {
if (flag1) {
*code = getchar();
if (!*code) return prev + 2;
}
if (*code < 1) return prev + 1;
offset = 1;
if (mapping[*code] == 6) { /* ] */
return prev + 2;
} else if (mapping[*code] == 9) { /* [ */
offset = recur_noflag3(0, flag1, 0, code + 1, 0);
if (!offset) return prev;
/* 아래 코드는 flag1이 0일 때 flag1과 flag0을 0으로 고친다.
* 하지만 flag0은 이미 0으로 가정하므로 아래 코드는 아무 영향도 없다. */
/*
if (!flag1) {
flag1 = flag0;
flag0 = 0;
}
*/
}
code += offset;
prev += offset;
}
}
이 함수의 재귀호출 부분에서는 prev, 즉 누산기 역할로 사용되는 인자를 단순히 0으로 쓰고 있지만, 0 대신 다른 숫자를 넣어도 되고 이 값은 결과적으로 원래 함수의 prev에 더해집니다. 0 대신에 그냥 prev를 넣어도 된다는 뜻이죠.
다만 [나 ]가 아닌 문자를 체크할 경우 code와 prev는 항상 1만큼 증가하게 됩니다. 따라서 offset을 사용하는 부분을 각 코드 경로에 맞춰서 복사해 줘야 하는데, 어차피 두 군데 밖에 없습니다.
int recur_noflag3(int flag0, int flag1, int flag3, int *code, int prev) {
assert(!flag0);
assert(!flag3);
while (1) {
if (flag1) {
*code = getchar();
if (!*code) return prev + 2;
}
if (*code < 1) return prev + 1;
if (mapping[*code] == 6) { /* ] */
return prev + 2;
} else if (mapping[*code] == 9) { /* [ */
int prev2 = recur_noflag3(0, flag1, 0, code + 1, prev);
if (prev2 == prev) return prev;
code += prev2 - prev; /* prev2가 증가한 만큼 증가시킴 */
prev = prev2;
} else {
code += 1;
prev += 1;
}
}
}
코드에서 볼 수 있듯이 code와 prev는 서로 같은 크기만큼 증가되는데, 이럴 바에는 prev만 즘가시키고 code는 가만히 냅둔 뒤 *code만 code[prev]로 접근하는 게 낫겠습니다. 이 부분은 조금 설명이 필요하겠군요.
이게 왜 가능한가 하면, 처음에 code0과 prev0 값이 있었다고 할 때 한 함수 안에서 code - code0 값과 prev - prev0 값은 항상 같지요. 그럼 code를 가만히 냅두고 code가 나오는 모든 코드를 code + (prev - prev0)이라고 바꿔도 같은 의미가 됩니다. 재귀 호출에서 code를 바꾸지만 않는다면 이 규칙은 중첩된 함수 안에서도 똑같이 동작할 것이고, 처음에 prev는 0으로 정해져 있으니 code 대신 code + prev로 써도 되게 됩니다. 다만 우리는 재귀 호출을 할 때 code만 하나 증가시키는데, 이 경우 재귀 호출된 함수에서는 code + 1 - code0 == prev - prev0이 성립할 거고, 그 안에서 재귀 호출되면 code + 2 - code0 == prev - prev0이 성립할 거고... 뭐 이렇게 될 겁니다. (여기서 0이 붙은 변수들은 최초에 호출된 함수에서의 code와 prev를 뜻합니다.) 1, 2와 같은 재귀 단계를 기억할 필요가 없이 안에서의 code는 바깥에서 code + 1이라고 정의하면, 즉 원래 호출을 그대로 냅두면, 처음의 불변식인 code - code0 == prev - prev0이 그대로 성립하기 때문에 우리는 이 이상 코드를 고칠 필요가 없습니다.
조금 복잡할 수 있으니 직접 임의의 입력을 가정해서 테스트해 보시는 게 좋겠습니다. 하여튼 이렇게 하면 code가 바뀌는 경우를 거의 모두 지울 수 있겠죠.
int recur_noflag3(int flag0, int flag1, int flag3, int *code, int prev) {
assert(!flag0);
assert(!flag3);
while (1) {
if (flag1) {
code[prev] = getchar();
if (!code[prev]) return prev + 2;
}
if (code[prev] < 1) return prev + 1;
if (mapping[code[prev]] == 6) { /* ] */
return prev + 2;
} else if (mapping[code[prev]] == 9) { /* [ */
int prev2 = recur_noflag3(0, flag1, 0, code + 1, prev);
if (prev2 == prev) return prev;
prev = prev2;
} else {
prev += 1;
}
}
}
또 하나. prev2가 prev와 같은 경우가 실제로 있을까요? 이 함수에는 return 문이 세 개가 있는데, 반환값이 prev와 같을 수 있는 경우는 단 하나, 재귀 호출 뒤 prev2와 prev가 같은 경우 뿐입니다. (다른 곳에서 prev를 그대로 반환할 경우 그걸 시발점으로 모든 재귀 호출이 끝날 수는 있겠습니다. 하지만 이 경우는 아니지요.) 따라서 prev2는 절대로 prev와 같을 수 없고, 해당하는 코드를 지우면 다음과 같은 간단한 코드가 나타납니다.
int recur_noflag3(int flag0, int flag1, int flag3, int *code, int prev) {
assert(!flag0);
assert(!flag3);
while (1) {
if (flag1) {
code[prev] = getchar();
if (!code[prev]) return prev + 2;
}
if (code[prev] < 1) return prev + 1;
if (mapping[code[prev]] == 6) { /* ] */
return prev + 2;
} else if (mapping[code[prev]] == 9) { /* [ */
prev = recur_noflag3(0, flag1, 0, code + 1, prev);
} else {
prev += 1;
}
}
}
이 함수의 역할을 이해하려면 직접 code가 가리키는 배열을 상상하면 되겠습니다. 예를 들어서 code가 다음과 같은 값들로 차 있다고 합시다. (code가 가리키는 배열은 정수의 배열이긴 합니다만 실제로는 문자 배열의 역할을 하므로 문자열로 다루겠습니다.)
...[abcdef[ghi]jklm]no...
recur_flag3 함수가 [를 만나면, recur_noflag3 함수를 호출할 때 [ 다음 글자의 포인터를 넘기기 때문에 처음에 code는 a를 가리킵니다. 이제 여섯 개의 평범한 문자를 지나치면 prev는 6이 되고, [를 만나면 재귀 호출을 하면서 code는 1 증가하고 code[6]은 g를 가리키게 됩니다. 세 개의 문자를 지나친 뒤 prev는 9가 되고, ]를 만났기 때문에 안쪽 재귀 호출은 11을 반환합니다. 이제 네 개의 문자를 지나친 뒤 prev는 15가 되며, ]를 만났기 때문에 함수는 17을 반환하게 됩니다.
[와 ]까지의 문자 갯수를 세어 보면 정확히 17개입니다. 따라서 이 함수는 [와 ]로 둘러 쌓인 코드의 길이를 반환합니다. 사실, [에서 code는 증가하고 prev는 안 증가하지만 ]에서는 code는 안 변하고 prev는 2 증가하기 때문에 괄호의 짝만 맞으면 정확한 길이를 찾아 내는 것입니다.
만약 [가 짝이 안 맞는 경우라면 어떻게 될까요? 예를 들어서, flag1이 설정되어 있어서 계속 입력을 받는데 파일의 끝이 나왔다고 합시다. 이 경우 getchar가 음수(EOF)를 반환할테니 code가 가리키는 값도 음수겠지요. 이 문자를 편의상 @로 표현하면 배열은 다음과 같이 될 것입니다.
...[abcdef[gh@
그럼 h까지는 제대로 진행되는데, 음수를 만난 시점에서 안쪽 재귀 호출은 ]를 만났을 경우랑 거의 비슷하지만 1 작은 결과를 반환합니다. 그럼 바깥쪽 함수에서 다음으로 찾는 문자는 똑같이 그 음수가 될테고, 결과적으로 [abcdef[gh라는 문자열의 길이, 10을 반환하게 됩니다. 따라서 위의 코드는 다음 코드와 같은 의미가 됩니다.
...[abcdef[gh]]
이제 이 코드를 비재귀로 바꿔 보겠습니다. 단순히 [와 ]를 만날 때마다 괄호가 중첩된 깊이를 계산하고 prev를 계속 증가시켜 나가면 되기 때문에 어렵지 않습니다. (code가 [를 만나면 혼자서 증가하거나 하는 것까지 재현하면 스택이 필요하겠지만, 그럴 필요는 없죠.) 좀 전에 재귀 호출을 할 때 prev를 서로 주고 받도록 코드를 바꾼 이유도 이런 식으로 하나의 변수로 통일하기가 쉽기 때문입니다.
int recur_noflag3(int flag0, int flag1, int flag3, int *code, int prev) {
int depth = 1; /* 처음에는 [ 바로 뒤에서 시작한다. */
assert(!flag0);
assert(!flag3);
assert(prev == 0);
while (1) {
if (flag1) {
code[prev] = getchar();
if (!code[prev]) {
/* ]를 만났을 때와 똑같이 동작한다. */
goto closing_bracket;
}
}
if (code[prev] < 1) break;
if (mapping[code[prev]] == 9) { /* [ */
++depth;
++prev;
} else if (mapping[code[prev]] == 6) { /* ] */
closing_bracket:
--depth;
++prev;
if (depth == 0) break;
} else {
++prev;
}
}
/* 반환값에는 호출하는 쪽에서 건너 뛴 [도 포함되어야 한다. */
return prev + 1;
}
이제 이 함수가 하는 일을 알았으니 함수 이름을 고치고, recur_flag3에서 이 함수를 호출할 때 쓸데 없는 인자를 주지 않도록 인자를 정리하겠습니다.
int get_loop_length(int read_code /* 본래는 flag1 */, int *code) {
int len = 0; /* 본래는 prev */
int depth = 1;
while (1) {
if (read_code) {
code[len] = getchar();
if (!code[len]) goto closing_bracket;
}
if (code[len] < 1) break;
if (mapping[code[len]] == 9) { /* [ */
++depth;
++len;
} else if (mapping[code[len]] == 6) { /* ] */
closing_bracket:
--depth;
++len;
if (depth == 0) break;
} else {
++len;
}
}
return len + 1;
}
int recur_flag3(int flag0, int flag1, int flag3, int *code, int prev) {
/* ... */
offset = get_loop_length(flag1, code + 1);
/* ... */
}
이제 recur_flag3을 살펴 봅시다. 지금까지 상당히 많은 코드를 정리했기 때문에 대부분의 인자가 더 이상 소용이 없는데, 직접 함수 호출을 확인해 보면 flag0(0으로 고정), flag3(1로 고정), prev(0으로 고정) 세 개의 인자가 항상 일정하므로 지울 수 있습니다. flag1은 앞에서 코드를 읽는 데 사용된다고 했으니 똑같은 이름으로 바꾸도록 하죠.
int recur_flag3(int read_code, int *code) {
int offset;
int flag0 = 0;
int prev = 0;
while (1) {
if (read_code) {
*code = getchar();
if (!*code) return prev + 2;
}
if (*code < 1) return prev + 1;
offset = 1;
switch (mapping[*code]) {
case 1: ++*data; break;
case 2: ++data; break;
case 3: printf("%d\n", *data); break;
case 4: *data = *input++; break;
default: break;
case 6: return prev + 2;
case 7: --*data; break;
case 8: --data; break;
case 9:
if (*data) {
offset = 0;
if (!recur_flag3(read_code, code + 1)) return prev;
flag0 = flag0 || read_code;
read_code = 0;
} else {
offset = get_loop_length(read_code, code + 1);
if (!offset) return prev;
if (!read_code) {
read_code = flag0;
flag0 = 0;
}
}
break;
}
code += offset;
prev += offset;
}
}
이 함수 안의 재귀 호출은 두 개가 있는데, 후자인 get_loop_length는 0을 절대로 반환하지 않기 때문에 ([는 이미 건너 뛰었으므로 반환값은 1 이상) 그 다음에 반환값을 체크하는 코드는 전혀 소용이 없습니다. 전자인 recur_flag3의 경우 조금 더 복잡한데, 사실은 앞에서 recur_noflag3을 정리할 때와 같은 이유로 이 함수의 반환값은 0이 될 수 없습니다. 따라서 두 개의 if 문은 깔끔하게 걷어 낼 수 있습니다.
이런 식으로 아무 의미도 없는 if 문이 나오는 가장 큰 이유는, 원래 코드에서 연속으로 실행되는 두 코드를 단순히 삼항 연산자 ?:로 묶어 버렸기 때문입니다. 삼항 연산자의 조건이 항상 참이거나 거짓이면 다른 한 쪽은 뭐래도 상관이 없죠.
뭐 이렇게 되고 보니 recur_flag3 함수의 반환값을 사용하는 곳이 사라졌으니 (main 함수 빼고) return할 때 반환값을 굳이 신경쓸 필요도 없게 되었습니다. 편의상 모두 0을 반환하도록 고치겠습니다.
int recur_flag3(int read_code, int *code) {
int offset;
int flag0 = 0;
while (1) {
if (read_code) {
*code = getchar();
if (!*code) return 0;
}
if (*code < 1) return 0;
offset = 1;
switch (mapping[*code]) {
case 1: ++*data; break;
case 2: ++data; break;
case 3: printf("%d\n", *data); break;
case 4: *data = *input++; break;
default: break;
case 6: return 0;
case 7: --*data; break;
case 8: --data; break;
case 9:
if (*data) {
offset = 0;
recur_flag3(read_code, code + 1);
flag0 = flag0 || read_code;
read_code = 0;
} else {
offset = get_loop_length(read_code, code + 1);
if (!read_code) {
read_code = flag0;
flag0 = 0;
}
}
break;
}
code += offset;
}
}
이제 [를 만났을 때의 코드를 자세히 봅시다.
if (*data) {
offset = 0;
recur_flag3(read_code, code + 1);
flag0 = flag0 || read_code;
read_code = 0;
} else {
offset = get_loop_length(read_code, code + 1);
if (!read_code) {
read_code = flag0;
flag0 = 0;
}
}
이 코드에서는 *data가 참이면 offset을 0으로 설정해서 코드 포인터를 같은 곳에서 맴돌도록 하고 있습니다. 원래 Brainfuck의 동작을 생각하면 이게 반복을 처리하는 코드임을 알 수 있죠. while 문으로 바꾸면 어떨까요?
while (*data) {
offset = 0;
recur_flag3(read_code, code + 1);
flag0 = flag0 || read_code;
read_code = 0;
/* 본래 바깥쪽에 있던 코드들 */
if (read_code) {
*code = getchar();
if (!*code) return 0;
}
if (*code < 1) return 0;
}
assert(*data == 0);
offset = get_loop_length(read_code, code + 1);
if (!read_code) {
read_code = flag0;
flag0 = 0;
}
offset은 루프를 빠져나간 뒤에 다시 바뀌기 때문에 루프 안에서 설정할 필요가 없고, read_code를 체크하는 조건문은 항상 성립되지 않으므로 지워도 됩니다. *code < 1 역시 switch 문 바깥에서 체크했으므로 항상 성립되지 않고요.
while (*data) {
recur_flag3(read_code, code + 1);
flag0 = flag0 || read_code;
read_code = 0;
}
assert(*data == 0);
offset = get_loop_length(read_code, code + 1);
if (!read_code) {
read_code = flag0;
flag0 = 0;
}
이제 flag0의 의미를 확인해 봅시다. 우선 while 문 안에서 flag0과 read_code를 설정하는 코드를, 같은 의미이면서 뒤에 나오는 코드와 비슷한 형태로 고칠 수 있습니다.
while (*data) {
recur_flag3(read_code, code + 1);
if (read_code) {
flag0 = read_code; /* 이 값은 항상 1임 */
read_code = 0;
}
}
assert(*data == 0);
offset = get_loop_length(read_code, code + 1);
if (!read_code) {
read_code = flag0;
flag0 = 0;
}
flag0은 read_code가 참일 때 설정되고, read_code는 거짓이 됩니다. 루프가 끝난 뒤 read_code는 flag0가 저장하고 있던 값을 다시 돌려 받게 되죠. 따라서 flag0은 read_code를 임시로 저장하는 역할을 하고, 대략 saved_read_code 같은 이름으로 바꿀 수 있습니다. 그럼 이게 무슨 의미일까요?
recur_flag3과 get_loop_length 두 함수는 본래 한 함수였음(!)을 생각해 봅시다. 그럼 이들 함수들을 호출할 때 맨 처음 호출에서만 read_code가 1이 될 수 있고, 나머지 호출에서는 read_code가 0이며, flag0의 가능한 값을 대조해 보면 모든 게 끝난 뒤 read_code는 루프를 시작하기 전의 read_code로 다시 돌아 옵니다. 즉, 이 코드는 같은 코드가 단 한 번씩만 읽히도록 하기 위해 만들어진 코드인 것입니다.
recur_flag3 함수는 [와 ]로 묶인 코드를 실행하고, [를 만나면 자기 자신을 재귀 호출하거나 다음 ]로 건너 뜁니다. read_code 인자는 아직 여기에 해당하는 코드가 표준 입력에서 읽히지 않았다는 뜻이며, [를 만날 때까지 이 값에 따라 코드를 읽어 들이게 됩니다. [를 만나면 재귀 호출을 해야 하는데(recur_flag3이든 get_loop_length든) 이 함수들에서도 코드는 필요하니 read_code를 넘겨 줘야 합니다. 그런데 이 함수들은 여러 번 불릴 수 있기 때문에, 첫번째 호출이 아닌 이상 중복으로 코드를 읽는 걸 방지하려면 read_code이 0이어야 합니다. 일단 다음 ]를 읽은 뒤에는 다시 원래 read_code로 돌아 와서 나머지 코드를 읽는 거고요.
이 코드가 매우 복잡한 이유도 여기에 있습니다. 하나의 함수 안에 플래그가 네 개 존재하는데, 하나(flag2)는 입력을 읽는지 코드를 읽는지를 체크하고, 하나(flag3)는 현재 루프에 해당하는 코드를 건너 뛸지 그냥 실행할지를 결정하고, 하나(flag1)는 다음에 코드 문자를 읽어야 할 지 아니면 이미 읽혔으니 포인터를 그냥 참조하면 되는지를 결정하며, 마지막 하나(flag0)는 현재 루프가 끝났을 때 다시 코드 문자를 읽어야 할 지를 저장하고 있습니다. 덤으로 flag0만 설정되고 나머지가 꺼져 있으면 재귀 호출이 아니라 처음에 main 함수가 불렸다는 뜻이 되고요.
뭐 복잡한 건 IOCCC 코드의 공통된 특징이니 넘어 가기로 하고, 그럼 recur_flag3을 다시 정리하고 넘어 가겠습니다. 별로 바뀌는 건 없고 주석만 좀 많이 추가했습니다.
int recur_flag3(int read_code, int *code) {
int saved_read_code = 0; /* 원래 flag0이었음 */
while (1) {
/* 필요하면 코드를 읽어 들인다. */
if (read_code) {
*code = getchar();
if (!*code) return;
}
/* EOF 등이 나오면 현재 루프를 종료한다.
* 만약 루프가 제대로 닫히지 않았으면, 마지막 글자에서 모든 루프가
* 닫히는 것처럼 행동한다. */
if (*code < 1) return;
switch (mapping[*code++]) {
case 1: ++*data; break; /* + */
case 7: --*data; break; /* - */
case 2: ++data; break; /* > */
case 8: --data; break; /* < */
case 3: printf("%d\n", *data); break; /* . */
case 4: *data = *input++; break; /* , */
case 6: /* ] */
return;
case 9: /* [ */
while (*data) {
/* 다음 ]가 나올 때까지 실행한다. */
recur_flag3(read_code, code);
/* read_code가 이미 설정되어 있으면 임시로 거짓으로 만들고
* 원래 값을 보관한다. */
if (read_code) {
saved_read_code = 1;
read_code = 0;
}
}
assert(*data == 0);
code += get_loop_length(read_code, code) - 1; /* 앞의 [는 제외 */
/* 보관된 read_code를 복원한다. */
if (!read_code) {
read_code = saved_read_code;
saved_read_code = 0;
}
break;
default: /* 공백 등등, 무시됨. */
break;
}
}
}
이제 코드의 흐름이 눈에 보이죠? 마지막으로 마저 남아 있던 변수 이름을 고치고 주석을 더한 뒤 정리한 최종 코드는 다음과 같습니다.
#include <stdio.h>
#include <assert.h>
/* 문자와 실제 코드 문자와의 매핑. */
static const int mapping[128] = {
9, 1, 2, 6, 4, 7, 5, 9, 5, 5, 5, 1, 5, 1, 9, 7, 5, 1, 6, 1, 8, 9, 5, 1,
5, 7, 2, 5, 9, 1, 5, 1, 5, 6, 5, 9, 5, 1, 2, 5, 8, 1, 9, 1, 4, 7, 3, 1,
6, 9, 5, 5, 4, 1, 5, 7, 9, 5, 5, 1, 8, 1, 2, 9, 5, 7, 5, 1, 4, 5, 9, 1,
5, 1, 2, 7, 4, 9, 6, 1, 8, 5, 5, 1, 9, 7, 2, 5, 5, 1, 5, 9, 4, 6, 5, 7,
5, 1, 9, 5, 8, 1, 5, 1, 5, 9, 3, 1, 6, 1, 5, 5, 9, 1, 5, 7, 4, 5, 5, 9,
8, 1, 2, 6, 4, 7, 9, 1};
/* codebuf는 입력과 코드를 담는다. 입력과 코드는 별도로 구분되지 않으며
* 입력이 모두 소진되면 코드 영역에 있는 내용을 읽을 수도 있다.
* databuf는 프로그램이 사용하는 메모리를 담는다. */
int codebuf[3125], databuf[3125]; /* 본래 BI, _I였음 */
/* 현재 데이터 포인터와 다음 , 명령이 읽을 값을 가리키는 포인터. */
int *input = codebuf, *data = databuf;
/* 주어진 code로부터 처음으로 짝이 맞지 않는 ]나 프로그램의 끝까지
* 얼마나 많은 문자를 건너 뛰어야 하는지 반환한다.
* (일반적으로 code는 [ 다음 글자지만, 아니어도 작동에는 문제가 없다.)
* read_code가 주어지면 코드를 읽으면서 진행한다. */
int skip_block(int read_code, int *code) {
int len = 0;
int depth = 1;
while (1) {
if (read_code) {
code[len] = getchar();
if (!code[len]) goto closing_bracket;
}
if (code[len] < 1) break;
if (mapping[code[len]] == 9) { /* [ */
++depth;
++len;
} else if (mapping[code[len]] == 6) { /* ] */
closing_bracket:
--depth;
++len;
if (depth == 0) break;
} else {
++len;
}
}
return len;
}
/* 주어진 code로부터 처음으로 짝이 맞지 않는 ]나 프로그램의 끝까지
* 코드를 실행한다. 만약 루프가 제대로 닫히지 않았으면,
* 마지막 글자에서 모든 루프가 닫히는 것처럼 행동한다.
* read_code가 주어지면 코드를 읽으면서 진행한다. */
void execute_block(int read_code, int *code) {
int saved_read_code = 0;
while (1) {
if (read_code) {
*code = getchar();
if (!*code) return 0;
}
if (*code < 1) return 0;
switch (mapping[*code++]) {
case 1: ++*data; break; /* + */
case 7: --*data; break; /* - */
case 2: ++data; break; /* > */
case 8: --data; break; /* < */
case 3: printf("%d\n", *data); break; /* . */
case 4: *data = *input++; break; /* , */
case 6: /* ] */
return 0;
case 9: /* [ */
while (*data) {
execute_block(read_code, code);
/* read_code가 이미 설정되어 있으면 임시로 거짓으로 만들고
* 원래 값을 보관한다. */
if (read_code) {
saved_read_code = 1;
read_code = 0;
}
}
assert(*data == 0);
code += skip_block(read_code, code);
/* 보관된 read_code를 복원한다. */
if (!read_code) {
read_code = saved_read_code;
saved_read_code = 0;
}
break;
default: /* 공백 등등. 여기에는 입력과 코드를 구분하는 ":"도 포함된다. */
break;
}
}
}
int main(void) {
/* 숫자가 아닌 게 나올 때까지 입력을 읽는다. */
int *code = input;
while (scanf("%i", code)) ++code;
/* 그 다음부터 코드를 읽으면서 실행한다. */
execute_block(1, code + 1);
return 0;
}
총 정리
이 코드는 흥미로운 방법으로 코드를 알아 볼 수 없게 만드는 데 성공했습니다. 그 중 몇 개만 들자면,
- 전처리기를 사용해서 코드 상에 나타난 모든 숫자를
1+1+1+...+1형태로 바꾼 것. - main 함수의 다중 재귀와 삼항 연산자들.
- 엽기적인 명령 디코딩 과정. 덤으로 엉뚱한 문자를 명령으로 쓸 수도 있게 되었음.
- 복잡한 내부 상태 관리. 특히 코드를 미리 읽는 것이 아니라 명령을 실행하기 직전에 읽는 것을 구현하기 위해서 상태가 더 복잡해졌음.
- 안 그래도 복잡한 내부 상태를 십분 활용하는 루프 구현.
심사위원들은 이 프로그램에 대해 설명하면서 "어떤 콰인(자기 자신을 출력하는 프로그램)들은 동작하지 않는다"라고 했는데, 여기에 대한 이유는 사실 자명합니다. 바로 그 엽기적인 명령 디코딩 과정 때문이지요. 예를 들어 Ryan Kusnery의 프로그램 같은 경우 코드 자체에 #가 포함되어 있고, []로 묶은 "주석" 영역은 대부분의 인터프리터가 무시해야 하지만 이 프로그램에서는 다른 괄호로 인식될 수도 있습니다. 일반적으로 아무 다른 문자도 없이 "깔끔한" 코드여야만 이 프로그램에서 잘 실행된다고 할 수 있겠죠.
심사위원들이 함께 던진 문제는 좀 더 흥미롭습니다. 원래 프로그램에서 세 글자만 고치면 이 프로그램이 덜 어려워진다고 합니다. 과연 어떤 방법일까요? 문제의 세 글자가 뭔지는 저도 모르겠지만, 아무래도 이 프로그램은 코드를 읽으면서 실행하는 과정이 복잡하다 보니 코드를 미리 모두 읽은 뒤 실행하도록 바꾸는 코드일 것입니다. 예를 들어서, 원래 코드를 전처리한 뒤 들여쓰기로 정리한 다음 코드에서,
if (_1 / 2) {
return main(scanf("%i", B1) ? 3 : 14, B1 + 1);
} else {
return main(3, l_);
}
이 코드를 다음과 같이 고치면,
if (_1 / 2) {
return main(scanf("%i", B1) ? 3 : main(6, B1 + 1) ? 12 : 0, B1 + 1);
} else {
return main(3, l_);
}
main(6, B1 + 1)은 코드를 읽기는 하되 실행은 하지 않도록 합니다. 이 결과는 항상 참으로 평가되고, main(12, B1 + 1)은 코드를 읽지 않고 실행만 하도록 하므로 실제로는 같은 일을 하는 것이지요. 여기에 해당하는 원본 소스 코드(...) 마지막 줄은 다음과 같고,
("%i",__1 ____1 _____):(___l _____)-____,__1 +____):_ _____,l_):__;}
대강 대충 돌아 가도록 고친 코드는 다음과 같습니다.
("%i",__1 ____1 _____):_ __+__+__,__1+____)?(___l __)+__:__,__1+____
):_ _____,l_):__;}
정확히 사각형으로 나눠 떨어지지 않는 게 좀 아쉽습니다만 뭐 적절히 고치면 큰 문제는 없겠군요. 혹시 세 글자만으로 가능한 방법을 알아내신 분께서는 연락해 주시면 감사하겠습니다 :)