쉬어가는 글: 람다 식은 어떻게 유래되었나요?

자세한 내용은 쉽게 다가가는 최신 프로그래밍: 코틀린 - 3.2 함수형 프로그래밍을 참고하기 바랍니다. 프로그래밍 언어가 등장한 역사적 변천 과정을 얘기해보려고 합니다.

람다 식(lambda expression)이 등장한 배경을 알려면 람다 대수(lambda calculus)를 알아야 합니다. 람다 대수는  튜링 기계(turing machine, TM)를 만든 Alan B. Turing의 지도 교수인 Alonzo Church까지 연결됩니다. 람다 대수가 등장한 시기는 1930년대이며 컴퓨터가 없었습니다. Church는 영국의 수학자입니다. 이 당시 수학자들이 고민하던 문제는 뭐였을까요? "어떤 가설(문장)이 논리적으로 타당한지 판단할 수 있는 장치가 있을까" 였습니다. 이를 결정 문제(decision problem)라고 합니다. 

Church는 어떤 문장이 맞는지 틀린지 이전에 가장 먼저 "문장이 형식적으로 정의되어야 한다"고 주장했습니다. 여러분은 코틀린 문법(BNF)이 공식(well-formed formula)이라고 얘기하면 믿을까요? c, 파이썬, 코틀린 등 모든 프로그래밍 언어는 형식 언어이며, 2차 방정식의 근을 구하는 공식처럼 공식을 갖고 있습니다. 그렇게 해서 Church가 제안한 것이 바로 람다 대수입니다. 다만, 람다 대수는 계산 모델로 적용 범위를 제한합니다. 예를 들면, "9는 소수(prime number)인가"는 람다 대수로 표현이 가능합니다. 람다 대수가 점점 발전해서 오늘날의 프로그래밍 언어가 된 것입니다. 

자연수 2, 3, 4, ... 가 있을 때, 이 값을 계산한 값이 4, 9, 16, ... 이라고 합시다. 2가 4가 되는 과정은 계산을 통해 구했겠죠. 이 과정에서 "잘 계산할 수 있을까" 문제가 발생합니다. 이 문제는 "계산을 할 수 있을까"와 "계산 과정이 너무 복잡하지 않을까"로 나눌 수 있습니다. 2, 3, 4, ... 가 4, 9, 16, ...으로 바뀌는 계산은 규칙성이 엿보이죠. 이 규칙성을 함수(function)라고 부릅니다.

함수 f(x)= \(x^2\)는 입력 (2, 3, 4, ...)를 (4, 9, 16, ...)으로 "잘 계산"할 수 있습니다. 함수 f(x)처럼 계산 가능한 함수를 Church는 람다 대수로 정의했습니다.

위에서 설명한 "2, 3, 4, ... "가 "4, 9, 16, ..."으로 계산되는 과정을 람다 대수로 표현하면 아래와 같습니다. 입력 x는 2, 3, 4...에 해당하며, 출력 y는 "4, 9, 16, ..."에 해당합니다. 입력 x와 출력 y 사이에 놓인 점(.)은 x와 y를 구분하기 위한 기호입니다. 람다( \(\lambda \)란 기호를 사용한 게 특이하죠. \(\lambda \) 는 특별한 의미가 있는 게 아니라 기호일 뿐입니다. 이를  \(\lambda \)-abstraction(람다 추상화)라고 부릅니다.

\(\lambda \)x.y 

x 대신 x2를 사용해도 됩니다. x2로 바뀌면 y도 y2로 바꾸어야 겠죠. 이를 \(\alpha\) conversion(변환)이라고 부릅니다. 

\(\lambda \)x2.y2

입력 변수 x 대신에 값을 전달하려면 어떻게 하면 될까요? 이를 \(\beta\) reduction(축소)이라고 부릅니다.

\(\lambda \)(x.y)3 → \(\lambda \)x.\(x^2\)(3) → 9

이 과정을 잘 들여다보면 형식 언어로 나타내는 과정과 비슷하죠... Church가 제안한 람다 대수는 정확히는 타입을 선언하지 않은 untyped- \(\lambda \) calculus 입니다. 처음에 람다 대수는 계산 가능성을 입증하기 위한 목적으로 등장했지만, 계속 발전하면서 컴퓨터가 계산할 수 있는 언어로 바뀌어 갑니다. 이 과정에 컴퓨터과학자(언어학자)가 등장하면서 타입(type)이 람다 대수에 포함됩니다.

Church의 제자인 Turing은 튜링 기계(실제 기계가 아니라 가상의 기계, 모델링)를 만들어 형식적으로 정의한 문장이 참(accept)인지 거짓(reject)인지를 판정할 수 있음을 입증하였습니다. 이렇게 자꾸 추적하다 보면  Church-Turing thesis(명제)까지 나오죠.  이 명제의 결론이 재미있는데요... 튜링이 처음 제안한 튜링 기계보다 이를 변형시킨 튜링 기계를 제안해도, 튜링이 처음 제안한 튜링 기계의 성능과 같다는 겁니다. 튜링 기계를 오토마타(automata)라 부릅니다.

여기서 우리가 기억해야 할 또 한 분이 등장합니다. 바로 촘스키(Noam Chomsky)입니다. 촘스키는 람다 대수와 튜링 기계에서 증명하려고 했던 것이 언어 체계 (자연어와 형식 언어를 모두 포함)  에서도 유사할 것이라 유추했습니다. 촘스키는 모든 언어는 4종류 문법으로 분류할 수 있다고 제안했으며, 이 중 CFG(context free grammar)와 RG(regular grammar)가 우리가 오늘날 사용하고 있는 프로그래밍 언어를 정의합니다.

오토마타에는 튜링 기계외에 유한 오토마타(finite automata, FA)와 푸시다운 오토마타(pushdown automata, PDA)가 있습니다. 오토마타는 c, 파이썬, 코틀린 등과 같은 형식 언어를 인식할 때 사용합니다. 한글 음절을 인식하는 오토마타 들어본 적 있나요? 한글 오토마타는 FA를 말합니다. 구문 분석기(parser)에 대해 들어본 적 있나요? 구문 분석기는 PDA를 사용해 구현합니다. 한글 오토마타는 앞서 촘스키 분류 중 RG를 사용해 정의하며, 구문 분석기에서 분석하는 구문(문장의 구조)는 CFG를 사용해 정의합니다.

1930년대 수학자들이 주도한 계산 가능성 이론은 1940년대 실제 컴퓨터가 등장하면서, 컴퓨터가 계산할 수 있느냐의 문제인 계산 과학으로 전환됩니다. 컴퓨터가 모든 계산을 할 수 있을 것처럼 보이지만 컴퓨터의 계산 능력에는 한계가 있습니다. 이를 연구하는 학문 분야가 계산 과학입니다.

2000년대 이르러 더 재미있는 논쟁이 등장하고 있습니다. 영국의 물리학자 로저 펜로즈(Roser Penrose)는 "오늘날의 컴퓨터는 알고리즘적으로 결정론적인 시스템이기 때문에 지능을 가질 수 없다"고 주장합니다. 이 말에 공감하나요? 이 주장의 근거로 사용된 것이 바로 튜링 기계입니다. 컴퓨터가 어떤 문장이 맞는지 틀렸는지 증명할 수 있는 유일한 방법은 알고리즘을 단계적으로 적용하는 것뿐이기 때문이라는 것입니다. 여기서 알고리즘이란, 우리가 익히 알고 있듯, 공리(axiom - 증명할 필요가 없는 진리)에 따라 서술한 단계적인 절차를 수행하는 방법입니다.