5. 엄격성과 지연성

코틀린은 기본적으로 엄격한 평가를 수행합니다. 

엄격하다는 것이 무엇일까요?

함수를 호출하기 전에 함수 파라미터를 완전히 평가한다는 뜻입니다. 
엄격한 평가에서 식은 식이 변수에 바운드되는 순간에 평가됩니다. 

fun main() {
	get(1+2, 10.0.pow(300))
}

fun get(a: Int, b: Double) {
	//...
}

요런 코드가 있을 때, get 함수를 호출하는 시점에 1+2, 10.0.pow(300)은 평가됩니다. 

평가하는 과정이 너무 복잡하고 비싸면 어떻게 할까?

리스트에 모든 요소에 평가를 해야하는데, 실제로는 몇개의 요소만 사용한다면 이러한 연산은 비효율적입니다. 

지연 평가를 사용하면 이 비효율을 줄일 수 있습니다. 

지연 평가는 값을 선언한(바운딩된) 시점이 아니라 실제 참조하는 시점에 계산이 이루어집니다.
필요에 따라 값을 계산하는 것입니다.

코틀린의 비효율적인 코드

List.of(1, 2, 3, 4).map { it + 10 }.filter { it % 2 == 0 }.map { it * 3 }

map, filter, map의 각 단계 마다 중간 리스트를 만들어낸다. 다음 변환의 입력으로 쓰인 후 즉시 버려질 임시 리스트를 만들어내는 것이다. 

지연 연산을 통해 이런 변환의 시퀀스를 융합해 한 번의 처리 단계로 끝낼 수 있다. 

5.1 엄격한 함수와 엄격하지 않은 함수

엄격성과 비엄격성에 대해 알아보고, 엄격성에 대한 형식적 정의를 하겠습니다. 

엄격한 함수

• 대부분 프로그래밍 언어의 표준
• 항상 모든 인자를 평가

엄격하지 않은 함수(비엄격성)

• 함수가 하나 이상의 인자를 평가하지 않기로 선택했다는 뜻

 

엄격한 함수

fun square(x: Double): Double = x * x

square(41.0 + 1.0)
square(exitProcess(-1))

이렇게 함수를 호출하면, 41.0 + 1.0을 계산해서 42.0을 전달받고,
square함수블럭에 들어가기 전에 exitProcess()가 호출되어 프로그램이 종료될 것입니다. 

이는 함수가 호출되기 전에 인자에 대해 평가가 일어난 것이고 이를 엄격한 함수라고 합니다. 

비엄격성의 예시

우리가 이미 쓰고있던 문법에도 비엄격성이 녹아있습니다. 

쇼트 서킷이라고 불리는 &&, || 같은 경우는 엄격하지 않습니다.
&&의 경우 첫 번째 인자가 true일 때만 두 번째 인자를 평가합니다. 
||의 경우 첫 번쨰 인자가 false일 때만 두 번째 인자를 평가합니다. 

또 if도 엄격하지 않습니다. 

val result = if (input.isEmpty()) exitProcess(-1) else input

if를 삼항연산자처럼 사용할 수 있습니다. 
여기서 조건식에 따라 참 거짓중 하나는 평가하지 않습니다. 모든 인자를 평가하지 않기 때문에 엄격하지 않다고 할 수 있습니다. 

다만 조건식에 대해서는 엄격하다고 할 수 있습니다. 

코틀린에서 엄격하지 않은 함수 작성하기

코틀린에서 엄격하지 않은 함수를 어떻게 작성할까요? 다른말로, 득정 인자를 평가하지 않겠다고 어떻게 표현할까요?

따로 표현하는 방법은 없고, () -> A 이러한 함수 타입을 사용해서 평가하지 않은 값을 표현합니다. 

fun maybeTwice(b: Boolean, i: () -> Int) =
	if (b) i() + i() else 0

이 함수에서 i 는 함수 타입이고, 이는 평가하지 않는 값입니다.. 

i를 보통 thunk라고 부르고, 함수 안에서 thunk를 실행하여 식을 평가한 결과를 얻을 수 있습니다. 

val x = maybeTwice(true) { 1 + 41 }

그런데 위 함수처럼 thunk를 여러번 실행한다면, 매번 평가가 일어납니다. 
i()를 호출할 때만다 1+41 연산이 수행된다는 것 입니다. 연산이 복잡하고 오래걸린다면 이 또한 골칫거리입니다. 

그래서 thunk를 한 번만 실행하고 값을 캐싱해서 사용하는 방법이 있습니다. 

fun maybeTwice2(b: Boolean, i: () -> Int) {
	val j: Int by lazy(i)
    if (b) j + j else 0
}

j라는 변수에 i의 결과를 캐싱했습니다. 
i를 실행하는 시점은 j를 참조하는 순간입니다. 이는 lazy 내장함수를 통해 가능합니다. 

fun maybeTwice3(b: Boolean, i: () -> Int) {
    val j: Int = lazy(i).value
    println("before if")
    if (b) j + j else 0
}

fun maybeTwice4(b: Boolean, i: () -> Int) {
    val j: Int = i()
    println("before if")
    if (b) j + j else 0
}

fun maybeTwice5(b: Boolean, i: () -> Int) {
    val j: Lazy<Int> = lazy(i)
    println("before if")
    if (b) j.value + j.value else 0
}

이런식으로도 작성할 수 있습니다. 

단, maybeTwice3, 4의 경우는 지연 초기화는 일어나지 않고 단순 캐싱만 일어납니다.
maybeTwice5같이 위임을 사용하지 않고도 지연 초기화를 할 수 있습니다. 

엄격성의 형식적인 정의

어떤 식을 평가했는데 결과를 반환하는 대신 영원히 실행되거나, 오류를 던지는 경우를 생각해봅시다.

fun maybe(value: Int) {
	//...
}

fun something1(): Int {
	while(true) {
    }
	return 0
}

fun something2(): Int {
	throw Exception()
    return 0;
}

maybe(something1())
maybe(something2())

이런 경우 일 것입니다. 이럴 떄 식이 종료되지 않는다는 뜻으로, "바텀으로 평가된다"라고 합니다.

엄격성이란.
어떤 식 x가 바텀으로 평가될 때 함수 f도 항상 바텀으로 평가된다면 이 함수 f를 엄격한 함수라고 말한다.

something1()과 something2()가 바텀으로 평가되는데, maybe(something1())도 바텀으로 평가되므로, maybe()는 엄격한 함수이다. 

5.2 확장 예제: 지연 리스트

List.of(1, 2, 3, 4).map { it + 10 }.filter { it % 2 == 0 }.map { it * 3 }

앞에서 이 예제를 얘기하며 엄격한 연산의 비효율성에 대해 얘기했었습니다.
각 단계를 수행하며 매번 새로운 리스트가 만들어져 비효율적이라는 게 문제였습니다. 
스트림을 사용하여 연쇄적인 변환이 지연 연산을 통해 하나의 단계로 융합하여 문제를 해결할 수 있습니다.

또한 지연 연산을 사용하면 함수형 프로그램의 효율을 높이고 모듈화를 촉진할 수 있습니다. 

sealed class Stream<out ITEM>

data class Cons<out ITEM>(
    val head: () -> ITEM,
    val tail: () -> Stream<ITEM>
) : Stream<ITEM>()

object Empty : Stream<Nothing>()

Stream이라는 새로운 자료형을 정의했습니다. 보기에 List와 비슷해보이지만, Cons의 생성자에 엄격한 값이 아니라 thunk를 받습니다.
2023.09.10 - [Programming/코틀린 함수형 프로그래밍] - 3. 함수형 데이터 구조 - Functional Programming in Kotlin

Stream을 관찰하거나 순회하려면, thunk를 강제로 평가해야 합니다. 

fun <ITEM> Stream<ITEM>.headOption(): Option<ITEM> =
    when(this) {
        is Empty -> None
        is Cons -> Some(head())
    }

Cons라면 Some(head())를 반환합니다. head()를 계산하는 과정이 있지만, 그 외에는 List와 똑같이 작동합니다. 

여기서는 tail()을 계산하지 않았습니다. 이런식으로 필요한 부분만 계산할 수 있는 것도 장점입니다. 

5.2.1 스트림을 메모이제이션해서 재계산 피하기

복잡한 계산은 피하는게 좋다. 메모이제이션은 어떤 식을 최초로 평가한 결과를 캐시에 넣고, 다음부터는 재사용하는 것이다. 

Cons 노드에 thunk를 강제 계산하고 나면 캐싱을 해두고 싶다. 하지만 지금 구조에서는 그렇지 않다.

val x = Cons({ println("cons"); 1}, { Empty })
val h1 = x.headOption()
val h2 = x.headOption()

이 코드에서는 head thunk를 2번 평가한다. 

메모이제이션을 하려면 일반적으로 스마트 생성자를 사용한다. 

data class Cons<out ITEM>(
    val head: () -> ITEM,
    val tail: () -> Stream<ITEM>
) : Stream<ITEM>() {
    companion object {
        fun <ITEM> cons(head: () -> ITEM, tail: () -> Stream<ITEM>): Stream<ITEM> {
            val head: ITEM by lazy(head)
            val tail: Stream<ITEM> by lazy(tail)
            return Cons({ head }, { tail })
        }
    }
}

관습적으로 클래스의 companion object에 위치하고, 클래스 이름의 첫글자를 소문자로 바꿔 함수명을 짓는다.
이 스마트 생성자를 통해 객체를 생성하면 head, tail이 변수에 캐싱되어, 처음 thunk가 실행될 때 한 번만 평가한다. 

sealed class Stream<out ITEM> {
    companion object {
        fun <ITEM> of(vararg xs: ITEM): Stream<ITEM> =
            if (xs.isEmpty()) Empty.empty()
            else Cons.cons({ xs[0] }, { of(*xs.sliceArray(1..<xs.size)) })
    }
}

object Empty : Stream<Nothing>() {
    fun <ITEM> empty(): Stream<ITEM> = Empty
}

Empty에 대한 스마트 생성자도 만들고, Stream을 of를 통해 생성할 수 있도록 만들었다.

5.2.2 스트림 관찰을 위한 도우미 함수

연습문제 5.1 ~ 3

fun <ITEM> Stream<ITEM>.toList(): List<ITEM> =
    when (this) {
        is Empty -> Nil
        is Cons -> funfun.study.kfp.chap3.Cons(head(), tail().toList())
    }
    
fun <ITEM> Stream<ITEM>.take(n: Int): Stream<ITEM> =
    if (n == 0) Empty
    else when (this) {
        is Empty -> Empty
        is Cons -> Cons(head, { tail().take(n - 1) })
    }

fun <ITEM> Stream<ITEM>.drop(n: Int): Stream<ITEM> =
    if (n == 0) this
    else when (this) {
        is Empty -> Empty
        is Cons -> tail().drop(n - 1)
    }
    
fun <ITEM> Stream<ITEM>.takeWhile(p: (ITEM) -> Boolean): Stream<ITEM> =
    when (this) {
        is Empty -> Empty
        is Cons -> if (p(head())) Cons(head, { tail().takeWhile(p) }) else Empty
    }

5.3 프로그램 기술과 평가 분리하기

앞에서부터 계속 관심사 분리를 해왔다. 

어떤 계산을 할지와 계산을 수행하는 것을 분리하고, 오류에 대한 포획과 오류에 대한 처리를 분리했다. 

지연 계산을 사용하면 식에 대한 기술(description)과 식에 대한 평가를 분리할 수 있다.

비용이 큰 커다란 식을 기술하고 일부만 평가하도록 선택하는 강력한 능력을 가질 수 있다. 

fun <ITEM> Stream<ITEM>.exists(p: (ITEM) -> Boolean): Boolean =
    when (this) {
        is Cons -> p(head()) || this.tail().exists(p)
        else -> false
    }

exists함수는 stream안에 어떤 Boolean 함수를 만족하는 원소가 있는지 검사한다.

여기서 ||는 두 번째 인자에 대해 엄격하지 않다. p(head())가 true라면 뒤는 평가하지 않는다. 그렇다면 또한 tail 역시 평가하지 않는다는 것이다 

fun <ITEM, RESULT> Stream<ITEM>.foldRight(
    default: () -> RESULT,
    combine: (ITEM, () -> RESULT) -> RESULT
): RESULT =
    when (this) {
        is Cons -> combine(head(), { tail().foldRight(default, combine) })
        is Empty -> default()
    }

fun <ITEM> Stream<ITEM>.exists2(p: (ITEM) -> Boolean): Boolean =
    foldRight({ false }, { a, b -> p(a) || b() })

명시적 재귀를 사용하지 않고, foldRight를 사용하여 재귀를 구현할 수도 있다.

연습문제 5.4 ~ 7

fun <ITEM> Stream<ITEM>.forAll(condition: (ITEM) -> Boolean): Boolean =
    when (this) {
        is Cons -> if (condition(head())) tail().forAll(condition) else false
        is Empty -> true
    }

fun <ITEM> Stream<ITEM>.forAll2(condition: (ITEM) -> Boolean): Boolean =
    foldRight({ true }, { head, tail -> condition(head) && tail() })



fun <ITEM> Stream<ITEM>.takeWhile2(p: (ITEM) -> Boolean): Stream<ITEM> =
    foldRight(
        { Empty },
        { head, tail: () -> Stream<ITEM> ->
            if (p(head)) Cons({ head }, { tail().takeWhile2(p) }) else Empty
        }
    )

fun <ITEM> Stream<ITEM>.headOption2(): Option<ITEM> =
    foldRight({ None }, { head, tail: () -> Option<ITEM> ->
        Some(head)
    })


fun <ITEM, RESULT> Stream<ITEM>.map(f: (ITEM) -> RESULT): Stream<RESULT> =
    foldRight({ Empty.empty() }, { head, tail: () -> Stream<RESULT> ->
        Cons({ f(head) }, tail)
    })

fun <ITEM> Stream<ITEM>.filter(f: (ITEM) -> Boolean): Stream<ITEM> =
    foldRight({ Empty.empty() }) { h, t ->
        if (f(h)) Cons({ h }, t) else t()
    }

fun <ITEM> Stream<ITEM>.append(sa: () -> Stream<ITEM>): Stream<ITEM> =
    foldRight(sa) { h, t ->
        Cons({ h }, t)
    }

5.4 공재귀 함수를 통해 무한한 데이터 스트림 생성하기

지금까지 작성한 함수들은 무한 스트림에 대해서도 작동한다. 
무한 스트림도 점진적으로 계산이 이뤄지기 때문이다.

fun ones(): Stream<Int> = Cons.cons({ 1 }, { ones() })

무한 시퀀스를 생성하는 코드이다. 

ones().take(5).toList()
ones().exists { it % 2 != 0 }
ones().map { it + 1 }.exists { it % 2 == 0 }
ones().takeWhile { it == 1 }

이런 연산들을 그대로 사용할 수 있다. 

하지만 아래와 같은 연산들은 stack overflow가 날 수 도 있다. 무한 스트림을 영원히 검사하기 때문이다. 

ones().forAll2 { it == 1 }
ones().takeWhile { it == 1 }.toList()
ones().exists { it % 2 == 0 }

연습문제

5.8

fun <ITEM> constant(item: ITEM): Stream<ITEM> = Cons.cons({ item }, { constant(item) })

5.9

fun from(n: Int): Stream<Int> = Cons.cons({ n }, { from(n + 1) })

5.10

fun fibs(): Stream<Int> {
    fun go(a: Int, b: Int): Stream<Int> {
        return Cons.cons({ a }, { go(b, a + b) })
    }
    return go(0, 1)
}

5.11

fun <A, S> unfold(z: S, f: (S) -> Option<Pair<A, S>>): Stream<A> =
    when (val s = f(z)) {
        is None -> Empty
        is Some -> {
            val (cur, next) = s.get
            Cons.cons({ cur }, { unfold(next, f) })
        }
    }

5.12

fun ones2(): Stream<Int> = unfold(1) {
    Some(1 to 1)
}

fun <A> constant2(a: A): Stream<A> =
    unfold(a) {
        Some(a to a)
    }

fun from2(n: Int): Stream<Int> =
    unfold(n) {
        Some(it to it + 1)
    }

fun fibs2(): Stream<Int> =
    unfold(0 to 1) { (cur, next) ->
        Some(cur to (next to (cur + next)))
    }

5.13

fun <ITEM, RESULT> Stream<ITEM>.map2(f: (ITEM) -> RESULT): Stream<RESULT> =
    unfold(this) {
        when (it) {
            is Empty -> None
            is Cons -> {
                Some(f(it.head()) to it.tail())
            }
        }
    }

fun <ITEM> Stream<ITEM>.take2(n: Int): Stream<ITEM> =
    unfold(n to this) { (num, item) ->
        if (num == 0) None
        else when (item) {
            is Empty -> None
            is Cons -> Some(item.head() to (num - 1 to item.tail()))
        }
    }

fun <ITEM> Stream<ITEM>.take3(n: Int): Stream<ITEM> =
    unfold(this) { item ->
        when (item) {
            is Empty -> None
            is Cons -> {
                if (n == 0) None
                else Some(item.head() to item.tail().take3(n - 1))
            }
        }
    }

fun <ITEM> Stream<ITEM>.takeWhile3(p: (ITEM) -> Boolean): Stream<ITEM> =
    unfold(this) { item ->
        when (item) {
            is Empty -> None
            is Cons ->
                if (p(item.head())) Some(item.head() to item.tail())
                else None
        }
    }

fun <ITEM1, ITEM2, RESULT> Stream<ITEM1>.zipWith(
    that: Stream<ITEM2>,
    combine: (ITEM1, ITEM2) -> RESULT
): Stream<RESULT> =
    unfold(this to that) { (item1, item2) ->
        when (item1) {
            is Empty -> None
            is Cons -> when (item2) {
                is Empty -> None
                is Cons -> Some(combine(item1.head(), item2.head()) to (item1.tail() to item2.tail()))
            }
        }
    }

fun <ITEM1, ITEM2> Stream<ITEM1>.zipAll(that: Stream<ITEM2>): Stream<Pair<Option<ITEM1>, Option<ITEM2>>> =
    unfold(this to that) { (item1, item2) ->
        when (item1) {
            is Empty -> when (item2) {
                is Empty -> None
                is Cons -> Some((None to Some(item2.head())) to (Empty.empty<ITEM1>() to item2.tail()))
            }

            is Cons -> when (item2) {
                is Empty -> Some((Some(item1.head()) to None) to (item1.tail() to Empty.empty()))
                is Cons -> Some((Some(item1.head()) to Some(item2.head())) to (item1.tail() to item2.tail()))
            }
        }
    }

5.14

fun <ITEM> Stream<ITEM>.startsWith(that: Stream<ITEM>): Boolean =
    this.zipWith(that) { item1, item2 ->
        item1 == item2
    }.forAll { it }

5.15

fun <ITEM> Stream<ITEM>.tails(): Stream<Stream<ITEM>> =
    unfold(this) { item ->
        when(item) {
            is Cons -> Some(item to item.tail())
            is Empty -> None
        }
    }