Fermetures et Grammaires Sans Contexte

Question

Je suis en train de parcourir mon programme pour mon cours d'informatique théorique et dans l'en-tête de Grammaires libres de contexte, il répertorie les "propriétés de fermeture". J'ai parcouru mon manuel sur ce sujet et je l'ai trouvé assez peu. Le peu qu’il a est un peu au-dessus de ma tête pour le moment (je n’ai pas encore suivi le cours) mais je comprends un peu.

Je me demandais si cette idée de fermeture dans les grammaires sans contexte était identique ou liée à l’idée de fermeture dans la programmation fonctionnelle. Autant que je sache, il est question de combiner des grammaires et de résoudre des chevauchements. La section du livre contient de nombreuses parties que je ne comprends pas encore. Je ne suis donc pas sûr que ces idées soient les mêmes.

(Un peu plus de contexte: j'écris un e-mail au professeur pour lui demander s'il est possible de basculer le cours vers Ruby ou Python depuis Perl. Si ces concepts sont liés, cela pourrait être une autre raison d'utiliser Ruby sur Perl. )

Answer 1

Le terme "fermeture" est utilisé de différentes manières, principalement dans un sens en quelque sorte.

• Un opérateur est " fermé sur " un ensemble de valeurs si vous appliquez cet opérateur aux valeurs de l'ensemble produit toujours une valeur de l'ensemble donné. Par exemple, l'addition est fermée sur les entiers, mais la division ne l'est pas (4/2 est intégral, mais 5/2 n'est pas). Ainsi, l’ajout d’entiers est en quelque sorte "complet". dans un sens, cette division n’est pas.

• Le "transitif" la fermeture d'une relation "complète" la relation en suivant (toutes les possibles) plusieurs applications. En termes courants, le concept de "est un descendant de" est la fermeture transitive de la relation "est un enfant de".

• Une "fermeture" fonctionnelle est " terminé " par exemple en spécifiant comment les variables libres doivent être résolues. Dans l'expression du pseudo-code:

  bump = function(x) (x + y)
  

  x est l'argument de bump , mais la définition semble laisser " ouvert " la question de la résolution de y . Par contre, si on définit:

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

  puis invoquer bumper renvoie une fonction qui ajoute l'argument d'origine de bumper à l'argument de la fonction créée, de sorte que:

  add3 = bumper(3)
  

  équivaut à définir:

  add3 = function(x) (x + 3)
  

  La définition imbriquée est " fermée sur " (ou complété par) les variables disponibles au moment de sa définition.

Ainsi, en réalité, les utilisations de "clôture" ont des significations spécifiques différentes et, à première vue, ne semblent pas liées, mais il existe une relation sous-jacente subtile.

Answer 2

Une propriété de fermeture ressemble à ceci: si L et M sont des langages sans contexte, alors L | M le sera aussi. Les fermetures de fonctions sont un moyen d'implémenter des fonctions de première classe. Donc non, ils n’ont pratiquement rien à voir les uns avec les autres.

Pourquoi le même nom, alors? Une fermeture de fonction est "fermée" sur ses variables libres:

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

Ici, n est une variable libre du lambda. Le nom le souligne, car Lisp ne l 'a pas fermé sur les variables libres - ils prendraient leur valeur dans la liaison de la pile présente lors de l'appel de la fonction interne.

La fermeture des propriétés en mathématiques est un peu plus évidente: si un ensemble est fermé sous une opération, appliquer cette opération à l'intérieur de cet ensemble ne vous en sortira pas. Si vous ajoutez des entiers, vous obtenez toujours un entier.

Answer 3

Darius a raison; " propriétés de fermeture " n'ont rien à voir avec les "fermetures de fonctions". Il n’ya que beaucoup de mots à dire: - (

L’idée des propriétés de fermeture s’applique à l’ensemble de la science informatique, mais beaucoup à différentes classes de langues. Les différentes classes de langues sont importantes car vous avez besoin d’une technologie différente pour numériser ou reconnaître un énoncé. Par exemple, les expressions rationnelles peuvent vous indiquer si vous avez un mot réservé, mais elles ne peuvent pas vous dire si vous avez une expression avec des parenthèses équilibrées - pour cela, vous avez besoin d’une grammaire sans contexte.

Les gens sont généralement intéressés par le fait de savoir si vous prenez une langue en particulier et que vous vous croisez ou que vous vous unissez avec une autre langue, ou si vous complétez simplement la langue, obtenez-vous une autre langue dans la même classe. Par exemple, est-il possible d'écrire une expression régulière qui correspond exactement aux jetons qui ne sont pas des mots réservés? Nous pouvons répondre à un "oui" retentissant. parce que les langues ordinaires sont fermées sous complément, c'est-à-dire que le complément d'une langue régulière est lui-même une langue régulière. Ceci est un exemple de propriété de fermeture. Habituellement, la preuve est constructive, c’est-à-dire que non seulement elle vous indique qu’il existe une expression régulière décrivant tous les jetons qui ne sont pas des mots réservés, la preuve de la propriété de fermeture vous indiquera comment trouvez une telle expression régulière.