lambda calculus - boolean 연산

출처

• https://www.youtube.com/watch?v=3VQ382QG-y4

lambda calculus, boolean으로 표현!

이번 글에서는 lambda calculus가 어떻게 boolean 연산으로 전환될 수 있는지에 대해 알아보는 시간을 갖도록 하겠습니다.

출처에 적힌 내용을 바탕으로 설명드리도록 하겠습니다. 위키에 있는 내용만으로는 이해가 잘 되지 않아서 해당 유튜브를 참고했네요.

글의 구성

이 글은 총 2편에 걸쳐 작성할 것입니다. 첫 편에서는 lambda calculus에서 쓰이는 용어 대신 새의 이름으로 치환하여 함수를 소개할 것입니다. 그러면 선입견과 위화감을 줄이는데 큰 도움이 되거든요~

그리고 다음 글에서는 어떻게 새의 이름을 실제 lambda calculus의 boolean 연산에 대응하고 어떻게 적용되는지를 보여드리겠습니다.

설명 방식은 lambda calculus와 javascript를 연결지어 말씀드리겠습니다. lambda calculus가 이론으로만 치우쳐지지 않도록 하기 위해서입니다.

이제 시작해보겠습니다.

Lmabda Calculus to Javascript

lambda calculus의 Expression에서 variable, abstraction, application이 있었죠? 각각들이 javascript에서 어떻게 표현되는지 아래 표에서 살펴보겠습니다.

lambda calculus	javascript	비고
x	x	variable, 변수 x는 x를 의미
a	a	variable, 변수 a는 a를 의미
f a	f(a)	application, let f = x => x+5; f(5)
f a b	f(a)(b)	application, let f = x => y => x**2 + y**2; f(2)(5)
(f a) b	(f(a))(b)	application, 소괄호는 애매할 수 있는 순서를 결정해준다.
f(a b)	f(a(b))	application, 순서 결정.
λa.b	a => b	abstraction
λa.b x	a => b(x)	abstraction
λa.(b x)	a => (b(x))	abstraction
(λa.b) x	(a => b)(x)	abstraction
λa.λb.a	a => b => a	abstraction
λab.a = λa.λb.a	a => b=> a	curring의 축약 표현입니다. (a,b) => a 가 아니죠.

위에 따라 javascript에서 add 함수를 만들고, application을 적용하면 아래처럼 사용할 수 있습니다.

β-reduction

β-reduction에 대해 헷갈린게 있었는데, 여기서 풀어서 알려줘서 다시 한 번 언급하겠습니다.

1. 첫번째 reduction에서는 a를 인수로 받으면 그대로 a가 반환되는 abstraction이기 때문에 그대로 λb.λc.b가 반환되었습니다.
2. λb.λc.b는 b를 인수로 받아 λc.b를 반환하고, c인수를 받아 b를 반환하는 abstraction이기 때문에 x하나만 application을 한다면 λc.x가 반환됩니다.
3. 인수 c를 받아 x를 반환하기 때문에 어떤 값을 넣어도 x를 반환합니다. body에 c에 관한 variable이 없기 때문이죠. 따라서 λe.f를 λc.x에 applicatoin한다면 x가 반환됩니다.

위 내용이 기본이므로 이해가 잘 안된다면 youtube 도입부를 보시면 편할 것 같습니다. 잘 정리되어 있거든요!

함수의 종류

새의 이름을 딴 함수들을 소개시켜드리겠습니다.

1. Idiot

a를 집어 넣어서 a가 나오는 함수를 의미합니다.

lambda expression

I := λa.a

JS

const I = a => a

exam

I(I)

위 결과는 무엇이 나올까요?

I가 그대로 나옵니다. I에 I를 인수로 넣었으므로 I가 그대로 나오겠죠.

한편으로, Haskell에선 기본 함수로써 id라는 이름으로 제공해주고 있습니다.

2. Mockingbird

이 함수는 f를 입력하면, f에 f를 application하는 함수를 반환합니다.

lambda calculus

M := λf.ff

JS

M => f => f(f)

exam

M(I)

의 결과는 무엇일까요?

M(I) => I(I) => I

위에서 보았듯, I(I)는 I였으므로 또 I가 나오네용~

M(M)

의 결과는 무엇일까요?

M(M) => M(M) => M(M) .....

무한하게 자기 자신을 application 하네요! 독특한 놈입니다. 따라서 javascript에서는 stack overflow가 발생합니다.

lambda calculus에서는 따로 omegra라는 이름을 붙이기도 합니다.

3. Kestrel

a,b 인수를 순차적으로 application하면 a를 반환하는 함수입니다. 즉, 파라미터의 앞에 것만 반환시키는 함수이지요.

lambda calculus

K := λab.a
   = λa.λb.a

JS

K = a => b => a

exam

K(I)(M)

앞의 것을 반환하기 때문에 I 함수가 나옵니다.

K(K)(M)

역시 앞의 것을 반환시키기 때문에 K를 반환하죠.

K(3)(I)
K(3)(M)
K(3)(K)

모두 3을 반환합니다.

다시 말해서, 뒤의 값에 상관없이 앞의 argument에 의해 값이 정해집니다. 이러한 성질 때문에 Haskell에선 const function이라고 부릅니다.

4. Kite

kestrel과 달리, a,b 인수를 순차적으로 application하면 b를 반환하는 함수입니다.

lambda calculus

KI := λab.b

JS

KI = a => b => b

kite는 kestrel의 성질에 의해 나왔습니다. Kestrel에서 다음을 살펴보죠.

lambda calculus

K I x y = I y = y

JS

K(I)(x)(y) === I(y), I(y) === y

 

오우; javascript에서도 뒤에 집어 넣은 값이 딱 튀어나왔죠? 값 뿐만이 아니라 함수로 적용해도 뒷 것이 나오겠죠?!

다시 한 번 lambda calculus는 variable뿐만 아니라 abstraction으로도 application이 된다는 것을 보여드리고 싶었네요 ㅎㅎ

앞선 내용들을 표로 정리하자면 다음과 같습니다.

여기서 combinators는 body에 free variable이 없는 function을 의미합니다.

정리

function을 새 이름으로 표현하고 이상한 연산을 수행했잖아요? 도대체 이게 뭔가 싶죠? 그런데 참고 다음 글을 보면 깜짝 놀랍니다!

위에 표현한 4개로 boolean을 표현할 수 있으니까요!

True, False, And, or, Xor, not 모두 표현가능하답니다. 그리고 마지막에선 어떻게 functional programming에서 lazy loading이란 개념이 나왔는지 단서도 얻을 수 있습니다.

다음 글까지 기다려주세요~ 다음 글까지 참기 어려워 너무 궁금하시다면 위 링크를 들어가시면 됩니다!