Cierres y gramáticas libres de contexto

Question

Estoy revisando mi programa de estudios para mi clase teórica de ciencias de la computación y dentro del encabezado de Gramática libre de contexto enumera las "propiedades de cierre". He revisado mi libro de texto sobre este tema y he encontrado muy poco. Lo poco que tiene está un poco por encima de mi cabeza en este momento (todavía no he tomado el curso) pero entiendo un poco.

Me preguntaba si esta idea de cierres dentro de las gramáticas libres de contexto es la misma o está relacionada con la idea de cierres dentro de la programación funcional. Habla de combinar gramáticas y resolver solapamientos hasta donde puedo decir. Hay muchas partes de la sección dentro del libro que aún no entiendo, así que no estoy seguro de si estas ideas son las mismas.

(Un poco más de contexto: estoy escribiendo un correo electrónico al profesor preguntando si el curso puede cambiarse a Ruby o Python desde Perl. Si estos conceptos están relacionados, esa podría ser otra razón por la que deberíamos usar Ruby sobre Perl. )

Answer 1

El término "cierre" se usa de varias maneras, principalmente rastreando hacia un concepto matemático de finalización, en algún sentido.

• Un operador está " cerrado sobre " un conjunto de valores si aplica ese operador a los valores del conjunto siempre produce un valor del conjunto dado. Por ejemplo, la suma se cierra sobre los enteros, pero la división no (4/2 es integral, pero 5/2 no lo es). Por lo tanto, la suma de enteros es de alguna manera "completa" en un sentido que la división no lo es.

• El "transitivo" cierre de una relación " completa " la relación siguiendo (todas las posibles) múltiples aplicaciones. En términos cotidianos, el concepto de " es un descendiente de " es el cierre transitivo de la relación "es hijo de".

• Un cierre funcional " está " completado " por ej. especificando cómo se resolverán las variables libres. En la expresión de pseudocódigo:

  bump = function(x) (x + y)
  

  x es el argumento para bump , pero la definición parece dejar " abierto " la cuestión de resolver y . Por otro lado, si definimos:

  bumper = function(y) (function(x) (x + y))
  

  luego invocando bumper devuelve una función que agrega el argumento original de bumper al argumento de la función creada, de modo que:

  add3 = bumper(3)
  

  es equivalente a definir:

  add3 = function(x) (x + 3)
  

  La definición anidada se cierra " (o completado por) las variables disponibles en el punto de su definición.

Entonces, en efecto, los usos de " cierre " sobre todo tienen diferentes significados específicos y, a primera vista, parecen no estar relacionados, pero hay una sutil relación subyacente.

Answer 2

Una propiedad de cierre es así: si L y M son lenguajes libres de contexto, entonces también lo es L | M. Los cierres de funciones son una forma de implementar funciones de primera clase. Entonces no, no tienen casi nada que ver el uno con el otro.

¿Por qué el mismo nombre, entonces? El cierre de una función se 'cierra sobre' sus variables libres:

def adder(n): return lambda m: n + m

Aquí n es una variable libre de la lambda. El nombre enfatiza esto porque Lisp originalmente no se cerró sobre las variables libres: tomarían su valor de cualquier enlace que estuviera en la pila cuando se llamó a la función interna.

El cierre de propiedades en matemáticas es un poco más obvio: si un conjunto se cierra bajo una operación, entonces aplicar esa operación dentro de ese conjunto no lo sacará de él. Si agrega números enteros, lo que obtienes sigue siendo un número entero.

Answer 3

Darius está en lo correcto; " propiedades de cierre " no tiene nada que ver con los cierres de funciones. Solo hay muchas palabras :-(

La idea de las propiedades de cierre se aplica en toda la informática, pero se aplica mucho a diferentes clases de idiomas. Las diferentes clases de idiomas son importantes porque necesita una tecnología diferente para escanear o reconocer un enunciado. Por ejemplo, las expresiones regulares pueden decirte si tienes una palabra reservada, pero no pueden decirte si tienes una expresión con paréntesis equilibrados, para eso necesitas una gramática libre de contexto.

La gente generalmente está interesada en saber si toma un idioma en particular y se cruza o se une con otro idioma, o simplemente complementa el idioma, ¿obtiene otro idioma en la misma clase? Por ejemplo, ¿es posible escribir una expresión regular que coincida exactamente con los tokens que son no palabras reservadas? Podemos responder un rotundo "sí". porque los idiomas regulares están cerrados bajo complemento, es decir, el complemento de un lenguaje regular es en sí mismo un lenguaje regular. Este es un ejemplo de una propiedad de cierre. Por lo general, la prueba es constructiva, es decir, no solo le dice que existe una expresión regular que describe todos los tokens que no son palabras reservadas, la prueba de la propiedad de cierre le dirá cómo > encontrar una expresión tan regular.