람다 대수

2026.03.19 15:43

람다 대수(Lambda Calculus)는 1930년대 알론조 처치가 만든 형식 체계이다. 이름 없는 함수 하나만으로 숫자, 논리, 재귀를 전부 구성할 수 있다.

람다 식

람다 대수의 세계에 존재하는 것은 세 가지뿐이다.

변수: x
추상화 (함수 정의): λx.M — x를 받아 M을 반환하는 함수
적용 (함수 호출): M N — M에 N을 넘김

숫자도, 참/거짓도, if문도, 루프도 없다. 함수만 있다. 이것만으로 컴퓨터가 하는 모든 계산을 표현할 수 있다는 것이 이 글의 결론이다.

λx.M이라는 표기가 낯설 수 있는데, 프로그래밍의 익명 함수와 같다. λx.x는 JavaScript로 쓰면 (x) => x, Python으로 쓰면 lambda x: x이다. 인자를 그대로 돌려주는 항등 함수이다.

β-축소

함수에 인자를 넘기는 것을 β-축소(beta reduction)라 부른다. 하는 일은 단순하다. 함수 본문에서 매개변수를 인자로 치환하는 것이다.

(λx.x) 5

λx.x는 x를 받아 x를 반환하는 함수이다. 여기에 5를 넘기면, 본문 x에서 x를 5로 치환한다.

(λx.x) 5 → 5

조금 더 복잡한 예시를 보자.

(λx.λy.x) a b

이 식은 두 단계로 축소된다. 먼저 바깥쪽 함수 λx.λy.x에 a를 넘긴다. 본문 λy.x에서 x를 a로 치환한다.

(λx.λy.x) a → λy.a

결과로 λy.a가 나왔다. 이것은 “y를 받지만 무시하고 a를 반환하는 함수”이다. 여기에 b를 넘긴다.

(λy.a) b → a

y를 b로 치환해야 하지만, 본문에 y가 없으므로 b는 버려지고 a만 남는다. 결국 (λx.λy.x) a b → a이다.

여기서 주목할 점은, λx.λy.x가 두 개의 인자를 한꺼번에 받는 게 아니라 하나씩 받는다는 것이다. x를 받으면 “y를 받는 새 함수”를 반환하고, 그 함수가 y를 받는다. 이렇게 여러 인자를 하나씩 받는 함수의 체인으로 바꾸는 것을 커링(currying)이라 한다. 람다 대수에서 함수는 항상 인자를 하나만 받으므로, 두 개 이상의 인자가 필요하면 커링을 쓴다.

처치 수

아무것도 없는 상태에서 숫자를 어떻게 만들까?

처치의 아이디어는 “함수를 몇 번 적용하느냐”로 숫자를 표현하는 것이다.

0 = λf.λx.x              f를 0번 적용: 그냥 x
1 = λf.λx.f x            f를 1번 적용
2 = λf.λx.f (f x)        f를 2번 적용
3 = λf.λx.f (f (f x))    f를 3번 적용

숫자 n은 “함수 f와 초기값 x를 받아, f를 x에 n번 적용한 결과를 돌려주는 함수”이다.

이게 대체 무슨 뜻일까? 구체적인 예시로 생각해보자. f를 “1을 더하는 함수”, x를 0이라 하면:

0 f x = x       = 0     (아무것도 안 함)
1 f x = f x     = f(0)  = 1
2 f x = f(f x)  = f(1)  = 2
3 f x = f(f(f x)) = f(2) = 3

f를 “문자열 끝에 ’*‘를 붙이는 함수”, x를 빈 문자열이라 하면:

0 f x = ""
1 f x = "*"
2 f x = "**"
3 f x = "***"

숫자 자체에 f나 x가 내장되어 있는 게 아니다. “무엇을 몇 번 반복할지”를 추상적으로 표현하는 것이다. 어떤 f와 x를 넘기느냐에 따라 다른 결과가 나오지만, 반복 횟수는 항상 n이다. 이 반복 횟수가 곧 숫자이다.

SUCC (다음 수)

n에 1을 더하려면? n이 f를 n번 적용하는 함수이므로, 거기에 f를 한 번 더 적용하면 n+1이 된다.

SUCC = λn.λf.λx.f (n f x)

읽어보면: n, f, x를 받아서, 먼저 n f x로 f를 n번 적용하고, 그 결과에 f를 한 번 더 적용한다. 총 n+1번.

SUCC 2를 단계별로 축소해보자.

SUCC 2

SUCC와 2를 풀어 쓰면:

= (λn.λf.λx.f (n f x)) (λf.λx.f (f x))

바깥쪽 λn에 2를 대입한다. 본문에서 n을 (λf.λx.f (f x))로 치환한다.

= λf.λx.f ((λf.λx.f (f x)) f x)

이제 안쪽의 (λf.λx.f (f x)) f x를 축소한다. 이것은 “2에 f와 x를 넘기는 것”이고, 2의 정의에 따라 f (f x)가 된다.

= λf.λx.f (f (f x))

이것은 f를 3번 적용하는 함수, 즉 3이다. ✓

ADD (덧셈)

m + n을 만들어보자. f를 총 m+n번 적용하면 된다. 어떻게?

먼저 n에 f와 x를 넘겨서 f를 n번 적용한다. 그 결과를 m의 초기값으로 넘기면 m이 거기서부터 f를 m번 더 적용한다.

ADD = λm.λn.λf.λx.m f (n f x)

n f x는 f를 n번 적용한 결과이다. 이것을 m의 “x 자리”에 넣으면, m은 그 값에서부터 f를 m번 적용한다. 총 n + m번이다.

ADD 2 3을 확인해보자.

ADD 2 3
= (λm.λn.λf.λx.m f (n f x)) 2 3

m에 2를, n에 3을 대입하면:

= λf.λx.2 f (3 f x)

안쪽부터 축소한다. 3 f x는 3의 정의에 따라 f (f (f x))이다.

= λf.λx.2 f (f (f (f x)))

이제 2 f (f (f (f x)))을 축소한다. 2는 f를 2번 적용하는 함수이니, 두 번째 인자 f (f (f x))에 f를 두 번 적용한다.

= λf.λx.f (f (f (f (f x))))

f가 5번 적용되었다. 5이다. ✓

MUL (곱셈)

m × n은 어떻게 할까? 2 × 3은 “f를 3번 적용하는 것”을 2번 반복하는 것이다. 3번씩 2번이면 총 6번이다.

처치 수의 정의를 다시 생각해보자. n f는 무엇일까? n은 “f를 n번 적용하는 함수”이므로, n f는 “f를 n번 적용하는 함수”이다. 즉, n f는 하나의 함수로서, 인자를 받으면 거기에 f를 n번 적용한다.

(3 f) = λx.f (f (f x))     3 f는 "f를 3번 적용하는 함수"

이 함수를 m에게 “적용할 함수”로 넘기면, m은 이것을 m번 적용한다. m번 × n번 = m×n번이다.

MUL = λm.λn.λf.m (n f)

MUL 2 3을 확인해보자.

MUL 2 3
= (λm.λn.λf.m (n f)) 2 3
= λf.2 (3 f)

3 f는 “f를 3번 적용하는 함수”이다. 이것을 g라 부르자.

= λf.2 g           (g = λx.f (f (f x)))

2 g는 “g를 2번 적용하는 함수”이다. 즉 λx.g (g x)이다.

= λf.λx.g (g x)

g x는 f를 3번 적용한 것이고, g (g x)는 그 결과에 f를 3번 더 적용한 것이다. 총 6번이다.

= λf.λx.f (f (f (f (f (f x)))))
= 6 ✓

boolean

숫자를 만들었으니 참/거짓을 만들 차례이다. 이것도 함수로 만들어야 한다.

처치의 아이디어는 “선택”이다. 참과 거짓의 본질은 둘 중 하나를 고르는 것이라는 관찰에서 출발한다. if-then-else를 생각해보면, 조건이 참이면 then 쪽을, 거짓이면 else 쪽을 선택한다. 그래서 불리언 자체를 “두 값 중 하나를 선택하는 함수”로 정의한다.

TRUE  = λa.λb.a       두 인자 중 첫 번째를 선택
FALSE = λa.λb.b       두 인자 중 두 번째를 선택

이러면 조건문이 공짜로 따라온다. p a b라고 쓰면, p가 TRUE일 때 a가, FALSE일 때 b가 선택된다. 별도의 IF문 구현이 필요 없다. 불리언 자체가 이미 조건문이다.

TRUE  "yes" "no" → "yes"
FALSE "yes" "no" → "no"

그런데 잠깐, TRUE의 정의 λa.λb.a를 아까 본 적이 있다. β-축소 섹션에서 (λx.λy.x) a b → a로 확인한 바로 그 함수이다. 처치 수에서 0의 정의 λf.λx.x도 보자. FALSE와 같은 형태이다. 0과 FALSE가 같은 함수라는 것은 우연이 아니라, “아무것도 하지 않는다”와 “거짓”이 같은 개념이라는 의미이다.

논리 연산

AND = λp.λq.p q FALSE
OR  = λp.λq.p TRUE q
NOT = λp.p FALSE TRUE

AND를 단계별로 읽어보자. p q FALSE는 p에 q와 FALSE를 넘기는 것이다. p가 TRUE이면 첫 번째 인자인 q를 선택한다. p가 참이면 결과는 q에 달려 있으므로 이것이 맞다. p가 FALSE이면 두 번째 인자인 FALSE를 선택한다. p가 거짓이면 q와 상관없이 거짓이므로 이것도 맞다.

확인해보자.

AND TRUE FALSE
= (λp.λq.p q FALSE) TRUE FALSE
= TRUE FALSE FALSE
= (λa.λb.a) FALSE FALSE
= FALSE ✓

AND TRUE TRUE
= TRUE TRUE FALSE
= (λa.λb.a) TRUE FALSE
= TRUE ✓

OR도 같은 방식이다. p TRUE q에서 p가 TRUE이면 TRUE를 선택하고(하나라도 참이면 참), p가 FALSE이면 q를 선택한다(p가 거짓이면 결과는 q에 달림).

ISZERO

숫자가 0인지 판별하는 함수도 필요하다.

ISZERO = λn.n (λx.FALSE) TRUE

처치 수의 정의를 다시 떠올리자. n은 “함수를 n번 적용하는 함수”이다. ISZERO는 n에게 (λx.FALSE)라는 함수와 TRUE라는 초기값을 넘긴다.

n이 0이면? 함수를 0번 적용하니까 초기값 TRUE가 그대로 반환된다.

n이 1 이상이면? (λx.FALSE)가 적어도 한 번 적용된다. 이 함수는 뭘 받든 FALSE를 반환하므로, 초기값이 뭐였든 결과는 FALSE이다.

ISZERO 0
= 0 (λx.FALSE) TRUE
= (λf.λx.x) (λx.FALSE) TRUE       0의 정의 대입
= TRUE ✓                            f를 0번 적용, 초기값 그대로

ISZERO 1
= 1 (λx.FALSE) TRUE
= (λf.λx.f x) (λx.FALSE) TRUE     1의 정의 대입
= (λx.FALSE) TRUE                   f를 1번 적용
= FALSE ✓

이전 수

SUCC는 간단했다. f를 한 번 더 적용하면 끝이었다. 그런데 반대로, n에서 1을 빼는 PRED는 어떻게 만들까? 직관적으로 생각하면 f의 적용을 한 번 ‘되돌리면’ 될 것 같다. 하지만 f가 무엇인지 모르는 상태에서 f의 역함수를 구할 수는 없다.

해결책은 우회 전략이다. f를 n번 적용해서 n을 만드는 대신, 처음부터 세면서 n-1에서 멈추는 것이다. 이를 위해 먼저 두 값을 묶는 도구가 필요하다.

쌍(Pair)

PAIR   = λa.λb.λf.f a b
FIRST  = λp.p TRUE
SECOND = λp.p FALSE

PAIR는 두 값 a, b를 받아서, “선택 함수 f를 기다리는 함수”를 만든다. 이 함수에 TRUE를 넘기면 첫 번째 값이, FALSE를 넘기면 두 번째 값이 나온다. 그래서 FIRST는 TRUE를 넘기고, SECOND는 FALSE를 넘긴다.

FIRST (PAIR 3 5)를 단계별로 확인하자.

PAIR 3 5
= (λa.λb.λf.f a b) 3 5
= λf.f 3 5                 3과 5를 기억하고 있는 함수

이제 FIRST를 적용한다.

FIRST (λf.f 3 5)
= (λp.p TRUE) (λf.f 3 5)
= (λf.f 3 5) TRUE          쌍에 TRUE를 넘김
= TRUE 3 5                  TRUE는 첫 번째를 선택
= (λa.λb.a) 3 5
= 3 ✓

PRED 트릭

이제 PRED를 만들어보자. 아이디어는 (0, 0)에서 시작해서, 매 단계마다 “두 번째 값을 첫 번째로 밀고, 두 번째는 1 증가”시키는 것이다.

0단계: (0, 0)    시작
1단계: (0, 1)    두 번째(0)를 첫 번째로 밀고, 두 번째를 SUCC(0)=1로
2단계: (1, 2)    두 번째(1)를 첫 번째로 밀고, 두 번째를 SUCC(1)=2로
3단계: (2, 3)    두 번째(2)를 첫 번째로 밀고, 두 번째를 SUCC(2)=3로

패턴이 보인다. n단계 후의 쌍은 항상 (n-1, n)이다. 따라서 FIRST를 꺼내면 n-1을 얻는다.

한 단계를 수행하는 함수를 SHIFT라 하자.

SHIFT = λp.PAIR (SECOND p) (SUCC (SECOND p))

SHIFT는 쌍 p를 받아서, p의 두 번째 값을 새 쌍의 첫 번째로, 두 번째의 SUCC를 새 쌍의 두 번째로 놓는다.

PRED는 SHIFT를 n번 적용한 뒤 FIRST를 꺼내는 것이다. “함수를 n번 적용”하는 건 처치 수 자체의 능력이므로:

PRED = λn.FIRST (n SHIFT (PAIR 0 0))

PRED 3을 단계별로 확인하자.

PRED 3
= FIRST (3 SHIFT (PAIR 0 0))

3은 함수를 3번 적용하는 함수이므로, SHIFT를 (PAIR 0 0)에 3번 적용한다.

= FIRST (SHIFT (SHIFT (SHIFT (PAIR 0 0))))

안쪽부터 하나씩 축소한다.

SHIFT (PAIR 0 0)
= PAIR (SECOND (PAIR 0 0)) (SUCC (SECOND (PAIR 0 0)))
= PAIR 0 (SUCC 0)
= PAIR 0 1

SHIFT (PAIR 0 1)
= PAIR (SECOND (PAIR 0 1)) (SUCC (SECOND (PAIR 0 1)))
= PAIR 1 (SUCC 1)
= PAIR 1 2

SHIFT (PAIR 1 2)
= PAIR 2 (SUCC 2)
= PAIR 2 3

마지막으로 FIRST를 꺼낸다.

FIRST (PAIR 2 3) = 2 ✓

PRED 0은 어떨까? SHIFT를 0번 적용하므로 (PAIR 0 0)이 그대로이고, FIRST를 꺼내면 0이다. 자연수에는 음수가 없으므로 자연스러운 동작이다.

뺄셈도 같은 원리이다. PRED를 n번 적용하면 n을 빼는 것이다.

SUB = λm.λn.n PRED m

재귀 (Y 콤비네이터)

숫자, 산술, 불리언, 조건분기까지 갖추었다. 하지만 결정적으로 빠진 것이 하나 있다. 재귀이다.

팩토리얼을 생각해보자.

fact = λn.ISZERO n 1 (MUL n (fact (PRED n)))

fact의 정의 안에서 fact 자신을 쓰고 있다. 문제는, 람다 대수에는 이름이 없다는 것이다. fact = ...이라고 쓰는 건 편의상의 약속일 뿐, 실제 람다 대수에서는 모든 것이 이름 없는 함수이다. 함수 안에서 “나 자신”을 가리킬 방법이 없다.

이름 없이 어떻게 자기 자신을 호출할 수 있을까?

자기 복제

한 가지 관찰부터 하자. 다음 식을 보자.

(λx.x x) (λx.x x)

이 식을 축소하면 어떻게 될까? λx.x x는 인자 x를 받아 x x(x에 x를 적용)를 반환하는 함수이다. 여기에 (λx.x x) 자신을 넘기면:

(λx.x x) (λx.x x)
→ (λx.x x) (λx.x x)        x 자리에 (λx.x x)를 대입하면 원래 식이 됨
→ (λx.x x) (λx.x x)
→ ...

축소하면 자기 자신이 나온다. 무한루프이다. 이 식을 ω(omega)라 부른다.

그 자체로는 쓸모없지만, 핵심 아이디어가 담겨 있다. 함수가 자기 자신의 복사본을 인자로 받으면, 본문 안에서 그 복사본을 다시 호출할 수 있다는 것이다. 이 구조에 유용한 계산을 끼워넣으면 어떨까?

고정점이라는 개념

재귀 문제를 다른 각도에서 보자. 팩토리얼 함수를 이렇게 바꿔 쓸 수 있다. 재귀 호출 부분을 매개변수 self로 빼낸다.

fact_step = λself.λn.ISZERO n 1 (MUL n (self (PRED n)))

fact_step은 “재귀 호출 대신 self를 호출하는 팩토리얼”이다. self 자리에 진짜 팩토리얼 함수가 들어가면 제대로 동작할 것이다.

우리가 원하는 것은 fact_step에 무언가를 넣어서 진짜 팩토리얼 fact를 얻는 것이다. 즉:

fact = fact_step fact

이 식이 성립하려면 fact는 fact_step의 고정점(fixed point)이어야 한다. 수학에서 고정점이란 f(x) = x를 만족하는 x이다. 여기서는 fact_step(fact) = fact이다.

이런 고정점을 임의의 함수에 대해 찾아주는 것이 Y 콤비네이터이다.

Y 콤비네이터

하스켈 커리가 발견한 Y 콤비네이터이다.

Y = λf.(λx.f (x x)) (λx.f (x x))

복잡해 보이지만, 아까 본 ω (λx.x x) (λx.x x)와 비교해보면 구조가 비슷하다. x x 대신 f (x x)가 들어갔을 뿐이다. 자기 복제를 하되, 매번 f로 감싸는 것이다.

어떤 함수 g에 Y를 적용하면 어떻게 되는지 단계별로 보자.

Y g
= (λf.(λx.f (x x)) (λx.f (x x))) g

바깥쪽 λf에 g를 대입한다.

= (λx.g (x x)) (λx.g (x x))

이제 왼쪽 λx.g (x x)에 오른쪽 (λx.g (x x))을 넘긴다. x 자리에 (λx.g (x x))를 대입한다.

= g ((λx.g (x x)) (λx.g (x x)))

그런데 (λx.g (x x)) (λx.g (x x))은 한 단계 전의 결과와 같다. 즉 Y g이다. 따라서:

= g (Y g)

Y g = g (Y g)이다. g에 Y g를 넣으면 다시 Y g가 나온다. Y는 어떤 함수든 그 함수의 고정점을 만들어준다.

팩토리얼 만들기

다시 팩토리얼로 돌아오자.

fact_step = λself.λn.ISZERO n 1 (MUL n (self (PRED n)))

여기에 Y를 적용한다.

fact = Y fact_step

Y fact_step = fact_step (Y fact_step)이다. 이것을 fact_step fact로 쓸 수 있다. 왜냐하면 Y fact_step이 fact이니까.

fact_step의 본문을 보면, self 자리에 fact가 들어간다.

fact = fact_step fact
     = (λself.λn.ISZERO n 1 (MUL n (self (PRED n)))) fact
     = λn.ISZERO n 1 (MUL n (fact (PRED n)))

self가 fact로 치환되었다. 이름 없이 재귀가 만들어졌다.

fact 3을 계산해보자.

fact 3
= fact_step fact 3
= ISZERO 3 1 (MUL 3 (fact (PRED 3)))

ISZERO 3은 FALSE이므로 두 번째 값이 선택된다.

= MUL 3 (fact (PRED 3))
= MUL 3 (fact 2)

fact 2를 같은 방식으로 전개한다.

= MUL 3 (MUL 2 (fact 1))
= MUL 3 (MUL 2 (MUL 1 (fact 0)))

fact 0에서 ISZERO 0은 TRUE이므로 첫 번째 값 1이 선택된다.

= MUL 3 (MUL 2 (MUL 1 1))
= MUL 3 (MUL 2 1)
= MUL 3 2
= 6 ✓

튜링 동치

이 시점에서 정리해보면, 우리에게는 자연수와 산술 연산(SUCC, ADD, MUL, PRED, SUB), 불리언과 조건분기(TRUE, FALSE, ISZERO), 그리고 재귀(Y 콤비네이터)가 있다. 모두 λ와 함수 적용만으로 만들었다.

이것으로 충분할까?

1936년, 처치와 튜링은 각각 독립적으로 “계산 가능한 함수”를 형식화했다 (처치는 람다 대수로, 튜링은 자신의 이름을 딴 기계로). 튜링 머신은 테이프 위에서 상태 전이 규칙에 따라 기호를 읽고 쓰는 기계이다. 두 사람의 접근은 완전히 달라 보이지만, 놀랍게도 정확히 같은 범위의 함수를 계산할 수 있다는 것이 증명되었다.

람다 대수로 튜링 머신 시뮬레이션

튜링 머신의 구성 요소를 하나씩 람다 식으로 인코딩할 수 있다. 머신의 상태는 처치 수로 표현하고, 테이프는 쌍의 연쇄(리스트)로 표현한다. 헤드 위치도 처치 수이다. 상태 전이 규칙은 현재 상태와 읽은 기호를 받아 새 상태, 쓸 기호, 이동 방향을 반환하는 함수이다. 이 전이 함수를 Y 콤비네이터로 반복 적용하면, 튜링 머신이 정지할 때까지의 전체 계산을 수행할 수 있다.

튜링 머신으로 람다 대수 시뮬레이션

반대 방향도 가능하다. 람다 식을 문자열로 테이프에 쓰고, β-축소 규칙을 기계적으로 수행하는 튜링 머신을 구성할 수 있다. 치환 규칙이 명확히 정해져 있으므로, 테이프를 스캔하면서 (λx.M) N 패턴을 찾아 M 안의 x를 N으로 치환하는 것을 반복하면 된다.

양쪽 방향이 모두 가능하므로, 두 체계의 계산 능력은 정확히 같다.

이 동치는 Church-Turing thesis의 근거가 된다. “효과적으로 계산 가능한 함수는 정확히 튜링 머신으로 계산할 수 있는 함수와 같다”는 명제이다. 이것은 수학적 정리가 아니라 정의에 가까운 명제이다. “계산 가능하다”라는 직관적 개념을 형식화한 것이기 때문이다. 하지만 람다 대수, 튜링 머신, μ-재귀 함수, 마르코프 알고리즘 등 독립적으로 제안된 여러 형식 체계가 모두 같은 범위의 함수를 계산한다는 사실이, 이 정의가 올바르다는 강력한 정황 증거이다.

프로그래밍 언어

람다 대수의 아이디어는 현대 프로그래밍에 직접 이어진다. Lisp(1958)은 람다 대수를 직접 구현한 최초의 언어이다. 이후 ML, Haskell, OCaml 같은 함수형 언어들이 람다 대수의 타입 이론 위에 세워졌다.

실용적 언어들은 처치 인코딩 대신 네이티브 숫자와 조건문을 사용하지만, “함수가 값이고, 함수를 인자로 넘기고, 함수를 반환할 수 있다”는 핵심은 동일하다.

// JavaScript — 커링
const add = (m) => (n) => m + n;
add(2)(3); // 5

# Python — 익명 함수
square = lambda x: x * x
square(4)  # 16

// Rust — 클로저
let add = |x: i32| move |y: i32| x + y;
add(2)(3); // 5

참고

한국사현대사 수학곱셈공식 수학근과 계수의 관계 수학미분 자료구조KD-tree 자료구조LSM Tree