하스켈로 가기 전 필수 코스 - 람다 대수 기본 용어

카테고리를 오브젝트로 보고, 카테고리끼리 연산을 펑크터로 정한 다음 집합과 일반 수로 다뤘던 개념들을 이들로만 표현하는 걸 Category theory라 불렀습니다. (Category 대수라 불러도 되지 않았을까요. 수학 비전공자라 theory를 붙인 이유는 잘 모르겠습니다.) 이 보다 전에 오브젝트를 함수로 보고, 함수끼리의 연산을 정하고, 일반 수들로 표현한 수식들을 함수만으로 표현하는 방법이 만들어졌습니다. 바로 람다 대수입니다.

람다 대수에서 많은 개념들을 가져왔기 때문에, 하스켈 자료들을 보면 특별한 언급없이 람다 대수 용어들이 자주 쓰입니다. 깊이 있게 들어가진 않아도 기본 용어들은 알아두면 문서를 보는데 도움이 됩니다.

그리고, 고차 함수를 적극 활용하는 스타일을 익히기 위해 봐야 될 것 같긴 한데, 람다 대수를 봤다고 머리가 확 바뀌진 않는 것 같습니다. 그저 함수만으로 세상을 표현할 수도 있구나 정도의 감탄만 나오고 또 하나의 벽이 생기는 느낌도 있습니다.

어쨌든, 하스켈 문서들을 매끄럽게 읽으려면 반드시 먼저 봐야하는 이론입니다.

여기 내용은 람다 대수로 함수형 프로그래밍을 설명한 AN INTRODUCTION TO FUNCTIONAL PROGRAMMING THROUGH LAMBDA CALCULUS - Greg Michaelson 앞 부분의 몇 챕터를 요약한 것입니다.

목차

1. 기본 용어
   1. Expression
   2. Bound variables
   3. Alpha equivalence
   4. Beta reduction
   5. Redex
   6. Free variables
   7. Eta reduction
   8. Combinators
   9. Beta Normal Form
   10. 여러 개의 arguments
2. 람다 함수 스타일로만 프로그래밍 구조를 만드는 게 가능할까?
   1. Identity function
   2. Self application function
   3. Function application function
   4. 튜플
   5. 분기문
   6. 함수 결과를 임시 저장해(메모리) 놓을 바운드 변수 - 클로저

기본 용어

Expression

variables : 변수. 함수 안으로 들어오는 길을 의미합니다.
arguments : 입력 값
abstractions : 함수 head + body 로 구분하여 부릅니다.
expressions : 한 번 이상 abstraction 으로 싸여져 있는 식

𝜆x   .    x
^^^^   ^^^^
head   body

Bound variables

head에 있는 변수 x를 parameter라 하고, body에 있는 모든 x에 bind되어 있다 말합니다. 이 때 body에 나오는 x를 bound variable이라 합니다.
※ parameter를 통해 넣어 준 값을 arguments라 합니다.

Alpha equivalence

𝜆x.x
𝜆d.d
𝜆z.z

x 나 d, z가 특별한 의미를 가지는게 아닙니다. 위 세 개는 같은 함수입니다. 이 걸 alpha equivalence라 부릅니다.

Beta reduction

함수에 인자를 넣어주는 걸, 인자에 함수를 적용(apply a function to an argument)한다라 말하기도 합니다. 이렇게 넣어 준 값(reduce가 필요한 expression일 수도 있고, 더 이상 reduce할 필요 없는 expression, 즉 값일 수도 있습니다.)으로 abstaction의 body에 있는 bound 변수를 대체하고, 헤드를 지우는 작업을 beta reduction이라 합니다.

지금까지 함수를 가지고 항상 해오던 작업들에 명확한 이름을 지어주기 위한 용어들입니다.

(𝜆x.x) 2
2

함수 적용은 위와 같이 표기합니다. 위 예는 입력값을 그대로 뱉어내는 identity 함수입니다.

(𝜆x.x)(𝜆y.y)z

함수 적용은 왼쪽 우선(left associative)입니다. 위 식은 아래와 같이 괄호로 감쌌다고 보면 됩니다.

((𝜆x.x)(𝜆y.y))z
(𝜆y.y)z
z

용어가 약간 혼동이 됩니다.
𝜆x.A : 인자가 있다면 beta reduce를 하겠지만, 이대로는 인자가 없어 reduce할 수 없는 표현식입니다.
(𝜆x.A) M : A안에 있는 모든 x를 M으로 바꾸는 beta reduce를 할 수 있는 표현식입니다. 이런 상태를 Beta redex라 합니다.
아래 식은 application의 우선 순위 > abstraction의 우선 순위를 알아야 제대로 해석 할 수 있습니다. 우선 순위가 거꾸로였다면 x2에 M1이 들어가는 모양이었을 겁니다. 저는 처음 봤을 때, abstraction이 우선인 줄 알았습니다.

𝜆x2.(𝜆x1.A) M1 M2
𝜆x2.A[x1:=M1] M2 -- A[x1:=M1]은 A안에 있는 x1은 모두 M1으로 대체한다는 뜻입니다.

이제 용어들을 알았으니, 용어들을 이용해 작업을 설명하면 (𝜆x1.A) M1 redex를 beta reduce하면 A[x1:=M1]이 된다고 말합니다.

Redex

reduce할 수 있는 표현식.
Beta reduce 할 수 있는 표현식을 Beta redex.
Eta reduce 할 수 있는 표현식을 Eta redex.

Free variables

𝜆x.xy

y 처럼 head에 없는 변수를 free 변수라고합니다.

(𝜆x.xy)z

z를 x에 넣어 주면 zy로 beta reduction은 끝납니다. 한 가지 주의할 점은 alpha equivalence는 free 변수에는 적용되지 않습니다.

𝜆x.xz
𝜆x.xy

두 개는 같은 함수가 아닙니다. 아래와 같이 bound 변수를 바꾸는 건 의미상 차이가 없는 alpha equivalence입니다.

𝜆x.xz
𝜆y.yz

그런데 문서를 읽는 동안 혼란스러웠던 점이 있습니다.

λf.(f λx.x)

f는 head에 묶여 있으니, bound 변수입니다. 하지만, 아래와 같이 head를 떼어내고 body만 두고 볼 때는 free라 말합니다.

(f λx.x)

head까지 포함되어 있는 식에서는 bound라고 하지만, head없이 body만 떼어내서 말할 때는, 어디 head에 묶여 있을지, 어디에도 묶여있지 않을지 알 수 없습니다. 이 때 f는 free입니다.

만일 free변수와 bound변수가 이름이 겹칠 때는 혼동을 막기 위해 bound변수를 alpha equivalence를 적용(alpha conversion이라 부릅니다)해서 이름을 바꿔서 풉니다.

((λfunc.λarg.(func arg) arg) boing) =>
(λarg.(arg arg) boing) =>
(boing boing)  ---------------- (x) arg 해석을 잘 못 했습니다.

혼동을 막기 위해 bound되어 있는 arg를 arg1로 바꾸었습니다.

((λfunc.λarg1.(func arg1) arg) boing) =>
(λarg1.(arg arg1) boing) =>
(arg boing) ----------------- (o) 제대로 풀었습니다.

Eta reduction

λ<name>.(<expression> <name>)

이렇게 바운드 되어 있는 변수에 <expression>을 적용하는 모양은 그냥 아래와 같이 함수만 적어 놓은 것과 같습니다.

<expression>

하스켈로 말하면 (\x -> f x) 1 은 그냥 f 1 과 같다는 말입니다. 이렇게 간단한 표현으로 바꾸는 걸 eta reduction이라 합니다.

Combinators

Free 변수가 없는 람다식을 컴비네이터라 부릅니다. 인자를 combine 한다는 의미로 이름 붙여졌습니다. 단어 뜻은 결합을 의미하는데, 이게 인자와 결합할 수 없는 변수는 없다란 뜻과 바로 연결되진 않네요. 여하튼 하스켈 문서에서 수시로 컴비네이터란 말이 등장하는데, Free 변수가 없다란 말로 쓰이는 경우보다, 어떤 목적을 달성하기 위해 조합해서 쓰이게 되는 비슷한 성격들의 함수들을 붙이는 고차 함수를 말할 때가 더 많습니다. 예를 들어 parsec에서 숫자 파서, 문자열 파서… 들을 조합해서 원하는 파싱을 할 때, 이들 파서 하나 하나를 붙이는 함수들을 컴비네이터라 부릅니다.

지금부터는 추측입니다.
혹시 람다 컴비네이터와 함수들을 붙이는 함수가 결국 같은 걸 의미하는 건 아닌지 생각해 봤습니다. ( Free 변수란 건 언젠간 헤드에 물릴 변수 아닐까요? 결국에 어떤 헤드에도 물리지 않는 변수가 있다면, 의미가 뭘까요? ) bound 변수만 존재한다면, 감싸고 있는 클로저가 필요 없다는 말이고, 감싸고 있는 함수에 전혀 의존하지 않는 함수입니다. 여기까지 생각을 풀어도 두 개가 같은 개념을 의미하는 건 아닌 듯 합니다. Combine 단어 뜻을 각각 사용한 게 아닐까요?

Beta Normal Form

더 이상 beta reduce 할 게 없는 상태

여러 개의 arguments

𝜆xy.xy

parameter가 여러 개일때는 왼쪽부터 beta reduction 합니다. 아래와 같이 괄호가 있다고 생각하면 됩니다.

𝜆x.(𝜆y.xy)
(𝜆x.(𝜆y.xy)) 1 2
(𝜆y.1y) 2
12

람다 함수 스타일로만 프로그래밍 구조를 만드는 게 가능할까?

전자 회로에 쓰이는 부품을 만들 듯, 특정 동작을 하는 함수들을 만들어 회로를 설계하는 것과 비슷해 보입니다. 모든 부품(함수)들의 정의를 살펴 보면 좋겠지만, 여기서는 그럴 수도 있겠다 정도의 감만 생기는게 목표입니다.

Identity function

λx.x

Self application function

재귀를 이용한 무한 루프

λs.(s s)

(λs.(s s) λs.(s s))

이렇게 reduction이 끝나지 않는 걸 divergence라 부릅니다.

Function application function

λfunc.λarg.(func arg)

((λfunc.λarg.(func arg) λx.x) λs.(s s))
((λarg.((λx.x) arg)) λs.(s s))
((λarg.(arg)) λs.(s s))
(λs.(s s))

2튜플 - 순서쌍

2튜플을 만들어 내는 함수를 만들어 봅시다. 흔히 봤던 (a,b) 이런 외적인 모양이 아니라 2튜플의 속성을 띄는 것이면 모양은 상관 없습니다. 첫 번째 값을 따로 꺼내거나, 두 번째 값을 따로 꺼낼 수 있는 걸 튜플의 속성이라 볼 수 있습니다.

먼저 첫 번째 값, 두 번째 값을 꺼내는 함수를 만들면

--첫 번째 인자를 고르는 함수
λfirst.λsecond.first
--두 번째 인자를 고르는 함수
λfirst.λsecond.second

※재밌는 건, 첫 번째 인자를 고르는 함수를 Identity 함수에 적용하면 두 번째 인자를 고르는 함수가 됩니다.

(λfirst.λsecond.first) (λx.x)
λsecond.(λx.x)

alpha equivalence 특성을 이용해 second를 first로 x를 second로 바꿔서 표기하면

λfirst.λsecond.second

그 다음, 이 함수들에 적용할 튜플 함수를 만들면

λfirst.λsecond.λfunc.((func first) second)

이 함수에 두 개의 인자를 주면, 두 개의 인자를 “가지고 있는” 함수가 됩니다.

λfirst.λsecond.λfunc.((func first) second) (λx.1) (λx.2)
λfunc.((func (λx.1)) (λx.2)) 

이 함수를 첫 번째 인자를 고르는 함수에 적용하면

λfunc.((func (x.1)) (λx.2)) λfirst.λsecond.first
λfirst.λsecond.first (λx.1) (λx.2)
(λx.1)

두 번째 인자를 고르는 함수에 적용하면

λfunc.((func (x.1)) (λx.2)) λfirst.λsecond.second
λfirst.λsecond.first (λx.1) (λx.2)
(λx.2)

이렇게 튜플 속성을 함수로 표현했습니다.

※ 보통 값에다 함수를 적용하는 방식으로 생각을 해왔습니다.
람다 대수에서는 값 역할을 하는 것도 함수고, 이 값 함수를 다른 값 함수와 매핑하는 것도 함수입니다.
좀 낯설지만, 많은 개념들이 매핑 함수를 값 역할에 적용하는게 아니라, 값 역할을 하는 함수를 매핑 함수에 적용하는 방식으로 구현합니다. 이렇게 하려면, 값 함수를 잘 째려보면 나중에 들어올 함수 자리가 있습니다. 튜플의 func 변수처럼 말입니다. 제가 느끼는 숨은 뜻은, 튜플이라는 속성을 다른 함수와의 관계로 표현했다는 것이 핵심입니다. 추가 문법 없이 다른 함수와 관계를 맺는 방법은 application뿐이 없습니다.

어떻게 이런 방식을 떠올렸을까 신기합니다.

분기문

함수만으로 분기문을 어떻게 만들까요? 이 글에서는 여기까지만 살펴 보겠습니다. 모든 걸 함수로 표기하면 얻는 잇점이 뭘까 더 생각해보고, 생각의 진전이 있을 때 이어가도록 하겠습니다.

True가 들어 왔을 때와 False가 들어 왔을 때 가는 길이 다르게 해야 합니다. True, False 일 때 길을 고르는 함수를 정의하기 전에, 당연히 True와 False를 함수로 정의해야 합니다. \_ -> True, \_ -> False … 쯤으로 생각하는게 아닙니다. True와 False를 쓸 함수들을 생각해서 속성을 떠올려야 합니다. 어떤 함수”를” True에 적용할 때와 False에 적용할 때 다른 값이 나오게 하면 됩니다.

True를 select_first로, False를 select_second로 표현하기로 하고, 조건문은 다음과 같이 정의합니다.

λe1.λe2.λc.((c e1) e2)

여기에 True, False 에 따라 실행할 식 2개를 먼저 넣어줍니다.

((λe1.λe2.λc.((c e1) e2) <expression1>) <expression2>) =>
(λe2.λc.((c <expression1>) e2) <expression2>) =>
λc.((c <expression1>) <expression2>)

이제 이 함수를 True (select_first) 에 적용하면,

(λc.((c <expression1>) <expression2>) select_first) =>
((select_first <expression1>) <expression2>) => ... =>
<expression1>

False (select_second) 에 적용하면

(λc.((c <expression1>) <expression2>) select_second) =>
((select_second <expression1>) <expression2>) => ... =>
<expression2>

조건에 따라 다른 결과를 만드는 함수를 만들었습니다. 어떤 문법 요소도 추가하지 않고, 오직 함수 적용 개념만으로 분기를 만들었습니다.

값이란 개념이 따로 없기 때문에 True라는 속성, False라는 속성은 어딘가에 적용되어야만 드러납니다.

더 추상화해서 생각하면, 우리가 속성이라 부르는 것들은 다른 것들과의 관계에 의해서 정해집니다. 혼자서 어떤 속성을 가지고 있는데, 그게 다른 어떤 것과도 관계가 없다면 아무런 의미가 없습니다. 속성이란 결국 다른 것들과의 관계입니다. True라는 속성은 True, False 두 개를 가지고 정해놓은 연산에 의해 의미(속성)를 가지거나, isTrue 같은 함수들을 정의해서 결과값을 달리하거나… 어떤식으로든 다른 것들과 관계가 있어야 합니다. 관계는 함수로 표현되므로 모든 속성은 함수로 표현할 수 있을 것 같다는 생각에 이릅니다. 아마 람다 대수나 카테고리 이론의 출발점이 이런 생각이 아니었을까요?

함수 결과를 임시 저장해(메모리) 놓을 바운드 변수 - 클로저

2021.8.5 추가

다른 문서에서 콕 찝어서 이렇게 얘기한 걸 본적이 없으니 의심하면서 읽어주세요.
람다 대수 기본 표현식에는 람다 함수로 프로그래밍이 가능하게 하는 매우 중요한 특징이 있습니다. 여러 함수를 연결 연결해서 결과가 나오는 속성은 함수로 함수를 감싸면서 표현하는데, 이때 각 함수들의 결과를 저장하는 변수가 존재합니다. 마치 람다 함수는 값의 저장이라는 개념없이 함수 연결로만 끝나는 것처럼 보이지만, 여기에 결과값 저장이 숨어 있습니다. 바로 헤드에 있는 변수입니다.

𝜆x.(𝜆y.xy)

(𝜆y.xy) 함수 안에서 바깥쪽 함수에 있는 x를 참조할 수 있습니다. 이 함수 안쪽에서 x는 일종의 전역 변수입니다. 더 깊이 nested 되어 있는 함수들에서도 x에 접근 할 수 있습니다. 여기 함수 묶음에서는 모두 접근 가능하다는 중요한 속성입니다. 이 속성이 없었다면 람다 대수로 프로그래밍을 표현하는 건 불가능 했을 겁니다. 참고 - 모나드 액션들간의 소통

참고 - 수학 관련 자료가 아닌 프로그래밍 관련 자료들입니다. 아무래도 이런 자료의 표기나 용어들이 프로그래머들에겐 더 익숙합니다.
AN INTRODUCTION TO FUNCTIONAL PROGRAMMING THROUGH LAMBDA CALCULUS - Greg Michaelson
HASKELL PROGRAMMING FROM FIRST PRINCIPLES - Christopher Allen, Julie Moronuki

@todo

1. 람다 대수 용어를 아는 것을 넘어, 람다 대수가 컴퓨터 동작과 잘 맞아 떨어지는 이유를 생각해 보자.

2. 전자 회로와 굉장히 비슷한 느낌이 든다. 전자 회로는 전기가 흐르면서 갈 길을 정하거나 증폭하거나 버리면서 회로가 구성된다. 전기는 어딘가에 머무르지 않는다. 함수형에서는? 함수를 엮어 엮어 길을 만들어 놓고, 나중에 전기 스위치를 On 하듯이 데이터를 넣어주는 순간, 회로가 동작하듯 함수 뭉치가 작동해서 결과가 나온다. 개념만으론 비슷한 정도가 아닌 같은 개념으로 보인다.

3. 함수를 함수에 적용(고차 함수)함으로써 얻는 이득이 뭘까? 왜 그런 생각을 하게 됐을까? 람다 대수적인 생각은 어떻게 시작 됐을까?