Puzzle: “Correspondence, of a sort”

If you’ve seen me in the past year or so, you’ve probably seen me with a crossword puzzle. I’ve thought about making one for a long time. This week, I dorked out beyond all belief and did it. It’s got a computer science theme, which is why I’m posting it here.

Download “Correspondence, of a sort”

First, a disclaimer. I’ve never done this before, and it’s not a good crossword in its construction. Additionally, I might have made a mistake — the tool support for crossword construction on Linux sucks. So don’t get upset. If you have a problem, feel free to e-mail. I’ll post the answers in a new post next Thursday, January 25th. I’d love to email hidden; JavaScript is required.

I’ve thrown a few easy clues in there so people can get a foothold. (I recommend the northeast and southwest.) Frankly, I feel terrible about 53D. I’m sorry. If you e-mail me, I’ll give you the answer, but it’s easier if you just search the Internet, and we can both pretend like it never happened. 45D is weak, but on par with a crappy Friday clue.

That said: wow, is it hard to construct a crossword! First, you pick a theme and some theme clues. Then you fill in some solid squares so that you have a good mix of short and long words. (“Good” is relative. I have too many three letter words. I think going for two whole-board theme clues — 16A and 59A — on my first attempt was over-ambitious.) Then you fill in the boxes. (Ha!) It’s easy to get in a mental rut and see only way to fill in a section. I tend to go for the longer words first, since there’s less of an opportunity for fudging (stock symbols, etc.). The published puzzle is the second iteration — the first 15×15 didn’t pan out, though I came up with a delightfully (?) offensive clue thanks to Joel W., Sarah Z., and Yaniv Z. (no relation): “AIDS buddy”, 6. I’ll give the answer by e-mail to those who want it.

Writing in Computer Science

Frankly, how do you do it? In particular, how do you do it well? So much writing in CS is obscure and difficult, if not poorly edited, I’m not sure where to look.

What are some examples of good writing in computer science research? Functional pearls tend to be well written, but I’m more interested in research writing. I’m looking for papers that not only introduce a new idea, but do so clearly and effectively. Bonus points if it’s a good idea, but I’d just like to see something worth emulating.

Examples are clearly a starting point, but it seems to me that the only way to improve is practicing with aware, concerted effort.

JS2/ES4

After reading Brendan Eich’s annotated slides from @media Ajax. I was formerly of two minds: on the one hand, I’d started to feel like JavaScript was hopeless, BASIC with closures and a dynamic object system that precludes efficient compilation; on the other, I’d started to feel the JS FP elitisim that Brendan so acutely calls out. The structured type fixture example in Brendan’s talk is particularly convincing — I could use that, definitely.

Then again, I’m not sure I’ll ever get the chance. It’s interesting that PL — and many other fields — is often more defined by the tools it happens to use (or happened to use at some point in the past) rather than problems of interest. What circumstances determine the used features of a programming language? How can feature use be encouraged (or discouraged)?

C# GC Leaks

Reading this experience report from the DARPA challenge via Slashdot, I wondered: if event registration caused object retention, how can we deal with these memory issues in Flapjax?

Worrying about memory leaks in JavaScript is a losing battle — the browsers have different collectors. But given functional reactive programming in other settings (e.g., Java/C#), how can we solve this kind of problem? We looked at deletion briefly, but never had time to address the issue in detail. The complexity in our case is that the event registration encodes the entire application — how do you decide that a certain code path is dead? It may be helpful to view a functional-reactive program as a super-graph of data producing, splitting, merging, and consuming nodes; the application state is the subgraph induced by the active nodes reaching the consumers. Then there’s a certain static overhead for the program, plus the dynamic overhead of its active components.

Most of the Flapjax code I’ve written has been for the user interface, so binding and unbinding isn’t much of an issue: if the interface changes temporarily (e.g., tabs), the older behavior is usually recoverable and shouldn’t be collected. When working with more complex models with longer lived state, a deletion policy is more important. Shriram has been working on larger Flapjax applications with application logic as well as presentation — I wonder if he’s run into serious GC issues.

Lifting in Flapjax

In the Flapjax programming language, ‘lifting’ is the automatic conversion of operations on ordinary values into operations on time-varying values. Lifting gets its name from an explicit operation used with Flapjax-as-a-library; we use the transform method call or the lift_{b,e} functions. To better understand lifting, we’ll walk through a simple implementation of the Flapjax library.

I consider the (excellent) Flapjax tutorial prerequisite reading, so it will be hard to follow along if you’re not vaguely familiar with Flapjax.

The following code is all working JavaScript (in Firefox, at least), so feel free to follow along.

Continue reading

The price of cloneNode

So the function fix_dom_clone described in my last post isn’t exactly cheap. In fact, it’s far and away where my lens library is spending most of its time.

Function Calls Percentage of time
fix_dom_clone 4920 47.22%
deep_clone 6022 5.57%
get 3513 5.51%
dom_obj 20842 5.34%

I’ve implemented a few optimizations to reduce the number of times it needs to be called, but its recursion is brutal. The DOM treeWalker might be more efficient than what I have now. I don’t think it can matter much, because according to this website, IE and Safari don’t support it.

Attack of the cloneNodes

So the solution to the bug I had yesterday was fixed with a call to element::cloneNode to avoid aliasing. This introduced, to my great consternation, another bug — some DOM nodes were reverting to their default value. Had I written this down in my (as yet hypothetical) bug journal, it might have become more clear. Instead, I slaved away in Firebug for a few hours without results.

Thinking about it clearly, the problem had to be in cloneNode. I ended up having to write the following recursive fix-up function:

/**
 * List of all DOM event handler names.
 */
var dom_events = 
['onblur', 'onfocus', 'oncontextmenu', 'onload',
'onresize', 'onscroll', 'onunload', 'onclick',
'ondblclick', 'onmousedown', 'onmouseup', 'onmouseenter',
'onmouseleave', 'onmousemove', 'onmouseover',
'onmouseout', 'onchange', 'onreset', 'onselect',
'onsubmit', 'onkeydown', 'onkeyup', 'onkeypress',
'onabort', 'onerror']; // ondasher, onprancer, etc.

/**
 Fixes copy errors introduced by {@link element#cloneNode}, e.g. failure to copy classically-registered event handlers and the value property.

 @param {element} o The original DOM element
 @param {element} copy The result of o.cloneNode()
 @return {element} A modified copy with event handlers maintained
*/
function fix_dom_clone(o, copy) {
    if (!(dom_obj(o) && dom_obj(copy))) { return; }
    
    for (var i = 0;i < dom_events.length;i++) {
        var event = dom_events[i];
        if (event in o) { copy[event] = o[event]; }
    }
    if ('value' in o) { copy.value = o.value; }
    
    // recur
    var o_kids = o.childNodes;
    var c_kids = copy.childNodes;
    for (i = 0;i < o_kids.length;i++) {
        fix_dom_clone(o_kids[i], c_kids[i]);
    }
}

Oof. Unsurprisingly, there are a few efficiency issues.

My bug was weird and unexpected, and the W3C DOM level 2 spec doesn't allude to problems like this, but looking at a Mozilla bug report on the topic, it seems that the W3C DOM level 3 spec says that "[u]ser data associated to the imported node is not carried over". I guess if that's true for event handlers, it's also true for the value property. Oh well. I'd feel better about this irritating API "feature" if they said "associated with".