Сопоставление с образцом - Pattern matching

Эта статья посвящена сопоставлению с образцом в функциональном программировании . Чтобы узнать о других значениях, см. Сопоставление строк и распознавание образов .
Для использования критериев сопоставления переменных при определении сопоставимых абстрактных шаблонов см. Регулярное выражение .

В информатике , сопоставление с образцом является актом проверки заданной последовательности из маркеров на наличие составляющих некоторого рисунка . В отличие от распознавания образов , совпадение обычно должно быть точным: «либо совпадение будет, либо нет». Шаблоны обычно имеют форму последовательностей или древовидных структур . Использование сопоставления с образцом включает вывод местоположений (если они есть) образца в последовательности маркеров, вывод некоторого компонента сопоставленного образца и замену сопоставленного образца некоторой другой последовательностью маркеров (т. Е. Поиск и замена ).

Шаблоны последовательности (например, текстовая строка) часто описываются с помощью регулярных выражений и сопоставляются с использованием таких методов, как поиск с возвратом .

Шаблоны дерева используются в некоторых языках программирования в качестве общего инструмента для обработки данных на основе их структуры, например, C # , F # , Haskell , ML , Python , Ruby , Rust , Scala , Swift и язык символьной математики Mathematica имеют специальный синтаксис для выражения дерева. шаблоны и языковая конструкция для условного выполнения и поиска значений на его основе.

Часто можно предложить альтернативные шаблоны, которые проверяются один за другим, что дает мощную конструкцию условного программирования . Сопоставление с образцом иногда включает поддержку охранников .

Алгоритмы синтаксического анализа часто полагаются на сопоставление с образцом для преобразования строк в синтаксические деревья .

История

Ранние языки программирования с конструкциями сопоставления с образцом включают COMIT (1957), SNOBOL (1962), Refal (1968) с сопоставлением с образцом на основе дерева, Prolog (1972), SASL (1976), NPL (1977) и KRC (1981).

Многие текстовые редакторы поддерживают различные виды сопоставления с образцом: редактор QED поддерживает поиск по регулярным выражениям , а некоторые версии TECO поддерживают при поиске оператор 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.

Шаблон подстановки (часто _обозначаемый как ) также прост: как и имя переменной, он соответствует любому значению, но не связывает это значение с каким-либо именем. Алгоритмы сопоставления подстановочных знаков в простых ситуациях сопоставления строк были разработаны в ряде рекурсивных и нерекурсивных разновидностей.

Образцы деревьев

Более сложные шаблоны могут быть построены из примитивных шаблонов предыдущего раздела, обычно таким же образом, как значения создаются путем комбинирования других значений. Разница в том, что с частями переменных и подстановочных знаков шаблон не встраивается в одно значение, а соответствует группе значений, которые представляют собой комбинацию конкретных элементов и элементов, которым разрешено варьироваться в структуре шаблона. .

Шаблон дерева описывает часть дерева, начиная с узла и указывая некоторые ветви и узлы и оставляя некоторые неопределенными с помощью шаблона переменной или подстановочного знака. Можно подумать об абстрактном синтаксическом дереве языка программирования и алгебраических типах данных .

В Haskell следующая строка определяет алгебраический тип данных, Colorкоторый имеет единственный конструктор данных ColorConstructor, заключающий в себе целое число и строку. 

data Color = ColorConstructor Integer String

Конструктор - это узел в дереве, а целое число и строка - это листья в ветвях.

Когда мы хотим писать функции , чтобы сделать Colorв абстрактный тип данных , мы хотим функции записи для взаимодействия с типом данных, и , таким образом , мы хотим , чтобы извлечь некоторые данные из типа данных, например, только строки или только целую часть Color.

Если мы передадим переменную типа 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 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 *)

Фильтрация данных с помощью шаблонов

Сопоставление с образцом можно использовать для фильтрации данных определенной структуры. Например, в Haskell для такой фильтрации можно использовать понимание списка : 

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

оценивает 

[A 1, A 2]

Сопоставление с образцом в системе Mathematica

В системе Mathematica единственная существующая структура - это дерево , заполненное символами. В синтаксисе Haskell, который использовался до сих пор, это можно было бы определить как 

data SymbolTree = Symbol String [SymbolTree]

Тогда примерное дерево может выглядеть как 

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

В традиционном, более подходящем синтаксисе символы записываются как есть, а уровни дерева представлены с использованием [], так что, например a[b,c], это дерево с a в качестве родителя, а b и c в качестве дочерних.

Шаблон в системе Mathematica включает в себя размещение символа "_" в позициях в этом дереве. Например, узор 

A[_]

будет соответствовать таким элементам, как A [1], A [2] или, в более общем смысле, A [ x ], где x - любая сущность. В данном случае Aэто конкретный элемент, а _обозначает кусок дерева, который можно изменять. Символ, добавленный в начале, _связывает совпадение с этим именем переменной, в то время как добавленный символ _ограничивает совпадения узлами этого символа. Обратите внимание, что даже сами пробелы внутри представлены как Blank[]для _и Blank[x]для _x.

Функция Mathematica Casesфильтрует элементы первого аргумента, которые соответствуют шаблону во втором аргументе: 

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

оценивает 

{a[1], a[2]}

Сопоставление с образцом применяется к структуре выражений. В приведенном ниже примере 

Cases[ {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]? 

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

возвращает структуру, которая представляет вхождения шаблона fib[_]в вычислительную структуру: 

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

Декларативное программирование

В языках символьного программирования легко использовать шаблоны в качестве аргументов функций или элементов структур данных. Следствием этого является возможность использовать шаблоны для декларативного составления утверждений о фрагментах данных и гибкого указания функциям, как работать.

Например, функцию MathematicaCompile можно использовать для создания более эффективных версий кода. В следующем примере детали не имеют особого значения; важно то, что подвыражение {{com[_], Integer}}указывает, Compileчто выражения формы com[_]можно считать целыми числами для целей компиляции: 

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

Почтовые ящики в Erlang также работают таким же образом.

Соответствие Карри – Ховарда между доказательствами и программами связывает сопоставление с образцом в стиле ML с анализом случаев и доказательством путем исчерпания .

Сопоставление с образцом и строки

Безусловно, наиболее распространенная форма сопоставления с образцом включает строки символов. Во многих языках программирования для представления регулярных выражений используется определенный синтаксис строк, которые представляют собой шаблоны, описывающие строковые символы.

Однако можно выполнить некоторое сопоставление строкового шаблона в рамках той же структуры, которая обсуждалась в этой статье.

Шаблоны дерева для струнных

В системе Mathematica строки представлены как деревья корневого StringExpression, а все символы по порядку - как дочерние элементы корневого. Таким образом, чтобы соответствовать «любому количеству завершающих символов», необходим новый подстановочный знак ___ в отличие от _, который соответствовал бы только одному символу.

В Haskell и языках функционального программирования в целом строки представлены в виде функциональных списков символов. Функциональный список определяется как пустой список или элемент, созданный на основе существующего списка. В синтаксисе Haskell: 

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

Структура списка с некоторыми элементами такова element:list. При сопоставлении с образцом мы утверждаем, что определенный фрагмент данных равен определенному образцу. Например, в функции: 

head (element:list) = element

Мы утверждаем, что первый элемент headаргумента называется element, и функция его возвращает. Мы знаем, что это первый элемент из-за способа определения списков: единственный элемент, созданный на основе списка. Этот единственный элемент должен быть первым. Пустой список вообще не будет соответствовать шаблону, поскольку пустой список не имеет заголовка (первого созданного элемента).

В этом примере нам не listнужна функция, поэтому мы можем не обращать на нее внимания и, таким образом, написать функцию: 

head (element:_) = element

Эквивалентное преобразование Mathematica выражается как 

head[element, ]:=element

Примеры строковых шаблонов

В системе Mathematica, например, 

StringExpression["a",_]

будет соответствовать строке, состоящей из двух символов и начинающейся с «а».

Тот же шаблон в Haskell: 

['a', _]

Символьные сущности могут быть представлены для представления множества различных классов соответствующих функций строки. Например, 

StringExpression[LetterCharacter, DigitCharacter]

будет соответствовать строке, состоящей сначала из буквы, а затем из числа.

В Haskell для достижения тех же результатов можно использовать охранников : 

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

Основное преимущество манипуляции с символической строкой состоит в том, что она может быть полностью интегрирована с остальным языком программирования, а не быть отдельным специализированным подразделением. Вся мощь языка может быть использована для построения самих шаблонов или анализа и преобразования программ, которые их содержат.

СНОБОЛ

Основная статья: СНОБОЛ

SNOBOL ( Струнное Oriented и символический язык ) является компьютерным языком программирования , разработанным между 1962 и 1967 в AT & T Bell Laboratories от David J. Фарбера , Ральф Грисуолда и Иван П. Полонского .

SNOBOL4 отличается от большинства языков программирования тем, что имеет шаблоны как первоклассный тип данных ( т. Е. Тип данных, значениями которого можно манипулировать всеми способами, разрешенными для любого другого типа данных в языке программирования), а также предоставляя операторы для конкатенации и чередования шаблонов. . Строки, сгенерированные во время выполнения, можно рассматривать как программы и выполнять.

СНОБОЛ довольно широко преподавался в крупных университетах США в конце 1960-х - начале 1970-х годов и широко использовался в 1970-х и 1980-х годах в качестве языка манипулирования текстом в гуманитарных науках .

С момента создания SNOBOL новые языки, такие как Awk и Perl , сделали модными манипуляции со строками с помощью регулярных выражений . Однако шаблоны SNOBOL4 включают грамматики BNF , которые эквивалентны контекстно-свободным грамматикам и более мощны, чем регулярные выражения .

Смотрите также

использованная литература

внешние ссылки