Courtesy: Tony Morris
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.
Table of Contents
- To Miss The Point
- What Does Functional Programming Mean?
- Referential Transparency
- Compositionality (Frege’s Principle)
- A. Tony Morris – PGP Key
- B. Licence
In a 1977 Turing Award 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.
It is often supposed that functional programming is the use of higher-order functions (HOFs).
- …and what are the practical implications?
- Central to the thesis of FP is the notion of referential transparency.
- Referential transparency leads to program compositionality.
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
functionis referentially transparent.
- In a pure functional language, all functions are referentially transparent (aka pure).
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 (
S s = player.score > 0 ? 7 : player.swizzle + 1; player.setSwizzle(s);
Now we have untangled it a little.
- 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.
- 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”. 
- While all turing complete languages are equivalent, some are more amenable to achieving the goals of the FP thesis than others.
- 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.