Fix 함수

수학에서 fixed point는 f a = a를 만족하는 a를 말합니다. 그래프로 얘기하면 y = x 그래프와 만나는 점들을 fixed point 또는 fix point라고 합니다. 이게 실용 세계에서는 어떤 의미로 쓰일까요? 수학적 용도는 다음과 같이 근사치를 구할 때 쓸 수 있습니다.

https://medium.com/@cdsmithus/fixpoints-in-haskell-294096a9fc10

fixpoint :: Eq a => (a -> a) -> a -> a
fixpoint f x
  | x == fx   = fx
  | otherwise = fixpoint f fx -- x 자리에 fx를 넘깁니다.
  where fx = f x

mySqrt :: Double -> Double
mySqrt n = fixpoint (\x -> (x + n/x) / 2) 1

main :: IO ()
main = print (mySqrt 10)

여기서는 루트값이 구해지는 알고리즘¹보다 fixpoint가 함수f를 반복해서 부르는 것에 주의를 기울여 주세요.

하스켈에서는 “fixed point 값을 찾는 함수”로 fix 함수가 있습니다. (단, 정의를 보면 위 fixpoint 함수와 다르게 엔딩 조건이 없습니다.) 팩토리얼을 구하는 데 fix를 이용해 보겠습니다. ~~~ haskell – fix 함수 정의 fix f = f (fix f) – 또는 fix f = x where x = f x – 각주 [2]를 참고하세요. – 또는 fix f = let {x = f x} in x – 셋 모두 결국 아래 모양을 의미합니다. – fix f = f (f (f … ))

fact = fix (n -> if n == 0 then 1 else n * func (n-1)) – fix f = f (f (f …)) – 여기서 f는 func,n을 받아 n이 0이면 1, 아니면 func를 실행하는 이항 함수입니다. – 보기에 복잡하니 f (f (f …)) 은 (f…) 으로 표기하겠습니다. – 여기에 5를 인자로 주면 f (f…) 5 = (n -> if n == 0 then 1 else n * func (n-1)) (f…) 5 – func에 (f…)를 넣고, n에 5를 넣으면 = 5 * (f…) 4 – f 함수는 (f …)와 4를 인자로 받습니다. = 5 * 4 * (f…) 3 = 5 * 4 * 3 * (f…) 2 = 5 * 4 * 3 * 2 * (f…) 1 = 5 * 4 * 3 * 2 * 1 * (f…) 0 = 5 * 4 * 3 * 2 * 1 * 1 ~~~

※ where 절에서 선언한 함수²

어째서 이런 결과가 나왔을까요? fix 함수를 말로 풀어 보면, 받은 함수를 품고 품는 모양으로(인자로 자기 자신을 넘기는 모양) 무한 반복해주는 함수입니다. 무한 반복해주는 함수지만 fix에 넘기는 함수에 엔딩 조건을 두었습니다. (n == 0 then 1) n이 0일 때는 받은 함수를 호출하지 않고 끝냅니다. fixed point가 없는 함수를 적당한 값에서 반복을 멈추게 해준 건 fix 함수의 특징이 아닙니다. fix 함수의 특징은 fixed point가 나올때까지 무한 반복입니다.

람다 함수의 고정점을 찾을 때 fix를 쓴다라고 얘기해도 되지만, 프로그래머에게 더 익숙한 표현은 다음과 같습니다.

함수를 인자로 받는 람다 함수를 fix에 넘겨주면 반복해서 실행됩니다. 이 특성을 이용해서 람다 함수 무한 반복에 쓰입니다. 람다 함수는 따로 바인딩되어 있는 이름이 없어 재귀적으로 다시 부를 방법이 없습니다. 그럴 때 fix를 쓸 수 있습니다. fix (\a -> ...a) 란 람다 함수를 반복할 때 쓰는 관용구idiom입니다. ~~~ haskell forkIO $ fix $ -> do (_,msg) <- readChan chan loop ~~~ \loop -> ... 를 반복하는 코드입니다. 센스있게 람다 함수의 매개 변수 이름을 loop로 지었습니다.

상상

2023.4.9 추가

차분히 fix 심화를 해보려 하니, 역시 쉬운게 없습니다. 여러 배경 지식을 요구합니다. 그러다 보니, 또 상상으로 빠졌는데, 나름 의미있는 추측 아닐까 해서 올립니다.

생각 스트레칭
이름이 없는 람다 함수를 다시 부를 방법이 뭐가 있을까요? 이름이 없으면, 부를 방법은 없습니다. 사실 람다 계산법엔 람다 함수에 이름을 붙이는 방법이 존재합니다. 바로 람다 헤드에 있는 변수에 인자로 넘기는 겁니다. 이렇게 매개 변수에 바인딩하면, 현재 람다 함수 내부에서는 이름을 가지게 됩니다.

(\g ->    ...    ) (\f -> ...)
       ^^^(나)^^^  ^^^(가)^^^^

(가)는 (나)에서 g라는 이름과 바인딩 됩니다. 람다 함수가 항상 이름이 없는anonymous 건 아닌 겁니다.

\n -> if n == 0 then 1 else n * (다) (n - 1)
^^^^^^^^^^^^^^^^^^^^(다)^^^^^^^^^^^^^^^^^^^^^

이렇게, 재귀로 부르면 되는데, 이름이 없는 상태니, 이름을 붙여야 합니다.

\f -> \n -> if n == 0 then 1 else n * f (n - 1) -- (라)

f로 이름을 붙였습니다. 이제 이 f를 통해 함수를 넣어 줄 컴비네이터³가 필요합니다. 스스로 자기 자신을 부르는 건 안되지만, 누군가가 반복해서 불러 줄 수 있게는 됐습니다.

fix f = f (fix f)
fact = fix $ \f -> \n -> if n == 0 then 1 else n * f (n - 1)

(라) 고차 함수에 (다) 함수를 넣어주면 (다) 함수가 나옵니다. f a가 a와 같을 때 a를 f의 고정점이라 하듯 (다) 함수는 (라) 고차 함수의 고정점fixed point입니다.

fix 함수는 인자로 받은 함수의 고정점을 반환하는 함수입니다. 어떻게, 저 정의만으로 고정점이 찾아질까요? 만일, f가 만들어내는 의미있는 결과를 다음 fix f를 알아야만 한다면, 무한히 반복될 수 밖에 없습니다.

fix f = f (fix f)
      = f (f (fix f))
      = f (f (f (f ( ...fix f...))))

하지만, f를 반복하다 다음 fix f의 값을 몰라도 되는 때가 생긴다면 멈출 수 있습니다. 아래의 경우 멈출 가능성을 만들어 주는 부분이 n - 1입니다. f를 반복하면서, 계속 똑같은 세상을 대상으로 하는 게 아니라, -1씩 변화가 생긴 세상을 대상으로 반복합니다.

-- 3을 넣으면,
fix (\f -> \n -> if n == 0 then 1 else n * f (n - 1)) 3
  = (\f -> \n -> if n == 0 then 1 else n * f (n - 1)) (fix ...) 3
  = \n -> 멈출 가능성이 있는 if문 n * ((fix ...) (n - 1)) 3 
  = \n -> 멈출 가능성이 있는 if문 n * (\n -> 멈출 가성성이 있는 if문 (n - 1) * ((fix ...) (n - 1 - 1))) 3
  = \n -> 멈출 가능성이 있는 if문 n * (\n -> if문... (n - 1) * (\n -> if문... (n - 2) * ((fix ...) (n - 1 - 1)))) 3
  -- fix f는 나중에 필요할 때 확장(평가)한다고 보면 됩니다. 여기선 3일 때, 필요한 만큼만 풀어 놨습니다.
  =               3 * (              (3 - 1) * (              (3 - 2) * 1))

여기까진 수렴하는 재귀에 대한 설명이고, 지금부터는 아주 인포멀한 상상입니다.

f 반복으로 고정점을 찾을 수 있는 이유를 다음처럼 상상해 봤습니다.

원래부터 f를 몇 번씩 반복하게 생겨먹은 함수에 f를 한 번 더 적용한다고 티가 나지 않습니다.

f (f (f (f ( ...fix f...))))
-- 이런 함수에 f를 한 번 더 적용한다고 무슨 차이가 있을까요?
f (f (f (f (f ( ...fix f...)))))

어찌 보면 당연한 정의 같아 보이기도 합니다. f를 적용해도 변화되지 않은 함수가 나오게 하려면, 애초에 f가 정해지지 않은 수로 적용된 놈을 고르면 됩니다.

여러 번 반복하는 걸, 하나로 바라본다는 측면에서 모노이드와 비슷한 철학이 보입니다.

복잡한 개념이 숨어 있는 고정점을 살짝 맛만 봤습니다. Combinatory logic도 보고, 커리 역설이 뭔지도 보고, domain theory도 보고… 그래야 하지만, 하스켈에선 재귀를 쓸 수 있으니, 그냥 아래와 같이 정의하면 됩니다!

fact = \n -> if n == 0 then 1 else n * fact (n - 1)