Párování vzorů - Pattern matching

Tento článek je o porovnávání vzorů ve funkčním programování . Pro další použití viz shoda řetězců a rozpoznávání vzorů .
Informace o použití kritérií shody proměnných při definování abstraktních vzorů, které mají odpovídat, najdete v regulárním výrazu .

Ve vědě o počítačích , vyhledávání vzorů je akt kontroly dané sekvenci z žetonů na přítomnost složek nějakého vzoru . Na rozdíl od rozpoznávání vzorů musí být shoda obvykle přesná: „buď to bude, nebo nebude shoda.“ Vzory mají obecně formu sekvencí nebo stromových struktur . Použití shody vzorů zahrnuje výstup umístění umístění (pokud existuje) vzoru v sekvenci tokenů, k výstupu některé komponenty spárovaného vzoru a k nahrazení shody vzoru za nějakou jinou sekvenci tokenů (tj. Hledání a nahrazení ).

Sekvenční vzory (např. Textový řetězec) jsou často popisovány pomocí regulárních výrazů a porovnávány pomocí technik, jako je zpětné sledování .

Stromové vzory se používají v některých programovacích jazycích jako obecný nástroj pro zpracování dat na základě jejich struktury, např. C # , F # , Haskell , ML , Python , Ruby , Rust , Scala , Swift a symbolický matematický jazyk Mathematica mají speciální syntaxi pro vyjádření stromu vzory a jazykový konstrukt pro podmíněné provádění a načítání hodnot na základě toho.

Často je možné dát alternativní vzory, které jsou zkoušeny jeden po druhém, což vede ke konstrukci výkonného podmíněného programování . Párování vzorů někdy zahrnuje podporu stráží .

Parsovací algoritmy se často při transformaci řetězců na syntaxové stromy spoléhají na porovnávání vzorů .

Dějiny

Mezi rané programovací jazyky s konstrukty shody vzorů patří COMIT (1957), SNOBOL (1962), Refal (1968) se stromovým porovnáváním vzorů, Prolog (1972), SASL (1976), NPL (1977) a KRC (1981).

Mnoho textových editorů podporuje porovnávání vzorů různých druhů: editor QED podporuje vyhledávání regulárních výrazů a některé verze TECO podporují při vyhledávání operátor OR.

Systémy počítačové algebry obecně podporují shodu vzorů na algebraických výrazech.

Viz také: Regulární výraz § Historie

Primitivní vzory

Nejjednodušší vzor při porovnávání vzorů je explicitní hodnota nebo proměnná. Uvažujme například o jednoduché definici funkce v Haskellově syntaxi (parametry funkce nejsou v závorkách, ale jsou odděleny mezerami, = není přiřazení, ale definice): 

f 0 = 1

Zde 0 je vzor jedné hodnoty. Nyní, kdykoli je f zadáno 0 jako argument, vzor se shoduje a funkce vrací 1. U jakéhokoli jiného argumentu selže shoda a tím i funkce. Protože syntaxe podporuje alternativní vzory v definicích funkcí, můžeme v definici pokračovat a rozšířit ji tak, aby převzala obecnější argumenty: 

f n = n * f (n-1)

Tady je první njediný variabilní vzor, ​​který bude odpovídat absolutně jakémukoli argumentu a sváže ho s názvem n, který bude použit ve zbytku definice. V Haskellu (na rozdíl od přinejmenším Hope ) jsou vzory zkoušeny v pořadí, takže první definice stále platí ve velmi specifickém případě vstupu, který je 0, zatímco pro jakýkoli jiný argument se funkce vrací, n * f (n-1)přičemž n je argument.

Vzor zástupných znaků (často psaný jako _) je také jednoduchý: stejně jako název proměnné odpovídá libovolné hodnotě, ale neváže hodnotu k žádnému jménu. Algoritmy pro porovnávání zástupných znaků v jednoduchých situacích shody řetězců byly vyvinuty v řadě rekurzivních a nerekurzivních odrůd.

Stromové vzory

Složitější vzory lze sestavit z primitivních vzorů z předchozí části, obvykle stejným způsobem, jako se vytvářejí hodnoty kombinací jiných hodnot. Rozdíl pak spočívá v tom, že u variabilních a zástupných částí se vzor nestaví do jedné hodnoty, ale odpovídá skupině hodnot, které jsou kombinací konkrétních prvků a prvků, které se mohou ve struktuře vzoru lišit .

Vzor stromu popisuje část stromu tak, že začíná uzlem a určuje některé větve a uzly a některé ponechává nespecifikované proměnným nebo zástupným vzorem. Může pomoci přemýšlet o abstraktním stromu syntaxe programovacího jazyka a algebraických datových typech .

V Haskellu následující řádek definuje algebraický datový typ, Colorkterý má jediný datový konstruktor, ColorConstructorkterý zabalí celé číslo a řetězec. 

data Color = ColorConstructor Integer String

Konstruktor je uzel ve stromu a celé číslo a řetězec jsou listy ve větvích.

Když chceme zapisovat funkce pro Colorvytvoření abstraktního datového typu , chceme zapsat funkce pro rozhraní s datovým typem, a proto chceme z datového typu extrahovat některá data, například pouze řetězec nebo celočíselnou část Color.

Pokud předáme proměnnou typu Color, jak můžeme z této proměnné dostat data? Například pro funkci, která získá celočíselnou část Color, můžeme použít jednoduchý stromový vzor a napsat: 

integerPart (ColorConstructor theInteger _) = theInteger

Také: 

stringPart (ColorConstructor _ theString) = theString

Vytváření těchto funkcí lze automatizovat pomocí syntaxe datových záznamů Haskella .

Tento příklad Ocaml, který definuje červeno-černý strom a funkci pro jeho opětovné vyvážení po vložení prvku, ukazuje, jak se shodovat ve složitější struktuře generované rekurzivním datovým typem. 

type color = Red | Black
type 'a tree = Empty | Tree of color * 'a tree * 'a * 'a tree

let 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 (* the 'catch-all' case if no previous pattern matches *)

Filtrování dat se vzory

K filtrování dat určité struktury lze použít porovnávání vzorů. Například v Haskellu lze pro tento druh filtrování použít porozumění seznamu : 

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

hodnotí na 

[A 1, A 2]

Párování vzorů v Mathematice

V Mathematice je jedinou strukturou strom , který je vyplněn symboly. V dosud používané syntaxi Haskell to lze definovat jako 

data SymbolTree = Symbol String [SymbolTree]

Příklad stromu by pak mohl vypadat 

Symbol "a" [Symbol "b" [], Symbol "c" []]

V tradiční, vhodnější syntaxi jsou symboly psány tak, jak jsou, a úrovně stromu jsou reprezentovány pomocí [], takže například a[b,c]je to strom s a jako rodič a b a c jako děti.

Vzor v Mathematice zahrnuje uvedení „_“ na pozice v tomto stromu. Například vzor 

A[_]

bude odpovídat prvkům jako A [1], A [2] nebo obecněji A [ x ], kde x je libovolná entita. V tomto případě Aje betonový prvek, zatímco _označuje kus stromu, který lze měnit. Symbol přidaný k _navázání shody na název proměnné, zatímco symbol připojený k _omezení shody na uzly tohoto symbolu. Všimněte si, že i samotné mezery jsou interně reprezentovány jako Blank[]pro _a Blank[x]pro _x.

Funkce Mathematica Casesfiltruje prvky prvního argumentu, které odpovídají vzoru v druhém argumentu: 

Cases[{a[1], b[1], a[2], b[2]}, a[_] ]

hodnotí na 

{a[1], a[2]}

Porovnávání vzorů se vztahuje na strukturu výrazů. V níže uvedeném příkladu 

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

se vrací 

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

protože pouze tyto prvky budou odpovídat a[b[_],_]výše uvedenému vzoru .

V Mathematice je také možné extrahovat struktury, které jsou vytvářeny v průběhu výpočtu, bez ohledu na to, jak a kde se objevují. Tuto funkci Tracelze použít k monitorování výpočtu a vrácení vznikajících prvků, které odpovídají vzoru. Například můžeme definovat Fibonacciho sekvenci jako 

fib[0|1]:=1
fib[n_]:= fib[n-1] + fib[n-2]

Potom si můžeme položit otázku: Jaká je posloupnost rekurzivních Fibonacciho volání vzhledem k fib [3]? 

Trace[fib[3], fib[_]]

vrací strukturu, která představuje výskyty vzoru fib[_]ve výpočetní struktuře: 

{fib[3],{fib[2],{fib[1]},{fib[0]}},{fib[1]}}

Deklarativní programování

V symbolických programovacích jazycích je snadné mít vzory jako argumenty k funkcím nebo jako prvky datových struktur. Důsledkem toho je schopnost používat vzory k deklarativním výrokům o částech dat a flexibilně instruovat funkce, jak pracovat.

Například funkci MathematicaCompile lze použít k vytvoření efektivnějších verzí kódu. V následujícím příkladu na detailech zvlášť nezáleží; důležité je, že subexpression {{com[_], Integer}}instruuje, Compileže výrazy formuláře com[_]lze pro účely kompilace považovat za celá čísla : 

com[i_] := Binomial[2i, i]
Compile[{x, {i, _Integer}}, x^com[i], {{com[_],  Integer}}]

Poštovní schránky v Erlangu také fungují tímto způsobem.

Curry-Howard korespondence mezi důkazy a programy se týká ML -styl porovnávání vzorků na analýzu případu a doklad o vyčerpání .

Párování vzorů a řetězce

Zdaleka nejběžnější forma porovnávání vzorů zahrnuje řetězce znaků. V mnoha programovacích jazycích se určitá syntaxe řetězců používá k reprezentaci regulárních výrazů, což jsou vzory popisující znaky řetězců.

Je však možné provést párování řetězcových vzorů ve stejném rámci, o kterém se hovoří v tomto článku.

Stromové vzory pro řetězce

V Mathematice jsou řetězce reprezentovány jako stromy root StringExpression a všechny znaky v pořadí jako podřízené kořeny. Pro shodu s „libovolným množstvím koncových znaků“ je tedy potřeba nový zástupný znak ___ na rozdíl od _, který by odpovídal pouze jednomu znaku.

V Haskellu a funkčních programovacích jazycích obecně jsou řetězce reprezentovány jako funkční seznamy znaků. Funkční seznam je definován jako prázdný seznam nebo prvek vytvořený na existujícím seznamu. V syntaxi Haskell: 

[] -- an empty list
x:xs -- an element x constructed on a list xs

Struktura seznamu s některými prvky je tedy element:list. Při porovnávání vzorů tvrdíme, že určitá část dat se rovná určitému vzoru. Například ve funkci: 

head (element:list) = element

Tvrdíme, že první prvek headargumentu se nazývá element a funkce to vrátí. Víme, že se jedná o první prvek z důvodu způsobu, jakým jsou seznamy definovány, jediný prvek zkonstruovaný do seznamu. Tento jediný prvek musí být první. Prázdný seznam by vůbec neodpovídal vzoru, protože prázdný seznam nemá hlavu (první vytvořený prvek).

V příkladu nemáme použití list, takže jej můžeme ignorovat, a tak napsat funkci: 

head (element:_) = element

Ekvivalentní transformace Mathematica je vyjádřena jako 

head[element, ]:=element

Ukázkové vzory řetězců

Například v Mathematice 

StringExpression["a",_]

bude odpovídat řetězci, který má dva znaky a začíná na „a“.

Stejný vzor v Haskellu: 

['a', _]

Lze zavést symbolické entity, které představují mnoho různých tříd příslušných funkcí řetězce. Například, 

StringExpression[LetterCharacter, DigitCharacter]

bude odpovídat řetězci, který se skládá nejprve z písmene a poté z čísla.

V Haskellu bylo možné použít stráže k dosažení stejných zápasů: 

[letter, digit] | isAlpha letter && isDigit digit

Hlavní výhodou manipulace se symbolickými řetězci je, že ji lze zcela integrovat do zbytku programovacího jazyka, místo aby byla samostatnou podjednotkou pro zvláštní účely. Celá síla jazyka může být využita k vytvoření samotných vzorců nebo k analýze a transformaci programů, které je obsahují.

SNOBOL

Hlavní článek: SNOBOL

Snobol ( String orientovaná a symbolického jazyka ) je programovací jazyk vyvinutý mezi 1962 a 1967 u AT & T Bell Laboratories od David J. Farber , Ralph E. Griswold a Ivan P. Polonsky .

SNOBOL4 stojí na rozdíl od většiny programovacích jazyků tím, že má vzory jako prvotřídní datový typ ( tj . Datový typ, s jehož hodnotami lze manipulovat všemi způsoby povolenými pro jakýkoli jiný datový typ v programovacím jazyce) a poskytuje operátorům zřetězení a střídání vzorů . Řetězce generované během provádění lze považovat za programy a spustit.

Koncem 60. a začátkem 70. let byl SNOBOL poměrně široce vyučován na větších amerických univerzitách a v 70. a 80. letech byl široce používán jako jazyk manipulace s textem v humanitních oborech .

Od vytvoření SNOBOLu novější jazyky jako Awk a Perl učinily módní manipulaci s řetězci pomocí regulárních výrazů . Vzory SNOBOL4 však zahrnují gramatiky BNF , které jsou ekvivalentní bezkontextovým gramatikám a výkonnější než regulární výrazy .

Viz také

Reference

externí odkazy