CSC/ECE 517 Fall 2012/ch1 1w32 cm: Difference between revisions

From Expertiza_Wiki
Jump to navigation Jump to search
Line 95: Line 95:
== '''CLOSURES IN DYNAMICALLY TYPED LANGUAGES''' ==
== '''CLOSURES IN DYNAMICALLY TYPED LANGUAGES''' ==


 
The following are examples of closure usage in some of the dynamically typed languages.:
      The following are examples of closure usage in some of the dynamically typed languages.:
          
          
===Perl ===
===Perl ===
Line 105: Line 104:
requires that Perl return a proper closure, thus locking in for all time the value that the lexical had
requires that Perl return a proper closure, thus locking in for all time the value that the lexical had
when the function was created.
when the function was created.
 
<pre>
sub make_adder {
sub make_adder {


Line 117: Line 116:


$f2 = make_adder(555);
$f2 = make_adder(555);
</pre>


Now &$f1($n) is always 20 plus whatever $n you pass in, whereas &$f2($n) is always 555 plus
Now &$f1($n) is always 20 plus whatever $n you pass in, whereas &$f2($n) is always 555 plus

Revision as of 08:04, 13 September 2012

       CLOSURES FOR STATICALLY TYPED LANGUAGES    

INTRODUCTION

A closure is a function or reference to a function together with a referencing environment—a table storing a reference to each of the non-local variables (also called free variables) of that function.1 A closure—unlike a plain function pointer—allows a function to access those non-local variables even when invoked outside of its immediate lexical scope.Closures can typically be treated like any other programming language objects, e.g. they can be stored in variables, passed to functions, and so on. 2

The best way to understand closures is to think about an example in Scheme.

(define f (lambda (x)

(lambda (y)

(+ x y))))

This is the simplest non-trivial example using closures. Here f is a function of one argument (x). When you call it, you pass it a single number as an argument, which gets bound to x. The return value from calling the function is another function which takes one argument (lambda (y) ...) This new function always adds x to its input (whichever x was passed when the function was created). 3

Closures are far from new to computer science. They're a standard feature in older languages such as Scheme, Smalltalk, and Lisp, and have more recently made their way into dynamic languages such as Ruby and Groovy. Closures are a natural fit for statically typed, functional Scala, and recently many have argued that they have a place in the Java language, too. 4

IMPORTANCE OF CLOSURES

The uses of closures:

1. They are very usable for making code more clear and readable. And as we all know clean readable short code is a code that is easier to debug and contains fewer bugs.

For example in Java,

    button.addActionListener(new ActionListener() {
        @Override public void actionPerformed(ActionEvent e) {
            System.out.println("Pressed");
        }
    });

Would be replaced (if Java had closures) with:

button.addActionListener( { System.out.println("Pressed"); } );


2. Closures are used to implement continuation-passing style, and in this manner, hide state. Constructs such as objects and control structures can thus be implemented with closures. Closures typically appear in languages in which functions are first-class values—in other words, such languages allow functions to be passed as arguments, returned from function calls, bound to variable names, etc., just like simpler types such as strings and integers.

For example, consider the following Scheme function:

 Return a list of all books with at least THRESHOLD copies sold.
(define (best-selling-books threshold)
  (filter
    (lambda (book)
      (>= (book-sales book) threshold))
    book-list))>

In this example, the lambda expression (lambda (book) (>= (book-sales book) threshold)) appears within the function best-selling-books. When the lambda expression is evaluated, Scheme creates a closure consisting of the code for the lambda expression and a reference to the threshold variable, which is a free variable inside the lambda expression.

The closure is then passed to the filter function, which calls it repeatedly to determine which books are to be added to the result list and which are to be discarded. Because the closure itself has a reference to threshold, it can use that variable each time filter calls it. The function filter itself might be defined in a completely separate file.

Here is the same example rewritten in JavaScript, another popular language with support for closures:

// Return a list of all books with at least 'threshold' copies sold.
function bestSellingBooks(threshold) {
  return bookList.filter(
      function (book) { return book.sales >= threshold; }
    );
}

The function keyword is used here instead of lambda, and an Array.filter method[10] instead of a global filter function, but otherwise the structure and the effect of the code are the same.

3. Code like the following, which is common in functional languages, can be parallelized,without needing to create a pool of worker threads and hand off the closure to them:

	results = map(closure, inputs, [0..numElements-1]);

In these languages, closures take away the pain of declaring a new function somewhere for short pieces of code.

4. Because closures delay evaluation i.e., they do not "do" anything until they are called so they can be used to define control structures. For example,all Smalltalk's standard control structures, including branches (if/then/else) and loops (while and for), are defined using objects whose methods accept closures. Users can easily define their own control structures also. In languages that allow assignment, multiple functions can be produced that close over the same environment, enabling them to communicate privately by altering that environment.

5. A closure can be used to associate a function with a set of "private" variables, which persist over several invocations of the function. The scope of the variable encompasses only the closed-over function, so it cannot be accessed from other program code. In stateful languages, closures can thus be used to implement paradigms for state representation and information hiding, since the closure's upvalues (its closed-over variables) are of indefinite extent, so a value established in one invocation remains available in the next. Closures used in this way no longer have referential transparency, and are thus no longer pure functions; nevertheless, they are commonly used in "near-functional" languages such as Scheme.

CLOSURES IN DYNAMICALLY TYPED LANGUAGES

The following are examples of closure usage in some of the dynamically typed languages.:

Perl

The following is a make_adder() function, in which the returned anonymous function contains a reference to a lexical variable outside the scope of that function itself. Such a reference requires that Perl return a proper closure, thus locking in for all time the value that the lexical had when the function was created.

sub make_adder {

my $addpiece = shift;

return sub { shift + $addpiece };

}

$f1 = make_adder(20);

$f2 = make_adder(555);

Now &$f1($n) is always 20 plus whatever $n you pass in, whereas &$f2($n) is always 555 plus whatever $n you pass in. The $addpiece in the closure sticks around. 11

Ruby

In Ruby, closures are supported through procs and lambdas. These constructs are very similar, but there are some subtle differences (I might do a post about that soon). Let's create a closure and see how it fulfils the two properties described above.

class SomeClass
  def initialize(value1)
    @value1 = value1
  end
 
  def value_printer(value2)
    lambda {puts "Value1: #{@value1}, Value2: #{value2}"}
  end
end
 
def caller(some_closure)
  some_closure.call
end
 
some_class = SomeClass.new(5)
printer = some_class.value_printer("some value")
 
caller(printer)

When we execute we get the following output:

alan@alan-ubuntu-vm:~/tmp$ ruby closures.rb

Value1: 5, Value2: some value

As you can see, the value_printer function creates a closure, using the lambda construct, and then returns it. We then assign our closure to a variable and pass that variable to another function, which then calls our closure. This satisfies the first property of a closure – we can pass it around. Notice also that when we called our closure, we printed out "5" and "some value". Even though both the @value1 and value2 variables were both well and truly out of scope in the rest of the program when we finally called the closure; inside the closure they were still in scope as it retained the state of all the variables that were in scope when it was defined. And so, our lambda satisfies the second property also which makes it a closure. 12

CLOSURES IN STATICALLY TYPED LANGUAGES

While neither Java nor C++ support higher order functions directly, both provide mechanisms for mimicking their behavior. Java's anonymous classes allow a function to be bundled with an object that can be treated much as a higher order function can. It can be bound to variables, passed to other functions as an argument, and can be returned as the result of a function. However, the function itself is named and thus cannot be treated in a generic fashion as true higher order functions can. C++ similarly provides partial support for higher order functions using function objects (or "functors"), and add the further benefit that the function call operator may be overloaded so that functors may be treated generically. Neither C++ nor Java, however, provides any support for lexical closures.


C

The code below, written in C, implements the call unarySumFactory to produce unary sums. C does not have syntactic support for closures. Nevertheless, we can implement closures by combining high-order function calls with dynamic heap allocation. 13


#include <stdio.h>
#include <stdlib.h>

typedef struct struct_free_variables_unarySum {
int x;
} FREE_VARIABLES_unarySum;

typedef struct {
FREE_VARIABLES_unarySum* t;
int (*f)(FREE_VARIABLES_unarySum* t, int x);
} CLOSURE_unarySum;

int unarySum(FREE_VARIABLES_unarySum* t, int y) {
return y + t->x;
};

void* unarySumFactory(int x) {
CLOSURE_unarySum* c = (CLOSURE_unarySum*) malloc (sizeof(CLOSURE_unarySum));
c->t = (FREE_VARIABLES_unarySum*) malloc (sizeof(FREE_VARIABLES_unarySum));
c->t->x = x;
c->f = &unarySum;
return c;

}

int test(int n) {
CLOSURE_unarySum* c = unarySumFactory(2);
int retVal = c->f(c->t, n);
free(c->t);
free(c);
return retVal;
}

int main(int argc, char** argv) {
printf("%d\n", test(argc));
return 0;
}

Java

The following is a code in Java programming without closures

public interface Block<T> {
     void invoke(T arg);
    }
    public class Utils {
     public static <T> void forEach(Iterable<T> seq, Block<T> fct) {
       for (T elm : seq)
       fct.invoke(elm);
     }
    }
    public class Test {
     public static void main(String[] args) {
       List<Integer> nums = Arrays.asList(1,2,3);
       Block<Integer> print = new Block<Integer>() {
         public void invoke(Integer arg) {
           System.out.println(arg);
         }
       };
       Utils.forEach(nums,print);
     }
    }

The example is admittedly contrived and extremely simple, but consider it: how often in Java do you find yourself implementing an interface and passing the implementation to a method for execution? We can think of three immediate examples:

Runnable and Callable, which we pass to threads or thread pools for asynchronous execution. Callback interfaces such as ActionListener, which we register for future execution in case a certain event occurs. Comparator, which we pass to a TreeMap for maintaining its sorting order.

In all these cases we use an interface, providing some functionality as an implementation of the interface. We then pass the functionality to a method for immediate or delayed, synchronous or asynchronous execution. Closures would simplify this process by allowing a more concise syntax, thereby eliminating some of Java's verbosity. Beyond allowing more concise and readable Java source code, closures would add some functionality completely new to Java, such as custom control structures.


Challenges due to lack of closures in Statically typed languages

Consider an example, given a list of employee objects and a list of those employees who are managers is to be created, which can be determined with an IsManager property.

Using C#, it probably would be written like this

public static IList Managers(IList emps)

{

IList result = new ArrayList();

foreach(Employee e in emps)

if (e.IsManager) result.Add(e);

return result;

}

In a language that has Closures, for example, Ruby, it would be written as,

def managers(emps)

return emps.select {|e| e.isManager}

end

Essentially select is a method defined on the Ruby collection class. It takes a block of code, a closure, as an argument. Select iterates through the input array, executes the block of code with each element, and returns an array of those elements for which the block evaluated as true.

The workaround in C could be using a function pointer; in Java with an anonymous inner class; and with a delegate in C#. These mechanisms are similar to closures, but there are two telling differences.

The first difference is closures can refer to variables visible at the time they were defined. Consider this method,

def highPaid(emps)

threshold = 150

return emps.select {|e| e.salary > threshold}

end

Here the code in the select block is referring to a local variable defined in the enclosing method. Many of the alternatives to closures in languages that don't have real closures can't do that. 15

Consider this function,

def paidMore(amount)

return Proc.new {|e| e.salary > amount}

end

This function returns a closure, indeed it returns a closure whose behavior depends on the argument sent into it.

highPaid = paidMore(150)

The variable highPaid contains a block of code (called a Proc in Ruby) that will return whether a tested object has a salary greater than 150.

john = Employee.new

john.salary = 200

print highPaid.call(john)

REFERENCES

  1. Sussman and Steele. "Scheme: An interpreter for extended lambda calculus". "... a data structure containing a lambda expression, and an environment to be used when that lambda expression is applied to arguments." (Wikisource)
  2. Wikipedia: Closure (computer science)
  3. Joe Morrison: Brief introduction to four programming language concepts
  4. Understanding the closures debate Does Java need closures? Three proposals compared By Klaus Kreft and Angelika Langer, JavaWorld.com
  5. perlfaq7 - General Perl Language Issues/ What's a closure?
  6. Alan Skorkin: Closures – A Simple Explanation (Using Ruby)
  7. Wikipedia: Introduction to Programming Languages/Closures
  8. Voegele.com/Programmer’s Corner/Programming Language Comparison
  9. Martin Fowler’s Bliki - Closure