Ask HN: Functional Programming Differences | Hacker News Reader

Ask HN: Functional Programming Differences

I found out today that I'm speaking at the local Code Camp next weekend. The topic is introducing F# and functional programming to a lot of C# and VB Microsoft guys.

I've got some good sample code, but my question is this: what are the key things you would tell an imperative programmer about functional programming? I need about a dozen key points to get across before I start drowning them in code.

So far I'm thinking: "start little, grow big", "stay immutable", "factor relentlessly", "learn recursion", and "treat functions as first-class citizens"

Any other blurbs come to mind that capture the differences in thinking between imperative and functional code?

View on HN

"Our programming model does not have to match how our computer works."

I think one of the biggest intellectual hurdles with functional programming is that we know, deep down, that modern computers don't work like that. They do have side-effects and changing, carried state. It's a revelation to realize that the programming model you use to write programs doesn't have to match how the computations will be physically carried out.

I think that there is a stepping stone, half-way between "talk" and "code". I remember a question on comp.lang.lisp. A student had the task of writing a "sublist" function, for example, (sublist (a b c d e f g) 3 2) => (d e). He task was to do it functionally and he was stuck.

But would supplying code unstick him? It seemed unlikely. Thinking about the equation "Concepts + details = code" I wondered if there was a way of conveying the concepts first, before getting down to the details, and wrote:

Put on your Dijkstra robe, and sit in your arm chair, with a cup of tea, and write on a pad of paper, made from dead tree, using a pen with real liquid ink. This is mathematics not computation :-)

    (sublist (a b c d e f g) 3 2) = (sublist (b c d e f g) 2 2)
                                  = (sublist (c d e f g) 1 2)
                                  = (sublist (d e f g) 0 2)
                                  = (d . (sublist (e f g) 0 1)) 
                                  = (d e . (sublist (f g) 0 0))
                                  = (d e . nil)
                                  = (d e)

compare this to peano arithmetic

    (- 7 3) = (- 6 2)
            = (- 5 1)
            = (- 4 0)
            = 4

If you want to learn recursion you should move quite quickly to writing code because that animates your recursions and clears up any lingering misconceptions. On the other hand, jumping from the words "learn recursion" direct to code is a big leap. Recursion has its own soul, separate from its embodiements in various programming languages.

The poor guy was stuck because he though: how do I build my sub-list? Without side effect and this way of thinking, of course he was stuck. The example you have shown demonstrate you wondered what would be a simpler equivalent expression ("simpler" meaning "eventually trivial", of course).

If you think "what", recursion is easy. If you think "how", recursion is magic. I think that is the biggest leap. I forgot how I made the jump, however.

You might include something more explicit about function composition (e.g. the power of currying).

Closures might be another thing to mention. For instance, you could show how they can be used to implement objects (which should be familiar to C# people).

Composability in general is a major attraction of functional languages. Haskell has an especially strong focus on it.

I'm torn on closures and currying/composition.

Great concepts, sure. But in an hour? Might be too much to get their heads around.

One of my code samples is going to be lifted from this great blog entry: http://diditwith.net/2008/03/14/WhyILoveFARefactoringTale.as... where he basically covers some of these concepts by way of example.

I think no matter how I do it, it's going to look (to them) like some hand-waving and magic. Can't really help that, I don't think.

If you are going to go any distance into the functions as first-class citizens path then it might not be too much of a diversion to show a function that generates functions and then bounce quickly to simple currying as a more advanced example of this. You would not even need to describe it as currying..

Plus, first class functions can be shown with mere high school mathematics. Lambda are really easy: the

    f: R  -> R
       x |-> blah(x)

you find in high school would be

    f : (float -> float)
      = fun x  -> blah x

In Ocaml (and probably F#).

The composition operator can easily be seen as a function with two arguments, which show "first class" functions:

    o : (R->R), (R->R)  -> (R  -> R      )
        (f    , g    ) |-> (x |-> f(g(x)))

And poof, you can introduce currying:

    o : ((R->R), (R->R) , R)  -> R
        (f     , g      , x) |-> f(g(x)))

"Treat functions as first class citizens"

Actually, Object oriented programmers already do this. If they use "class polymorphism", "mixins", or any mechanism where an object's method could be determined at runtime, they use first class functions. They just don't know it yet. So, take an example where they would use mixins, then present them a closure or lambda equivalent. That should make functions less scary. (Side note: try to avoid the terms "first class" and "anonymous", "closure", and "lambda". "Ordinary" and "literal" are better, less scary. They point out the fact that functions are as mundane as integers, or strings, so of course they could be parameters or return values.)

"stay immutable"

This is indeed crucial. But effectively impossible until you don't change the way you think. Most imperative programmers think about what the objects should do. Of course, without side effect, they won't do anything, making programming impossible. So they have to think more about what the objects should be. Then, they will be able to avoid side effects until they are really needed.

"factor relentlessly"

Talk about that only when you have talked about functions (don't say "first class"!), as an example of how you could really use them. `sort`, `map` and `filter` would be my favourite examples. Insist on the low syntactic burden of factoring.

To me, "functions as first-class citizen" implies that the language being spoken about treats functions on the same level as other data. In that sense, I don't agree that OO programmers "already do this."

What you are getting at, though, is that constructs they are already familiar with can be expressed functionally. That is a good point, and it always helps make concepts more concrete when you provide a mapping from current knowledge to new knowledge.

Functional programming make testing easier. Functional programming make threading easier. Functional programming make understanding things easier. (i.e. easier to understand something that will never change vs understanding all the possible permutations of something)

(Sorry for my bad english)

Those are the standard claims, but drowning the reader in code that consists of lots of tiny, obscurely named functions (most of which you just defined), combined with abstractions based on high-level mathematics, limits your audience to people who would be comfortable reading mathematics papers. That's pretty much the opposite of making it easier to understand something.

I like Haskell for the intellectual challenge, but if the aim is to write clear example code that will be understandable to a large audience, you'd be much better off writing it in Python.

Well, you choose how you want to name your function. That you code in a functional style, or in python or in haskell has nothing to do with that. And the fact that you use high-level level function based on maths is still a choice of yours.

What I say is by using a functional style (might it be in java, c++, haskell, scheme, python, or whatever), it makes testing, threading and understanding things easier.

For instance, it's easier to test an immutable class since once it is created, it will never change.

Threading is also simplified since you don't have to think about your object being corrupted by 2 threads mutating it.

Understanding is simplified in the sense that it's easier to quickly get an idea of what an object is doing because it only has 1 state at a time.

But please, don't think I didn't understand your point about obscurely named function and bad code.. Often when people show functionnal code, they try to show how short the code is so they make it practically unreadable for the novices - which is indeed not the best way to show the vertue of FP.

"you'd be much better off writing it in Python." => Nothing stop you from using FP in python :)

I think numbers 2 and 4 are going to be the most valuable in introducing functional programming. I've been using Scala to learn functional programming, and the hardest conceptual pieces for me have been been staying immutable and using recursion.

Another point I'd consider is "avoid side-effects".

"Avoid side-effects" is #1 IMO. Everything else stems from it.

The funny thing is after playing around with functional programming for a bit simply out of interest I've found that I've definitely changed to 'avoid side-effects' in my 'regular' programming as well, and it really helps to do that.

Assignment is evil (most of the time): http://news.ycombinator.com/item?id=1117217

That's because it's relatively rarely needed: http://www.info.ucl.ac.be/~pvr/paradigms.html (I don't recall the HN submission.) The paper says that any feature in a programming language makes it more difficult to analyse it. First class functions are one of them. Named state (with assignment) is another. So, when such a feature isn't needed (for, say, modularity), the complexities it introduces are unnecessary.

My version would be slightly bigger-picture (some are the same as yours, though):

- Functional design is about breaking a problem up into a series of transformations (functions) on data, rather than modelling object states and behaviors.

- Compose the transformations by treating functions as first-class citizens. Introduce map, filter, foldr, etc. here

- "Functional" = Avoid side-effects! (wrap an I/O layer around your pure core processing instead) Otherwise the composing breaks.

(optional):

- "Start little, grow big", "factor relentlessly" - these are good concepts in ALL programming, and they apply here too.

I think if you just get those points in an hour, along with a nice example (I think F# comes with a web crawler that illustrates all these points), you'll have done very well.

"stay little, grow big" is probably one of the less-appreciated points there and I'm exuberant that you noted it. It's also something that they likely won't encounter until they've actually tried writing something more open-ended in a functional language, like a full-blown program of any sort. It's like telling people to use MVC for a GUI. Important to mention it, but it's going to take some experience before it's down pat.

OT: I fit the profile of your target audience. So, if you don't mind, please post your slides after your talk. Thanks.

I'd focus really heavily on "stay immutable", "use recursion", and lambda functions. I think these things take a little effort to get used to, especially if you are stuck heavily in a certain programming paradigm as many Microsoft focused guys often are.

Programming with expressions (functional) vs programming with statements (imperative).

I tend to avoid naked recursion whenever possible. It is not much better than loops. Combinators like foldr, filter and map reduce the cognitive overhead.

Me too, of course. But every now and then you've got something a little strange to do, like slice a immutable list, and you're recursing.

The thing about recursion is that for imperative guys, the first place they go is the for...next loop. Whereas in FP the first place you should go is the built-in stuff like map, fold, etc. But the second place is recursion (with the tail calls done correctly), not for..next

Slicing an immutable list should be a library function (splitAt or span in Haskell), and even if it weren't, it can be written as a fold:

  splitAt :: Int -> [a] -> ([a], [a])
  splitAt n xs = (reverse before, reverse after)
    where
      (before, after, _) = foldl' incr ([], [], 0) xs
      incr (ys, zs, m) x | m < n = (x:ys, zs, m + 1)
      incr (ys, zs, m) x = (ys, x:zs, m + 1)

Basically, any imperative loop can be transformed into a foldl' where the accumulator is all the loop state and the increment function is the loop body, taking in the loop state and the current element. Breaks and continues are represented by returning the same loop state that is passed in. If you have breaks, you'll want a foldl (non-strict) instead of foldl' (strict), because lazy evaluation will prevent the rest of the loop from being executed.

That works. Thanks for the tip -- I never thought of foldl as a universal replacement for for/next.

Here's what I've been using for slicing:

  let slice l b e =
          let rec slice_2 l b e f =
                  match l with
                  [] -> f
                  | h::t -> if (b<2)
                          then
                                  if (e>0)
                                  then ( slice_2 t b (e-1) (f@[h]) )
                                  else f
                          else
                                  ( slice_2 t (b-1) (e-1) f )
          in
          slice_2 l b e [];;

Though you are right that foldl and friends don't always help you. Especially in strict languages. But you can define your own combinators---to hide away the recursion in.

How about using an application to illustrate the power of FP. Combinatorial parsers are a neat non-trivial, but (hopefully) understandable, choice.

I would stress composability (which fits in with that whole DRY fad).

Also, the ability to reason about your code is a big selling point of side-effect free code. When you don't have to keep track of a bunch of state in your head, it's much easier to reason about what code does, and find any bugs or unexpected behavior.

Reply on news.ycombinator.com