Introduction
- Twenty five years ago, Hughes published a paper entitled “Why Functional Programming Matter".
- It shows that two distinctive functional features, namely higher order functions and lazy evaluation, are capable of bringing considerable improvement in modularity.
- Twenty five years on, how has functional programming mattered? Hughes’s vision has become more widely accepted. Main-stream languages such as C#, C++ and Java scrambled one after another to offer dedicated support for lambda expressions, enabling programming with higher-order functions. Lazy evaluation has also risen to prominence,
- One way to gauge the popularity of functional programming is through its presence at conferences both in academia and industry.
- Functional languages are also increasingly being adopted by industry in the real world.
- Generally speaking, functional programming is a style of programming: the main program is a function that is defined in terms of other functions, and the primary method of computation is the application of functions to arguments.
- Functional programming has no implicit state.
- Functional programming focuses on what is being computed rather than how it is being computed.
- Functional programs are more declarative and often much shorter than their imperative counteparts.
- In the imperative program, ‘=’ refers to a destructive update, assigning a new value to the left-hand-side variable, whereas in the functional program ‘=’ means true equality.
- This characteristic of functional programming (known as referential transparency or purity) has a profound influence on the way programs are constructed and reasoned about
- Since functional programming is a style, in theory one could write functional programs in any language, but of course with vastly dif- fering levels of effort. We call a language functional if its design encourages or to some extent enforces a functional style.
- In this paper, we mostly use Haskell, because Haskell is not only a dominant functional language, but also covers all the most important features of functional programming.
Correctness of program construction
- In order to specify the complete correctness of any imperative program, one has to describe the whole state of the system, and the unlimited possibilities of interacting with the outside world - an impossible task indeed.
- Functional programming departs dramatically from this state of impediment by promoting purity: the result value of an execution depends on nothing other than the argument values.
- Consequently, it becomes possible to specify program behaviours independently of the rest of the system.
- This freedom makes functional programs more tractable mathematically than their conventional counterparts, allowing the use of equational reasoning in the design, construction and verification of programs.
Equational reasoning
Correctness proofs
- Functional programs are often recursively defined over datatypes, lending themselves well to proofs by structural induction.
Property-based testing
- Using the QuickCheck test library, properties can be expressed via Haskell function definitions.
- QuickCheck defines a domain specific language, embedded in Haskell, for expressing properties in a testable subset of predicate calculus.
Automatic optimization
- The Glasgow Haskell Compiler (GHC) uses equational reasoning extensively internally, and also supports programmer-specified rewrite rules (equational transformations) as part of the source program (in pragmas) for automatic optimization.
- HERMIT is a powerful toolkit for developing new optimizations by enabling systematic equational reasoning inside the Glasgow Haskell Compiler’s optimization pipeline.
- Higher-order functions are not only useful for expressing programs, they can be helpful in reasoning and proofs as well.
- Two of the most important higher order functions are fold and unfold (also known as catamorphism and anamorphism).
- We give them the name functional forms - they can be used as design patterns to solve many computational problems, and these solutions inherit their nice algebraic properties.
Algebraic datatypes
data List α = Nil | Cons α (List α)
Fold
- Foldr, which consumes a list and produces a value as its result.
Unfold
- Unfoldr is the dual of foldr, which generates a list from a “seed”.
- Compositions of an unfold followed by a fold form very interesting patterns, known as hylomorphisms.
General laws
- foldr has the following uniqueness property:
foldr f 1 e 1 ≡ foldr f 2 e 2 ⇔ f 1 ≡ f 2 ∧ e 1 ≡ e 2
- foldr is equipped with a general fusion rule to deal with composition of foldrs, saying that composition of a function and a foldr can be fused into a foldr, under the right conditions.
h (f a r) ≡ f a (h r)
-----------------------------
h ◦ foldr f e ≡ foldr f (h e)
- Multiple traversals of the same list by different foldrs can be tupled into a single foldr, and thus a single traversal.
h x = (foldr f1 e1 x, foldr f2 e2 x)
----------------------------------------
h = foldr f (e1, e2)
where f a (r1, r2) = (f1 a r1, f2 a r2)
- Equational reasoning and higher order functions (functional forms) enjoy a symbiotic relationship: each makes the other much more attractive.
Types
Polymorphic types
- In 1978, Milner introduced polymorphic types to ML, to solve this problem. The key idea is to allow types to include type variables, which can be instantiated to any type at all, provided all the occurrences of the same variable are instantiated to the same type
- ML also supported type inference.
Type classes for overloading
- Haskell’s class system gives us a programmable type checker, which—while it does not allow us to accept programs that will generate run-time type errors—does allow us to construct type systems for DSLs embedded in Haskell with exquisite precision.
Types and logic
- Any type which is inhabited by some expression (in a sufficiently carefully designed functional language) corresponds to a provable property.
- Proof assistants such as Coq and Agda are based on this correspondence, the Curry-Howard isomorphism, and enable users to prove theorems by writing programs.
- A key notion here is that of a dependent type, a type which depends on a value.
Algebra of programming
Programming: Deriving programs from specifications
- We would like to have an algebra of programs: a concise notation for problem specification, and a set of symbol manipulation rules with which we may calculate (derive) programs from specifications by equational reasoning.
Programming theories
- Many laws (theorems) for deriving efficient functional programs from specifications have been developed.
Programming theory development
- Many theories for the algebra of programming have been developed.
Systems for program derivation
- Many systems have been developed for supporting program derivation and calculation.
- MagicHaskeller is an interesting tool that automatically synthesizes functional programs from input/output examples.
Structuring computation
- Side effects are encoded by a programming pattern known as monads.
- The concept of monads as a programming pattern has applications far beyond handling side effects; it is fundamentally a powerful way of structuring computations.
Monadic composition
- A monad M consists of a pair of functions return and (>>=) (pronounced as bind).
return :: α → Mα
(>>=) :: M α → (α → M β) → M β
- One shall read M α the type of a computation that returns a value of type α, and perhaps performs some side-effects.
- We cannot use a value of type M α directly, but we can combine it with other instructions that use the result.
- Monads not only encapsulate side effects, but also make them first class.
- Inspired by monads, other abstract views of computation have emerged, notably arrows and applicative functors.
Embedded domain-specific languages.pdf
- Languages produced through embedding are known as embedded languages, which are libraries in host languages.
- The languages resulting from are seen as embedded domain-specific languages (EDSLs).
- A classic example: Parser combinators.
Parallel and distributed computation
- Functional programming languages offer a medium where programmers can express the features of parallel algorithms, without having to detail the low-level solutions.
Parallel functional programming
- Functional languages have two key properties that make them attractive for parallel programming: they have powerful abstraction mechanisms (higher order functions and polymorphism) for supporting explicit parallel programming known as skeleton parallel programming that abstracts over both computation and coordination and achieves the architecture-independent style of parallelism, and they have no side-effect that can eliminate unnecessary dependencies for easy parallelization.
Skeleton parallel programming
- Parallel primitives (also called parallel skeletons) intend to encourage programmers to build a parallel program from ready-made components for which efficient implementations are known to exist, making the parallelization process easier.
- The higher order functions discussed in Section 2.2 can be regarded as parallel primitives suitable for parallel computation over parallel lists, if we impose some properties on the argument operators.
- Three known data parallel skeletons map, reduce and scan can be defined as special instances of foldr op e.
- map, reduce and scan have nice massively parallel implementations on many architecture. If k and an associative ⊕ use O(1) parallel time, then map k can be implemented using O(1) parallel time, and both reduce op e and scan op e can be implemented using O(log N ) parallel time (N denotes the size of the list).
Easy parallelization
- Purely functional languages have advantages when it comes to (implicit) parallel evaluation.
- Parallel Haskell provides two operators pseq and par for parallelization: (pseq e1 e2) evaluates e1 then e2 in sequential order, and (par e1 e2) is some kind of a fork operation, where e1 is started in parallel with e2 and the result of e2 is returned.
Distributed functional programming
- Distributed systems, by definition, do not share memory between nodes (computers) - which means that the imperative approach to parallel programming, with shared mutable data structures, is inappropriate in a distributed setting.
- This makes functional programming, with its immutable data structures, a natural fit.
- Erlang was designed at Ericsson in the late 1980s for building systems of this kind, originally for the telecom domain. Later, Erlang proved to be ideal for building scalable internet services, and many start-ups have used it as their “secret sauce”.
- Erlang’s approach to concurrency and distribution has been very successful, and has been widely emulated in other languages; for example, Cloud Haskell provides similar features to Haskell developers.
Functional thinking in practice
Education
- The style of teaching functional languages as first languages was pioneered by MIT in the 1980s.
- Now many universities such as Oxford (Haskell) and Cambridge (ML) follow this functional-first style.
- In a recent survey, 19 out of top 30 American universities in the US News 2014 Computer Science Ranking give their undergraduate students a serious exposure to functional languages.
- The functional-first approach has the advantages of reducing the effect of diversity of students in background, letting students focus on more fundamental issues, think more abstractly, and touch ideas of recursion, data structure, functions as first class data earlier.
- One of the explicit goals of Haskell’s designers was to create a language suitable for teaching.
- For learning the latest advanced functional programming techniques, there has been an excellent series of International Summer Schools on Advanced Functional Programming.
- There is a series of International Workshops on Trends in Functional Programming in Education.
Influences on other languages
- Ideas originated from functional programming such as higher-order functions, list structure, type inference etc. have made their way into the design of many modern programming languages,
Uses in industry
- There have been many, many start-ups using functional programming for their software development.
- The first company to use Haskell was Galois.
- More recently, Facebook boasts its spam detecting and remediating system being the largest Haskell deployment currently in existence, actively and automatically fighting off vast amounts of undesirable content from reaching its users.
- Erlang, with its roots in industry, has a strong start-up culture.
- The highest-profile Erlang start-up to date, though, is WhatsApp
A tech blog at the time asked "How do you support 450 million users with only 32 engineers? For WhatsApp, acquired earlier this week by Facebook, the answer is Erlang".
- Functional programming has also found many users in the financial sector.
- Credit Suisse was the first to use this technology.
- Functional programming is also used for automated trading at Jane Street.
- Apache Spark, a popular open-source framework for Big Data analytics, is largely built in Scala.
- New applications of functional programming are appearing constantly.
Conclusion
- Twenty-five years ago, functional programming was high in the sky, favored only by researchers in the ivory tower. Twenty-five years on, it has touched down on the ground and had a wide impact on the society as a new generation of programming. What would functional programming be in twenty-five years?