パターンマッチング

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

コンピュータサイエンスではパターンマッチングは、特定のトークンシーケンスをチェックして、あるパターンの構成要素が存在するかどうかを確認する行為ですパターン認識とは対照的に、一致は通常、正確である必要があります。「一致するかどうかのどちらかです」。パターンは通常、シーケンスまたはツリー構造のいずれかの形式になります。パターンマッチングの使用には、トークンシーケンス内のパターンの位置(存在する場合)の出力、一致したパターンの一部のコンポーネントの出力、および一致するパターンを他のトークンシーケンスで置き換える(つまり、検索と置換)が含まれます。

シーケンスパターン(テキスト文字列など)は、正規表現を使用して記述され、バックトラッキングなどの手法を使用して照合されることがよくあります。

ツリーパターンは、その構造に基づいてデータを処理するための一般的なツールとして一部のプログラミング言語で使用されます。たとえば、 C#[1] F#[2] Haskell[3] MLPython[4] Ruby[5] Rust[6] Scala[7] Swift [8]およびシンボリック数学言語Mathematicaには、ツリーパターンを表現するための特別な構文と、それに基づく 条件付き実行および値検索のための言語構造があります。

多くの場合、1つずつ試行される代替パターンを指定することが可能であり、これにより強力な条件付きプログラミング構造が生成されます。パターンマッチングには、ガードのサポートが含まれる場合があります。[要出典]

構文解析アルゴリズムは、多くの場合、文字列を構文ツリーに変換するためにパターンマッチングに依存しています[9] [10]

歴史

パターンマッチング構造を備えた初期のプログラミング言語には、COMIT(1957)、SNOBOL(1962)、ツリーベースのパターンマッチングを備えたRefal (1968)、 Prolog(1972)、SASL(1976)、NPL(1977)、およびKRC(1981)が含まれます。

多くのテキストエディタは、さまざまな種類のパターンマッチングをサポートしています。QEDエディタ正規表現検索をサポートしており、 TECOの一部のバージョンは検索でOR演算子をサポートしています。

数式処理システムは、一般に代数式のパターンマッチングをサポートしています。[11]

プリミティブパターン

パターンマッチングで最も単純なパターンは、明示的な値または変数です。例として、Haskell構文の単純な関数定義を考えてみましょう(関数パラメーターは括弧内ではなくスペースで区切られています。=は代入ではなく定義です)。

f  0  =  1

ここで、0は単一値パターンです。ここで、引数としてfが0​​に指定されると、パターンは一致し、関数は1を返します。他の引数を使用すると、一致、つまり関数は失敗します。構文は関数定義の代替パターンをサポートしているため、定義を拡張して、より一般的な引数を取ることができます。

f  n  =  n  *  f  n --1 _

ここで、最初nのパターンは単一の変数パターンであり、すべての引数に完全に一致し、それを名前nにバインドして、残りの定義で使用します。Haskellでは(少なくともHopeとは異なり)、パターンが順番に試行されるため、入力が0の非常に特殊なケースでも最初の定義が適用されますが、他の引数の場合、関数はn * f (n-1)nを引数として返します。

ワイルドカードパターン(多くの場合、と記述されます_)も単純です。変数名と同様に、任意の値に一致しますが、値を任意の名前にバインドしません。単純な文字列照合状況でワイルドカードを照合するためのアルゴリズムは、多くの再帰的および非再帰的な種類で開発されています。[12]

ツリーパターン

通常、他の値を組み合わせて値を作成するのと同じ方法で、前のセクションの基本的なパターンからより複雑なパターンを作成できます。違いは、可変パーツとワイルドカードパーツでは、パターンが単一の値に組み込まれるのではなく、具体的な要素とパターンの構造内で変更できる要素の組み合わせである値のグループに一致することです。 。

ツリーパターンは、ノードから開始し、いくつかのブランチとノードを指定し、変数またはワイルドカードパターンで指定されていないものを残すことにより、ツリーの一部を記述します。プログラミング言語の抽象構文木代数的データ型を考えると役立つ場合があります

Haskellでは、次の行は、整数と文字列をラップする Color単一のデータコンストラクターを持つ代数的データ型を定義しています。ColorConstructor

data  Color  =  ColorConstructor 整数 文字列

コンストラクターはツリー内のノードであり、整数と文字列はブランチ内の葉です。

抽象データ型を作成する関数を記述したい場合、データ型とインターフェイスする関数を記述したいので、データ型からいくつかのデータを抽出したいのです。たとえば、文字列だけ、またはの整数部分だけです。ColorColor

Color型の変数を渡す場合、この変数からデータを取得するにはどうすればよいですか?たとえば、の整数部分を取得する関数のColor場合、単純なツリーパターンを使用して次のように記述できます。

integerPart  ColorConstructor  theInteger  _  =  theInteger

同じように:

stringPart  ColorConstructor  _  theString  =  theString

これらの関数の作成は、Haskellのデータレコード構文によって自動化できます。

赤黒木と要素挿入後にそれを再調整する関数を 定義するこのOcamlの例は、再帰データ型によって生成されたより複雑な構造に一致する方法を示しています。

タイプ  =  |  
タイプ 'ツリー=| * '* ' 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  (*前のパターンが一致しない場合は「catch-all」の場合*)

パターンによるデータのフィルタリング

パターンマッチングは、特定の構造のデータをフィルタリングするために使用できます。たとえば、Haskellでは、リスト内包表記をこの種のフィルタリングに使用できます。

[ A  x | A  x  <-  [ A  1  B  1  A  2  B  2 ]]

に評価します

[A 1、A 2]

Mathematicaでのパターンマッチング

Mathematicaでは、存在する唯一の構造はツリーであり、それはシンボルによって占められています。これまでに使用されたHaskell構文では、これは次のように定義できます。

データ SymbolTree  = シンボル 文字列 [ SymbolTree ]

その場合、ツリーの例は次のようになります。

記号「a」[記号「b」[]、記号「c」[]]       

従来のより適切な構文では、シンボルはそのまま記述され、ツリーのレベルはを使用して表さ[]れます。たとえばa[b,c]、aを親、bとcを子とするツリーです。

Mathematicaのパターンは、そのツリーの位置に「_」を置くことを含みます。たとえば、パターン

A [_]

A [1]、A [2]、またはより一般的にはA [ x ]などの要素に一致します。ここで、xは任意のエンティティです。この場合、Aは具体的な要素であり、_は変更可能な木の部分を示します。_一致をその変数名にバインドするために付加されたシンボル_と、そのシンボルのノードへの一致を制限するために付加されたシンボル。空白自体でさえ、内部的にBlank[]for_およびBlank[x]forとして表されることに注意してください_x

Mathematica関数Casesは、2番目の引数のパターンに一致する最初の引数の要素をフィルタリングします。[13]

ケース[{ 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を使用して、計算を監視し、パターンに一致する発生要素を返すことができます。たとえば、フィボナッチ数列を 次のように定義できます。

fib [ 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 _ ] :=二項式[ 2 i i ]   
コンパイル[{ x { i _Integer }}、x ^ com [ i ]、{{ com [ _ ]、Integer }}]      

Erlangのメールボックスもこのように機能します。

証明とプログラムの間カリーハワード対応は、 MLスタイルのパターンマッチングをケース分析および枯渇による証明に関連付けます。

パターンマッチングと文字列

パターンマッチングの最も一般的な形式には、文字列が含まれます。多くのプログラミング言語では、文字列の特定の構文を使用して、文字列文字を記述するパターンである正規表現を表します。

ただし、この記事全体で説明したのと同じフレームワーク内で文字列パターンマッチングを実行することは可能です。

文字列のツリーパターン

Mathematicaでは、文字列はルートStringExpressionのツリーとして表され、すべての文字はルートの子として順番に表されます。したがって、「任意の数の末尾の文字」と一致させるには、単一の文字のみと一致する_とは対照的に、新しいワイルドカード___が必要です。

Haskellおよび一般的な関数型プログラミング言語では、文字列は文字の機能リストとして表されます。機能リストは、空のリスト、または既存のリスト上に構築された要素として定義されます。Haskell構文の場合:

[]  -空のリスト
x : xs-リストxs 上に構築された要素x

したがって、いくつかの要素を含むリストの構造はelement:listです。パターンマッチングでは、特定のデータが特定のパターンに等しいと主張します。たとえば、関数では次のようになります。

ヘッド 要素リスト = 要素

引数の最初の要素はheadelementと呼ばれ、関数はこれを返すと主張します。リストの定義方法により、これが最初の要素であり、単一の要素がリスト上に構築されていることがわかります。この単一の要素が最初である必要があります。空のリストにはヘッド(最初に作成される要素)がないため、空のリストはパターンとまったく一致しません。

この例では、を使用しないためlist、無視して、次の関数を記述できます。

ヘッド 要素_  = 要素

同等の数学変換は次のように表されます。

head [element、]:= element

文字列パターンの例

たとえばMathematicaでは、

StringExpression ["a"、_]

2文字で、「a」で始まる文字列に一致します。

Haskellの同じパターン:

[ 'a'  _ ]

シンボリックエンティティを導入して、文字列の関連する機能のさまざまなクラスを表すことができます。例えば、

StringExpression [LetterCharacter、DigitCharacter]

最初に文字、次に数字で構成される文字列に一致します。

Haskellでは、ガードを使用して同じ一致を達成できます。

[文字 数字]  |  isAlpha 文字 &&  isDigit 数字

シンボリック文字列操作の主な利点は、個別の特別な目的のサブユニットではなく、残りのプログラミング言語と完全に統合できることです。言語の全能力を活用して、パターン自体を構築したり、パターンを含むプログラムを分析および変換したりできます。

SNOBOL

SNOBOL(StriNg Oriented and symBOlic Language)は、1962年から1967年にかけてAT&T ベル研究所David J. FarberRalph E. GriswoldIvan P.Polonskyによって開発されたコンピュータープログラミング言語です。

SNOBOL4は、ファーストクラスのデータ型つまり、プログラミング言語の他のデータ型で許可されているすべての方法で値を操作できるデータ型)としてパターンを持ち、パターンの連結交互変換の演算子を提供することで、ほとんどのプログラミング言語とは一線を画しています。 。実行中に生成された文字列は、プログラムとして扱い、実行することができます。

SNOBOLは、1960年代後半から1970年代初頭にかけて、米国の大規模な大学で非常に広く教えられ、1970年代と1980年代に人文科学のテキスト操作言語として広く使用されました。

SNOBOLの作成以来、 AwkPerlなどの新しい言語では、正規表現による文字列操作がファッショナブルになっています。ただし、SNOBOL4パターンには、BNF文法が含まれています。これは、文脈自由文法と同等であり、正規表現よりも強力です[14]

も参照してください

参考文献

  1. ^ 「パターンマッチング-C#ガイド」
  2. ^ 「パターンマッチング-F#ガイド」
  3. ^ Haskellの穏やかな紹介:パターン
  4. ^ 「Python3.10の新機能— Python3.10.0b3ドキュメント」docs.python.org 2021-07-06を取得
  5. ^ "pattern_matching-Ruby3.0.0のドキュメント。0"docs.ruby-lang.org 2021-07-06を取得
  6. ^ 「パターン構文-Rustプログラミング言語」
  7. ^ 「パターンマッチング」Scalaドキュメント2021年1月17日取得
  8. ^ 「パターン— Swiftプログラミング言語(Swift 5.1)」
  9. ^ ウォース、アレッサンドロ、イアンピウマルタ。 OMeta:パターンマッチングのためのオブジェクト指向言語。」動的言語に関する2007年のシンポジウムの議事録。ACM、2007年。
  10. ^ Knuth、Donald E.、James H. Morris、Jr、およびVaughanR.Pratt。「文字列での高速パターンマッチング。」コンピューティングに関するSIAMジャーナル6.2(1977):323-350。
  11. ^ Joel Moses、「記号積分」、MITプロジェクトMAC MAC-TR-47、1967年12月
  12. ^ Cantatore、Alessandro(2003)。「ワイルドカードマッチングアルゴリズム」
  13. ^ 「ケース—Wolfram言語ドキュメント」reference.wolfram.com 2020年11月17日取得
  14. ^ Gimpel、JF1973。離散パターンの理論とSNOBOL4でのそれらの実装。コミュン。ACM 16、2(1973年2月)、91〜100。DOI = http://doi.acm.org/10.1145/361952.361960

外部リンク