What does Functional Programming Mean?

Courtesy:  Tony Morris

Abstract

This presentation is intended for the February 2010 meeting of the Brisbane Functional Programming Group http://www.meetup.com/Brisbane-Functional-Programming-Group-BFG/.

The term functional programming has become common nomenclature, but its definition is also ambiguous. There are many de facto definitions, all of which fail to identify the important point to functional programming.

This work is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License Appendix B, Licence.


Introduction

In a 1977 Turing Award[1] lecture, John Backus proposed the question “Can We Be Liberated From the von Neumann Machine?” [CanWeBeLiberated]

Backus then went on to propose an answer to this question, which has been the inspiration for a particular approach to programming research by achieving a degree of compositionality.

To Miss The Point

Identifying the Essentials

  • There are some (many) definitions of “functional programming” that miss the point.
  • We may have lengthy discussions about which is correct.
  • However, I propose that we remain focussed on the point.
  • The Essence of Functional Programming [EssenceFp] or Why Functional Programming Matters [WhyFP].

Functional Programming is programming with functions

It is often supposed that functional programming is the use of higher-order functions (HOFs).

Example 1. Python

>>> map(lambda a: a + 1, [1, 2, 3])
[2, 3, 4]
Example 2. C#

csharp> new []{ 1, 2, 3 }.Select(a => a + 1);
{ 2, 3, 4 }
Example 3. Scala

scala> List(1, 2, 3) map (1+)
res0: List[Int] = List(2, 3, 4)

But this misses the point, so…

  • Some say it is about advanced type system features.
  • Example 4. Higher-order polymorphism with rank-n data types

    data Monad m = M {
      forall a. a -> m a
      forall a b. m a -> (a -> m b) -> m b
    }

But this is off the mark too

  • We might talk about this all day long.
  • Is Python a functional language? What about Scala? C#? Java even?
  • Am I functional programming? Are you? Is this functional code? What about that?
  • Who cares!?
  • Stop avoiding the important question; even though it is hard!

What Does Functional Programming Mean?

  • …and what are the practical implications?
  • Central to the thesis of FP is the notion of referential transparency.
  • Referential transparency leads to program compositionality.

Referential Transparency

X x = function(args);
R r1 = arbitrary(x);
R r2 = arbitrary(x);
R r1 = arbitrary(function(args));
R r2 = arbitrary(function(args));
  • If these two programs produce the same outcome then function is referentially transparent.
  • In a pure functional language, all functions are referentially transparent (aka pure).

Compositionality (Frege’s Principle)

Purity

Purity leads to compositionality.

  if(player.score > 0)
    player.setSwizzle(7);
  else
    player.setSwizzle(player.swizzle + 1);

Analyse this program. It intertwines purity with impurity (setSwizzle).

  S s = player.score > 0 ? 7 : player.swizzle + 1;
  player.setSwizzle(s);

Now we have untangled it a little.

Measuring compositionality

  • Supposing a program composed of parts A B C and D and a requirement for program of parts A B C and E.
  • The effort required to construct this program should be proportional to the size of E. The extent to which this is true is the extent to which one achieves the central thesis of Functional Programming.
  • Identifying independent program parts requires very rigorous cognitive discipline and correct concept formation. This can be very (very) difficult after exposure to sloppy thinking habits.

Implications

  • Composable programs are easier to reason about. We may (confidentally) determine program behaviour by determining the behaviour of sub-programs -> fewer bugs.
  • Composable programs scale indefinitely, by composing more and more sub-programs.
  • There is no distinction between a “small” and a “large” application; only “smaller than” or “greater than”. [2]

Languages

  • While all turing complete languages are equivalent, some are more amenable to achieving the goals of the FP thesis than others.
  • Extremely poor: Java (http://functionaljava.org/), Python, Ruby, JavaScript, C, C++
  • Moderate but still poor: Scala (http://code.google.com/p/scalaz), C#, F#
  • Practical: Haskell, Clean (pure, lazy functional languages).
  • There is nothing in between (this is an implication of the central tenet of FP!). We need a revolutionary leap to discontinue the overwhelming, costly mistakes we currently endure and often insist on!
  • This is unfortunate, but this is true. Let’s face the hard facts. Let’s understand What Functional Programming Means.

Beware

  • PS: Beware of the popular FP/OO false dichotomy.
  • Questions?

Bibliography

[EssenceFp] Philip Wadler . 1992 . The Essence of Functional Programming .
[WhyFP] John Hughes . 1984 . Why Functional Programming Matters .
[CanWeBeLiberated] John Backus . 1977 . Can We Be Liberated From the von Neumann Machine? .

Advertisements