Kuro5hin.org: technology and culture, from the trenches
create account | help/FAQ | contact | links | search | IRC | site news
[ Everything | Diaries | Technology | Science | Culture | Politics | Media | News | Internet | Op-Ed | Fiction | Meta | MLP ]
We need your support: buy an ad | premium membership

[P]
Seven Lessons from the ICFP Programming Contest

By tmoertel in Op-Ed
Tue Jul 31, 2001 at 04:17:37 AM EST
Tags: Technology (all tags)
Technology

Yesterday, I submitted my entry to the Fourth ICFP Programming Contest. During the twenty-some hours that I hacked on my entry over the contest's three days, I made a lot of stupid mistakes and re-learned some important lessons that I thought I had learned a long time ago. To make sure that the lessons stay in my brain this time, I'm sharing them with you. I also did a few things right, and I might as well share those as well. If you think you might need to hack under time pressure some day -- or if you just want to laugh at my expense -- read on.


Background

The ICFP Programming Contest is an annual programming competition held before the International Conference on Functional Programming. The motivation for the contest is to spread the word about functional programming (FP).

The FP community thinks that functional programming is cool, but most other folks couldn't care less about FP or are ignorant of its existence altogether. So, how to convince the unbelievers? Like so:

  1. Hold an international programming contest,
  2. Invite anybody and everybody to enter, in teams of any size,
  3. Let them use their choice of language(s) and tools to hack for 72 hours on a Challenge Task,
    and
  4. Hope that when the smoke clears and all the entries are judged, the entrants who used FP in their solutions will rise to the top, demonstrating just how darn cool FP is.
Or something like that.

In any case, I entered last year as "Team Functional Beer," but, owing to a horrible scheduling mistake, didn't have the opportunity to compete. This year, I vowed to myself, I would put the contest dates on my calendar before promising the very same dates to help two people move into two separate homes on totally opposite sides of glorious Pittsburgh. (In last year's contest, I didn't do much hackin', but I sure did do a lot of packin', which as any person with a sore back will tell you, isn't nearly as fun.) Which brings us to the first lesson:

Lesson 1: Don't forget about the contest!
[Yes, I'm a moron.]

Okay, so I didn't forget that painful lesson this year. But, I did forget what I now refer to as Lesson 2:

Lesson 2: Invest more time in planning than just putting the dates on the calendar.
I should have, for instance, recruited friends to join me. I did try to impose upon one friend a few days before the contest, but he couldn't make it, and I just gave up on recruiting. That was a mistake. It turns out that I could have saved several hours of misspent contest time by having somebody double-check my work, especially to confirm that my understanding of the Challenge Task was correct. I didn't build a team, and I suffered for it.

About the Challenge Task

This first thing you need to know about the Challenge Task is that it is highly non-trivial. Past Tasks were playing board games (against other entries), optimizing NPC rules for an adventure game (equivalent to a problem in compiler theory), and ray-tracing scenes described in a purely-functional scene-description language. The tasks were designed to provide equal opportunity for both imperative and functional programmers, keeping the contest fair for folks in either camp.

This year's Task was no different. The challenge was to write an optimizer for a fictional markup language (SML/NG) that could convert one marked-up document (the input) into an equivalent yet smaller document (the output). Here, equivalent was defined to mean that when each document is rendered into a sequence of "decorated characters" according to a set of devious rules, the same sequence would result for each. In other words, you can change the original document all you want, but you cannot change its meaning. If you change the meaning, you're out of the competition.

In other words, correctness comes first. Then degree of optimization (how much the original document was reduced). Then speed (there is a time limit).

SML/NG Optimizer 3000, Iron Chef Style

That's what I named my entry, which reveals a lot about how darn goofy I am. Out of kindness, I won't share the README file, which is even goofier. It's for your own good. Trust me.

At the outset, I established my strategy:

  1. Always produce output, even if it's identical to the input (which is correct by definition, and prevents you from getting eliminated for correctness problems when your optimizer otherwise comes up with jack squat.)
  2. Prepare for catastrophic failure. I used a wrapper program to ensure that if my optimizer crashed, I could at least return the input document as output.
  3. Test, test, test! I didn't want to waste my time on bug hunts, so I adopted the policy of not building upon any module of code until I was confident of the code's correctness.
  4. Drink espresso. Unfair advantage? Perhaps. But when you're dealing with a vessel as leaky as my brain, you've got to fill it with something.
A deficiency in the above brings us to the next lesson:
Lesson 3: Try, as part of your Grand Master Strategy, O Sage-like CoderBoy, to glance at the Challenge Task before jumping behind the keyboard. (In other words, understand the problem before solving it.)
I kept a log of my activities during the contest, and here's the initial sequence of events:
  • Thu 11:00 EDT. Downloaded challenge task, sent it to the printer, and jumped into the shower. Exited shower, dressed. Read description. [Why I didn't shower and dress before the contest is a mystery that can only partially be explained by lack of caffeine.]
  • Thu 11:30 EDT. Started project with parser.
So, doing the math, it would seem that in the space of thirty scant minutes, I managed to get the Task, print it out, shower, dress, read the entire excruciatingly detailed specification -- all of seven 10-point typeset pages -- and decide, as the next course of action, that it would be logical to begin writing a parser Right Freakin' Now.

Sad but true. Later, on the final day of the contest, I ripped out the parser and replaced it with a new one. Had I studied the Task more closely I would have realized that the input documents would always be correct (meaning that I could eliminate error-detection) and a few other things that led to a much simpler design. The new parser ran about six times faster than the original and consumed less stack space. I wish I had written it in the first place.

This mistake cost me about two and a half hours, or 10% of my total coding time. How many more optimizations could I have worked into my program had that time not been wasted?

Lesson 4: Test early, test often.
This one I got right. Early on I decided to invest a substantial portion of my time on correctness. I wrote the optimizer in Haskell, so I benefited from Haskell's wicked-powerful type system, which catches a lot of problems all by itself, and then I used QuickCheck, an automatic testing tool, to further automate away the pain of testing. Here are a few examples from my log that show how a tool like QuickCheck can be your best friend in a tight coding corner:
  • Thu 17:13 EDT. QuickCheck is revealing that something is going wrong with either the Parser or my Show instances.
  • . . .
  • Thu 17:37 EDT. QuickCheck to the rescue! QuickCheck found a test case that falsified my RoundTrip property for Show->Parse->Show, and I was able to hand-feed that case to my parser to determine the error.
  • . . .
  • Fri 12:19 EDT. My naive optimizer is done. Not so fast, QuickCheck spotted a corner case that causes the optimizer to discard untagged text at the end of a document. Oops.
QuickCheck found these problems and more, many that I wouldn't have found without a massive investment in test cases, and it did so quickly and easily. From now on, I'm a QuickCheck man!

Two tales of measurement

I once read in an engineering text the following quotation (although I don't know who said it):

Lesson 5: "Measure. For what you cannot measure, you cannot control."
Throughout my coding adventure, I made two kinds of measurements that helped me invest my time where it made the most difference. This turned out have a big payoff, as I will share.

The first kind of measurement was profiling. The Glasgow Haskell Compiler comes with some great profiling tools to pinpoint where your program is spending its CPU cycles and allocating its memory. I didn't waste my time wondering where my cycles were going, I told the profiler to tell me, and it did. For example, I noticed that my program's run time was proportional to the square of the input document's size. Since some of the input files were going to be 5 MB, that was a serious problem.

How long did it take to find the problem's source? The log tells the tale:

  • Sat 22:53 EDT. Okay, I'm not sure if it's the parser. I do know that the overall running time is about O(N^2) with an input of size N. Time to use GHC's profiling options to pinpoint the trouble.
  • Sat 22:57 EDT. Profiling located the culprit: showsDoc!

        COST CENTRE          MODULE     %time %alloc
        
        showsDoc             Document    86.1   83.8
        dm'                  Meaning      5.2   10.6
        docParser            Parse        4.3    2.2
        mkTagParser          Parse        1.7    2.8
Note that it took just four minutes to turn on the profiling options and find the problem. That's what I call Return On Investment!

The second kind of measurement was output quality. I wanted to know how well the optimizer was performing. A quick Perl script told me what I wanted to know. At first, my optimizer reduced random documents by about 30%:

    AVERAGE REDUCTION = 30%
      10% ********
      20% *************************************
      30% ***********************************************************
      40% **********************************
      50% *******************************
      60% ********************
      70% **************************
      80% ***********
      90% ************
     100% **************************************************************

Then I made a change regarding whitespace handling in my optimizer that I thought would lead to smaller documents, but did it really? The measurements told me it did, and I kept the change:

    AVERAGE REDUCTION = 37%
      10%
      20% ***
      30% **
      40% *************
      50% ********************************************
      60% *********************************************
      70% ***********************
      80% ***********
      90% ********
     100% ***********************************************

I used this tool throughout development to tell me which optimizations were worth keeping, and which ought to be left behind. Without it, I would have been guessing and probably would have wasted a lot of time making worthless "improvements."

A brief word about time, and your brain

More than once, I caught myself staring at code or poking at the keyboard for what seemed hours, all without doing anything productive. It's not that I'm really that stupid; rather, my brain was fried. In one case, a problem that I had struggled with for an hour or so before going to bed turned out to be easy to solve in the morning. The problem didn't get simpler overnight, but it seemed that way because my morning brain was rested and ready to tackle hard problems. I wish I had gone to bed an hour earlier that night!

Lesson 6: Take breaks, your brain needs them.
I've learned this lesson before, but I forgot it for the contest. More often than not, I coded beyond the point of stupidity. I nearly drooled on the keyboard once!

And then, idiot that I am, I decided to pull an all-nighter before the contest deadline. That was particularly stupid because I accomplished only about fifteen minutes of real work as I "coded" away many hours that would better have been spent on sleep. I had asked my brain to perform in ways that it was unwilling, and it let me suffer for it.

I'm sure I'll forget this lesson just in time for next year's contest. It's so me.

The final lesson

The final lesson was another that I miraculously got right, but just barely. Foggy-eyed at 4 AM on Sunday morning, I almost snatched defeat from the jaws of victory. The final lesson:

Lesson 7: Have fun!
The ICFP Programming Contest is, most of all, a good way to have a bunch of fun. Early on Sunday morning, I almost forgot that important bit of truth, as I coded into near oblivion. But then I remembered why I write code in the first place -- because I love to code. The lightbulb went on: I stopped coding, went to bed, and dreamed happy coding dreams.

Heed my words, lest ye suffer!

Learn from my mistakes, remember the lessons that I forgot, and you too may dream happy coding dreams. Otherwise, you are doomed to learn the hard way: from your own mistakes.

Sponsors

Voxel dot net
o Managed Hosting
o VoxCAST Content Delivery
o Raw Infrastructure

Login

Poll
Do you like functional programming?
o What's functional programming? 38%
o No. 9%
o I use map in Perl sometimes. 8%
o Yes. 30%
o foldr ! 5%
o I named my firstborn "Continuation Passing Style". 7%

Votes: 92
Results | Other Polls

Related Links
o Fourth ICFP Programming Contest
o Internatio nal Conference on Functional Programming
o playing board games
o optimizing NPC rules
o ray-tracin g
o Task
o Haskell
o QuickCheck
o Glasgow Haskell Compiler
o Also by tmoertel


Display: Sort:
Seven Lessons from the ICFP Programming Contest | 31 comments (31 topical, editorial, 0 hidden)
At 2:18 AM... (2.66 / 3) (#1)
by kevsan on Tue Jul 31, 2001 at 04:22:58 AM EST

...this is an auto +1 SP vote. It looks to be very well-written, and there are obviously a great deal of people that enjoyed it, since it currently presides on the front page. However, as a non-programming-oriented geek, I didn't get it. :)

-K
You said it all (3.50 / 2) (#2)
by davidmb on Tue Jul 31, 2001 at 05:13:16 AM EST

Which must be the reason why your article was posted to the front page quite quickly, but with only one comment attached to it!

A good article, it makes me want to enter programming competitions, which believe me would be a bad idea...
־‮־
Haa! I could not submit my entry because (3.37 / 8) (#3)
by exa on Tue Jul 31, 2001 at 05:32:24 AM EST

Well I followed most of the good practice of testing and everything but couldn't get to finish the program in time because the extra-mighty MDL search based optimizer I wrote didn't work in the last hours it was finished.

Even funnier that I had to do an all-nighter even though I coded everything by the book. Of course, that's kind of tolerable since it was the first time I ever wrote a program in Haskell. I must admit that this is one hell of a language and it allowed me to do any fantasy I liked to.

In the last hour, since my brain was totally cooked I couldn't figure out how to read an integer for the "time limit" from command line args. I was browsing like mad through the reports, docs and tutorials but found nothing! Gosh, it took me more than half an hour to do that, then I tried my obviously superior optimizer on real data and saw that it resulted in sheer stupidity. Hmmm, yes you can get really sophisticated and end up not submitting anything. That felt so bitter.

At any rate, I learnt a lot of Haskell. I used a monadic combinatorial parser and a lot of monadic programming elsewhere (I/O, filtering, tc.) and it did look that equational reasoning could be made to work well. The type system is a bit difficult to get used to and the language has its oddities in places, but otherwise it's a superb functional pl. And BTW, lazy evaluation rocks.

I wrote the optimizer in a GOFAI-combined-with-machine-learning style, with a best first search on DL (description length), and the design was a bit weird:

* parser gets from syntax a doctree
* doctree -> semantics -> rle (run length encoding of the semantic string)
* rle -> doctree (I drop the original document altogether)
* search based optimizer on the 'wide' tree.

It looked like I could fix the optimizer but it was 3 minutes past the deadline and the submission page didn't accept entries. I thought, hmm, what will I do with this code now? It looks pretty cool but what use would it have even if I fixed it. :)

You know, I sure hope that damn optimizer had worked properly when it was finished. Only if I knew Haskell like I knew C++, I would've wreaked havoc on lucky hackers who submitted their code, and for those who didn't work alone, grrrrr. :)

Thanks,
__
exa a.k.a Eray Ozkural
There is no perfect circle.

Submit it anyway (3.00 / 1) (#9)
by tmoertel on Tue Jul 31, 2001 at 11:29:21 AM EST

exa wrote:
It looked like I could fix the optimizer but it was 3 minutes past the deadline and the submission page didn't accept entries. I thought, hmm, what will I do with this code now? It looks pretty cool but what use would it have even if I fixed it. :)
Finish your optimizer and submit it via email. From the contest news page:
  • 2001-07-29 15:40 UTC
    To the people who missed the deadline and are still trying to submit: if you send us your entries, and if there are not too many of them, we will evaluate them with the others, but out-of-competition (i.e. you cannot win a prize, even if you're the best). Contact us if this is your case. In the Web industry, time-to-market is everything.
You wrote:
... the design was a bit weird:
  • parser gets from syntax a doctree
  • doctree -> semantics -> rle (run length encoding of the semantic string)
  • rle -> doctree (I drop the original document altogether)
  • search based optimizer on the 'wide' tree.
Weird? That's my design! ;-)

I'm not kidding. Here's my main, where naiveOptimizer is the doctree -> semantics -> doctree transformation:

   main :: IO ()
   main =
       do [timeLimit, resultsFile] <- getArgs
          input <- readFile resultsFile
          let doc = case parseS input of
                    Left  e -> error (show e)
                    Right d -> d
          let doc' = naiveOptimizer doc
          writeDocResults resultsFile doc'
          -- further optimizations ...

I didn't do the RLE part, however. Instead, I relied on value sharing to give me a poor-man's RLE for free. And my optimizer is dumber than a bag of hammers -- but it works, so I'll take it. ;-)

At any rate, I learnt a lot of Haskell. I used a monadic combinatorial parser and a lot of monadic programming elsewhere (I/O, filtering, tc.) and it did look that equational reasoning could be made to work well. The type system is a bit difficult to get used to and the language has its oddities in places, but otherwise it's a superb functional pl. And BTW, lazy evaluation rocks.
Yeah, Haskell is sweet and lazy evaluation does indeed rock. However, if you're not careful, the laziness can bite you in the form of unintentional space consumption (sometimes called a "space leak", although nothing actually leaks -- it's really just a ton of unevaluated thunks that eventually will be evaluated, but perhaps not before you exhaust stack or heap space!). One misapplication of foldl when foldr (or foldl') would do can cause a whole heap of nastiness to unfold.

Out of curiosity, have you tried your optimizer on large inputs, say, 1 MB or more? That was a real eye-opener for me.

Cheers,
Tom

--
My blog | LectroTest

[ Disagree? Reply. ]


[ Parent ]
First the Casino series, now this... (3.00 / 4) (#4)
by Locked on Tue Jul 31, 2001 at 06:15:59 AM EST

Real life tales of trials and tribulations - love 'em! More please. In particular, I'd like to hear more entertaining and informative programming/technical anecdotes.

Spec bugs (4.66 / 3) (#5)
by slaytanic killer on Tue Jul 31, 2001 at 06:49:11 AM EST

What a true programming competition. The news page lists five new versions of the spec over two days after the start. Like real life. Though to be fair, the real bugs were fixed about 6 hours after the beginning...

+1, FP! (4.44 / 9) (#6)
by DesiredUsername on Tue Jul 31, 2001 at 08:14:36 AM EST

Oh wait, it already is. Excellent article.

Favorite line is Lesson 5: "Measure. For what you cannot measure, you cannot control."

I've never heard it put this way but I always do it nonetheless. I can't tell you how many times I have to explain to people (even fellow programmers) get a baseline. Baselines serve as a take-off point for future comparisons, especially where no metric for measurement exists. For instance, I'm supposed to be testing some email migration software right now. Install email client A and client B and then the migration software. See if it can migrate. Others who have done this testing in the past have reported things like "couldn't migrate from Notes to Exchange" (or whatever). My first question is always "can you read your Notes and Exchange mail with the client itself"? "Ummm...I dunno, I didn't check that." Gah! That's your baseline! Check it first!

Play 囲碁
baseline == control (4.00 / 2) (#10)
by kubalaa on Tue Jul 31, 2001 at 01:47:00 PM EST

What you call a baseline, scientists call a control. But same difference; results are meaningless without one. :)

[ Parent ]
Excellent advice (4.40 / 5) (#7)
by baptiste on Tue Jul 31, 2001 at 09:23:01 AM EST

I myself have been in similar situations. I really like the idea of writting a small perl program to monitor optimizations. Very slick.

I think all coding texts should have this classic advice - when you're cross eyed and droolin on the keyboard - take a major break. I've lost count of tiny problems that cost me hours and hours that I ended up fixing in a few minutes after an extended break.

One other tidbit - if you don't use CVS for serious coding - start. I've found my CVS repository to be an EXCELLENT tool for tracking changes I've made. I won't submit code to the repository unless it runs. But the code gets committed before I start any serious testing. This way I can track what changes were made and if I broke something, its fairly easy to find. I also would recommend Chora from Horde.org which is a slick CVS web front end that takes the older CVSWeb variants to a somewhat higher level - with color coded code viewers, ability to annotate and show when a given line was last changed, etc.
--
Top Substitutions For 'Under God' In The Pledge Of Allegiance

Time allocation (4.50 / 6) (#8)
by Manax on Tue Jul 31, 2001 at 10:00:50 AM EST

I too put some work into the task, and ended up not submitting anything... Here are some of my mystakes:

1. Spend more time on the tools you plan to use before hand.

I planned to use lex/yacc/C. I have only written one program with lex/yacc and that was many years ago, so I spent a few hours playing with lex/yacc (or really flex/bison) before the contest start. Not enough time. I spent far too long working on the parser, which I should have spent on figuring out the optomization.

2. Spend more time on thinking about the problem.

I assumed I would spend the majority of my time on the optomizing section of my code. This was correct, but I didn't spend enough time preparing for that code. I didn't realize where all the gotchas would be in the optomizer.

3. Think about having a teammate.

One person would have helped a lot, and it would have allowed me to complete the task on time and under budget. :) And not get stuck on solvable problems.

There are really three orthogonal problems, within the optomizer. The first is the <B|I|U|EM|S|PL> (attribute) problem, the second is the <r|g|b|c|m|y|k|w> (color) problem, and the third (isomorphic to the color problem) is the <[0-9]> (font size) problem.

I assumed (though didn't entirely finish) that the optomization for the attribute portion would be straight forward, which I believe it is. A handful of rules would create optimal output.

The place I got stuck was with the color/size problems. I knew some things about it, but didn't figure it out until last night... I discussed the problem with an associate and after an hour or so we came up with what I believe is an optimal solution and in O(n), though I'd like to spend more time and prove it. I can post more details if anyone cares...

Babble, babble... ;)


"Why should I be content to simply live in this world, when I, as a human being, can CREATE it!?"

FP, bah! (4.00 / 4) (#11)
by der on Tue Jul 31, 2001 at 07:46:07 PM EST

Someone needs to win the ICFP Programming Contest with straight C and just traditional UNIX tools.

That'd piss 'em off. :)



well, yeah (5.00 / 2) (#13)
by evanbd on Wed Aug 01, 2001 at 03:42:45 PM EST

but the point is, no one has. And every year, they get multiple C solutions, which don't do as well. It seems they have a point. Of course, since I don't know what FP is, I can't tell you what their point is, but hey. I think the challenge of "Our method is best, come beat us at a task with yours and prove us wrong" becomes fairly compelling when no one can...

[ Parent ]
True, their idea is a good one (4.00 / 1) (#16)
by der on Thu Aug 02, 2001 at 12:42:09 AM EST

... but obviously the problems are tailored to the functional style of programming.

Someone could just as easily run a contest rigged so that people coding language Foo++/3*pi on FreeOpenNetGNULindows would win hands down.

Not really anything wrong with that though, it shows in what problem area FP has an advantage, but anyone claiming that Foo style of programming is the ultimate super-mega-task-doer is either a liar or an idiot. As said by many, no paradigm is a panacea.



[ Parent ]
Moreover... (4.00 / 1) (#17)
by Macrobat on Thu Aug 02, 2001 at 09:13:59 AM EST

The ostensible criteria of the contest are: correctness, optimization, and speed. But implicit in a three-day time limit is--over everything--ease of implementation. So there's no news here. C takes some time to do right. If I wanted to create a contest where C was the optimal solution, I'd give contestants a month.

"Hardly used" will not fetch a better price for your brain.
[ Parent ]

Optimum solution (3.00 / 3) (#12)
by tbadiuk on Wed Aug 01, 2001 at 02:51:05 AM EST

Just took a quick look at the contest details...

Wouldn't the optimum solution simply "render" the input document to a data structure in memory and then just parse the created data structure outputing the optimal solution? Memory usage wouldn't be an issue given that a small % of the input document is the actual text, most of it is just context changing tags...

I know the above is a very simplistic explenation (ie- I've left out the details to what the rendered data structure looks like, etc), but I think I can pretty much see a quick and easy solution that can be implemented in any langauge quickly... Mind you, I'm probably missing something since I only spent 10 min going over the contest details. To bad I didn't know about the contest sooner...

Ted

not quite so simple... (4.00 / 1) (#14)
by sesquiped on Wed Aug 01, 2001 at 06:56:44 PM EST

Unfortunately for you, though fortunately for the contest creators, simply "parse[ing] the created data structure outputting the optimal solution" isn't as easy as it sounds, and it certainly isn't linear.

As a simple example, what tags should be inserted between text with the attributes {bold, underline x 2} and text with {italic, emphasis, underline x 1}? Well, you could close one of the open underline tags, close the bold, and add an emphasis tag then an italic, or you could add the italic and emphasis in the other order, or add a plain then an italic, emphasis, underline, or one of the other 5 permutations of that last option....

As you can see, there's some number of choices at each junction, which (if you look at everything) leads to some kind of exhaustive search, which will have exponential performance. Since inputs can be up to 5 megs, that makes the maximum number of junctions something like 500,000. Even if you only had two choices per junction (there's usually many more), exhaustive search is impractical. In fact, the number of choices per junction can be infinite if you don't do some simple pre-pruning of your choices.

And as for memory usage, much more memory will be spent on the working data structures of your algorithm than the text, so that's not really an issue.

[ Parent ]
Lists... (3.50 / 2) (#15)
by slaytanic killer on Wed Aug 01, 2001 at 07:43:45 PM EST

I haven't read the spec since seeing it on /., but isn't it a trivial problem, optimizing a List according to its transform rules? I mean "trivial" in the sense that there should be libraries to help this.

I don't think this can be done during run-time since... way too many possibilities. But I wonder if one can be made which operates on small snatches of semi-random legal documents and thinks for a day, then tells the programmer what optimizations it made, so she can hardcode it into the final optimizer which would have fast run-time properties. While it runs, the programmer debug code and find her own optimizations in addition to the one the computer will find.

Eh, maybe nontrival, but I'll post it because I find this approach interesting if unfeasible.

[ Parent ]
Functional Programming In Banking (3.50 / 2) (#18)
by the trinidad kid on Thu Aug 02, 2001 at 09:34:40 AM EST

An interesting tale:
The motivation for the contest is to spread the word about functional programming (FP).
Well it raised my interest and I scooted around reading about it - on the Haskell site I found a introductory text on functional programming.

One thing right up close really jumped out at me:
What is functional programming?

C, Java, Pascal, Ada, and so on, are all imperative languages. They are "imperative" in the sense that they consist of a sequence of commands, which are executed strictly one after the other. Haskell is a functional language. A functional program is a single expression, which is executed by evaluating the expression. Anyone who has used a spreadsheet has experience of functional programming. In a spreadsheet, one specifies the value of each cell in terms of the values of other cells. The focus is on what is to be computed, not how it should be computed.
The point about spreadsheets as functional programming jumped out at me.

I work in a bank (previously I was the Chief Technical Architect, currently I am the business architect). We offer a complex product, for instance you can have (under the aegis of a plan):
  • an unsecured personal loan a, li>
  • a mortgage
  • a credit card
  • a current account (checking account)</</li>
  • a savings account
The way the product works is that every night your interest is calculated. Prior to the calculation all the debt and credit products are offset against one another in quite a complex way and you either pay or are paid the relevant interest on the remaining balance (read our blurb here - needs Flash).

There are 2 major algorithms associated with this product type:
  • the interest calculation algorithm which calculated the daily interest
  • the offer engine that decides (based upon your personal details and circumstances) which products or combinations of products we will offer you (including things like overdraft limits, total risk exposure, etc, etc)
The point of this comment is both of these algorithms required considerable time, expense and skilled labour to implement and maintain - and for both of them some of the (non-technical) business designers said:
"Why does this take such a long time to develop? I can do this on a spreadsheet in an afternoon!"
(Made up quote). Now I buried these comments in my brain, filed under "interesting conundrums that life chucks at us", but on seeing the FAQ they leapt back at me.

Maybe the problem is that we are implementing functional algorithms in imperative languages?

Yes and no (4.33 / 3) (#19)
by Paul Johnson on Thu Aug 02, 2001 at 09:49:58 AM EST

Functional languages are pretty neat, and they do read a lot like a spreadsheet would if you took out all the rows and columns and used names instead.

Where things get interesting is in doing loops. Spreadsheets do loops by just copying the same calculation across the page, which is crude (to put it mildly). Functional languages do it by recursion. And its at this point that peoples brains start to rebel.

Sure, we've all done recursion at University, but for many programmers Programming 101 was the first and last time the wrote a real recursive routine. So if you put them in front of a Haskell environment they would have to spend weeks or months reprogramming their brains to think recursively.

I was there for the big change from structured design to OO. There were rougly 3 groups of people: those who saw it instantly, those who could think in objects after practicing for a few weeks, and those who would never get it.

The same thing is going to happen if we switch to functional programming, except that the proportion of the code monkeys who just get it is going to be miniscule. (BTW, people who read Slashdot and Kuro5hin are not code monkeys).

Paul.
You are lost in a twisty maze of little standards, all different.
[ Parent ]

Tools for the job (4.00 / 2) (#20)
by the trinidad kid on Thu Aug 02, 2001 at 10:05:42 AM EST

Algorithms like interest calculations are intrinsically recursive - the output from yesterday's interest calculation is the input into today's, and with the ability to post backwards and forwards in time (ie correcting a cheque amount that has been miskeyed happens today but pertains for the purpose of interest and charges from last week) you need it.

Offer calculations are (ideally) sort of incremental:
  • I want an 80k mortgage and a 3k loan and a 500 overdraft and 3,500 limit on my credit card
  • based on my financial position you'll only give me 2,000 on my credit card, what if I drop the mortgage to 78k?
  • etc, etc
The things I need to know are:
  • are there specific sorts of alogorithms that I should consider exporting from an imperative language like Java to a functional one (one of the ones I am thinking of is over 30k lines long)
  • is "easy to do in a spreadsheet, hard in cobol" a good rule of thumb?
  • if I were to consider using a functional language what criteria should I use?
(I did a PdD in molecular physics in the late 1980s and have no exposure to formal computer science at all - self-taught all the way, with all the lacunae of the autodidact that that implies.)

[ Parent ]
Its not easy (5.00 / 1) (#21)
by Paul Johnson on Thu Aug 02, 2001 at 11:26:18 AM EST

Its not that easy. I don't want to discourage you, but once you have learned a functional language (Haskell is the obvious one: its where all the action is these days) you have only started on the problems of using it in real life. Most of these problems stem from isolation: you will incur significant costs just to bring Haskell software into production, and you are the only person who is going to recover those costs. If you were going to bring a couple of hundred coders with you then it would be different.

Tool support is patchy. There is HUGS for interactive prototyping and GHC for production work. And thats about it.

Interfacing to other languages is non-trivial. Systems like Green Card (never actually tried it) will help, but my experience in other languages is that these things always seem to involve a lot of tweaking at a low level to get them to work. Creating a Haskell interface to existing software takes a lot of grunt work.

Who will maintain this software when you have moved on? Your employer should be very worried about the maintenance costs of your code if they have to have someone spend two weeks learning Haskell (at a minimum) before they can touch your code.

I understand and applaud your desire to improve the efficiency of software engineering for your employer, but you need to take a long-term view. Suppose that you take 30k lines and turn it into 300 (quite possible). Now what? Is your employer going to roll out Haskell for all coding tasks? What is the likely investment required for this exercise? How long will it take to recover? What are the risks to current and future programmes? These are the kinds of questions that your management should ask if you talk to them.

To answer your original questions, Haskell is best at algorithmic stuff, less good for GUI. Apart from the IO monad stuff (which is really mind-bending to someone from an imperative universe) the GUI design tools just aren't there for Haskell.

Easy in spreadsheet, hard in COBOL? I'm not sure.

Criteria for a functional language: use Haskell.

Paul.
You are lost in a twisty maze of little standards, all different.
[ Parent ]

I am the business (5.00 / 1) (#23)
by the trinidad kid on Thu Aug 02, 2001 at 05:05:23 PM EST

In this context I am the business/management. We are a big organisation (around 200 IT staff at my bank out of 1,500 staff - with hundreds more in the group). We still employ about several hundred mainframe assembler programmers. The main data centre is the size of a soccer pitch with 3 3090s, a Unix corner that you could build a house in, rows of AS/400s, literally hundreds of Intel servers. So if it were the right decision 4 or 6 expert staff would not be a problem.

Some of our decisioning software (ie the 30k lines of java) are at the upper limits of these -ilities:
  • maintainability
  • changeability
  • respondability
  • testability
  • provability
Contraction of this software to 300 lines (as you suggest might be achieved) would make possible a whole new degree of decisioning - an expansion of what can be done. I have seen "utopian" proposals that might require a decisioning engine of 300k lines in the current world which might become practical under that degree of compression.

Clearly with implementing stuff in a functional language I would have reservations about a different set of -ilities:
  • enterprisability
  • scalability
  • deployability
  • utility and utilities
Some of these -ilities might be assuaged by a functional language other than Haskell: like Erlang which would appear to be an enterprise language.

One of our strategic aims is to change the internal development culture to move away from a `financial services' mentality towards a process engineering mentality (the output of the IT department is software that support processes where profitability, usability and so on are funtional behaviours that the developers have shared responsibility for) so moving to a `real-time' process managing language makes a weird sort of sense.

This discussion is somewhat academic until I can establish better criteria for identifying algorithms that might benefit from a migration from an imperative to a functional language.

[ Parent ]
Pardon me, my assumptions were showing (5.00 / 1) (#26)
by Paul Johnson on Fri Aug 03, 2001 at 06:06:00 AM EST

Sorry about that. I've spent several years trying to get a large company to try Eiffel (which, BTW, might also be worth you having a look at), and I imagined you were in a similar situation.

What I said in my previous post still holds: just about anything involving complicated algorithms is going to be suitable for functional languages. That 30KSLOC of Java sounds ideal, and would make a good pilot project: if you can afford it I'd suggest taking a couple of your brightest coders and asking them to see what they can do. But don't rely on getting anything useful. Like I said, most of your headaches are going to come from integrating functional and conventional code and training your programmers into the new way of thinking. Its all very well recoding that 30KSLOK into a few hundred lines, but if you can't integrate it into your software or have J Random Programmer maintain it after the authors have gone then you haven't actually achieved anything from a business point of view.

I guess what I'm saying is: don't think of the functional code in isolation. Suppose your pilot project is successful: how are you going to roll this out to the rest of your organisation? This will be a major strategic move. Even if FP is as good as it claims, it might still be the wrong move. Think about the investment required and impact on your cash flow during the transition period.

Sorry if I'm teaching you to suck eggs here, but one thing I did learn during my years of Eiffel evangelism is that the technology benefits are actually one of the least important aspects in this kind of situation.

Paul.
You are lost in a twisty maze of little standards, all different.
[ Parent ]

A Fellow Heretic (none / 0) (#27)
by the trinidad kid on Fri Aug 03, 2001 at 06:20:20 AM EST

the technology benefits are actually one of the least important aspects
I agree completely.

This discussion has opened up the possibilities of doing business in a different/better/and more importantly more profitable way - there may or may not be technical barriers to doing it, and they may or may not be surmountable/avoidable.

We are already a heterogeneous environment so the issue of roll-out doesn't really apply - it doesn't make sense to try and migrate the organisation to a whole new paradigm when the existing stuff we do works fairly well - with the (partial) exception of the business critical can do it in a spreadsheet, can't do it in cobol algorithms.

[ Parent ]
Tail-recursive... (4.50 / 2) (#22)
by beergut on Thu Aug 02, 2001 at 01:25:02 PM EST

The calculations that you've suggested seem to me to be tail-recursive. I.e., they can be calculated recursively, but the output of one calculation becoming the input for the same calculation at a different step, is tail-recursive.

It is mathematically provable that tail-recursion can be refactored into iteration (and some imperative language compilers can do that.) Recursion, in an implementation sense, is dangerous in that it is resource-intensive (think: stack.) Iteration is much less so, and wins in other ways (reduced call overhead, reduced memory consumption, better optimization, simpler to factor when the mind is not trained to recursion.)

But, iterative solutions are harder to factor in a functional language than in an imperative language.

i don't see any nanorobots or jet engines or laser holography or orbiting death satellites.
i just see some orangutan throwing code-feces at a computer screen.

-- indubitable
[ Parent ]

Are you sure you don't mean the opposite? (5.00 / 3) (#24)
by tmoertel on Thu Aug 02, 2001 at 09:44:15 PM EST

beergut wrote:
But, iterative solutions are harder to factor in a functional language than in an imperative language.
Actually, the opposite is true. Functional languages are usually easier to factor because they encourage programming that is free of side effects, leaving the compiler free to use equational reasoning to reshuffle the implementation details in order to eliminate recursive calls. Moreover, functional languages encourage programming on a higher level in which recursion itself is often factored out into terms that the compilers can optimize into thin air. Witness the common factorial function (in Haskell):

    fac 0 = 1
    fac n = n * (fac (n-1))

That version isn't tail recursive, and so it is often manually factored like so:

    fac2 n = fac2' 1 n

    fac2' acc 0 = acc
    fac2' acc n = fac (acc*n) (n-1)

This new version's tail call is so easy to eliminate that even a rudimentary optimizer can do away with it.

But somebody familiar with functional programming would probably use a higher-order function like foldl to factor out recursion altogether:

    fac3 0 = 1
    fac3 n = foldl (*) 1 [1 .. n]

This version not only saves typing and improves the S/N ratio of the code but also is easy for the compiler to optimize into a very efficient form in which the tail call is eliminated.

--
My blog | LectroTest

[ Disagree? Reply. ]


[ Parent ]
FP in a financial setting? Absolutely! (4.50 / 2) (#25)
by tmoertel on Thu Aug 02, 2001 at 10:32:47 PM EST

Here are a couple of papers that you will want to read: For an idea of what is possible, check out Peyton-Jones, Eber, and Seward's "Composing contracts: an adventure in financial engineering", a paper from last year's ICFP. It's a real trip and shows the expressive power of functional languages in a financial setting. And, if you haven't done so already, read John Hughe's classic, "Why Functional Programming Matters."

Now, regarding your business, I don't know the particulars of your situation, but I can say that most situations could benefit from a little functional programming -- and more than a few could benefit from a whole heap of functional programming. But do keep in mind that FP is a tool. Although it is an exceptionally powerful tool, it may not be right for every job. It's up to you to figure out where FP is the right tool.

Why not pick a problem for which you think FP is well suited, hand select some smart programmers who you trust are willing to invest the time to learn FP in earnest, and give them the problem to solve as a way of introducing FP to your company? Get expert help if you need it, but do the job right. FP is sufficiently different from other forms of programming that you must give your team the time they need to learn, make mistakes, and start thinking in functional terms. Once they become ``functionalized,'' they will start seeing applications for FP all over the place. They'll have a new tool in their belts, and they will start seeing places to use it. That's when your return on investment kicks in.

--
My blog | LectroTest

[ Disagree? Reply. ]


[ Parent ]
Experiment paper on SLOC reduction (4.00 / 1) (#28)
by Paul Johnson on Fri Aug 03, 2001 at 08:29:56 AM EST

Go for it and good luck. Let us know how you get on.

BTW the estimate of 100x reduction in line count is from memory. Somewhere I came across a paper on a comparative programming experiment where the problem was the detection of conflicts between aircraft trajectories. Other languages took hundreds or thousands of lines of code, whilst the Haskell solution was (IIRC) around 100 lines of which thirty-something were actually executable.

According to the paper the judges looked at this, complimented the author on writing a formal specification of the problem, and asked if they could please see his solution now. They couldn't believe that this "formal spec" was actually executable.

Unfortunately I can't find the paper again.

Paul.
You are lost in a twisty maze of little standards, all different.

My experience (3.00 / 1) (#29)
by Garc on Fri Aug 03, 2001 at 10:49:30 AM EST

I entered with 2 other friends as Team Imperative (we wrote in C :). When they released the task description we all decided that it was easier than last year, and that we'd try it on our own. Which meant that we'd each write our own code, but help each other with debugging, testing, benchmarking, and suggestions. Then we would all submit our entries under the team name.

There were only so many types of optimizations that you could do.

  • (color|size) nesting
  • PL insertion
  • whitespace
  • redundancy elimination
  • I think I'm missing some...

My strategy:

  1. get input
  2. convert to internal data structure that represents output in decorated strings (This gave me whitespace & redundancy optimizations for free :)
  3. regenerate SNL/MJ from internal representation
  4. Give smaller of (input, newly generated SNL)
  5. If I ran out of time, give input

Thursday say the completion of the parser... or mostly, I still had some bugs in it. Friday after work, right around alcoholic beverage #4, I got a bug that made no sense. 4 hours later (after first 6 pack was gone, and I had purchased 6-pack #2) I found the bug. I had done realloc (text, size + 1000); instead of text = realloc (text, size + 1000); Next time I'll drink slower.

Saturday I worked on optimizations. I ended up implementing a best guess algorithm for where to put tags. Its not perfect though, and the most optimal solutions will probably only be found by using a search tree of some sort. I got all of the optimizations workin except PL, and for all my (simple) test cases I generated the optimal output. I think in some cases I would guess the wrong optimization to use, and not generate optimal output.

Did I mention that my implementation was slow? For testing and quick writing purposes, I wrote it using an O(NxN) implementation. I figured that I'd go back and rewrite it using a single pass, O(N) algorithm. Unfortunately I never had the time for that.

Sunday morning, I woke up, and wrote the PL stuff. One of my teamates had given me a partially correct algorithm to work from, so it wasn't too hard. I tested a bunch and submitted my code half an hour early. Then, filed with caffine, liquor and adrenaline, I lifted weights, then slept.

How did my teamates do you ask? The first one attempted the same sort of thing I did, but got disheartened early on b/c of the slowness of his code. Mine was slow too, but I think I cared less :) He still submitted but I don't even know if he finished the nesting completely. He was invaliable to me and the third teamate by testing and making suggestions. Our third teamate wrote something very interesting. It basically did the whole thing in one pass. But by whole thing I mean whitespace, and redundancy elimination. It was blazingly fast though. It would do a 5 meg file in under 10 seconds.

Next year I'll spend about double my time planning, and try to arrange to be in the same physical location as my teamates. We did amazlingly well only using AIM, but I think it would be nicer if we were all there.

The contest was a lot of fun. I suggest that you try it next year, even if you don't consider yourself a great programmer.

garc
--
Tomorrow is going to be wonderful because tonight I do not understand anything. -- Niels Bohr

There's a Lesson 8 in there somewhere! (4.50 / 2) (#30)
by tmoertel on Fri Aug 03, 2001 at 12:26:02 PM EST

Garc wrote:
Friday after work, right around alcoholic beverage #4, I got a bug that made no sense . . . Next time I'll drink slower.
Right there! That's Lesson 8: If you're drinking while coding, by all means, do it slowly!
 
:)

--
My blog | LectroTest

[ Disagree? Reply. ]


[ Parent ]
UPDATE: SOURCE CODE AND FULL LOG AVAILABLE (4.00 / 1) (#31)
by tmoertel on Fri Aug 03, 2001 at 03:25:23 PM EST

I now have my Functional Beer Team Page online. From the team page you can download the source code for my entry and also get a look at my complete minute-by-minute log, which has all the nitty-gritty details about what I tried, where I spent my time, and how things worked out. (Yes, the goofy README is on the team page, too.)

[If the server seems a little slow, give it some time. It's presently being pounded by all the ICFP requests, not to mention having to fend off a constant stream Code Red Worm attacks.]

Cheers,
Tom

--
My blog | LectroTest

[ Disagree? Reply. ]


Seven Lessons from the ICFP Programming Contest | 31 comments (31 topical, 0 editorial, 0 hidden)
Display: Sort:

kuro5hin.org

[XML]
All trademarks and copyrights on this page are owned by their respective companies. The Rest 2000 - Present Kuro5hin.org Inc.
See our legalese page for copyright policies. Please also read our Privacy Policy.
Kuro5hin.org is powered by Free Software, including Apache, Perl, and Linux, The Scoop Engine that runs this site is freely available, under the terms of the GPL.
Need some help? Email help@kuro5hin.org.
My heart's the long stairs.

Powered by Scoop create account | help/FAQ | mission | links | search | IRC | YOU choose the stories!