왜 Swift는 함수형 언어로서 형편없을까

Source: Dev.to

소개

몇 달 전, 나는 끔찍한 대규모 정리해고의 많은 피해자 중 한 명이 되었습니다.
개인적인 문제—그 중에서도 COVID에 걸린 아버지를 돌보는 일—때문에 아직도 직장을 찾고 있습니다.

이 과정에서 나는 비교적 새롭게 다가온 추세, 즉 코딩 테스트의 증가를 목격했습니다. 학위 과정에서 자료구조와 알고리즘을 공부했지만, 그때가 언제였는지 인정하기가 쉽지 않을 정도로 오래됐습니다. 수년간 데이터를 데이터베이스에 저장하고 화면에 표시하기 위해 가져오는 일만 해왔기에 그 기술들이 날카롭게 유지되지는 않았습니다.

최근 몇 차례 면접에서 나는 인정하고 싶지 않을 정도로 자주 떨어졌습니다. 다행히도 친절한 팀 리드(네, 실제로 존재합니다)를 만나 내 퍼포먼스에 대한 귀중한 피드백을 받았습니다. 그의 조언 덕분에 앞으로의 면접에서 성공하기 위한 계획을 세웠습니다. 하지만 그것은 다음 포스트의 주제입니다.

---

문제

제가 마주한 코딩 문제 중 하나는 정수 배열에서 지역 최대값을 찾는 것이었습니다.

• 지역 최대값은 이웃보다 큰 값을 의미하며, 첫 번째와 마지막 요소는 각각 한쪽 이웃만 고려합니다.
• 입력 배열에는 추가 제약이 있었는데, 중복된 값이 존재하지 않는다는 점이었습니다.

이 문제를 올바르게 해결하기 위해 필요한 핵심 통찰은 (뇌의 일부가 심하게 녹슬어 스스로는 찾지 못했지만 약간의 도움을 받아 깨달은) 다음과 같습니다:

지역 최대값이 아닌 어떤 값을 선택하더라도, 현재 값보다 큰 이웃 쪽에서 반드시 지역 최대값을 찾을 수 있습니다.

예시

let values = [5, 15, 1, 6, 8, 9, 7]

중간 위치(6)를 선택하면, 이는 지역 최대값이 아닙니다. 왜냐하면 6 …

Int? {
    guard numbers.count > 1 else { return numbers.first }

    var left = 0
    var right = numbers.count - 1

    while left < right {
        let mid = (left + right) / 2

        if (mid == 0 || numbers[mid] > numbers[mid - 1]) &&
           (mid == numbers.count - 1 || numbers[mid] > numbers[mid + 1]) {
            return numbers[mid]
        }

        // If left neighbour is greater, search the left half
        if mid > 0 && numbers[mid - 1] > numbers[mid] {
            right = mid - 1
        } else {
            // Otherwise, search the right half
            left = mid + 1
        }
    }

    return nil
}

함수형 스칼라 솔루션

import scala.annotation.tailrec
import scala.collection.IndexedSeqView

def findAnyLocalMaxima(numbers: Array[Int]): Option[Int] =
  extension (numbers: IndexedSeqView[Int])
    def hasLocalMaximaAt(index: Int) =
      numbers(index) > numbers(index - 1) && numbers(index) > numbers(index + 1)

    def leftHalf = numbers.slice(0, numbers.length / 2)
    def rightHalf = numbers.slice(numbers.length / 2 + 1, numbers.length)

  @tailrec
  def findAnyLocalMaximaInView(numbers: IndexedSeqView[Int]): Option[Int] =
    numbers.length match
      case length if length > 2 =>
        val middleIndex = length / 2
        if numbers.hasLocalMaximaAt(middleIndex) then
          Some(numbers(middleIndex))
        else if numbers(middleIndex - 1) > numbers(middleIndex) then
          findAnyLocalMaximaInView(numbers.leftHalf)
        else
          findAnyLocalMaximaInView(numbers.rightHalf)

      case 2 => Some(math.max(numbers(0), numbers(1)))
      case 1 => Some(numbers(0))
      case 0 => None
  end findAnyLocalMaximaInView

  findAnyLocalMaximaInView(numbers.view)
end findAnyLocalMaxima

음, 인정합니다. 메인 코드를 더 읽기 쉽게 만들기 위해 확장을 좀 과하게 사용했네요.

Functional Programming Thoughts

함수형 프로그래밍은 referential transparency(참조 투명성)을 강조합니다 — 순수 함수를 사용할 경우 함수 호출을 그 결과값으로 교체해도 프로그램의 동작이 변하지 않는 능력입니다. 이는 문제를 더 작은 경우로 재작성하여 기본 사례에 도달하는 재귀적 접근과 일치합니다. 결과적으로 함수형 프로그래밍은 재귀 호출을 루프보다 선호하는데, 이렇게 하면 코드의 의도를 훨씬 더 명확하게 표현할 수 있습니다.

위의 함수형 코드를 살펴보면 알고리즘의 의도가 매우 명확합니다:

1. 중간 값이 지역 최대값인지 확인합니다.
2. 그렇지 않다면, 적절한 절반으로 재귀합니다.

그 의도는 부수 효과에 의존해 인덱스를 조정하여 관심 있는 데이터를 검사하는 명령형 버전에서는 완전히 사라집니다. 논리를 설명하는 주석까지 필요하게 됩니다!

Swift에서 완전 함수형으로 가는 문제

두 단어로 말하면: 스택 오버플로우!

아마도 한 번쯤은 스택 오버플로우 예외를 경험했을 것입니다. 이는 새로운 함수를 호출할 때마다 해당 호출에 대한 정보를 담은 프레임을 스택에 푸시하기 때문입니다. 따라서 분할‑정복 알고리즘을 순진하게 재귀적으로 구현하면 큰 입력에 대해 스택이 넘칠 수 있지만, Swift의 반복 버전은 스택 제한 내에서 안전하게 동작합니다.

결론

두 솔루션은 동일한 문제를 해결하지만, 고전적인 트레이드오프를 보여줍니다:

함수형 언어에서 스택 오버플로가 절대 발생하지 않는 솔루션이 필요하다면, 언제든 명시적 스택이나 꼬리 재귀 최적화(컴파일러가 지원하는 경우)를 사용할 수 있습니다. 반대로, 재귀의 우아함을 선호하고 입력이 그리 크지 않다면, 함수형 버전은 알고리즘의 핵심 통찰을 아름답게 보여줍니다.

Stack Overflow와 Tail‑Call 최적화

함수가 자신을 재귀적으로 호출하면, 각 호출마다 새로운 스택 프레임이 필요합니다.
너무 많은 호출을 중첩하면 스택 공간이 부족해 stack overflow 예외가 발생합니다.

Scala가 이 문제를 겪지 않는 이유

Scala는 이 점에서 “진정한” 함수형 언어입니다.
함수형 프로그래밍은 루프보다 재귀에 크게 의존하므로 tail‑call 최적화 (TCO) 가 필수입니다.

• TCO를 사용하면 함수의 마지막 연산이 자신에 대한 호출일 때, 현재 스택 프레임을 재사용하여 새 프레임을 만들지 않습니다.
• @tailrec 어노테이션(findAnyLocalMaximaInView 참고)은 Scala 컴파일러에게 이 최적화를 적용하도록 지시하며, 스택 오버플로우 위험 없이 잠재적으로 무한한 재귀 호출을 허용합니다.

Swift와 Tail Call

Swift는 때때로 tail call을 최적화하지만, 보장되지 않습니다.

• 디버그 빌드(-Onone)에서는 TCO가 종종 생략되어 스택 오버플로우가 발생합니다.
• 최적화 플래그 -Osize 혹은 -O를 사용하더라도 tail call이 최적화된다는 보장은 없습니다.
  • Swift 문서의 Writing High‑Performance Swift Code 기사에서는 TCO를 언급하지 않습니다.
  • Scala의 @tailrec를 참조한 오래된 Swift Forum 제안도 구현 없이 종료되었습니다.

핵심: Swift에서 tail recursion을 사용하는 것은 도박과 같습니다—때로는 동작하지만, 때로는 그렇지 않습니다. 이를 신뢰한다면 위험을 감수하는 것입니다.

Space‑Complexity Concerns

Coding tests evaluate both time and space complexity:

• How much extra space does your algorithm need?
• How does that space grow with the input size? (constant, linear, logarithmic, quadratic?)

If a functional approach uses excessive extra space, it may be less attractive than an imperative, mutable solution.

Immutability and Intermediate Structures

Functional programming typically works with immutable data structures, transforming them through pipelines.
Each transformation can create intermediate structures that are discarded after use.

For divide‑and‑conquer recursion:

1. The input is split into roughly half‑size chunks until a base case is reached.
2. The solution is then built back up from the bottom.

If we naïvely allocate a new array for each split, the total extra space becomes O(n) (linear in the input size).

Source: …

Scala와 Swift가 과도한 할당을 피하는 방법

Swift – ArraySlice

Swift의 Array 연산인 prefix(_:)이나 Range를 이용한 서브스크립트는 ArraySlice(또는 Slice)를 반환합니다.
이들은 원본 컬렉션을 감싸는 뷰입니다:

• 요소에 대해 추가 메모리가 할당되지 않습니다.
• 접근 시간과 공간 복잡도가 O(1) 입니다.

Scala – Views

Scala는 views를 통해 유사한 메커니즘을 제공합니다:

val view = numbers.view   // creates a view over the underlying collection

• 뷰에 대한 연산(예: IndexedSeqView)은 새로운 구조를 할당하지 않고 수행됩니다.
• 이러한 뷰를 무한히 슬라이스해도 공간 복잡도는 O(1) 을 유지합니다.

TL;DR

• 제목은 클릭베이트일 수 있지만, 논의는 Swift가 여전히 “진정한” 함수형 언어로서 뒤처진다는 점을 강조합니다.
• 여기까지 읽었다면, 아마도 함수형 접근 방식에 동의할 것입니다:
  • 알고리즘을 더 명확하게 표현한다, 또는
  • Swift의 꼬리 재귀 최적화가 신뢰할 수 없음을 보여준다.

핵심 정리

1. Scala: @tailrec + 보장된 TCO → 안전한 재귀 알고리즘.
2. Swift: 꼬리 호출 최적화는 선택 사항 → 주의해서 사용하세요.
3. 두 언어 모두 제로 복사 뷰 (ArraySlice / view)를 제공하여 공간 복잡도를 선형 또는 그 이하로 유지합니다.

Swift의 꼬리 재귀 최적화에 대해 더 알고 있다면, 댓글을 남겨 주세요—궁금합니다!