En informática , la comparación 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 comparación 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 comparación de patrones incluyen la salida de las ubicaciones (si las hay) de un patrón dentro de una secuencia de tokens, para generar algún componente del patrón coincidente y para sustituir el patrón coincidente con alguna otra secuencia de tokens (es decir, búsqueda y reemplazo ).
Los patrones de secuencia (por ejemplo, una cadena de texto) a menudo se describen utilizando expresiones regulares y se comparan mediante técnicas como el retroceso .
Los patrones de árbol se utilizan en algunos lenguajes de programación como una 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 de matemáticas simbólicas Mathematica tienen una sintaxis especial para expresar patrones de árbol y una construcción de lenguaje para ejecución condicional y recuperación de valores basada en ella.
A menudo es posible proporcionar patrones alternativos que se prueban uno por uno, lo que produce una poderosa construcción de programación condicional. La comparación de patrones a veces incluye soporte para guardias . [ cita requerida ]
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 Kent Recursive Calculator (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 computacional generalmente admiten la coincidencia de patrones en expresiones algebraicas. [9]
El patrón más simple en la búsqueda de patrones es un valor explícito o una variable. Por ejemplo, considere una definición de función simple en sintaxis Haskell (los parámetros de la función no están entre paréntesis sino separados por espacios, = no es una asignación sino una definición):
f0 = 1 Aquí, 0 es un patrón de valor único. Ahora, siempre que se le dé 0 a f como argumento, el patrón coincide y la función devuelve 1. Con cualquier otro argumento, la coincidencia y, por lo tanto, la función fallan. Como la sintaxis admite patrones alternativos en las definiciones de funciones, podemos continuar la definición extendiéndola para que acepte argumentos más genéricos:
f n = n * f ( n - 1 ) Aquí, el primero nes un patrón de una sola variable, que coincidirá con absolutamente cualquier argumento y lo vinculará al nombre n para que se use en el resto de la definición. En Haskell (al menos a diferencia 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 retorna n * f (n-1)con n como argumento.
El patrón de comodín (que suele escribirse como _) también es simple: al igual que 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 de coincidencia de cadenas simples 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 los valores combinando otros valores. La diferencia es que, con las partes variables y comodines, un patrón no se construye en un único 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 una variable o un patrón de 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 entero y una cadena.
datos Color = ColorConstructor Entero Cadena El constructor es un nodo en un árbol y el entero y la cadena son hojas en las ramas.
Cuando queremos escribir funciones para crear Colorun tipo de datos abstracto , deseamos 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 de tipo Color, ¿cómo podemos obtener 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:
parteEntero ( ColorConstructor elEntero _ ) = elEntero También:
stringPart ( ColorConstructor_theString ) = theString La creación de estas funciones se puede automatizar 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 de elementos, 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.
tipo color = Rojo | Negro tipo ' un árbol = Vacío | Árbol de color * ' un árbol * ' un * ' un árboldeje que reequilibre t = coincida con 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 , d )) | _ -> t (* el caso 'cajón de sastre' si no coincide ningún patrón anterior *)La comparación de patrones se puede utilizar para filtrar datos de una determinada estructura. Por ejemplo, en Haskell se podría utilizar una comprensión de listas para este tipo de filtrado:
[ A x | A x <- [ A 1 , B 1 , A 2 , B 2 ]] evalúa a
[Un 1, Un 2]
En Mathematica , la única estructura que existe es el árbol , que está poblado por símbolos. En la sintaxis de Haskell utilizada hasta ahora, esto podría definirse como
datos ÁrbolDeSímbolos = Cadena De Símbolos [ ÁrbolDeSímbolos ] Un árbol de ejemplo podría entonces 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 son y los niveles del árbol se representan utilizando [], de modo que por ejemplo a[b,c]es 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, de forma más general, A[ x ], donde x es cualquier entidad. En este caso, Aes el elemento concreto, mientras que _denota la parte del árbol que se puede variar. Un símbolo antepuesto a _vincula la coincidencia a ese nombre de 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 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 ejemplo siguiente,
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 durante el proceso de cálculo, independientemente de cómo o dónde aparezcan. La función Tracese puede utilizar para supervisar 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
fib [ 0 | 1 ] := 1 fib [ n_ ] := fib [ n -1 ] + fib [ n -2 ] Entonces, podemos hacer la pregunta: Dado fib[3], ¿cuál es la secuencia de llamadas recursivas de Fibonacci?
Rastro [ fib [ 3 ], fib [ _ ]] devuelve una estructura que representa las ocurrencias del patrón fib[_]en la estructura computacional:
{ fib [ 3 ],{ fib [ 2 ],{ fib [ 1 ]},{ fib [ 0 ]}},{ fib [ 1 ]}}En los lenguajes de programación simbólica, es fácil utilizar patrones como argumentos de funciones o como elementos de estructuras de datos. Una consecuencia de esto es la capacidad de utilizar patrones para realizar declaraciones sobre fragmentos de datos y para indicar de forma flexible cómo deben operar las funciones.
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 son particularmente importantes; lo que importa es que la subexpresión {{com[_], Integer}}indica Compileque las expresiones de la forma com[_]se pueden asumir como números enteros para fines de compilación:
com [ i_ ] := Binomio [ 2 i , i ] Compilar [{ x , { i , _Entero }}, x ^ com [ i ], {{ com [ _ ], Entero }}] Los buzones de correo en Erlang también funcionan de esta manera.
La correspondencia Curry-Howard entre pruebas y programas relaciona la correspondencia de patrones de estilo ML con el análisis de casos y la prueba por agotamiento .
La forma más común de comparación 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 cadenas.
Sin embargo, es posible realizar algunas coincidencias de patrones de cadenas 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 que coincida con "cualquier cantidad de caracteres finales", se necesita un nuevo comodín ___ en contraste con _ que coincidiría solo con un único 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, por tanto element:list, . Cuando se realiza una comparación de patrones, se afirma 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 devuelve esto. Sabemos que este es el primer elemento debido a la forma en que se definen las listas, un solo elemento construido sobre 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 tenemos ningún uso para 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,
Expresión de cadena["a",_]
coincidirá con una cadena que tenga dos caracteres y comience 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ácterLetra, CarácterDígito]
coincidirá con una cadena que consta primero de una letra y luego de un número.
En Haskell, se podrían utilizar guardias para lograr las mismas coincidencias:
[ letra , dígito ] | isAlpha letra && isDigit dígito La principal ventaja de la manipulación simbólica de cadenas es que se puede integrar completamente con el resto del lenguaje de programación, en lugar de ser una subunidad separada y de propósito especial. Se puede aprovechar todo el poder del lenguaje para construir los propios patrones o analizar y transformar los programas que los contienen.
SNOBOL ( String Oriented and symBOlic Language ) es un lenguaje de programación informática desarrollado entre 1962 y 1967 en los Laboratorios AT&T Bell 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 se pueden manipular de 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 se pueden tratar como programas y ejecutar.
SNOBOL se enseñó ampliamente en las grandes universidades de Estados Unidos a finales de la década de 1960 y principios de la de 1970 y se usó ampliamente en las décadas de 1970 y 1980 como lenguaje de manipulación de texto en las 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 de SNOBOL4 incluyen gramáticas BNF , que son equivalentes a gramáticas libres de contexto y más potentes que las expresiones regulares . [12]
