Búsqueda de patrones

En ciencias de la computación, búsqueda de patrones es el acto de comprobación de una determinada secuencia de fichas para la presencia de los componentes de algún patrón. En contraste con el reconocimiento de patrones, la coincidencia por lo general tiene que ser exacta. Los patrones generalmente tienen la forma de secuencias o estructuras de árbol. Usos de coincidencia de patrones incluyen la salida de los lugares (en su caso) de un patrón dentro de una secuencia de tokens, a la salida de algún componente del patrón emparejado, y sustituir el patrón coincidente con alguna otra secuencia de tokens (es decir, buscar y reemplazar).

Patrones de secuencia (por ejemplo, una cadena de texto) se describen a menudo el uso de expresiones regulares y combinados utilizando técnicas tales como retrocesos.

Patrones de árbol se utilizan en algunos lenguajes de programación como una herramienta general para procesar los datos sobre la base de su estructura, por ejemplo, Haskell, ML y el idioma simbólico de las matemáticas Mathematica tienen una sintaxis especial para expresar patrones de árboles y un lenguaje construyente para la ejecución condicional y recuperación de valor basado en ella. Por razones de simplicidad y eficiencia, estos patrones de árboles carecen de algunas de las características que están disponibles en las expresiones regulares.

A menudo es posible dar patrones alternativos que se pretenden uno por uno, que produce una potente construcción de programación condicional. La coincidencia de patrones a veces incluye soporte para los guardias.

Reescritura Plazo y gráfico reescritura idiomas dependen de coincidencia de patrones para el modo fundamental de un programa evalúa en un resultado.

Historia

Los primeros programas de ordenador para utilizar la coincidencia de patrones fueron los editores de texto. En laboratorios Bell, Ken Thompson extendió la búsqueda y sustitución de características del editor QED para aceptar expresiones regulares. Los primeros lenguajes de programación con el modelo búsquede de patrones fueron SNOBOL de 1962, SASL de 1976, NPL desde 1977, y KRC desde 1981. El primer lenguaje de programación con funciones de coincidencia de patrones basados en los árboles era la extensión de Fred McBride de LISP, en 1970.

Patrones primitivos

El patrón más simple en la coincidencia de patrones es un valor explícito o una variable. Por ejemplo, considere una definición de función sencilla en la sintaxis de Haskell (parámetros de función no están entre paréntesis, pero están separados por espacios, = no es tarea pero la definición):

 f 0 = 1

Aquí, 0 es un patrón único valor. Ahora, siempre que f da 0 como argumento coincide con el patrón y la función devuelve 1. Con cualquier otro argumento, el argumento no coincide y por lo tanto la función fallará. Como la sintaxis soporta patrones alternativos en las definiciones de funciones, podemos seguir la definición extendiéndolo a tomar argumentos más genéricos:

 f n = n * f (n-1)

Aquí, la primera n es un único patrón variable, que coincidirá con absolutamente ningún argumento y enlazarlo a nombre de n que se utilizará en el resto de la definición. En Haskell (a diferencia de Hope), los patrones son juzgados en orden para la primera definición todavía se aplica en el caso muy específico de la entrada es 0, mientras que para cualquier otro argumento de la función se devuelve n * f (n-1), siendo n el argumento.

El patrón de comodines (a menudo escrito como _) también es simple: como un nombre de variable, que coincide con cualquier valor, pero no se une el valor a cualquier nombre.

Patrones de árboles

Más patrones complejos pueden ser construidos a partir de los primitivos de la sección anterior, por lo general en la misma forma que los valores se construyen mediante la combinación de otros valores. La diferencia, entonces es que con partes variables y comodín, un patrón no construir en un solo valor, pero coincide con un grupo de valores que son la combinación de los elementos de hormigón y los elementos que se permite variar dentro de la estructura del patrón.

Un patrón de árbol describe una parte de un árbol comenzando con un nodo y especificar algunas ramas y nodos y dejando algunos no especificado con un patrón variable o comodín. Puede ayudar a pensar en el árbol de sintaxis abstracta de un lenguaje de programación y tipos de datos algebraicos.

En Haskell, la siguiente línea define un tipo de datos algebraica Color que tiene un solo constructor ColorConstructor datos que envuelve un entero y una cadena.

 data Color = ColorConstructor Integer String

El constructor es un nodo en un árbol y el número entero y la cadena son las hojas en las ramas.

Cuando queremos escribir funciones para hacer Color un tipo abstracto de datos, queremos escribir funciones para interactuar con el tipo de datos, y por lo tanto queremos extraer algunos datos del tipo de datos, por ejemplo, sólo la cadena o sólo la parte entera de Color.

Si pasamos una variable que es de tipo color, ¿cómo podemos obtener los datos de esta variable? Por ejemplo, para una función obtener la parte entera de color, podemos utilizar un patrón simple árbol y escribir:

 integerPart (ColorConstructor theInteger _) = theInteger

También:

 stringPart (ColorConstructor _ theString) = theString

Las creaciones de estas funciones se pueden automatizar mediante la sintaxis de registro de datos de Haskell.

Filtrado de datos con patrones

La coincidencia de patrones se puede utilizar para filtrar los datos de una cierta estructura. Por ejemplo, en Haskell una lista por comprensión podría ser utilizado para este tipo de filtrado:

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

evalúa a

[A 1, A 2]

La coincidencia de patrones en Mathematica

En Mathematica, la única estructura que existe es el árbol, que está poblada por símbolos. En la sintaxis Haskell utilizado hasta el momento, esto podría ser definida como

data SymbolTree = Symbol String [SymbolTree]

Un ejemplo de árbol puede verse como lo siguiente

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

En la sintaxis tradicional, más adecuado, los símbolos se escriben como son y los niveles del árbol se representan utilizando [], de modo que, por ejemplo, un a[b,c] es un árbol con a como padre, y b y c como los hijos.

Un modelo en Mathematica consiste en colocar "_" en las posiciones en ese árbol. Por ejemplo, el patrón

A[_]

coincidirá con elementos tales como A [1], A [2], o más generalmente A [x] donde x es cualquier entidad. En este caso, A es el elemento de hormigón, mientras _ denota la pieza de árbol que se puede variar. Un símbolo antepondrá _ une el partido para el nombre de la variable, mientras que un símbolo anexa a _ restringe los partidos a los nodos de ese símbolo.

La función de Cases de Mathematica filtra elementos del primer argumento que coincide con el patrón en el segundo argumento:

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

evalúa a:

{a[1], a[2]}

La coincidencia de patrones se aplica a la estructura de las expresiones. En el siguiente ejemplo,

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

devuelve

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

porque sólo estos elementos que coincida con el patrón de una a[b[_],_] anteriormente.

En Mathematica, también es posible extraer las estructuras a medida que se crean en el curso de cálculo, independientemente de cómo o dónde aparecen. La función Trace se puede utilizar para controlar un cálculo, y devolver los elementos que surgen que coincidan con un patrón. Por ejemplo, podemos definir la secuencia de Fibonacci como

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

Entonces, podemos hacer la pregunta: Dada fib[3], lo que es la secuencia de llamadas recursivas Fibonacci?

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

devuelve una estructura que representa las apariciones del patrón fib[_] en la estructura computacional:

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

Programación declarativa

En los lenguajes de programación simbólicos, es fácil tener patrones como argumentos a funciones o como elementos de estructuras de datos. Una consecuencia de esto es la capacidad de utilizar patrones para hacer declarativa declaraciones sobre piezas de datos y para instruir flexible funciones de la forma de operar.

Por ejemplo, la función Compile de Mathematica se puede utilizar para hacer versiones más eficientes del código. En el siguiente ejemplo los detalles no hacen particularmente materia; lo que importa es que la subexpresión {{com[_], Integer}} Compile instruye que las expresiones de la forma com[_] se puede suponer que ser enteros a los efectos de su compilación:

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

Los buzones de Erlang también funcionan de esta manera.

La correspondencia Curry-Howard entre pruebas y programas relaciona patrón de estilo ML a coincidir con el caso de análisis y prueba por agotamiento.

Coincidencia de patrones y cadenas

Con mucho, la forma más común de coincidencia de patrones consiste en cadenas de caracteres. En muchos lenguajes de programación, una sintaxis particular de cadenas se utiliza para representar expresiones regulares, que son patrones que describen caracteres de la cadena.

Sin embargo, es posible realizar algún patrón cadena que coincide en el mismo marco que se ha discutido en este artículo.

Patrones de árbol para cadenas

En Mathematica, las cadenas se representan como árboles de StringExpression raíz y todos los caracteres en orden como hijos de la raíz. Por lo tanto, para que coincida con "cualquier cantidad de caracteres finales", un nuevo comodín ___ que se necesita en contraste con _ que coincidiría con un solo carácter.

En Haskell y lenguajes de programación funcionales en general, las cadenas se representan como listas funcionales de caracteres. Una lista funcional se define como una lista vacía, o un elemento construido en una lista existente. En la sintaxis de Haskell:

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

La estructura de una lista con algunos elementos es por tanto element:list. Cuando el modelo a juego, afirmamos que una determinada pieza de datos es igual a un cierto patrón. Por ejemplo, en la función:

 head (element:list) = element

afirmamos que el primer elemento de la argumentación de la head se llama elemento, y la función devuelve esto. Sabemos que este es el primer elemento debido a la forma listas se definen, un solo elemento construido en una lista. Esto solo elemento debe ser el primero. La lista vacía no se coincida con el patrón en absoluto, como una lista vacía no tiene una cabeza (el primer elemento que se construye).

En el ejemplo, no tenemos ningún uso para la lista, por lo que podemos prescindir de ella, y así escribir la función:

 head (element:_) = element

La transformación en Mathematica equivalente se puede escribir como:

head[element, ]:=element

Ejemplo Patrones de cadena

En Mathematica, por ejemplo,

StringExpression["a", ]

coincidirá con una cadena que cuenta con dos personajes y comienza con "a".

El mismo patrón en Haskell:

 ['a', _]

Entidades simbólicas pueden ser introducidos para representar muchas clases diferentes de las características relevantes de una cadena. Por ejemplo,

StringExpression[LetterCharacter, DigitCharacter]

coincidirá con una cadena que consta de una carta primero, y luego un número.

En Haskell, podrían utilizarse guardias para lograr las mismas coincidencias:

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

La principal ventaja de la manipulación de cadenas simbólica es que puede ser completamente integrado con el resto del lenguaje de programación, en lugar de ser una subunidad de propósito especial separado. Todo el poder de la lengua se puede aprovechar para construir los patrones de sí mismos o analizar y transformar los programas que los contienen.

SNOBOL

SNOBOL (String Orientada lenguaje simbólico) es un lenguaje de programación desarrollado entre 1962 y 1967 en el AT & T laboratorios Bell por David J. Farber, Ralph E. Griswold y Ivan P. Polonsky.

SNOBOL4 se distingue de la mayoría de los lenguajes de programación por tener patrones como un tipo de datos de primera clase (es decir, un tipo de datos cuyos valores pueden ser manipulados en todas las formas permitidas para cualquier otro tipo de datos en el lenguaje de programación) y al proporcionar los operadores para el patrón de la concatenación y la alternancia. Cuerdas generados durante la ejecución pueden ser tratados como programas y ejecutados.

SNOBOL fue ampliamente enseñado en las universidades más grandes de Estados Unidos en la década de 1960 y principios de 1970 y fue ampliamente utilizado en los años 1970 y 1980 como un lenguaje de manipulación de texto en las humanidades.

Desde la creación de SNOBOL, nuevos lenguajes como Perl y Awk y han hecho la manipulación de cadenas mediante expresiones regulares de moda. Patrones SNOBOL4, sin embargo, subsumen gramáticas de BNF, que son equivalentes a las gramáticas libres de contexto y más potente que las expresiones regulares ^[1]

Véase también

AIML for an AI language based on matching patterns in speech
AWK language
Coccinelle pattern matches C source code
glob (programming)
EasyPattern language pattern matching language for non-programmers
Pattern calculus
Pattern language
Pattern recognition for fuzzy patterns
PCRE Perl Compatible Regular Expressions, a common modern implementation of string pattern matching ported to many languages
REBOL parse dialect for pattern matching used to implement language dialects
Symbolic integration
Tom (pattern matching language)
SNOBOL for a programming language based on one kind of pattern matching
Unification, a similar concept in Prolog

Referencias

The Mathematica Book, chapter Section 2.3: Patterns
The Haskell 98 Report, chapter 3.17 Pattern Matching.
Python Reference Manual, chapter 6.3 Assignment statements.
The Pure Programming Language, chapter 4.3: Patterns

↑ Gimpel, J. F. 1973. A theory of discrete patterns and their implementation in SNOBOL4. Commun. ACM 16, 2 (Feb. 1973), 91-100. DOI=http://doi.acm.org/10.1145/361952.361960