This is a read-only archive!

Functional programming hurts me

This post will probably come back to haunt me, but functional programming doesn't sit well with me. I'm trying again to read through SICP. Last time I tried, I lost track of it and gave up after a few chapters. This time I hope to persevere, and I'm trying to go more slowly through the examples to really understand things.

I was trying to do some of the exercises in chapter 1 today, and pretty much bombing on all of them. Most of the exercises I've seen so far in SICP sound like they came out of a math book. "There is a clever algorithm for computing the Fibonacci numbers in a logarithmic number of steps..." Uh huh. This is not the kind of problem I enjoy, or have even the slightest use for. But maybe the problems are only pointless examples to illustrate a point, like "mass-less friction-less pulleys" in physics textbooks. I can live with that I guess.

Here is a Scheme example from SICP to compute b to the power of n:

(define (expt b n)
  (expt-iter b n 1))

(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                (- counter 1)
                (* b product))))

This is presented as a wonderful and novel functional programming approach.

One of my problems is the amount of brain-work it takes to understand this. OK, start with EXPT. We take b and n, and then call some recursive helper function with b, n, and a state variable product initialized to 1 HEY WAIT A SECOND THERE'S A STATE VARIABLE?!

This is one way to cheat in functional programming, I guess. product is a variable name / symbol, which describes "something" that takes on different values over time, each value representing the same "thing" in different states. That qualifies as a state variable to me. The only difference is that the state variable is actually N different variables (with the same name) splattered across a bunch of frames on a call stack, instead of an abstraction of a single simple bucket where I dump a value.

Now in EXPT-ITER, counter starts at n, and every time the function calls itself, counter decreases by 1, until you reach 0, at which point EXPT-ITER stops calling itself and returns something. So this is a perverted, inside-out way of saying "do something N times", where every iteration costs me a recursive function call. Nice.

OK, what are we doing N times? We're multiplying product, which starts at 1, by b, which then becomes the new value of product next time around.

SO WHY NOT JUST WRITE THAT TO BEGIN WITH?

(defun simple-expt (b n)
  (let ((total 1))
    (dotimes (i n)
      (setf total (* total b)))
    total))

In Common Lisp this reads as "Let total start at 1. N times, set total to the product of total and b. Then return total." This is EXACTLY what the Scheme version is doing. Except I don't have to turn my brain inside-out to write it down this way. The CL code reads exactly like what the program is doing.

When all you have is a hammer, every problem looks like a nail. When all you have is recursion, every problem looks like it should be solved using recursion, I guess.

Actually if I ignore the functional programming bits, SICP is a great book. There are a lot of good things in there. But (so far) Scheme isn't one of them.

February 01, 2008 @ 4:53 PM PST
Cateogory: Programming

4 Comments

Adam
Quoth Adam on February 01, 2008 @ 6:34 PM PST

The problem really is just there to demonstrate a point. The class this book was designed around can't really expect much in the way of knowledge at this point. There's plenty of better examples of uses for recursion, but a fibonacci series is one of the few that is accessible at this point.

You'd also be interested to know that this implementation of expt-iter doesn't allocate a pile of stack frames in Scheme. The language standard guarantees tail call optimization, so in situations where one function returns the (unmodified) result of another the calling function's stack frame can be replaced with the callee. Due to this, expt-iter runs in constant space regardless of input.

This part of SICP really does seem like recursion for the sake of recursion. That's because it is, not due to the authors being blind towards other methods, but because students need to be forced to develop an understanding of it for cases where recursion is a more useful problem solving mechanism.

Jakub
Quoth Jakub on February 02, 2008 @ 1:25 AM PST

Ideally, statelessness and lack of side effects, which are what the example above is about, allow one to reason about any form in the program as a mathematically defined function, that is, the only thing it does is return a value, a the value returned depends only on the form arguments, which, in turn, are, at most, a function only of encompassing function's argument, defined either in place or through lexical environment.

That is, looking at the form (setf total (* total b))) you can't tell what it will return without considering dynamic environment as well, which changes over time, and you have to consider its side effect as well. Whereas for any form in Scheme example you can determine what it will return by simple substitution of definitions.

Obviously, in this example it only makes things more convoluted, as it will in many cases, especially "at the bottom". That's why I personally prefer CL to Scheme, or any other language trying to enforce a programming paradigm. But the general idea is useful, as there is a complexity level where not having to care about dynamic state can make reasoning about a program much easier. Also, unit testing is much easier if you can be certain that a function depends only on its arguments.

Chris Giroir
Quoth Chris Giroir on February 02, 2008 @ 1:54 AM PST

I think Jakub said it best already, but at that point in the book, state and side effects are not introduced yet (If I'm correct about where you are). You can't do a setf and what it means doesn't make sense in the substitution model so if you only have the knowledge that they present about how the computer computes things, you can't even work out what the second example would do.

If you augment the substitution model to allow for this you'd end up with something that looks exactly like the first method, wear you have a variable changing over time in the same call stack. I probably didn't explain it perfectly but the book doesn't go out to teach you the quickest way to solve things. You're trying to solve the problems with much more knowledge and experience then the book wants you to have at this point.

Ciaran McCreesh
Quoth Ciaran McCreesh on February 02, 2008 @ 2:31 AM PST

Functional programming books give lots of trivial but supposedly neat mathematical examples because that's all functional programming languages can sensibly do.