Lambda Calculus에 대해 알아보자
그만 알아보자
남영환
게시 날짜: 2020.06.17.
함수형 프로그래밍에서 '람다 표현식(lambda expression)'은 단순히 '익명 함수(anonymous function)'로 생각할 수도 있겠지만, 람다 표현식은 사실 함수형 프로그래밍의 근간이며, 더 나아가 사고하는 방식을 제시한다.
나를 알기 위해서는 내가 살고 있는 사회에도 관심을 가져야 하듯이, 람다 표현식에 대해서 자세히 알고 싶다면 이것을 조작하는 '람다 대수(lambda calculus)'에 관심을 가져야 한다.
람다 대수는 프로그래머에게 세상을 추상화하는 새로운 방식을 제시할 것이다.
이것은 개발자로서 함수를 만들고 조합할 때, 좀 더 자유로운 사고를 가지게 될 것이라 기대해 본다.
Abstraction : 모든 것이 추상화를 하기 위해서
추상화는 프로그래밍에서 문제를 해결하는 근간이 된다.1
예를 들어보자.
\[\text{사과 2개가 있고 한 개에 10원이다.} \\ \text{ 전부 사려면 얼마가 필요할까?}\]우리는 직관적으로 \(10 \times 2\) 를 계산하여 20원이라고 답할 것이다.
그런데, 사과의가격->10, 2개->2의 관계는 어떻게 이어지는 것일까? 사과를 포도라고 바꿔도 문제는 바뀌지 않는다. 마찬가지로 개수가 2개에서 10개로 바뀐다 해도 문제는 바뀌지 않는다.
우리는 사과의 가격과 개수를 추상화하여 숫자로 만든 것이다.
\[가격 \times 개수\]우리는 이 식에 주어진 숫자들을 적용하여 답을 구한다. 구체적인 숫자들을 적용한다는 것은 임의로 이름을 부여한 가격, 개수를 그것들로 치환한다는 말이다.
을, 를, 으로, 로가 신경쓰인다. 이 식을 의사 코드로 다시 작성해보자.
그런데 \(cost\)가 사과 하나당 가격이 아니라, 사과를 \(items\)개수 만큼 구매할 때 필요한 총액이라고 하자.
다음은 사과 한 개의 가격을 구하는 식이다.
\[\apple = \cost / \items\]이 형태는 \(cost \times items\)에서 \(\times\)만 빼면 동일한 형태이다.
다음은 이 형태를 추상화한 결과이다. 나눗셈 연산자를 op로 분리하였다.
이제 총액을 구하는 식과 하나당 가격을 구하는 식을 하나의 대수식으로 표현할 수 있다.
- 나누기 적용
- 곱하기 적용
이러한 대수 형식으로 사과의 가격 정도는 구할 수 있겠지만, 모두가 이해할 수 있는 방식은 아니다.
람다대수(lambda calculus)가 이 문제를 해결할 것이다.
Lambda Caclulus로 추상화한 문제를 풀어보자.
사과 문제를 새로운 형식을 사용해 표현해보자.
1. lambda expression - 추상화를 하는 방식
lambda expression의 정의는 다음과 같다.2
\[\begin{align} <e&xppression> ::= <name> | <function> | <application> \\ \\ <n&ame> - \text{빈칸이 없는 문자열의 나열} \\ \\ <f&unction> ::= \lambda <name> . <body> \\ &<body> ::= <expression> \\ \\ <a&pplication> ::= (<function \ expression> \ <argument \ expression>) \\ &<function \ expression> ::= <expression> \\ &<argument \ expression> ::= <expression> \end{align}\]알기 쉽게 정의를 분해하면 세 가지 항목으로 이해할 수 있다.
- \(<name>\) : 추상화의 대상(예: items, cost, op)
- \(<function>\) : 추상화 대상을 식에 소개하는 부분
- \(<application>\) : 함수를 적용하기 위한 형태이며, 구체화한 부분
하나씩 예시를 만들어 보자.
\[\begin{align} &<name> \ - \ abcd \quad name1 \quad user_1 \\ &<function> \ - \ \lambda a . a \quad \lambda a.b \ \\ &<application> \ - \ (\lambda a . a \ \ \lambda b . b) \\ \end{align}\]이미 이해한 사람도 있겠지만, \(<function>\)을 만들어서 \(<application>\)의 형태로 조립하는 것이다.
이 과정에서 \(<name>\)으로 간단히 치환할 수 있기 때문에, 식이 점점 이해하기 쉬워진다.
이제 이전에 만든 대수식
\[\begin{align} & REPLACE \ \color{red}{op} \ IN \\ & \quad REPLACE \ cost \ IN \\ & \quad \quad REPLACE \ items \ IN \ cost \ \color{red}{op} \ items \end{align}\]을 lambda expression으로 표현해보자.
\[(\lambda \color{red}{op} . \lambda cost . \lambda items . (\color{red}{op} \ cost \ items)) \tag{L1}\label{L1}\]\(\color{red}{op}\)에 \(/\)를 넣으면 나눗셈이 될 것이고 \(+\)를 넣으면 덧셈이, \(\times\)를 넣으면 곱셈이 될 것이다.
2. beta reduction - 추상화된 문제를 풀어내는 방식
우리는 아래처럼 대수식을 만들고 그곳에 특정 숫자들을 적용하여 값을 찾아냈었다.
\[\begin{align} &(치환하라 \ 가격을 \ 10으로 \\ & \quad (치환하라 \ 개수를 \ 2으로 \\ & \quad \quad (가격 \ \times \ 개수) \ 에서)) \end{align}\]식 를 참고해 꾸며보자.
좀전에 만든 lambda expression \(\eqref{L1}\)도 위 형식과 비슷하게 식을 풀어낼 것이다.
식을 풀어내는 방법은 여러가지가 있다. 우리는 그 중에 beta reduction을 배워볼 것이다.
다음 예를 보면 쉽게 이해할 수 있을 것이다.
\[\begin{align} (\lambda y . x \ z) == & \\ x[y := z] \rightarrow & \\ x & \end{align}\]\(x[y := z]\) 는 body 인 x에 한해서 y를 z로 치환하라이다.
이제 우리가 만들었던 lambda expression\(\eqref{L1}\)을 보자.
\[\lambda \color{red}{op} . \lambda cost . \lambda items . (\color{red}{op} \ cost \ items)\]여기에 곱하기, 가격=10 그리고 개수=2 를 적용해보자.(잠시 후 이야기하겠지만 값 또한 lambda expression이다)
3. name clash - beta reduction의 문제
beta reduction을 적용 하다보면 동일한 이름이 충돌하면서 문제가 발생하는 경우가 생긴다. 3
첫번째 \(y\)와 두번째 \(y\)는 서로 다르다. 전자는 \(\lambda x . y \ x\)에 있는 것이며, 후자는 이 함수에 적용된 것이다. 이 문제를 해결하기 위해 alpha conversion이 필요하다.
4. alpha conversion - name clash를 방지하기
alpha renaming이라고도 불리며 이름처럼 bound variable의 이름을 변환시키는 것이다. 4 5
wiki에 있는 예제를 빌려오겠다. \((\lambda x . t)\)에서 x를 y로 변환해야 한다면, \((\lambda y . t [y/x])\)라고 쓴다.
\(t[y/x]\)는 "t with y instead of x"를 의미한다.
연습
identity
identity 함수는 매개변수로 온 값을 그대로 리턴하는 함수이다.
\[\lambda x . x\]여기서 \(x\)는 \(<name>\)에 해당하며 bound variable이라고 부르기도 한다.
이 함수를 개발자에게 익숙한 형태로 표현하면 다음과 같다.
function(x) {
return x;
}
constant function
상수함수는 정의역에 상관없이 항상 같은 값을 갖는 함수이다.
\[\lambda x . 1\]\(x\)가 어떤 값을 가지던, 함수의 값은 항상 1 이다.
function(x) {
return 1;
}
plus 1
덧셈또한 람다로 표현할 수 있다. 하지만 이번에는 \(+\)가 우리가 통상적으로 아는 수학의 덧셈연산이라고 하자.
\[\lambda x . x + 1\]function(x) {
return x + 1;
}
여기서 x=10을 넣어서 적용해보자.
(function(x) {
return x + 1;
})(10);
bound variable & free variable
\[\lambda y . x \ x \ y\]여기서 \(y\) 는 bound variable이며, \(x\)는 free variable이다.
\(<name>\)에 이름이 없으면 free variable이라고 생각하면 쉽다.
function lambda(x) {
return lambda(x);
}
lambda(lambda);
자가증식
\[\lambda ( x . x \ x ) \quad \lambda (x . x \ x)\]이 함수를 beta reduction으로 풀어서 표현해보자.
재밌는 결과를 확인 할 것이다.
실습
사과문제를 람다만으로 표현하기
이전에 만든 식을 다시 가져왔다.
\[(\lambda op . \lambda cost . \lambda items . (op \ cost \ items))\]\(op\)로 들어오는 부분이 2개의 람다가 겹쳐져 있어서 \(cost\)와 \(item\)가 적용될 수 있는 함수라고 말한 적이 있다.
맛보기로 곱하기가 어떻게 만들어지는지 확인하자. 그러기 위해서는 먼저 숫자부터 표현할 수 있어야 한다. Church numeral로 숫자를 표현하자.
위의 숫자 표기 방식 Church numeral은 한 개의 매개변수 f를 받아서 하나의 매개 변수x만 받는 함수를 반환한다.(higher-order function)
여기서 주의 깊게 보아야 할 것은 λx.x 이 0이며 <body> 안에 f의 개수가 숫자를 표현한다는 것이다.
즉, \(f\)의 개수가 숫자에 해당한다.
그러므로 \(n+1\)은 Church numeral을 따라 (f ..)를 한번 더 씌우면 된다.
\(f\)의 개수가 숫자이기 때문에 연속적으로 \(f\)가 적용되는 형태로 보일 것이다. 이것은 \(f\)의 멱급수(\(f^n\))로 표현된다.(\(f\)는 연산자로 간주)
숫자는 \(f\)의 멱급수로 표현되며 지수의 법칙을 따른다. \(f\)의 지수로 숫자를 표현할 수 있는 것이다. 하여 아래처럼 함수를 구성하여 곱셈을 표현할 수 있다.
- SUCC 가 적용될 때마다 1이 추가된다. (멱급수로 구성되고 해당 값의 지수가 우리가 원하는 값이 된다)
- PLUS m n 으로 SUCC를 이용하여 더하기를 적용한다.
- MULT m n 은 PLUS를 이용하여 곱하기를 적용한다.
정의들을 식으로 정의하고 더해서 \(cost \times items\)를 표현하자. 2
\[\begin{align} & SUCC := \lambda n . \lambda f . \lambda x.f (n \ f \ x) == \lambda n . \lambda f . \lambda x . f ((n \ f) \ x) \\ & PLUS := \lambda m . \lambda n . m \ SUCC \ n \\ & MULT := \lambda m . \lambda n . m \ (PLUS \ n) \ 0 \\ \\ & ((λop.λcost.λitems.(op \ cost \ items) \ MUL) \\ \end{align}\]이렇게 곱하기를 정의하고, 그것을 이용해서 \(cost \times items\)를 완성했다.
SUCC 부연설명
SUCC에 대해 더 설명하자면, λn.λf.λx.f (n f x) 는 λn.λf.λx.f ((n f) x) 로 표현될 수 있다. (n f) x는 x에 f가 n번 적용되는 것을 말한다.
아래는 그 예제이다. 2
\[\begin{align} & 2S3 \equiv (\lambda f . \lambda x . f (f \ x)) (\lambda x . \lambda y . \lambda z . y (x \ y \ z)) (\lambda u . \lambda v . u \ (u \ (u \ v))) == \\ & ((\lambda a.\lambda b.a (a b)) (\lambda x.\lambda y.\lambda z.y (x y z))) (\lambda u.\lambda v.u (u (u v))) \\ & \\ & (λa.λb.a (a b)) (λx.λy.λz.y (x y z))) \Rightarrow \\ & (λb.(λx.λy.λz.y (x y z)) ((λx.λy.λz.y (x y z)) b)) \\ & \\ & (λb.(λx.λy.λz.y (x y z)) ((λx.λy.λz.y (x y z)) b)) (λu.λv.u (u (u v))) \Rightarrow \\ & (λx.λy.λz.y (x y z)) ((λx.λy.λz.y (x y z)) (λu.λv.u (u (u v)) == \\ & S S 3 => \\ & 5 \end{align}\]이렇게 잘 보면 알겠지만 우리가 당연스럽게 생각했던 숫자(1,2,3…)들은 primitive value를 넘어서 lambda 로 표현되는 것을 알 수 있다.
참고문헌
- An Introduction to Functional Programming Through Lambda Calculus
- Beta Reduction, Alpha Conversion에 대한 설명입니다. 특히 Kevin Sookocheff의 블로그는 간결하고 알기 쉽게 설명하고 있습니다.
주석
-
Lambda Calculus와 직접적인 연관은 없지만 폴 그레이엄은 추상화의 정도가 강력한 도구를 가려내는 척도 중 하나라고 주장한다. 폴 그레이엄의 에세이 Beating the Average 중 "The Blub Paradox"와 폴 그레이엄 에세이에 대한 토론 Why does Paul Graham advise using higher level language over lower ones?을 권한다. ↩
-
람다식 정의와 Curch numerals의 정의는 다음 문서를 참고하였습니다. A Tutorial Introduction to the Lambda Calculus, Wiki : Lambda Calculus ↩ ↩2 ↩3