람다 표현과 처치 인코딩(1)

람다 표현(Lambda Expression)이란?

간단히 설명하자면, 람다 표현은 어떤 함수를 이름 없이 표현하는 방식이라 할 수 있습니다. 이런 특징으로 인해, 람다 표현은 종종 익명 함수(anonymous function)라고 불리기도 합니다.

‘이름 없이 표현한다’는 의미를 좀 더 와닿게 하기 위해, 한 가지 예시를 들어보도록 하겠습니다. 만약 $x$를 받아서 $x+1$을 내놓는 함수를 표현하고 싶다면 어떻게 해야 할까요?

보통의 경우, 아래와 같이 수학적인 표현법을 사용할 수 있습니다.

$ f(x) = x + 1 $

눈치채셨을지도 모르지만, 어느새 이 함수에는 $f$라는 이름이 생겼습니다. 사실, 이 함수가 꼭 $f(x)$여야 할 필요도 없습니다. 이것을 $g(x)$라고 부르든 $h(x)$라고 부르든, 이것이 $x$를 받아서 $x+1$을 내놓는 함수라는 사실에는 변함이 없기 때문입니다.

본질적으로 봤을 때, 함수의 이름은 중요하지도 않고 꼭 있어야 할 필요도 없습니다. 그러나, $f(1)=2$, $f(4)=5$ 처럼 이 함수를 사용해서 식을 쓰려면 어떻게든 이름을 지어주어야 합니다. 그렇지 않고는 이 함수에다가 어떤 값을 넣는다는 걸 마땅히 표현할 방법이 없기 때문이죠.

이 때, 함수의 이름을 정하지 않고도 사용할 수 있게 해 주는 것이 바로 람다 표현입니다. 예를 들어, 위에서 사용한 예시인 $x$를 받아서 $x+1$을 내놓는 함수는 람다 표현으로 $\lambda x.x+1$처럼 나타낼 수 있습니다.

위의 예시에서 볼 수 있듯이, $\lambda$ 다음에는 함수가 받을 매개변수의 이름을 써주고, 점($.$)을 찍은 다음에는 함수가 내놓을 값을 쓰면 람다 표현이 완성됩니다.

아래는 람다 표현을 만드는 몇 개의 예시입니다.

상수함수 $ f(x) = 1 \quad \leftrightarrow \quad \lambda x.1$
항등함수 $ f(x) = x \quad \leftrightarrow \quad \lambda x.x$

함수에 어떤 값을 적용하는 것은 람다 표현 오른쪽에 단순히 이어서 씀으로써 표현합니다.

$ f(x) = x+1, \, f(1) = 2 \quad \leftrightarrow \quad (\lambda x.x+1) \, 1 = 2$

커링(Currying)

람다 표현을 이해하셨다면, 하나의 의문이 자연스럽게 떠오르실 수 있습니다. 바로 매개 변수가 한 개보다 많은 함수는 어떻게 표현하는지입니다. 지금까지는 매개 변수가 하나인 경우만을 다뤘으며, 람다 표현을 쓸 때에도 $\lambda$ 다음에 하나의 변수만을 쓸 수 있었습니다.

$ f(x,y) = x+y $

만약 위와 같이 두 개의 변수를 받는 함수라면, 이를 어떻게 표현할 수 있을까요?

다음과 같은 람다 표현을 생각해 볼 수 있습니다.

$ \lambda x.(\lambda y. x+y) $

이것은 $x$를 받아서 $\lambda y.x+y$를 내놓는, 즉 또 다른 함수를 반환하는 람다 표현입니다. 이것이 어떻게 작동하는 걸까요? 이 함수에 $1$과 $2$를 적용하는 경우를 생각해 봅시다.

$ (\lambda x.(\lambda y. x+y)) \, 1 \, 2 $

$ = (\lambda y . 1+y) 2 $

$ = 1+2 = 3 $

놀랍게도, 원하는 결과가 나오는 것을 볼 수 있습니다.

매개 변수가 더 많은 $f(x,y,z) = x + y \times z $의 경우도 똑같이 적용할 수 있습니다.

$ \lambda x.(\lambda y. \lambda z. x + y \times z) \, 1 \, 2 \, 3$

$ = \lambda y.(\lambda z. 1 + y \times z) \, 2 \, 3 $

$ = \lambda z.(1 + 2 \times z) \, 3 $

$ = 1 + 2 \times 3 = 7 $

이처럼 람다 표현 안에 람다 표현을 씀으로써 매개 변수를 여러 개 받는 것과 비슷한 효과를 볼 수 있습니다. 이와 같은 기법을 커링이라고 부릅니다.

위 그림에서, 람다 표현의 실질적 의미는 왼쪽에 가깝습니다. 그러나 함수의 인자(argument)가 모두 주어진다고 가정하면, 커링의 개념을 생각할 때 오른쪽의 의미로 이해해도 무방하며 이 편이 더욱 편리합니다.

값으로서의 함수

람다 표현의 또 다른 의의는 함수를 값처럼 사용할 수 있다는 것입니다. 함수 그 자체를 식 하나로 표현할 수 있으므로, 아래 예시처럼 함수를 매개변수로 넘겨주거나 받는 일이 가능한 것이죠.

$ (\lambda f.f \, 1) \, (\lambda x.x) = (\lambda x.x) \, 1 = 1 $

비슷하게, 함수가 함수를 반환하거나 변수에 함수를 넣는 것 등의 일도 가능합니다. 이런 개념의 함수를 일급 함수(first-class function)라고 부르며, 현대의 많은 프로그래밍 언어들이 이런 맥락에서 람다 표현 혹은 익명 함수 기능을 지원합니다.

앞으로 이어질 내용에서도 값으로서의 함수 개념을 이용하므로, 함수도 값이라고 생각하시고 계속 읽어주시면 되겠습니다.

처치 인코딩(Church encoding)

지금까지 람다 표현을 이용해서 식을 작성하는 방법을 간단하게 알아보았습니다. 이러한 람다 표현은 수학적으로도 중요한 의미가 있는데, 이것을 통해 람다 대수라는 수학적 구조를 구성할 수 있기 때문입니다.

람다 대수(lambda calculus)에 대해 간단히 설명하자면, 오직 순수한 함수만을 이용해서 수식을 쓰는 체계라고 할 수 있습니다. 여기서 순수한 함수만을 이용한다는 것은, 오직 함수와 변수, 함수 적용만을 사용해서 표현한다는 것입니다. 허용되는 값은 오직 함수뿐이며, 우리에게 친숙한 자연수, 정수는 물론이고 덧셈, 곱셈 같은 연산 역시 사용할 수 없습니다.

함수만을 이용한 예시 $ \lambda x.x$, $(\lambda x.\lambda y.x \, y) \, (\lambda z.z)$
그렇지 않은 예시 $ \lambda x.1$, $\lambda x.\lambda y.x+y$

함수만을 가지고 식을 쓴다니 이게 무슨 쓸데없는 짓인가 싶지만, 놀랍게도 람다 대수를 이용하면 컴퓨터가 할 수 있는 모든 계산을 해낼 수 있음이 밝혀져 있습니다. 가능한 값이 함수밖에 없는데 이것이 어떻게 가능한 걸까요?

이 말을 바꿔서 생각하면, 우리가 생각하는 모든 값 혹은 연산을 함수로 풀어서 표현할 수 있다는 것입니다. 참/거짓도 함수, 숫자도 함수, 덧셈도 함수, … 이런 식으로 말이죠.

이처럼 함수가 아닌 개념을 함수로 인코딩(encoding)해서 표현하는 것을 처치 인코딩이라고 합니다. 처치 인코딩이라는 이름은 이러한 방식을 처음 제안한 알론조 처치(Alonzo Church)의 이름을 따서 지어졌습니다.

모든 것을 함수로 나타낼 수 있다니, 흥미롭지 않나요? 이제, 처치 인코딩이 어떤 방식으로 모든 것을 함수로 나타내는지 알아봅시다.

참/거짓 인코딩(Church Booleans)

처치 인코딩에서는 다음과 같이 참/거짓을 정의합니다.

$ T = \lambda x. \lambda y. x $

$ F = \lambda x. \lambda y. y $

$T$는 $x$, $y$를 받아서 $x$를 내놓는 함수이고, F는 $x$, $y$를 받아서 $y$를 내놓는 함수입니다. 즉, 이 둘은 $x$, $y$를 받아서 그 중 하나를 선택해주는 역할을 합니다.

어떤 역할을 하는지는 알겠는데, 도대체 어떤 구석에서 이 함수들이 참과 거짓을 나타낸다는 걸까요? 그것은 $True$, $False$값이 실제로 사용되는 곳인 if-then-else문의 맥락을 보면 알 수 있습니다.

참/거짓 연산 인코딩

참/거짓을 이용하는 가장 대표적인 연산은 if문일 것입니다.

if $cond$ then $A$ else $B$는 $cond$가 참이면 $A$를 내놓고, $cond$가 거짓이면 $B$를 내놓습니다. 이러한 if-then-else문은 위에서 정의한 참/거짓을 사용하면 간단하게 $cond \, A \, B$로 인코딩됩니다. 이는 아래와 같이 확인해 볼 수 있습니다.

if $T$ then $A$ else $B$

$ True \, A \, B $

$ = (\lambda x. \lambda y. x) \, A \, B $

$ = A$

if $F$ then $A$ else $B$

$ False \, A \,B $

$ = (\lambda x. \lambda y. y) \, A \, B $

$ = B$

이처럼, 참/거짓 인코딩과 if-then-else 인코딩이 함께 제대로 동작하는 것을 볼 수 있습니다.

$not$ 연산은 아래와 같이 정의됩니다.

$ not = \lambda x. (\lambda a. \lambda b. x \, b \, a) $

$not \, T$

$ \lambda x. (\lambda a. \lambda b. x \, b \, a) T $

$ = \lambda a. \lambda b. T \, b \, a $

$ = \lambda a. \lambda b. b $

$ = \lambda x. \lambda y. y = F $

$not \, F$

$ \lambda x. (\lambda a. \lambda b. x \, b \, a) F $

$ = \lambda a. \lambda b. F \, b \, a $

$ = \lambda a. \lambda b. a $

$ = \lambda x. \lambda y. x = T $

이처럼, $T$와 $F$를 넣어 보면 참/거짓이 바뀌어 재구성됨을 알 수 있습니다.

또한, $and$ 연산과 $or$ 연산도 다음과 같이 정의할 수 있습니다.

$ and = \lambda x. \lambda y. x \, y \, x $

$ or = \lambda x. \lambda y. x \, x \, y $

마찬가지로, $F \, F$, $T \, F$, $F \, T$, $T \, T$의 경우를 모두 인자로 넣어보면 결과가 옳게 나옴을 쉽게 확인할 수 있습니다.

$not$, $and$, $or$의 세 가지 연산이 모두 가능하므로, 처치 인코딩을 통해 참/거짓 논리식을 완전하게 표현할 수 있습니다.

다음 글에서 계속…

이번 글에서는 람다 표현이 무엇인지와 어떻게 사용되는지, 그리고 참/거짓을 함수로 인코딩하는 방법에 대해 알아보았습니다. 분량 상의 문제로, 자연수의 인코딩과 덧셈, 곱셈, 뺄셈 등의 연산을 인코딩하는 방법 및 다른 흥미로운 주제들은 다음 글에 이어서 다루도록 하겠습니다.

긴 글 읽어주셔서 감사합니다!

References

https://en.wikipedia.org/wiki/Anonymous_function

https://en.wikipedia.org/wiki/Lambda_calculus

https://en.wikipedia.org/wiki/Church_encoding