Tail Recursion: Shame of a Paradigm

Proponents of functional programming are a dedicated lot, and I can’t blame them.  Years ago, I was fanatical about Haskell — a pure functional language.   It really changed how I thought about programming.   Maps, filters, folds, closures, currying, combinators, point free programming! I still like to think in functional terms, both for practical reasons and as a pleasant mental exercise.

Also the promises of functional programming are enticing.  Extracting programs from proofs?  Automatic concurrency management?  Mathematical rigor in software development?  What’s not to like?

A lot, sadly.  Not everything’s rosy in the functional world. Functional languages have their disadvantages, and this article is dedicated to one that I have not seen mentioned.

I will start at the beginning, in a semi-axiomatic style with obvious points and work my way up to the conclusions.

So let’s start…

 

Being forced to manage details irrelevant to the problem at hand is a failure of the language.  For instance, if I’m processing a list, manual memory management is a failure of the language.  List processing’s my job, not memory management!

Being forced to program in a certain style is only excusable if that style makes my job easier; otherwise, it’s a huge failure for the language. 

Functional languages force me to program in a certain style to handle irrelevant low level details: namely, tail recursion.  For example, here’s a non-tail recursive sum function:

      sum [] → 0

      sum head:tail → head + (sum tail)

I have to rewrite it like this to be tail recursive:

      sum list → sum’ list 0

         where

           sum’ [] total → total

           sum’ head:tail total → sum’ tail head+total

This is unacceptable.

Therefore, tail recursion represents a severe failure in functional languages.  If you thought manual memory management was bad, mull over this.  It only required that you track memory use and insert the right calls.  This requires that you change HOW YOU CODE.

 

NOTE: Fortunately, much of functional recursion can be replaced by use of higher order functions. However, these functions (and closures) are available in modern imperative languages, thus rendering that benefit for functional programming moot. This means the big differentiator is recursion so this issue is a bigger problem than ever.


Advertisements

One thought on “Tail Recursion: Shame of a Paradigm

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