Immutability, Purity, and Referential Transparency

re: Immutability, Purity, and Referential Transparency

Tom Kirby-Green — Thu, 01 Mar 2007 15:16:55 GMT

Another great post Wes, where do you find time? I'm really hoping some of the Spec# ideas make it into C# 4, at which point I think the language will essentially be complete (caveat: if STM ever becomes real then maybe we'll get a 'atomic' keyword, or language bindings for message based method invocation). I can see a real need for the constraints and stuff that Spec # offers - esp. when you think about being able to use things like DLINQ with confidence in a compositional manner. That said I also wonder about the comment in Charlie's Orcas Feb/March CTP video about is "C# begining too complicated?" I don't think so yet - but I'd hate to see it decay to the complexity of C++. I think one of the goals for C# is that the majority should be able to grok the entire language.

A Tale about the Importance of Simplicity

Harald Radi's Weblog — Thu, 01 Mar 2007 18:33:07 GMT

I just read another brilliant blog post of Wes Dyer that emphasizes the importance of simplicity of code. This is one of the paradigms of agile software development and I think this cannot be accentuated too much. It not only helps the author to keep

re: Immutability, Purity, and Referential Transparency

Patrick Lioi — Thu, 01 Mar 2007 22:59:15 GMT

Not that this affects the point you were making in the QuickSort example, but do the implementations of Skip(int) and Concat(IEnumerable<T>) also work without changing state? It seems like at least Skip(int) would have to alter the state of the enumerable it is acting on, but does it instead create a new enumerable from the original one?

re: Immutability, Purity, and Referential Transparency

damien morton — Fri, 02 Mar 2007 01:38:32 GMT

But unfortunately, object-oriented programming and mreo specifically, object oriented design, is completely incompatible with immutability and referential transparency.

In particular, the idea of encapsulating (state) in an object, and providing methods to manipulate that state, just doesnt work with immutability and referential transparency.

Theres ways around this, say my making each method return a new instance of the object (and its encapsulated state), but then things begin to get nasty.

How do you do Model-View-Controller in a referentially transparent way? How do you do the Observer pattern? Is there any way to gho down this functional programming road without abandoning everything we know about making good programs?

Community Convergence XXII

Charlie Calvert's Community Blog — Fri, 02 Mar 2007 11:23:23 GMT

Welcome to the twenty-second Community Convergence, the March CTP issue. I'm Charlie Calvert, the C#

Community Convergence XXII

RSS It All — Fri, 02 Mar 2007 11:36:49 GMT

Welcome to the twenty-second Community Convergence, the March CTP issue. I'm Charlie Calvert, the

re: Immutability, Purity, and Referential Transparency

wesdyer — Fri, 02 Mar 2007 13:39:35 GMT

Tom:

I would love to see the constraints stuff make it into a future rev of C# (hopefully the next one). It is true that we need to be concerned about the language becoming too hard to grasp. I remember two years ago we were talking about the possibility that perhaps we would soon be exceeding our complexity budget as a language. I'm very interested to see what others have to say about this, so if someone has an opinion then please chime in.

Patrick:

It is very good that you noticed that. Skip and Concat do not change state themselves. They are passed IEnumerables and they return *new* IEnumerables. Yes, iterators are codegened as little state machines so they have state that changes but those side-effects are relatively contained. The side-effects only are visible when it is accessed as an IEnumerator (assuming the enumerable itself isn't changing state). Most code deals with IEnumerables and not IEnumerators (foreach, queries, ...). But remember that it is best to not have side-effects but that if either clarity, conciseness, performance, or some other constraint demands otherwise then go ahead and add it at the appropriate scope.

Damien:

Object-oriented design is not incompatible with immutability. Yes, I agree that providing methods to mutate state doesn't work well with immutability by definition but think of the string object. It has a host of methods but each one returns a new string to act on and I don't think things get very nasty with strings. Sometimes performance is a problem so there is a class that builds strings. Note that this thing is not a string but builds them and once you ask for a string then that string is immutable. The string builder has encapsulated all of the state changing and removed it from strings.

You can certainly do either the Observer pattern or MVC following the principles that I outlined. Object-oriented programming and functional programming are not mutually exclusive. Do not throw away everything that you know!!! That would be a terrible waste. Just learn new things and incorporate them into your toolbox.

Also, remember that I didn't say never use side-effects otherwise the basic Hello World program would be out of the question in C#. I essentially said try to use them sparingly and understanding the tradeoffs that are being made when you do use them. Know that there are alternatives that work very well in many cases.

re: Immutability, Purity, and Referential Transparency

Tom Kirby-Green — Fri, 02 Mar 2007 15:16:14 GMT

Well right now C# is going through it's 'data access evolution' period, and it's doing so in a manner which might well lead into its 'concurrency evolution' period.

I'm aware that folks like Sutter are rightly cautious of over selling FP as a magic solution for concurrency. I think he's right about the over selling bit - but I also think the way FP tends to make you think about mutation vs. value and side effects and what not help hugely in expressing and partioning ones logic in a form that takes us a step closer towards Sutter's "sea of available concurrency". If we don't decompose and express with a eye on mutation vs. value then it's going to be very hard for any runtime to infer intent and distribute without us having to explicitly decorate code (in a OpenMP or .NET attribute based manner).

So I feel that with LINQ plus some carefully chosen bits of Spec# could position C# 4 or C# 5 as a great platform on which to build software that runs atop of the 16 to 32 hardware threads per socket we can expect by that time.

Personally I think once constraints and maybe some language bindings for concurrency are in place then its pretty much "job done" for C#. It would I feel be a huge mistake for it to descend into the murky syntactic depths that C++ has got itself into.

The beauty of .NET is the degree to which you can "mix it up". It may well be I feel that C# 5 or 6 would best be realised as a different and complimentary language. Look at the way XAML compliments C#. Or the way you can mix up solutions using F# and C#. Better I feel to have a language which the majority can really grok and feel super comfortable with - that leads to better software in terms of being on time and defect free - which ultimately is better for Windows since its the software that runs on top of Windows that delivers the real value to the end user.

re: Immutability, Purity, and Referential Transparency

jmlovero — Sat, 03 Mar 2007 02:30:05 GMT

A very informative and insightful post as usual, Wes. I'm afraid I have to take exception with these statements about performance, though:

>>>

At this point, some people will probably be thinking, "But isn't the first approach so much faster than the second approach?"

Maybe, maybe not. Perhaps it doesn't even matter.

I think it is important to use the following principle: Make it correct, make it clear, make it concise, make it fast. In that order.

<<<

I agree with you that for many of the problems that we encounter, a developer is better off writing clear, concise code that just works. The re-worked QuickSort method is a great example of that principle. However, the QuickSort example belongs to a class of problems for which such a laissez-faire attitude towards performance is likely to be unacceptable to many people. This class of problems includes these very general sorts of methods where performance is important, you need an algorithm that scales well, and you are unlikely to modify the code much once it's written. If we were going to need the QuickSort method to operate on very large arrays, then you can bet that the difference between an O(n log n) algorithm and (for the sake of argument) an O(n^3) algorithm is going to be important. Furthermore, once it is written and works correctly, you can use QuickSort on just about anything that implements IEnumerable<T> and IComparable<T> without modification, so chances are that you aren't going to need to do much to the method once it is created. So, it would seem that this sort of problem is one for which our priorities are inverted: make it fast, make it clear, make it concise.

Now, I'm sure you understand all of this and you were just trying to make a more general point. I happen to agree with that point for the vast majority of problems. Here's what really bothers me about the performance issue, though. How do we tell which is faster, the original implementation of QuickSort or the implementation using LINQ? You seem to be admitting that you don't know. My fear is that we either can't know or that it will be very difficult to determine. I might be willing to trade some performance for code clarity and simplicity, but to do so, I want to have some idea of what the performance is going to be. Heck, the LINQ implementation could be faster, but I'm not willing to roll the dice on this sort of problem, so I'd approach it in the traditional way. Is there a way to get a good approximation of the efficiency of a LINQ algorithm? Sure, you can always profile the application, but I think many of us would like a more generic and rigorous way to analyze their performance. Am I just overlooking something that should be really obvious?

re: Immutability, Purity, and Referential Transparency

wesdyer — Sat, 03 Mar 2007 10:01:37 GMT

Tom:

Thanks for the input. FP is no silver bullet ;) Just another tool in the toolbox.

re: Immutability, Purity, and Referential Transparency

wesdyer — Sat, 03 Mar 2007 12:11:47 GMT

jmlovero:

Great comments. Just to be clear, I am pro performance. I was actually getting at two things: first, having clear and concise code lends itself to be in better shape to be improved for performance and second optimizing code is not straightforward. Some optimization choices while improving characteristics in some dimensions actually cause performance to degrade in others. We need to make sure that we understand which scenarios are important and then optimize for those.

I understand that you are talking about asymptoptic performance. You are right that we don't want to just throw around O(n^3) algorithms, that would be irresponsible. What I am saying is that the particular code in question may not be important to the overall performance depending upon our performance budget and the customer scenarios that we support. You make a very good point that QuickSort is something that should just be written and stored away in a library and I agree with that. Hopefully there will be at least two implementations: one which modifies the collection in place and another which just returns a new collection.

Thank you for having me clear that up. -- Performance is important.

re: Immutability, Purity, and Referential Transparency

Alex James — Sat, 03 Mar 2007 14:02:17 GMT

I might be missing something but

.Concat(pivot) fails because it isn't enumerable.

To fix this I wrote this:

public static IEnumerable<T> Enumerate<T>(this T t)

{

yield return t;

}

And modified the code to this:

if (!sequence.Any())

return sequence;

var pivot = sequence.First();

var remaining = sequence.Skip(1);

return ((from x in remaining where x.CompareTo(pivot) < 0 select x).QuickSort())

.Concat(pivot.Enumerate())

.Concat((from x in remaining where x.CompareTo(pivot) >= 0 select x).QuickSort());

seems to work.

re: Immutability, Purity, and Referential Transparency

wesdyer — Sat, 03 Mar 2007 22:06:02 GMT

Alex:

Good point. I had written my own extension method called Concat that looked like this:

IEnumerable<T> Concat<T>(this IEnumerable<T> sequence1, params T[] sequence2)

{

foreach (var item in sequence1) yield return item;

foreach (var item in sequence2) yield return item;

}

re: Immutability, Purity, and Referential Transparency

Sadek Drobi — Sun, 04 Mar 2007 18:24:39 GMT

i aree that Immutability brings clearity, i would like to c an example from the PLinq implementation where it uses several hardware threads for doing job, that will give some more arguments in my java-oriented consulting company :P

i guess the complexity budget is higher than what u think,i even think that adding functional programming features has the opposite effect, because as long as you write side-effects free functions, and Intention revealing interfaces, u are free of complexity. But the overuse of mutability, in not encapsulating state , is the source of the complexity.

I went through the implementation of the visitor of expressions, and i have two questions:

1: why in a lambda expression you are not visiting the parameter expressions in the VisitLambdaExpression

2: why u make the class as internal, it would be very helpfull if i could extend it, so that i can replace all the old parameters in my predicate's (LambdaExpression<Predicate>) implementation with the new one resulting from the "And" operator, i would only need to override the VisitParameterExpression to have it done.

re: Immutability, Purity, and Referential Transparency

Alex James — Sun, 04 Mar 2007 22:14:44 GMT

Wes

That makes sense, and is much cleaner than mine. I'm just learning all this stuff, and to that end your blog posts are invaluable.

Keep up the good work

Alex

re: Immutability, Purity, and Referential Transparency

Judah — Mon, 05 Mar 2007 08:13:47 GMT

Great blog post. Keep it coming, Wes.

Please push for Spec# ideas to be integrated into C#. IIRC, you can mark methods as [Pure], you can mark reference types as non-null, you can guarantee pre- and post-conditions. Seems to me these things would help us write more correct software.

re: Immutability, Purity, and Referential Transparency

Tom Kirby-Green — Mon, 05 Mar 2007 08:27:37 GMT

Totally agree. It's not just things like "[Pure]" but being able to constrain parameter values, not least "not null" that I think we have a real need for. Goodness knows how many developers hours get sunk into implementing #region Parameter Validation blocks at the start of every public and protected method.

In that C9 video on Language Innovation (http://channel9.msdn.com/Showpost.aspx?postid=273697) with Anders and Herb et al rapping on the motivations behind and directions in language design they certainly seem to hint that some form of formal contraints notation might, possibly, be coming ;-)

re: Immutability, Purity, and Referential Transparency

Mr Agile — Mon, 05 Mar 2007 15:59:02 GMT

I vote for Judah's suggeestion! i love spec#!

re: Immutability, Purity, and Referential Transparency

Joost Morsink — Mon, 05 Mar 2007 16:25:09 GMT

seems a lot like the haskell definition:

qsort (x:xs) = qsort [y | y<-xs, y<=x] ++ (x: qsort [y | y<-xs, y>x])

qsort [] = []

What about Monads? Is this haskell feature feasible to implement in C# 3.0?

re: Immutability, Purity, and Referential Transparency

Joost Morsink — Mon, 05 Mar 2007 19:04:58 GMT

Or maybe a more generic way of putting this is:

Can I add interface types to existing classes using extension methods? Like in Haskell I could define:

instance Monad {a} where

x>>=y = ...

return x = ...

I could make IList<T> a Monad by implementing:

static IList<T> bind(this IList<T> a, Func<T,IList> f);

and

static IList<T> return<T>(T item);

or something like that?

re: Immutability, Purity, and Referential Transparency

wesdyer — Mon, 05 Mar 2007 22:26:19 GMT

I will relay all of the feedback about Spec# features in the next rev of C#.

Joost:

It is very similar to the haskell definition.

Well, I think what you want is something like type classes in haskell. I love them and we are working on some ideas to implement an interface with extension methods (post C# 3.0).

re: Immutability, Purity, and Referential Transparency

Alex James — Mon, 05 Mar 2007 22:55:50 GMT

FYI I just did a post on this...

The Essence Of Good Code

DonXml's All Things Techie — Mon, 05 Mar 2007 23:32:09 GMT

In my recent Syntactic Sugar presentation I was trying to get to the essence of good code, and come up

re: Immutability, Purity, and Referential Transparency

wesdyer — Tue, 06 Mar 2007 01:16:09 GMT

Sadek:

1. We don't visit the parameters because they are not part of the body of the lambda.

2. We wanted to expose it, but we were very short on resources so this feature was cut. We may expose it in a sample.

re: Immutability, Purity, and Referential Transparency

Sadek Drobi — Tue, 06 Mar 2007 03:05:27 GMT

But you do visit arguments, so why to visit arguments and not paramters, anyway thats not a big deal as i can override the methods.

I would really like to revisit all the everyday's patterns and think about them in an immutable implementation, maybe it will work for some, i like the new horizon a mixed language like c# offers.

re: Immutability, Purity, and Referential Transparency

Joost Morsink — Tue, 06 Mar 2007 12:17:53 GMT

Yeah type classes, that's exactly what I want. Too bad it isn;t going to be in the next release. I guess I'd better head back to Reflection :). But seriously I could write some interface transformer extension methods. In my example like:

static IMonad<A> ToMonad(this IList<A> l);

which brings me to my next question: Can I implement a preferably implicit, but otherwise explicit cast/conversion operator as an extension method, so when coding, it does look like it has the new type, but it really doesn't?

Quicksort in C#, Ruby, Haskell e LINQ

Il Blog di Antonio Cangiano — Wed, 07 Mar 2007 08:53:47 GMT

Il sottotitolo di questo blog ora appare come Pensieri eretici nel mondo .NET . Ho deciso di rinominarlo

Would MS consider hosting a FP Community site?

Tom Kirby-Green — Wed, 07 Mar 2007 09:14:01 GMT

Wes,

Would Microsoft consider hosting a FP community site? It seems clear that there's a real interest and hunger in the community for this stuff. The responses to your own posts show that the existing FP community has a considerable body of experience and insight to offer and are now coming out of the woodwork given the tentative steps C# 3 is making in this direction.

What I'm suggesting is some central place where we can hang out, with links to your blog, HubFS, Lambda The Ultimate etc, Iron Python. The remit would be FP on .NET.

Perhaps a sub-section of Channel 9, but I was really thinking of something like Coding For Fun in terms of having its own identity.

Would Microsoft consider putting some resource behind this?

Kind regards,

tom

re: Immutability, Purity, and Referential Transparency

Joost Morsink — Wed, 07 Mar 2007 15:58:20 GMT

Tom: I agree :)

re: Immutability, Purity, and Referential Transparency

wesdyer — Wed, 07 Mar 2007 19:29:37 GMT

Joost:

You can't do that today, but I'd love to add support for that.

Tom:

I forwarded your request on to the people who could organize that. Thanks for the suggestion.

re: Immutability, Purity, and Referential Transparency

wesdyer — Thu, 08 Mar 2007 02:25:27 GMT

I was told that it would be fairly difficult to organize such a site; however, I was also told that we'd be happy to host articles and provide links to FP related things on the C# site. You can contact Charlie Calvert if you have something. His blog is at: http://blogs.msdn.com/charlie.

MVC, Desktop Clients, & WPF

Christopher Bennage — Thu, 12 Apr 2007 06:55:52 GMT

I've spent the majority of my career as a Web developer, and I've only recently (with the discovery of