Partial application is not Schönfinkeling

The wages of pedantry

Foreach Mutation

| Comments

Many languages have adopted some form of the “foreach” keyword, for traversing elements of a collection. The advantages are obvious: fencepost errors are impossible, and programs are easier to read. Foreach loops are not places where I expect to find bugs. But about a month ago, I found one, in a piece of code similar to the code below. The expected behavior of the program is to print out the numbers zero and one, on separate lines. Do not read past the end of the program if you want to find the bug yourself, because I explain it below.

(foreach.py) download
1
2
3
4
5
6
7
8
9
10

nums = [0, 1]
numclosures = []
for num in nums:
    numclosures.append(lambda: num)
for numclosure in numclosures:
    print numclosure()

# output from Python 2.5.2
# 1
# 1

The solution has to do with the implementation of the for loop in python. (I ran the program in cpython; it may be interesting to see what other implementations of python do.) Rather than creating a new binding for the num variable on every iteration of the loop, the num variable is mutated (probably for efficiency or just simplicity of implementation). Thus, even though numclosures is filled with distinct anonymous functions, they both refer to the same instance of num.

I tried writing similar routines in other languages. Ruby and C# do the same thing as Python:

(foreach.rb) download
1
2
3
4
5
6
7
8
9
10
11
12

nums = Array[0, 1]
numclosures = Array.new
for num in nums
    numclosures.push lambda { return num }
end
for numclosure in numclosures
    print numclosure.call, "\n"
end

# output from Ruby1.8
# 1
# 1
(foreach.cs) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

using System;
using System.Collections.Generic;

public static class Foreach
{
    public delegate int NumClosure(); // Func<int> does not exist in the latest Mono???

    public static void Main()
    {
        int[] nums = new int[] { 0, 1 };
        List<NumClosure> numclosures = new List<NumClosure>();
        foreach (int num in nums)
        {
            numclosures.Add(delegate() { return num; });
        }
        foreach (NumClosure numclosure in numclosures)
        {
            Console.WriteLine(numclosure());
        }
    }
}

// output from Mono 1.2.6
// 1
// 1

Please excuse the use of the NumClosure delegate. For some reason I could not get Mono to compile with Func.

Fortunately, all of these languages provide some kind of work-around. Ruby has Array#each, and C# has List<>.ForEach. Python has the map built-in.

(foreach_rebind.py) download
1
2
3
4
5
6
7
8
9
10
11

nums = [0, 1]
numclosures = []
def body(num):
    numclosures.append(lambda: num)
map(body, nums)
for numclosure in numclosures:
    print numclosure()

# output from Python 2.5.2
# 0
# 1
(foreach_rebind.rb) download
1
2
3
4
5
6
7
8
9
10
11
12

nums = Array[0, 1]
numclosures = Array.new
nums.each { |num|
    numclosures.push lambda { return num }
}
for numclosure in numclosures
    print numclosure.call, "\n"
end

# output from Ruby1.8:
# 0
# 1
(foreach_rebind.cs) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

using System;
using System.Collections.Generic;

public static class Foreach
{
    public delegate int NumClosure(); // Func<int> does not exist in the latest Mono???

    public static void Main()
    {
        int[] nums = new int[] { 0, 1 };
        List<NumClosure> numclosures = new List<NumClosure>();
        new List<int>(nums).ForEach(delegate (int num)
        {
            numclosures.Add(delegate() { return num; });
        });
        foreach (NumClosure numclosure in numclosures)
        {
            Console.WriteLine(numclosure());
        }
    }
}

// output from Mono 1.2.6
// 0
// 1

Not everybody mutates their enumerators, however. Lisp, the language which normally requires every programmer to be an expert in variable scoping, handles iteration very cleanly:

(foreach.cl) download
1
2
3
4
5
6
7
8
9
10
11

(let ((nums (list 0 1))
      (numclosures (list)))
  (progn
    (dolist (num nums)
      (push #'(lambda () num) numclosures))
    (dolist (numclosure numclosures)
      (format t "~a~%" (funcall numclosure)))))

; output from SBCL 1.0.11.debian
; 1
; 0

And despite its messy syntax, Perl also scores a 10 for clean variable semantics:

(foreach.pl) download
1
2
3
4
5
6
7
8
9
10
11
12

my @nums = (0, 1);
my @numclosures = ();
for my $num (@nums) {
  push (@numclosures, sub { return $num; });
}
for my $numclosure (@numclosures) {
  print &$numclosure() . "\n";
}

# output from Perl 5.8.8:
# 0
# 1

Comments