IanG on Tap

Ian Griffiths in Weblog Form (RSS 2.0)

Blog Navigation

August (2014)

(1 item)

July (2014)

(5 items)

April (2014)

(1 item)

March (2014)

(1 item)

January (2014)

(2 items)

November (2013)

(2 items)

July (2013)

(4 items)

April (2013)

(1 item)

February (2013)

(6 items)

September (2011)

(2 items)

November (2010)

(4 items)

September (2010)

(1 item)

August (2010)

(4 items)

July (2010)

(2 items)

September (2009)

(1 item)

June (2009)

(1 item)

April (2009)

(1 item)

November (2008)

(1 item)

October (2008)

(1 item)

September (2008)

(1 item)

July (2008)

(1 item)

June (2008)

(1 item)

May (2008)

(2 items)

April (2008)

(2 items)

March (2008)

(5 items)

January (2008)

(3 items)

December (2007)

(1 item)

November (2007)

(1 item)

October (2007)

(1 item)

September (2007)

(3 items)

August (2007)

(1 item)

July (2007)

(1 item)

June (2007)

(2 items)

May (2007)

(8 items)

April (2007)

(2 items)

March (2007)

(7 items)

February (2007)

(2 items)

January (2007)

(2 items)

November (2006)

(1 item)

October (2006)

(2 items)

September (2006)

(1 item)

June (2006)

(2 items)

May (2006)

(4 items)

April (2006)

(1 item)

March (2006)

(5 items)

January (2006)

(1 item)

December (2005)

(3 items)

November (2005)

(2 items)

October (2005)

(2 items)

September (2005)

(8 items)

August (2005)

(7 items)

June (2005)

(3 items)

May (2005)

(7 items)

April (2005)

(6 items)

March (2005)

(1 item)

February (2005)

(2 items)

January (2005)

(5 items)

December (2004)

(5 items)

November (2004)

(7 items)

October (2004)

(3 items)

September (2004)

(7 items)

August (2004)

(16 items)

July (2004)

(10 items)

June (2004)

(27 items)

May (2004)

(15 items)

April (2004)

(15 items)

March (2004)

(13 items)

February (2004)

(16 items)

January (2004)

(15 items)

Blog Home

RSS 2.0

Writing

Programming C# 5.0

Programming WPF

Other Sites

Interact Software

Language Expressiveness, C# Anonymous Delegates, and Accumulators

Thursday 21 April, 2005, 05:41 PM

I recently happened to get directed to this article by Paul Graham. In the appendix, he shows a number of implementations of a simple bit of code in various languages. His intent was to provide a rough measure of the expressiveness of the language, by seeing how much code each language required to achieve the same goal.

The goal is to write a function that returns an 'accumulator' - something which maintains a running total, and allows that total to be incremented. Whether this is a particularly meaningful measure of a language's expressive power is debateable, but I'll not tackle that one. If you're familiar with Graham's writing, you'll know how much he loves LISP, so it is unsurprising that this example does, if nothing else, allow him to confirm how great LISP is - here's the LISP code:

defun foo (n)
  (lambda (i) (incf n i)))

I have to admit that's pretty succinct.

Graham goes on to show a series of solutions in other languages, each getting progressively more complex. By the time he gets to Java, it's looking kind of messy. And a V1.x C# implementation would look the same as the Java one. C# v2 adds anonymous delegates, which let us get away with something much more compact than the Java version, although still more verbose than the LISP:

Converter<int, int> MakeAccumulator(int n)
{
    return delegate(int i) { return n += i; };
}

Testing with this code:

Converter<int, int> f = MakeAccumulator(40);
Console.WriteLine(f(2));
Console.WriteLine(f(57));
Console.WriteLine(f(1));

generates this output:

42
99
100

So the accumulation facility is working just fine.

(In case you're wondering what the Converter is all about, that's a handy built-in generic delegate type for functions that take some data and return some other data. Usually it would be used with different input and output types, but here I'm using it with the same input and output types. It saves defining a new delegate type.)

I'm not entirely sure how Paul is quantifying complexity. If we count lexical elements, I see 17 in his, mostly brackets, and 27 in the C#. If we choose not to count brackets of any kind, it's 8 vs. 17. (Two of those 17 are semicolons.) I think that however you slice it, the LISP is significantly simpler than the C#.

Why is the C# version more complex? Mainly because it declares parameter and return types explicitly, and requires explicit use of the return statement. Without those, the two start to look pretty similar.

Sadly, the C# version is not polymorphic - it only works on ints. What we'd like to write is this:

Converter<T, T> MakeAccumulator<T>(T n)
{
    return delegate(T i) { return n += i; };
}

Unfortunately, that doesn't work, due to the limitations inherent in how CLR generics work, and the inability of C# to work around those limitations. The IL representation of 'add' has the operand type baked in - there is no generic add. There is no way that the compiler can express the intent of the code above in IL.

I suspect this is the kind of thing that leads people to conclude that the CLR is only suitable for implementing languages that look like C#. But I don't think that's true. After all, even though IL doesn't have a native representation of the notion of "I don't know what the type of these two things will be, but add them together anyway" this doesn't stop VB.NET from letting you write code that does just that:

Public Class AddUtils
    Shared Function GenericAdd(ByVal left As Object, ByVal right As Object) As Object
        Return left + right
    End Function
End Class

So how come VB.NET is able to do this when C# isn't. Simple: because the VB.NET language chooses to support a late bound addition facility, but the C# language does not. The VB.NET compiler just generates code that does the right thing for you under the covers. The resulting IL happens not to be quite as succinct, because this particular VB.NET idiom doesn't have a direct representation in IL. So the compiler has to do a little work - it has to generate the code required to support the language features it offers.

It's that simple.

This is a pretty clear illustration that just because IL doesn't directly support a particular feature, that's no reason for the language not to support it. The idea that a compiler should bridge the gap between language features and underlying platform features is hardly a new one, so it's really rather odd that so many people have this strange idea that languages targeting the CLR have to be constrained by the CLR's intrinsic feature set.

So, now we can write the function we wanted to. Sadly, VB.NET doesn't do anonymous functions, so we can't just write the whole thing in VB.NET. But the VB.NET+C# combo gets us where we want to be. With that VB.NET utility function in place, we can now write this C# function:

Converter<T, T> MakeAccumulator<T>(T n)
{
    return delegate(T i) { return (T) AddUtils.GenericAdd(n, i); };
}

This is now polymorphic - it works for any numeric type. I was going to say you'll get a runtime error if you try it with non-numeric types, but I just tried it with String and that works too - it just appends the strings... This is either cool, weird, or downright wrong depending on your programming language preferences. Anyway, if you try it with types that can't be added, it will fail at runtime.

Can this compete with LISP for conciseness? I think not - I had to resort to using two languages, because C# didn't offer sufficiently late binding for addition, and VB.NET didn't offer higher order functions. (If you're not familiar with that remarkably snooty term, 'higher order functions' are functions that can return and/or consume other functions.) So LISP does indeed score better here - it provides the two features required in one language. But I think this illustrates that the CLR isn't the limiting factor here - evidently the "any language you like so long as it's C#" theory is wrong.

Useful?

And yet...I feel strangely unempowered by this example. Indeed, it's a feeling I often get with examples constructed to illustrate a language feature. I don't feel that the ability to cruft up accumulators with ease will make a major contribution to my quality of life, which is why I'm doubtful of its value as a measure of language expressiveness.

Copyright © 2002-2013, Interact Software Ltd. Content by Ian Griffiths. Please direct all Web site inquiries to webmaster@interact-sw.co.uk