my turn to explain type covariance and contravariance

The Web has a wealth of resources about type covariance and contravariance, but I often find the approach unsatisfying: either code snippets or abstract-ish theoretical axioms. I prefer an additional, intermediate level of understanding that may be called pragmatic. Pragmatically understood, any pattern or concept isn't solely "standalone" snippets or logical axioms. A learner should be able to connect the concept to his or her prior knowledge and also to the question "When would I use this?" I'll attempt to remedy this shortcoming.

For code reuse, a pivotal issue is which data type substitutions in the code will work. Can code written for type Y also function properly for data of type Z? Well, if the definition of data type Z is strictly "Y's definition plus some other stuff", then yes, since the code can treat Z data as if it were Y data. Z is said to be derived from Y. Z is a stricter data type relative to Y. We then say that Z is covariant to Y but Y is contravariant to Z. Code that acts on Y can also act on Z because Z encompasses Y, but code that acts on Z may not be able to act on Y because the code may rely on the "other stuff" in Z beyond Y's definition. In languages that support it, the creation of a data type that's covariant to an existing type can be easily accomplished through inheritance of the existing type's language artifacts. (When someone uses the language feature of inheritance to create a type whose data can't be treated by code as if it were of the original type, confident code reuse is lost, which is the goal behind type covariance/contravariance!)

Thus far I've only mentioned the reuse of one piece of code over any data type covariant to the code's original type. The data varies but the code doesn't. A different yet still eminently practical situation is the need for the code to vary and nevertheless join up with other pieces of code without any of the code failing to work (e.g. a callback). What relationship must there be between the data types of the code pieces in order for the whole to work?

All that's necessary to approach this question is to reapply the same principle: a piece of code that works with data type Y will also work with data type Z provided that Z is covariant to Y. Assume an example gap to be filled by varying candidates of code. In this gap, the incoming data is of original type G and the outgoing data is of original type P.

Consider the code that receives the outgoing data. If the candidate code sends data of type P, the receiving code will work simply because it's written for that original type. If the candidate code sends data of a type covariant to (derived or inherited from) P, the receiving code will work because, as stated before, covariant types can "stand in" for the original type. If the candidate code sends data of a type contravariant to P, the receiving code won't work because it may rely on the parts of P's definition that are included in P alone. (In fact, this should always be true. Whenever it isn't, the receiving code should have instead targeted either a less-strict type or even just an interface. A "snug" data-type yields greater flexibility.) So the rule for the candidate code is that it must be written to send data of type P or covariant to P.

Meanwhile, the code that sends the gap's incoming data has committed to sending it as type G. If G is the original type that the candidate code is written to receive, it will work simply because it's written for that type. If a type covariant to G is the original type that the candidate code is written to receive, it won't work because it may rely on the parts of that type that aren't in G. If a type contravariant to G is the original type that the candidate code is written to receive, it will work because G is covariant to it, and once again covariant types are substitutable. So the rule for the candidate code is that it must be written to receive data of type G or contravariant to G.

Hence, the rules for covariance and contravariance in various programming languages (delegates in C#, generics in Java or C#) are neither arbitrarily set nor needlessly complex. The point is to pursue greater code generality through careful variance among related data types. Static data types are "promises" that quite literally bind code together. Pieces of code may exceed those promises (legal covariance of return); however, the code may not violate those promises (illegal contravariance of return). Pieces of code may gladly accept what is seen as excessively-generous promises (legal contravariance of paramaters); however, no code should expect anything that hasn't been promised (illegal covariance of parameters).

LINQ has your Schwartzian transform right here...

I was looking around for how to do a decorate-sort-undecorate in .Net. Eventually I realized (yeah, yeah, sometimes I'm slow to catch on) that the LINQ "orderby" clause actually makes it incredibly easy. For instance, if you had some table rows from a database query that you needed to sort according to how the values of one of the columns are ordered in an arbitrary external collection...

var sortedRows = from rw in queryResults.AsEnumerable()
orderby externalCollection.IndexOf((string) rw["columnName"])
select rw;

Oh brave new world, that has such query clauses in it! Back when I first read about the Schwartzian transform in Perl, with its hot "map-on-map" action, it took a little while for me to decipher it (my education up to that point had been almost entirely in the imperative paradigm with some elementary OO dashed in).

Between this and not having to learn about pointers, either, programmers who start out today have it too easy. Toss 'em in the C, I say...

UPDATE: Old news. Obviously, others have noticed this long before, and more importantly taken the steps of empirically confirming that LINQ does a Schwartzian under the covers. (I just assumed it was because my mental model of LINQ is of the clauses transforming sequences into new sequences, not ever doing things in-place.)

looking forward to completing your training

It's been a long time since I had anything on here about .Net or F#, but this news is too noteworthy to ignore. Plans are afoot to move F# from a research language into one of the officially-supported, "first-class" .Net languages. That probably means "first-class" more in the sense of IronPython/IronRuby than C#/VB, but in any case Microsoft will be starting to devote real resources to developing F# and further improving its Visual Studio integration (F# has always had the highly-useful "identifier mouseover to see inferred data types" as part of its plugin). Congratulations Don.

with our combined strength we can end this destructive conflict

I haven't written a .Net-related entry for months, simply because I haven't had anything noteworthy to write. The last time I even opened up a F# code file was about as long ago. (But the "Active Patterns" are interesting.)

The DLR seems like a fascinating idea, though: a common runtime/implementation abstraction layer for dynamically-typed languages, similar to the CLR and JVM for statically-typed languages. Hmm, sounds familiar...oh, Parrot. Microsoft does seem to end up creating doppelgangers for everything, doesn't it? A monoculture just has to stay competitive, y'know.

Kidding aside, according to the linked blog post by Jim Hugunin (who has Jython and IronPython cred), the code is under a "BSD-style" license. I'm not great at legalese, so I can't comment on what the specific license precisely allows/enforces. If Microsoft keeps paying talented folks to produce good shtuff that doesn't lead to vendor lock-in, I find it hard to complain. Conflict is overrated. Yet the lack of specifications and fully-functional alternative implementations for important .Net pieces, like ASP.Net, gives me the willies.

update on F#

I haven't used F# much recently, but I've tried to keep myself apprised of it. Don Syme's blog seems like the de-facto news site; many of the following links go there. Let the bullet shooting commence.

• F# has a new "light" syntax option (put #light at the top of the file). With #light, various end-of-line constructs like semicolons or the "in" at the end of a "let" are no longer necessary. Also, groups of statements are delimited by indentation (Python-style). I like the convenience of this option, of course, but my snobbish side feels offended by how it makes ML-style functional code feel even more like the plain imperative kind. So, points for style, maintainability, conciseness, shallower learning curve, etc., but negative points for reducing the tangy esoteric/baroque flavor.
  
• Syme has made a draft chapter of his upcoming F# book available for anyone to read. I recommend it as a supplement or even a replacement to the tutorial information floating around the Web. It's a kinder, gentler approach to learning F#. After reading it, I realized that I could simplify parts of my code by using object methods where possible rather than always calling functions from modules (functions in which the first parameter was the object!).
  
• There are a couple F#-related video clips that were on Channel 9. One is an interview, and the other is a flashy demo. If you already know all about F#, neither of these clips will provide new information. I repeatedly paused the demo clip so I could examine the code on screen. In the interview, Syme is quite diplomatic about the possible real-world uses of F#. While F# may shine at data crunching, it also is a general-purpose language that shares many features with C#.
  
• I went to TIOBE after reading that Python had overtaken C#, and I found that, although F# isn't in the top 20 or even 50, it has a specific mention in the "October Newsflash - brought to you by Paul Jansen" section. To quote:

  Another remarkable language is F#. The first official beta of this Microsoft programming language has been released 3 months ago. This variant of C# with many functional aspects is already at position 56 of the TIOBE index. James Huddlestone (Apress) and Robert Pickering draw my attention to F# via e-mail. Later Ralf Herbrich from the X-box team of Microsoft wrote to me "After working with F# for the last 9 months, I firmly believe that F# has the potential to be the scientific computing language of the future." [...] In summary, I think both Lua and F# have a great future.

Regardless of a programming language's merits, qualitative factors like its buzz level, ease of learning, and PR savvy affect its popularity. As others have noted, Python and Ruby had a long history before achieving notoriety. In spite of still being just a continually-evolving "research project", F# is well on its way.

.Net: He will join us or die

Have I become a mere link blog? One of those newsy blogs that's constantly linking elsewhere and making snide comments, with no original content? How can I justify my existence if I'm just one more "talking head" poring over RSS feeds? What--ah, screw it.

Somehow I ended up at Lisp is sin while I was following a thread along the warp and woof of the Web. I'm glad I did. Sriram's main point is the same one that many others make: over time, everyone is rediscovering the features of Lisp. Sriram's unique spin is that the .Net side of the house may get there sooner. Some evidence: Linq, lsharp, fsharp (which I've reported on in other posts), anonymous delegates, iterators (what the rest of the world calls "generators"). In the example from the blog, the C# 2.0 delegate keyword appears to be the stand-in for lambda. Does a C# 2.0 anonymous delegate form a true closure, with its own lexically-scoped copy of the variables in effect at the time of definition? I don't know. At work we're not yet using 2.0, because our vendor isn't.

Once you finish digesting that link, which is long and informative, read this pdf document by Erik Meijer about how functional programming has reached (will reach) the masses in the form of Visual Basic. I don't know what to believe in anymore...

For Sriram, Lisp is sin because it tempts him to flirt with it over and over again, but without leading to deep, lasting satisfaction. According to him, because of obstacles like a steep learning curve and a lack of libraries, Lisp in its current state cannot thrive in the mainstream. In fact, people have foretold its death for years. A .Net advocate far more militant than Sriram might say, "Lisp and its brethen, or at least the features therein, will join .Net or die." (By the way, I personally believe that popular programming languages never die; they just get reincarnated).

Bonus link: It's not as if Joel on Software needs me linking to it, but in Language Wars he takes a pretty definite stance: for serious, scalable, maintainable, productive Web development, you have merely a handful of choices, but as long as you choose from that group, you can just use whatever you're most comfortable with since the alternatives are about equally capable. Python is "half" on his list, but Ruby and Lisp and Perl are not. Admittedly, I'm not in a cutting-edge startup (far from it), but I don't think he's giving the up-and-comers enough credit. This conservative, enterprise, entrenched approach to Web development has a great deal of inertia, so we shouldn't be surprised if something else shiny and new sneaks up from behind and takes over, like Java did to C++.

.Net: it is you and your abilities the Emperor wants

I haven't mentioned my ongoing .Net indoctrination in a while. I decided to exercise my sub-Padawan F# muscles by reimplementing one of our simplest but still useful portlets. The actual code wasn't anything special: get data, format and show data. The harder part was working out how to write in F# such that the portal would recognize it like a portlet written in the recommended C#. At first, I couldn't get it to work no matter how I futzed with the class declarations, until I realized that by default I was compiling to generic-friendly 2.0, and not the portal's supported 1.1 - d'oh!

An interesting case study of F# vs. C# was my use of Printf.sprintf to substitute parameters into my SQL statement (no, the parameters did not come in from the user, I have heard of SQL injection attacks). The compiler kept complaining every time I tried to separately store the pre-interpolated SQL as a string. It kept telling me, through the handy "mouse over a variable for a type tooltip" F# VS feature, that the first parameter to Printf.sprintf was of type 'a Printf.string_format, or something like that. Eventually the message got through my thick noggin: at compile time Printf.sprintf somehow transforms its first string argument into a function that takes a series of specifically-typed parameters! I had two ways of doing the interpolation: use Printf.sprintf by storing the SQL as a static method that just returns the SQL with a type annotation of 'a Printf.string_format, or use the .Net String.Format method by storing the SQL as an immutable plain string member variable, initialized in the constructor. Either way, I'm storing the SQL as an immutable at the class level.

Some other little tidbits from the experience:

• The general form of the code was "class member function equals pattern match on argument evaluates to let-binding of intermediate step in let-binding of intermediate step in expression to save to a Page mutable property". In other words, for a class method, perform a data transformation through repeated function application and then use an expression with a side-effect to save the transformation result.
• Normally a single F# source file becomes a module, but if you want to go C#-style and use the file to declare a namespace with internal class definitions, just put a 'namespace' line at the top and only declare types (such as classes) at the file's top level.
  
• Watch out for nulls creeping into your code through variables from non-F# .Net APIs! The very handy ?? binary operator appears to return its left argument if it is not null and the right argument if it is. null can also be used in pattern matches.
• F# does not appear to support the usual class access modifiers as other .Net languages. Well, it supports only one, I guess: public. F# (and OCaml, I believe) use a different way to hide implementation: signature files, which seem a bit like a C++ header file containing prototypes.
  

I think it's clear that for frameworks as heavily object-centric as ASP.Net, F# implementations may not be as compelling, since it isn't a context in which F#'s strengths can be best leveraged. To be fair, I'm still a novice at using F#'s object system, so it could also be that I didn't know what I was doing. I could see F# being an excellent language for a library that could be called from ASP.Net, however. F# is not a mere OO language in the crowd for .Net. Presumably the people at Microsoft wanted F# for its unique identity and abilities.

.Net: pathway to many abilities some would consider unnatural

You just know I've been waiting for an opportunity to use that particular dark side quote.

On Saturday afternoon, I decided to learn more about OCaml since it has long been on my list of "interesting languages I should look into sometime". The wikipedia page had a link to the F# project. It is to OCaml as Boo is to Python: a .Net implementation that mutated the language by enhancing some features, smoothing out some rough edges, and, last and least, taking on new restrictions/limitations due to the platform. Here's a nice table. I've read recreationally about some other functional languages like Lisp, Scheme, Haskell, but I must say that OCaml/F# appeals to me the most at this point. Part of the reason may be because of the down-to-earth, clearly written tutorial I skimmed through. Honestly, my comprehension level reminded me of when I learned Perl. When you start out at ground zero, the code looks like so much gibberish (Python would be an example of code that at least looks more welcoming to beginners), but with each little bit you learn the code makes more and more sense. Haskell gave me the same impression, but on the other hand I still can't read Haskell code as fluently as I can read OCaml now.

Some of the specifics I like:

• OCaml is fundamentally functional, but it has perfectly adequate support for imperative and object-oriented styles if the need arises. F# has different ways of doing objects than OCaml, but for the sake of CLR interoperability this could be a hybrid bug/feature. OCaml is multi-paradigm to a pleasing degree. Lazy evaluation can be turned on at will.
• An impressive list of language primitives, and unlike some other languages the primitives are REAL unboxed primitives, not object wrappers. Tuples, lists of course, records, discriminated unions, even references for those cases in which you feel you must have a true variable to store an intermediate result. The syntax doesn't make you want to choke yourself, either.
  
• It has good roots and history. OCaml is not just a project that outgrew its original boundaries; it was carefully architected upon solid theoretical work.
• Static typing without explicit variable type declarations. I like to think of it as adding program efficiency and safety without even trying. Of course, this can only go so far before the programmer needs to intervene to prevent the compiler from guessing wrong, but it's still a marvel. Something about me just gets queasy at the idea of a variable containing a variety of possible things at runtime, or morphing into something else accidentally. OCaml does offer a 'generic' type, by the way, and since its operators can handle all data types, functions with generic type parameters just work without having to write separate code paths per type. Its templating ability is par excellence.
  
• It's not Ruby. I have an irrational animosity toward anything that even hints of being the latest pasture for sheeple, even if the category is "languages with functional features and dynamic (meaning the type is not set at compile time) typing". I hate the concept of a herd controlling my thoughts, with or without my consent.

Unfortunately, I'm not sure that there's a strong case for using OCaml or F# as general-purpose languages. The syntax is definitely tilted toward heavy symbolic/math applications. Some of the examples I have seen look more like algebra than any other programming language, except Haskell perhaps. A hundred lines of Caml will blow your mind. In particular, the example of the 3rd derivative of a sine is still blowing my mind. The great thing about F# is the potential to mate this great power (when wielded responsibility) with the extensive .Net libraries. But I could see myself having trouble explaining an F# program to people who haven't been initiated. OO would feel more natural to them. Thanks to some people at Microsoft Research working on F#, the .Net CLR is a pathway to many abilities some would consider to be unnatural.

.Net: The dark side clouds everything

The past week at work I spent some time reimplementing one of our more complicated, multi-page, multi-function, high-profile portlets using sharpdevelop/web matrix. I'm getting better at the mere mechanics of the conversion, replacing former items in the page template with asp controls and moving code from former actions to page_load and onclick handlers.

The interesting wrinkle this time was a page that has a dynamic form. Not only are the choices different for each category of user, but even the categories of those choices are different. Meaning that the form has a variable number of inputs; in fact, the form is data driven. Of course, adding new inputs would require a change in code, but the order of the form's existing inputs could be rearranged just by modifying an 'ord' field in a database table.

The difficulty is not dynamically creating the inputs, but getting the values from the inputs back out again the next time the form is submitted. Before .Net, I did this by assigning the correct HTML 'name' attribute to each input as it was dynamically created inside the 'repeat' tag's template. Getting the values out on submit was just a matter of keying into the request's form inputs with the relevant name. In .Net, setting the 'name' attribute on an asp control to whatever the hell you want won't work, and it might even mess up its VIEWSTATE processing (the part that automatically keeps track of the current state of all inputs on the page). The control innocently named inside the repeater template receives a new, menacing name once it falls under the Dark influence. So how does one know that the value for data item 'farg3' is in the dynamically generated dropdownlist control with id '&4745_ct100_5'?

I wrote a handler for the ItemDataBound event for the repeater in which the uniqueID property for that generated input goes in the view state bag keyed by the data item name that input was genereated for. Then, when I need the value for a particular data item, I get the uniqueID from the view state bag, start at the repeater control, and recursively search for the input control with that uniqueID. Uuuuuugly, the elegance of recusion notwithstanding, but it seems to work in my tests so far. I bet that there was easier way to accomplish this, but I just didn't know it or find it. Sometimes I like that the .Net controls just sit on the page and handle the details of how they look, but only as long as they take direction like an agreeable actor and not like, well, Brando. I don't have a page any more to work with, but a hierarchy of controls. In this case, that worked against me, because I had trouble seeing the individual value I wanted to inside the shroud. In other words, sometimes the dark side clouds everything.

.Net: The Sith and the Jedi are similar in almost every way

Most of this week I was too busy with other things at work to attack the .Net migration again. When I had a chance, I opted to go for the portlet that collects user feedback and stuffs it in a database. Still one page like the previous one, but at least it was interactive. I had my first real encounter, or should I say collision, with the page lifecycle. I added a RequiredField Validator for the textarea in web matrix, then a simple branch in Page_Load that checks IsPostBack and IsValid. Task done, right? Ohhh no. If it was a Perl CGI script, then that strategy would have worked. Not so here, because the Page_Load event comes before validation happens. That means, Page_Load cannot check IsValid! I know that the "button click" event never really "fires", because on the Web all that happens is documents zipping back and forth over HTTP, browser to server. The game is pretending that the user just clicked a button, and the server is handling that event, rather than receiving a POST. It's an interesting conceptual shift, and I imagine it will feel more natural in visual studio than in sharpdevelop/web matrix. Anyway, I just moved the code from Page_Load to the onClick handler, and that was that.

The real letdown in this round was saving the data out to the database, over the Light/Dark boundary, as our main database is not Sql Server or (heaven forbid) Access. The feedback goes in a CLOB in our database. This turned out to be a point at which my meager .Net experience matched my experience in Java: CLOBs are a pain in the cojones to work with. (The real blame in both cases is, of course, on the database driver implementations and not the platforms). Should have used a varchar, I imagine, but can't change it now. Tried it one way, got a mysterious and unhelpful error message from the driver, then tried it a different way. Joy, another unhelpful error message. Repeat ad nauseum. Finally, after admitting defeat through switching from the database-specific provider classes to the more generic OleDb family, it worked. Have I mentioned that a CLOB should be a last resort data type? We don't need to give our users the ability to spew a novella of bile at us, a short story will do.

The sun still rises in the east and sets in the west, no matter where you live, unless you're in a polar region that has time periods of darkness. Database vendors tend to focus their best driver efforts on whatever platform they see as advantagous. In any case, CLOBs alternately blow and suck. The Sith and the Jedi are similar in almost every way, including their quest for greater power.

.Net: You don't know the power of the dark side

Visual Studio isn't yet on our computers at work, so I opted to try out the sharpdevelop/web matrix combination by reimplementing one of our simpler, existing Java portlets. The portlet was display-only: get user data and show it. No pagination in this case, or viewing options of any kind. No postback whatsoever.

Wading through reference material and examples, I got a rough but working version done much faster than I had expected. The compiler type checks and editor code completion (the corresponding Sith term is intellisense) came in handy here, in the worst case at least allowing for faster typo-free typing. There were only a handful of controls on the web form, so I can't claim to have truly tested web matrix. I can see how it could get tedious trying to keep the control declarations synchronized between the aspx in web matrix and the code behind in sharpdevelop...from what I read, visual studio does that task for you.

The biggest hurdle was getting the database access working, of course. The .Net provider installed without any trouble, but when I tried a 'using', my combine failed to build. A quick web search showed the newbie that one must go to the project tab, right click on references, and add the assembly reference before 'using'. It's even in SD's FAQ. After that, I moved on to getting the connection string exactly right. And finally, figuring out which methods on which objects in which combinations in order to execute a few queries. For my first attempt to display the data, I used a custom grid control that happened to be in the example I was following. It worked in a way that felt a bit kludgy, but then I noticed that the custom control was a subclass of DataGrid. I switched to using a vanilla DataGrid for the sake of standardization. Suddenly I was able to precisely define the columns of my DataGrid within the web matrix GUI. After looking up what else my asp.net training book had to say about DataGrid, I'm feeling excited. I hope Java doesn't have a custom data table-generating tag with DataGrid's combination of flexiblity and ease, because if it does then I had been working much harder than I had to.

My initial foray into .Net development has remained positive. I am getting the impression that even as I learn, I still do not know on a palpable level the power of the dark side.

Quicker, Easier, More Seductive

At work we're planning to switch from Java to .Net, because we're switching our existing Java portal for a .Net portal (both proprietary, by the way). We've received books and a short time in the future the portal vendor will send someone out for a three-day training in portlet development. As time and duties allow, I've been skipping around in the books, researching various .Net resources and projects online, and trying out some code just to test my growing understanding. We don't have official development environments set up, so no Visual Studio .Net 2003 on my computer yet. 2005 appears to not be recommended by the vendor since the portal hasn't yet been ported to .Net 2.0. It seems to me that any modern tool should be able to target a particular platform version, but whatever.

I do have to say that, even without Visual Studio, the books and the code that I have experimented with give the impression that the ASP.Net framework has its act together. There are web controls, validation controls, the ability to make custom controls. Each control "knows" what it has to generate on the page and it exposes clear properties or attributes to make it fit into a given situation. And the programming model is all event-driven, with the server firing events from controls in a predictable manner. (Hmm, suddenly I don't think this resemblance to JSF is accidental...) C# is Java but without its warts. Then there's Boo, which I found just earlier today. Boo is Python for the .Net CLR but without its warts. .Net has a large number of third-party controls floating around to experiment with, in addition to Java doppelgangers NHiberate, NAnt, iBatis, etc. The .Net API has so much thrown in, and it makes data access and binding simple enough, that there may not be as much call for external libraries or frameworks.

I'm not convinced that this .Net approach of closely coupling code to page components is better for maintainability than a clean separation from View to Action (*cough* WebWork *cough*). Meaning, I'm not sure this .Net approach is more powerful, but I can say that even without Visual Studio it seems quicker, easier, and more seductive than the usual Java EE.