Lambda the Ultimate

It's so funny how it seems like you, David Barbour and Sean McDirmid seem to have answers to things I am curious about :)

My interest isn't really in making the Web a better place for CSS, though :)

Have you seen Greg Bardos' Ph.D. thesis? I just linked to it on my tumbelog: Extending Interactive Graphical Applications with Constraints. Haven't read it yet, but it looks interesting, and I know Bardos is a genius (he is basically one of the top guys at Google).

Yes. Unfortunately, it has little to do with using constraints as a semantic basis for graphical applications: he extends parts to use them, and uses the core of CSS without. Sort of like adding a linear constraint library to Silverlight and then invoking it in the binding layer; close, but not quite it. The overall Cassowary project is very inspirational, but also a cautionary tale. This stuff is hard, especially once you care about performance.

My goal is a good layout language for mobile (i.e., resource-constrained) devices. I'm not the biggest fan of CSS, and it currently does not fit the bill in neither goodness nor performance; however, when doing research, I'm with Hoare on analyzing one thing at a time. Right now I'm doing static layout + rendering performance and, hopefully, this summer will start on incrementalism and analyzability. Given such a fundamental understanding (+ my own industry experience here), hopefully reach a point where I can do a cleaner approach to design (and/or graduate).

I'm not the biggest fan of CSS, and it currently does not fit the bill in neither goodness nor performance;

Only criticisms I've found about CSS was in Chris Anderson's Essential WPF book (sort of handwaving, probably not trying to intimidate readers too much) and INRIA's Hop programming system; see section 2.2 of Serrano's The Hop Development Kit for Scheme.

Most of my interest in this point actually stems off of Anderson's comments that cascading stylesheets are not all that. I'll dig up the exact pages in the book at some point, it's in the chapter on Styles, and chances are you can just use Google Reader to snatch up the relevant discussion.

There are a lot of problems. Off the top of my head:

-- poor abstraction / reuse facilities in selectors and property lists
-- no notions like encapsulation or containment within the static stylesheet, must be encoded
-- specificity is used for selectors but not properties
-- poor handling of text (as opposed to boxes)
-- no GPU-ish support (textures, shaders, etc.)
-- box model (width/margin/padding/borders) are broken; even the creator wrote this in his thesis
-- ~12-pass rendering priority instead of a HTML-tree driven containment ordering
-- ambiguity on constraints (min/pref widths, float positioning)
-- poor orthogonality of many features (particular core relationships between display inline/block/inlineblock and floats and overflow).

Etc., etc. . Again -- I'm just working on the performance side right now, so don't expect much from me :) I believe either Reddit or Digg has their own Python-based CSS generator from a richer language, and I bet Google does too. The PL community hasn't done much for the web community in terms of pragmatics, as is becoming painfully obvious when researchers try to do formal (e.g., security analysis) stuff for web apps. XHTML, JavaScript, and CSS -- the core -- are painful. I'm not very knowledgeable about HTTP/protocols, but as obvious by the discussion here on Doloto, we aren't delivering applications to clients in the right way.

I'll update this as I move through the paper, but there is another component besides Google manually optimizing page designs - layout renders must be personalized per device to help with the UX. Chris Lord has a good summary on techniques used today in Displaying Web Content on Small Displays; he also has a similar overview in his Ph.D. dissertation: Small-Screen HTML Rendering on Memory Constrained Devices.

So I think there is an architecture / software engineering component to "next gen browsers".

I also see you cite Greg Bardos' Cassowary constraint solver project on Page 10, but you say they are insufficient for CSS. Yet you don't cite Bardos' Ph.D. thesis as the authoritative reference. Why not? (I still haven't read it of course!, but is there a paper discussing why this is specifically an "open problem"?)

layout renders must be personalized per device to help with the UX.

I talked about that in my introduction section: instead of just rewriting their style for the new device, reusing existing JavaScript etc., developers switch languages entirely when going mobile. That's an indictment of modern browsers. Multitouch etc. APIs exist; performance doesn't.

. Yet you don't cite Bardos' Ph.D. thesis as the authoritative reference. Why not? (I still haven't read it of course!, but is there a paper discussing why this is specifically an "open problem"?)

I cited the computational core (the Cassowary solver) which I'm guessing Greg started to work on later -- I thought that was the canonical reference. I had to drop a lot of content in the paper due to low page count for WWW; will add to extended version.

It's an open problem because nobody has solved it ;-) As far as I can tell, Lin's paper at HP has made the most progress. Systems like Garnet and Amulet laid out a vision for a nice linguistic basis for these systems, but nobody has hit it.

Linear constraints, to me, sound like an optimistic choice when you have stuff like conditionals (and unevaluated by their proponents by say translating common layout languages into them). However, I came from a school where I saw Pascal Van Hentenryck and Meinolf Sellmann do amazing things with constraint problems, so I expect there's a more expressive formulation (e.g., I played with quadratic constraints a couple summers ago). I think we're close with the linearly-bounded attribute grammar stuff: CSS shows many common metaphors are good for layout, I've had promising results in this approach to formulating it, and there have been theoretical (though not practical) results in incrementalizing them.

Edit: The question of whether the layout engine should override the layout of a page is still open (there are papers about this every year in WWW/Multimedia/UIST/etc.). I think systems like CSS have the right approach, though the abstractions and tools are still primitive: let the designer specify how content works in different contexts. Subjectively, all of the content reformatting tools I've seen looks bad. That doesn't mean they always will nor that they're worse than the alternative (a layout aimed at the wrong format). However, I'm interested in the typical case where a designer is willing to target multiple mediums. CSS supports this to an extent (media types and constraints) but clearly falls down (see some of David Salesin's UI papers); exploring the boundary and abstractions further is fun but a distinct topic.

I was not being fair to Greg Badros'' thesis. The relevant section is chapter 5. He shows

-- cascading can be understood in terms of prioritized constraints. I just didn't find that to be a surprise because that's how the CSS specification describes them: a rule prioritization algorithm.

-- many non-layout constraints, such as font family and size, are a question of inheritance or functional dependence (20% of 30% of 10% of 200px); he correctly points out mixing linear constraints with finite domain ones work here.

-- the problem is the layout language (once conflicting constraints are removed) where we have most of the confusion is not related to his work. E.g., word-wrapping (see Lin's paper) or floats and shrink-to-fit sizing (see mine). The box model is a beast.