En el de informática, la adaptación de modelos del es el acto de la comprobación para saber si hay la presencia de los componentes de un patrón dado . En contraste con el reconocimiento de patrón, el patrón se especifica rígido. Tal patrón se refiere convencionalmente o a las secuencias o la adaptación de modelos de las estructuras arborescentes se utiliza para probar si las cosas tienen una estructura deseada, para encontrar la estructura relevante, para recuperar las piezas que alinean, y para substituir la parte que empareja con algo más. Los patrones de la secuencia (o específicamente secuencia de texto) se describen usar las expresiones regulares (es decir vuelta hacia atrás ) y se emparejan a menudo usar algoritmos respectivos. Las secuencias se pueden también considerar como la ramificación de árboles para cada elemento en el elemento respectivo y el resto de la secuencia, o como árboles que ramifiquen inmediatamente en todos los elementos.
Los patrones del árbol se pueden utilizar en los lenguajes de programación como herramienta general para procesar los datos basados en su estructura. Algunos lenguajes el de programación funcional tal como Haskell, ml y el simbólico Mathematica de la lengua de las matemáticas tienen un sintaxis especial para expresar patrones del árbol y una construcción de lengua para la ejecución condicional y valoran la recuperación basada en ella. Por razones de la simplicidad y de la eficacia, estos patrones del árbol carecen algunas características que estén disponibles en expresiones regulares. Dependiendo de las idiomas, la adaptación de modelos se puede utilizar para las discusiones de la función, en caso de que las expresiones, siempre que las nuevas variables estén limitadas, o en situaciones muy limitadas por ejemplo solamente para las secuencias en la asignación (en el pitón ). Es a menudo posible dar los patrones alternativos que se intentan uno por uno, que rinde a de gran alcance la construcción programada condicional . La adaptación de modelos puede beneficiarse de los protectores
Las idiomas de la reescritura del término confían en la adaptación de modelos para la manera fundamental que un programa evalúa en un resultado. La adaptación de modelos beneficia la mayoría cuando los datastructures subyacentes son tan simples y flexibles como sea posible. Éste es especialmente el caso en idiomas con un sabor simbólico fuerte. En los lenguajes de programación simbólicos los patrones son la misma clase de datatype que todo, y se pueden por lo tanto alimentar adentro como discusiones a las funciones.
Patrones primitivos
El patrón más simple de la adaptación de modelos es un valor explícito o una variable. Por un ejemplo, considerar una definición de función simple en el sintaxis de Haskell (los parámetros de la función no están entre paréntesis sino son separados por los espacios, = no son asignación sino definición):
f 0 = 1
Aquí, 0 es un solo patrón del valor. Ahora, siempre que f se dé 0 como discusión que el patrón empareja y las vueltas 1. Con cualquie otra discusión, emparejar y así el fall de la función. Pues el sintaxis apoya patrones alternativos en definiciones de función, podemos continuar la definición que lo amplía para tomar discusiones más genéricas:
f n = n * f (n-1)
Aquí, el primer n es un solo patrón variable, que emparejará absolutamente cualquier discusión y la atará para nombrar n para ser utilizado en el resto de la definición. En Haskell (desemejante por lo menos de la esperanza ), los patrones se intentan en orden así que la primera definición todavía se aplica en el caso muy específico de la entrada que es 0, mientras que para cualquier otra discusión la función vuelve el n * f (n-1) con n que es la discusión.
El patrón del comodín (escrito a menudo como _) es también simple: como un nombre variable, empareja cualquier valor, pero no ata el valor a ninguÌn nombre.
Patrones del árbol
Patrones más complejos se pueden construir los primitivos de la sección anterior, generalmente de la misma forma que los valores son construidos combinando otros valores. La diferencia entonces es ésa con las piezas de la variable y del comodín, un patrón no se incorpora a solo valor, sino empareja un grupo de valores que sean la combinación de los elementos concretos y los elementos que se permiten variar dentro de la estructura del patrón.
Un patrón del árbol describe una parte de un árbol comenzando con un nodo y especificando algunas ramas y nodos y dejando alguno sin especificar con una variable o un patrón del comodín. Puede ayudar a pensar en el árbol de abstract syntax de los tipos algebraicos de un lenguaje de programación y de datos
En Haskell, la línea siguiente define un tipo de datos algebraico Color que tenga un solo constructor ColorConstructor de los datos que envuelva un número entero y una secuencia. color de los datos = secuencia del número entero de ColorConstructor
El constructor es un nodo en un árbol y el número entero y la secuencia son hojas en ramas.
Cuando queremos escribir las funciones para hacer Color un el tipo de datos abstracto, deseamos escribir funciones al interfaz con el tipo de datos, y queremos así extraer un ciertos datos del tipo de datos, por ejemplo, apenas la secuencia o apenas la pieza de número entero de Color.
¿Si pasamos una variable que sea de tipo color, cómo podemos salir los datos de esta variable? Por ejemplo, para que una función consiga la pieza de número entero de Color, podemos utilizar un patrón simple del árbol y escribir: integerPart (_ del theInteger de ColorConstructor) = theInteger
También: stringPart (_ de ColorConstructor theString) = theString
Las creaciones de estas funciones se pueden automatizar por el sintaxis del expediente de datos de Haskell.
Datos de filtración con los patrones
La adaptación de modelos se puede utilizar para filtrar datos de cierta estructura. Por ejemplo, en Haskell una comprensión de la lista se podía utilizar para esta clase de filtración:
x | X < - [A 1, B 1, A 2, B 2]
evalúa a 1, A 2
Adaptación de modelos en Mathematica
En el Mathematica, la única estructura que existe es el árbol, que es poblado por símbolos. En el sintaxis de Haskell usado hasta el momento, esto se podía definir como datos SymbolTree = secuencia de símbolo Un árbol del ejemplo podía entonces mirar gusto " del símbolo; a" " b" [, " del símbolo; c" ]
En el sintaxis tradicional, más conveniente, se escriben los símbolos mientras que son y los niveles del árbol se representan usar, de modo que por ejemplo a sea un árbol con a como el padre, y b y c como los niños.
Un patrón en Mathematica implica el poner del " _" en las posiciones en ese árbol. Por ejemplo, el patrón
A
Emparejará elementos tales como A, A, o más generalmente A donde está cualquier entidad el x . En este caso, A es el elemento concreto, mientras que el _ denota el pedazo de árbol que puede ser variado. Un símbolo prepended al _ ata el fósforo a ese nombre variable mientras que un símbolo añadido al _ restringe los fósforos a los nodos de ese símbolo.
Los elementos filtrantes de la función Cases de Mathematica de la primera discusión que emparejan el patrón en la segunda discusión:
Casos, b, a, b}, a]
evalúa a
{a, a}
La adaptación de modelos se aplica a la estructura del de expresiones. En el ejemplo abajo,
Casos, a, a, d], a, d], a, d, e]}, a, _]]
vueltas
{a, d], a, d]}
porque solamente estos elementos emparejarán el a del patrón, el _] arriba.
En Mathematica, es también posible extraer las estructuras como se crean en el curso del cómputo, sin importar cómo o donde aparecen. La función Trace se puede utilizar para supervisar un cómputo, y vuelve los elementos que se presentan que emparejan un patrón. Por ejemplo, podemos definir la secuencia de Fibonacci como
bola: =1 bola: = bola + bola
Entonces, podemos hacer la pregunta: ¿La bola dada, cuál es la secuencia de llamadas recurrentes de Fibonacci?
Rastro, bola]
vuelve una estructura que represente las ocurrencias de la bola del patrón en la estructura de cómputo:
{bola, {bola, {bola}, {bola}}, {bola}}
Programación declarativa
En lenguajes de programación simbólicos, es fácil tener patrones como discusiones a las funciones o como elementos de las estructuras de datos. Una consecuencia de esto es la capacidad de utilizar patrones para hacer declarativamente declaraciones sobre pedazos de datos y para dar instrucciones fexiblemente funciones cómo funcionar.
Por ejemplo, la función Compile de Mathematica se puede utilizar para hacer versiones más eficientes del código. En el ejemplo siguiente los detalles no importan particularmente; qué importa es que el subexpression da instrucciones Compile que las expresiones de COM de la forma se puedan asumir para ser los números enteros para los propósitos de la compilación:
COM: = binomio i Compilar {i, _Integer}}, el x^com [i,]
Las cajas en el Erlang también trabajan esta manera.
Adaptación y secuencias de modelos
En gran medida la forma más común de adaptación de modelos implica cadenas de carácteres. En muchos lenguajes de programación, un sintaxis particular de secuencias se utiliza para representar las expresiones regulares, que son patrones que describen carácteres de la secuencia.
Sin embargo, es posible realizar una cierta adaptación de modelos de la secuencia dentro del mismo marco que se ha discutido a través de este artículo.
Patrones del árbol para las secuencias
En Mathematica, las secuencias se representan como árboles de la raíz StringExpression y todos los carácteres en orden como niños de la raíz. Así, emparejar el " cualquier cantidad de characters" que se arrastra;, un nuevo _ del comodín es necesario en contraste con el _ que emparejaría solamente un solo carácter.
En Haskell y lenguajes el de programación funcional las secuencias se representan generalmente mientras que el funcional enumera de carácteres. Una lista funcional se define como una lista vacía, o elemento construido en una lista existente. En el sintaxis de Haskell: -- una lista vacía x: xs -- un elemento x construyó en xs de una lista
La estructura para una lista con algunos elementos es así element: list. Cuando la adaptación de modelos, nosotros afirma que cierto pedazo de datos es igual a cierto patrón. Por ejemplo, en la función: cabeza (elemento: lista) = elemento
afirmamos que el primer elemento de la discusión de head está llamado elemento, y la función vuelve esto. Sabemos que éste es el primer elemento debido a la manera que se definen las listas, un solo elemento construido sobre una lista. Este solo elemento debe ser el primer. La lista vacía no emparejaría el patrón en absoluto, pues una lista vacía no tiene una cabeza (el primer elemento se construye que).
En el ejemplo, no tenemos ninguÌn uso para list, así que podemos desatenderlo, y escribimos así la función: cabeza (elemento: _) = elemento
Se expresa la transformación de Mathematica del equivalente como
_ principal: =element
Patrones de la secuencia del ejemplo
En Mathematica, por ejemplo,
_ De StringExpression
emparejará una secuencia que tenga dos carácteres y comience con el " a".
El mismo patrón en Haskell:
_
Las entidades simbólicas se pueden introducir para representar muchas diversas clases de características relevantes de una secuencia. Por ejemplo,
StringExpression DigitCharacter
emparejará una secuencia que consista en una letra primero, y entonces un número.
En Haskell, los protectores podrían ser utilizados para alcanzar los mismos fósforos:
dígito | dígito del isDigit del && de la letra del isAlpha
La ventaja principal de la manipulación de secuencia simbólica es que puede ser integrada totalmente con el resto del lenguaje de programación, algo que siendo una subunidad del propósito separado, especial. La energía entera de la lengua se puede leveraged aumentó los patrones ellos mismos o analiza y transforma los programas que los contienen.
Historia
Los primeros programas de computadora para utilizar la adaptación de modelos eran editores de textos. En los laboratorios de Bell, el Ken Thompson amplió buscar y las características de reemplazo del redactor QED para aceptar las expresiones regulares de programación temprano lenguajes con las construcciones de la adaptación de modelos incluyen el SNOBOL a partir de 1962, el NPL a partir de 1977, y el KRC a partir de 1981. El primer lenguaje de programación con las características árbol-basadas de la adaptación de modelos era extensión de Fred McBride del lisp, en 1970.
considera también:
expression#History regular
SNOBOL
considera también: SNOBOL
Ver también
reconocimiento de patrón para los patrones borrosos
: Categoría: Adaptación de modelos para los artículos acerca de la adaptación de modelos de la secuencia
AIML para una lengua del AI basada en patrones que emparejan en discurso
SNOBOL para un lenguaje de programación basado en una clase de adaptación de modelos
Expresiones regulares compatibles del Perl PCRE, una puesta en práctica moderna común de la adaptación de modelos de la secuencia virada hacia el lado de babor a muchas idiomas
Unificación, un concepto similar en el prólogo .
Tom (lengua) de la adaptación de modelos
.
| Random links: | Pedro GY | Figbird | Inmunoglobulina G | Lista de líderes estatales en 1878 | División de la escuela de los ríos de Saskatchewan |