이 문제는 프로시저를 인자로 받아

그 프로시저를 두 번 계산하는 프로시저인 double 프로시저를 만들어

(((double (double double)) inc) 5)의 식의 값을 구하는 문제입니다.

여기서 inc 프로시저는 하나의 인자를 받아 그 인자에 1을 더한 값을 반환합니다.

double 프로시저는 간단하게 만들었습니다.

그리고 ((double inc) 5)로 7이 나오는 것을 확인하였습니다.

이제 문제에 나오는 식을 돌려보았습니다.

답은 21이 나왔습니다.

이유는 다음과 같습니다.

먼저 (double double)를 구하면 다음과 같은 lambda식이 나옵니다.

(lambda (x) (double (double x)))

여기서 x는 프로시저 인자입니다.

이를 해석하면 다음과 같습니다.

(double x)는 x 프로시저가 두 번 실행되는 lambda 식이 나옵니다.

그 식을 한 번더 double하였으니

x 프로시저를 두 번 실행하는 lambda 식을 두 번 실행하는 lambda시기 나옵니다.

(상당히 길군요.)

x 프로시저를 두 번 실행하는 lambda 식을 두 번 실행하기에

x 프로시저는 총 네 번 실행이 됩니다.

x 프로시저를 총 네 번 실행시키는 lambda 식을 p_4라고 하겠습니다.

이 식을 double 프로시저의 인자로 들어갑니다.

그럼 반환되는 lambda 식은 다음과 같습니다.

(lambda (x) (p_4 (p_4 x)))

위의 식은 x 프로시저를 총 네 번 실행시키는 lambda 식인 (p_4 x)을

총 네 번 실행시키는 lambda 식입니다.

그렇기에 4 * 4가 되어 x 프로시저를 16번 실행시키는 lambda 식이 됩니다.

처음에 저는 8번 실행하여 13이 나올 것이라 생각했습니다.

하지만 결과는 16번 실행하여 21이 나왔습니다.

이는 반환되어 다시 인자가 들어가는 것에 실수가 있었기에

이런 실수는 많아 어디가 틀렸는지 금방 알 수 있었습니다.

그보다 이 문제에 대한 설명을 어떻게 블로그에 적어야 하는가 고민이었습니다.

지금 제가 한 설명이 그리 만족스럽지 못합니다.

알고 있는 것과 가르치는 것은 이처럼 다릅니다.ㅜㅜ

하지만 이렇게 전개되는 프로시저인 듯싶습니다.

double을 하나 실행하면 인자로 들어온 프로시저(이후로 p)를 두 번 실행합니다.

이 double을 double하면 p를 두 번 실행하는 프로시저가 두 번 실행되기에

2 * 2 = 4 즉 p를 네 번 실행하는 프로시저가 됩니다.

다음으로 double을 세 번 실행하면 p를 네 번 실행하는 프로시저가 네 번 실행되기에

4 * 4 = 16이 즉 p를 16번 실행하는 프로시저가 됩니다.

이를 확장하면 다음과 같습니다.

2, 4, 16, 256 ....

이는 앞의 항을 제곱하여 구하는 형식이니

a_n = 2^b_n {b_n = 2^(n-1)}입니다.

(((double (double (double (double double)))) inc) 5)

위의 식을 실행시키니 65541이 나옵니다.

이는 65536 + 5이니 inc를 65536번 즉, 2^16번 실행시킵니다.

double이 5번 나오니 맞군요.^^

참조

Structure and Interpretation of Computer Programs 2/E - Page 98

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.