SICP 연습문제 2.6 친절한 풀이

문제

프로시저로 쌍을 나타낼 수 있다는 것이 황당하지 않았다면, 프로시저를 다룰 수 있는 언어에서 (양의 정수만 가지고 이야기한다면) 수의 표현을 빌리지 않고, 0과 더하기 1을 다음과 같이 프로시저 연산으로 나타낼 수 있다.

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

이런 표현 방법을 처치의 수^{Church numeral}라 하는데, 이는 람다계산법을 처음 만들어 낸 논리학자 엘렌조 처치의 이름을 딴 것으로 알려져 있다. one과 two를 zero와 add-1을 쓰지 않고 곧바로 정의해 보라. (귀띔: 맞바꿈계산법으로 (add-1 zero)를 풀어 보라.) 덧셈 프로시저 +를 (add-1을 여러번 되풀이하지 말고) 곧바로 정의하라.

문제로 부터 얻은 것

문제를 풀기 위해 람다 대수를 따로 공부했습니다.
오버헤드가 조금 큰 감이 있지만, 배우는 것이 많았습니다.
다른 함수형 프로그래밍의 이론적 지식을 공부할 떄, 분명 도움이 될 것입니다.

문제풀이

이 문제를 정확히 이해하기 위해서는 람다 대수에 관한 지식이 조금 필요합니다.
이 문제를 위해 처치의 수를 간단히 설명해 보겠습니다.
람다대수에서 모든 것은 함수입니다.
심지어 숫자나 논리연산같은 것들도 모두 함수입니다.
람다대수에서 1은 λsz.s(z)라는 함수로 표현하기로 약속했습니다.
s와 z를 인자로 받아서 s(z)를 반환하겠다는 뜻입니다.
비슷한 원리로 2는 λsz.s(s(z))이고 3은 λsz.s(s(s(z)))입니다.
즉, z라는 인자에 s함수를 몇번 적용하는지가 그 숫자가 나타내는 값이라고 할 수 있습니다.
0을 함수로 나타내면 문제에서 본 것처럼 (lambda (f) (lambda (x) x))입니다.
첫번째 인자인 f를 두번째 인자인 x에 0번 적용하겠다는 뜻입니다.
자세한 설명이 필요하신 분들은 람다 대수 입문 번역을 읽어주시기 바랍니다

1. one과 two

(add-1 zero)를 정리한 함수인 one은 아래와 같습니다.

(lambda (f) (lambda (x) (f x)))

즉, 1을 나타내는 함수 one은 (lambda (f) (lambda (x) (f x)))입니다.

$one = (lambda (f) \ (lambda (x) \ (f \ x)))$

2를 나타내는 함수 two는 (add-1 one)으로 구할 수 있습니다.

$two = (lambda (f) \ (lambda (x) \ (f \ (f \ x))))$

앞서 설명한 것처럼 두 인자 f와 x를 받아서 x에 f를 몇번 적용하는 지가 람대대수의 숫자표현입니다.

2. 더하기 함수

람다대수에서는 숫자도 함수라고 약속했습니다.
람다대수로 나타낸 숫자는 함수 f와 x를 인자로 받아서 x에 f를 숫자의 크기만큼 적용하는 함수입니다.
이 원리를 이용하면 더하기 함수를 짜는 힌트를 얻을 수 있습니다.
n+m을 계산하는 것은, 두번째 인자로 받은 x에 f를 n번 적용하고나서 다시 m번 적용하는 것과 같습니다.
다시말하면 (n f)를 x에 적용한 후에 다시 (m f)를 적용하는 것입니다.
(n f)는 f를 n번 적용하는 함수를 뜻하기 때문입니다.

$n+m = (f \ (f ⋯ (f \ x)))$

f의 갯수는 n+m개

그러므로 더하기 함수를 구현하면 다음과 같습니다.

(define (+ n m)
  (lambda (f)
    (lambda (z)
      ((n f) ((m f) z))))
)

읽어주셔서 감사합니다.