En informática , la coincidencia de patrones es el acto de comprobar una secuencia dada de tokens para detectar la presencia de los constituyentes de algún patrón . A diferencia del reconocimiento de patrones , la coincidencia normalmente tiene que ser exacta: "o será una coincidencia o no". Los patrones generalmente tienen la forma de secuencias o estructuras de árbol . Los usos de la coincidencia de patrones incluyen generar las ubicaciones (si las hay) de un patrón dentro de una secuencia de tokens, generar algún componente del patrón coincidente y sustituir el patrón coincidente con alguna otra secuencia de tokens (es decir, buscar y reemplazar ).
Los patrones de secuencia (por ejemplo, una cadena de texto) a menudo se describen mediante expresiones regulares y se combinan mediante técnicas como el retroceso .
Los patrones de árbol se utilizan en algunos lenguajes de programación como herramienta general para procesar datos en función de su estructura, por ejemplo, C# , [1] F# , [2] Haskell , [3] ML , Python , [4] Ruby , [5] Rust . [6] Scala , [7] Swift [8] y el lenguaje matemático simbólico Mathematica tienen una sintaxis especial para expresar patrones de árbol y una construcción de lenguaje para la ejecución condicional y la recuperación de valores basada en ella.
A menudo es posible ofrecer patrones alternativos que se prueban uno por uno, lo que produce una potente construcción de programación condicional. La combinación de patrones a veces incluye soporte para los guardias . [ cita necesaria ]
Los primeros lenguajes de programación con construcciones de coincidencia de patrones incluyen COMIT (1957), SNOBOL (1962), Refal (1968) con coincidencia de patrones basada en árboles, Prolog (1972), St Andrews Static Language ( SASL ) (1976), NPL (1977), y Calculadora recursiva de Kent (KRC) (1981).
Muchos editores de texto admiten la coincidencia de patrones de varios tipos: el editor QED admite la búsqueda de expresiones regulares y algunas versiones de TECO admiten el operador OR en las búsquedas.
Los sistemas de álgebra informática generalmente admiten la comparación de patrones en expresiones algebraicas. [9]
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 simple en la sintaxis de Haskell (los parámetros de la función no están entre paréntesis sino que están separados por espacios, = no es una asignación sino una definición):
f 0 = 1 Aquí, 0 es un patrón de valor único. Ahora, siempre que a f se le dé 0 como argumento, el patrón coincide y la función devuelve 1. Con cualquier otro argumento, la coincidencia y, por tanto, la función fallan. Como la sintaxis admite patrones alternativos en las definiciones de funciones, podemos continuar la definición ampliándola para aceptar argumentos más genéricos:
f norte = norte * f ( norte - 1 ) Aquí, el primero nes un patrón de variable única, que coincidirá con absolutamente cualquier argumento y lo vinculará al nombre n para usarlo en el resto de la definición. En Haskell (a diferencia al menos de Hope ), los patrones se prueban en orden, por lo que la primera definición aún se aplica en el caso muy específico de que la entrada sea 0, mientras que para cualquier otro argumento la función regresa n * f (n-1)con n como argumento.
El patrón comodín (a menudo escrito como _) también es simple: como un nombre de variable, coincide con cualquier valor, pero no vincula el valor a ningún nombre. Se han desarrollado algoritmos para hacer coincidir comodines en situaciones simples de coincidencia de cadenas en varias variedades recursivas y no recursivas. [10]
Se pueden construir patrones más complejos a partir de los primitivos de la sección anterior, generalmente de la misma manera que se construyen valores combinando otros valores. La diferencia entonces es que con partes variables y comodines, un patrón no se construye en un solo valor, sino que coincide con un grupo de valores que son la combinación de los elementos concretos y los elementos que pueden variar dentro de la estructura del patrón. .
Un patrón de árbol describe una parte de un árbol comenzando con un nodo y especificando algunas ramas y nodos y dejando algunos sin especificar con un patrón variable o comodín. Puede resultar útil pensar en el árbol de sintaxis abstracta de un lenguaje de programación y en los tipos de datos algebraicos .
En Haskell, la siguiente línea define un tipo de datos algebraicos Colorque tiene un único constructor de datos ColorConstructorque envuelve un número entero y una cadena.
Color de datos = ColorConstructor Cadena entera El constructor es un nodo en un árbol y el número entero y la cadena son hojas en las ramas.
Cuando queremos escribir funciones para crear Colorun tipo de datos abstracto , queremos escribir funciones para interactuar con el tipo de datos y, por lo tanto, queremos extraer algunos datos del tipo de datos, por ejemplo, solo la cadena o solo la parte entera de Color.
Si pasamos una variable que es de tipo Color, ¿cómo podemos sacar los datos de esta variable? Por ejemplo, para que una función obtenga la parte entera de Color, podemos usar un patrón de árbol simple y escribir:
integerPart ( ColorConstructor theInteger _ ) = theInteger También:
stringPart ( ColorConstructor _ theString ) = theString Las creaciones de estas funciones pueden automatizarse mediante la sintaxis de registro de datos de Haskell .
Este ejemplo de OCaml que define un árbol rojo-negro y una función para reequilibrarlo después de la inserción del elemento muestra cómo hacer coincidir una estructura más compleja generada por un tipo de datos recursivo. El compilador verifica en tiempo de compilación que la lista de casos sea exhaustiva y que ninguno sea redundante.
color del tipo = Rojo | Tipo negro ' un árbol = Vacío | Arbol de color * ' un arbol * ' un * ' un arbol dejar reequilibrar t = hacer coincidir t con | Árbol ( Negro , Árbol ( Rojo , Árbol ( Rojo , a , x , b ), y , c ), z , d ) | Árbol ( Negro , Árbol ( Rojo , a , x , Árbol ( Rojo , b , y , c )), z , d ) | Árbol ( Negro , a , x , Árbol ( Rojo , Árbol ( Rojo , b , y , c ), z , d )) | Árbol ( Negro , a , x , Árbol ( Rojo , b , y , Árbol ( Rojo , c , z , d ))) -> Árbol ( Rojo , Árbol ( Negro , a , x , b ), y , Árbol ( Negro , c , z , re )) | _ -> t (* el caso 'general' si ningún patrón anterior coincide *)La coincidencia de patrones se puede utilizar para filtrar datos de una determinada estructura. Por ejemplo, en Haskell se podría utilizar una lista por comprensión para este tipo de filtrado:
[ A x | A x <- [ A 1 , B 1 , A 2 , B 2 ]] evalúa a
[A 1, A 2]
En Mathematica , la única estructura que existe es el árbol , que está poblado de símbolos. En la sintaxis de Haskell utilizada hasta ahora, esto podría definirse como
datos SymbolTree = Cadena de símbolos [ SymbolTree ] Un árbol de ejemplo podría verse así
Símbolo "a" [ Símbolo "b" [], Símbolo "c" []] En la sintaxis tradicional, más adecuada, los símbolos se escriben tal como están y los niveles del árbol se representan usando [], de modo que, por ejemplo a[b,c], sea un árbol con a como padre y b y c como hijos.
Un patrón en Mathematica implica poner "_" en posiciones de ese árbol. Por ejemplo, el patrón
A[_]
coincidirá con elementos como A[1], A[2] o, más generalmente, A[ x ] donde x es cualquier entidad. En este caso, Aes el elemento concreto, mientras que _denota el trozo de árbol que puede variar. Un símbolo añadido a _vincula la coincidencia con el nombre de esa variable, mientras que un símbolo añadido a _restringe las coincidencias a los nodos de ese símbolo. Tenga en cuenta que incluso los espacios en blanco se representan internamente como Blank[]for _y Blank[x]for _x.
La función de Mathematica Casesfiltra elementos del primer argumento que coinciden con el patrón del segundo argumento: [11]
Casos [{ a [ 1 ], b [ 1 ], a [ 2 ], b [ 2 ]}, a [ _ ] ] evalúa a
{ un [ 1 ], un [ 2 ]} La coincidencia de patrones se aplica a la estructura de las expresiones. En el siguiente ejemplo,
Casos [ { a [ b ], a [ b , c ], a [ b [ c ], d ], a [ b [ c ], d [ e ]], a [ b [ c ], d , e ]} , a [ b [ _ ], _ ] ] devoluciones
{ a [ b [ c ], d ], a [ b [ c ], d [ e ]]} porque sólo estos elementos coincidirán con el patrón a[b[_],_]anterior.
En Mathematica, también es posible extraer estructuras a medida que se crean en el curso del cálculo, independientemente de cómo o dónde aparezcan. La función Tracese puede utilizar para monitorear un cálculo y devolver los elementos que surgen y que coinciden con un patrón. Por ejemplo, podemos definir la secuencia de Fibonacci como
mentira [ 0 | 1 ] := 1 fib [ n_ ] := fib [ n -1 ] + fib [ n -2 ] Entonces, podemos hacer la pregunta: dada fib[3], ¿cuál es la secuencia de llamadas recursivas de Fibonacci?
Seguimiento [ fib [ 3 ], fib [ _ ]] devuelve una estructura que representa las apariciones del patrón fib[_]en la estructura computacional:
{ mentira [ 3 ], { mentira [ 2 ], { mentira [ 1 ]}, { mentira [ 0 ]}}, { mentira [ 1 ]}}En los lenguajes de programación simbólicos, es fácil tener patrones como argumentos para funciones o como elementos de estructuras de datos. Una consecuencia de esto es la capacidad de utilizar patrones para hacer declaraciones sobre piezas de datos de forma declarativa y para indicar de manera flexible a las funciones cómo operar.
Por ejemplo, la función MathematicaCompile se puede utilizar para crear versiones más eficientes del código. En el siguiente ejemplo los detalles no importan particularmente; lo que importa es que la subexpresión {{com[_], Integer}}indica Compileque se puede suponer que las expresiones de la forma com[_]son números enteros a efectos de compilación:
com [ i_ ] := Binomial [ 2 i , i ] Compilar [{ x , { i , _Integer }}, x ^ com [ i ], {{ com [ _ ], Integer }}] Los buzones de correo en Erlang también funcionan de esta manera.
La correspondencia Curry-Howard entre pruebas y programas relaciona la coincidencia de patrones de estilo ML con el análisis de casos y la prueba por agotamiento .
Con diferencia, la forma más común de coincidencia de patrones implica cadenas de caracteres. En muchos lenguajes de programación, se utiliza una sintaxis particular de cadenas para representar expresiones regulares, que son patrones que describen caracteres de cadena.
Sin embargo, es posible realizar algunas coincidencias de patrones de cadena dentro del mismo marco que se ha analizado a lo largo de este artículo.
En Mathematica, las cadenas se representan como árboles de raíz StringExpression y todos los caracteres en orden como hijos de la raíz. Por lo tanto, para hacer coincidir "cualquier cantidad de caracteres finales", se necesita un nuevo comodín ___ en contraste con _ que coincidiría con un solo carácter.
En Haskell y en los lenguajes de programación funcional 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 sobre una lista existente. En la sintaxis de Haskell:
[] -- una lista vacía x : xs -- un elemento x construido en una lista xs La estructura de una lista con algunos elementos es así element:list. Al comparar patrones, afirmamos que un determinado dato es igual a un determinado patrón. Por ejemplo, en la función:
cabeza ( elemento : lista ) = elemento Afirmamos que el primer elemento del headargumento de se llama elemento y la función lo devuelve. Sabemos que este es el primer elemento por la forma en que se definen las listas, un único elemento construido en una lista. Este único elemento debe ser el primero. La lista vacía no coincidiría en absoluto con el patrón, ya que una lista vacía no tiene un encabezado (el primer elemento que se construye).
En el ejemplo, no utilizamos list, por lo que podemos ignorarlo y así escribir la función:
cabeza ( elemento : _ ) = elemento La transformación equivalente de Mathematica se expresa como
cabeza[elemento, ]:=elemento
En Mathematica, por ejemplo,
CadenaExpresión["a",_]
coincidirá con una cadena que tiene dos caracteres y comienza con "a".
El mismo patrón en Haskell:
[ 'a' , _ ] Se pueden introducir entidades simbólicas para representar muchas clases diferentes de características relevantes de una cadena. Por ejemplo,
Expresióndecadena[carácter de letra, carácter de dígito]
coincidirá con una cadena que consta primero de una letra y luego de un número.
En Haskell, los guardias podrían usarse para lograr los mismos combates:
[ letra , dígito ] | es letra alfa && es dígito dígito La principal ventaja de la manipulación de cadenas simbólicas es que puede integrarse completamente con el resto del lenguaje de programación, en lugar de ser una subunidad separada con un propósito especial. Se puede aprovechar todo el poder del lenguaje para construir los patrones mismos o analizar y transformar los programas que los contienen.
SNOBOL ( StriNg Oriented and symBOlic Language ) es un lenguaje de programación informático desarrollado entre 1962 y 1967 en AT&T Bell Laboratories por David J. Farber , Ralph E. Griswold e 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 manipularse en todas las formas permitidas para cualquier otro tipo de datos en el lenguaje de programación) y por proporcionar operadores para la concatenación y alternancia de patrones. . Las cadenas generadas durante la ejecución pueden tratarse como programas y ejecutarse.
SNOBOL se enseñó ampliamente en las grandes universidades estadounidenses a finales de los años 1960 y principios de los años 1970 y fue ampliamente utilizado en los años 1970 y 1980 como lenguaje de manipulación de textos en humanidades .
Desde la creación de SNOBOL, lenguajes más nuevos como Awk y Perl han puesto de moda la manipulación de cadenas mediante expresiones regulares . Sin embargo, los patrones SNOBOL4 incluyen gramáticas BNF , que son equivalentes a gramáticas libres de contexto y más poderosas que las expresiones regulares . [12]
