코틀린으로 살펴보는 Y 컴비네이터 (Feat Fixed Point)

- Y-Combinator를 사용한 함수 고정점 소개  과 [Kotlin Pearls 8] Recursion, Tail Recursion and Y Combinator | by Uberto Barbini | ProAndroidDev 의 Y Combinator 부분 간단한 요약임

 

재귀함수

간단한 재귀함수를 짜보자

// 재귀 함수를 짜보자
fun factorial (n: Int): Int {
    if (n == 0) return 1
    return n * factorial(n - 1)
}

짜잔!

재귀는 자기 자신을 호출하므로, factorial 내부에서 factorial 을 호출하면 된다.

 

람다로 짜보자

val factorialLambda: (Int) -> Int = { n ->
    if (n == 0) 1 else n * factorialLambda(n - 1)
}

 

에러가 난다.

재귀는 자기 자신을 Call 하는데, 자기 자신이라는 Identifier 가 존재 하지 않는다 (람다이기때문에..)

람다는 이름이 없어서 이름을 붙여주기 위하여 val 에 할당하면 이름이 생기는데 그 이름을 호출하기 위해서는 Body 를 완성시켜야되는데 이름이 없어서 오류가 나고 이 오류를 해결하기 위하여 호출가능한 이름을 붙여줘야 하는데 람다는 이름이 없어서 이름을 붙여주기 위하여 val 에 할당하면....

 

그냥 파라미터로 받음 되는거 아님?

함수도 파라미터로 받을수있는 FP 의 혁신적 기법덕분에

참조 할 수 있게 파라미터 f 를 받아서 쓰자. 

// 컴파일이 불가능한 Labmda factorial 재귀
val factorialLambda: (Int) -> Int = { n ->
    if (n == 0) 1 else n * factorialLambda(n - 1)
}

// 참조 가능하게 F 를 받자
val factorialGenerator: ((Int)->Int) -> (Int) -> Int = { f ->
    { n -> if (n <= 1) 1 else n * f(n - 1) }
}

factorialGenerator 로 재귀 람다 함수의 본문은 정의 했다, 이제 컴파일 오류따위는 없다

이제 factorialGenerator 로 factorial 을 만들어 사용하면 된다.

val f1 = factorialGenerator(??); // 결국 여기에 뭐가 들어가야되지?
//아하! 펙토리얼 함수가 들어가야되니까 factorialGenerator 로 만들면되겠네

val f2 = factorialGenerator(factorialGenerator(??)); // 결국 여기에 뭐가 들어가야되지?
//아하! 펙토리얼 함수가 들어가야되니까 factorialGenerator 로 만들면되겠네

val f3 = factorialGenerator(factorialGenerator(factorialGenerator(??)));// 결국 여기에 뭐가 들어가야되지?
//아하! 펙토리얼 함수가 들어가야되니까 factorialGenerator 로 만들면되겠네

val f4 = factorialGenerator(factorialGenerator(factorialGenerator(factorialGenerator(??))));// 결국 여기에 뭐가 들어가야되지?
//아하! 펙토리얼 함수가 들어가야되니까 factorialGenerator 로 만들면되겠네

후략...

이젠 내가 무한루프에 같혀버렸다...

.. 사용할수가 없다... 넘겨줘야 하는 f 를 정의 할 수가 없다..

코드가 안끝난다

 

헬퍼 함수를 만들어서 쓰자..

fun closeLoop (factorialGenerator: ((Int)->Int) -> (Int)->Int): EndoMorph<Int> {
    fun result (v: Int): Int {
        val completeFn =  factorialGenerator(::result)
        return completeFn(v)
    }
    return ::result
}

println(closeLoop(factorialGenerator)(5)) // 120

헬퍼함수의 동작을 살펴보면,

내가 직접 넣어주는것이 아닌, RunTime result 가 들어가게 되고, result 는 다시 factorialGenerator 를 호출하므로,

결국 factorialGenerator 가 더이상 내부적으로 f 를 쓰지 않는상황 (재귀 함수 종료 조건) 이 올때까지 반복하다가 끝나게 된다, (아니면 계속 돌다가 런타임중에 스택오버플로우로 터질것이다)

이렇게 람다에서 무한한 재귀를 정의할 수 있게 하고 사용할수 있게 하는 저런 Helper 함수가 바로 Y 콤비네이터 되시겠다. 

 

실제로 이 Y 컴비네이터가 저 Y 컴비네이터에서 따온 이름이다.

 

Fix Point (고정점)

Y 컴비네이터를 설명하기 전에, Fixed Point 가 무엇인지부터 알아보자 

부동소수점/고정소수점할때의 Fixed Point 는 아니고 다른 개념이다.

 

수학에서 함수의 고정점은 함수의 정의역에 속하는 원소 중에서 함수에 의해 자기 자신으로 매핑되는 원소를 말합니다. 즉, 함수 f 가 있을 때, x = f(x) 를 만족하는 x가 고정점입니다.

 

그니까

fun myFormula(x: Double): Double = x * 5 - 8
fun square(x: Int): Int = x * x
fun reverse(s: String): String = s.reversed()

println("x is " + 2.0 + " then myFormula is " + myFormula(2.0))
println("x is " + 1 + " then square is " + square(1))
println("s is " + "abba" + " then reverse is " + reverse("abba"))
    
//x is 2.0 then myFormula is 2.0 : 2 = f(2)
//x is 1 then square is 1 : 1 = f(1)
//s is abba then reverse is abba = abba = f(abba)

myFormula 의 고정점은 2.0

square 의 고정점은 1

reverse 의 고정점은 abba , aaaa, bbbb, caac ... 등등이 되시겠다.

 

그리고 자기 자신이 나오기 위해서는, 당연히 Parameter 의 Type 과 Return Type 이 같아야한다.

이를 Endomorphisms 이라고 한다 (자기 사상)

// EndoMorph 은 같은 타입을 받아서 같은 타입을 리턴하는 함수
typealias EndoMorph<A> = (A) -> A

 

FP 에서는 함수 조차 값이기 때문에 다음과 같은 함수도 가능하다

fun takeFunction(x: (Int) -> Int): (Int) -> Int {
    return x
}

fun takeEndoMorph(x: EndoMorph<Int>): EndoMorph<Int> {
    return x
}

위 함수는 x 를 바로 리턴하므로, 어떤 (int) -> int 함수든 takeFunction 의 fixed Point 라고 할 수 있다

    val x = { x: Int -> x + 1 }
    val fixedX = takeFunction(x)

    println(x == fixedX) // true
    
    // { x: Int -> x + 1 } 라는 람다펑션은,  takeFunction 의 FixedPoint

 

Y 컴비네이터

FixedPoint 를 찾기위한 컴비네이터가 Fixed Point 컴비네이터 이고, 그중 recursive functions 에 대하여 Fixed Point 를 찾는 컴비네이터가 바로 Y 컴비네이터 이다.

 

일반 함수로 정의 되어있다 손 치면, factorialGenerator 의 고정점은 다음과 같을것이다.

fun factorialFn(n: Int): Int {
    return if (n <= 1) 1 else n * factorialFn(n - 1)
}

fun factorialFnGenerator(f: (Int) -> Int): (Int) -> Int {
    return ::factorialFn
}

// factorialFnGenerator 의 고정점은 ::factorialFn 자체

 

findFix 라는 함수가 있다면 람다에서도 다음과 같이 쓸수 있을것이다.

// 불가능한 Labmda factorial 재귀
val factorialLambda: EndoMorph<Int> = { n ->
    if (n == 0) 1 else n * factorialLambda(n - 1)
}

// 참조 가능하게 F 를 받자
val factorialGenerator: (EndoMorph<Int>) -> EndoMorph<Int> = { f ->
    { n -> if (n <= 1) 1 else n * f(n - 1) }
}

// findFix 를 찾자, 일반 함수 버전과 같이, 그냥 재귀함수 그 자체가 fixedPoint가 된다
val fixedPoint = findFix(factorialGenerator)

// factorialGenerator 의 Fixed Point 는 { n -> if (n <= 1) 1 else n * f(n - 1) } 이다.
val factorialFromGenerator = factorialGenerator(fixedPoint)

val value1 = factorialFromGenerator(5) // 이제 factorialGenerator 로 factorial 을 만들어서 쓸수있다!
val value2 = fixedPoint(5) // 근데 찾은 고정점 이 재귀함수 자체라 애초에 그냥 이거 써도 됨 ㄷㄷ

 

 

일단 Fixed Point 를 찾는 함수를 Kotlin 에 정의해보자

fun <A> findFix (x:(EndoMorph<A>) -> EndoMorph<A>): EndoMorph<A> {
    val f = x
    return f(findFix(f))
}

x = f(x) = f(f(x)) = f(f(f(x))) ...

fun closeLoop (factorialGenerator: ((Int)->Int) -> (Int)->Int): EndoMorph<Int> {
    fun result (v: Int): Int {
        val completeFn =  factorialGenerator(::result)
        return completeFn(v)
    }
    return ::result
}

println(closeLoop(factorialGenerator)(5)) // 120

위와 사실상 동일 하다..

즉 closeLoop == findFix == Y 컴비네이터 이다.

 

Lazy

이제 findFix 를 이용하여 고정점을 찾았으니 재귀함수를 람다로 정의할 수 있다!

확인해보자

는 터짐~

 

이유는 우리가 방금 정의한 findFix 함수는 실행이 eager 하다

처음에 만든 closeLoop는 result 가 돌면서 -> result 를 넣고 -> 이게 돌면서 result 를 넣고 -> ... -> 종료조건되면 종료..

인데, findFix는 실행하는순간, input parameter x 가 평가되고 또 그안에서 평가하고 또 그안에서 평가하고 ... 되어, 실행하기도 전에 터져 버리는것.

 

해결방법은 그냥 lazy 하게 실행시키면 된다..

typealias EndoMorph<A> = (A) -> A

data class LazyFix<A>(val callIt: (LazyFix<A>) -> EndoMorph<A>)

fun <A> findFixLazy(lazyFix: LazyFix<A>): EndoMorph<A> =
    lazyFix.callIt(lazyFix)

fun<A> Y(recursiveFun:(EndoMorph<A>) -> EndoMorph<A>): EndoMorph<A> =
    findFixLazy(LazyFix { rec -> recursiveFun{ x -> findFixLazy(rec)(x) } })

// 참조 가능하게 F 를 받자
val factorialGenerator: (EndoMorph<Int>) -> EndoMorph<Int> = { f ->
    { n -> if (n <= 1) 1 else n * f(n - 1) }
}

fun main() {
    println(Y(factorialGenerator)(5))
    println(Y<Int> { f -> { n -> if (n <= 1) 1 else n * f(n - 1) } }(5)) // 와! 람다로 재귀가 된다 혁신적이다.
}

 

마지막으로 FixedPoint 가 맞는지 확인해보자

fun testFactorial(f: EndoMorph<Int>) {
    println(listOf(1, 2, 3, 4, 5, 6, 7).map(f))
}

fun main() {
    val factorial = Y(factorialGenerator)
    val factorial2 = factorialGenerator(factorial)
    val factorial3 = factorialGenerator(factorialGenerator(factorial))
    val factorial4 = factorialGenerator(factorialGenerator(factorialGenerator(factorial)))

    testFactorial (factorial)
    testFactorial (factorial2)
    testFactorial (factorial3)
    testFactorial (factorial4)
}

//[1, 2, 6, 24, 120, 720, 5040]
//[1, 2, 6, 24, 120, 720, 5040]
//[1, 2, 6, 24, 120, 720, 5040]
//[1, 2, 6, 24, 120, 720, 5040]

고정점이 확실하다.. 재귀만 돌렸을뿐인데!