CSC/ECE 517 Fall 2011/ch1 1c cm

From Expertiza_Wiki
Jump to navigation Jump to search

Introduction

Closures are first-class functions that capture the bindings of free variables in the lexical scope in which they are defined. Closures are associated with functional programming. Functional programming is a programming paradigm in which higher-order functions act on other functions. Functional programming is motivated by lambda calculus which dates back to the 1930s. Object-oriented programming dates back to the 1960s. One of the first languages to implement this ideology was SIMULA. Objects in object-oriented programming are first-class entities that themselves contain instance data, referred to as fields or data members, and procedures or functions called methods. These methods can act on the instance data stored in an object instance. While object-oriented programming is widely (almost universally) used today, there are some tasks or problems that are solved more concisely, more extensibly, or more elegantly using closures than methods. Some of these tasks include iterating across a collection and performing some computation for each item in the collection, callbacks, parallelized reduction, policy enforcement, deferred execution, and continuations. In addition the functional programming style that relies upon closures offers a more declarative style of programming that often leads to better readability and less code to maintain.

Definitions

Closures

"A closure is a function that captures the bindings of free variables in its lexical context."[gafter] In other words, a closure is a block of executable code together with a reference to the variables in scope at the site of its creation. These free variables are captured by the closure, and their lifetime is extended throughout the lifetime of the closure.

Closures can be created by defining a function within the body of another function as the following example illustrates. Note that the scope of the parameter n is limited to the inside of the addGen function. However, because addGen returns a closure, that closure has access to n whenever it is evoked. 

def addGen(n)
    Proc.new { |x| x + n }
end

add5 = addGen(5)
add10 = addGen(10)

puts add5(6)      # 11
puts add10(6)     # 16

First-class functions

Closures are typically implemented as first-class functions. A first-class function is a function that can appear anywhere in a program that other first-class values (such as a number or a string) can appear. Namely, a first-class function can be assigned to a variable, passed as an argument to another function, and returned as the return value from a function.

Execution-time environment contains free variables

Early functional programming languages such as LISP relied upon dynamic scoping in which free variables are bound at run-time to the first matching variable name in the call stack. First the compiler would look inside the function for a definition of each variable. If none was found, it would next look at the calling function, and so on.

An example of dynamic scoping in a JavaScript-like language: 

function alertX() {
    alert(x);           // Note that with dynamic scoping, x need not be defined at the site of the function declaration
}

function fun1() {
    var x = 10;
    alertX();           // 10
}

function fun2() {
    var x = "hello";
    alertX();           // hello
}

Closures, on the other hand, capture variables that are in scope at the time they are created, and the lifetime of those captured variables is extended throughout the lifetime of the closure. This is called lexical or static scoping. Free variables must be defined at compile time -- hence the name static scoping as opposed to dynamic scoping, where the values of free variables can only be known at run time. Closures were first implemented in the Scheme programming language in the 1960s.

The following example illustrates the fact that free variables inside of a closure are in fact bound to the variables defined at the site of the closure's definition. Here we have a function multipleClosures that returns two closures that both act on the variable i. Both are able to act on i though it is not in scope at the site where they are called but rather at the site where they were defined. 

def multipleClosures
i = 0
[ Proc.new { i = i + 1 }, Proc.new { i = i - 1 } ]
end

closures = multipleClosures

puts closures[0].call    # 1
puts closures[0].call    # 2
puts closures[1].call    # 1

Methods

Object-oriented programming dates back to at least the middle 1960's. One of the fundamental principals of objects is the notion of encapsulation. One of the earliest descriptions of the methodology, dates back to a 1966 paper describing the SIMULA, a language designed to ease simulation of large systems. The SIMULA language used classes to encapsulate coupled procedures and data into an object, “an object is a self-contained program (block instance) having its own local data and actions defined by a 'class declaration'” [pg 6, Simula]. This 50 year-old concept of fields and procedures is central to the design of today's object-oriented languages such as Smalltalk, Java and C++. The method will be defined using the following criteria:

  • An object as first-class data which allows binding of
  1. finite set of static or instance data (commonly referred to as fields) created by the programmer which hold the state of the object referenced in the method call with implicit this or self
  2. procedures or actions modifying the data to change the state of the object

Instance or static class functions

Our definition of a method requires functions which can be bound to a first-class object. All object-oriented languages provide this construct. We can create objects and pass those objects around to be executed by other objects or in the global environment. Methods receive an implicit 'this' pointer which givens the execution context access to fields of the object.

Execution-time environment contains instance or static variables

The second point of the method definition is that the we can bind static or instance data to our first-class data object. All object-oriented language also provide this construct.

Closures vs. Methods - Benefits of Closures

Where the benefits of methods have been demonstrated in object-oriented systems, closures are finding their way into languages which haven't had them in the past, like C++ and Java. The C++ proposal for extending the language lists some of the benefits of supporting closures in the traditionally OO language, including notational simplicity, code sharing of common algorithms, and generality [Lamba]. The IBM developerWorks site article lists the some common usages of closures as customization, iterating across collections, and managing resources and enforcing policy.

We will broadly break these down into examples where Closure provide a clean implementation.

  • Generic algorithms - iterating across collections
  • Callbacks - customizing behavior
  • Managing resources and enforcing policy (this is new)
  • Deferred execution
  • Continuations
  • Declarative syntax leads to less code

Generic Algorithms

We can break the generic algorithms down further into the following examples.

  • basic algorithm syntax
  • parameter currying
  • parallel programming (e.g. the map-reduce problem)

Basic Algorithms

The C++ proposal makes light of the fact that closures provide the ability to inject code into generic routines without the programmer having to provide adapters. "The lack of a syntactically light-weight way to define simple function objects is a hindrance to the effective use of several generic algorithms in the Standard Library" [C++]

The classic for_each template algorithm in C++ is called using the following syntax: 

template <class InputIterator, class OutputIterator, class UnaryFunction>
OutputIterator transform(InputIterator first, InputIterator last,
                         OutputIterator result, UnaryFunction op);
{
   for ( ; first != last; ++first, ++result ) *result = op(*first);
   return result;
}

Because C++ does not have Closures, the fourth parameter requires either a named function or an object which supports "operator ()". 

// static function
int multiply_2(int x) 
{
   return x * 2;
}
class multiply_it
{
   int multiplier;
   multiple_it(int x) : multiplier(x) {}
   int operator()(int x) const { return x * multiplier }
}

std::vect test(3,10);
std::vect output(3);

std::transform( test.begin(), test.end(), output.begin(), multiply )
std::transform( test.begin(), test.end(), output.begin(), multiply_it(2) )

If we use the static function and we want to change the multiply function, we either have to create a new named function or create a global variable and make sure the global variable is set correctly before the function is executed. Using the function object, we have can easily change the multiplier, but we were forced to create and manage a new class specifically for the integer multiply.

Consider the same code using Ruby and a Closure where the each function where the developer can pass a code block. 

test = [10,10,10]
output = test.collect { |x| x * 2 }

The Closure is syntactically much cleaner.

Specialization / currying parameters

Currying generically refers to the act of transforming a procedure that takes multiple parameters and converting it to one that takes fewer. [wikipedia] Currying allows creation of specialized versions of generic functions using parameters bound by the closing environment. In languages without closure support it is necessary to explicitly create specialized classes containing the fields needed to call the generic function.

A very simple example in Ruby that make use of an enclosing environment are a CSV line reader and an XML tag reader built from the string scan method, itself a method that can 

def splitter( type )
  in_regex = type
  lamba { |in_line|
    in_line.scan(in_regex)
    if block_given? 
      result.each { |value| yield(value) }
    else
      result
    end
  }
end

cvs_splitter = splitter(/[^,]+/)
xmltag_splitter = splitter(/<[^>]+>/)

cvs_splitter.call("bob,fred");               # returns a list of fields
xmltag_splitter.call("<name>text</name>");   # returns a list of tags

Building the same function in C++ again requires a specialization. 

class Splitter {
  public:
    Splitter( boost::regex &in_regex ) : mregex(in_regex) {}
    std::vector operator()(std::string in_string) { [implement function to return list] } 
  private:
    boost::regex mregex;
};

Splitter cvs_splitter("/[^,]+/);
Splitter xmltag_splitter("/<[^>]+>/");

For these simple types of functions, the Closure provides some benefit but a class specialization can provide the same function.

Parallel Programming - map-reduce

Google popularized the technique of Map Reduction with its search algorithm that simultaneously runs the same search algorithm on multiple threads and combines the results to produce a single answer. Within a programming environment Closures allow parallelized reduction.

The following Ruby example is taken from [pg 382, Ruby] as an example of performing a multi-threaded concurrent map and reduce using a thread per file. The Closure provides a thread context and simple function which counts lines in each file and populates a map which is reduced to a total number of lines in all files. 

module Enumerable
  def con_map(&block)
    threads = []
    self.each do |item|
        threads << Thread.new { block.call(item) }
    end
    threads.map { |t| t.value }
  end
end

input = ['file1.txt','file2.txt','file3.txt']
lines = {}

output = input.con_map { 
  |file| 
  lines[file] = 0
  IO.foreach(file) { 
    |in_line| lines[file] += 1
    puts "adding #{file} #{lines[file]} #{in_line}\n"
  }
  lines[file]
}.reduce {
  |total, val| total+=val
}

Callbacks

Callbacks are often cited as the most desirable application of Closures because the environment around the callback is initialized without programmer intervention. In languages that don't provide Closures, interfaces, fields, or even parameters may have to be added to provide thunking and state information to object being called.

There are several forms of callbacks that can demonstrate this capability.

  • GUI behavior injection
  • generic exception handling

GUI behavior Injection

Behavior injection is used heavily in Javascript libraries where they allow the creation of generic libraries which can be easily extended using a provided function.

Below is an example using the JQuery bind method to provide some capability to an event framework. 

$("p").bind("mouseenter", 
   function(event) {
     $(this).toggleClass('someclass');
   }
)

The Closure is created in the context of each selected DOM object (in this case those objects with type of "p"). The anonymous function is then called when the "mouseenter" event fires. The context of the this pointer is unique to each DOM object because the Closure captured the environment (object) at the time of function creation.

Consider the same callback behavior in a language like Java which does not provide Closures. 

public class MouseClick implements MouseListener {
  [... class implementation ...]
  public void mousePressed(MouseEvent e) {
   this.toggleClass;
  }
}
window.addMouseListener( [instance of MouseClick class] );

We must first define the interface or function which will provide the callback. It must provide the context under which the callback will execute. If we want access to more of the environment we must make provisions in the MouseClick class by adding state variables or pointers to the environment under which it was instanced.

Generic Exception Handling

It can be useful in exception handling because the context of the execution is maintained in the Closure. There is a guarantee that the objects referenced will still be in scope when the exception is taken. 

def exception_handler( &cleanup )
  lambda {
    begin
      yield
    rescue e
      cleanup.call(e)
    end
  }
end

ex_handler = exception_handler { puts "Just another Error" }

ex_handler.call {
  File.open("text.txt","r")
}

Resource Management / Policy Enforcement

Closures allow the creation of policies within an application or class. Closures allow injection of user specified code within the generic policy.

  • maintaining resources
  • resource policy

Maintaining Resources - Simple

This often cited example shows the encapsulation of file base policy using a C++ and a Ruby Closure. [wikipedia-RAII] 

class file {
  public:
    file(const char* filename)
      : file_(std::fopen(filename, "w+")) {
    }
 
    ~file() {
      std::fclose(file_)
    }
 
    void write(const char* str) {
      fputs(str, file_);
    }
 
  private:
    std::FILE* file_;
 
    // prevent copying and assignment; not implemented
    file(const file &);
    file& operator=(const file &);
};

file logfile("logfile.txt"); // open file (acquire resource)
logfile.write("A line in the log\n");

A Ruby Closure showing the same example. 

def log_write(filename)
  in_filename = filename
  logfile = File.open(in_filename, "w+")
  lambda { |output|
    logfile.write(output)
  }
end

log_writer = log_write("logfile.txt")

log_writer.call("A line in the log\n")

The Closure is created with the file handle and the file name in scope. When the Closure goes out of the scope the file handle will be closed.

Resource Policy

The IBM developerWorks site gives an excellent example of an database policy that could be implemented in Ruby. 

def transaction_handler
   lambda {
     begin
        setup_transaction
        yield
        commit_transaction
     rescue
        roll_back_transaction
     end
   }
end

The user of this policy would be able to define a transaction_handler, providing a Closure that will execute between steps of setup and commit.

The Ruby ActiveRecord library makes extensive use of this pattern to provide multiple callbacks throughout record creation: before_validation_on_create, validation_on_create, after_validation_on_create, before_create, after_create.

Deferred execution

Closures are subject to deferred execution. This means that they can be constructed, passed around, and executed at a later time or not at all. This saves the computer from performing unnecessary computations.

An example of deferred execution using LINQ in C# 3.5 or higher: 

List<Person> peeps = new List<Person>
{
    new Person { Name = "Joe", Age = 29, Occupation = "Plumber" },
    new Person { Name = "Mary", Age = 44, Occupation = "Teacher" },
    new Person { Name = "Bob", Age = 56, Occupation = "Teacher" }
};

string occupation = "Teacher";
            
IEnumerable<int> agesOfPeopleInOccupation = peeps.Where(p => p.Occupation == occupation).Select(p => p.Age);    // Because of deferred execution, the list is not enumerated here.

occupation = "Plumber";

double average = agesOfPeopleInOccupation.Average();    // Average() causes the list to be enumerated. Because occupation is now set to "Plumber", that is the value used to filter the list.

Console.WriteLine(average)    // 29.0

Continuation Passing Style

Continuation Passing Style (CPS) in functional programming allows a programmer to finish a process at a later time. A method implementing CPS takes as an argument a function (closure) that is to be called instead of returning a value. The supplied function is instead invoked with the return value.

The following example is taken from [1]. The ICommandExecutor has two methods, which both implement CPS by requiring a closure to be passed as an argument. 

public interface ICommandExecutor
{
    // Execute an operation on a background thread that
    // does not update the user interface

    void Execute(Action action);


    // Execute an operation on a background thread and
    // update the user interface using the returned Action

    void Execute(Func<Action> function);
}

public class Presenter
{
    private readonly IView _view;
    private readonly IService _service;
    private readonly ICommandExecutor _executor;

    public Presenter(IView view, IService service, ICommandExecutor executor)
    {
        _view = view;
        _service = service;
        _executor = executor;
    }

    public void RefreshData()
    {
        _executor.Execute(() =>
        {
            var data = _service.FetchDataFromExtremelySlowServiceCall();
            return () => _view.UpdateDisplay(data);
        });
    }
}

Declarative syntax leads to less code

Functional programming leads to more declarative programming where a programmer specifies what he wants to do rather than how to do it.

To illustrate, we will again use LINQ and C#. In this example we tell the compiler to sort, filter, and partition a list of elements without ever specifying how it is to be done. The logic to do so has been written once by the language developers and can be reused in a multitude of ways by passing in lambda expressions (closures). 

List<Person> peeps = new List<Person>
{
    new Person { Name = "Joe", Age = 29, Occupation = "Plumber" },
    new Person { Name = "Mary", Age = 44, Occupation = "Teacher" },
    new Person { Name = "Bob", Age = 56, Occupation = "Teacher" },
    new Person { Name = "John", Age = 23, Occupation = "Teacher" },
    new Person { Name = "Susan", Age = 39, Occupation = "Plumber" }
};

var subset = peeps.OrderBy(p => p.Age).Where(p => p.Occupation == "Teacher").Take(2);

foreach (Person p in subset)
    Console.WriteLine(p.Name + " ");      // John Mary

Topical References

External Links

[C++] Stroustrup, Bjarne and Jeremiah Willcock, Jaakko Jarvi, Doug Gregor, and Andrew Lumsdaine. "Lamba expressions and closures for C++", Technical Report N1968, ISO/IEC JTC 1, Information Technology, Subcommittee SC 22, Programming Language C++, 2006 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1968.pdf

[Ruby] Flanagan, David and Yukihiro Matsumoto, The Ruby Programming Language. Sebastopol: O'Reilly Media, Inc., 2008. http://oreilly.com/catalog/9780596516178

[wikipedia-RAII] http://en.wikipedia.org/wiki/Resource_Acquisition_Is_Initialization

http://martinfowler.com/bliki/Closure.html

http://gafter.blogspot.com/2007/01/definition-of-closures.html

http://jibbering.com/faq/notes/closures/

http://onestepback.org/articles/invitationtoruby/reason4.html

http://www.skorks.com/2010/05/closures-a-simple-explanation-using-ruby/

http://www.ibm.com/developerworks/java/library/j-cb01097/index.html

http://samdanielson.com/2007/9/6/an-introduction-to-closures-in-ruby

http://csharpindepth.com/Articles/Chapter5/Closures.aspx

http://en.wikipedia.org/wiki/Closure_(computer_science)

http://ynniv.com/blog/2007/08/closures-in-python.html

http://msdn.microsoft.com/en-us/magazine/ee309512.aspx

http://www.randomhacks.net/articles/2007/02/01/some-useful-closures-in-ruby

http://weblog.raganwald.com/2007/01/closures-and-higher-order-functions.html

Retrieved from "https://wiki.expertiza.ncsu.edu/index.php?title=CSC/ECE_517_Fall_2011/ch1_1c_cm&oldid=46559"