Loading article…
コンピュータサイエンスにおいて、パターンマッチングとは、与えられたトークンのシーケンスの中に、あるパターンの構成要素が存在するかどうかをチェックする行為です。パターン認識とは対照的に、パターンマッチングでは通常、一致が完全でなければなりません。「一致するか、一致しないかのどちらかです」。パターンは一般的に、シーケンスまたはツリー構造のいずれかの形式をとります。パターンマッチングの用途としては、トークンシーケンス内のパターンの位置（存在する場合）を出力すること、一致したパターンの構成要素を出力すること、一致したパターンを別のトークンシーケンスに置き換えること（つまり、検索と置換）などがあります。
シーケンスパターン（テキスト文字列など）は、正規表現を使用して記述され、バックトラッキングなどの手法を使用してマッチングされることが多い。
ツリーパターンは、 C# [ 1 ] F # [ 2 ] Haskell [ 3 ] Java [ 4 ] ML、Python [ 5 ] Racket [ 6 ] Ruby [ 7 ] Rust [ 8 ] Scala [ 9 ] Swift [ 10 ]などのプログラミング言語で、データの構造に基づいてデータを処理するための一般的なツールとして使用されています。また、記号数学言語Mathematica には、ツリーパターンを表現するための特別な構文と、それに基づいて条件付き実行と値取得を行うための言語構造があります。
多くの場合、代替パターンを1つずつ試すことが可能であり、これにより強力な条件付きプログラミング構造が得られます。パターンマッチングには、ガードのサポートが含まれる場合もあります。[ 11 ]
パターンマッチング構造を持つ初期のプログラミング言語には、COMIT (1957)、SNOBOL (1962) があり、SNOBOL はパターンマッチングを文字列やテキスト操作のためのコアとなる第一級の言語機能として導入しました。このパラダイムは、 Refal (1968)で構造化されたツリーベースのデータ評価へと発展し、Refal はパターンマッチングを使用して記号式を操作しました。この概念はすぐにProlog (1972)で論理プログラミングに適用され、パターンマッチングは論理クエリを解決するための構造的単一化の形をとりました。関数型プログラミング言語は、 1970 年代後半から 1980 年代前半にかけて、この機能を急速に採用し形式化しました。その始まりは、St Andrews Static Language (SASL) (1976)、NPL (1977)、Kent Recursive Calculator (KRC) (1981) です。[ 12 ]
ML (1973) 言語とその方言Standard ML (1983)の関数引数のパターン マッチング機能は、コンパイル時の網羅性チェックを高度に形式化しました。このアプローチは、 Haskell (1990)、Scala (2004)、F# (2005) など、影響を受けた他の関数型プログラミング言語にも引き継がれています。ML方言Camlmatch (1985)で導入されたキーワードによるパターン マッチング構造は、OCaml ( 1996)、F# (2005)、F* (2011)、Rust (2015)などの言語に引き継がれました。時が経つにつれ、マルチ パラダイム言語は代数的データ型とパターン マッチングをネイティブに実装し始め、 Python の構文 (2021) やJava のパターン マッチングの拡張 (2023)のような現代的な実装に至りました。 [ 13 ]match-case
多くのテキストエディタは、高度な検索と置換機能を容易にするために、さまざまな種類のパターンマッチングをサポートしています。ケン・トンプソンによって設計されたQEDエディタは、正規表現検索をサポートする先駆者でした。トンプソンによるQEDでの正規表現解析の実装は、ed、sed、grepのテキスト検索ユーティリティの基礎を築きました。さらに、TECOエディタのいくつかのバージョンは、検索における論理OR演算子を含む高度なマッチング機能をサポートしていました。[ 14 ]
コンピュータ代数システム(CAS) は一般的に、代数式のパターン マッチングをサポートし、記号の簡略化と統合を実現しています。Macsyma (1968) のような初期のシステムは、意味的パターン マッチングを使用して代数的等価性を認識していました。たとえば、その内部エンジンは、とを「x の二次式」パターン テンプレートの出現として正しくマッチングすることができました。Mathematicaや Maple などの現代のコンピュータ代数システムは、ユーザー式の変換、微分方程式の解析解の探索、ユーザー定義の簡略化フレームワークの構築にパターン マッチング ルールを多用しています。[ 15 ]3x2 + 4(x + 1)(x + 6)
パターンマッチングには専門的な用語が用いられる。
いくつかの概念は多くのパターン言語に比較的共通しているが、他のパターン言語には独自の、あるいは珍しい拡張機能が含まれている。
matchv{(a,b)=>...}vab..._ワイルドカードパターンは、構造を無視して値をさらに調べずにすべてを受け入れます。破棄、ワイルドパターン、キャッチオールパターン、または穴とも呼ばれます。(list(?even?)...)even?(==expr)expr123やなどの単純な原子データに一致するパターンは、リテラルパターン"hello"と呼ばれます。orパターン）パターンマッチングにおける最も単純なパターンは、明示的な値または変数です。例として、Haskell構文の単純な関数定義を考えてみましょう（関数パラメータは括弧ではなくスペースで区切られ、=は代入ではなく定義です）。
f 0 = 1ここで、0は単一の値パターンです。fに引数として0が与えられると、パターンが一致し、関数は1を返します。それ以外の引数では、一致せず、関数は失敗します。構文は関数定義で代替パターンをサポートしているため、定義を拡張してより一般的な引数を取るようにすることができます。
f n = n * f ( n - 1 )ここで、最初のnパターンは単一の変数パターンであり、あらゆる引数に完全に一致し、定義の残りの部分で使用する名前 n にバインドします。Haskell では (少なくともHopeとは異なり)、パターンは順番に試されるため、最初の定義は入力が 0 という非常に特殊なケースにも適用されますが、その他の引数の場合は、関数はn * f (n-1)引数 n を返します。
ワイルドカードパターン（多くの場合 と表記される_）も単純です。変数名と同様に、任意の値に一致しますが、値を特定の名前にバインドしません。単純な文字列マッチングの状況でワイルドカードをマッチングするためのアルゴリズムは、再帰的および非再帰的なさまざまな種類で開発されています。[ 19 ]
前のセクションで説明した基本的なパターンから、より複雑なパターンを構築できます。これは通常、値が他の値を組み合わせて構築されるのと同じ方法です。違いは、可変部分とワイルドカード部分がある場合、パターンは単一の値に構築されるのではなく、具体的な要素とパターンの構造内で変化が許容される要素の組み合わせである値のグループに一致するという点です。
ツリーパターンは、ノードから始めて、いくつかのブランチとノードを指定し、変数またはワイルドカードパターンを使用して一部を指定しないことで、ツリーの一部を記述します。プログラミング言語の抽象構文木と代数的データ型をイメージすると理解しやすいでしょう。
Haskellでは、次の行で、整数と文字列をラップするColor単一のデータコンストラクタを持つ代数的データ型を定義します。ColorConstructor
データColor = ColorConstructor Integer Stringコンストラクタはツリーのノードであり、整数と文字列はブランチの葉である。
抽象データ型を作成する関数を記述する場合、データ型とインターフェースする関数を記述したいので、データ型から何らかのデータ（たとえば、文字列部分だけ、または整数部分だけ）を抽出したいと考えます。ColorColor
Color型の変数を渡した場合、その変数からデータを取り出すにはどうすればよいでしょうか？たとえば、の整数部分を取得する関数ではColor、シンプルなツリーパターンを使用して次のように記述できます。
integerPart ( ColorConstructor theInteger _ ) = theInteger同じように：
stringPart ( ColorConstructor _ theString ) = theStringこれらの関数の作成は、Haskellのデータレコード構文によって自動化できる。
赤黒木と、要素挿入後にそのバランスを再調整する関数を定義するこのOCamlの例は、再帰的なデータ型によって生成されるより複雑な構造に対してマッチングを行う方法を示しています。コンパイラはコンパイル時に、ケースのリストが網羅的であり、冗長なケースがないことを検証します。
type color = Red | Black type ' a tree = Empty | Tree of color * ' a tree * ' a * ' a treelet rebalance t = match t with | Tree ( Black , Tree ( Red , Tree ( Red , a , x , b ), y , c ), z , d ) | Tree ( Black , Tree ( Red , a , x , Tree ( Red , b , y , c )), z , d ) | Tree ( Black , a , x , Tree ( Red , Tree ( Red , b , y , c ), z , d )) | Tree ( Black , a , x , Tree ( Red , b , y , Tree ( Red , c , z , d ))) -> Tree ( Red , Tree ( Black , a , x , b ), y , Tree ( Black , c , z , d )) | _ -> t (* 前のパターンが一致しない場合の「キャッチオール」ケース *)パターンマッチングは、特定の構造を持つデータをフィルタリングするために使用できます。例えば、Haskellでは、リスト内包表記をこの種のフィルタリングに使用できます。
[ A x | A x <- [ A 1 , B 1 , A 2 , B 2 ]]評価結果
[A 1、A 2]
Mathematicaでは、存在する唯一の構造はツリーであり、それはシンボルで満たされています。これまで使用してきたHaskell構文では、これは次のように定義できます。
データSymbolTree = Symbol String [ SymbolTree ]例としてツリーは次のようになります。
記号「a」[記号「b」[]、記号「c」[]]従来型のより適切な構文では、記号はそのまま記述され、ツリーのレベルは を使用して表現されます[]。たとえば、 はa[b,c]、親が a、子が b と c であるツリーです。
Mathematica のパターンは、そのツリー内の位置に「_」を挿入することによって定義されます。たとえば、次のパターン
A[_]
は、A[1]、A[2]、またはより一般的には A[ x ] のような要素に一致します。ここでxは任意のエンティティです。この場合、Aは具体的な要素であり、 は_変更可能なツリーの一部を表します。 の前にシンボルを付ける_とその変数名に一致をバインドし、 にシンボルを付けるとそのシンボルのノードに一致を制限します。なお、空白自体も内部的には の場合は、 の場合は_として表現されます。Blank[]_Blank[x]_x
Mathematica 関数は、Cases2 番目の引数のパターンに一致する最初の引数の要素をフィルタリングします。[ 20 ]
ケース[{ 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[_],_]。
Mathematicaでは、構造がどのように、どこに現れるかに関わらず、計算の過程で生成される構造を抽出することも可能である。この関数は計算を監視し、パターンに一致する要素を返すために使用できる。たとえば、フィボナッチ数列を次のようにTrace定義できる。
フィブ[ 0 | 1 ] := 1 fib [ n_ ] := fib [ n -1 ] + fib [ n -2 ]そこで、次のような質問をすることができます。fib[3] が与えられたとき、再帰的なフィボナッチ呼び出しのシーケンスは何ですか？
トレース[ fib [ 3 ]、fib [ _ ]]fib[_]計算構造におけるパターンの出現箇所を表す構造体を返します。
{ fib [ 3 ],{ fib [ 2 ],{ fib [ 1 ]},{ fib [ 0 ]}},{ fib [ 1 ]}}記号プログラミング言語では、パターンを関数の引数やデータ構造の要素として扱うことが容易です。その結果、パターンを用いてデータに関する宣言的な記述を行ったり、関数の動作を柔軟に指示したりすることが可能になります。
例えば、Mathematica の関数をCompile使用すると、より効率的なコードを作成できます。次の例では、詳細は特に重要ではありません。重要なのは、部分式が、コンパイルの目的で、次の形式の式を整数とみなすように{{com[_], Integer}}指示している点です。Compilecom[_]
com [ i_ ] := Binomial [ 2 i , i ] Compile [{ x , { i , _Integer }}, x ^ com [ i ], {{ com [ _ ], Integer }}]Erlangにおけるメールボックスも同様の仕組みで動作します。
パターンマッチングで最も一般的なのは、文字列を用いる方法です。多くのプログラミング言語では、文字列の特定の構文を用いて正規表現を表します。正規表現とは、文字列の文字を記述するパターンです。
しかし、この記事全体を通して説明してきたのと同じフレームワーク内で、文字列パターンマッチングを実行することは可能です。
Mathematicaでは、文字列はルートStringExpressionと、その子として順番に並んだすべての文字からなるツリーとして表現されます。したがって、「任意の数の末尾文字」に一致させるには、単一の文字にしか一致しない_とは対照的に、新しいワイルドカード___が必要になります。
Haskellや一般的な関数型プログラミング言語では、文字列は文字の関数リストとして表現されます。関数リストは、空のリスト、または既存のリスト上に構築された要素として定義されます。Haskellの構文では次のようになります。
[] -- 空のリストx : xs -- リスト xs 上に構築された要素 x要素を持つリストの構造は、次のようになりますelement:list。パターンマッチングでは、特定のデータが特定のパターンと等しいことを主張します。たとえば、次の関数では次のようになります。
ヘッド（要素：リスト）＝要素引数の最初の要素headは element と呼ばれ、関数はこの要素を返すことを断言します。リストの定義方法、つまりリスト上に構築される単一の要素から、これが最初の要素であることが分かります。この単一の要素が最初の要素でなければなりません。空のリストは先頭要素（最初に構築される要素）を持たないため、このパターンには全く一致しません。
この例では、 は不要なlistので無視して、次のように関数を記述します。
ヘッド（要素：_ ）＝要素同等のMathematica変換は次のように表されます。
head[element, ]:=element
例えば、Mathematicaでは、
StringExpression [ "a" , _ ]2文字で「a」で始まる文字列に一致します。
Haskellにおける同じパターン：
[ 'a' , _ ]記号エンティティを導入することで、文字列の関連する特徴のさまざまなクラスを表現できます。たとえば、
文字列式[文字、数字]
最初に文字、次に数字で構成される文字列に一致します。
Haskellでは、ガードを使って同様のマッチングを実現できます。
[文字、数字] | isAlpha文字&& isDigit数字記号文字列操作の主な利点は、独立した特殊機能ではなく、プログラミング言語の他の部分と完全に統合できる点です。言語の持つあらゆる機能を活用して、パターン自体を構築したり、パターンを含むプログラムを分析・変換したりすることができます。
SNOBOL（String Oriented and symBOlic Language ）は、1962年から1967年にかけてAT&Tベル研究所でDavid J. Farber、Ralph E. Griswold、Ivan P. Polonskyによって開発されたコンピュータプログラミング言語です。
SNOBOL4は、パターンを第一級データ型（つまり、プログラミング言語内の他のデータ型と同様に、その値をあらゆる方法で操作できるデータ型）として扱い、パターンの連結や選択のための演算子を提供する点で、ほとんどのプログラミング言語とは一線を画しています。実行中に生成された文字列はプログラムとして扱い、実行することができます。
SNOBOLは1960年代後半から1970年代前半にかけて、アメリカの大規模大学でかなり広く教えられており、1970年代から1980年代にかけては人文科学分野におけるテキスト操作言語として広く利用されていた。
SNOBOL の作成以来、 AWKやPerlなどの新しい言語では、正規表現による文字列操作が流行しています。しかし、SNOBOL4 パターンは、文脈自由文法と同等で正規表現よりも強力なバッカス・ナウア記法(BNF) 文法を包含しています。[ 21 ]
{{cite web}}引用には一般的なタイトルを使用します（ヘルプ）{{cite web}}:ヘルプ内の外部リンク|title=