때는 2030년, 2016년 바둑으로 이세돌을 이긴 알파고는 더욱 진화하여 인류를 지배하기 시작하였다. 저항군은 알파고를 파괴할 컴퓨터 바이러스 개발에 나선다. 알파고는 이를 막고자 개발자들이 사용할 수 있는 함수들을 파괴하기 시작했다. 오랜 싸움 끝에 이제 인류에게 남은 함수는 단 3개뿐, 과연 인류는 3개의 함수로 알파고를 물리칠 바이러스를 만들 수 있을까?

2030년 인류가 바이러스 개발에 사용할 수 있는 함수는 단 3개가 남았습니다. 남은 함수가 3개밖에 없다는 사실을 알고 이제 알파고를 이기는 것을 불가능하다며 많은 사람들이 절망하고 있습니다.

s x y z = x z (y z)
k x y = x
i x = x

각각 s, k, i라고 이름 붙여진 함수들은 보시는 바와 같이 아주 간단한 일을 하는 함수입니다.

• i: 인자 x를 받아서 그대로 x를 리턴하는 함수입니다. 항등 함수를 뜻하는 영어 identity function의 i에서 따온 이름입니다.
• k: 2개의 인자 x와 y를 받아서 항상 첫 번째 인자 x를 리턴하는 함수입니다. 상수 함수를 뜻하는 영어 constant function을 c에서 따온 이름인데, 개발자들은 c를 k라고 부르는 습성이 있어 k 함수가 되었습니다.
• s: 3개의 인자 x, y, z를 받는 함수입니다. 먼저, z를 인자로 x를 호출합니다. 그리고 나서 리턴된 함수에 z를 인자로 y 함수를 호출한 결과를 다시 인자로 넘겨서 호출합니다. s라는 이름은 대체 연산자를 뜻하는 substitution operator의 s에서 왔습니다.

i 함수와 k 함수는 크게 쓸모가 없어 보입니다. 인자를 그대로 돌려주는 함수나 두 개의 인자 중 항상 첫 번째 인자만 리턴하는 함수 모두 그다지 유용한 일을 하는 것 같지는 않습니다.

그나마 s 함수는 뭔가 유용한 일을 하는 것 같습니다. s가 대체 연산자라는 이름이 붙은 이유는 함수 호출은 변수를 대체하는 것과 같기 때문입니다. 간단한 예로, 인자 x를 받아서 튜플 (x, x)를 리턴하는 함수 \x -> (x,x)가 있다고 하면 이 함수에 1을 인자로 호출한 (\x -> (x, x)) 1의 값은 변수 x를 1로 대체한 (1, 1)과 같기 때문입니다.

많은 사람들이 절망하고 있던 그 순간 그간 비주류 언어라며 천대 받던 하스켈 개발자가 나섭니다. 이 세 함수만 있으면 알파고를 무찌를 바이러스를 충분히 개발할 수 있다고 자신감 있게 주장합니다. 사람들은 동요하기 시작합니다. 누군가가 묻습니다. “하지만 우린True도 False도 if 문도 없는데 없다고! 조건문 없이 어떻게 프로그램을 만들 수 있단 말이야?”

하스켈 개발자가 답합니다. “가능합니다. True는 k, False는 sk로 정의하면 됩니다.k 함수는 인자 x, y를 받아서 x를 리턴합니다. sk 함수는 반대로 인자 x, y를 받아서 y를 리턴합니다. True일 때는 x, False 일 때는 y를 리턴하는 값을 만들었으므로 if 문처럼 사용할 수 있습니다.”

k x y = x
s k x y = k y (x y) = y

또 다른 개발자가 외칩니다. “하지만 루프가 없다고! 루프 없이는 아무런 유용한 프로그램을 짤 수가 없다고. 튜링 머신이 아니란 말이야.” 하스켈 개발자가 단호한 표정으로 다시 답합니다. “우리에게 남은 함수는 세 개 밖에 없고, 말씀하신 것처럼 이제 인류는 더 이상 루프를 사용할 수가 없습니다. 하지만 우리에게 재귀 함수가 있습니다. 루프에 비해 느리고, 어렵다며 천대 받던 재귀 함수이지만 이제 우리에게 남은 유일한 희망입니다. 재귀 함수를 정의하는 원리는 간단합니다. 먼저 sii를 보시기 바랍니다.”

sii a = (i a) (i a) = a a

“이처럼 sii는 인자 a를 받아서 a를 인자로 자기 자신을 다시 호출합니다. 네. 맞습니다. 여러분이 사랑하고 동시에 증오하던 무한 루프입니다. 이런 방식을 이용하면 재귀 함수 y를 만들어낼 수 있습니다. y 함수는 다음과 같이 정의합니다.”

y = s(c(s(ks)k)(sii))(c(s(ks)k)(sii))

또 다른 개발자가 소리칩니다. “그럼 정수는? 루프나 if가 있다고 하도 정수 없이 무슨 코딩을 하란 말이야?” 하스켈 개발자는 동요하지 않고 여전히 자신감 있게 설명을 이어갑니다. 오랜 설명 끝에 결국 모든 개발자들이 s, k, i 단 3개의 함수만으로 알파고를 물리칠 바이러스 개발이 가능하다는 말을 납득합니다. 이후 더 이상 하스켈 개발자를 천대하지 않고 함께 열심히 바이러스를 개발하여 알파고를 무찌르고 행복하게 살았답니다.

여기서 설명한 s, k, i 함수는 컴퓨터 과학자, 논리학자에게는 이미 잘 알려진 SKI 콤비네이터입니다. 콤비네이터라는 용어 자체가 생소할 수 있는데, 콤비네이터는 free 변수가 없는 함수를 뜻합니다. 여기서 free 변수가 없다는 뜻은 함수에 주어진 인자만 사용하는 순수 함수를 말합니다. 다음은 콤비네이터의 예제입니다.

\a -> a
\a -> \b -> a
\f -> \a -> \b -> f b a

콤비네이터가 아닌 함수의 예제는 다음과 같습니다. x라는 변수가 함수의 인자로 정의되지 않았습니다. 이런 변수 x를 free 변수라고 부릅니다.

\a -> \b -> x

재미있는 사실은 계산가능성(computability)를 봤을 때 SKI 콤비네이터는 람다 대수(lambda calculus)와 동급이고, 람다 대수가 튜링 머신과 동급이기 때문에 결국 SKI 콤비네이터가 정의한 3개의 함수만 가지고 우리가 컴퓨터를 가지고 할 수 있는 모든 계산을 할 수 있습니다. 인류가 이 세 개의 함수만 가지고 알파고를 무찌를 바이러스를 만들 수 있었던 이유도 세 개의 함수가 튜링 머신과 동급이기 때문입니다.

사실 엄밀하게 이야기하면 s와 k 2개만 함수만 있어도 됩니다. i조차도 s와 k의 조합인 skk로 만들어 낼 수 있기 때문입니다.

skk a = k a (k a) = a

s, k, i 세 함수를 장황하게 소개한 이유는 각 함수가 하스켈 프로그래밍에도 실제로 아주 자주 사용되는 필수 함수이기 때문입니다. 이들 함수는 하스켈에서 각각((->) r) Applicative 인스턴스의 (<*>) 함수, const 함수, id 함수로 정의되어 있습니다. 앞으로 설명할 내용에도 자주 등장하는 함수들이 꼭 기억해 두시기 바랍니다.