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

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

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

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

Образцы деревьев используются в некоторых языки программирования как общий инструмент для обработки данных на основе их структуры, например C #,[1] F #,[2] Haskell, ML, Ржавчина,[3] Scala, Быстрый[4] и язык символической математики Mathematica имеют специальный синтаксис для выражения шаблонов дерева и языковая конструкция за условное исполнение и поиск значения на его основе.

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

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

История

Первыми компьютерными программами, использующими сопоставление с образцом, были текстовые редакторы.[нужна цитата ] В Bell Labs, Кен Томпсон расширили возможности поиска и замены Редактор QED принять обычные выражения. Ранние языки программирования с конструкциями сопоставления с образцом включают СНОБОЛ с 1962 г., Советский язык Рефал с 1968 года с сопоставлением по образцу на основе дерева, SASL с 1976 г., НПЛ с 1977 г. и KRC с 1981 года. Другим языком программирования с функциями сопоставления шаблонов на основе дерева было расширение Фреда Макбрайда LISP, в 1970 году.[7]

Смотрите также: Регулярное выражение § История

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

Самый простой образец сопоставления с образцом - это явное значение или переменная. В качестве примера рассмотрим простое определение функции в синтаксисе Haskell (параметры функции не в скобках, а разделены пробелами, = не присвоение, а определение):

ж 0 = 1

Здесь 0 - это шаблон с одним значением. Теперь, когда в качестве аргумента f задано 0, шаблон совпадает, и функция возвращает 1. С любым другим аргументом сопоставление и, следовательно, функция терпят неудачу. Поскольку синтаксис поддерживает альтернативные шаблоны в определениях функций, мы можем продолжить определение, расширив его, чтобы принять более общие аргументы:

ж п = п * ж (п-1)

Здесь первый п - это шаблон с одной переменной, который будет соответствовать абсолютно любому аргументу и связывать его с именем n, которое будет использоваться в остальной части определения. В Haskell (в отличие от как минимум Надеяться ) шаблоны проверяются по порядку, поэтому первое определение по-прежнему применяется в очень конкретном случае, когда вход равен 0, в то время как для любого другого аргумента функция возвращает п * ж (п-1) с аргументом n.

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

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

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

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

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

данные Цвет = ColorConstructor Целое число Нить

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

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

Если мы передадим переменную типа Color, как мы можем получить данные из этой переменной? Например, для функции, получающей целую часть Цвет, мы можем использовать простой шаблон дерева и написать:

integerPart (ColorConstructor Целое число _) = Целое число

Также:

stringPart (ColorConstructor _ Струна) = Струна

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

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

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

[А Икс|А Икс <- [А 1, B 1, А 2, B 2]]

оценивает

[A 1, A 2]

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

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

данныеСимволДерево=СимволНить[СимволДерево]

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

Символ"а"[Символ"б"[],Символ"c"[]]

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

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

А [_]

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

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

Случаи[{а[1],б[1],а[2],б[2]},а[_]]

оценивает

{а[1],а[2]}

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

Случаи[{а[б],а[б,c],а[б[c],d],а[б[c],d[е]],а[б[c],d,е]},а[б[_],_]]

возвращается

{а[б[c],d],а[б[c],d[е]]}

потому что только эти элементы будут соответствовать шаблону a [b [_], _] над.

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

выдумать[0|1]:=1выдумать[n_]:=выдумать[п-1]+выдумать[п-2]

Тогда мы можем задать вопрос: какова последовательность рекурсивных вызовов Фибоначчи для fib [3]?

След[выдумать[3],выдумать[_]]

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

{выдумать[3],{выдумать[2],{выдумать[1]},{выдумать[0]}},{выдумать[1]}}

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

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

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

com[я_]:=Биномиальный[2я,я]Компилировать[{Икс,{я,_Integer}},Икс^com[я],{{com[_],Целое число}}]

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

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

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

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

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

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

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

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

[] - пустой списокИкс:хз - элемент x, построенный на списке xs

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

голова (элемент:список) = элемент

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

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

голова (элемент:_) = элемент

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

head [element,]: = element

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

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

StringExpression ["а", _]

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

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

['а', _]

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

StringExpression [LetterCharacter, DigitCharacter]

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

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

[письмо, цифра] | isAlpha письмо && isDigit цифра

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

СНОБОЛ

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

СНОБОЛ (СтрО-ориентированный и символьный язык) - это язык компьютерного программирования, разработанный между 1962 и 1967 годами в AT&T Bell Laboratories к Дэвид Дж. Фарбер, Ральф Э. Грисволд и Иван Павлович Полонский.

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

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

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

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

Рекомендации

  1. ^ «Сопоставление с образцом - Руководство по C #».
  2. ^ «Сопоставление с образцом - Руководство по F #».
  3. ^ "Синтаксис паттернов - язык программирования Rust".
  4. ^ "Шаблоны - язык программирования Swift (Swift 5.1)".
  5. ^ Варт, Алессандро и Ян Пиумарта. "OMeta: объектно-ориентированный язык для сопоставления с образцом. »Материалы симпозиума 2007 г. по динамическим языкам. ACM, 2007.
  6. ^ Кнут, Дональд Э., Джеймс Х. Моррис-младший и Воган Р. Пратт. «Быстрое сопоставление с образцом в строках». Журнал SIAM по вычислениям 6.2 (1977): 323-350.
  7. ^ «Архивная копия». Архивировано из оригинал на 2007-02-03. Получено 2007-04-14.CS1 maint: заархивированная копия как заголовок (связь)
  8. ^ Кантаторе, Алессандро (2003). "Алгоритмы сопоставления подстановочных знаков".
  9. ^ «Кейсы - документация на языке Wolfram Language». reference.wolfram.com. Получено 2020-11-17.
  10. ^ Гимпель, Дж. Ф. 1973. Теория дискретных паттернов и их реализация в СНОБОЛ4. Commun. ACM 16, 2 (февраль 1973 г.), 91–100. DOI =http://doi.acm.org/10.1145/361952.361960.

внешняя ссылка