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

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

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

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

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

Древовидные шаблоны используются в некоторых языках программирования в качестве общего инструмента для обработки данных на основе их структуры, например C# , Ф# , Хаскелл , ML , Питон , Руби , Ржавчина , Скала , Быстрый и язык символьной математики Mathematica имеет специальный синтаксис для выражения древовидных шаблонов и языковую конструкцию для условного выполнения и поиска значений на его основе.

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

История

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

Ранние языки программирования с конструкциями сопоставления шаблонов включают COMIT (1957), SNOBOL (1962), Refal (1968) с древовидным сопоставлением шаблонов, Prolog (1972), St Andrews Static Language ( 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.

Функция Математика 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]}}

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

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

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

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

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

Соответствие Карри-Ховарда между доказательствами и программами связывает МО сопоставление шаблонов в стиле с анализом случаев и доказательством путем исчерпывания .

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

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

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

Древовидные шаблоны для строк

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

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

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

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

head (element:list) = element

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

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

head (element:_) = element

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

head[element, ]:=element

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

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

StringExpression["a",_]

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

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

['a', _]

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

StringExpression[LetterCharacter, DigitCharacter]

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

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

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

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

СНОБОЛ

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

SNOBOL ( StrNg Oriented and symBOlic Language ) — язык компьютерного программирования, разработанный между 1962 и 1967 годами в лабораториях AT&T Bell Laboratories Дэвидом Дж. Фарбером , Ральфом Э. Грисволдом и Иваном П. Полонски.

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

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

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

См. также

• Язык разметки искусственного интеллекта (AIML) для языка ИИ, основанный на сопоставлении шаблонов речи.
• AWK язык
• Шаблон божьей коровки соответствует исходному коду C
• Соответствующие подстановочные знаки
• глобус (программирование)
• Исчисление шаблонов
• Распознавание нечетких образов
• PCRE Perl-совместимые регулярные выражения, распространенная современная реализация сопоставления строковых шаблонов, портированная на многие языки.
• Диалект синтаксического анализа REBOL для сопоставления с образцом, используемый для реализации языковых диалектов.
• Символическая интеграция
• Теговый союз
• Том (язык сопоставления с образцом)
• СНОБОЛ — язык программирования, основанный на одном виде сопоставления с образцом.
• Язык шаблонов — метафорический, заимствованный из архитектуры.
• Сопоставление графиков

Ссылки

• Книга Mathematica, глава Раздел 2.3: Шаблоны
• Отчет Haskell 98, глава 3.17 Сопоставление с образцом .
• Справочное руководство Python, глава 6.3 Операторы присваивания .
• Чистый 4.3 язык программирования, глава : Шаблоны

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

• Представления: расширение сопоставления шаблонов Haskell
• Николаас Н. Остерхоф, Филип К. Ф. Хёльценшпис и Ян Купер. Шаблоны приложений . Презентация на выставке «Тенденции в функциональном программировании», 2005 г.
• JMatch : язык Java , дополненный сопоставлением с образцом.
• ShowTrend : Сопоставление шаблонов онлайн для цен на акции
• Неполная история текстового редактора QED Денниса Ритчи - представляет историю регулярных выражений в компьютерных программах.
• Реализация языков функционального программирования, страницы 53–103 Саймона Пейтона Джонса, опубликовано Prentice Hall, 1987.
• Немерль, сопоставление с образцом .
• Эрланг, сопоставление с образцом .
• Реквизит: язык сопоставления шаблонов на основе C++, 1999 г.
• PatMat: библиотека сопоставления шаблонов C++, основанная на SNOBOL / SPITBOL.
• Темур Куция. Плоское соответствие . Журнал символических вычислений 43 (12): 858–873. Подробно описывает плоское сопоставление в системе Mathematica.
• Язык сопоставления шаблонов языка EasyPattern для непрограммистов