여기 있는 다른 글을 읽기 전에 준비 운동 - 품고 품기

람다 대수의 기본 틀이 품는 구조입니다. 이 걸 그대로 가져온 게 함수형 프로그래밍입니다. 데이터 구조를 만들 때 첫 번째로 해야 하는, 무의식 중에, 아무 생각없이 떠올려야 하는 가장 기본적인 테크닉입니다. list로 만들어 map, filter 등을 쓰고, fold류 함수들을 쓰는게 함수형이 아닙니다.(데이터를 두고 함수들이 와서 먹고 뱉고 먹고 뱉고 하는 뉘앙스가 잘 보여, 보통 함수형 프로그래밍 하면 리스트, 매핑, 필터등으로 설명을 시작합니다.) 가장 기본 설계, 출발점이 함수를 품는데서 시작해야 함수형 프로그램 모양이 나옵니다.

왜 함수를 품는게 중요할까요?

여러 포스트에서 얘기했지만, 또 얘기하자면 현란한 함수형 테크닉들이 필요하게 된 가장 근원적인 이유는, 바로 함수가 매개 변수를 제외하곤 외부와 소통할 방법이 없기 때문입니다. 보통은 딱 여기까지만 말하는데, 람다 대수가, 함수형이 이런 제약속에서도 범용 문제 해결책으로 쓰일 수 있게 하는 핵심 규칙이 하나 있습니다. 바로 람다 함수의 헤드에 있는 변수의 스코프입니다.

let f = \x -> ( 3 , (\y -> (2 , (\z -> x + y + z))))
> snd (snd (f 3) 4) 5
12

마지막 \z -> ... 람다 함수안에 있는 x, y는 바깥에 있는 헤드 \y, \x와 바인딩 되어 있습니다. 한 문장으로 정리하면, 다음과 같습니다.

“람다 함수가 자신을 감싸고 있는 람다 함수의 헤드에 접근이 가능하다”

매개 변수로만 소통한다는 제약을 뚫고 날개를 펴게해 주는 규칙, 약속입니다. 이 약속이 없이는 람다 대수로 할 수 있는 건 거의 없습니다. 하스켈도 물론 이 규칙을 이용해 기본 프로그램 설계가 시작되고 끝이 납니다. 첫만남에 매우 어려움을 주었던 모나드나 free 모나드, cps 패턴 같은 것들이, 이 관점에서 보면 많이 달라 보이지 않습니다. 모두 이어지는 작업들의 중간 중간 결과를 저장하가 위해 람다 헤드를 메모리로 쓰는 패턴들입니다.

이 개념을 쓰려면 꼭 람다와 고차함수가 있어야 합니다.

고차함수

func :: Int -> (Int -> Int) -> Int 
func x f = f (x + 1)

> func 1 (+10)
12

func의 결과값을 바로 (+10) 함수에게 넘겼습니다. 조금 다르게 표현해 보겠습니다.

> func 1 (\r -> r + 10) 
12

r은 func 내부의 작업을 저장해 둘 메모리입니다.

> func 1 (\r1 -> func (r1 + 10) (\r2 -> r1 + r2))
15

r1은 람다 함수 \r2 ... 에서도 접근 가능한 값입니다.

> func 1 (\r1 -> func (r1 + 10) (\r2 -> func (r1 + r2) (\r3 -> func (r1 + r2 + r3) id)))
32

r1에는 2, r2에는 13, r3에는 16, 마지막 결과는 32가 됩니다.
func 작업을 두 개로 나누어 볼 수 있습니다. 첫 번째는 +1 하는 작업이고, 두 번째는 결과를 다음 함수로 넘기는 작업입니다. 보통 작업을 읽을 때는 두 번째 연계 작업은 잠시 문장에서 빼고 +1 작업만 보면서 설계를 하게 됩니다. 여기서는 의도적으로 단계마다 추가 작업을 할 수 있는 걸 보이기 위해 r1 + 10, r1 + r2, r1 + r2 + r3을 넣었는데, 간단히 다음 형태의 패턴도 많이 보입니다.

> func 1 (\r1 -> func r1 (\r2 -> func r2 (\r3 -> func r3 id)))
5

또는 마지막에 메모리에서 모두 값을 가져오는 패턴도 있습니다.

> func 1 (\r1 -> func r1 (\r2 -> func r2 (\r3 -> func (r1+r2+r3) id)))
10

이런 고차 함수 테크닉은 굉장히 많은 곳에 쓰이며, 따로 테크닉이라 부르기 뭐할 정도로 기본으로 쓰입니다. 여기서 예시를 장황하게 보인 이유는 각 단계의 결과값이 어떻게 다음 단계, 혹은 다음 다음 단계에서 쓰이는지 보이기 위해서입니다.

※ id 함수를 설명하려 한 예시는 아닌데, 흐름을 끊기termination 위해 id 함수를 쓰는 것도 봐 둘만 합니다.

보통 함수형은 변수 대입이 없어, 함수의 결과값을 잡아 둘 수 없기 때문에 바로 함수 “컴포지션”으로 결과를 잡아두는 정도만 생각하는데, 컴포지션도 구현을 보면 함수를 품은 모양입니다.

(.)    :: (b -> c) -> (a -> b) -> a -> c
(.) f g = \x -> f (g x)

컴비네이터

함수를 받는 함수를 고차함수라 하는데, 이 중 특별히 함수와 함수를 붙이는 작업을 하는 고차함수를 컴비네이터라 부르기도 합니다. 우리 말로 번역하자면 조합자 혹은 조합기로 번역하는데, 조각들을 합쳐 큰 덩어리로 만들 때 쓰는 도구들을 컴비네이터라 부릅니다.

아직 래핑 타입들을 다루지 않기 위해 약간은 억지스러운 예시를 보겠습니다.

combi :: (Int -> Bool) -> (Int -> Bool) -> (Int -> Bool)
combi f g = \i -> case f i of
                   True -> g i
                   False -> id i
f :: Int -> Bool
f x | x > 0 = True
f x | otherwise = False

g :: Int -> Bool
g x | x `mod` 2 == 0 = True
g x | otherwise = False

> combi f g $ 10
True

f 작업을 하고, 그 결과에 따라 g작업을 할지 말지 결정 짓는다면 f와 g를 엮어 놓습니다. 어느 함수의 작업 결과를 다른 함수가 이어 받아 작업 할 때, 흔히 쓰는 패턴입니다.

공부하며 복잡하게 생긴 모양을 만나더라도 개념상으로 보면 결국 두 가지 중 하나일 수 밖에 없습니다. 이어지는 함수를 직접 받든지, 다른 컴비네이터 함수가 엮어 주든지 두 가지 중 하나입니다. 그렇지 않으면 함수값을 끌고 다닐 수 없기 때문에, 의미 있는 함수 프로그램을 만들 수 없습니다.

cps, Free 모나드 패턴들은 이어질 함수를 직접 받고, 함수 컴포지션, 모나드, 펑크터, 어플리커티브들은 컴비네이터로 구현합니다.

※ 마치 IO 작업은 함수가 단독으로 작동하는 것처럼 보일테지만, 실은 IO 바인드가 do에 가려져 있을 뿐, bind (>>=)라는 컴비네이터를 쓰는 형태입니다.

이런식으로 함수 결과를 끌고 다니는구나를 알고 모나드, Free 모나드나, cps 등을 보면, 이해하는데 도움이 될 겁니다.

2022-02-02 추가

람다 헤드는 값만 저장하는 곳이 아니다.

프로파일링을 살펴보다 중간 언어 Core 동작을 보는 중 다음과 같은 중간 코드 변환이 나옵니다.

https://serokell.io/blog/haskell-to-core#parametric-polymorphism

f :: Num a => a -> a
f x = x + x

이 하스켈 코드는 다음 중간 언어 Core로 변환됩니다.

f = \ @(a :: Type) ->
    \ ($dNum :: Num a) ->
    \ (x :: a) ->
      (+) @a $dNum x x

Num이라는 타입 클래스 제약을 람다 변수에 넣어 놓고 감싸고 있습니다. Core 언어에서는 외부로부터 들어오는 필요한 정보는 모두 람다 변수로 표현됩니다. 람다 변수를 메모리로 사용하는게 잘 드러나는 예라고 생각합니다.

유지해야 하는 정보가 있다면 람다로 감싸고, 또 필요한 정보가 있으면 또 람다로 감싸놓는 모양입니다. 매개 변수 하나만 있는 함수들의 커링으로 보는 걸 생각하면 필요한 정보가 있을 때마다 람다로 감싼다고 볼 수 있습니다.

f x y = ...
f x = \y -> ...
f = \x y -> ...

처음 입문하면서부터 들었던 내용이고, 알고 있었던 내용으로 별다를 것 없이 보이지만, Core가 람다를 쓰는 방식을 보니, 람다를 보는 눈이 달라지는데 도움이 될 수 있을 것 같아 써 놓습니다.