The Good Soldier LMeyerov

The point of semantics

2009-06-29T00:17:00.000-07:00

There are essentially three purposes for language semantics. Overall, as a smell test to guide language design: if you can't define a feature, it's probably bad. Second, to help other implementers of our language and programmers for the language -- unfortunately, I'd claim we generally fail on this point. Third, to help structure proofs about our language.

As part of the preparation for a paper submission, I'm finishing up my formalization of a subset of CSS 2.1 (blocks, inlines, inline-blocks, and floats) from last year. My first two, direct formalization approaches failed the smell test so Ras and I created a more orthogonal kernel language. It's small, and as the CSS spec is a scattered hodge-podge of prose and visual examples riddled with ambiguities, we phrase it as a total and deterministic attribute grammar that is easy to evaluate in parallel. Finally, to prove that it can be implemented efficiently (e.g., linear in the number of elements on a page, meaning no reflows), the grammar without floats leads to a syntactic proof, and the version with floats then only has to explain away some edge cases (using a single-assignment invariant, which can probably also be made syntactic).

All of this should have happened 10 years ago. However, the academic language design community, as per the norm, seems to have been late to the party. Instead, we have huge, slow interpreters that don't give the same answers and a generation of abused and confused artists and designers.

An evil test case

2009-06-26T23:23:00.000-07:00

Opera, WebKit, and Firefox are supposed to conform to CSS 2.1 standards, at least, right?

A fun test:


<div style="width: 30px; height: 30px; background-color: blue; padding: 1px">
  <div style="display: block; background-color: red; padding: 1px">
  <div style="opacity: .1; float: left; width: 100px; height: 40px; background-color: green">a</div>
  <div style="opacity: .2; float: left; width: 100px; height: 40px; background-color: green">b</div>
  <div style="opacity: .3; float: left; width: 100px; height: 40px; background-color: green">c</div>
  <div style="width: 50px; height: 10px; background-color: green">d</div>
  </div>
</div>

Do three versions of it: set the red box to be display block, inline-block, and inline. A little subtle to why this breaks is that, while these browsers might conform to the CSS specification for these (I'm still not sure about this), it exercises ambiguously defined parts of the spec.

For the few folks actually implementing this stuff, it exercises ambiguity in the definition of preferred widths, preferred minimum widths, and shrink-to-fit in the presence of floats.

Formalizing one fully-defined interpretation of the spec is... interesting. Thought I was done, but realized I wasn't =/

First weekend in Seattle

2009-06-12T22:25:00.001-07:00

Still looking for a place, but Capitol Hill successfully captured my heart:

Lunch: jamon serrano crepe @ joe bar cafe
Snack: picked up a copy of Pride and Prejudice and Zombies and headed off to another cafe
Discovered Dilletante, a chocolate cafe and chocolate martini bar -- opens at 4pm, so on my TODO list

I also somehow came across two free passes to the Seattle International Film Festival that is ending this weekend. Viable candidates (will see one each on both remaining days; haven't found anyone else who is interested yet):

Saturday:

~~In Your Absence~~
Breathless (it was great!)
~~Fifty Dead Men~~
~~Flame & Citron~~
~~Forever Enthralled~~

Sunday:

~~Marcello Marcello~~
The Shaft (done well)
~~Involuntary~~
~~OSS 117: Lost in Rio (+ closing gala)~~
~~The Overbrook Brothers~~
~~A Pain in the Ass~~

300+ movies over one month... that's an intense festival. Despite the lack of an apartment and a slowdown on my research, summer is going well (and I apparently had a subletter for my place in Berkeley without realizing it!)

RazorFish

2009-06-11T08:35:00.000-07:00

I think the most significant demonstration was somewhere between 5:00 and 5:30. Would have loved to have hacked on this in high school :)

Security as a Disease

2009-06-07T09:10:00.000-07:00

Lovely post by Rob Meijer on the capability list about how to write a useful Wikipedia article (in particular, for cleaning up the entry on ambient authority):

A good way for me personally to think about the audience for infosec related subjects, is to think about myself on medical related subjects.

...

In this case, the main things you would want to know would be:

* How do I know if I have ambientitus?

If I know I don't have ambientitus, I'm out, off to find other possible sources of my symptom. If it is likely that I have ambientitus, I would want to know:

* How bad is it? Is it fatal?

...

That totally made my morning. Worth reading.

updateable secure views

2009-06-05T20:17:00.000-07:00

Was looking at what the bidirectional programming folks at UPenn were up to, and got excited: the paper we had rejected last year about secure browser programming through views was, in another form, accepted for these guys: Updateable Security Views. Our take on it (a tentative title was "membranes, views, and browsers") was of capabilities and flexibility; this clearly has different principles (static checking, information flow, etc.). The important thing is that the idea is gaining traction!

Assembly Language of the Web

2009-06-04T20:48:00.000-07:00

What should be the assembly language of the web? JavaScript has risen as the pragmatic choice, with the Flash VM trailing far behind. Some elements of Google think x86 is the way to go.

With Flapjax, JS was a fine choice: we were interested in rewiring existing AJAX-style apps and could do it. Sometimes, with both Flapjax and the membrane work, it wasn't enough (weak references, reflection / interpositioning woes, no good separability). Other notions, like parallelism and DB transactions, are just missing entirely (e.g., workers were not enough when I did some Firefox extension work).

Given a void, what's the way forward? CLR? DLR? JS? x86? VMs? Folks like Erik Meijer and Gilad Bracha seem comfortable with JS is the new assembly, but I'm not. At best, it would then need an overhaul that it isn't getting, and, at worst, we're slowing the web down by maybe 5-10 years.

Exciting times!

2009-05-27T00:36:00.001-07:00

Thought I'd post a quick status update. I will not actually be here this summer!

1. Browser stuff. Over the next month, I'll be bouncing around and hopefully finishing the initial version of my parallel web page layout algorithms. In the fall, I want to make sure it's all stitched together and then might switch into thinking about adaptivity or, even more general, parallel scripting.

2. Webpage model extraction / exploration stuff. After the browser work reaches a good state (PPoPP?), I'll be rewriting and scaling out our blackbox analyzer and will make it directed. If collaboration works out, there'll be some interesting twists (either a new type of analysis or integrating and expanding some earlier whitebox ideas)

3. Summer! Something mysterious at Microsoft Research about browser security. I'm guessing/hoping a principled clean-slate approach or some program analysis.

One of many flights start tomorrow.

mixing thread-aware and thread-agnostic code

2009-05-25T00:46:00.000-07:00

For almost all of the algorithms I've been playing with for the parallel browser, Cilk-style parallelism matches. My development pattern is to do a sequential version, do a Cilk++ sketch, and then, for final tweaking, convert to TBB. (... and a lot of iteration involving hawkish monitoring of KCacheGrind statistics). However, invariably, something always goes wrong.

This week, it's using task-parallelism with a multi-threaded library. Task parallelism gets you away from the notion of a thread: whenever you have a unit of work, you just spawn it off, and thus may have many tasks for only a few processors. With threads, assuming you're CPU bound, you have as many threads as processors. FreeType2 is written for threaded use: each thread gets its own Library. However, task parallel usage (I'm rendering a bunch of glyphs: turning one character into a pixel can be thought of as a task) doesn't map nicely -- if I were to create a Library per task, I'd have to create thousands of Libraries instead of, say, 8.

The naive solution is to set up a resource pool: a task asks the pool for a Library when it starts, and returns it when it finishes. If there is no Library available, it gets created. If tasks are really small (e.g., individual characters, as opposed to, say, words), there'll be a lot of chatter when trying to get these Libraries (and, even if not, locks waste cycles, which is still a penalty proportional to task size).

TBB, because it is a library level solution, has actual task objects (Cilk should just puts some sort of continuation mark on the stack) and therefore faces the same problem all the time. It provides conveniences for reusing task objects (think of it like a manual TCO or trampoline). When reusing a task, a good habit can be to reuse data within it. In this case, when a task completes, it passes off its Library object to the next one that gets/becomes the reified task object.

Unfortunately, I don't think the code will work out that well. In reality, there's a hierarchy of resources (Library -> {Font}, Font -> {Glyph}). It'll work, but the impedance mismatch will cause some slowdowns.

collaborative security

2009-05-20T21:42:00.000-07:00

Was watching a video of Aza Raskin and, around 18:00, I got excited. Can we treat security as a people problem?

I've been mulling about this both in my work in overcoming data silos and in extracting models of applications. In the former, the user might want to add extra security to an app like google calendar, say by doing special permissions on for a particular event or even encrypting data before Google sees it, and, in the model extraction, I'd like users to pool their models together to collaboratively get bigger ones -- but I don't want stuff like bank account info to leak over. This latter problem occurs slightly differently in some of my work in mashup security: can we trust an extension to translate a webpage, but not, say, leak a bank account number?

Everyone, including Aza, bashed on the UAC: we can't just pepper users with dialog boxes. We really want things like blacklists That Just Work. Aza asks, just as we might trust a smart nephew to buy us a computer, might we trust one to figure out security for us? In the absence of a smart nephew, can we learn the security policy? What do cautious people normally say to a dialog box? Is there a bit of information on a page that users generally mark as privileged?

In three of my projects so far, I've found cases where I didn't think the application writer could a priori determine the appropriate action, yet doubt that the casual web user can either. What would it mean to build a browser or application extension that outsources security?

The magical incantation

2009-05-20T16:06:00.001-07:00

//height in font units => height in pixels
int height = ((*(cachedFont->face))->height / ( (int) (*(cachedFont->face))->units_per_EM)) * fsizev * (RESOLUTION / 72);

extension idea

2009-05-17T22:03:00.000-07:00

Turn any html table into a spreadsheet.

I wanted to average some columns in a web page I was looking at, but Excel no longer copies/pastes correctly :(

Android != Web

2009-05-12T23:52:00.001-07:00

I get asked three questions pretty frequently when I mention I'm trying to parallelize web browsers as a way to make phones faster.

First, folks ask about Chrome. No, not like Chrome -- parallel processes might as well be concurrent; the point there was OS/hardware enforced address and maybe time/resource scheduling separation to provide security guarantees.*

Second, what about V8, Tamarin, Tracemonkey, etc.? These are awesome and I wish I had skills like that. However, two caveats. First, most of the time in a browser is not spent in the JavaScript runtime. Therefore, despite being a language geek, that's not what I'm working on speeding up. Second, Proebstring's Law tells us that compiler speedups give us 4% speedup a year while new hardware give us 60%. Now that JavaScript is getting serious compiler attention (e.g., not being interpreted), I wouldn't be surprised at maybe another 2-3x speedup over the next couple of years. However, then it'll reach a similar state to Java and Proebstring's Law will apply. If you consider that we can effectively get an extra core of performance every year or two, perhaps maybe we should listen to Proebstring and take advantage of the hardware.

Finally, folks wonder about the iPhone, Android, and their relation to the web. A surprising thing here is that, despite Google and Apple both pushing the web as a platform (viz. Chrome and Safari, respectively), they are also torpedoing it. Contrary to mass perception, my technology-driven understanding is that Android and the iPhone SDK are anti-web. Currently, they're a necessary evil for performance reasons, but they are also distinctly outside of the web ecosystem. I am working to make high-level domain specific web languages (e.g., CSS) fast enough to avoid the need for a return to such lower-level systems.**

Back to work...

*Interestingly enough, the Chrome security model isn't good for say, mashups or extensions, and there are faster ways to achieve what it is currently being used for (also, in part, researched by Google!). I think pragmatism, such as for time-to-market concerns, had a sad impact here.

**Android is interesting and important for many other reasons, such as opening up phone functionality and a push towards rethinking the integration of a browser into an operating system.

Hurray, a paper acceptance!

2009-05-10T16:59:00.000-07:00

In the words of an esteemed collaborator, "DisneyWorld, whoooo!". [OOPSLA, 2009]

2 out of 4 so far this year (hopefully, after a lot more polishing, be 4/5 by the end of it!):

This paper presents Flapjax, a language designed for contemporary Web applications. These applications communicate with servers and have rich, interactive interfaces. Flapjax provides two key features that simplify writing these applications. First, it provides event streams, a uniform abstraction for communication within a program as well as with external Web services. Second, the language itself is reactive: it automatically tracks data dependencies and propagates updates along those dataﬂows. This allows developers to write reactive interfaces in a declarative and compositional style.

Flapjax is built on top of JavaScript. It runs on unmodiﬁed browsers and readily interoperates with existing JavaScript code. It is usable as either a programming language (that is compiled to JavaScript) or as a JavaScript library, and is designed for both uses. This paper presents the language, its design decisions, and illustrative examples drawn from several working Flapjax applications.

I'll be keeping quiet on what my next thoughts on it are for awhile (three biggies on my mind, however: sharing, search, and parallelism) -- hopefully the next public things will be sometime next winter. Edit: one last biggie. Live programming.

software licenses

2009-05-06T20:38:00.001-07:00

Finally, a reason to use types.

Hurray for SPJ

2009-05-05T23:53:00.000-07:00

Just one tidbit from SPJ on writing papers:

Every review is gold dust

Be (truly) grateful for criticism as well as praise

This is really, really, really hard

But it’s really, really, really, really, really, really important

Whenever I prepare a new talk or am writing a paper, I always check back to his hints. Dave Patterson also has some useful advice on how to have a bad career.

On a more fun note.. starting to architect the world's fastest font rendering engine.

information flow security

2009-05-03T00:52:00.000-07:00

This has been bugging me for awhile: while I find the research questions surrounding information flow fascinating and important, when did it transform from a program analysis idea into a usable, deployable security one? It seems just like STM: there's been a huge emphasis on it in the community, but shockingly relatively little analysis of wide-scale deployments -- apparently even the browser guys at MS & Mozilla have sunk their teeth into information flow now.

I get it for low-level systems: if you can run an analysis to detect leaks just like you do for buffer overflows, great! However, when I start thinking about something like mashup security, its lossy/conservative nature seems like an awkward fit, in which case we're back at square one. Worse, when I type "information flow usability" into google, the result is about type inference.

Information flow analysis is a fundamental program analysis question. Building an information flow type system / language / etc. is a principled research approach. While I'm still enthusiastic about adding something like gradual types to a scripting language (for both performance and correctness -- and I view it as a fairly conservative extension), I'm worried about adding qualifiers for information flow: relying on this is much deeper and I'm not convinced expressiveness and usability have been adequately investigated (though the Jif guys do have some interesting case studies there). Again, if you can check a property using information flow analysis, that's great, but I'm surprised by the emphasis on static/type support for it, and have no clue as to how far it gets it. Are we over-optimizing something tiny or does it hit some sweet spots?

Maybe I'm the only one. Next week will be interesting..

sequential render

2009-04-23T00:26:00.000-07:00

Last semester, I wrote up the semantics of a kernel of CSS and proposed a parallel evaluation strategy, but never got to implementing it beyond seeing how a very simple computational model of it would perform. It wasn't clear that the semantics made any sense... until now.

Running it sequentially:

Line-wrapping horizontal layout, including a vertical layout child, an image (white box, blogger killed it), and some text.

Thus, my parallel vertical and horizontal layout decompositions make sense. I'll try to parallelize these over the next week couple of weeks for the proof-of-concept before moving on to floats (viz. speculative execution) and then figuring out table semantics. The biggest stumbling block is actually calling into lower-level systems, not the algorithm itself. I don't know them, and need to worry about things like reentrant calls into font libraries when I'm sure they're doing optimizations requiring synchronization like memoization. On the plus side, I can finally learn some of Knuth's formatting algorithms (and modernize them ;-)).

So many ideas

2009-04-20T00:53:00.000-07:00

so little time :(

May should be a fun month.

Fun Talks at CodeCon

2009-04-18T22:18:00.000-07:00

Went to my first CodeCon today. (I'll be talking tomorrow about the what and why of my parallel browser project.)

CodeCon felt like emerging from a dark tunnel.

First, I like their standards. A depressingly recurring theme in the research I see on a typical day is the lack of true motivation and understanding. Successful languages and frameworks are typically (originally) paired with successful products because you can't solve everybody's problems if you haven't solved anybody's. CodeCon makes a point to celebrate those in the guts of the matter; academia penalizes them (and encourages us to write too much trendy and incremental crap). At CodeCon, if you can't give a cool (for many notions of cool) demo, your talk is awkward.

Second, and somewhat related, there is an emphasis on fostering subcultures that do something tangible. This mixture of TED and Burning Man ideals highlights how technology might interact with our lives. The do-it-yourself biohacking talk and Tahoe capability URLs talk were great because of that (and, adding to my interest in Tahoe, I had spec'd out a project last year for breaking the data wall that, for the server part, had a lot of the same highlevel design!). The vetting for talks is good: many were inspiring (... or would have been if I hadn't previously been inspired by them).

Third, the speakers are the active developers of the projects, and everyone in the audience is probably the same. As a friend remarked, it's always amusing to see a professor present a student's work. In terms of hallway conversations, this mix of people is a revealing lot.

CodeCon was not what I expected at all, more for the better than the worse. Now that I have a better feel for what CodeCon is, I probably should add more motivation and some notion of a demo to my talk :)

HCI challenge

2009-04-16T00:27:00.000-07:00

Describe a mobile interface that you can use while walking. Audio doesn't count: I don't want to listen to nor talk to machines. Similarly, the domain should not be too specific (e.g., the next button on a MP3 player, or the indicator for a heart rate monitor). Bell's law, taking advantage of Moore's law, predicts that smaller devices like handhelds will soon not only replace laptops but surpass them. One way might be computing while on the go.

Thinking outside of the (iPhone) box is encouraged. This problem has been bugging me all day.

Oh wikipedia

2009-04-15T19:50:00.000-07:00

I often feel that wikipedia articles make a binary decision between legibility (and, likely, over-simplification) and precision (and, likely, being opaque).

Double buffering was a breath of fresh air:

Now consider how you would do it if you had two buckets. You would fill the first bucket and then swap the second in under the running tap. You then have the length of time it takes for the second bucket to fill in order to empty the first into the paddling pool. When you return you can simply swap the buckets so that the first is now filling again, during which time you can empty the second into the pool. This can be repeated until the pool is full. It is clear to see that this technique will fill the pool far faster as there is much less time spent waiting, doing nothing, whilst buckets fill. This is analogous to double buffering. The tap can be on all the time and does not have to wait whilst the processing is done.

In computer science the situation of having a running tap that cannot be, or should not be, turned off is common (such as a stream of audio). Also, computers typically prefer to deal with chunks of data rather than streams. In such situations double buffering is often employed.

ECMAScript 5, I've got needs!

2009-04-13T23:44:00.000-07:00

ECMAScript 5... because 3.1 and 4 drowned in politics? Nah, not really -- the relatively superficial update of 3.1 prevailed (because that's what we need after 10 years and the mass migration of applications to the web, right?). Snark: I'm not sure how I feel about standardizing libraries such as for JSON nor the push for generators; perhaps my Scheme roots are showing.

I wanted to submit a comment about the incomplete meta programming capabilities that cropped up in my work on membranes, but I couldn't understand the spec. Perhaps someone has a better shot, because these I actually do care about (and don't relate to the DOM):

The problems occurred when I was trying to create a shadow-copy of an object where I would add funny behavior whenever a call on the shadow would get proxied to the original. The motivation was to enable an application to take one of its objects and communicate it to an untrusted application, and by only sending shadow copies, guarentee the untrusted receiver couldn't get access to the privileged, original objects (or any other privileged ones made accessible by them via potential object graphs). Proxying generally worked. I'd create a new object, look at the (shallow) fields of the original object, and then define setters and getters on the copy for those fields to do all the proxying magic. There is some fun(ny) recursiveness necessary to get this membrane right, and, if you care, I can send you our paper about it.

A lot of important encapsulation and consistency considerations occur, which is important if we want people to be writing secure mashups in JavaScript without resorting to annoying subsets:

What about proxying the definition and extraction of setter and getter functions? Can we redefine the getter and setter for the functions to get, set, and use them?
What about the setters and getters for the prototype field?
It's impossible to define the getter for a missing field (not as much of a security problem, but a huge expressitivity gap, which hit me hard here)
Root prototype poisoning. It should be possible to define new 'root' prototype instances, making it more natural to protect and pass around privileged objects.
Adding and deleting fields should also be introspectable and adviseable.

There are features that I think would be neat, like guarenteed tail-call optimizations, but I view the lack of the above as fundamental weaknesses and incomplete specifications. I can trampoline recursive code pretty easily, but we don't see how to write secure membranes around arbitrary JavaScript objects without these (or writing a BetterJavaScript=>JavaScript compiler, which is stupid as these are basic).

Regardless, at this point, I'm happy to get anything! The committee has gone through a lot, and there's a lot of pressure on making sure what they release does not have holes. Perhaps that's my meta-problem with the whole process: without a benevolent dictator and given the emphasis on folks writing standards compliant code, there is too much pressure against adding fundamental features and not enough for fixing the code we're writing today. At least that means whatever gets through is probably good :)

Addendum: I really, really want weak references, or at least a dictionary with weak references. Adobe already provides this and I think Microsoft does too. JavaScript is typically used in reactive settings, so this would be a big expressive win. Again, I can implement my own TCO or macro system on top, but weak references seem too deep. (Addendum 2: the lack of weak references led to potential memory leaks in both Flapjax and the membrane system. They're an important building block.)

Crazy Fast

2009-04-13T03:04:00.000-07:00

After some more data representation and cache tuning.. it takes 1-2ms to match all of the CSS selectors on slashdot/facebook against the DOM (on a Nehalem).

Preprocessing, like parsing, now dominates the computation probably by a factor of like 50x. Crazy.

ChordMate for Windows

2009-04-13T00:52:00.000-07:00

Obligatory shout out: Ilya released the Windows version of ChordMate (a chord exploration tool for guitar players) so it's not just for us OS X (ab)users anymore.

It's useful even if you're just reading tabs. It helps find alternate phrasings, even in multiple positions, so there's even less of a reason to play power chords.

And it's pretty :)