Closures and Context Free Grammars

Question

I'm looking over my syllabus for my theoretical computer science class and within the heading of Context Free Grammars it lists "closure properties". I have looked through my textbook on this subject and found quite little. The little it does have is a bit above my head at the moment (I haven't taken the course yet) but I understand a little.

I was wondering if this idea of closures within context free grammars is the same as or related to the idea of closures within functional programming. It talks about combining grammars and resolving overlaps as far as I can tell. There are a lot of parts to the section within the book I don't understand yet, so I'm unsure about whether these ideas are the same.

(A little more context: I'm writing an email to the professor asking if the course can be switched to Ruby or Python from Perl. If these concepts are related, that could be another reason we should use Ruby over Perl.)

Answer 1

The term "closure" is used an a variety of ways, mostly tracking back to a Mathematical concept of completion, in some sense.

• An operator is "closed over" a set of values if applying that operator to values from the set always produces a value from the given set. For example, addition is closed over the integers, but division isn't (4 / 2 is integral, but 5 / 2 isn't). So addition of integers is somehow "complete" in a sense that division isn't.

• The "transitive" closure of a relation "completes" the relation by following (all possible) multiple applications. In everyday terms, the concept of "is a descendent of" is the transitive closure of the relation "is a child of".

• A functional "closure" is "completed" by e.g. specifying how the free variables are to be resolved. In the pseudo-code expression:

  bump = function(x) (x + y)
  

  x is the argument to bump, but the definition seems to leave "open" the question of resolving y. On the other hand, if we define:

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

  then invoking bumper returns a function which adds the original argument of bumper to the created function's argument, so that:

  add3 = bumper(3)
  

  is equivalent to defining:

  add3 = function(x) (x + 3)
  

  The nested definition is "closed over" (or completed by) the variables available at the point of its definition.

So, in effect, the uses of "closure" above all have different specific meanings, and at first glance seem unrelated, but there's a subtle underlying relationship.

Answer 2

A closure property is like this: if L and M are context-free languages, then so is L|M. Function closures are a way of implementing first-class functions. So no, they have pretty much nothing to do with each other.

Why the same name, then? A function closure is 'closed over' its free variables:

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

Here n is a free variable of the lambda. The name emphasizes this because Lisp originally didn't close over free variables -- they'd take their value from whatever binding was on the stack when the inner function was called.

Closure for properties in math is a bit more obvious: if a set is closed under an operation, then applying that operation within that set won't take you out of it. If you add integers, what you get is still an integer.

Answer 3

Darius is correct; "closure properties" have nothing to do with "function closures". There are only so many words to go around :-(

The idea of closure properties is applied all over computer science, but it is applied a lot to different classes of languages. The different classes of languages are important because you need different technology to scan or recognize an utterance. For example, regular expressions can tell you if you have a reserved word, but they can't tell you if you have an expression with balanced parentheses---for that you need a context-free grammar.

People are generally interested in whether if you take a particular langauge and you intersect or union with another language, or simply complement the language, do you get another language in the same class. For example, is it possible to write a regular expression that matches exactly those tokens that are not reserved words? We can answer a resounding "yes" because regular languages are closed under complement, that is, the complement of a regular language is itself a regular language. This is an example of a closure property. Usually the proof is constructive, that is, not only does it tell you that there exists a regular expression describing all tokens that are not reserved words, the proof of the closure property will tell you how to find such a regular expression.