The burden of FP

A rude awakening…

When the fire alarm sounded at about 2:00 AM, I didn’t want to think about electrical engineering, hydrology, or locksmithing. I wanted a quick fix.

The tiniest of pinhole leaks in the attic water heater drain line had released a fine mist, some of which escaped the footprint of the catch pan. Condensing on the attic floor, it accumulated to the point of dripping through the crack between boards, trickling down to the upstairs hall ceiling and through the hole where the wiring ran from the smoke detecter to the alarm system. Smoke detectors don’t like water.

(Of course, that little exercise in house debugging, with no advance warning and severe time pressure, it totally unlike anything experienced by a professional software developer. πŸ˜‰ ) And that (believe it or not) brings me to Project Euler and the title of this post. I had heard of Project Euler before, but this post enticed me to visit the site. One look and I was hooked.

The site offers a series of little mathematical problems of gradually increasing difficulty. The result of each task is a number, which you submit for verification that you completed the task. The point, of course, is to think beyond the obvious brute force solution to produce one which continues to be feasible as the task scales.

All in all, the site is a nice collection of progressively larger lab rats. I know that some folks don’t care for such problems, but the very first one rewarded my attention.

Problem 1

My paraphrase: “Sum the positive integers below 1000 that are multiples of 3 or 5.” Simple (to the point of triviality) for any practicing programmer. So there must be more to it than the obvious (and very procedural) Scala implementation…

  def sumi(n: Int) = {
    var s = 0
    for (i <- 1 until n) {
      if (i % 3 == 0 || i % 5 == 0)
        s += i
    }
    s
  }

…and there is. (The ‘i‘ on the end of sumi stands for “imperative”.)

Mathematics and programming

Student programmers are often guided to look for general solutions, especially by their more mathematically-inclined teachers. But generalizing requires thinking about what kinds of generality may be needed, thinking about what is likely to change. OOP’s polymorphism and inheritance encourage us to think about kinds of generality that are harder to express in procedural programming. FP allows easy exploration of even more kinds of change. But having more options means having to make more choices. I found it interesting to take a hard look at the above code to see how many issues were hard-wired into its structure. FP makes it easier to break those issues apart, but at the cost of thinking more abstractly (math-speak for “more generally”).

Highlighting the issues

At the risk of consuming a fair bit of virtual ink, I want to identify some aspects of the task, highlighting the parts of the code that deal with each aspect.

  1. Sum the positive integers below 1000 that are multiples of 3 or 5.
      def sumi(n: Int) = {
        var s = 0
        for (i <- 1 until n) {
          if (i % 3 == 0 || i % 5 == 0)
            s += i
        }
        s
      }
    

    I’ve already cheated a little; the parameter n allows us to replace the 1000 with a different limit.

  2. Add all the positive integers below 1000 that are multiples of 3 or 5.
      def sumi(n: Int) = {
        var s = 0
        for (i <- 1 until n) {
          if (i % 3 == 0 || i % 5 == 0)
            s += i
        }
        s
      }
    

    The generator 1 until n produces exactly the values one up to (but not including) n.

  3. Sum the positive integers below 1000 that are multiples of 3 or 5.
      def sumi(n: Int) = {
        var s = 0
        for (i <- 1 until n) {
          if (i % 3 == 0 || i % 5 == 0)
            s += i
        }
        s
      }
    

    Confession time: obviously I made the subconscious assumption that the 1000 was more likely to change than the 3 or 5.

  4. Sum the positive integers below 1000 that are multiples of 3 or 5.
      def sumi(n: Int) = {
        var s = 0
        for (i <- 1 until n) {
          if (i % 3 == 0 || i % 5 == 0)
            s += i
        }
        s
      }
    

    I unconsciously represented the concept of “being a multiple of” with “has a remainder of zero when divided by”. It makes me ponder how often our programs completely replace a problem domain concept with an implementation choice without even noticing that we’ve done so.

  5. Sum the positive integers below 1000 that are multiples of 3 or 5.
      def sumi(n: Int) = {
        var s = 0
        for (i <- 1 until n) {
          if (i % 3 == 0 || i % 5 == 0)
            s += i
        }
        s
      }
    

    The (single!) idea of producing a sum has become multiple steps: initializing and updating a variable, and retrieving its value as the answer.

Functions and patterns

While I wholeheartedly appreciate the contributions of the pattern movement to OO, the approach is evolutionary, not revolutionary. A few decades ago even the humble for-loop had to be recognized as expressing a standard solution to a recurring need. In the FP world, higher-order functions often provide the same sort of “glue” expressed in some patterns. For example pipes-and-filters are function composition in OOP clothing.

The little sumi method above is certainly a function from its argument n to the corresponding sum. But the “function-like” quality stops at the outer most curly braces, because sumi is almost entirely conceived in terms of imperative commands acting on mutable state (i.e. side effects). That has some subtle consequences when compared with an approach that tries to “be functional” all the way down, in the same way that OO changed our perspective when we began to design in terms of objects all the way down.

I believe that most of us would recognize sumi as belonging to this general design:

  • generate a set of values,
  • test those values to select the desired subset, and
  • perform a specified action on that subset,

but those aspects of the design are not cleanly, independently represented in the code. Functional programming offers us a way to do that.

The next post will offer some examples as justification of that claim. Meanwhile, I need to catch up on the sleep interrupted by the fire alarm!

The life of a programmer

Before I end this post, let me close the fire-alarm connection. It’s easy to slip into fire-fighting (or fire-alarm-fighting) mode in day-to-day programming. And when doing so, it’s easy to become impatient with anything that doesn’t lead in a straight line to working code. I recall a collegue’s remark in a discussion about resolving a problem with a production system. Different participants offered a series of suggestions, all beginning with, “Well, you could…”, until he finally blurted out, “I don’t need more options; I need fewer options!”

Sometimes fixing the immediate problem quickly is the right thing to do, in the near term. I unplugged the shorted smoke detector, put a piece of plastic in place to collect the mist and deposit it into the catch pan, and went back to bed. But the second step is to go beyond the symptoms to the root cause and fix that. The plumber has replaced the failed pipe, and the technician with a replacement smoke detector is on the way.

But the third step is to prevent the problem from happening in the first place. Or, as the agile guys say, “Deliver tested working code quickly. But leave yourself set up properly to do the same thing on the next cycle!”

Maybe plastic pipe isn’t the best choice for difficult-to-reach applications, especially when elevated temperatures are involved.

Advertisements
Trackbacks are closed, but you can post a comment.

Comments

  • Matt Stine  On 2008-04-06 at 19:51

    Joel,

    I’m reading this just as I’m getting ready to hit the sack before flying out of Boston’s airport in less than eight hours. I immediately found myself trying to hit Project Euler. Fortunately, it seems to be down. Otherwise I am quite sure that I would have found myself awake at Midnight and having to get out of the bed at 3 for the short drive to drop off the rental car and check in for my flight.

    You have an uncanny way of getting me to want to go off and write functional programs every time I talk to you or read your writing. STOP THAT! I need all the sleep I can get right now. πŸ™‚

    At any rate, I thoroughly enjoyed your breakdown of the code you wrote. It is quite amazing to see all of the unconscious assumptions we make when writing seemingly trivial code.

    Cheers!

    Matt

  • Russ  On 2008-04-07 at 07:36

    Hi Joel,

    Interesting stuff! I like the analysis of the imperative solution – I think it’s a valuable exercise to examine the silent assumptions we make when coding. It’s discarding some of those assumptions that make learning other paradigms (e.g. FP) so challenging and rewarding.

    Good luck with Project Euler, I’ve got a post up about problem 3 if you’re interested. I’m glad my first Euler post inspired you to go take a look; my aim with each post is to fire up some sort of enthusiasm in someone πŸ˜‰

  • joelneely  On 2008-04-09 at 20:18

    @Matt, For my sake, I hope Project Euler stays up. You’ll have to fend for yourself! πŸ˜‰

  • joelneely  On 2008-04-09 at 20:20

    @Russ, Thanks for keeping your series going! I’m going to be interested to see how the Scala solutions compare/contrast with your solutions in C#, Haskell, and F#.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: