Lazy Evaluation in C#

Laziness,or Deferred Execution as it is called in C# ,is the program behavior that an expression is not evaluated before its value is needed. In C# this is made possible natively through iterators which the C# compiler transforms into state machines, that is, automata.

Below is a simple example of an iterator. Iterators are recognized in two ways: 1) the return type of an iterator method is always IEnumerable or IEnumerator and 2) one or more expressions are prefixed with “yield return” – or “yield break”.

public IEnumerable<int> Integers()
{
	int x = 0;
	while (x < int.MaxValue)
		yield return x++;
}

Iterators allow programmers to write highly lazy computations very easily and very elegantly (although not always very efficiently, as per current C# compiler and CLR (4.0); in particular recursive iterators are not dealt with in an optimal way; for more information see the research paper “Iterators Revisited” by Erik Meijer, Wolfram Schulte et al – this paper proposes a language syntax and semantics for efficient recursive iterators; as an example of a recursive iterator, imagine an iterator that traverses a tree data structure, asking each branch to iterate over its descendants, via recursion. With the current C# compiler this will generate very inefficient code which scales poorly).

The form of laziness afforded by iterators have the type of IEnumerable. So these yielded computations create sequences of lazy values. But what if you don’t want to create an entire sequence of values, what if you only want to create a single lazy value? C# does not directly support this in the language – but how might one express this? The simple syntax that comes to mind is reusing the iterator syntax. See the example below

public static N Square<N>(this N x) where N : INumeric<N>
{
	yield return x.Multiply(x);
}

The example shows a Square function (x x) which squares a generic numeric value. It is implemented as an extension method. Notice the “yield return” syntax. This is how iterators work but the difference here is that the result is of type N, not IEnumerable<N>. The laziness is concealed in the output type and the compiler will have to be smart about it. I’m not sure how easy this would be to implement but it would very much simplify some algorithms.

So the advantage here is that this generalizes laziness beyond sequences into arbitrary types.

It is fun to reflect over the fact that in computing, as opposed to real life, laziness is a virtue. It is the discipline of least effort. An algorithm that does just enough work to complete is preferable to one which always does all work, even if it is not always needed.

Microsoft .Net Framework 4.0 also has a library mechanism for explicit “lazy evaluation” through a type; if memory serves me this type is called LazyInit. It is very easy to make such a type yourself, e.g. as such

public class Lazy<T>
{
	public Lazy(Func<T> expression)
	{
		Contract.Requires(expression != null);

		_expression = expression;
		_evaluated = false;
		_value = default(T);
	}

	private readonly Func<T> _expression;

	private bool _evaluated;

	private T _value;

	public T Value
	{
		get
		{
			if (_evaluated)
				return _value;
			_value = _expression();
			_evaluated = true;
			return _value;
		}
	}
}

Note: This implementation compiles but I’ve not tested it and it is a minimal, thread-unsafe implementation. The purpose of this type is to store potentially expensive computations in a class and if not accessed, the values will never be computed, thus saving work.

To be more precise, all Func and Action delegates represent functions but these functions may or may not cache their outputs. In the code above a value is produced where a value can be acessed but the value is not actually evaluated before the first call to the get method; but all successive calls just get the underlying cached value.

A function which internally caches its range is known as a memoized function and the technique is known as memoization. It is possible to build a memoizer, that is, a higher-order function which memoizes other functions. See this blog post on Memoization for Dummies by Bart de Smet.

There is actually another mechanism for lazy evaluation of sorts in C# and that is the conditional operator also known as the ternary operator. An example is provided below

public static X Negate<X>(this X _) where X : INumeric<X>
{
	Contract.Ensures(Contract.Result<X>().Sign.Symmetric(_.Sign));

	return _.Zero.Subtract(_);
}

public static X Abs<X>(this X _) where X : INumeric<X>
{
	Contract.Ensures(Contract.Result<X>().Sign.Positive());

	return _.Positive()
		? _
		: _.Negate();
}

The conditional operator only evaluates the subexpression dictated by the condition. If, in the example, _ is positive (meaning the condition is true), then the result is _ and the second subexpression will not be touched at all; if however _ is negative (meaning the condition is false) then the subexpression “_.Negate()” will be evaluated. One could argue this is a simple kind of laziness.

See: http://en.wikipedia.org/wiki/Short-circuit_evaluation

The functional programming language Haskell is pure and lazy by default. Side-effects are tracked by the type system via the use of the IO monad whereas computations are assumed lazy. The compiler may perform all kinds of tricks to remove laziness where it is not needed (laziness may have some overhead as well, so it can be a double-edged sword, depending on how smart the compiler is) and would slow down speed but the principle of not doing more work than needed is indeed a computational virtue.

More information about laziness and Haskell with some C# and VB.Net context can be found in the excellent functional programming lecture series on Channel 9, presented by Erik Meijer. See http://channel9.msdn.com/ and search for functional programming lecture series.

Enhanced by Zemanta
Advertisements

About xosfaere

Software Developer
This entry was posted in Computer Science, Declarative, Imperative, Paradigm, Software, Technical and tagged , , , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s