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 hear comments/tips/ideas.

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.


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