패턴 매칭과 알고리즘

함수형 프로그밍에서 패턴 매칭은 입력 데이터의 패턴을 인식하고 해당 패턴에 따라 실행 흐름을 결정하기 때문에 데이터의 구조와 상태에 따라 동작을 조절합니다. 일종의 switch문과 비슷한 역할을 한다고 볼 수 있는데, 패턴 매칭은 기본적인 정수를 비롯해서 다양한 형태의 데이터(튜플, 리스트 등)들을 패턴으로 간편하게 처리할 수 있습니다.

패턴 매칭은 항목 재작성 규칙(term rewriting rule)과 기술적으로는 다르지만 어느 부분에서는 비슷하다고 볼 수 있습니다. 이 재작성 규칙은 왼쪽 항과 오른쪽 항으로 구성되며, 왼쪽은 대체될 패턴을 나타내고 오른쪽은 그 패턴이 대체될 결과를 나타냅니다.

x + 0 -> x
x * 1 -> x

예를 들어, 위 규칙은 덧셈과 곱셈에서 항등원(Identity element)을 제거하는 역할을 합니다. 왼쪽에 있는 수식이 대체된 결과는 오른쪽의 x를 나타낸다고 볼 수 있고 이것이 재작성 규칙의 작동 방식입니다.

하지만 패턴 매칭은 주어진 데이터의 구조와 값이 특정 패턴과 일치하는지 확인하고 그에 따라 코드를 실행하는 더 단순화된 문제를 처리합니다. 패턴 매칭은 주어진 데이터의 구조와 값이 특정 패턴과 일치하는지만 단순히 확인하고 그에 따라 코드를 실행합니다[1]. 또한 텍스트 우선 체계(textual priority scheme)를 이용해 매칭된 규칙이 항상 고유하도록 합니다. 이는 패턴 매칭 규칙이 코드에서 나타나는 순서에 따라 적용되는 방식을 의미합니다.

head :: [a] -> a
head (x:_) = x
head [] = error "Empty list"

이 코드는 (x:_)와 [] 두 가지 패턴이 있습니다. (x:_) 패턴은 하나 이상의 요소를 가진 리스트에 매칭되며, 두 번째 패턴 []는 빈 리스트에 매칭됩니다.

패턴은 코드에 나타나는 순서대로 평가되기 때문에 첫 번째 패턴이 먼저 평가됩니다. 매칭에 실패하면 두 번째 패턴이 평가됩니다. 이러한 방식이 텍스트 우선 체계를 나타냅니다.

패턴 매칭을 수행하면서 컴파일러는 패턴 매칭을 매칭 오토마타(matching automata)라는 테스트로 변환합니다. 이 매칭 오토마타에는 주로 결정 트리(decision tree)와 백트래킹 오토마타(backtracking automata)와 같은 방식이 있습니다.

결정 트리

먼저 결정 트리에 대해 알아보겠습니다. 결정트리는 트리 기반 모델이며 각 노드에서 특정 조건을 테스트 하고 결과에 따라 다른 분기로 이동하는 구조를 가지고 패턴의 순서에 따라 트리를 구성합니다.

    [Root]
    /    \
[Node1] [Node2]
 /  \     /  \
[A] [B] [C] [D]

Root는 최상위 노드를, Node1과 Node2는 Root의 자식 노드를 나타내며 A, B, C, D는 각각 Node1과 Node2의 자식 노드를 나타냅니다. 각 노드에서 특정 조건을 테스트하고, 그 결과에 따라 다음 노드로 이동합니다.

Python을 이용해 결정 트리의 코드를 간단히 작성한다면 아래와 같습니다.

def match_pattern_decision_tree(pattern, data):
    if len(pattern) != len(data):
        return False

    for p, d in zip(pattern, data):
        if p != d and p != '_':
            return False

    return True

print(match_pattern_decision_tree(['A', 'B', '_'], ['A', 'B', 'C']))  # True
print(match_pattern_decision_tree(['A', 'B', '_'], ['A', 'B', 'D']))  # True
print(match_pattern_decision_tree(['A', 'B', 'C'], ['A', 'B', 'D']))  # False

패턴과 데이터를 zip()으로 묶은 후, 서로 맞는지 확인하는 간단한 동작을 합니다. 여기서 _ 는 와일드카드(wildcard)이며 모든 값에 일치하는 패턴입니다.

트리 구조 기반 알고리즘은 트리의 높이를 최소화 하는 것이 중요합니다. 높이는 트리의 루트 노드에서 임의의 리프(leaf) 노드 까지의 최대 경로의 길이와 같고, 일반적으로 시간 복잡도는 $O(h)$라 할 수 있습니다. 즉, 복잡한 패턴을 처리할 수록 트리의 높이와 복잡도는 커집니다. 또한 복잡해지는 만큼 필요한 노드의 수도 동일하게 증가하기 때문에 공간복잡도는 $O(n)$ 정도입니다. 따라서 결정트리는 복잡한 패턴을 처리할 때 시간과 비용을 많이 소모하게 됩니다.

Backtracking automata

백트래킹 오토마타는 정규표현식 매칭에서 주로 쓰이는 알고리즘입니다. 정확히는 비결정적 유한 오토마타(Non-deterministic Finite Automaton, NFA)라고 표현하는게 맞겠지만, 편의상 여기서는 백트래킹 오토마타라는 표현으로 퉁치겠습니다.

NFA 방식은 주어진 상태와 입력에 대해 여러 가지 가능한 상태 전이를 허용하기 때문에 패턴 매칭이 다양한 패턴을 동시에 고려할 수 있게 합니다. 예를 들어, 패턴이 "", "B", "C"으로 주어진 경우 “” 패턴에는 여러가지 경우에 대응할 수 있기 때문에 여러가지 매칭이 가능합니다. 이러한 특성 덕분에 패턴 매칭이 다양한 패턴을 고려할 수 있게됩니다.

  [S1] ---A--->  [S2] ---B---> [S3]
  ^  \                          /
   \--C------------------------/

S1, S2, S3는 각각 오토마타의 상태를 나타냅니다. 각 화살표는 상태 전이를 나타내며, 화살표 위의 문자는 해당 전이를 유도하는 입력을 나타냅니다.

매칭이 실패하면 이전 상태로 돌아가서 다른 경로를 탐색하는데 여기서 S3 부근이 매칭에 실패해 S1로 돌아간 후 다시 경로 C를 통해 S3로 이동하는 것을 볼 수 있습니다.

가능한 모든 경로를 탐색해야하기 때문에 불필요한 노드를 방문할 수 있고, 최악의 경우 $O(2^n)$이라는 시간복잡도를 가집니다. 하지만 다양한 상태와 상태 전이를 이용해 패턴을 찾아내기 때문에 결정 트리 방식 보다 복잡한 패턴에서는 더 유연하게 동작합니다. 또한 이 복잡도는 휴리스틱이나 memoziation과 같은 방식으로 충분히 개선할 수 있다고 봅니다.

Python으로 간단히 구현하면 다음과 같습니다.

def match_pattern_backtracking(pattern, data, index=0):
    if index == len(pattern):
        return True

    if index < len(data) and (pattern[index] == data[index] or pattern[index] == '_'):
        return match_pattern_backtracking(pattern, data, index + 1)

    return False

print(match_pattern_backtracking(['A', 'B', '_'], ['A', 'B', 'C']))  # True
print(match_pattern_backtracking(['_', 'B', '_'], ['A', 'B', 'D']))  # True
print(match_pattern_backtracking(['_', 'B', 'C'], ['A', 'B', 'D']))  # False

결정 트리와 코드는 비슷하지만, 재귀 호출을 통해 백트랙킹을 수행한다는 점에서 차이를 보입니다. 매개변수 index는 현재 어디까지 확인했는지 나타내는 역할을 합니다.

각주

[1] 패턴 매칭은 데이터 구조나 표현 식의 가장 바깥쪽 부분(예를 들어, 트리 구조에서 루트 부분)에서만 이뤄집니다. 즉, 데이터 구조와 표현식 내부에서는 매칭이 이뤄지지 않는다는 것을 의미합니다. 예를 들어 다음과 같은 코드가 있습니다.

case list of
  (x:_) -> print x          -- 첫 번째 요소를 출력
  [] -> print "Empty list"  -- 리스트가 비어있을 경우 출력

이 코드는 리스트의 상위 레벨인 첫 번째 요소에서만 패턴 매칭을 수행합니다. 리스트의 세부사항 $n$번째 요소나 중첩된 리스트의 경우는 이 코드만으로 처리되지 않습니다.

반면에 항목 재작성 규칙은 임의의 컨텍스트 $C[\space . \space]$ 에 대해 규칙 $(lhs, rhs)$을 적용해 $C[lhs] \rightarrow C[rhs]$과 같은 규칙을 적용합니다. 위에서 설명했듯, 왼쪽 항을 오른쪽의 항으로 바꾸는 것입니다.

이 임의의 컨텍스트에서는 데이터 구조의 어느 부분에서든지 이 규칙을 적용할 수 있습니다.

add([]) -> 0
add([hd | tl]) -> hd + add(tl)

예를 들어, 이 규칙은 재귀적으로 동작하면서 리스트의 모든 요소를 더합니다. 여기서 컨텍스트는 다음과 같습니다

1. 빈 리스트에 적용되는 컨텍스트. 빈 리스트를 0으로 재작성
2. 리스트의 첫번째 요소(hd)와 나머지 요소(tl)에 적용되는 컨텍스트. 리스트의 첫 번째 요소와 나머지 요소의 합을 계산하여 재작성

이와 같이, 재작성 규칙은 임의의 컨텍스트 내에서는 어느 부분이든 적용될 수 있으며, 이를 통해 데이터 구조의 내부적인 세부 사항까지 처리할 수 있습니다.

---

참고 자료

1. https://en.wikipedia.org/wiki/Rewriting
2. https://stackoverflow.com/a/7883554
3. Compiling Pattern Matching to Good Decision Trees (Luc Maranget)
4. 형식언어와 오토마타 (Peter Linz, 역: 김응모, 홍릉출판사, p.58)
5. https://cstheory.stackexchange.com/a/6266