Categories

# It’s imperative that it’s functional

So last week I mentioned that I’d been practicing my Common Lisp by having a go at some puzzles on Project Euler.

A few days later I got an email asking me about what my experiences of the project were and how far I’d got on the puzzles. Well now I can reveal to all of you the heady extent of my genius. My correspondent also casually dropped in the fact that he was trying to do his puzzles in a functional, rather than imperative, programming style. Oh … yeah, “functional programming” I’d conveniently forgotten about that. I was so busy getting to grips with programming in CL I forgot about the important bit. I guess 15 years bashing your head against C++.Java and C# is going to have some long-term mental health effects.

## Losing the plot

Now, my CS class at University (15 years ago) very briefly touched on functional languages so I’m not totally clueless. However, we learnt precious little and there is really no defense for that University to not place a larger emphasis on functional programming. I would argue, now, that it would have been a lot more useful for them to teach us a functional language than what they did teach us, which was: COBOL.

So, given my limited understanding, the point of functional programming is to write programs that behave more like mathematical functions. This has certain consequences since a mathematical function can not have side-effects like printing “Hello, World!” or delivering spam. Which surely is going to disappoint some people.

It is this “dirty” little secret of programming (i.e. that it should probably do something if we’re gonna get paid) that makes pure functional-programming a little less straightforward. Languages like Haskell have monads that address the problem of purity by effectively differentiating the pure from the impure. But I don’t think I’m quite ready to go there just yet. Maybe in another 15 years.

## Taking the tablets

Ok, so where was I? Well, I’m going to try to make my code more functional too. Which means a diet of higher order functions and recursion for me. So let’s pick a trivial example and see how we do.

Problem #6 in Project Euler asks us:

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

My first solution looked like this:

(defun sum-of-arithmetic-series (n)
(/ (* n (1+ n)) 2)

(- (expt (sum-of-arithmetic-series 100) 2)
(loop for i from 1 to 100 sum (expt i 2)))


Which I was proud of because I’d figured out that I could use an equation to solve the first part. This isn’t terribly functional though because the second part uses a loop. So I tried again, this time I thought I could do better. I decided that what I was really doing was summing a series of natural numbers in the range 1..n. I could generalise this into: “apply a function (or the identity) over a series of numbers and sum the results”.

Looking at the problem this way generates an abstraction that did not previously exist in the earlier solution, making it a more general result and increasing the possibility of its reuse (perhaps!):

(defun sum-of-series (n &optional f)
(let ((n-dash (if (null f) n
(funcall f n))))
(if (= n 1) 1
(+ n-dash (sum-of-series (1- n) f)))))

CL-USER> (- (expt (sum-of-series 100) 2)
(sum-of-series 100 (lambda (x) (* x x))))
25164150
CL-USER>

 

Ok, I know it's trivial but it made me feel better. There was only one problem though. When testing this for large n (> 30000) I got stack-overflows. Which surprised me because I was expecting it to be tail recursive and hence a tail-optimization to happen. I tried playing around with the debug settings and trying different variations but no amount of playing could make SBCL do the right-thing and optimize the recursion away.

Guess I need to do some more investigation into functional programming and that's probably an imperative! (groan)

## 13 replies on “It’s imperative that it’s functional”

JFTsays:

Hello Steve,

you got the stack-overflow because your function is not tail-recursive. To be tail recursive the result of the recursive call must be used “as-is”.

In your exemple you’d need to have an additional parameter to accumulate the results so that when you are done you just return it. Transforming your function would yield:

(defun sum-of-series (n &optional f)
(labels ((helper (current total)
(let ((n-dash (if (null f)
current
(funcall f current))))
(if (

JFTsays:

Sorry it seems like the previous replied got truncated here’s the function:

(defun sum-of-series (n &optional f)
(labels ((helper (current total)
(let ((n-dash (if (null f)
current
(funcall f current))))
(if (

JFTsays:

Ok well it seems like your blog dont like part of the pgrogram and keeps truncating it 🙁

Any idea how I can post the code without it beeing “interpreted” by your blog?

Hi JFT,

WordPress, I think, truncates after unescaped < and >. Not sure though I’ll take a look.

I think I understand what you mean though. Even though my code looks like the sum-of-series is the last item it’s actuall part of a + statement and that’s the problem, it’s simply not tail recursive because there’s a summation that happens at the tail, not a recursive call. Doh! Thanks for pointing that out I’ll give it a try!

Steve

JFTsays:

You’re welcome 🙂

Out of curiosity how do I escape the “less than” and “greater than” sign ?

JFTsays:

Ok take 3 😛 Trying with HTML escaping!
(defun sum-of-series (n &optional f)
(labels ((helper (current total)
(let ((n-dash (if (null f)
current
(funcall f current))))
(if (&lt current 1)
total
(helper (1- current)
(+ n-dash total))))))
(helper n 0)))

JFTsays:

Trying a larger post (sorry I’m new at blogging!)

Seems like the it worked although formating got lost!

The idea here is that the function doing the real work is hidden inside and take an additional parameter (helper). “Labels” is used so the locally defined function can recurse. The original function name is now only use to jumpstart the helper!

Now I’d like to suggest another way to do this exercise, it is less performan in strict language than with lazy language but it has some value to learn functional programming IMO.

If you take the problem more literally it’s about working on the “list of natural”. So let’s first make a small function to get such a list (I’m more of and Haskeller so bear with me on CL 😉 )

(defun make-range (start end)
(labels ((helper (cur sofar)
(if (&lt cur start)
sofar
(helper (1- cur) (cons cur sofar)))))
(helper end ())))

Once we have that the rest of of the problem get’s even simpler and even more generic!
(setq nats (make-range 1 100))

What is the list of the 100 first natural squared?
(mapcar (lambda (x) (expt x 2)) nats)
Let’s generalize this to any list
(defun square-list (l)
(mapcar (lambda (x) (expt x 2)) l))

What about doing a summation?
(defun sum (l)
(reduce #’+ l))

If we put it all together:
(let ((nats (make-range 1 100)))
(- (expt (sum nats) 2)
(sum (square-list nats))))

Finally a last level of candy:
(defun square (x)
(flet ((sq (n) (* n n)))
(cond ((numberp x) (sq x))
((listp x) (mapcar #’sq x))
(1 (error “unsupported type”)))))

which afford us:
(let ((nats (make-range 1 100)))
(- (square (sum nats))
(sum (square nats))))

You have a nicer solution, which read almost like the problem and utilities to get range of numbers, sums & square 🙂

P.S. In Haskell all of this is simply
nats = [1..100] in (sum nats)^2 – (sum (map (^2) nats))
and assuming I am not using sum, which is part standard library, and rather use the Haskell equivalent of reduce here’s what I would get:
let nats = [1..100] in (foldl1 (+) nats)^2 – (foldl1 (+) (map (^2) nats))

JFTsays:

The make-range function termination test should be (“less-than” cur start) the symbol got eatten again!

Nice! Thanks.

Arnar Birgissonsays:

You can “cheat” a little, using the fact that the sum of the squares of 1,…,n is n(n+1)(2n+1)/6

A little arithmetic gives that the difference between the sum of squares and square of sum of 1,…,n is
(3n^4 + 2n^3 – 3n^2 – 2n)/12

Plug in n=100 and get 25164150

Hey Steve – it wasn’t just COBOL… we did Modula-2 as well 😉

Oh yeah! Modula-2 wasn’t bad. It was easy to apply the principles to other languages so it had some value.

I don’t know about your experience, but for me I think if we’d have learnt C and a dynamic language of the time (like Smalltalk) it would have been more valuable than what we did learn. To me at least.

Yeah – I quite liked the Modula-2 stuff but you are far more qualified than me to comment on the suitability of the programming languages we were taught (having not followed that path in my career).

Certainly from an infrastructure perspective a little bit of Windows NT (even OS/2 or LAN Manager) would have set me up far better than any of the stuff we were doing! And how many times were we told in our OS internals module that the PowerPC would kill off the 80×86 line of CPUs…

Those were the days.