Ezra's Research

So I got sucked into editing the wikipedia page for anamorphisms, which was a mess: it didn't define the concept itself, except to say that it's a generalization of unfolds, and allude to category theory; it had duplicated code, but treated the duplicates as different, and was generally jargon-heavy and not very helpful.

But while fixing it, I got stuck on a puzzle: what exactly is an anamorphism?

Is an anamorphism a higher-order unfold operator? Or is it any function which is defined by partially applying such an operator? Or a function that is defined using a certain syntactic pattern, corresponding to an unfold operator? Or any function at all that could be so defined?

In the almighty "Programming with Bananas, Lenses, Envelopes and Barbed Wire," they seem to use "anamorphism" to refer to a function defined by a certain syntactic pattern. It's a question of interpretation, but they don't seem to define it as a higher-order function, exactly: the text posits some pre-existing operators and then the code sample, which takes just one argument (the "seed" value to unfold from), uses those posited operators.

It seems natural to me to use "anamorphism" to refer to the (unique) unfold operator for a given ADT, and likewise for "catamorphism" and fold. We still have the plural "anamorphisms," since we have many types with such operators. And, I'm not sure to what extent a function is intrinsically "an anamorphism" in Meijer, et al.'s sense. Of course, it is intrinsic whether a function can or cannot be defined that way; but when we start using the whole bag of bananas, lens, envelopes and barbed wire, I think we get multiple ways to define many functions, so it's less intrinsic.

I'd like to hear what others think: What are anamorphisms? Please comment!

7 March, 5:26 AM | Permalink | Comments (0)

I've been working on trying to extend a result from my thesis, having to do with strong normalization of a certain higher-order rewrite system, but its proof is very complicated, so I've been working on simplifying it.

Along the way I found a paper by Mitsuhiro Okada from 1989 which proves strong normalization for the combination of STLC with any first-order term-rewriting system. But this paper is hard to read because it has strange notations and concepts and says things like, "If a part s[*/x1, ..., */xn, */y] of t belongs to the cap then the part s[*/x1, ..., */xn, */y] also belongs to the cap." Say what?

I knew I could prove the same result using the Tait-Girard method (the same basic approach Okada takes) in a more straightforward way—at least to me. So I did, and here it is for future reference: "Simply adding lambda won't make your rewrites diverge."

1 March, 2:54 AM | Permalink | Comments (0)

Economist Paul Krugman, as portrayed in this week's New Yorker profile, reminds me a lot of a computer scientist. MacFarquhar explains one of Krugman's economic ideas, namely that locations specialize economically—cars in Detroit and chips in Silicon Valley—and reports this interesting reaction to it:

'I explained this basic idea to a non-economist friend, who replied in some dismay, "Isn't that pretty obvious?" And of course it is.' Yet, because it had not been well modelled, the idea had been disregarded by economists for years.
(MacFarquhar, "The Deflationist." The New Yorker, March 1, 2010.)

Much of what we academics do (in computer science and, apparently, in economics) is to take an intuitive idea and make it precise—modelling it, if you will. Those who simply think intuitively may have already absorbed the idea and treat it as old hat—but the model, by making it more precise, illuminates it further and more securely and can lead to new inspirations.

MacFarquhar adds another interesting idea here:

His friend Craig Murphy, a political scientist at Wellesley, had a collection of antique maps of Africa. ... Sixteenth-century maps of Africa were misleading in all kinds of ways, but they contained quite a bit of information about the continent's interior—the River Niger, Timbuktu. Two centuries later, mapmaking had become much more accurat, but the interior of Africa had become a black. As standards for what counted as a mappable fact rose, knowledge that didn't meet those standards—secondhand travellers' reports, guess hazarded without compasses or sextants—was discarded and lost. Eventually, the higher standards paid off—by the nineteenth century the maps were filled in again—but for a while the sharpening of technique caused loss as well as gain.

I'm intrigued by this idea that higher standards of precision can cause us to 'forget' disciplinary knowledge, material that no longer meets the standards. Of course, the higher standards are all about eliminating 'knowledge' that isn't actually correct. But some of it, perhaps, is correct, and anyway there's an outer shape to the knowledge that is useful: after all, there was still a River Niger even if the mapmakers didn't know exactly where it flowed.

This might happen in computer science, too. I think of Don Knuth's penchant for reading antique sources describing algorithms from pre-modern times.

There might be inspiration in the older, less-precise knowledge of one's field: it might be a source of ideas to be modelled.

27 February, 4:02 AM | Permalink | Comments (0)

So what I do lately is I work for a company in Cambridge, MA that has a big XQuery engine for searching "semi-structured" databases. That is, we use language technology to allow people to write nifty searches.

I had some other interesting job offers, but I took this one because (a) it was in the Boston area, which is where I wanted to be at the time and (b) I wanted to get behind one central product and contribute some programming-language knowledge to it. I was surprised to discover a company that would let me do both.

As part of what how we're improving the product just now, we're building a parallelizing compiler for relational algebra—roughly the sort of stuff that titilates me as a langauge engineer, and tangentially (at least) related to some of my thesis work.

Since it's a company trying to compete against others, I probably won't be blogging much about what I'm doing at work, but I still hope to keep this blog active and post researchy notes here.

16 February, 12:09 AM | Permalink | Comments (0)

Proposal: As an academic reviewer, you should always vote to publish a paper, without reading it, even if it is a tedious waste of time.

The time-saving benefit of this strategy is subtle to grasp but significant. You see, only the reviewers of a paper "must" read it, while everyone else will discard it if it's boring. By voting to publish, you waste no one else's time—but the time you save is your own. If every reviewer did this, the time saved would allow us all to do far more research!

7 January, 3:53 AM | Permalink | Comments (1)

Tim Bray is spreading more misinformation about tail recursion. He describes it this way:

It looks like a subroutine call, but in the case where it occurs as the last thing in the routine, it magically, silently, and automatically gets turned into, now how did I put it? “A highly controlled and structured GOTO.”

A tail-call is a subroutine call. The efficient implementation does not magically transformed into something else; if it doesn't create a stack frame on such a call, it's because one simply isn't relevant.

The essential observation behind the efficient-tail-call implementation (not "optimization"—more on which in a moment) is as follows: For most programming languages, a stack frame is needed not for a subroutine call but only for an argument evaluation, that is, an evaluation whose result is temporary and needs further processing. Calls in the middle of a procedure are "argument" evaluations, because their results need further processing. It's really the temporary, non-final natural of the result that forces us to do the book-keeping that remembers where to come back to.

Another confusion is between semantics and cost model:

Call me old-fashioned, but it just seems wrong when the semantics of two identical function invocations vary wildly as a function of whether there’s an executable statement between the invocation and the function exit.

The semantics of the call doesn't change; the result and the side-effects are the same (that's what's usually meant by "semantics" anyway). The cost, on the other hand, might be quite different depending on whether a stack frame is needed.

Unfortunately, efficient tail recursion has often been described as a transparent "optimization," so that it might or might not be efficient and the programmer can't tell in advance.

Efficient tail calls (or space-consuming ones) really should be part of the official "cost model" of the language, something that goes along with the semantics, as a peer to the semantics, in fact. The cost model tells you how expensive you can expect things to be, but should be a little less binding than the semantics, since language implementors should have some freedom to do additional optimizations.

The idea that stack frames should correspond directly to the call structure is just odd. Maybe we want to know the call structure at runtime; in that case, we should capture that as debugging information, or as a reflection feature of the runtime system, but not as a core language design. Let the language implementation use the stack as efficiently as possible!

To summarize:

• "Tail-call optimization" is a terrible misnomer.
• The programmer should have assurance as to whether tail-calls have a cost.
• Most languages have no reason to use up space on every function call; only calls whose result will be fed to another expression need to use space.

3 November, 5:29 PM | Permalink | Comments (13)