Ben Biddington

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

Archive for June 22nd, 2009

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 ,

Book review — Clean Code

with one comment

An excellent book by Bob Martin, with tips on often overlooked fundamentals.

3 — Functions

Functions should:

  • Be small.
  • Do one thing, with no side effects.
  • Do something or answer something, not both (command query separation). A function should either change the state of an object (but not its arguments), or return information about an object. Doing both is confusing.
  • Operate at one level of abstraction.
  • Have as few arguments as possible

Arguments

Arguments are required for a function to do its job. Arguments are parameters describing how a function should operate. Zero argument functions (niladic) are ideal, from both understandability and testability perspectives.

Arguments should:

  • Be at the same level of abstraction as the function
  • Describe input, not output. We expect information to go in to a function through its arguments not out (consider mathematical functions — they have no concept of output arguments). Functions should not, therefore, modify their arguments. Passing a list to a function expecting it to be filled when the function returns is incorrect usage. Plus it violates the “do something or answer something”. [TBD: What about functions that accept Streams and write to them? Is this considered modifying an argument?]
  • Not contain flag arguments. Flag arguments imply the method does more than one thing, anyway. Consider splitting the method in two in this case.

Monadic functions

Two common reasons for passing single argument:

  1. To ask a question about it (e.g., File.Exists(“path”)).
  2. To operate on the argument, transform it and return it (e.g., Stream inStream = File.Open(“path”)).

[TBD: TW anthology describes trying to limit classes to two instance fields, is this similar?]

Argument objects

If a function expects more than two or three arguments, it’s likely that at least some of those should be wrapped in their own class. For example:

Circle createCircle(Int32 x, Int32 y, Int32 radius);

Could be refactored to:

Circle createCircle(Point point, Int32 radius);

This is not cheating, provided the resultant object actually makes sense. In the first version, x and y are ordered components of a single value (or concept). You wouldn’t do the same thing with:

void WriteField(Stream outStream, String name);

Here, Stream and String are not components of the same concept.

Error handling is “one thing”

Consider extracting error handling to its own function — so the one thing it does is handle errors. A function written in this style will start with try and do nothing after its catch/finally. [TBD: Give this one a try]

Arguments or instance variables?

[TBD: How doI tell whether to pass a variable as an argument or add it as an instance member of the object?]

Currying is a way to simplify a function signature, but where should the line be drawn?

Perhaps its worth focusing on the arguments that clients would like to be able to supply.

Should instance members only be used for real object state? If an object uses a variable to perform its functions, surely that qualifies as eligible for instance membership?

6 — Objects and data structures

This was perhaps my favourite section (even though it has that cretinous modern Star Trek character on its title page).

Hiding implementation is about more than defining getters and setters on instance fields — it’s about abstractions.

Consider these interfaces:

// 1
public interface Vehicle {
    double getFuelTankCapacity();
    double getGallonsInTank();
}
// 2
public interface Vehicle {
    double getPercentFuelRemaining();
}

(2) is considered preferable, because it is defining an abstraction, rather than exposing data. [TBD: I am not sure about this, though. Shouldn’t I be able to query for internal state? Shouldn’t I be able to see how much gas my vehicle has?].

The reason (2) is preferred is outlined in the next section, data/object anti-symmetry.

Data/Object anti-symmetry

Objects and data structures and virtual opposites, as described by these anti-symmetry rules:

  • Objects hide their data behind abstractions and expose functions that operate on those abstractions.
  • Data structures expose their data and have no meaningful functions

This section goes on to describe the differences between OO and procedural code, using calculating the area of geometric shapes as an example.

The difference in the two alternatives amounts to where you put your behaviour (functions).

If we followed the antisymmetry rules, we’d add a Geometry class that defined an area function. We would have successfully kept our data structures pure, but we’d have to modify the area function whenever we add a new data structure (which violates the open-closed principle).

Procedural code makes it hard to add data structures

The OO approach forces our shapes to implement a polymorphic area function. This is the way I am most used to, however it has a down side: if we want to add new functions, we have to change all of our data structures.

OO code makes it hard to add functions

Also, we have polluted our data structure with functions — our shapes no longer satisfy the anti-symmetry rules. Our shapes are now hybrids.

This, too, shows that objects and data structures are opposites.

Interesting. The final point in the section is that the idea that everything is an object is a myth — sometimes the procedural approach is applicable.

Bob Martin has written more about this in his post about ActiveRecord. Here he makes the case that an object designed as an active record contains both data and behaviour. By definition, a class like this exposes both its innards, and a persistence abstraction.

The Law of Demeter

So, if objects hide data and expose operations, then an object must not expose its internal structure through accessors [TBD: ?].

A module should not know about the innards of the objects it manipulates.

Note: The term object is important, because the law does not apply to data structures. Data structures are supposed to expose their innards — so we’re free to dig as deep into them as we like.

The Law of Demeter:

A function f of class C should only call the methods of:

  • C
  • An object created by f
  • An object supplied as an argument to f
  • An object held as an instance variable of C

Note: f should not invoke methods on the objects returned from these allowed functions either.

Talk to friends not strangers.

11 — Systems

[TBD: Returned the book already]

Written by benbiddington

22 June, 2009 at 17:49

Posted in development, oop

Tagged with , , ,