패턴 매칭

Pattern matching
이 기사는 기능 프로그래밍의 패턴 매칭에 관한 것입니다.그 외의 용도는, 문자열 매칭과 패턴 인식을 참조해 주세요.
일치시킬 추상 패턴을 정의할 때 변수 일치 기준을 사용하려면 정규 표현을 참조하십시오.

컴퓨터 과학에서 패턴 매칭은 주어진 일련의 토큰에 어떤 패턴의 성분이 존재하는지 확인하는 행위입니다.패턴 인식과는 달리, 일반적으로 "일치할 것인지 아닐 것인지"라는 정확한 일치가 필요합니다.패턴은 일반적으로 시퀀스 또는 트리 구조의 형태를 가집니다.패턴 매칭의 용도에는 토큰 시퀀스 내의 패턴 위치(있는 경우)를 출력하고 일치하는 패턴의 일부 컴포넌트를 출력하며 일치하는 패턴을 다른 토큰 시퀀스로 치환하는 것(검색 및 치환)이 포함된다.

시퀀스 패턴(예: 텍스트 문자열)은 종종 정규 표현을 사용하여 기술되고 역추적과 같은 기법을 사용하여 일치됩니다.

나무 패턴 몇개의 프로그램 언어로 된 일반적인 도구로 데이터 구조에 근거하여, 처리합니다. 사용된다 C#(F#,[2]Haskell,[3]맥스, Python,[4]Ruby,[5]Rust,[6]Scala,[7]Swift[8]고 상징적인 수학 언어 원리다 특별한 구문에 표현하는 나무 패턴과 언어 구성을 조건부로 실행과 va.루 교수 검색 나에 기초한t.

종종 하나씩 시도되는 대체 패턴을 제공할 수 있으며, 이는 강력한 조건부 프로그래밍 구성을 생성합니다.패턴 매칭에는 [citation needed]가드 지원이 포함될 수 있습니다.

역사

패턴 매칭 구조를 가진 초기 프로그래밍 언어로는 COMIT(1957), SNOBOL(1962), 트리 기반 패턴 매칭을 사용한 Refal(1968), Prolog(1972), SASL(1976), NPL(1977), KRC(1981) 등이 있습니다.

많은 텍스트 에디터는 다양한 종류의 패턴 매칭을 지원합니다.QED 에디터는 정규 표현 검색을 지원하며 TECO의 일부 버전은 검색에서 OR 연산자를 지원합니다.

컴퓨터 대수 시스템은 일반적으로 대수식에서의 [9]패턴 매칭을 지원한다.

다음 항목도 참조하십시오.정규 표현 history 이력

원시 패턴

패턴 매칭에서 가장 단순한 패턴은 명시적 값 또는 변수입니다.예를 들어, Haskell 구문에서 간단한 함수 정의를 고려합니다(함수 매개 변수는 괄호 안에 없지만 공백으로 구분되고 =는 할당이 아니라 정의임). 

f 0 = 1

여기서 0은 단일 값 패턴입니다.이제 f가 인수로0이 지정되면 패턴은 일치하고 함수는 1을 반환합니다.다른 인수를 사용하면 매칭이 실패하여 함수가 실패합니다.구문은 함수 정의에서 대체 패턴을 지원하므로 정의를 계속 확장하여 보다 일반적인 인수를 사용할 수 있습니다.

f n = n * f (n-1)

여기, 첫 번째n는 단일 변수 패턴으로, 모든 인수와 완전히 일치하며 정의의 나머지 부분에서 사용되는 이름n 에 바인드 합니다.Haskell에서는 (적어도 Hope와는 달리) 패턴이 순서대로 시행되므로 첫 번째 정의는 입력이 0인 매우 구체적인 경우에도 적용되지만 다른 인수에서는 함수가 반환됩니다.n * f (n-1)n을 인수로 합니다.

와일드카드 패턴(종종 다음과 같이 표기)_)도 간단합니다.변수명과 마찬가지로 임의의 값과 일치하지만 값을 임의의 이름으로 바인드하지 않습니다.단순한 문자열 일치 상황에서 와일드카드를 일치시키기 위한 알고리즘은 많은 재귀적 및 비재귀적 [10]변종에서 개발되었습니다.

트리 패턴

더 복잡한 패턴은 이전 섹션의 원시 패턴에서 작성할 수 있습니다.일반적으로 다른 값을 조합하여 값을 작성하는 것과 동일한 방식으로 작성할 수 있습니다.다른 점은 변수 및 와일드카드 부분의 경우 패턴이 단일 값으로 구축되지 않고 패턴 구조 내에서 변화하는 요소와 구체적인 요소의 조합인 값 그룹과 일치한다는 것입니다.

트리 패턴은 노드부터 시작하여 일부 브랜치 및 노드를 지정하고 일부는 변수 또는 와일드카드 패턴으로 지정하지 않음으로써 트리의 일부를 나타냅니다.프로그래밍 언어의 추상 구문 트리와 대수적 데이터 유형을 생각하는 것이 도움이 될 수 있습니다.

Haskell에서 다음 행은 대수 데이터 유형을 정의합니다.Color단일 데이터 생성자를 가지고 있습니다.ColorConstructor정수와 문자열을 감습니다. 

데이터. 색. = ColorConstructor 정수 스트링

생성자는 트리의 노드이며, 정수와 문자열은 분기에 있습니다.

우리가 만들 함수를 쓰고 싶을 때Color추상적인 데이터 타입, 우리는 데이터 타입과 인터페이스하기 위해 함수를 쓰고 싶다, 그래서 우리는 데이터 타입에서 일부 데이터를 추출하고 싶다, 예를 들어 문자열 또는 정수 부분Color.

Color 타입의 변수를 전달하면 이 변수에서 데이터를 꺼내려면 어떻게 해야 합니까?예를 들어, 함수가 정수 부분을 가져오려면Color단순한 트리 패턴을 사용하여 다음과 같이 쓸 수 있습니다.

정수 부품 (ColorConstructor 정수 _) = 정수

또, 다음과 같습니다.

string Part (string Part) (ColorConstructor _ 스트링) = 스트링

이러한 함수의 생성은 Haskell의 데이터 레코드 구문을 통해 자동화할 수 있습니다.

이 Ocaml 예에서는 red-black 트리와 요소 삽입 후 재조정하는 함수를 정의하고 있습니다.이 예에서는 재귀 데이터 타입에 의해 생성된 보다 복잡한 구조를 대조하는 방법을 보여 줍니다. 

유형 색. = 빨간.   블랙입니다. 유형 'a 트리 = 빈   트리 의 색. * 'a 트리 * 'a * 'a 트리  허락하다 밸런스를 하다 t = 경기 t 와 함께       트리 (블랙입니다., 트리 (빨간., 트리 (빨간., a, x, b), y, c), z, d)       트리 (블랙입니다., 트리 (빨간., a, x, 트리 (빨간., b, y, c)), z, d)                                         트리 (블랙입니다., a, x, 트리 (빨간., 트리 (빨간., b, y, c), z, d))       트리 (블랙입니다., a, x, 트리 (빨간., b, y, 트리 (빨간., c, z, d)))         ->  트리 (빨간., 트리 (블랙입니다., a, x, b), y, 트리 (블랙입니다., c, z, d))       _ -> t (* 이전 패턴과 일치하지 않는 경우 'syslog-all' 대소문자*)

패턴으로 데이터 필터링

패턴 매칭을 사용하여 특정 구조의 데이터를 필터링할 수 있습니다.예를 들어 Haskell에서는 다음과 같은 필터링에 목록 이해를 사용할 수 있습니다.

[A x A x <-> [A 1, B 1, A 2, B 2]]

까지 평가하다.

[A1, A2]

매스매티카의 패턴 매칭

매스매티카에서 존재하는 유일한 구조는 기호로 채워진 나무이다.지금까지 사용된 Haskell 구문에서는 다음과 같이 정의할 수 있습니다.

데이터. 심볼 트리 = 기호. 스트링 [심볼 트리]

예시 트리는 다음과 같이 보일 수 있습니다.

기호. "a" [기호. "b" [], 기호. "c" []]

전통적인 보다 적절한 구문에서는 기호를 그대로 쓰고 트리의 수준을 다음과 같이 표현합니다.[]예를 들어,a[b,c]는 a를 부모로 하고 b와 c를 자녀로 하는 트리입니다.

매스매티카의 패턴은 그 트리의 위치에 "_"를 넣는 것을 포함합니다.예를 들어 패턴은

A[_]

는 A[1], A[2], 또는 보다 일반적으로 A[x] 등의 요소와 일치합니다.x는 임의의 엔티티입니다.이 경우,A구체적인 요소인데 반해_는 변경할 수 있는 나무를 나타냅니다.앞에 붙는 기호_는 해당 변수 이름에 일치를 바인드하며, 기호는 에 부가됩니다._는 해당 기호의 노드로 일치를 제한합니다.빈칸 자체도 내부적으로는 다음과 같이 표시됩니다.Blank[]위해서_그리고.Blank[x]위해서_x.

매스매티카 함수Cases는 두 번째 [11]인수의 패턴과 일치하는 첫 번째 인수의 요소를 필터링합니다. 

경우들[{a[1], b[1], a[2], b[2]}, a[_] ]

까지 평가하다.

{a[1], a[2]}

패턴 매칭은 식 구조에 적용됩니다.다음 예에서는

경우들[ {a[b], a[b, c], a[b[c], d], a[b[c], d[e]], a[b[c], d, e]}, a[b[_], _] ]

돌아온다

{a[b[c],d], a[b[c],d[e]]}

왜냐하면 이 요소들만이 패턴과 일치하기 때문이다.a[b[_],_]위에.

매스매티카에서는 구조가 나타나는 방법과 장소에 관계없이 계산 과정에서 생성된 구조를 추출할 수도 있습니다.함수Trace는 계산을 감시하고 패턴과 일치하는 요소를 반환하는 데 사용할 수 있습니다.예를 들어 Fibonacci 시퀀스를 다음과 같이 정의할 수 있습니다.

파이브[0 1]:=1 파이브[n_]:= 파이브[n-1] + 파이브[n-2]

그런 다음 fib[3]를 지정하면 재귀적인 Fibonacci 콜의 시퀀스는 어떻게 됩니까? 

추적하다[파이브[3], 파이브[_]]

패턴의 발생을 나타내는 구조를 반환합니다.fib[_]계산 구조:

{파이브[3],{파이브[2],{파이브[1]},{파이브[0]}},{파이브[1]}}

선언적 프로그래밍

기호 프로그래밍 언어에서는 함수를 인수하거나 데이터 구조의 요소로 패턴을 갖는 것이 쉽습니다.그 결과 패턴을 사용하여 데이터 조각에 대해 선언적으로 진술하고 기능에게 조작 방법을 유연하게 지시할 수 있습니다.

예를 들어, 매스매티카 함수는Compile를 사용하여 보다 효율적인 버전의 코드를 만들 수 있습니다.다음 예제에서는 세부 사항은 특별히 중요하지 않습니다. 중요한 것은 하위 표현식이{{com[_], Integer}}지시하다Compile그 형식의 표현.com[_]컴파일 목적의 정수로 가정할 수 있습니다.

com[i_] := 이항[2i, i] 컴파일[{x, {i, _정수}}, x^com[i], {{com[_],  정수}}]

Erlang의 우편함도 이와 같이 동작합니다.

증명과 프로그램 간의 Curry-Howard 대응은 ML 스타일의 패턴 매칭과 사례 분석 및 소진에 의한 증명과 관련이 있습니다.

패턴 매칭 및 문자열

지금까지 패턴 매칭의 가장 일반적인 형태는 문자열 문자열입니다.많은 프로그래밍 언어에서 문자열의 특정 구문은 문자열 문자를 기술하는 패턴인 정규 표현을 나타내기 위해 사용됩니다.

단, 이 문서에서 설명한 것과 동일한 프레임워크 내에서 일부 문자열 패턴 매칭을 수행할 수 있습니다.

문자열의 트리 패턴

Mathematica에서 문자열은 루트 StringExpression의 트리로 표시되고 모든 문자는 루트의 자식 순서로 표시됩니다.따라서 "모든 양의 후행 문자"를 일치시키려면 단일 문자만 일치하는 것과 대조적으로 새로운 와일드카드 __가 필요합니다.

일반적으로 Haskell 및 기능 프로그래밍 언어에서 문자열은 기능적인 문자 목록으로 나타납니다.기능 목록은 빈 목록 또는 기존 목록에 구성된 요소로 정의됩니다.Haskell 구문:

[] -- 빈 리스트 x:xs -- 리스트 xs에 작성된 요소 xx

일부 요소를 포함하는 목록의 구조는 다음과 같습니다.element:list패턴을 일치시킬 때 특정 데이터가 특정 패턴과 동일하다고 주장합니다.예를 들어, 함수의 경우:

머리 (요소:목록.) = 요소

우리는 의 첫 번째 요소가head의 인수는 요소라고 불리며 함수는 이를 반환합니다.리스트가 정의되는 방법, 즉 리스트에 구성되는 단일 요소이기 때문에 이것이 첫 번째 요소라는 것을 알고 있습니다.이 단일 요소가 첫 번째 요소여야 합니다.빈 목록에는 머리(생성된 첫 번째 요소)가 없기 때문에 빈 목록은 패턴과 전혀 일치하지 않습니다.

이 예에서는, 다음과 같은 것은 사용할 수 없습니다.list이를 무시하고 함수를 쓸 수 있습니다.

머리 (요소:_) = 요소

등가 매스매티카 변환은 다음과 같이 표현된다.

head[facebook, ] : = head

문자열 패턴 예시

예를 들어 매스매티카에서는

String Expression ["a",_]

는, 2 문자의 문자열과 일치해, 「a」로 시작합니다.

Haskell에서도 같은 패턴:

['a', _]

심볼 엔티티는 문자열의 관련 기능의 다양한 클래스를 나타내기 위해 도입될 수 있습니다.예를 들어.

StringExpression [문자 문자, 숫자 문자]

는 먼저 문자로 구성된 문자열과 일치하고 다음으로 숫자로 구성됩니다.

하스켈에서도 같은 시합을 치르기 위해 가드를 사용할 수 있다.

[편지, 숫자]   알파 편지 & & 숫자 숫자

기호 문자열 조작의 주요 장점은 별도의 특수 목적 서브유닛이 아닌 나머지 프로그래밍 언어와 완전히 통합될 수 있다는 것입니다.언어의 모든 힘을 활용하여 패턴 자체를 구축하거나 패턴을 포함하는 프로그램을 분석하고 변형할 수 있습니다.

스누볼

주요 기사: SNOBOL

SNOBOL(StriNg 지향 및 심볼)BOLIC Language)는 1962년부터 1967년까지 AT&T Bell 연구소에서 David J. Farber, Ralph E. Griswold 및 Ivan P에 의해 개발된 컴퓨터 프로그래밍 언어입니다. 폴론스키.

SNOBOL4는 패턴을 퍼스트 클래스 데이터 타입(즉, 프로그래밍 언어의 다른 데이터 타입에 허용되는 모든 방법으로 값을 조작할 수 있는 데이터 타입)으로 하고 패턴 연결 및 변경을 위한 연산자를 제공함으로써 대부분의 프로그래밍 언어와 구별된다.실행 중에 생성된 문자열을 프로그램으로 처리하여 실행할 수 있습니다.

SNOBOL은 1960년대 후반과 1970년대 초반에 미국의 큰 대학에서 매우 널리 가르쳤고 1970년대와 1980년대에 인문학의 텍스트 조작 언어로 널리 사용되었다.

SNOBOL이 만들어진 이후, Awk와 Perl과 같은 새로운 언어들은 정규 표현을 통한 문자열 조작을 유행시켰다.단, SNOBOL4 패턴은 컨텍스트프리 문법과 동등하고 정규 표현보다 강력한 BNF 문법을 채택합니다.[12]

「 」를 참조해 주세요.

레퍼런스

  1. ^ "Pattern Matching - C# Guide".
  2. ^ "Pattern Matching - F# Guide".
  3. ^ 해스켈에 대한 부드러운 소개: 패턴
  4. ^ "What's New In Python 3.10 — Python 3.10.0b3 documentation". docs.python.org. Retrieved 2021-07-06.
  5. ^ "pattern_matching - Documentation for Ruby 3.0.0". docs.ruby-lang.org. Retrieved 2021-07-06.
  6. ^ "Pattern Syntax - The Rust Programming language".
  7. ^ "Pattern Matching". Scala Documentation. Retrieved 2021-01-17.
  8. ^ "Patterns — The Swift Programming Language (Swift 5.1)".
  9. ^ Joel Moses, "심볼릭 통합", MIT 프로젝트 MAC-TR-47, 1967년 12월
  10. ^ Cantatore, Alessandro (2003). "Wildcard matching algorithms".
  11. ^ "Cases—Wolfram Language Documentation". reference.wolfram.com. Retrieved 2020-11-17.
  12. ^ 짐펠, J. F. 1973년SNOBOL4에서의 이산 패턴과 그 실장 이론.커뮤니케이션.ACM 16, 2(1973년 2월), 91-100.DOI=http://doi.acm.org/10.1145/361952.361960.

외부 링크

Wikibook Haskell에는 패턴 매칭에 관한 페이지가 있습니다.
Wikimedia Commons에는 패턴 매칭과 관련된 미디어가 있습니다.