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

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

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

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

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

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

История [ править ]

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

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

Примитивные паттерны [ править ]

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

f  0  =  1

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

f  n  =  n  *  f  ( n - 1 )

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

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

Образцы деревьев [ править ]

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

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

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

data  Color  =  ColorConstructor  Целочисленная  строка

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

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

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

integerPart  ( ColorConstructor  theInteger  _ )  =  theInteger

Также:

stringPart  ( ColorConstructor  _  theString )  =  theString

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

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

тип  color  =  красный  |  Черный тип  ' дерево = Слейте | Дерево из цветов * « дерево * » * ' дерево               позвольте  перебалансировать  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  (* универсальный случай, если предыдущий шаблон не соответствует *)

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

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

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

оценивает

[A 1, A 2]

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

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

данные SymbolTree = Symbol String [ SymbolTree ]

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

Символ "a" [ Символ "b" [], Символ "c" [] ]

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

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

А [_]

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

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

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

оценивает

{ а [ 1 ], а [ 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 ] : = 1fib [ n_ ] : = fib [ n -1 ] + fib [ n -2 ]

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

Трассировка [ фиб [ 3 ], фиб [ _ ]]

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

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

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

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

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

com [ i_ ] : = Биномиальное [ 2 i , i ]   Скомпилировать [{ x , { i , _Integer }}, x ^ com [ i ], {{ com [ _ ], Integer }}]

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

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

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

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

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

Шаблоны дерева для строк [ править ]

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

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

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

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

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

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

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

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

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

head [element,]: = element

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

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

StringExpression ["а", _]

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

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

[ 'а' ,  _ ]

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

StringExpression [LetterCharacter, DigitCharacter]

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

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

[ буква ,  цифра ]  |  isAlpha  буква  &&  isDigit  цифра

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

СНОБОЛ [ править ]

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

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

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

Внешние ссылки [ править ]

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