La coincidencia de patrones - Pattern matching

Este artículo trata sobre la coincidencia de patrones en la programación funcional . Para otros usos, consulte la coincidencia de cadenas y el reconocimiento de patrones .
Para el uso de criterios de coincidencia de variables en la definición de patrones abstractos que coincidan, consulte expresión regular .

En informática , la coincidencia de patrones es el acto de verificar una secuencia dada de tokens para detectar la presencia de los constituyentes de algún patrón . En contraste con el reconocimiento de patrones , la coincidencia generalmente tiene que ser exacta: "o será o no una coincidencia". 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, para 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 usando expresiones regulares y se combinan usando técnicas como el retroceso .

Los patrones de árbol se utilizan en algunos lenguajes de programación como una herramienta general para procesar datos basados ​​en su estructura, por ejemplo, C # , F # , Haskell , ML , Python , Ruby , Rust , Scala , Swift y el lenguaje matemático simbólico Mathematica tiene una sintaxis especial para expresar árbol patrones y una construcción de lenguaje para la ejecución condicional y la recuperación de valores basados ​​en él.

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 coincidencia de patrones a veces incluye soporte para guardias .

Los algoritmos de análisis a menudo se basan en la coincidencia de patrones para transformar cadenas en árboles de sintaxis .

Historia

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), SASL (1976), NPL (1977) y 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 por computadora generalmente admiten la coincidencia de patrones en expresiones algebraicas.

Ver también: Expresión regular § Historia

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 simple en la sintaxis de Haskell (los parámetros de la función no están entre paréntesis pero 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 da 0 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 con la definición extendiéndola para tomar argumentos más genéricos: 

f n = n * f (n-1)

Aquí, el primero nes un patrón de una sola variable, que coincidirá absolutamente con cualquier argumento y lo vinculará al nombre n que se usará en el resto de la definición. En Haskell (a diferencia de Hope , al menos ), 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 de 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 emparejar comodines en situaciones simples de emparejamiento de cadenas en una serie de variedades recursivas y no recursivas.

Patrones de árboles

Se pueden construir patrones más complejos a partir de los primitivos de la sección anterior, generalmente de la misma manera que los valores se construyen combinando otros valores. La diferencia entonces es que con las partes variables y comodín, 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 sintáctico abstracto 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 solo constructor de datos ColorConstructorque envuelve un número 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 hojas en ramas.

Cuando queremos escribir funciones para hacer 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 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 se pueden 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 del elemento muestra cómo hacer coincidir una estructura más compleja generada por un tipo de datos recursivo. 

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 *)

Filtrar datos con patrones

La coincidencia de patrones se puede utilizar para filtrar datos de una determinada estructura. Por ejemplo, en Haskell se podría usar una lista de 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]

Coincidencia de patrones en Mathematica

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 

data SymbolTree = Symbol String [SymbolTree]

Un árbol de ejemplo podría verse así 

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

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

Un patrón en Mathematica implica poner "_" en posiciones en 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 se puede variar. Un símbolo antepuesto a _vincula la coincidencia a ese nombre de variable, mientras que un símbolo adjunto 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: 

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[_], _] ]

devoluciones 

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

porque solo 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 usar 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 

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 de Fibonacci recursivas? 

Trace[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]}}

Programación declarativa

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 usar patrones para hacer declaraciones declarativas sobre piezas de datos e instruir de manera flexible a las funciones sobre cómo operar.

Por ejemplo, la función de MathematicaCompile se puede usar para hacer 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 com[_]se puede suponer que las expresiones de la forma son números enteros a los efectos de la compilación: 

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

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

La correspondencia de 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 .

Coincidencia de patrones y cadenas

Con mucho, la forma más común de coincidencia de patrones involucra 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 discutido a lo largo de este artículo.

Patrones de árboles para cuerdas

En Mathematica, las cadenas se representan como árboles de la 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 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 así element:list. Cuando se realiza una coincidencia de patrones, afirmamos que un determinado dato es igual a un determinado patrón. Por ejemplo, en la función: 

head (element:list) = element

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 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 encabezado (el primer elemento que se construye).

En el ejemplo, no tenemos uso para list, por lo que podemos ignorarlo, y así escribir la función: 

head (element:_) = element

La transformación equivalente de Mathematica se expresa como 

head[element, ]:=element

Patrones de cadena de ejemplo

En Mathematica, por ejemplo, 

StringExpression["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, 

StringExpression[LetterCharacter, DigitCharacter]

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

En Haskell, los guardias podrían usarse para lograr los mismos partidos: 

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

La principal ventaja de la manipulación de cadenas simbólicas es que se puede integrar completamente con el resto del lenguaje de programación, en lugar de ser una subunidad separada 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

Artículo principal: SNOBOL

SNOBOL ( StriNg Oriented and SymBOlic Language ) es un lenguaje de programación de computadoras 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 al 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 a cualquier otro tipo de datos en el lenguaje de programación) y al proporcionar operadores para la concatenación y alternancia de patrones. . Las cadenas generadas durante la ejecución pueden tratarse como programas y ejecutarse.

El SNOBOL se enseñó ampliamente en las universidades más grandes de los Estados Unidos a fines 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 un lenguaje de manipulación de textos 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 . Los patrones SNOBOL4, sin embargo, subsumen las gramáticas BNF , que son equivalentes a las gramáticas libres de contexto y más poderosas que las expresiones regulares .

Ver también

Referencias

enlaces externos