# Lambda the Ultimate

 Calculating Functional Programs: maximum segment sum started 8/11/2003; 3:42:54 AM - last post 8/17/2003; 6:46:31 PM
 Ehud Lamm - Calculating Functional Programs: maximum segment sum   8/11/2003; 3:42:54 AM (reads: 2856, responses: 15)
 Calculating Functional Programs: maximum segment sum Jeremy Gibbons. Calculating Functional Programs. In Proceedings of ISRG/SERG Research Colloquium, School of Computing and Mathematical Sciences, Oxford Brookes University, November 1997. A good way of developing a correct program is to calculate it from its specification. Functional programming languages are especially suitable for this, because their referential transparency greatly helps calculation. We discuss the ideas behind program calculation, and illustrate with an example (the maximum segment sum problem). We show that calculations are driven by promotion, and that promotion properties arise from universal properties of the data types involved. Everone should be familiar with Jon Bentley's Programming Pearl in which he discusses the design of a linear time algorithm for solving this problem (he calls it the maximun consecutive subsequence, if I am not mistaken. Try to guess why Gibbons calls it maximum segment sum...) A very short and elegant example. Posted to functional by Ehud Lamm on 8/11/03; 3:46:15 AM

 Ehud Lamm - Re: Calculating Functional Programs: maximum segment sum   8/11/2003; 6:38:00 AM (reads: 1101, responses: 0)
 Reference: Jon Bentley, Programming Pearls, column 7. The name Maximum Concecutive Subsequence comes from Udi Manber, Introduction to Algorithms, A creative approach, where it appears in section 5.8
 Pseudonym - Re: Calculating Functional Programs: maximum segment sum   8/11/2003; 11:19:22 PM (reads: 1018, responses: 4)
 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 Lamm - Re: Calculating Functional Programs: maximum segment sum   8/11/2003; 11:34:08 PM (reads: 1053, responses: 3)
 Marc Hamann - Re: Calculating Functional Programs: maximum segment sum   8/12/2003; 5:01:17 AM (reads: 1067, responses: 2)
 Please let's not start another argument about practical programmers. Please... Ehud, you make it sound like the last discussion was a flamewar to terrify the ages. ;-)
 Ehud Lamm - Re: Calculating Functional Programs: maximum segment sum   8/12/2003; 5:09:49 AM (reads: 1089, responses: 1)
 Well, my personal feeling is that too many discussions recently turned into flamefest and troll hunts. Maybe I am wrong, but it seems to me that what attracted most LtU readers was exactly that this sort of thing happened rarely, and that most of the time LtU disucssions were more technical and/or research oriented. Marc, I am not referring to you. Well, you shouldn't carry the burden alone, anyway... Ding, dong. The last sentence was a joke...
 Marc Hamann - Re: Calculating Functional Programs: maximum segment sum   8/12/2003; 6:05:18 AM (reads: 1134, responses: 0)
 too many discussions recently turned into flamefest and troll hunts 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 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... ;-)
 Kragen Sitaker - Re: Calculating Functional Programs: maximum segment sum   8/13/2003; 5:55:02 PM (reads: 949, responses: 2)
 The paper isn't exactly about deriving a program systematically from an abstract description; it's about deriving a faster program from a slower one, proving stepwise that the two programs perform the same function. This is a widely-known technique known as 'optimization' or 'refactoring'; this differs from the optimization your C compiler does only in that Jeremy directed the optimizations himself instead of having his compiler do a bunch of heuristics, and in that he's applying some pretty sophisticated meaning-preserving transformations, rather than the simple ones C compilers normally deal with.
 Ehud Lamm - Re: Calculating Functional Programs: maximum segment sum   8/14/2003; 12:52:33 AM (reads: 966, responses: 1)
 The paper isn't exactly about deriving a program systematically from an abstract description. Right. 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.
 Marc Hamann - Re: Calculating Functional Programs: maximum segment sum   8/14/2003; 6:45:35 AM (reads: 980, responses: 0)
 FYI, there is an updated version of this paper available here. Not sure how much it changes. (BTW note that, despite his provocative intro (under "Context"), I didn't start a thread... ;-) )
 Marc Hamann - Re: Calculating Functional Programs: maximum segment sum   8/14/2003; 6:51:38 AM (reads: 892, responses: 0)
 Oops, apparently that is an update of a different paper (similar topic, recycled name). My apologies.
 Kragen Sitaker - Re: Calculating Functional Programs: maximum segment sum   8/14/2003; 8:39:47 AM (reads: 909, responses: 0)
 First, we in fact derive a new and different algorithm. This is much more profound than what usually comes under the heading of optimization. ... 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. 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.
 Vesa Karvonen - Re: Calculating Functional Programs: maximum segment sum   8/14/2003; 11:05:20 AM (reads: 913, responses: 2)
 hmm... Some general purpose languages do make things such as algebraic optimizations easier, but even compilers for those languages rarely make such optimizations. I think the fundamental reason why compilers for general purpose languages do not perform optimizations that essentially derive new and different algorithms is because many of such optimizations are domain specific, and may not be as well studied as more general optimizations, and for most domain specific optimizations only a very small percentage of programs would benefit from the optimization. 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.
 Ehud Lamm - Re: Calculating Functional Programs: maximum segment sum   8/14/2003; 12:25:51 PM (reads: 945, responses: 1)
 but even compilers for those languages rarely make such optimizations.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
 Vesa Karvonen - Re: Calculating Functional Programs: maximum segment sum   8/14/2003; 2:19:31 PM (reads: 969, responses: 0)
 I wrote: 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.
 Pseudonym - Re: Calculating Functional Programs: maximum segment sum   8/17/2003; 6:46:31 PM (reads: 820, responses: 0)
 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. :-)