Lambda the Ultimate

she's just too old for the computer thing. But, perhaps with a well suited "mass-market" programming language and IDE...

That paper was previously discussed on LtU here - I don't know if you've seen the discussion before, but thought I'd provide a pointer just in case.

Thanks for the heads-up.

There is a wonderful new paper Hybrid Type Checking by Cormac Flanagan. He uses a statically undecidable type system (dependent functions and refinement types) with dynamic checks to ensure soundness. The hybrid checker also has more precision than a convensional static checker!

I wish I could agree with you about "Static typing where possible", IMO, it reads like flamebait.

Also, The link above has an extra / at the end.

I've made available a version in PDF.

Note that the "I want contracts" paragraph in my paper describes exactly the idea of hybrid type checking.

The state monad is just one example of many other possible monads, but the concept of monads is useful beyond that.

The monad comprehensions in C# and Visual Basic are used for queries, and the library provides "instances" for IEnumerable (the standard list monad) and for IQueryable (the query monad as in HaskellDB).

I see.. sort of. Can you recommend any introductions to the concept of monads from an imperative programmer's perspective?

Phil Wadler's original papers are still my favorites.

Mostly a me too post. Phil Wadler has a second sense with making good puns for paper titles and almost all his papers are very enjoyable to read.

You need to know a bit of Haskell or a similar language for this: What the Hell are Monads?

The same for this one: Monads for Functional Programming

Explaining Monads

I do really wish, though, that this stuff wasn't going to be tied to the Microsoft platform. Ethical or business disagreements aside, I've always been pretty uninspired by the Windows aesthetic, and as I don't expect you to re-invent the OS as well, I'm afraid I'll be stuck admiring your work from a distance. Obviously advancing the state of the art fosters competition, so I expect that we'll start to see some more interesting work outside of the Microsoft fold as well, but few companies can drive adoption like Microsoft, so it remains to be seen whether other offerings will gain (or retain) mainstream acceptance.

Who says it's going to be tied to the windows platform? Haven't you heard of Mono?

Haven't you heard of patents? :-} Even if there is a claim that the ECMA-submitted core isn't hindered by patents, the fact is that anything which could have patents could have lawyers involved, which clearly then becomes a horrendously evil situation.

The same argument could be applied for any software under any license, admittedly. The reality is one has to try to guess the intentions of folks through their license and their past behaviour. Take a look at the history of MS (or IBM, or Sun, or even little weasels with JPEG or whatever patents), mix that with the license, and compare against things which are put out under, say, GPL.

Haven't you heard of patents? :-} Even if there is a claim that the ECMA-submitted core isn't hindered by patents, the fact is that anything which could have patents could have lawyers involved, which clearly then becomes a horrendously evil situation.

Sun has lots of patents too. If you're going to worry about software patents then you might as well get out of the software field. If you write 300 lines of code, you're probably infringing on some patent somewhere.

I think you are quite correct, that the difference between Sun and Microsoft when it comes to any sort of proof that they won't some day try to screw the little guy is zero. The issue of patents pretty much encumbers everything - very, very sad from my perspective. I guess as far as languages are concerned, the way to go is with something that was very GPL / BSD from the beginning? (As you point out, that doesn't guarantee anything either, but it would seem to be less blatantly fraught with peril.) The whole software patent thing seems so blatently corrupt and stifling and just plain wrong it makes me weep.

Well, for one thing there's the intellectual property issues mentioned in another comment. But as far as I'm concerned, that's not really the main thing.

Even if all of the work that Erik et al are doing will run on Mono seamlessly and with binary compatibility (including Visual Studio, Linq, etc., which I highly doubt), there's still the fact that Mono is one of many smaller players in an open source ecosystem, and doesn't have the weight of a Microsoft to drive adoption. So I guess I have two concerns: (1) they're likely to be stuck on a treadmill, (2) I doubt it will acheive the pervasiveness of Java or .Net.

In fact, I think Mono is good and exciting work, and I definitely hope it continues to mature. But it's exactly the kind of project I was referring to when I said "we'll start to see some more interesting work outside of the Microsoft fold as well," with all the problems that come with that.

LINQ will run just fine on Mono - it doesn't involve any changes to the runtime, just a couple new libraries and syntax changes to the C# and VB. You can compile a LINQ program with C# 3.0 and run it on .NET 2.0; there's no reason you shouldn't be able to run it on Mono as well.

Whether Mono can achieve the pervasiveness of .NET seems irrelevant to me. Mono and .NET are both implementations of the CLI. As long as Mono and .NET can run the same programs, there's no compatibility problem, and it doesn't matter which implementation is more pervasive. Getting to that point is just a matter of implementing all the libraries that ship with .NET.

Getting to that point is just a matter of implementing all the libraries that ship with .NET.

Just a matter of implementing all the libraries? I think you might be underestimating the scale of that project... From Erik's original post: "For example, in the context of LINQ, the language extensions are just the tip of the iceberg, and in fact the bulk of the work is in the libraries..."

And remember that my interest isn't primarily in deploying applications. My interest is primarily in writing software. So whether or not I can run my app on Mono is irrelevant to me if I still need to run VS on Windows. I don't have Windows. Look at the whole stack of components mentioned in the original post (Dev Tools, Language, Runtime, Libraries)... I want that whole stack to be OS-agnostic. Looking at other modern mainstream languagues (Java, Python, Ruby) they do seem to have largely achieved this.

Maybe I'm misunderstanding you, and I really will be able to run all of the MS development tools without running Windows. If that's the case, I apologize, and I really will look forward to it.

Right now, I am working on a POPL paper on LINQ with Gavin Bierman. One of our goals is to formally prove that LINQ requires no CLR changes and that all C# 3.0 extensions can be erased into ordinary C# 2.0.

Interestingly, for Visual Basic 9.0 we show that we cannot compile into Visual Basic 8.0 and we aim to show what extensions are required to Visual Basic late-binding runtime library. But again, these require no CLR changes.

Visual Basic a very interesting topic for programming language semantics research.

That's what it sounds like you're saying.

As far as language tools go... Sure, I wish they would. Maybe it just doesn't make business sense, but I'm not totally convinced. And it's not like the idea is totally ludicrous: Sun supports Windows, after all.

Anyway, like I said, I can't really make a business case for it... It's just wishful thinking, plain and simple.

The business brains at Microsoft know if it's viable to support alternative OSs or not. And most likely it's not.

Stop this "wishful thinking" crap. "I wish" someone would just drop a couple million in cash on my doorstep.

I think you have a simplistic view of simplicity ;) Joking aside, I think the simplicity in terms of language design comes from well organized features and powerful primitives. Number of features is largely irrelevent if they are properly orthagonal and self consistent.

Yukihiro Matzumoto, creator of Ruby:

The orthogonal features, when combined, can explode into complexity.

Great text, by the way.

Hence th esecond half of the statement - properly organized. Matz organizes his language around the principle of least surprize and an "everything is an object" structure. Scheme supports numerous things and organizes everything around lambda expressions. Perl supports everything and is organized around a hodge-podge of english and unix (okay so not all organizing principles are successful...). Arguably the urge for a simple elegant programming languages goes down the same road that physics takes - a quest for a unifying principle from which all other features can be naturally derived.

I agree with simplicity and minimalism. What John Hughes refers to is the misconception that if you take an existing imperative language such as C, and leave out assignment, the resulting language suddenly suddenly becomes more powerful, i.e "functional" or "declarative". It just becomes "assignment free", and hence less expressive.

In your anology it would be like removing the roof of a house. You should be careful not to remove the essence of things.

Hope this helps,

Yes, I know, I've read "Why Functional Programming Matters".

The point I was trying to get across: C# 3.0 is too complex. Why?

Mike Gunderloy: "I freely admit that my eyes glazed over. As far as I'm concerned, C# is now going the way of C++: it's got syntax that I will never, ever use and is well on its way to complexifying its way out of my life."

The point I was trying to get across: C# 3.0 is too complex. Why?

Well, they could make it simpler while retaining the expressive power that 3.0 brings to C#, but it wouldn't be C# anymore. ;-)

Kidding aside, I really wonder what Mr. Gunderloy ment when he said C# was "complexifying its way out of [his] life." Is he referring to lambda expressions and expression trees, or to their implementation in C# 3.0? If the former, then many would beg to differ, if the later, then if we fix the implementation, it wouldn't be C# anymore (syntactically, it would be difficult to find another implementation that fits in with C# 3.0). Whether or not these features should be added into a language that is as syntax bound as C# as an afterthought is a very good question.

I'm not really convinced that C# is getting more complex: I think it has been complex the whole time: its just that nobody noticed it until now. That is, C# (really any decendant of C) isn't very ameable to changes as fundamental as this without the addition of new syntax.

So, to answer your question, as I see it, C# 3.0 is so complex because its the syntax of the language requires it.

Okay, so the bridge collapsed because the concrete was poor. And the question becomes, why does Microsoft sell poor concrete?

Trolling aside, I was hoping to hear sound engineering justifications for:

"extension methods" (local extensions to existing classes in a statically-typed environment)

"expression trees" (macros that run at runtime because there's no macroexpansion time)

the many different forms of lambda (Smalltalk did fine with just one)

object and collection initializers (instead of a proper argument-passing convention)

query expressions (why isn't the new macro mechanism expressive enough to encode them, why does the standard need "query expressions" with magic method names?)

And so on.

LtU is a good place to discuss the technical issues and questions. These questions are a good start.

Good questions, yes.

But it seems Erik has decided to leave them unanswered, and I couldn't find definite answers anywhere else on the Net. It's sad.

I reread the article on expression trees, and I kind of have to agree with you. It does seem overly complicated. My guess is they realize that Java isn't their only competitor anymore. They have these “new” (but older than Java!) languages like Python and Ruby gaining popularity. (Python and Ruby are much more popular in the Windows world than they were just 4 years ago, and are rapidly gaining acceptance in the business world.) These languages allow all sorts of programming and meta-programming possibilities, and can walk circles around C# all day long when it comes to DSLs and library creation. (What I mean by that is, these types of languages can use their meta-programming “kung-fu” to create libraries that much simpler and more elegant.) They realize that they need to compete with that, but they’re syntactically bound (old code might break if you introduce new syntax), as well as being bound by other concerns. C# isn’t a “new” language anymore: they have a lot of customers who would be upset of all of their old code broke when they upgraded to C# 3.0 and who won’t take the risk of upgrading if C# 3.0 breaks old code. Python and Ruby, on the other hand, have had much longer to refine themselves, and haven’t had to fear customers getting upset and leaving over broken code. Heck, Guido wants to make changes to Python 3000 that could break a lot of old Python code, but he isn’t overly concerned about that. Microsoft, on the other hand, could never get away with that sort of behavior. The result: Python, Ruby, and other “open source” languages are much more dynamic languages (no pun intended), and have a much cleaner design as a result (old cruft gets thrown out).

You do bring up some interesting points, and it would be interesting to hear what sort of defense they have for their decisions.

The interesting thing about comprehensions and expression trees in VB and C# is that they are based on a type-directed translation.

For instance in Lisp/Scheme you use quote and quasi-quote to build code as data expression trees, whereas in VB and C# it is based the type to which you assign and the compiler will insert quotes for you.

My question is how would you do that in Python or Ruby?

For instance in Lisp/Scheme you use quote and quasi-quote to build code as data expression trees, whereas in VB and C# it is based the type to which you assign and the compiler will insert quotes for you.

Oh, duh! I'm sorry I must of missed that. Yeah, it makes more sense now. Thanks for the comment. Of course the syntax is still kind of crappy, but like I said in an earlier post, Microsoft is rather constrained when it comes to modifying C#. They don't have a lot of wiggle room, change too much and old stuff breaks. That is not an option for Microsoft (they have customers; if all their costomers stop using .NET for fear that all their old stuff breaks, it's a pointless product).

My question is how would you do that in Python or Ruby?

Good question! To tell you the truth, I don't know Python very well. I don't know Ruby either, but from what I understand such meta-programming is possible in Ruby as well. I do know Lisp/Scheme pretty well. The only reason I used Ruby and Python as examples is because, I've heard all sorts of raving about meta-programming in these languages and these languages are much more popular than Scheme or Lisp. I've looked at django, for example, and it is a pretty cool framework, and does all sorts of stuff that would be difficult to do in C# (or is it difficult because I'm not a very good C# programmer?). If I understand correctly, Python does allow one to look at and manipulate syntax trees, but from what I've seen it looks more complicated than the expression trees in VB and C#.

Anyway, C# 3.0 does look like its trying to compete with (integrate the features of) more dynamic languages such as Python or Scheme. (Or at least they should, because if they don't they might find themselves behind again. These languages are rising in popularity!) I think this is a good thing, because I work in a Microsoft shop, so I have to code in C#. If C# 3.0 can gain the expressive power of Scheme (while still being C#!) that would be pretty cool.

Python does allow one to look at and manipulate syntax trees

How about Perl6?

Perl6 has macros. See Apocalypse 6. The general approach seems to be Lisp-like, but the details are too weird for me to understand.

This is indeed what I was referring to.

The Apocalypse was discussed here, of course.

I haven't really followed the development of Perl6 much in the last few years. Looks interesting. Thanks for the link.

Ruby doesn't have macros. You can embed queries in the language (sorta) by overloading operators on placeholder objects. Criteria, a Ruby library, does just that... doesn't seem to be very popular, though. A Smalltalk analog would be ROE.

An alternative approach would be using closures instead of macros, as this snippet by Sam Ruby does. But this doesn't work with databases, as far as I can see.

All I could find for Python was SQLComp. It seems to be based on expression trees, just like LINQ. No type-directed translation - a wrapping call to make_query() is used instead.

On further thought... Erik, I don't see the point of type-directed translation here. Don't we lose type inference and composability?

You mention single assignment/dataflow variables...I just posted a proof of concept implementation in Scala you might find interesting. Scala's unification of Functions and Objects lets us do some very neat things.

Future.scala

In there you'll find six implementations of futures:

1. Blocking/Dataflow -- if value not available, block until it is.
2. Promise -- externally settable result.
3. Lazy -- calculate on demand, in calling thread.
4. Concurrent -- spawn new thread for calclation, blocks on get until available.
5. Dependent -- calculated based on modifiable values, fixed expression.
6. Cell -- calculated based on modifiable, variable expression.

These are all unified under Function0[T], so any type of future can be passed anywhere you need a T. Scala's "implicit" keyword is used to "automagically" insert all necessary unboxing, and can also be used to lift functions on T to operate seamlessly on functions of Future[T].