Lambda the Ultimate

I think it's high time to have a good, possibly long, and decidedly newbie-friendly meta-discussion about Lambda the Ultimate. Of particular interest is the goals of the site, suitable topics of discussion, and general etiquette.

As I've said before, I have been bothered by the way "off topic" discussions have been handled lately. Moreover, it appears that Ehud's recent front-page post, while accurate, has brought site participation to a virtual standstill.

Again, some of this policing is necessary to maintain the quality of this site, but the civil libertarian in me would like to gracefully accommodate wider participation while maintaining attractive discussions and overall site content.

Let me open this discussion with an extremely astute observation by Philip Wadler:

My experience on the Haskell committee caused me to formulate 'Wadler's Law': time spent in debating a feature doubles as one moves down the following list:

* Semantics
* Syntax
* Lexical syntax
* Lexical syntax of comments

The reason for this is quite simple: it's easy to debate the lexical syntax of comments, whereas it's hard to make meaningful insights into semantics, especially for a language that is as esoteric as Haskell was 20 years ago.

Naturally, more people will be able to offer an informed opinion on the latter topics, even though we shouldn't care as much as we move down the list. (and many of us don't)

Thus, if we model human behavior as a Markov chain, even assuming that each individual person is (somewhat) less likely to add to a lengthy discussion of such trivialities, it's only natural that there will be much more discussion generated on the easy topics. LtU is no exception to this rule.

I absolutely love it when we are graced with the participation of some of LtU's highest-profile members, including Philip Wadler, Lennart Augustsson, Tim Sweeney, Conal Elliott, and Oleg. (who needs no last name) These people are all easily smarter and more knowledgeable than myself, and it makes me very happy that we can attract such participation from time to time.

Of course, there are plenty of other members that fall into the same category, that don't (yet) have quite the same level of fame. Anton van Straaten and neelk immediately come to mind. I don't intend to slight anybody by acknowledging these particular members; my choices reveal more about my own personal (and often obvious) programming biases than anything else.

The elite should also realize that due to Wadler's Law, the more intelligent or abstruse the comment or post, the harder and more time consuming it is to produce a meaningful response. So don't feel too slighted if you don't get as much response as you hoped for, or some noob makes a patently silly or overly longwinded comment. If an appropriate response to such a comment is obvious to me, believe me, I've got your back. Of course, the better I understand your work, the better I will be able to help.

Let me wrap this lengthy post up with one final, but critical point: LtU is not only about the elite, who we welcome with open arms, but also relative newbies like myself, or even total newbies that have no background but have the interest and enthusiasm to stick around and learn something.

If you fall into this last category, your first priority should be to figure out the right questions to ask. Figure out how to provoke us into sharing what we know. And if you think you have some insight, by all means, try.

In the mean time, we'll try to cut you some slack, but try not to be too obnoxious. If you can correct Oleg, by all means, go for it. I definitely want to read it. But beware, the odds are not in your favor. You definitely want to double and triple check your work.

In concurrence with our illustrious and over-worked dictator for life, Ehud Lamm, I would direct everybody to re-read the Spirit Page. Dominic Fox's testimonial is particularly compelling. He deserves to be LtU-famous as well, for very successfully being a total noob.

If you go back and re-read Dominic's comments in the archives, it is unfortunate that he hasn't been around much lately. I suspect that growing demands from his family and his job keep him quite busy these days.

So, in conclusion, I want to hear about your perception of LtU. My goal here is to make LtU better. Any insights into or questions about goals, topics, ettiquette, or even site mechanics are particularly welcome. How can we attract both elite experts and enthusiastic novices without alienating the experts or intimidating the novices?

Equality Saturation: A New Approach to Optimization, Ross Tate, Michael Stepp, Zachary Tatlock, Sorin Lerner, POPL 2009.

Optimizations in a traditional compiler are applied sequentially, with each optimization destructively modifying the program to produce a transformed program that is then passed to the next optimization.

We present a new approach for structuring the optimization phase of a compiler. In our approach, optimizations take the form of equality analyses that add equality information to a common intermediate representation. The optimizer works by repeatedly applying these analyses to infer equivalences between program fragments, thus saturating the intermediate representation with equalities. Once saturated, the intermediate representation encodes multiple optimized versions of the input program.

At this point, a profitability heuristic picks the final optimized program from the various programs represented in the saturated representation. Our proposed way of structuring optimizers has a variety of benefits over previous approaches: our approach obviates the need to worry about optimization ordering, enables the use of a global optimization heuristic that selects among fully optimized programs, and can be used to perform translation validation, even on compilers other than our own.

We present our approach, formalize it, and describe our choice of intermediate representation. We also present experimental results showing that our approach is practical in terms of time and space overhead, is effective at discovering intricate optimization opportunities, and is effective at performing translation validation for a realistic optimizer.

I thought this was one of the more interesting papers at POPL this year. The idea of tackling the phase ordering problem by splitting the problem into two steps --- first computing classes of equivalent programs, and second picking the best member of the equivalence class --- is very clever.