Is C# becoming a functional language?

Artykuł
01/23/2007

As many of you will be aware, C#3.0 is adding a significant number of new language features. While the overall driving force behind putting these features in is the support of LINQ (Language INtegrated Query), the way we do it is strongly inspired by functional programming techniques. Moreover, we strive to make the new features as general-purpose as possible (with the exception of query expressions – they are undeniably tied to the querying domain!), so they do come out as features that will enable more of a functional style of programming.

This begs the question: Are we making C# a functional language?

This of course is a vague question. First of all, what exactly is a functional programming language? What does it take to qualify? Rather than trying to define the canonical list of language features that you have to have to be functional, I think it makes more sense to define it as “a language that supports a functional style of programming.”

Given that, my just as vague answer would be “to some degree”: If you’re a dedicated functional programmer, is this the time to throw out your Haskell, Scheme, F# or OCaml compiler and join the party? Probably not. C# doesn’t go the whole way. In this post I’ll explore in more detail the goodie bag of functional programming, in a kind of willy-nilly fashion, not focusing on a particular functional language, and then examine to what extent C# is supporting each of the features or styles of programming.

Please be aware that Visual Basic is adding most of the same language features as C# in the Orcas release.

Expression-based programming

Wes Dyer has a great post about expression-based versus statement-based programming. When you construct things the expression-based way, you build them bottom-up from their constituents, as opposed to the statements based way, where you create things top down by modifying them.

Instead of

Point p1 = new Point();

P1.X = 3; P1.Y = 5;

Point p2 = new Point();

p2.X = -5; p2.Y = 4;

Point p3 = new Point();

p3.X = -1; p3.Y = -6;

Polygon triangle = new Polygon();

Triangle.Add(p1);

Triangle.Add(p2);

Triangle.Add(p3);

Given the right constructors you could do it the expression-oriented way:

Polygon triangle =

new Polygon(

new Point(3,5),

new Point(-5,4),

new Point(-1,-6));

Much nicer, and composes really well. Trouble is you have to have the right constructors, but sometimes you don’t, or sometimes it’s impractical or annoying to write all the constructors that correspond to reasonable initialization patterns of your type. Furthermore they may get big, and the caller then has to remember the order of all the arguments.

To this end, C#3.0 introduces object initializers and constructor initializers. Assuming that Polygon is a collection type (see my previous post for a definition of that term), you can now write this:

Polygon triangle =

new Polygon {

new Point { X = 3, Y = 5 },

new Point { X = -5, Y = 4 },

new Point { X = -1, Y = -6 }};

In LINQ, queries are all about expressions. In order to produce the right output of a query, you often need to construct new objects out of old ones as in

from m in members

group m by m.Address.PostalCode into group

select new Entry { PostalCode = group.Key, Number = group.Count() };

The subexpressions of the query expressions are, well, expressions, and it is really important that you can create and initialize new objects in that context, or we don’t have projection in our query story.

Value based programming

Expression based programming limits the need for mutation operations (assignment) to such a degree that some functional languages (the “pure” ones) don’t even have them. Instead all data, whether simple or complex, is considered immutable values.

Even if they do allow mutation, many functional languages rely more on value types. The lack of mutability is really quite a feature. No-one can mess with the stuff you pass to them, and concurrent access is really easy to synchronize! You can have sound value-based equality and hashing. Implementations can optimize to their heart’s contend by copying, parallelizing, etc.

In C# you can certainly create user defined types that are immutable, but it is far from as easy as in a functional language. Making properties immutable is quite easy – don’t write a setter - but the associated value based semantics for equality and hashcode computation are a pain to write.

C# 3.0 doesn’t change that a lot, but this is something we may want to look into in the future, as the need for parallelism increases with the number of cores in our CPUs, and the number of people wanting to use value-based techniques increases.

Types on the fly

Many functional programming languages rely to a larger degree on structural types that do not have to be declared but are just there when you need them: You have type constructors that allow you to build types from other types, and corresponding value constructors to built values of those types. In a fully structurally typed world you never declare a new type: any type declaration would just introduce an alias for an existing type. (And you need that, because these types can get large!)

We don’t quite go there in C#3.0, but we do take you further in the direction of not having to declare so many trivial little types. With anonymous types, for instance, the above query can be written as

from m in members

group m by m.Address.PostalCode into group

select new { PostalCode = group.Key, Number = group.Count() };

eliminating the need to author a trivial type Entry to hold your results. The limitation here is that you cannot designate the type in any way, so it cannot be used

Another thing that takes you in the direction of structural types is generics: You still have to declare a generic type, but once declared you can construct new types from it over and over. We utilize that in the LINQ libraries to make a set of fully generic delegate types called Func, one for each number of arguments, e.g.:

public delegate TResult Func<TArg0, TResult>(TArg0 arg0);

From this you can create a delegate for almost any one argument function type, e.g. Func<int,bool> for functions from int to bool. Because we use the Func types consistently within LINQ, in that context they essentially act as structural function types. You never need to write your own delegate type again. Essentially, Func is a type constructor for delegate types.

Tuples

One kind of on-the-fly types heavily used in functional programming is tuples: strongly typed lists of values; just like the set of arguments to a method, only as a value in itself that you can pass around.

In popular syntax (1,”one”) is an example of a tuple value of the type (int,string). Some functional languages don’t even allow you to specify functions of more than one value; instead that value can be a tuple. Where tuples would be really interesting would be for multiple results of a function or method. Imagine

(int,int) NextFib(int curr, int prev) { return (curr+prev,curr); }

Tuples is one really useful kind of type constructor that it might be useful to add in the future. Like the Func types above, you could imagine .NET having centrally defined generic Tuple<…> types predeclared up to a certain arity, e.g.:

public class Tuple<TFirst,TSecond> {

readonly TFirst first;

readonly TSecond second;

public TFirst First { get { return first; } }

public TSecond Second { get { return second; } }

public Tuple(TFirst first, TSecond second) { … }

}

You get the idea. It would then be a matter of syntactic desugaring to translate (5,3) into new Tuple<int,int>(5,3).

There are currently no plans of shared tuple types on .NET, but languages such as F# on top of .NET roll their own.

Pattern matching

To really make use of constructed values, you need a good way of deconstructing them. For the functional programmer, pattern matching is the tool of choice. With tuples for instance, rather than “dotting your way” into the individual values, as in:

(int,int) result = NextFib(5,3);

int current = result.First;

int previous = result.Second;

you can create and assign in one fell swoop the variables to hold the individual component value of the tuple, by “matching” its structure:

(int current, int previous) = NextFib(5,3);

Pattern matching can be used to declare a function by cases – as in:

FibHelp(0) = (1,0)

FibHelp(n) = NextFib(FibHelp(n–1))

This defines one function, but saves the if-then-else logic by matching on the arguments.

A final common use of type constructors and pattern matching is with built-in immutable list types. Let’s say that [] is the empty list. You can the “cons up” a list as e.g. 1 :: 2 :: 3 :: []. Each occurrence of :: creates a new list value with the left hand side value prepended to the right hand side list. The cool thing is that you can pattern match the elements back off when you see them:

AddAll([]) = 0;

AddAll(n :: l) = n + AddAll(l);

Pattern matching is a whole different approach to plucking values apart, and we are nowhere near adding such features to C#.

Higher-order programming

When you want to have a piece of code executed conditionally, or repeatedly, C# has a nice set of built-in control structures. This is, however, a very closed regime: No one gets to add their own control structures as new language features! In order to write your own control structures you need the ability to be parameterized with functionality, with chunks of code.

Any object oriented programming language actually facilitates that. You can write a class

class ChunkOfCode {

public abstract void DoIt();

}

which people can subclass to override the DoIt method with the right functionality. ChunkOfCode objects can then be passed to “control structure methods” that execute the DoIt methods if and where they want.

On .NET we make this a whole lot easier with delegate types. You can grab a delegate to any old method and pass it around.

In C#2.0 we made it even easier by allowing you to construct a delegate “on the fly” with anonymous methods. The major improvement here is not so much avoiding to declare a method, but the fact that anonymous methods are “closures” that allow you to refer to arguments and local variables in the enclosing method body. This is crucial when the functionality you want to pass depends on your local state, as is so often the case.

At the core of LINQ you find the standard query operators, such as Where, Select, GroupBy, Join, etc. These are really user defined control structures, parameterized by little bit of functionality represented as delegate types. Thus to make the passing of these delegates really neat we’ve given anonymous methods a face lift in the form of lambda expressions:

members

.GroupBy(m => m.Address.PostalCode)

.Select(group => new { PostalCode=group.Key, Number=group.Count() });

Lambda expressions in C# are not entirely like anonymous functions in a functional language because they don’t have a type in and off themselves. Instead they can be converted to delegate types, and with the Func types sufficiently standardized, the effect is pretty much the same.

Currying

We talk above about tuples as a way of making input and output more symmetric on methods or functions. However, whereas a C# programmer today only has the option of writing multiple parameters, not multiple results, a functional programmer will often choose to do the opposite – use tuples only for compound result types. The reason is that functions of multiple arguments are often written using currying, where the original function only takes one argument, and then returns a function that takes the rest. Example: Instead of

Add (x,y) = x + y

You write

Add (x) (y) = x + y

which is a shorthand for

Add x = y => x + y

So instead of calling Add(3,2) you can call Add(3) to get a function that will take an integer and return the result of adding 3 to it! Hardcore functional programmers will use this technique extensively and take great care to arrange their curried arguments in such an order that they will lead to the most useful “derived functions” when only some of the arguments are passed.

You have to question how useful this is in practice, but enough functional programmers swear by it that I guess I’m willing to believe it will save me some day.

Strictly speaking, with anonymous methods or lambda expressions C# methods can also be curried, but it ain’t pretty:

Func<int,int> Add(int x) { return y => x + y; }

However currying of lambda expressions themselves gets pretty agreeable:

x => y => x + y;

Type inference

One convenient feature of statically typed functional languages is that you can have most or all of your type annotations inferred for you so that typing is really the compiler’s problem. In an object-oriented world we don’t have that option in the large, and in statically typed object-oriented languages such as C# we sort of take pride in the fact that our APIs are in fact annotated with types that users can see. At the architectural level, having explicit contracts is important.

However, in the small there are often cases where types are just in the way.

Already in C# 2.0 we introduced type inference for generic method calls, so that most of the time you do not have to be explicit about the type arguments to a method – they are inferred from the types of the method arguments.

In C# 3.0 we take this idea further, by being really clever about the way we use lambda expressions for type inference when they are used as arguments to a call of a generic method. Thus the types “flow” through the method call in and out of the lambdas and out in the return type.

Furthermore we’re adding type inference for local variables with the var keyword. Thus in

var query = customers

.Where(c => c.City == “London”)

.SelectMany(c => c.Orders)

.GroupBy(o => o.OrderDate.Year);

Without writing a simple type the compiler can figure out that query is of type IGrouping<int,Order>.

In C# we have deliberately kept the type inferencing algorithm simple, in the sense that it never infers a type that is not already there in the constituent values: We don’t synthesize types. This keeps the types under control, so the user has a chance of understanding what is going on if they get an error message etc.

Comprehensions

Oftentimes the passing around of lambdas gets too messy even for a functional programmer, and so many functional languages introduce syntactic sugar for common patterns involving the passing of functions. Such sugar is called a comprehension (presumably because it makes the code comprehensible) and we snatched that idea right in with query expressions in C# and VB – indeed in the early design days we did call them query comprehensions. In C# these are really just syntactic sugar which enables people to write most queries without lambda expressions. The above query (or one very much like it), for instance is generated by the query expression

var query =

from c in customers

where c.City == “London”

from o in c.Orders

group o by o.OrderDate.Year;

The extreme syntacticness of comprehensions is central in LINQ; it means that we just generate the method calls to the query operators syntactically, but anyone can implement their own methods with the right names on a given type and have it be the source of query expressions.

Conclusions

C# 3.0 and LINQ owe a lot to the functional programming languages in terms of the mechanisms we adopt. No doubt this will rub off to some degree on non-LINQ scenarios where a more expression-oriented style of programming becomes possible. People who are functional programmers by night and have to write C# by day will find that the daily headache sets in a little later in the afternoon.

However, as you can see from the above, there is some way to go before full-blown functional programming becomes totally natural in C#. There is probably a limit as to how far you can straddle before the pants rip, and we may never get to a point where C# is a true multiparadigm language with equal treatment of object-oriented and functional programming. Still I think there is room for more of this kind.

We have this thing about listening to customers, so I guess it is also up to you!

Comments

Anonymous
January 23, 2007
I hadn't thought of using lambdas like that to get currying. It makes sense that it would work that way. Of everything you've listed, Tuples seem like a nice, easier addition that could have some benefit. Given Tuples, some simple type decomposition would be nice as well, even if it was just at function return boundaries (like your example in the Pattern Matching section with Tuples). That seems like basic syntactic sugar, as opposed to the value-based decomposition stuff, which is more complex.
Anonymous
January 23, 2007
Dr. T takes you through a well-explained tour of C# 3.0's new features. http://blogs.msdn.com/madst/archive/2007/01/23/is-c-becoming-a-functional-language.asp
Anonymous
January 23, 2007
The comment has been removed
Anonymous
January 25, 2007
Im with Pinku - the pattern based language extensions are fine and good, but why not add a meta-language and be done with it.
Anonymous
January 25, 2007
The comment has been removed
Anonymous
January 26, 2007
Using the new anonymous delegate stuff in C# 2.0 has proved to be unsatisfying - is too verbose compared to doing similar things in scripting languages such as Groovy. C# 3.0 - is so overwraught - these days it looks like a public works project for language designers. Smacks of the kitchen sink feel of the likes of languages such as ancient PL/1.
Anonymous
January 26, 2007
I'm with Pinku too. So client voice from Monster is make things simple. Simplicity is always prove of genius and I was said by math prof :) So prove yourself guys! ;)
Anonymous
January 26, 2007
Notably absent from the list is the issue of sum types which are central to the pattern matching story in FP. Although there are ways to emulate these with patterns such as additional abstract superclasses, current projects on convergent OO & FP such as Scala put them in center stage. I really think the C# team has to look hard in that direction! I also agree with the remark that instead of providing concrete query comprehension syntax C# ought to give as expressions strong enough that a lot of DSL can be embedded in it - after all SQL syntax is not the last word in query notatation. There are alternatives out there such as Kleisli or even ZF that many people like better...
Anonymous
January 27, 2007
L'avvento di .NET 3.5 porterà ai linguaggi che usiamo di più (C# e VB) una serie di novità che sono principalmente
Anonymous
February 04, 2007
This begs the question - why not just use F# instead?
Anonymous
February 17, 2007
The comment has been removed
Anonymous
February 19, 2007
The comment has been removed
Anonymous
June 27, 2007
While I do look forward to C# 3, I must honestly say that I am a little disappointed. The reason is that it is just about all syntactic sugar. It will save me time, but I could already accomplish all of it before with a little more typing. > We have this thing about listening > to customers, so I guess it is also > up to you! Surely you are referring to functional language features. However, there are precisely two things that I have been asking for since Whidbey Beta 1:

Generic variance. See for example http://research.microsoft.com/research/pubs/view.aspx?type=inproceedings&id=1215
Generic operator constraints. I need a way to tell the compiler that a type T contains a +, -, *, / etc operator. This is not possible because operator overloads are implemented statically.

Anonymous
July 05, 2007
If you need a great book on linq than i can recommend you the following book from microsoft - Introducing
Anonymous
November 06, 2007
What makes C# 3.0 shine is that LINQ extensions are not mere syntatic sugar, and the difference has to do with expression trees. It's a pity ET's are not receiving enough publicity: they are a sort of bidirectional bridge between code and data... as in old fashioned FP languages and Prolog. Without ET's, the whole LINQ thing would make no sense at all.
Anonymous
February 21, 2008
I know it's been a little bit too long since I began this series from when I continued, but plenty of
Anonymous
April 29, 2008
Chapter2:C#LanguageFeatures AfullknowledgeoftheC#3.0languageenhancementsisnotnecessa...
Anonymous
July 10, 2008
As noted before, I was scheduled to give a presentation on Aspects of Functional Programming in C# 3
Anonymous
July 10, 2008
As noted before, I was scheduled to give a presentation on Aspects of Functional Programming in C# 3
Anonymous
August 14, 2008
Last month, I posted my Functional C# presentation for the Rockville .NET User Group (RockNUG) . 
Anonymous
August 14, 2008
Last month, I posted my Functional C# presentation for the Rockville .NET User Group (RockNUG) . 
Anonymous
August 14, 2008
Last month, I posted my Functional C# presentation for the Rockville .NET User Group (RockNUG) . Yesterday
Anonymous
August 19, 2008
Chapter Page Url 4 111 http://msdn2.microsoft.com/en-us/library/bb386907.aspx 4 111 http://msdn2.microsoft.com/en-us/library/bb399400.aspx
Anonymous
October 07, 2008
Thanks to everyone who attended my session "Functional C# or how I lost the foreach and learned
Anonymous
October 07, 2008
Thanks to everyone who attended my session "Functional C# or how I lost the foreach and learned to love
Anonymous
October 07, 2008
Thanks to everyone who attended my session "Functional C# or how I lost the foreach and learned
Anonymous
October 08, 2008
Thanks to everyone who attended my session "Functional C# or how I lost the foreach and learned
Anonymous
October 11, 2008
F# es un lenguaje funcional, creado por Microsoft. Implementado bajo el soporte de .NET CLR, es un lenguaje
Anonymous
December 02, 2008
You have to love a hotel where you have the amazing Lavazza coffee in your hotel room. CLR/Silverlight/Orcas/C# One of the things that has been a bit fustrating over the years with the CLR is the limitation of one CLR per process. Specifically, where
Anonymous
February 03, 2009
nice work, i guess introducing linq was a huge work. but i think C# can never get the place of functional programming especially with pattern matching or higher order function let add x y= x+y;; let add10=add 10;; add10 34;; val it -: 44;; can C# do that, no way i guess thanx for the work!!!

Udostępnij za pośrednictwem

Is C# becoming a functional language?

Comments

Dodatkowe zasoby