함수형 프로그래밍으로 루프 사용 줄이기

모든 프로그래밍 구문 가운데 가능한한 반드시 절대적으로 줄여야 하는 것이 바로 루프다. 루프는 작성하기도 힘들지만 읽기는 더 힘들고, 코드 복잡도를 크게 증가시키며 디버깅을 힘들게 만들어서 온갖 잡기 힘든 버그의 온상이 되기 쉽다. 예를 들어 다음과 같은 코드를 생각해 보자:

private KoreanTextMatch match(String text, int startIndex, int length) {
    if (_pattern.length() == 0)
        return new KoreanTextMatch(this, text, 0, _pattern.length());

    for (int i = startIndex; i < startIndex + length - _pattern.length() + 1; i++) {
        for (int j = 0; j < _pattern.length(); j++) {
            if (!KoreanCharApproxMatcher.isMatch(text.charAt(i + j), _pattern.charAt(j)))
                break;

            if (j == _pattern.length() - 1)
                return new KoreanTextMatch(this, text, i, _pattern.length());
        }
    }
    return KoreanTextMatch.EMPTY;
}

KoreanTextMatcher에서 문자열 검색을 하는 핵심 루틴으로, 이중 for 루프를 쓴 전형적인 명령형 프로그래밍 스타일 코드이다. 이 자바 코드는 두가지 심각한 문제를 가지고 있는데,

무슨 일을 하는 코드인지 따로 설명이 없으면 알아내기가 대단히 힘들다
무슨 일을 하는 코드인지 이해하더라도 제대로 작동하는지 예측하기는 더더욱 힘들다

이것을 .NET 버전의 KoreanTextMatcher에 포함된 아래 코드와 비교해 보자:

member this.Match(text, startIndex, length) =
    if pattern.Length = 0 then KoreanTextMatch(this, text, 0, 0)
    elif length < pattern.Length then KoreanTextMatch.Empty
    else
        text
        |> Seq.skip startIndex
        |> Seq.take length
        |> Seq.windowed pattern.Length
        |> Seq.tryFindIndex (fun subtext ->
            (subtext, pattern)
            ||> Seq.forall2 KoreanCharApproxMatcher.isMatch)
        |> function
            | Some index -> KoreanTextMatch(this, text, index, pattern.Length)
            | None -> KoreanTextMatch.Empty

이 F# 코드는 실제로 위의 자바 코드와 100% 똑같은 일을 한다. 이 두번째 코드의 특징은

루프가 전혀 없다
값이 변하는 변수가 전혀 없다
실행 흐름이 파이프라인을 따라 직선화되어 있어서 코드를 쉽게 이해할 수 있다.
코드를 이해하기 쉽기 때문에 디버깅하기도 쉽다.

이제 이 코드를 하나씩 분해해 가면서 함수형 프로그래밍과 명령형 프로그래밍이 어떻게 다른지 비교해 보자.

검색할 텍스트의 구간 줄이기

이 match/Match 메쏘드의 목적은 text의 [startIndex, startIndex + length) 구간내에 존재하는 pattern을 찾는 것이다(pattern은 클래스 필드 변수로 미리 정의되어 있음). 명령형 프로그래밍의 전형적인 아이디어는 text를 순회할 루프 카운터 i를 만들고 이 값을

    for (int i = startIndex; i < startIndex + length - _pattern.length() + 1; i++) {

처럼 startIndex와 startIndex + length - _pattern.length() + 1 구간에서 움직이도록 하는 것이다. 여기서 특히 뒤의 - _pattern.length() + 1 부분이 중요한데, 이 부분을 틀리게 계산하면 나중 pattern의 루프 카운터가 문자열 범위를 이탈하면서 예외가 발생하게 된다. 반면 함수형 프로그래밍에서는

        text
        |> Seq.skip startIndex
        |> Seq.take length

처럼 text의 맨 앞 startIndex개를 건너 뛰고 그 이후의 length 개만큼을 취해서 파이프라인의 뒤쪽으로 넘겨준다. 루프 카운터와 복잡한 인덱싱은 전부 Seq.skip/Seq.take 함수 안으로 숨어들어가 있다.

원래의 조건이었던 text의 [startIndex, startIndex + length) 구간을 생각해 보면 두 코드의 차이를 더 잘 느낄 수 있다. 조건과 달리 명령형 코드는 i를 [startIndex, startIndex + length - _pattern.length() + 1] 구간에서 움직이도록 하는 반면 함수형 코드는 구간 조건과 정확히 일치한다.

문자열 비교

text 내에서 pattern을 찾으려면 text의 특정 위치에서 시작해서 pattern의 길이 만큼되는 부분문자열을 pattern과 비교하면 된다. 이때 명령형 프로그래밍에서는 pattern을 순회할 루프 카운터로 j를 써서 매 루프당 text와 pattern로부터 문자를 한개씩 가져와 서로 비교한다:

        for (int j = 0; j < _pattern.length(); j++) {
            if (!KoreanCharApproxMatcher.isMatch(text.charAt(i + j), _pattern.charAt(j)))
                break;

            if (j == _pattern.length() - 1)
                return new KoreanTextMatch(this, text, i, _pattern.length());
        }

반면 함수형 프로그래밍 스타일의 F#에서는

            |> Seq.windowed pattern.Length
            |> Seq.tryFindIndex (fun subtext ->
                (subtext, pattern)
                ||> Seq.forall2 KoreanCharApproxMatcher.isMatch)

처럼 파이프라인 앞부분에서 [startIndex, startIndex + length) 구간으로 잘라낸 text를 pattern 길이 만큼씩의 윈도로 잘라내서 이 각각을 pattern과 비교한다. 이때 Seq.windowed 함수가 쓰였는데, 예를 들어 text가 "12345"이고 pattern이 "34"라면 이 함수는 text를 "12", "23", "34", "45"로 변환한다. 이 각각의 부분문자열은 모두 pattern과 길이가 같으므로 Seq.forall2 KoreanCharApproxMatcher.isMatch에 넣으면 두 문자열의 모든 원소가 KoreanCharApproxMatcher.isMatch를 만족시키는지 알 수 있다. 이 조건이 성립할 경우 외부의 Seq.tryFindIndex 함수가 해당 위치를 Some index 형태로 리턴한다. 만약 찾지 못하면 None을 리턴하므로 두 경우에 대해 최종 처리를 해주면 된다:

            |> function
               | Some index -> KoreanTextMatch(this, text, index, pattern.Length)
               | None -> KoreanTextMatch.Empty

함수형 프로그래밍의 단점

그런데 여기서 자연스럽게 떠오르는 의문은 저렇게 함수형 프로그래밍이 명령형 프로그래밍보다 쓰기 쉽고 읽기 쉬운 코드를 만드는데 기여한다면 왜 명령형 프로그래밍은 없어지지 않는가 하는 것이다. 사실 그 이유는 딱 한가지라고 볼 수 있는데, 함수형 프로그래밍으로 짜면 성능이 떨어지기 쉽다(아…). 실제로 위의 F# 코드는 Seq.windowed 함수가 text의 부분문자열을 다량 생성하기 때문에 text가 길어질 수록 가비지 컬렉터에 가해지는 부담이 비례해서 커진다. 반면 자바 코드는 루프 내에서 생성하는 오브젝트가 전혀 없기 때문에 성능상의 오버헤드가 없고, 그 결과 text의 길이가 길어질 수록 F# 버전보다 훨씬 빨라지게 된다.

이 문제를 해결할 방법이 없을까? 다음번에 .NET의 Span<T>와 Memory<T>를 다루면서 생각해보기로 하겠다. 오늘은 여기까지.