Closures and Context Free Grammars

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.