Closures/Value capture: Difference between revisions

Content added Content deleted

Inline

Revision as of 02:32, 13 March 2012

Task: Create a list of 10 functions, in the simplest manner possible (anonymous functions are encouraged), such that the function at index $i$ (you may choose to start $i$ from either 0 or 1), when run, should return the square of the index, that is, $i^{2}$ . Display the result of running any but the last function, to demonstrate that the function indeed remembers its value.

Goal: To demonstrate how to create a series of independent closures based on the same template but maintain separate copies of the variable closed over. In imperative languages, one would generally use a loop with a mutable counter variable. For each function to maintain the correct number, it has to capture the value of the variable at the time it was created, rather than just a reference to the variable, which would have a different value by the time the function was run.

Axiom

Using the Spad compiler: <lang Axiom>)abbrev package TESTP TestPackage TestPackage() : with

    test: () -> List((()->Integer))
  == add
    test() == [(() +-> i^2) for i in 1..10]</lang>

This can be called from the interpreter using: <lang Axiom>[x() for x in test()]</lang>

With output: <lang Axiom>[1,4,9,16,25,36,49,64,81,100]

                                    Type: List(Integer)</lang>

C

Function image copying approach

Non-portable. Copying a function body depends on implementation-specific semantics of volatile, if the replacement target still exists after optimization, if the dest memory is suitably aligned, if the memory is executable, if it makes any function calls to a relative offset, if it refers to any memory location with an absolute address, etc. It only very occasionally works.

<lang c>#include <stdio.h>

include <stdlib.h>
include <string.h>

typedef int (*f_int)();

define TAG 0xdeadbeef

int _tmpl() { volatile int x = TAG; return x * x; }

f_int dupf(int v) { size_t len = (void*)dupf - (void*)_tmpl; f_int ret = malloc(len); char *p; memcpy(ret, _tmpl, len); for (p = (char*)ret; p < (char*)ret + len - sizeof(int); p++) if (*(int *)p == TAG) *(int *)p = v; return ret; }

int main() { f_int funcs[10]; int i; for (i = 0; i < 10; i++) funcs[i] = dupf(i);

for (i = 0; i < 9; i++) printf("func[%d]: %d\n", i, funcs[i]());

return 0; }</lang>output<lang>func[0]: 0 func[1]: 1 func[2]: 4 func[3]: 9 func[4]: 16 func[5]: 25 func[6]: 36 func[7]: 49 func[8]: 64</lang>

Greenspunned mini Lisp dialect

See Closures/Variable_capture/C for complete code. The relevant excerpt is:

<lang c>void init(void) {

 t = intern(lit("t"));
 x = intern(lit("x"));

}

val square(val env) {

 val xbind = assoc(env, x); /* look up binding of variable x in env */
 val xval = cdr(xbind);     /* value is the cdr of the binding cell */
 return num(cnum(xval) * cnum(xval));

}

int main(void) {

 int i;
 val funlist = nil, iter;

 init();

 for (i = 0; i < 10; i++) {
   val closure_env = cons(cons(x, num(i)), nil);
   funlist = cons(func_f0(closure_env, square), funlist);
 }

 for (iter = funlist; iter != nil; iter = cdr(iter)) {
   val fun = car(iter);
   val square = funcall(fun, nao);

   printf("%d\n", cnum(square));
 }
 return 0;

}</lang>

Here, we create an environment explicitly as an association list which we can search with the assoc function. The environment contains a binding for the symbol x. The square function retrieves the value and returns its square.

Output:

$ ./a.out
81
64
49
36
25
16
9
4
1
0

C++

Works with: C++11

<lang cpp>#include <iostream>

include <functional>
include <vector>

int main() {

 std::vector<std::function<int()> > funcs;
 for (int i = 0; i < 10; i++)
   funcs.push_back([=]() { return i * i; });
 std::cout << funcs[3]() << std::endl;

 return 0;

}</lang> Output: <lang>9</lang>

C#

Using Linq

<lang csharp>using System; using System.Linq;

class Program {

   static void Main()
   {
       var captor = (Func<int, Func<int>>)(number => () => number * number);
       var functions = Enumerable.Range(0, 10).Select(captor);
       foreach (var function in functions.Take(9))
       {
           Console.WriteLine(function());
       }
   }

}</lang> Output: <lang>0 1 4 9 16 25 36 49 64</lang>

Using delegates only

<lang csharp> using System; using System.Collections.Generic;

class Program {

   static void Main( string[] args )
   {
       List<Func<int>> l = new List<Func<int>>();
       for ( int i = 0; i < 10; ++i )
       {
           // This is key to avoiding the closure trap, because
           // the anonymous delegate captures a reference to 
           // outer variables, not their value.  So we create 10
           // variables, and each created anonymous delegate 
           // has references to that variable, not the loop variable
           var captured_val = i;
           l.Add( delegate() { return captured_val * captured_val; } );
       }

       l.ForEach( delegate( Func<int> f ) { Console.WriteLine( f() ); } );
   }

} </lang> Output: <lang>0 1 4 9 16 25 36 49 64</lang>

Common Lisp

<lang lisp>CL-USER> (defparameter alist (loop for i from 1 to 10 collect (cons i (let ((i i)) (lambda () (* i i)))))) ALIST CL-USER> (funcall (cdr (assoc 2 alist))) 4 CL-USER> (funcall (cdr (assoc 8 alist))) 64</lang>

The loop mutates its binding i. The purpose of (let ((i i)) ...) is to create a different binding i for each lambda to capture. Otherwise, all 10 lambdas would capture the same binding and return 100.

D

<lang d>import std.stdio;

void main() {

   int delegate()[] funcs;

   foreach (i; 0 .. 10)
       funcs ~= (i => () => i ^^ 2)(i);

   writeln(funcs[3]());

}</lang> Output:

More functional version: <lang d>import std.stdio, std.range, std.algorithm;

void main() {

   auto funcs = map!(i => () => i*i)(iota(10));
   writeln(map!q{ a() }(funcs));

}</lang> Output:

[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

Factor

Using lexical variables

<lang factor>USING: io kernel locals math prettyprint sequences ;

[let

   ! Create a sequence of 10 quotations
   10 iota [
       :> i            ! Bind lexical variable i
       [ i i * ]       ! Push a quotation to calculate i squared
   ] map :> seq

   { 3 8 } [
       dup pprint " squared is " write
       seq nth call .
   ] each

]</lang>

$ ./factor script.factor
3 squared is 9
8 squared is 64

The code :> i always binds a new variable. This happens inside a loop, so this program creates 10 different bindings. Each closure [ i i * ] captures a different binding, and remembers a different value.

The wrong way would use f :> i! 10 iota [ i! [ i i * ] ] map :> seq to mutate a single binding. Then the program would print, "3 squared is 81", "8 squared is 81".

Using fried quotations

Forget the variable! Each fried quotation captures some values by pulling them from the stack.

<lang factor>USING: fry io kernel math prettyprint sequences ;

! Push a sequence of 10 quotations 10 iota [

   '[ _ dup * ]        ! Push a quotation ( i -- i*i )

] map

{ 3 8 } [

   dup pprint " squared is " write
   over nth call .

] each drop</lang>

Fantom

<lang fantom> class Closures {

 Void main ()
 {
   // define a list of functions, which take no arguments and return an Int
   |->Int|[] functions := [,]

   // create and store a function which returns i*i for i in 0 to 10
   (0..10).each |Int i|
   {
     functions.add (|->Int| { i*i })
   }

   // show result of calling function at index position 7
   echo ("Function at index: " + 7 + " outputs " + functions[7].call)
 }

} </lang>

Output:

Function at index: 7 outputs 49

Go

<lang go>package main

import "fmt"

func main() {

   fs := make([]func() int, 10)
   for i := range fs {
       i := i
       fs[i] = func() int {
           return i * i
       }
   }
   fmt.Println("func #0:", fs[0]())
   fmt.Println("func #3:", fs[3]())

}</lang> Output:

func #0: 0
func #3: 9

Groovy

Solution: <lang groovy>def closures = (0..9).collect{ i -> { -> i*i } }</lang>

Test: <lang groovy>assert closures instanceof List assert closures.size() == 10 closures.each { assert it instanceof Closure } println closures[7]()</lang>

Output:

Icon and Unicon

This uses Unicon specific calling sequences for co-expressions. It can be made to run under Icon by modifying the calling syntax.

<lang Unicon>procedure main(args) # Closure/Variable Capture

   every put(L := [], vcapture(1 to 10))                 # build list of index closures
   write("Randomly selecting L[",i := ?*L,"] = ",L[i]()) # L[i]() calls the closure

end

The anonymous 'function', as a co-expression. Most of the code is standard
boilerplate needed to use a co-expression as an anonymous function.

procedure vcapture(x) # vcapture closes over its argument

  return makeProc { repeat { x[1]^2 @ &source } }

end

procedure makeProc(A) # the makeProc PDCO from the UniLib Utils package

   return (@A[1], A[1])

end</lang>

Library: Unicon Code Library

package Utils provides makeProc Summary of Anonymous Functions in Unicon

Sample Output:

Randomly selecting L[8] = 64

J

The natural way of implementing this in J is to define a function which produces a gerund of a constant function.

<lang j>constF=:3 :0

 {.`(y "_)

)</lang>

Thus, a list of 10 functions each producing a value in 0..9, and another with their squares:

<lang j>flist=: constF"0 i.10 slist=: constF"0 *:i.10</lang>

Referencing a function:

<lang j> flist @.3 3"_

  slist @.3

9"_</lang>

Using a function:

<lang j> flist @.4 4

  slist @.4

16</lang>

Running a randomly picked function which is not the last one:

<lang j> flist@.(?9) 7

  slist@.(?9)

25</lang>

JavaScript

<lang javascript>var funcs = []; for (var i = 0; i < 10; i++) {

   funcs.push( (function(i) {
                    return function() { return i * i; }
               })(i) );

} window.alert(funcs[3]()); // alerts "9"</lang>

Works with: JavaScript version 1.7+

(Firefox 2+)

<lang javascript><script type="application/javascript;version=1.7"> var funcs = []; for (var i = 0; i < 10; i++) {

   let (i = i) {
       funcs.push( function() { return i * i; } );
   }

} window.alert(funcs[3]()); // alerts "9" </script></lang>

Mathematica

<lang Mathematica>a[i_] := Function[z, z*z][i]

a[2] ->4

a[5] ->25

a[2] ->4</lang>

Objective-C

Works with: Cocoa version Mac OS X 10.6+

<lang objc>NSMutableArray *funcs = [[NSMutableArray alloc] init]; for (int i = 0; i < 10; i++) {

 [funcs addObject:[[^() { return i * i; } copy] autorelease]];

}

int (^foo)() = [funcs objectAtIndex:3]; NSLog(@"%d", foo()); // logs "9" [funcs release]; </lang>

OCaml

All functions in OCaml are closures.

<lang ocaml>let () =

 let cls = Array.init 10 (fun i -> (function () -> i * i)) in
 Random.self_init ();
 for i = 1 to 6 do
   let x = Random.int 9 in
   Printf.printf " fun.(%d) = %d\n" x (cls.(x) ());
 done</lang>

Output:

 fun.(4) = 16
 fun.(1) = 1
 fun.(4) = 16
 fun.(7) = 49
 fun.(3) = 9
 fun.(6) = 36

PARI/GP

Works with: PARI/GP version 2.4.2 and above

<lang parigp>vector(10,i,()->i^2)[5]()</lang>

Output:

%1 = 25

Perl

<lang perl>my @f = map(sub { $_ * $_ }, 0 .. 9); # @f is an array of subs

print $f[$_](), "\n" for (0 .. 8); # call and print all but last</lang>output

Perl 6

All blocks are anonymous closures in Perl 6, and parameters are lexicals, so it's easy to generate a list of them. We'll use a gather/take generator loop, and call the closures in random order, just to keep things interesting. <lang perl6>my @c = gather for ^10 -> $i {

   take { $i * $i }

}

.().say for @c.pick(*); # call them in random order</lang> Output:

Or equivalently, using a more functional notation: <lang perl6>say .() for pick *, map -> $i { -> {$i * $i} }, ^10</lang>

PHP

Works with: PHP version 5.3+

<lang php><?php $funcs = array(); for ($i = 0; $i < 10; $i++) {

   $funcs[] = function () use ($i) { return $i * $i; };

} echo $funcs[3](), "\n"; // prints 9 ?></lang>

Works with: PHP version pre-5.3

This method can capture value types like numbers, strings, arrays, etc., but not objects. <lang php><?php $funcs = array(); for ($i = 0; $i < 10; $i++) {

   $funcs[] = create_function(, '$i = ' . var_export($i, true) . '; return $i * $i;');

} echo $funcs[3](), "\n"; // prints 9 ?></lang>

PicoLisp

<lang PicoLisp>(setq FunList

  (make
     (for @N 10
        (link (curry (@N) () (* @N @N))) ) ) )</lang>

Test:

: ((get FunList 2))
-> 4

: ((get FunList 8))
-> 64

Pike

<lang Pike>array funcs = ({}); foreach(enumerate(10);; int i) {

 funcs+= ({ 
             lambda(int j)
             {
                 return lambda()
                        { 
                            return j*j; 
                        }; 
             }(i) 
         });

}</lang>

Prolog

Works with SWI-Prolog and module lambda.pl from Ulrich Neumerkel.
lambda.pl can be found there : http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl

<lang Prolog>:-use_module(library(lambda)).

closure :- numlist(1,10, Lnum), maplist(make_func, Lnum, Lfunc), maplist(call_func, Lnum, Lfunc).

make_func(I, \X^(X is I*I)).

call_func(N, F) :- call(F, R), format('Func ~w : ~w~n', [N, R]). </lang> Output :

 ?- closure.
Func 1 : 1
Func 2 : 4
Func 3 : 9
Func 4 : 16
Func 5 : 25
Func 6 : 36
Func 7 : 49
Func 8 : 64
Func 9 : 81
Func 10 : 100
true.

Python

The naive way does not work: <lang python>funcs = [] for i in range(10):

   funcs.append(lambda: i * i)

print funcs[3]() # prints 81</lang>

The simplest solution is to add optional parameters with default arguments at the end of the parameter list, to create a local copy of the variable, and evaluate the variable at the time the function is created. (The optional parameter is not expected to ever be passed.) Often, the optional parameter will be named the same as the variable to be closed over (leading to odd-looking code of the form foo=foo in the arguments), so that the code inside the function need not be changed, but this might lead to confusion. This technique does not work for functions with a variable number of arguments. <lang python>funcs = [] for i in range(10):

   funcs.append(lambda i=i: i * i)

print funcs[3]() # prints 9</lang> or equivalently the list comprehension: <lang python>funcs = [lambda i=i: i * i for i in range(10)] print funcs[3]() # prints 9</lang>

Another solution is to wrap an immediately-executed function around our function. The wrapping function creates a new scope, and its execution forces the evaluation of the variable to be closed over. <lang python>funcs = [] for i in range(10):

   funcs.append((lambda i: lambda: i)(i * i))

print funcs[3]() # prints 9</lang> or equivalently the list comprehension: <lang python>funcs = [(lambda i: lambda: i)(i * i) for i in range(10)] print funcs[3]() # prints 9</lang>

In this case it is also possible to use map() since the function passed to it creates a new scope <lang python>funcs = map(lambda i: lambda: i * i, range(10)) print funcs[3]() # prints 9</lang>

It is also possible to use eval and eliminate the double function <lang python>funcs=[eval("lambda:%s"%i**2)for i in range(10)] print funcs[3]() # prints 9</lang>

R

R is a natural language for this task, but you need to understand the nuances of delayed evaluation. Arguments in R are referred to as promises because they aren't evaluated until first use. If you're not careful, you can bind to a promise that hasn't yet been evaluated, and you won't get what you expect.

assign 's' a list of ten functions

s <- sapply (1:10, # integers 1..10 become argument 'x' below

   function (x) {
       x  # force evaluation of promise x

function (i=x) i*i # this *function* is the return value

})

s5() # call the fifth function in the list of returned functions [1] 25 # returns vector of length 1 with the value 25 </lang>

Note that I bound the captured variable as the default argument on a unary function. If you supply your own argument, as below, it squares the supplied argument and ignores the default argument.

As a further technicality, note that you need some extra voodoo to modify the bound argument with persistence across calls. This example increments the bound variable after each call.

<lang R> s <- sapply (1:10,

   function (x) {
       x  # force evaluation of promise x

function () {

           R <- x*x 
           # evaluate the language expression "x <- x + 1" in the persistent parent environment 
           evalq (x <- x + 1, parent.env(environment()))
           R  # return squared value 
   }})

s5() [1] 25 # 5^2 s5() [1] 36 # now 6^2 s1() [1] 1 # 1^2 s1() [1] 4 # now 2^2 </lang>

As shown, each instance increments separately.

Ruby

This works because i in (1..10).each {|i| ...} is local to its block. The loop calls the block 10 times, so there are 10 different variables to capture.

With Ruby 1.9, i is always local to its block. With Ruby 1.8, i is local unless there is another i in the outer scope. If i is not local, all 10 procs will return 100.

Scala

<lang scala>val closures=for(i <- 0 to 9) yield (()=>i*i) 0 to 8 foreach (i=> println(closures(i)())) println("---\n"+closures(7)())</lang> Output:

Smalltalk

<lang smalltalk>funcs := (1 to: 10) collect: [ :i | [ i * i ] ] . (funcs at: 3) value displayNl .</lang> Output:

Tcl

Tcl does not support closures (either value-capturing or variable-capturing) by default, but value-capturing closures are easy to emulate. <lang tcl>package require Tcl 8.6; # Just for tailcall command

Builds a value-capturing closure; does NOT couple variables

proc closure {script} {

   set valuemap {}
   foreach v [uplevel 1 {info vars}] {

lappend valuemap [list $v [uplevel 1 [list set $v]]]

   }
   set body [list $valuemap $script [uplevel 1 {namespace current}]]
   # Wrap, to stop untoward argument passing
   return [list apply [list {} [list tailcall apply $body]]]
   # A version of the previous line compatible with Tcl 8.5 would be this
   # code, but the closure generated is more fragile:
   ### return [list apply $body]

}

Simple helper, to avoid capturing unwanted variable

proc collectFor {var from to body} {

   upvar 1 $var v
   set result {}
   for {set v $from} {$v < $to} {incr v} {lappend result [uplevel 1 $body]}
   return $result

}

Build a list of closures

proc buildList {} {

   collectFor i 0 10 {

closure { # This is the body of the closure return [expr $i*$i] }

} set theClosures [buildList] foreach i {a b c d e} {# Do 5 times; demonstrates no variable leakage

   set idx [expr {int(rand()*9)}]; # pick random int from [0..9)
   puts $idx=>[{*}[lindex $theClosures $idx]]

}</lang> Sample output:

5=>25
0=>0
8=>64
1=>1
8=>64