Lambda the Ultimate

The name Maximum Concecutive Subsequence comes from Udi Manber, Introduction to Algorithms, A creative approach, where it appears in section 5.8

On the other hand...

In Engineering, mathematics is most often used as a means of design analysis. In contrast, many Computer Scientists talk about systematically deriving programs from specifications. Program derivation is analogous to deriving a bridge from a description of the river and the expected traffic. Refining a formal specification would be like refining a blueprint until it turned into a house. Neither is realistic; the creative steps in design are absolutely essential. This is as true in programming as it is in any other area of Engineering.
    -- David Lorge Parnas, Teaching Programming as Engineering

Now admittedly David Parnas is occasionally given over to hyperbole, but still, it's something to think about. "A very short and elegant example" doesn't necessarily help a programmer with a practical problem.

Ehud, you make it sound like the last discussion was a flamewar to terrify the ages. ;-)

Marc, I am not referring to you. Well, you shouldn't carry the burden alone, anyway...

Ding, dong. The last sentence was a joke...

I guess after years of BBS conference groups, USENET and Slashdot, I haven't seen anything I would qualify as a real flamefest here, I think, ever. Probably best to have a low tolerence threshold though, to keep it that way. ;-)

it seems to me that what attracted most LtU readers was <snip> that most of the time LtU disucssions were more technical and/or research oriented

An interesting thing about this: I lurked here, on and off, almost since LtU began, and I observed that it was usually the least technical, most partisan topics that got all the discussion volume. (e.g. dynamic vs static)

I think this is a universal trait of this kind of forum: people are most confident to speak out on topics where they can less easily be squashed by someone more expert.

Having said that, the technical content here is pretty high, so people who aren't also interested in the theory probably go away pretty quickly.

Ding, dong. The last sentence was a joke...

I'm so excited! You acquired the bell... ;-)

This is a widely-known technique known as 'optimization'

Looks like it, right? But this is the wrong perspective for two reasons.

First, we in fact derive a new and different algorithm. This is much more profound than what usually comes under the heading of optimization. We should ask ourselves why this is possible, and what lessons does it imply.

Second, but related, is that there's a fundamental reason why C compilers (for example) don't perfom this sort of transformation. The fact that these transformations are really meaning-preserving comes from the semantics of the underlying language (i.e., purity, r.t).

Thus, if indeed this sort of technique can improve efficiency by scales that are considered to be in the realm of algorithm design (i.e, changing the order of magnitude, big-oh speaking), we should factor in this fact when we assess the value of the relevant language features.

...it's about deriving a faster program from a slower one, proving stepwise that the two programs perform the same function.

This statement is, of course, correct. That's the whole point, really.

The real question is how to make these techniques as powerful and as widely applicable as possible.

Not sure how much it changes.

(BTW note that, despite his provocative intro (under "Context"), I didn't start a thread... ;-) )

My apologies.

I agree --- I don't mean to imply that this paper is somehow trivial. I just wanted to point out that it's not without precedent. For example, SQL optimizers regularly perform optimizations that change your query's execution time by orders of magnitude (big-O doesn't apply here because SQL optimizers usually know the size of their input, though not of their intermediate results, before they start planning) and even a simple constant subexpression being hoisted out of a loop can change your algorithm from O(N^2) to O(N). (Consider def percentages(lst): [item/sum(lst) for item in lst], for example.)

Determining that a subexpression is constant, of course, is often very difficult in C, and utterly trivial in Haskell. On the other hand, determining that an algorithm is O(N) is usually trivial in C, and often very difficult in Haskell.

Here is a link to a talk by Oege De Moor that basically talks about domain specific optimizations in IP and might help others to see the point I'm getting at.

http://www.comlab.ox.ac.uk/oucl/work/oege.demoor/papers/ip.pdf.gz

But recall this quote from Wadler:

Whereas some declerative programmers only pay lip service to equational reasoning, users of functional languages exploit them every time they run a compiler, whether they notice it or not. -- Philip Wadler, How to declare an imperative

Some general purpose languages do make things such as algebraic optimizations easier, but even compilers for those languages rarely make such optimizations.

With the second "such" I was really referring to somewhat more complex optimizations (not just simple reductions).

For example, compilers that would transform many kinds of (non-tail) recursion into efficient iteration (not simple CPS). Quite often (always?) a recursive algorithm is shorter and easier to understand than an iterative algorithm (which uses explicit accumulators). If the compiler were smart enough to transform most typical forms of (non-tail) recursion into efficient (constant space) iteration (when possible), it could make the programmer's job much easier. I find it unpleasing that it is usually necessary to write code in tail recursive form so that the compiler can then trivially compile it to efficient iteration.

Please let's not start another argument about practical programmers. Please...

This wasn't my intention. I actually don't believe there is such a thing as a "practical programmer". (Does this make some programmers "impractical"?) "Practical" is a property of the problem before the programmer, not the programmer themselves. "Practical" isn't a property of the tools that a programmer uses, though with respect to a specific problem, "effective" and "ineffective" seem perfectly appropriate labels.

But I digress. I don't want to restart this argument either. :-)