Are lambda expressions/delegates in C# "pure", or can they be?

Question

I recently asked about functional programs having no side effects, and learned what this means for making parallelized tasks trivial. Specifically, that "pure" functions make this trivial as they have no side effects.

I've also recently been looking into LINQ and lambda expressions as I've run across examples many times here on StackOverflow involving enumeration. That got me to wondering if parallelizing an enumeration or loop can be "easier" in C# now.

Are lambda expressions "pure" enough to pull off trivial parallelizing? Maybe it depends on what you're doing with the expression, but can they be pure enough? Would something like this be theoretically possible/trivial in C#?:

• Break the loop into chunks
• Run a thread to loop through each chunk
• Run a function that does something with the value from the current loop position of each thread

For instance, say I had a bunch of objects in a game loop (as I am developing a game and was thinking about the possibility of multiple threads) and had to do something with each of them every frame, would the above be trivial to pull off? Looking at IEnumerable it seems it only keeps track of the current position, so I'm not sure I could use the normal generic collections to break the enumeration into "chunks".

Sorry about this question. I used bullets above instead of pseudo-code because I don't even know enough to write pseudo-code off the top of my head. My .NET knowledge has been purely simple business stuff and I'm new to delegates and threads, etc. I mainly want to know if the above approach is good for pursuing, and if delegates/lambdas don't have to be worried about when it comes to their parallelization.

Answer 1

Lambda's should be pure. And then the FrameWork offers automatic paralellization with a simple .AsParallel addition to a LINQ query (PLINQ).

But it is not automatic or guaranteed, the programmer is responsible to make/keep them pure.

Answer 2

Whether or not a lambda is pure is tied to what it is doing. As a concept it is neither pure or impure.

For example: The following lambda expression is impure as it is reading and writing a single variable in the body. Running it in parallel creates a race condition.

var i = 0;
Func<bool> del = () => {
  if ( i == 42 ) { return true; }
  else ( i++ ) { return false; }
};

Contrarily the following delegate is pure and has no race conditions.

Func<bool> del = () => true;

Answer 3

As for the loop part, you could also use the Parallel.For and Parallel.ForEach for the example about the objects in a game. This is also part of .net 4 , but you can get it as a download.

Answer 4

First off, note that in order to be "pure" a method must not only have no side effects. It must also always return the same result when given the same arguments. So, for example, the "Math.Sin" method is pure. You feed in 12, it gives you back sin(12) and it is the same every time. A method GetCurrentTime() is not pure even if it has no side effects; it returns a different value every time you call it, no matter what arguments you pass in.

Also note that a pure method really ought not to ever throw an exception; exceptions count as observable side effects for our purposes.

Second, yes, if you can reason about the purity of a method then you can do interesting things to automatically parallelize it. The trouble is, almost no methods are actually pure. Furthermore, suppose you do have a pure method; since a pure method is a perfect candidate for memoization, and since memoization introduces a side effect (it mutates a cache!) it is very attractive to take what ought to be pure methods and then make them impure.

What we really need is some way to "tame side effects" as Joe Duffy says. Some way to draw a box around a method and say "this method isn't side-effect-free, but its side effects are not visible outside of this box", and then use that fact to drive safe automatic parallelization.

I'd love to figure out some way to add these concepts to languages like C#, but this is all totally blue-sky open-research-problem stuff here; no promises intended or implied.

Answer 5

There is a 13 parts reading that discuss about the new Parallelism support in .NET 4.0 here. It includes discussion on LINQ and PLINQ as well in Part 7. It is a great read, so check it out