The difference between imperative and functional programming

Have you ever had this frustrating experience?  You need to drive somewhere that you’ve not been before, so you look that place up on the web.  You find its site, and start looking through the pages for the address and postcode.  Instead, you find this kind of thing:

To get to us from the south/east (for example, if driving from London), the easiest way is to get onto the A4136 heading southwest, then turn right onto Morse Road which takes you straight to Ruardean.  Our house is on the right as you approach from this direction, almost immediately after the 30-mile-per-hour speed-limit sign that marks the boundary of the village.

You didn’t want instructions on how to find the place.  You just wanted to know what the address is: you know how to reach a place with a known address, because you have Google Maps and a satellite navigation system and a helpful wife who will shout “Left!  Left!  No, LEFT!  Why didn’t you turn LEFT?” when required.

The postcode GL17 9XF tells you what the destination is; the series of instructions on the unhelpful web-site tell you how to reach the destination.

And this seems to be the core of the difference between imperative programming (which is what most of us do most of the time) and functional programming (which is what exotic academic types like to do in their ivory towers, never actually getting anything done but writing a lot of papers).

Except, wait, didn’t we just agree that functional addresses are better than imperative ones?  They give you more freedom in figuring out how to implement them, and they are not sensitive to global state such as whether you happen to be coming from London in the first place.  What if you’re coming from Cardiff?  If you follow the imperative address (and you are of a literal turn of mind) you’ll drive to London, then follow the directions quoted above(*), which is hardly optimal.

So could it be that functional programming is better than imperative programming after all?

What does a functional program look like?  At the risk of perpetuating a cliché, consider the toy problem of factorials.  (I nearly said “the problem of calculating factorials, but even saying it that way presupposes an imperative approach to solving the problem.)  A factorial is a produce of a specified integer and all smaller positive integers, so that factorial(5) is 1x2x3x4x5 = 120.  And the obvious way to write a function for that is of course:

def factorial(x)
res = 1
while (x > 1)
res = res*x
x = x-1
end
res
end

This is nice, simple code, and hard to get wrong.  (Although as a matter of full disclosure, I guess I should admit that I did get it wrong when I typed it in just now for this article: I forgot the x = x – 1 and got into an infinite loop.  Oops.)

That’s an imperative program, which tells you how to calculate a factorial.  But a functional program just says what a factorial is — the number you first thought of times the factorial of the number one less than that.  (I’m using Ruby as a sort of executable pseudocode for both versions of the factorial function so that language-wars  don’t obscure the conceptual point.)

def factorial(x)
if x < 2
1
else
x*factorial(x-1)
end
end

And this version also works just fine.  Of course I cheated a bit, by not saying up front how this version avoids getting into an infinite loop of its own.  The answer is that the factorial of 1 is just 1 — there’s no need to go figure out the factorial of one-less-than-one.

Which version is better?  That’s a matter of judgement and, yes, opinion.  Leaving aside all performance considerations (which we probably don’t understand as well as we think we do anyway), and thinking only about comprehensibility, which is clearest?  I really couldn’t say.

But of course this function is so short and simple anyway that both versions are bound to be easy to read and understand.  The real question is: which approach scales better to realistic-sized problems? And the answer to that seems to depend as much on the temperament of the individual as it does on the intrinsic merits of one approach of the other.

Like a lot of programmers, I was raised imperative but have been repeatedly drawn to functional — often seeing the appeal, but never yet able to make the leap into actually doing anything in a functional style beyond artificial exercises.  It’s time that changed: I am going to make a serious attempt at Lisp, the canonical functional language, and I’m going to blog it as I go.

Let me be clear: I am not setting myself up to teach anyone anything about this subject, since I know close to nothing about it myself.  I’m just hoping my notes might be useful to fellow travellers, if only so that they can avoid making the same dumb mistakes as I do.  And those of you who are further along the road than I am, please do shout when I wander off the path!

We start next week!

(*) A favourite joke of mine (not original to me, but I don’t remember where it’s from).  The university’s Health and Safety officer is checking that the faculty know what to do in the event of a fire.  He asks an engineer, “What would you do if you were locked in the laboratory and a fire broke out?”  The engineer thinks for a moment and says “The centrifuge in the lab is pretty heavy: I’d use that to smash the door down and make my escape”.  “Very good”, says the H&S guy, and turns to a mathematician.  “And what would you do”, he asks, “if you were up on the roof when a fire broke out?”  Quick as a flash, she replies “I’d lock myself in the engineering lab, thus reducing the problem to one that has already been solved.”

Thank you, thank you, I’m here all week.  Don’t forget to tip your waitress.

*** Special bonus EoPS extract ***

As I’ve continued my re-reading of The Elements of Programming Style, I ran across this old favourite from page 70, which I thought you might enjoy:

“Finally, the two inner loops (on K2) are handled differently even though they perform similar functions.  This tips us off that one of them is incorrect.  (As a matter of fact both are, but the details are not worth pursuing.)”

This, by the way, in the section illustrating the rule “Don’t patch bad code — rewrite it.

About these ads

26 responses to “The difference between imperative and functional programming

  1. The school where I received my undergraduate CS degree a decade ago has since started teaching their introductory CS course in Scheme. I think the CS department takes the opinion that if you can’t handle thinking in a functional language, you shouldn’t be taking CS, and you’d better find that out as soon as possible.

    Great blog by the way; picked it up with a link to the “whatever happened to programming” post and I’m definitely enjoying it. Look forward to your Lisp experiences.

  2. Thanks, KR. I guess I sort of agree with your school’s approach — it reminds me of Joel Spolsky’s two-point-test for potential hires, which is: can they cope with recursion and pointers?

    I nearly didn’t post this article because I am kind of ashamed of never having got properly to grips with functional programming after all this time. But I figured that if I made a public commitment to remedy that deficiency, I’d be more likely to stick to it :-) And hopefully, some of this blog’s readers will be inspired to do the same.

    At the very least, coming to terms with Lisp should make me a better Ruby programmer.

  3. I have been fighting myself over imperative and functional programming for a long time. But still looking at the two code snippets you have shown; I still find the first one more natural. Recursion in particular is like a paranormal entity to me :)

  4. Lisp is terribly unpopular. Perhaps you should try Phosphorous – a Popular Lisp:

    http://jfm3.org/phosphorous.pdf

  5. I applaud your project. It’s something I’ve wanted to do for a long time, so I’ll follow your efforts with great interest. I’ve done many toy projects in Scheme but have never done “realistic” projects. I’ve also played around with Ruby and Clojure.

    One reason I am particularly interested in learning functional languages is because I think they provide the best way forward for handling concurrent applications with thread safety and performance. As processors add more cores, concurrency gets more important. It’s nearly impossible to write code that is both safe and scalable with OO languages when the number of threads gets large.

    Good luck!

  6. Xiong Chiamiov

    Most of the functional weenies I know swear by Haskell.

  7. Yeah, I know that Haskell is the new kid on the block; but Lisp is canonical, and I want to be in a position where no-one can tell me “You say you’ve learned functional but you don’t know Lisp!” OCaml is another trendy alternative which I’d like to learn one day, but Lisp is just The Functional Language, isn’t it?

    (Also, I am interested in the ability to get Lisp programs to read and write other Lisp programs due to their lack of syntax.)

  8. Go with Lisp. It’s plasticity actually makes it easier to write algorithms that take advanage of multiple processors. The Thinking Machine, a SIMD machine with 8,192 processors, was programmed in an extension to Lisp that borrowed ideas from APL and the hardware interprocessor architecture.

  9. I applaud your project too!
    I have also learn Ocaml for the same reason.
    I have always programmed in an imperative style and I was just curious about another way to “think”.
    So, I have chosen two application target(s):
    * Brute force, validation of Fermat’s theorem (bignum…)
    * network application(multithread), port scanning, which looks for kademlia nodes.

    I have wrote these application twice.. the first time while learning, the second time when I was used to functional style.
    It has been a funny experience, after a few weeks thinking: “This guys are simply crazy, spending their time in useless jokes” … I have started writing program in different ways.
    I have also noted I was able to produce code at impressive (high) speed.

    My last note:
    I have acquired a “trasversal” way to look at algorithm’s implementation and this is useful when coming back to imperative programming but I have also understood that functional programming is (for me) not the natural way to solve problems.
    Why?
    Time ago I have had few months without programming but after coming back to the keyboard I was able to program in few seconds(imperative).
    Now, thinking about functional style programming, I’m sure I need a full day in order to get back to functional programming.
    Yes this coud be related I was raised in imperative paradigm, but for me functional still sounds a strange way to program.(quick nice and elegant)

  10. If it boils down to teaching a course, I would pick Haskell as the language for the course.

    However if you want to stay with lisp, that’s allright to.

    However the comment “You say you’ve learned functional but you don’t know Lisp!” is something most people that did do their homework on FP will plainly laugh at you and tell you you’re not serious in your attempt at FP.

    By the way Erlang is a cool functional language too if you want to work with distributed systems.

  11. Xiong Chiamiov

    We used Scheme for my programming languages course, and it worked really well for making a lispy language, because it has native parsers.

    Making a non-lispy language is actually much more difficult.

  12. Andrew Raybould

    Funny you should raise the credibility issue; there was a time I used Common Lisp extensively, and now I feel I should dip back in to find out what modern functional languages are like. I’m thinking of Haskell, OCaml or Erlang, with a bias towards the last because of its concurrency support and extensive ‘real-world’ use.

    On the other hand, I think Lisp will give you a sound basis in functional style. Just be aware that most, if not all, Lisp dialects support an imperative programming style as well as functional. I’m no fundamentalist in this regard, but as you want to experience the latter, watch out that you don’t slip into a Basic style of programming!

  13. Hmmph, well, er, hmmm. Having spent the last two summers wrestling with XSL and overflowing stacks and for-next loops that take 12 lines of code I’m still unconvinced of the practical applications of functional languages over imperative ones.

    On the other hand, I’m no genius, but at least I’m open-minded enough to keep a lookout for applications that could benefit from a functional approach. No luck there yet, however.

    Having an average brain is, I think, what makes me an OK programmer – my code is simple because my cave-man mind needs to be able to understand it.

    My problem is not with functional languages per-se, but the difficulty I constantly run into when it takes me several hours to implement what seems to be to be a simple enhancement to an existing functional program.

    Of course it could just be that my brain doesn’t, uh, function properly.

    At any rate, I have one specific thought to share; how many large applications (with a user interface, please) can we name that are written in any functional language? Isn’t this an indication of something? I’m not talking about a web-app here but a real end-user application such as iTunes or Word. How about any games written in functional languages? If there are no (commercial) examples then there must be a reason for this, right? Right?

    Probably I’m just missing something really obvious here…

  14. Chris,

    These questions bother me, too.

    But, at least, I don’t think we should use the extreme horribleness of XSLT as a reason to write off the entire functional paradigm. It is truly difficult to invent a more ugly, inconvenient and error-prone syntax for anything, and that surely conceals whatever intrinsic beauty the underlying XSLT model might have. (Why the world ever switched from the elegant Lisp-like syntax of DSSSL to something as foul as XSLT has always astounded me: it seems to be simply a manifestation of the Angle Brackets Good fever that took over the world a decade ago.)

  15. Mark Arvieux

    Now it’s XML:

    <catalog>
    <cd>
    <title>Empire Burlesque</title>
    <artist>Bob Dylan</artist>
    <country>USA</country>
    <company>Columbia</company>
    <price>10.90</price>
    <year>1985</year>
    </cd>
    </catalog>

    Now it’s Lisp:

    '(catalog
    '(cd
    '(title '(Empire Burlesque))
    '(artist '(Bob Dylan))
    '(country USA)
    '(company Columbia)
    '(price 10.90)
    '(year 1985)
    )
    )

    This is easy!

  16. Mark, you don’t need all those quote marks.

    ‘(catalog (cd (title (Empire Burlesque)) (artist (Bob Dylan)) (country (USA)) … ))

    If you want to execute code in there, use ` instead: this was the sort of thing backquote was *made* for.

    (I wrote a Lisp->XML translator *long* ago, in Lisp macros of course. It makes writing XML not quite so much like stabbing your eyes out with a toasting fork.)

    Oh, btw, DSSSL wasn’t just ‘Lisp-like syntax': it *was* Lisp, or rather a dialect of Scheme. I wish the world never switched, but, hey, it could be worse. We could be using XExpr to write our shell scripts. (The standard for it — a dead draft — is notable for being the only standard I’ve ever seen to include syntax errors in virtually every one of its examples. If a language is too ugly for even its inventors to get right, it’s a bad language.)

  17. Pingback: What is “simplicity” in programming? « The Reinvigorated Programmer

  18. Hey, great blog, just wanted to make a few points:

    – Lisp itself doesn’t necessarily imply functional programming. Common Lisp users especially dislike the label. The dialect Scheme tends to be very functional, so if you decide to go Lispy for your functional fix I would suggest you take a look at that one.

    An especially helpful set of books for this are The Little Schemer and The Seasoned Schemer. They start with simple exercises to get you used to thinking recursively, but by the end you will have had a lovely brainmelt ^_^

    A good, easy-to-setup Scheme implementation is PLT Scheme, soon renamed PLT Racket.

    – Regarding Chris’ post with the questions that bothered you, two points. First, I’m curious which language left him with stack overflows (all functional languages implement tail call elimination, and it’s one of Scheme’s only features).

    And second, I’m wary of the “how many large applications have been built in X?” argument as a basis for discrediting X. There was a time when the best medical treatment available was a good bleeding; to look at something new and note that it hasn’t immediately overtaken the establishment, and inferring that it’s lacking is shortsighted. This field is very new, especially the point at which we citizens can have computers of our own.

    Further, it depends on what you mean by large software. Darcs, XMonad, and the Scheme used in Naughty Dog’s video games are contenders, I would argue ^_^

  19. Thanks, Paul, good points. I did intend to get The Little Schemer, but that approach was overtaken by events, which I’ll write about in a forthcoming post. It looks like I will be using PLT Scheme/Racket, though.

    I think that, for a paradigm that’s been around since 1958, “How many large applications have been built using it?” is a fair question to ask. For all I know, the answer is “lots”; the point is that I don’t know, and if functional advocates out there can point me at some examples, I’ll be the wiser for it.

  20. A late comment – it strikes me that a lot of the problem with functional programming is similar to your comment in the article about closures – at times it seems that essentially simple concepts are made harder to understand by choice of terminology.

    (I can understand why – it’s an area that is still closer to the mathematical roots of computer science, so the terminology tends to be more academic and less colloquial).

  21. Because all those advantages are also disadvantages.

    Stateless programs; No side effects

    Real-world programs are all about side effects and mutation. When the user presses a button it’s because they want something to happen. When they type in something, they want that state to replace whatever state used to be there. When Jane Smith in accounting gets married and changes her name to Jane Jones, the database backing the business process that prints her paycheque had better be all about handling that sort of mutation. When you fire the machine gun at the alien, most people do not mentally model that as the construction of a new alien with fewer hit points; they model that as a mutation of an existing alien’s properties.

    When the programming language concepts fundamentally work against the domain being modelled, it’s hard to justify using that language.

    Concurrency; Plays extremely nice with the rising multi-core technology

    The problem is just pushed around. With immutable data structures you have cheap thread safety at the cost of possibly working with stale data. With mutable data structures you have the benefit of always working on fresh data at the cost of having to write complicated logic to keep the data consistent. It’s not like one of those is obviously better than the other.

    Programs are usually shorter and in some cases easier to read

    Except in the cases where they are longer and harder to read. Learning how to read programs written in a functional style is a difficult skill; people seem to be much better at conceiving of programs as a series of steps to be followed, like a recipe, rather than as a series of calculations to be carried out.

    Productivity goes up (example: Erlang)

    Productivity has to go up a lot in order to justify the massive expense of hiring programmers who know how to program in a functional style.

    And remember, you don’t want to throw away a working system; most programmers are not building new systems from scratch, but rather maintaining existing systems, most of which were built in non-functional languages. Imagine trying to justify that to shareholders. Why did you scrap your existing working payroll system to build a new one at the cost of millions of dollars? “Because functional programming is awesome” is unlikely to delight the shareholders.

    Imperative programming is a very old paradigm (as far as I know) and possibly not suitable for the 21th century

    Functional programming is very old too. I don’t see how the age of the concept is relevant.

    Don’t get me wrong. I love functional programming, I joined this team because I wanted to help bring concepts from functional programming into C#, and I think that programming in an immutable style is the way of the future. But there are enormous costs to programming in a functional style that can’t simply be wished away. The shift towards a more functional style is going to happen slowly and gradually over a period of decades. And that’s what it will be: a shift towards a more functional style, not a wholesale embracing of the purity and beauty of Haskell and the abandoning of C++.

    I build compilers for a living and we are definitely embracing a functional style for the next generation of compiler tools. That’s because functional programming is fundamentally a good match for the sorts of problems we face. Our problems are all about taking in raw information — strings and metadata — and transforming them into different strings and metadata. In situations where mutations occur, like someone is typing in the IDE, the problem space inherently lends itself to functional techniques such as incrementally rebuilding only the portions of the tree that changed. Many domains do not have these nice properties that make them obviously amenable to a functional style.

  22. Thanks, babor, you make some excellent points here, not least that most programming is maintenance of existing (imperative) systems rather than building new (functional or imperative) ones.

    I have a post lined up on what I call side-effect schizophrenia: that it’s easier to reason about code that doesn’t have side-effects, but ultimately the only reason we run programs at all is for the side-effects. (Dammit, now I just summarised the entire post in 24 words — is there any point in writing the post?)

  23. Pingback: Five and a half months late | The Reinvigorated Programmer

  24. Pingback: Tagore Smith on functional programming | The Reinvigorated Programmer

  25. Pingback: Too Much Imperative? « I, Geek

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