Ben Biddington

Whatever it is, it's not about "coding"

Closure

leave a comment »

Closures have been floating around lately, cropping up in Ruby as blocks and procs, as well as pure functional languages.

[A closure] is a first-class function with free variables. Such a function is said to be “closed over” its free variables. A closure is defined within the scope of its free variables, and the extent of those variables is at least as long as the lifetime of the closure itself. The explicit use of closures is associated with functional programming and with languages such as MLLisp and Perl. Closures are used to implement continuation passing style, and in this manner, hide state. Constructs such as objects and monads can thus be implemented with closures.

Free variables

A free variable specifies a place holder in an expression. Whether it is bound or free depends on where it is declared with respect to the expression.

It is approximately correct to say:

  • A variable is free if you can substitute a value for it and the resulting expression is meaningful.
  • A variable is bound if the expression is a statement about all the possible values of the variable all at once.  A bound variable is bound by an operator such as the integral sign, a quantifier, or a summation sign.

Or:

  • [A free variable is] An occurrence of a variable in a logic formula which is not inside the scope of a quantifier.
  • [A bound variable] In logic, [is] a variable that occurs within the scope of a quantifier, and cannot be replaced by a constant.

Example:

This expression is considered bound in x, and free in y. This expression holds for all values of x between the limits, but y can take only one value. The variable y stands for a fixed value, not specified inside the expression, while x is bound by the expression definition.

In mathematical examples, it is often mentioned that bound variables cannot be replaced with a constant, otherwise a meaningless expression would result — try replacing x with 1 in the integral above. Clearly d1 doesn’t make any sense.

Interestingly, as shown in the example, this can be applied to language:

Satomi found her book.

In this expression, the pronoun her is ambiguous. It may refer to Satomi, or any female declared outside the current context, or scope. The variable her is free.

A variable in an expression is either free or bound.  It is approximately correct to say:
¨  A variable is free if you can substitute a value for it and the resulting expressions is meaningful.
¨  A variable is bound if the expression is a statement about all the possible values of the variable all at once.  A bound variable is bound by an operator such as the integral sign, a quantifier, or a summation sign.

Free variables in computer programming

In computer programming, a free variable is a variable referred to in a function that is not local (not declared within the scope of the function), or an argument of that function. An upvalue is a free variable that has been bound (closed over) with a closure.

So, in terms of a closure, a free variable is any variable in scope that is declared outside the closure itself, and is not supplied as an argument. By contrast, arguments and locals are always bound.

Closed over free variables

A closure is said to be closed over its free variables, what does that mean? This means completed by. A closure expression is completed by specifying values for its free variables.

[TBD: hoisting — what a complier emits for free variables.

Closures in ruby

Though blocks are like closures in that they’re closed over their free variables, they’re not closures because they’re not really first class functions — a block cannot be passed around like an object.

A block can be converted to a proc, though. Capture a block as a proc using ampersand:

class Simple
    attr_reader :saved_block

    def initialize()
        yield self if block_given?
    end

    def save_block_for_later(&proc)
        @saved_block = proc
    end
end

And the proc can be assigned like:

var_x= 'x'
simple = Simple.new
simple.save_block_for_later { puts "The current value for var_x = '#{var_x}'."}

This closure can then be invoked at a later time — still bound to its free variables — using call:

simple.saved_block.call

Which prints the text:

"This one has var_x defined as 'x'."

And the same as usual to supply arguments:

simple.save_block_for_later do |an_argument|
    puts "The current value for var_x = '#{var_x}', " +
        "and an_argument has been supplied as '#{an_argument}'."
end

simple.saved_block.call 'xxx'

Funargs

The funarg problem — how to manage variable scoping when dealing with first-class functions.

Stack frames and locals

Traditionally, local variable scope is managed using stack frames.

The idea behind a stack frame is that each subroutine can act independently of its location on the stack, and each subroutine can act as if it is the top of the stack.

When a function is called, a new stack frame is created at the current esp location. A stack frame acts like a partition on the stack. All items from previous functions are higher up on the stack, and should not be modified. Each current function has access to the remainder of the stack, from the stack frame until the end of the stack page. The current function always has access to the “top” of the stack, and so functions do not need to take account of the memory usage of other functions or programs.

In short, functions are allocated temporary storage in a stack frame. This frame stores arguments and local variables. The frame is allocated before the function call, and cleaned up at function exit. The problem arises when a function returns another function.

Normally all local variables are removed with the stack frame, however if a function is returned that references locals, i.e.,  a closure, then these variables have to be kept alive.

CPU registers

[In computer architecture], a processor register is a small amount of storage available on the CPU whose contents can be accessed more quickly than storage available elsewhere.

  • ESP: stack pointer for top address of the stack
  • EBP: stack base pointer for holding the address of the current stack frame

In terms of functions, this article describes the roles of the EBP and ESP registers. The ESP register marks the top of the stack

References

Advertisements

Written by benbiddington

22 June, 2009 at 21:24

Posted in development

Tagged with ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: