How to Check Komp Structure During Order Processing
Abstract
In 1989 when functional programming was still considered a niche topic, Hughes wrote a visionary paper arguing convincingly 'why functional programming matters'. More than two decades have passed. Has functional programming really mattered? Our answer is a resounding 'Yes!'. Functional programming is now at the forefront of a new generation of programming technologies, and enjoying increasing popularity and influence. In this paper, we review the impact of functional programming, focusing on how it has changed the way we may construct programs, the way we may verify programs, and fundamentally the way we may think about programs.
INTRODUCTION
Twenty-five years ago, Hughes published a paper entitled 'Why Functional Programming Matters' [1], which has since become one of the most cited papers in the field. Rather than discussing what functional programming isn't (it has no assignment, no side effects, no explicit prescription of the flow of control), the paper emphasizes what functional programming is. In particular, it shows that two distinctive functional features, namely higher order functions and lazy evaluation, are capable of bringing considerable improvement in modularity, resulting in crucial advantages in software development.
Twenty-five years on, how has functional programming mattered? Hughes's vision has become more widely accepted. Mainstream 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, with numerous papers on new ways to exploit its strengths and to address its shortcomings.
One way to gauge the popularity of functional programming is through its presence at conferences both in academia and industry. The ACM International Conference of Functional Programming grew to 500 participants in 2014. Developer conferences on functional programming abound—such as the Erlang User Conference/Factory in Stockholm, London and San Francisco, Scala Days and Clojure West in San Francisco, Lambda Jam in Chicago, Lambda Days in Krakow—all with hundreds of participants. Functional programming is also well represented nowadays at more general industry conferences such as GOTO in Aarhus, Strange Loop in St. Louis, and YOW! in Melbourne, Brisbane and Sydney, each with well over 1000 delegates.
Functional languages are also increasingly being adopted by industry in the real world (https://wiki.haskell.org/Haskell_in_industry). To name a few examples, Facebook uses Haskell to make news feeds run smoothly; WhatsApp relies on Erlang to run messaging servers, achieving up to 2 million connected users per server; Twitter, LinkedIn, Foursquare, Tumblr, and Klout use Scala to build their core infrastructure for sites. And while not using functional languages directly, Google's popular MapReduce model for cloud computation was inspired by the map and reduce functions commonly found in functional programming.
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. Unlike traditional imperative programming, where computation is a sequence of transitions from states to states, functional programming has no implicit state and places its emphasis entirely on expressions (or terms). Functional programming focuses on what is being computed rather than how it is being computed, much like the way we define mathematical functions. As a simple example, consider a mathematical definition of the factorial function:
\begin{equation*} \begin{array}{llll}0! &=& 1\\ (n+1)! &=& (n+1) n! \end{array} \end{equation*}
Its definition in the functional language Haskell [2] has exactly the same structure:
\begin{equation*} \begin{array}{llll}\mathit {fac}\;0 &=& 1\\ \mathit {fac}\;(n+1) &=& (n+1) * \mathit {fac}\;n \end{array} \end{equation*}
In contrast, with imperative programming, we would consider a state of (n, s) representing the current counter and the partial result, and show how to compute the final result by a sequence of state transitions from the initial state of (x, 1):
n = x;
s = 1;
while (n>0) do {
s = s*n
n = n-1;
}
The contrast in style is apparent: functional programs are more declarative and often much shorter than their imperative counterparts. This is certainly important. Shorter and clearer code leads to improved development productivity and higher quality (fewer bugs).
But it is probably a more subtle difference, well hidden behind the overloaded use of the symbol '=', that really sets the two apart. 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: fac 0 is equal to 1 in any execution context, and can be used interchangeably. This characteristic of functional programming (known as referential transparency or purity) has a profound influence on the way programs are constructed and reasoned about—a topic that will be covered extensively in the section entitled 'Correctness of program construction'.
What this toy example does not illustrate is the use of higher order functions, a powerful abstraction mechanism highlighted in Hughes's paper [1]. We will not repeat the message here. Instead, we will describe the concept of monads (in the section entitled 'Structuring computation'), a design pattern for structuring computation that crucially depends on higher order functions. We will show how monads are used in developing domain-specific languages (DSLs) and taming side effects. In the section entitled 'Parallel and distributed computation', we revisit the ideas of purity and higher order functions in the context of parallel and distributed computing, again showing the unparalleled advantages that they bring. Lastly, in the section entitled 'Functional thinking in practice', we briefly sketch the impact of functional programming in terms of influence on education and other programming languages, and real-world adoption. As a note to readers, this review paper is not intended to systematically teach functional programming, nor to comprehensively discuss its features and techniques. They can be found in various textbooks on functional programming [3–5]. Rather, we aim to give a broad and yet focused view on how functional programming has mattered to software development, through showcasing advances in both academia and industry.
Since functional programming is a style, in theory one could write functional programs in any language, but of course with vastly differing levels of effort. We call a language functional if its design encourages or to some extent enforces a functional style. Prominent languages in this category include Haskell [2], Erlang [6], ML [7,8], OCaml [9], F# [10], Lisp [11,12], Scheme [13], Racket [14], Scala [15], and Clojure [16]. 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
Today's software systems are essential parts of our everyday lives, and their correctness is becoming ever more important; incorrect programs may not only cause inconvenience, but also endanger life and limb. A correct program is one that does exactly what its designers and users intend it to do.
Obvious as it sounds, guaranteeing the correctness of programs, or even defining the meaning of correctness, is notoriously difficult. The complexity of today's software systems is often to blame. But the design of many programming languages in use today—the fundamental tools we use to build software—does not help either. Programs are expressed as sequences of commands returning a final result, but also at the same time updating the overall state of the system—causing both intended and unintended side effects. State update is just one of the many kinds of side effect: programs may throw exceptions, send emails, or even launch missiles as side effects. For 'convenience', most languages allow such effects to be performed, without warning, anywhere in a program.
The result is that in order to specify the complete correctness of any 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. Just consider the task of testing part of a software system—perhaps a function called f. Before f can be executed, the tester must bring the system into the intended pre-state. After f has finished, the tester must check the outcome, which includes checking that the system state is as expected. But in general, the system state is only partly observable, and even identifying the parts of the state which f changed is problematic. Much of the work of testing imperative software consists of setting up the right state beforehand, and observing the final state afterwards.
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, and no state may change as program execution proceeds. Consequently, it becomes possible to specify program behaviours independently of the rest of the system. For example, given a function that reverses a list (where [ ] represents the empty list and + + appends two lists), we can state the following set of properties governing the function's correctness. (As a notational convention, we use '≡' to denote semantic equality to avoid confusion with the use of '=' (function definition) and '==' (comparison for structural equality) in Haskell.)
\begin{eqnarray*} \begin{array}{l{@}{\quad}l{@}{\quad}l}\mathit {reverse}\;[\,] &\equiv & [\,]\\ \mathit {reverse}\;[x] &\equiv &[x]\\ \mathit {reverse}\;(ys \,{+\!\!+}\, xs) &\equiv & \mathit {reverse}\;xs \,{+\!\!+}\, \mathit {reverse}\;ys \\ \mathit {reverse}\;(\mathit {reverse}\;xs) &\equiv & xs\\ \end{array} \end{eqnarray*}
As there are neither side effects nor outside influence, these laws (the first three) completely characterize the function |$\mathit {reverse}$|. Drawing an analogy with sworn testimony, the laws specify 'the behaviour, the whole behaviour, and nothing but the behaviour'! The significance of this ability to claim that two expressions are equal (in any semantically observable way) is that one can now freely replace variables by their values, and in general any expressions by their equals—that is, programs are referentially transparent. 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.
This is just a toy example, but the underlying idea is far-reaching. Readers who are Linux users may have come across xmonad (http://xmonad.org/), a tiling window manager for X11, known for its stability. xmonad is implemented in Haskell and relies on heavy use of semi-formal methods and program derivation for reliability; window manager properties (such as the behaviour of window focus) are specified as equational laws, similar to the ones above, and exploited for testing using QuickCheck [17].
The holy grail of program correctness is to prove the absence of bugs. A landmark achievement in this respect is Leroy's CompCert [18], an optimizing C compiler which is almost entirely proven correct with the Coq proof assistant. Tellingly, when John Regehr tested many C compilers using his random C program generator CSmith, he found 79 bugs in gcc, 202 in LLVM and so on, but only 6 in Compcert [19]. The middle-end bugs found in all other compilers were entirely absent from CompCert, and as of early 2011, CompCert is the only compiler tested with Csmith which lacks wrong code errors. As in the case of xmonad, the use of purely functional immutable data structures played a crucial role in this unprecedented achievement. This idea of immutability is also appearing in application areas where people might least expect it. Datomic (http://www.datomic.com), a fully transactional, cloud-ready and distributed database, presents the entire database as an immutable value, leveraging immutability to achieve strong consistency combined with horizontal read scalability.
In the rest of this section, we will see equational reasoning at work—in formal proofs of program correctness, in program testing, and in program optimization—how to associate algebraic properties to functional forms for program reasoning, how to automatically verify type properties, and how to structure and develop algebraic properties and laws for program derivation.
Equational reasoning
We have already seen the use of equational properties as specifications in the reverse example. Thanks to referential transparency, we are not only able to write the specifications, but also to reason with them.
Correctness proofs
One way to make use of these equations is in correctness proofs, just as in mathematics. Functional programs are often recursively defined over datatypes, lending themselves well to proofs by structural induction. For example, the |$\mathit {reverse}$| function we have already specified via equations can be defined in Haskell as follows:
\begin{equation*} \begin{array}{llll}\mathit {reverse}\;[\,] &=& [\,]\\ \mathit {reverse}\;(x:xs) &=& \mathit {reverse}\;xs \,{+\!\!+}\, [x] \end{array} \end{equation*}
The second equation says that, to reverse a list with the first element as x and the rest of the list as |$\mathit {xs}$|, we reverse |$\mathit {xs}$| and append x to the end of it. In fact, this equation is derivable from the third law for |$\mathit {reverse}$| by replacing ys by [x] and simplifying.
Now suppose we wish to prove that the definition actually satisfies its specification, say the property that |$\mathit {reverse}$| is its own inverse: for any finite list |$\mathit {xs}$|,
\begin{equation*} \mathit {reverse}\;(\mathit {reverse}\;xs) \equiv xs \end{equation*}
holds. In order to prove this property for any finite list |$\mathit {xs}$|, it is sufficient to show that (1) it holds when |$\mathit {xs}$| is the empty list [ ], and (2) if it holds for |$\mathit {xs}$|, then it also holds for x: xs—this is the induction step. (1) is easy to show, and (2) can be confirmed as follows:
\begin{eqnarray*} \begin{array}{l@{\quad}l} & \mathit {reverse}\; (\mathit {reverse}\; (x:xs)) \\ \equiv & \lbrace \mbox{def. of $\mathit {reverse}$ }\rbrace \\ & \mathit {reverse}\; (\mathit {reverse}\; xs \,{+\!\!+}\, [x]) \\ \equiv & \{ \mbox{ law: $\mathit {reverse}\; (xs \,{+\!\!+}\, ys) = \mathit {reverse}\; ys $} \\ & {+\!\!+}\, \mbox{$\mathit {reverse}\; xs$ }\} \\ & \mathit {reverse}\; [x] \,{+\!\!+}\, \mathit {reverse}\; \mathit {reverse}\; xs \\ \equiv & \lbrace\mbox{ def. of $\mathit {reverse}$ and inductive hypothesis }\rbrace\\ & (\mathit {reverse}\; [\,] \,{+\!\!+}\, [x]) \,{+\!\!+}\, xs\\ \equiv & \lbrace\mbox{ def. of $\mathit {reverse}$ and simplification }\rbrace \\ & x:xs \end{array} \end{eqnarray*}
Here, the law used in the above calculation can also be formally proven by induction.
Inductive proof is very commonly used in the functional setting as an effective way to verify critical software systems. The inductive proof of the inverse property of |$\mathit {reverse}$| has a strong resemblance to that of the inverse property of complex encoding and decoding in real practice [20]. More practical application examples include using the Coq proof assistant for proving the security properties of the JavaCard platform [21], certifying an optimizing compiler for C [18], and formally proving computational cryptography [22].
Property-based testing
Equational properties can also be used for testing functional programs. Using the QuickCheck test library [17], properties can be expressed via Haskell function definitions. For example, the property of |$\mathit {reverse}$| stated in the previous section can be written as
\begin{equation*} \begin{array}{llll}\mathit {propReverseReverse} \; ::\; [\mathit {Integer}] \rightarrow \mathit {Bool}\\ \mathit {propReverseReverse}\; \mathit {xs} =\\ \quad \mathit {reverse}\; (\mathit {reverse}\; \mathit {xs}) == \mathit {xs} \end{array} \end{equation*}
If the property holds, then the corresponding function should always return |$\mathit {True}$|, so QuickCheck generates a large number of random argument values and checks that the function returns |$\mathit {True}$| for each one (the type stated for the property is needed to tell QuickCheck what kind of test data to generate, namely lists of integers). QuickCheck defines a DSL, embedded in Haskell, for expressing properties in a testable subset of predicate calculus. Quantified variables, such as xs above, range over 'sets' which are represented by test data generators, with fine control over the distribution of the randomly generated data.
When a test fails, QuickCheck 'shrinks' the test case to a minimal failing example. If we test the following (wrong) property,
\begin{equation*} \begin{array}{llll}\mathit {propReverse} \; ::\; [\mathit {Integer}] \rightarrow \mathit {Bool}\\ \mathit {propReverse}\; \mathit {xs} = \mathit {reverse}\; \mathit {xs} == \mathit {xs} \end{array} \end{equation*}
then QuickCheck reports that [0, 1] (or, occasionally, [1, 0]) is a counterexample; the shrunk counterexample is obtained by searching for ways to simplify whatever randomly generated counterexample is first found. We obtain [0, 1] because at least two elements are needed to make this property fail, and they cannot be equal—so [0, 0] is not a counterexample. Shrinking is of critical importance to make property-based testing useful; without it, the 'signal' that causes a test to fail is drowned in the 'noise' of randomly generated data, and debugging failures is far more difficult.
Interestingly, this kind of testing finesses Dijkstra's famous objection that testing can never demonstrate the absence of bugs in software, only their presence. If we test properties that completely specify a function—such as the four properties of |$\mathit {reverse}$| stated in the introduction—and if every possible argument is generated with a non-zero probability, then property-based testing will eventually find every possible bug. In practice this isn't true, since we usually do not have a complete specification, and we limit the size of generated tests, but in principle we can find any possible bug this way—and in practice, this approach to testing can be very effective, since generated tests can explore scenarios that no human tester would think to try.
QuickCheck is heavily used in the Haskell community—it is the most heavily used testing package, and the |$10{\mathit {{\rm th}}}$| most used package of any kind, in the Hackage Haskell package database. The core of xmonad, discussed above, is thoroughly tested by simple equational properties on the state of the window manager, just like those we have discussed. The basic idea has been ported to many other programming languages—FsCheck for F#, ScalaCheck for Scala, test.check for Clojure, but even non-functional languages like Go and Java. There is even a commercial version in Erlang, marketed by Quviq AB, which adds libraries for defining state machine models of effectful software [23]. This version has been used to find bugs in an Ericsson Media Proxy [24], to track down notorious race conditions in the database software supplied with Erlang [25], and to formalize the basic software part of the AutoSAR automotive standard, for use in acceptance testing of vendors' code for Volvo Cars [26]. In this last project, 3000 pages of standards documents were formalized as 20 000 lines of QuickCheck models, and used to find more than 200 different defects—many of them defects in the standard itself. A comparison with conventional test suites showed that the QuickCheck code was almost an order of magnitude smaller—despite testing more!
Automatic optimization
The ability to replace expressions with their equals and be oblivious to the execution order is a huge advantage in program 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. For instance, we could give GHC the inverse property of |$\mathit {reverse}$| to eliminate unnecessary double reversals of lists, and GHC will then apply the rule whenever it can. (While it is unlikely that a programmer would write a double reversal explicitly, it could well arise during optimization as a result of inlining other function calls.)
{-# RULES
''reverse-inv'' forall xs.
reverse (reverse xs) = xs
#-}
In practice, people make use of this utility for serious optimizations. For example, shortcut fusion [27,28] is used to remove unnecessary intermediate data structures, and tupling transformation [29] is used to reduce multiple traversals of data.
HERMIT [30] is a powerful toolkit for developing new optimizations by enabling systematic equational reasoning inside the GHC's optimization pipeline. It provides a transformation API that can be used to build higher level rewrite tools.
Functional forms
Higher order functions are not only useful for expressing programs, they can be helpful in reasoning and proofs as well. By associating general algebraic (equational) laws with higher order functions, we can automatically infer properties from these laws when the higher order functions are applied to produce specific programs.
Two of the most important higher order functions are fold and unfold (also known as catamorphism and anamorphism). They capture two natural patterns of computation over recursive datatypes such as lists and trees: unfolds generate data structures and folds consume them. Here, 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. In this review, we focus on fold and unfold on lists. In fact, a single generic definition of fold can be given for all (algebraic) datatypes [31– 33], and dually for unfold.
Algebraic datatypes
We have seen an example of an algebraic datatype, namely List, earlier on in the reverse example. List is the most commonly used datatype in functional programming—to such an extent that the first functional language was named Lisp [11], as in 'LISt Processing'. A list whose elements have the type α can be constructed by starting with the empty list |$\mathit {Nil}$|, and successively adding elements of type α to the list, one by one, using the data constructor |$\mathit {Cons}$|.
\begin{equation*} \mathbf {data}\; \mathit {List}\; \alpha \; =\; \mathit {Nil} \; |\; \mathit {Cons}\; \alpha \; (\mathit {List}\; \alpha ) \end{equation*}
For instance, the list [1, 2, 3, 4], of type |$\mathit {List}\; \mathit {Int}$|, is represented as follows:
\begin{eqnarray*} as = \mathit {Cons}\; 1\; (\mathit {Cons}\; 2\; (\mathit {Cons}\; 3\; (\mathit {Cons}\; 4\; \mathit {Nil}))) \end{eqnarray*}
The notations [ ] and infix : that we used above are simply shorthand for applications of |$\mathit {Nil}$| and |$\mathit {Cons}$|—|$\mathit {Cons}\; x\; xs$| can be written as x : xs. We will also use the 'section notation' (surrounding an operator by parentheses) to turn a binary infix operator ⊕ into a prefix function: (⊕) a b = (a⊕) b = (⊕b) a =a ⊕ b.
Fold
Foldr, which consumes a list and produces a value as its result, is defined as follows:
\begin{eqnarray*} \begin{array}{llll}\mathit {foldr}\; f\; e\; \mathit {Nil} &=& e\\ \mathit {foldr}\; f\; e\; (\mathit {Cons}\; x\; xs) &=& f\; x\; (\mathit {foldr}\; f\; e\; xs) \end{array} \end{eqnarray*}
The effect of |$\,\mathit {foldr}\; f\; e\; \mathit {xs}$| is to take a list xs, and return the result of replacing |$\mathit {Nil}$| by e and each |$\mathit {Cons}$| by f. For example, |$\mathit {foldr}\; f\; e\; \mathit {as}$| converts the above list as to the value of
\begin{equation*} f\; 1\; (f\; 2\; (f\; 3\; (f\; 4\; e))) \end{equation*}
This structurally inductive computation pattern captured by |$\mathit {foldr}$| is reusable; by choosing different fs and es, |$\mathit {foldr}$| can perform a variety of interesting functions on lists. To take a few examples, |$\mathit {sum}$| sums up all elements of a list, |$\mathit {prod}$| multiples all elements of a list, |$\mathit {maxlist}$| returns the maximum element of a list, |$\mathit {reverse}$| reverses a list , |$\mathit {map}\; f$| applies function f to every element of a list, and |$\mathit {inits}$| computes all initial prefix lists of a list. In the definitions below, we use partial applications of foldr: defining sum as |$\mathit {foldr}\; (+)\; 0$| (with two arguments rather than three) is the same as defining sum xs to be |$\mathit {foldr}\; (+)\; 0\; \mathit {xs}$|.
\begin{eqnarray*} \begin{array}{llll}\mathit {sum} &=& \mathit {foldr}\; (+)\; 0\\ \mathit {prod} &=& \mathit {foldr}\; (\times )\; 1\\ \mathit {maxlist} &=& \mathit {foldr}\; \mathit {max}\; (-\infty )\\ \mathit {reverse} &=& \mathit {foldr}\; \mathit {f}\; [\,]\; \mathbf {where}\; f\; a\; r = r \,{+\!\!+}\, [a]\\ \mathit {map}\; g &=& \mathit {foldr}\; f\; [\,]\; \mathbf {where}\; f\; a\; r = g\; a : r\\ \mathit {inits} &=& \mathit {foldr}\; f\; [[\,]]\; \mathbf {where}\; f\; a\; r = [\,] :\\ && \mathit {map}\; (a:)\; r\\ \end{array} \end{eqnarray*}
Unfold
Unfoldr is the dual of foldr, which generates a list from a 'seed'. It is defined as follows:
\begin{eqnarray*} \begin{array}{llll}\mathit {unfoldr}\; p\; f\; g\; \mathit {seed} = \\ \qquad \mathbf {if}\; p\; \mathit {seed}\; \mathbf {then}\; [\,]\\ \qquad \mathbf {else}\; (f\; \mathit {seed}) : \mathit {unfoldr}\; p\; f\; g\; (g\; \mathit {seed}) \end{array} \end{eqnarray*}
The functional form |$\mathit {unfoldr}$| takes a predicate p indicating when the seed should unfold to the empty list. When the condition fails to hold, then function f is used to produce a new list element as the head, and g is used to produce a new seed from which the tail of the new list will unfold. Like |$\mathit {foldr}$|, |$\mathit {unfoldr}$| can be used to define various functions on lists. For example, we can define the function |$\mathit {downfrom}\; n$| to generate a list of numbers from n down to 1:
\begin{equation*} \begin{array}{llll}\mathit {downfrom}\; n = \mathit {unfoldr}\; \mathit {isZero}\; f\; g\; n\\ \quad \mathbf {where}\\ \qquad \begin{array}{llll}\mathit {isZero}\; n \; =\; n==0\\ f\; n \; =\; n\\ g\; n \; =\; n-1 \end{array}\end{array} \end{equation*}
Composition of functional forms
Foldr and unfoldr can be composed to produce clear definitions of computations, which we think of as specifications in this section, because of their declarative nature. For example, the following gives a clear specification for computing the maximum of all summations of all initial segments of a list:
\begin{equation*} \mathit {mis} = \mathit {maxlist}\; \circ \; (\mathit {map}\; \mathit {sum}) \circ \mathit {inits} \end{equation*}
It is defined as a composition of four functions we defined as foldrs before.
Given the duality of unfold and fold (one generating data structures and the other consuming them), compositions of an unfold followed by a fold form very interesting patterns, known as hylomorphisms [32,34,35]. A simple example of a hylomorphism is the factorial function:
\begin{equation*} \begin{array}{llll}\mathit {factorial}\; n = \mathit{prod}\; (\mathit{down}\, \mathit{from}\; n) \end{array} \end{equation*}
where |$\mathit {prod}$| is defined using |$\mathit {foldr}$| and |$\mathit {downfrom}$| using |$\mathit {unfoldr}$|.
General laws
Functional forms enjoy many nice laws and properties that can be used to prove properties of programs that are in those forms. Fold has, among others, the following three important properties [32].
First, foldr has the following uniqueness property:
\begin{eqnarray*} \mathit {foldr}\; f_1\; e_1 \equiv \mathit {foldr}\; f_2\; e_2 \; \Leftrightarrow \; f_1 \equiv f_2 \wedge e_1 \equiv e_2 \end{eqnarray*}
which means that two foldrs are equivalent (extensionally), if and only if their corresponding components are equivalent. It serves as the basis for constructing other equational rules.
Second, 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.
\begin{equation*} \frac{h\; (f\; a\; r) \equiv f^{\prime }\; a\; (h\; r)}{h \circ \mathit {foldr}\; f\; e \equiv \mathit {foldr}\; f^{\prime }\; (h\; e)} \end{equation*}
Third, multiple traversals of the same list by different foldrs can be tupled into a single foldr, and thus a single traversal.
\begin{eqnarray*} \frac{h\; x = (\mathit {foldr}\; f_1\; e_1\; x,\; \mathit {foldr}\; f_2\; e_2\; x)}{ \begin{array}{llll}h = \mathit {foldr}\; f\; (e_1,e_2)\; \\ \quad \mathbf {where}\; f\; a\; (r_1,r_2) = (f_1\; a\; r_1, f_2\; a\; r_2) \end{array}} \end{eqnarray*}
Let us use a simple example to demonstrate how fusion is useful in the derivation of efficient programs. Assume that we have an implementation of insertion sort (into descending order) using foldr:
\begin{equation*} \begin{array}{llll}\mathit {sort} = \mathit {foldr}\; \mathit {insert}\; [\,]\\ \quad \mathbf {where}\\ \quad \mathit {insert}\; a\; [\,] = [a]\\ \quad \mathit {insert}\; a\; (b:x) = \mathbf {if}\; a \ge b\; \mathbf {then}\;\\ \quad a:b:x\; \mathbf {else}\; b:\mathit {insert}\; a\; x \end{array} \end{equation*}
Now suppose that we want to compute the maximum element of a list. This is easy to do using the existing sorting program:
\begin{equation*} \begin{array}{llll}\mathit {maxList} = \mathit {hd} \circ \mathit {sort}\\ \end{array} \end{equation*}
where |$\mathit {hd}$| is a function to select the first element from a non-empty list (|$\mathit {hd}\; (a:x) = a$|) and return −∞ if the list is empty. Though declarative and obviously correct, this program is inefficient. It is overkill to sort the whole list, just to get the head. Fusion, using the laws above, provides a standard way to solve this problem. The laws tell us that if we can calculate |$\mathit {f^{\prime }}$| such that
\begin{equation*} \forall a,x.\; \mathit {hd}\; (\mathit {insert}\; a\; x) \equiv f^{\prime }\; a\; (\mathit {hd}\; x) \end{equation*}
then we can transform |$\mathit {hd} \circ \mathit {sort}$| to |$\mathit {foldr}\; f^{\prime }\; (-\infty )$|. By instantiating x as b : y and performing a simple calculation, we obtain f ′ as follows:
\begin{equation*} \begin{array}{llll}f^{\prime }\; a\; b &\equiv & \mathit {hd}\; (\mathit {insert}\; a\; (b:y))\\ &\equiv & \mathbf {if}\; a \ge b\; \mathbf {then}\; a\; \mathbf {else}\; b\\ \end{array} \end{equation*}
Thus, we have derived a definition of |$\mathit {maxList}$| using a single foldr, which is exactly the same as the definition in the section entitled 'Fold' above. This fusion improves the time complexity of maxList from quadratic in the length of the list to linear.
As we have seen, equational reasoning and higher order functions (functional forms) enjoy a symbiotic relationship: each makes the other much more attractive.
Types
What is the type of a function like |$\mathit {foldr}$|? In the examples above, we have already seen it used with several different types! Its arguments are a function that combines a list element with an accumulator, an initial value for the accumulator, and a list of elements to be combined—but those list elements may be integers, lists themselves, or indeed any type; the accumulator can likewise be of any type. Being able to reuse higher order functions like |$\mathit {map}$| and |$\mathit {foldr}$| for different types of data is a part of what makes them so useful: it is an essential feature of functional programming languages. Because of this, early functional languages did without a static type checker; they were dynamically typed, but the compiler did not attempt to discover type errors. Some, like Erlang or Clojure, still are.
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. For example, the type of |$\mathit {foldr}$| is
\begin{eqnarray*} \mathit {foldr}\; ::\; (\alpha \rightarrow \beta \rightarrow \beta ) \rightarrow \beta \rightarrow \mathit {List}\; \alpha \rightarrow \beta \end{eqnarray*}
where α is the type of the list elements, and β is the type of the accumulator. When |$\mathit {foldr}$| was used to define |$\mathit {sum}$| above, then it was used with the type
\begin{eqnarray*} \begin{array}{c}\mathit {foldr}\; ::\; (\mathit {Integer} \rightarrow \mathit {Integer} \rightarrow \mathit {Integer}) \rightarrow \\ \quad \quad \quad \mathit {Integer} \rightarrow \mathit {List}\; \mathit {Integer} \rightarrow \mathit {Integer} \end{array} \end{eqnarray*}
(in which α and β are both instantiated to |$\mathit {Integer}$|); when it was used to define |$\mathit {sort}$| then its type was
\begin{eqnarray*} \mathit {foldr}\; ::\; (\gamma \rightarrow \mathit {List}\; \gamma \rightarrow \mathit {List}\; \gamma ) \\ \rightarrow \mathit {List}\; \gamma \rightarrow \mathit {List}\; \gamma \rightarrow \mathit {List}\; \gamma \end{eqnarray*}
(in which α is replaced by γ, the elements in the list to be sorted and β the accumulator type is a list of these). This allowed the flexibility of polymorphism to be combined with the security of static type checking for the first time. ML also supported type inference: the type of |$\mathit {foldr}$| (and indeed, every other function) could be inferred by the compiler from its definition, freeing the programmer from the need to write types in function definitions at all so ML was as concise and powerful as the untyped languages of its day, with the added benefit of static type checking.
Both these ideas have made a tremendous impact. Many functional programming languages since, Haskell among them, have borrowed the same approach to polymorphic typing that ML pioneered. Java generics, introduced in Java 5, were based directly on Odersky and Wadler's adaption of Milner's ideas to Java [36]; similar features appeared thereafter in C#. Type inference (in a more limited form) appeared in C# 3.0 in 2007, and type inference is increasingly available in Java too.
In fact, ML's polymorphic types also give us surprisingly useful semantic information about the functions they describe. For example, the reverse function can be applied to lists with any type of element, and so has the polymorphic type
\begin{equation*} {reverse}\; ::\; {List}\; \alpha \rightarrow {List}\; \alpha \end{equation*}
This implies that it also satisfies
\begin{eqnarray*} \forall {f},{xs}.\; {map}\; f\; ({reverse}\; {xs}) = {reverse}\; ({map}\; f\; {xs}) \end{eqnarray*}
as, indeed, does any other function with the same polymorphic type! These 'free theorems', discovered by Wadler [37], are an application of Reynold's parametricity[38]; they are used, among other places, to justify the 'short cut deforestation' optimization in the GHC [27].
Type classes for overloading
Haskell's major innovation, as far as types are concerned, was its treatment of overloading. (Over the years, many innovations have been made in Haskell's type system; here we refer to innovations in the early versions of the language.) For example, the equality operator is overloaded in Haskell, allowing programmers to use different equality tests for different types of data. This is achieved by declaring an equality type class:
\begin{equation*} \begin{array}{llll}\mathbf {class}\; \mathit {Eq}\; \alpha \; \mathbf {where}\\ \qquad (==) :: \alpha \rightarrow \alpha \rightarrow \mathit {Bool} \end{array} \end{equation*}
which declares that the equality operator (==) can be applied to any type α with an instance of the class |$\mathit {Eq}$|; programmers can define instances of each class, and the compiler infers automatically which instance should be used.
Right from the start, Haskell allowed instances to depend on other instances. For example, (structural) equality on lists uses equality on the list elements, expressed in Haskell by defining
\begin{equation*} \begin{array}{llll}\mathbf {instance}\; \mathit {Eq}\; \alpha \Rightarrow \mathit {Eq}\; ({\mathit{List}}\; \alpha )\; \mathbf {where}\\ \qquad xs == ys = \ldots \end{array} \end{equation*}
That is, given an equality on type α, the compiler can construct an equality on type |$\mathit {List}\; \alpha$|, using the definition of == in the instance. Or to put it another way, the compiler can reduce a goal to find an |$\mathit {Eq}\; (\mathit {List}\; \alpha )$| instance, to a goal to find an |$\mathit {Eq}\; \alpha$| instance, for any α. This looks a lot like logic programming! Over the years, Haskell class and instance declarations have become more and more powerful, incorporating aspects of both logic programming and functional programming, with the result that the type checker is now Turing-complete (Robert Dockins, The GHC typechecker is Turing-complete, https://mail.haskell.org/pipermail/haskell/2006-August/018355.html). The important observation here is that Haskell's class system gives us a programmable type checker, which—while it does not allow us to accept programs that will generate runtime-type errors—does allow us to construct type systems for DSLs embedded in Haskell with exquisite precision. Scala's implicits were directly inspired by Haskell's type classes, and allow many of the same tricks to be played [39].
Types and logic
Finally, there is a deep connection between types and logic. Just consider the type of the apply function:
\begin{equation*} {apply}\; ::\; (\alpha \rightarrow \beta , \alpha )\rightarrow \beta \end{equation*}
If we read function arrow types as logical implications, and the pair type as a conjunction, then this type reads as the (true) proposition
\begin{equation*} ((A \Rightarrow B) \wedge A) \Rightarrow B \end{equation*}
It turns out that this is not a coincidence: we can soundly regard apply as a proof of this property, and 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 [40] and Agda [41] 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. For example, if the List type is parameterized not only on the element type, but also on the length of the list, then reverse can be given a more informative type:
\begin{eqnarray*} {reverse}\; ::\; \forall k::{Nat}, \alpha ::{Set}.\; {List}\; k\; \alpha \rightarrow {List}\; k\; \alpha \end{eqnarray*}
representing the fact that its result has the same length as its argument. (Here Set is roughly speaking 'the type of types', or more precisely, the type of small types, i.e. excluding types such as Set itself.) Predicates can then be represented by types that are sometimes empty. For example, Even k might be a type that is empty if k is odd, and non-empty if k is even—so constructing a term of type Even k proves that k is even. Using these ideas, it is possible to construct large functional programs with formal proofs of correctness. Perhaps the most impressive example to date is CompCert [18], already discussed above.
Algebra of programming
In the section entitled 'Functional forms', we have seen a useful set of functional forms that capture common computation patterns while enjoying general algebraic laws for program reasoning. This attractive idea can be carried much further, leading to the development of many specific theorems as building blocks for more complex reasoning. The result is the algebra of programming [42,43], where functional programming provides an algebraic framework for building programming theories for solving various computational problems by program calculation (derivation)—a systematic way of transforming specification into efficient implementation through equational reasoning. This supports, in practice, Dijsktra's argument that programming should be considered as a discipline of a mathematical nature [44].
In this section, we review the programming theories that have been developed for constructing programs from specifications, and demonstrate how these theories can be used to derive programs in various forms for efficient sequential or parallel computation.
Programming: deriving programs from specifications
Before addressing the solution of programming problems, consider the following mathematical problem known as the Chinese Chicken–Rabbit-Cage Problem:
An unknown number of rabbits and chickens are locked in a cage. Counting from above, we see there are 35 heads, and counting from below, there are 94 feet. How many rabbits and chickens are in the cage?
The degree of difficulty of this problem largely depends on which mathematical tools one has to hand. A preschool child may find it very difficult; he has no choice but to enumerate all possibilities. However, a middle school student equipped with knowledge of equation solving should find it easy. He would let x be the number of chickens and y that of rabbits, and quickly set up the following problem specification:
\begin{equation*} \begin{array}{llll}x + y &=& 35\\ 2x + 4y &=& 94\mbox{} \end{array} \end{equation*}
The rest is entirely straightforward. The theory of linear equations gives us a strategy for solving them systematically, to discover the values of the unknowns (i.e., x = 23, y = 12).
We want to solve our programming problems this way too! 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. Here, by 'specification', we mean two things: (1) a naive functional program that expresses a straightforward solution whose correctness is obvious; and (2) a program in a specific form of composition of functional forms. By 'program', we mean an efficient functional program, which may be sequential, parallel, or distributed.
Programming theories
Just like the specific laws developed for factorization in solving equations, many laws (theorems) for deriving efficient functional programs from specifications have been developed [43,45]. They are used to capture programming principles by bridging the gap between specifications and their implementing programs. As an example, many optimization problems can be naively specified in a generate-and-test way: generating all the possibilities, keeping those that satisfy the requirements, and returning one that maximizes a certain value:
\begin{eqnarray*} \mathit{opt} = \mathit {maxlist} \circ \mathit {map}\; \mathit {value} \circ \mathit {filter}\; p \circ \mathit {gen} \end{eqnarray*}
To solve this kind of optimization problems using folds, many theorems [43,46] have been developed. One example is: if (1) gen, p, and value can be defined as foldrs, and (2) |$\mathit {value} = \mathit {foldr}\; (\oplus )\; e$|, where ⊕ is associative and |$\mathit {max}$| is distributive over ⊕, then opt can be solved in linear time by a functional program in terms of a single foldr. With this theorem, solving optimization problems become easy: one just needs to specify the problem in the form described and the rest will follow!
Programming theory development
Many theories for the algebra of programming have been developed—but new ones can always be added. There is a general procedure to develop programming theories consisting of the following three major steps [47,48].
-
Define a specific form of programs, in terms of functional forms and their composition, that can be used to describe a class of interesting computations.
-
Develop calculational rules (theorems) to bridge the gap between the new specific form and the existing functional forms.
-
Develop more theorems that can turn more general programs into the specific form to widen the application scope.
The first step plays a very important role in this development. The specific form defined should not only be powerful enough to describe computations of interest, but also manipulable and suitable for the later development of calculational laws.
Systems for program derivation
Many systems have been developed for supporting program derivation and calculation. Examples are KIDS [49], MAG [50], Yicho [47], and so on. In general, such tools (1) support interactive development of programs by equational reasoning so that users can focus on their creative steps, (2) guarantee correctness of the derived program by automatically verifying each calculation step, (3) support development of new calculation rules so that mechanical derivation steps can be easily grouped, and (4) make the development process easy to maintain (i.e. the development process should be well documented).
Proof assistants and theorem provers can provide a cheap way to implement a system for program reasoning and program calculation [51–53]. For instance, with Coq [40], a popular theorem prover, one can use Ltac, a language for programming new tactics, to build a program calculation system [53]: (1) Coq tactics can be used effectively for automatic proving and automatic rewriting, so that tedious calculation can be hidden with tactics; (2) new tactics can coexist with the existing tactics, and a lot of useful theories of Coq are ready to use for calculation, and (3) tactics can be used in a trial-and-error manner thanks to Coq's interaction mechanism.
In contrast to deriving functional programs from formal specifications, MagicHaskeller [54,55] is an interesting tool that automatically synthesizes functional programs from input/output examples. Although still under development, it has demonstrated the feasibility of the idea by synthesizing many interesting Haskell programs from just a small number of examples.
STRUCTURING COMPUTATION
In the previous section, we have experienced the liberating power of the absence of side effects. Referential transparency is the basis of the wealth of properties that enabled us to reason, to test, to optimize, and ultimately to derive programs. On the other hand, functional programmers are by no means ascetics withdrawing from worldly pleasures. Functional programs are real programs! They do perform necessary computations with side effects such as I/Os, exceptions, non-determinism, etc.
The difference is simply a shift of perspective. Functional programmers view side effects as costly, which shall be used with care, and at the best avoided. Let us suppose that we have to pay for each pair of parentheses in a game of writing arithmetic expressions. Associativity, which removes the need of parenthesizing, becomes very valuable and players will be incentivized to write 3 × 0.5 × 5 instead of (3÷2) × 5 for example. Programming is like such writing of expressions, and the role of a programming language is to encourage good practice and at the same time discourage the opposite.
Pure functional languages do just that: side effects are encoded by a programming pattern known as monads [56–59]. Since it is an encoding, purity is not threatened. But monads do enjoy a clearly distinguished syntax and type to encourage thoughtful design. We will see later in this section in more details the idea of monadic effects, and the benefit of being disciplined with the uses of them. As a matter of fact, the concept of monads as a programming pattern has applications far beyond handling side effects; it is fundamentally a powerful way of structuring computations and has been adopted in languages with built-in side effects! To name a few, some readers may have heard of async monad in F#, promises in JavaScript, or future in Scala, which are essentially imitations of a monad used to structuring asynchronous operations. On a different front, Language INtegrated Query (LINQ) in .NET is directly inspired by monads, and a syntax sugar for them known as monad comprehension (following from set comprehension) in Haskell.
In the sequel of this section, we will briefly review monads and demonstrate their uses in structuring computations, in the context of programming language development, which is itself a particularly successful application of functional programming.
Monadic composition
Originally as a concept in category theory that was used by Moggi to modularize the structure of a denotational semantics [56,57], monads are soon applied by Wadler to the functional implementations of the semantics that Moggi describes, and as a general technique for structuring programs [58,59].
A monad |$\mathit {M}$| consists of a pair of functions |$\mathit {return}$| and |$\mathit {(\gg =)}$| (pronounced as 'bind').
\begin{eqnarray*} \begin{array}{llll}\mathit {return} &::& \alpha \rightarrow M\; \alpha \\ (\gg =) &::& M\; \alpha \rightarrow (\alpha \rightarrow M\; \beta ) \rightarrow M\; \beta \end{array} \end{eqnarray*}
One shall read M α the type of a computation that returns a value of type α, and perhaps performs some side effects. An analogy is to see a value of type M α as a bank card and its pin; they are not the same as plain cash a (of type α) which can be used immediately, but contain the instruction of producing an a, and in fact any number of as.
We cannot use a value of type M α directly, but we can combine it with other instructions that use the result. For example, consider an evaluator of type |$\mathit {Term} \rightarrow \mathit {Environment} \rightarrow M\; Value,$| where M is a monad. The evaluator does not give us a value directly, but we can bind its result to be used in subsequent computations:
\begin{equation*} \begin{array}{llll}\mathit {eval}\; u\; e \gg = (\lambda a \rightarrow \\ \mathit {eval}\; v\; e \gg = \lambda b \rightarrow \\ \mathit {return}\; (\mathit {Num}\; (a + b)) \end{array} \end{equation*}
This expression evaluates the two operands of an addition and add them up. The result of the first evaluation is bound to the variable |$\mathit {a}$| and is passed to the second evaluation, and together with the second result (bound to |$\mathit {b}$|) they form parts of a new value which is again encapsulated in the monad by |$\mathit {return}$|. This pattern of structuring computation is very common and has been giving special syntax support in Haskell [58]. The above expression can be rewritten as the following equivalent form:
\begin{equation*} \begin{array}{llll}\mathbf {do} & a \leftarrow \mathit {eval}\; u\; e \\ & b \leftarrow \mathit {eval}\; v\; e \\ & \mathit {return}\; (\mathit {Num}\; (a + b)) \end{array} \end{equation*}
which is seemingly similar to the following expression:
\begin{equation*} \begin{array}{llll}\mathbf {let} \; a = \mathit {eval}\; u\; e\\ \phantom{\mathbf {let} \; } b = \mathit {eval}\; v\; e\\ \mathbf {in}\; \mathit {Num}\; (a+b) \end{array} \end{equation*}
Now, let us say we want to extend the evaluator with error handling as in
\begin{eqnarray*} \begin{array}{llll}\mathit {eval} :: \mathit {Term} \rightarrow \mathit {Environment} \rightarrow \mathit {Maybe}\; \mathit {Value}\\ \\ \mathbf {data}\; \mathit {Maybe}\; a = \mathit {Just}\; a \; |\; \mathit {Nothing} \end{array} \end{eqnarray*}
where failures are represented by |$\mathit {Nothing}$| and successful computations return values wrapped in |$\mathit {Just}$|. Without giving up on purity and resorting to a language with side effects, the non-monadic definitions which structure computations with let have to be tediously rewritten: every let binding now has to be made to perform a case analysis, separating successes from failures, and then decides the next step accordingly.
Whereas for the monadic version, the story is rather different. The structure of the evaluator is independent of the underlying computation that is used, and if carefully designed changing one entails minimum changes to the other. In the above, the specializing of monad type M to |$\mathit {Maybe}$| links the right instances of |$\mathit {return}$| and ≫= (in fact monads forms a type class).
\begin{equation*} \begin{array}{llll}\mathbf {instance}\; \mathit {Monad}\; \mathit {Maybe}\; \mathbf {where}\\ \quad \begin{array}{llll}\mathit {return}\; x &=& \mathit {Just}\; x \\ \mathit {Nothing} \gg = f &=& \mathit {Nothing} \\ \mathit {Just}\; x \gg = f &=& f\; x \end{array}\end{array} \end{equation*}
There is no change in the evaluator's definition, as the handling of failure is captured as a pattern and localized in the definition of ≫=. In a similar manner, we can add to the evaluator real-world necessities such as I/Os, states or non-determinism in a similar manner—simply replacing the underlying monad.
Monads not only encapsulate side effects, but also make them first class. For example, the function |$\mathit {sequence :: [m\; \alpha ]} \rightarrow \mathit {m\; [\alpha ]}$|, where |$\mathit {m}$| is a monad, evaluates each computation in turn, and collects the results. In the evaluator example, one may rewrite the expression for addition as
\begin{equation*} \mathit {liftM}\; \mathit {sum}\; (\mathit {sequence}\; [\mathit {eval}\; u\; e, \mathit {eval}\; v\; e]) \end{equation*}
where |$\mathit {sum}$| adds up a list of numbers and is lifted (by |$\mathit {liftM}$|) to handle monadic values.
In addition to structuring programming languages semantics, monads also offer a nice framework for I/Os in a pure language. The idea is to view I/O operations as computations interacting with the 'outside world' before returning a value: the outside world is the state, which (represented by a dummy 'token') is passed on to ensure proper sequencing of I/O actions [60]. For example, a simple Read-Eval-Print Loop that reverses the command line input can be written with recursion as a function of type |$\mathit {IO}\; ()$|, where |$\mathit {IO}$| is the monad and |$\mathit {()}$| is a singleton type with |$\mathit {()}$| as its only value.
\begin{equation*} \begin{array}{llll}\mathit {repl} :: \mathit {IO}\; ()\\ repl = \mathbf {do}\\ \qquad \qquad \mathit {line} \leftarrow \mathit {getLine}\\ \qquad \qquad \mathit {putStrLn}\; (\mathit {reverse}\; \mathit {line}) \\ \qquad \qquad \mathit {repl} \end{array} \end{equation*}
Giving the stateful implementation of the |$\mathit {IO}$| monad, it is obvious that it could be used to support mutable states and arrays [60], though a different approach based on normal state monad, which encapsulates effectful computations inside pure functions, may be considered better [61,62].
Further extensions of the IO include the handling of concurrency [63]. The implementation of software transactional memory (STM) with monads [64] is a clear demonstration of the benefit of carefully managed side effects; two monads are used in the implementation: the |$\mathit {STM}$| monad structures tentative memory transactions, the |$\mathit {IO}$| monad commits the STM actions exposing their effects to other transactions, and a function |$\mathit {atomic}$| connects the two:
\begin{equation*} \mathit {atomic} :: \mathit {STM}\; \alpha \rightarrow \mathit {IO}\; \alpha \end{equation*}
As a result of this explicit distinction of different type of effects made possible by monads, only STM actions and pure computations can be performed inside a memory transaction ruling out irrevocable actions by construction, and no STM actions can be performed outside a transaction effectively eliminating a class of bugs altogether. Moreover, since reads from and writes to mutable cells are explicit as STM actions, the large number of other (guaranteed pure) computations in a transaction are not tracked by the STM, because they are pure, and never need to be rolled back. All these guarantees make a solution based on monads very attractive indeed.
Monads are often used in combination. For example, an evaluator may need to handle errors and at the same time performing I/O, and it will be desirable to reuse existing monads instead of creating specialized ones. The traditional way of achieving such reuse is through moving up the abstraction level to build monad transformers [65,66], which are similar to regular monads, but instead of standing alone they modify the behaviours of underlying monads, effectively allowing different monads to stack up. The downside of monad transformers is that they are difficult to understand and are fragile to changes. Alternatives have been proposed and it is still an active area of research [67–69].
Inspired by monads, other abstract views of computation have emerged, notably arrows [70,71] and applicative functors [72]. First proposed by Hughes [70], arrows are more general than monads allowing notions of computation that may be partially static (independent of the input) or may take multiple inputs. Applicative functors are a proper superset of monads, which has weaker properties and thus more members. Similar to monads, both arrows and applicative functors can be used for structuring the semantics of embedded domain-specific languages (EDSLs) [73,74]. A theoretical comparison of the three can be found in [75].
Embedded domain-specific languages
So far, we have only discussed one way of developing languages that is to implement stand-alone compilers or interpreters. Functional programming is well suited for the task and the use of monad has significant impact on modularity. However, the particular success of functional programming actually comes from another way of language development known as embedding [76,77].
Languages produced through embedding are known as embedded languages, which are libraries in host languages. Giving that such libraries usually focus on providing functionalities of a specific problem domain, the languages resulting from are seen as EDSLs, while the host languages are usually general purpose. The EDSL and its host language are one: the API of the library specifies a set of constructs of the new DSL, which at the same time shares the tool chain and the generic features of the host language, such as modules, interfaces, abstract data types, or higher order functions. Moreover, the EDSL implementation is very 'lightweight'—the EDSL designer can add features just by implementing a new function in the library, and can easily move functionality between the EDSL library and its clients. The ease of experimentation with such an EDSL helps implementors fine-tune the design, and enables (some) end users to customize the implementation with domain-specific optimizations.
Such EDSLs have appeared in a wide spectrum of application areas, including compiler development, database queries, web applications, GUIs, music, animations, parallelism, hardware descriptions, image processing, workflow, and more. See Fig.1 for a few examples and [78] for a comprehensive listing.
We have said that EDSLs are libraries. But obviously not all libraries are languages. So what is it that elevates EDSLs from their humble origin as libraries to the level of languages?
For a language to be worth its name, it must allow code fragments manipulating primitive data to be shared through defining reusable procedures. In an EDSL setting, the data (also known as the domain concepts) are themselves functions. For example, in modelling 3D animation, the domain concept of behaviour, representing time-varying reactive values, is a function from time to a 'normal' value. To have a language, we need to provide constructs that manipulate such domain concepts. This is easy in functional languages: we can simply define higher order functions called combinators, taking domain concepts as inputs and combining them into more complex ones, just like what procedures do to primitive data. For this reason, EDSLs are also known as combinator libraries—libraries that not just offer domain-specific operations, but also more importantly combinators that manipulate them. We illustrate this idea by developing an example EDSL.
A classic example: parser combinators
Our aim is to develop a parsing EDSL for the following BNF grammar:
\begin{equation*} \begin{array}{llll}{\it float} ::= {\it sign}^?\; {\it digit}^+\; (^{\prime }.^{\prime }\; {\it digit}^+)^? \end{array} \end{equation*}
Like any language, an EDSL has syntax and semantics. In this embedded setting, the syntax is simply the interface of the library containing the representation of the domain concept, and the operations on it; and the semantics is the implementation of the operations in the host language.
A parser is a program that receives a piece of text as the input, analyses the structure of the text, and produces an output usually in the form of trees that can be more conveniently manipulated by other parts of a compiler. A parser can be represented as a function:
\begin{eqnarray*} \begin{array}{llll}\mathbf {newtype}\; \mathit {Parser}\; \alpha = \mathit {MkP}\; (\mathit {String} {\rightarrow} [(\alpha , \mathit {String})]) \end{array} \end{eqnarray*}
The type |$\mathit {Parser}$| is a new type, distinct but isomorphic to its underlying type of a function from strings to lists of parsing results, depending on how many ways the parse could succeed, or fail with an empty list. The parameterized type α is the tree produced by parsing, and is paired with the remaining unparsed string. In DSL terminology, |$\mathit {Parser}$| is the domain concept we are trying to model and as usual it has an underlying representation as a function.
Primitive Parsers: With a parser representation at hand, we can start building a library to manipulate it. To start with, we define some basic parsers.
\begin{equation*} \begin{array}{llll}\mathit {item} :: \mathit {Parser}\; \mathit {Char}\\ \mathit {item} = \mathit {MkP}\; f\\ \quad \mathbf {where}\\ \qquad \begin{array}{llll}f\; [\,] &=& [\,]\\ f\; (c:\mathit {cs}) &=& [(c,\mathit {cs})]\\ \end{array}\end{array} \end{equation*}
The parser |$\mathit {item}$| consumes a character of the input string and returns it. And a second parser is a parser that always fails.
\begin{equation*} \begin{array}{llll}\mathit {zero} :: \mathit {Parser}\; \alpha \\ \mathit {zero} = \mathit {MkP}\; f\; \mathbf {where}\; f\; \_ = [\,] \end{array} \end{equation*}
These two are the only basic parsers that we will ever need, and all the power of the resulting language comes from its combinators.
Parser Combinators: For the grammar we have in mind, our language consists of the following set of basic combinators:
\begin{eqnarray*} \begin{array}{llll}\mathit {sat} &::& (\mathit {Char} \rightarrow \mathit {Bool}) \rightarrow \mathit {Parser}\; \mathit {Char}\\ \mathit {plus} &::& \mathit {Parser}\; \alpha \rightarrow \mathit {Parser}\; \alpha \rightarrow \mathit {Parser}\; \alpha \\ \mathit {optional} &::& \mathit {Parser}\; \alpha \rightarrow \mathit {Parser}\; (\mathit {Maybe}\; \alpha ) \end{array} \end{eqnarray*}
In the above, |$\mathit {sat}$| enriches |$\mathit {item}$| with a predicate so that only characters satisfying the predicate will be parsed. By providing different predicates, it can be specialized to a number of different parsers:
\begin{equation*} \begin{array}{llll}\mathit {char}\; x = \mathit {sat}\; (==x)\\ \mathit {digit} = \mathit {sat} (\lambda x \rightarrow \mathit {^{\prime }0^{\prime }} \le x \wedge x \le \mathit {^{\prime }9^{\prime }}) \end{array} \end{equation*}
For example, |$\mathit {digit}$| succeeds with |$\mathit {`123{\hbox {'}}}$| and produces |$\mathit {[(`1{\hbox {'}},`23{\hbox {'}})]}$| as the outcome, but fails (returning |$\mathit {[\,]}$|) with |$\mathit {`A23{\hbox {'}}}$|. Similarly, |$\mathit {char}$| only recognizes the character that is passed to it as input and fails on all others.
Parser |$\mathit {plus\; p\; q}$| combines the outcomes of applying |$\mathit {p}$| and |$\mathit {q}$|. In the case when one of the two fails, the outcome will be the same as using the other one:
\begin{equation*} \begin{array}{llll}\mathit {sign} :: \mathit {Parser}\; \mathit {Char}\\ \mathit {sign} = (\mathit {char}\; \mathit {^{\prime }+^{\prime }})\; \mathit {`plus`}\; (\mathit {char}\; \mathit {^{\prime }-^{\prime }}) \end{array} \end{equation*}
In the above, the prefix function |$\mathit {plus}$| is turned into an infix one by the surrounding left single quotes.
The combinator |$\mathit {optional}$| corresponds to the (|$^?$|) notation in our grammar allowing an optional field to be parsed into |$\mathit {Nothing}$| when it is not filled. Note that here |$\mathit {Nothing}$| represents success in parsing, not failure which is represented by the empty list.
So far, what we have seen are combinators that are useful for constructing parsers recognizing individual components of a grammar. A crucial missing part is a way to sequence the individual components, so that individual parsers are chained together and applied in sequence. For example, our |$\mathit {float}$| grammar is a chain of sign, digits, and fraction parsers. In another words, we need a way to structure the parsing computation. Sounds familiar? Monads introduced in the previous subsection fit the bill very well.
Just like |$\mathit {Maybe}$|, |$\mathit {Parser}\; \alpha$| is a monad with its own bind and return:
\begin{eqnarray*} \begin{array}{llll}(\gg =) &::& \mathit {Parser}\; \alpha \rightarrow (\alpha \rightarrow \mathit {Parser}\; \beta ) {\rightarrow} \mathit {Parser}\; \beta \\ \mathit {return} &::& \alpha \rightarrow \mathit {Parser}\; \alpha \end{array} \end{eqnarray*}
Now we are ready to define combinators that repeatedly apply a parser:
\begin{equation*} \begin{array}{llll}\mathit {zeroOrMore} :: \mathit {Parser}\; \alpha \rightarrow \mathit {Parser}\; [\alpha ]\\ \mathit {zeroOrMore}\; p = \\ \quad \mathbf {do}\; \lbrace x \leftarrow p; \\ \phantom{\quad \mathbf {do}\; \lbrace } \mathit {xs} \leftarrow \mathit {zeroOrMore}\; p; \\ \phantom{\quad \mathbf {do}\; \lbrace } \mathit {return}\; (x:\mathit {xs}) \rbrace \\ \quad \mathit {`plus`}\; \mathit {return}\; [\,]\\ \\ \mathit {oneOrMore} :: \mathit {Parser}\; \alpha \rightarrow \mathit {Parser}\; [\alpha ]\\ \mathit {oneOrMore}\; p = \\ \quad \mathbf {do}\; x \leftarrow p \\ \phantom{\quad \mathbf {do}\; } \mathit {xs} \leftarrow \mathit {zeroOrMore}\; p \\ \phantom{\quad \mathbf {do}\; } \mathit {return}\; (x:\mathit {xs}) \end{array} \end{equation*}
Parser |$\mathit {zeroOrMore\; p}$| returns each application of |$\mathit {p}$| as a list. For example, applying |$\mathit {(zeroOrMore\; digit)}$| to |$^{\prime }\mathit {12a^{\prime }}$| results in |$\mathit {[(^{\prime }12^{\prime },^{\prime }a^{\prime }),(^{\prime }1^{\prime },^{\prime }2a^{\prime }),(^{\prime \prime },^{\prime }12a^{\prime })]}$|. Parser |$\mathit {oneOrMore\; p}$| is similar to |$\mathit {zeroOrMore\; p}$| except requiring p to apply at least once.
Just to show that the use of monad has not prevented us from doing the same kind of equational reasoning as before, we list a few arbitrarily selected laws as an example:
\begin{eqnarray*} \begin{array}{lcl}\mathit {zero}\; \gg =\; p &\equiv & \mathit {p}\\ \mathit {zero}\; \mathit {`plus`}\; p &\equiv & \mathit {p}\\ \mathit {p\; `plus`\; (q\; `plus`\; r)} &\equiv & \mathit {(p\; `plus`\; q)\; `plus`\; r}\\ \mathit {(p\; `plus`\; q)\; \gg =\; r} &\equiv & \mathit {(p \gg = r)\; `plus`\; (q \gg = r)} \end{array} \end{eqnarray*}
Finally, we can directly translate the BNF grammar at the beginning of this subsection to the following executable parser:
\begin{eqnarray*} \begin{array}{llll}\mathit {float} = \mathbf {do}\\ \quad \mathit {sgn} \leftarrow \mathit {optional}\; \mathit {sign}\\ \quad \mathit {in} \leftarrow \mathit {oneOrMore}\; \mathit {digit}\\ \quad \mathit {frac} \leftarrow \mathit {optional}\; (\mathbf {do}\; \lbrace char ^{\prime }.^{\prime }; \mathit {oneOrMore}\; \mathit {digit}\rbrace )\\ \quad \mathit {return}\; (\mathit {mkFloat}\; \mathit {sgn}\; \mathit {in}\; \mathit {frac}) \end{array} \end{eqnarray*}
We stop here and look at what we have learnt from this exercise. Readers interested in knowing more about parser combinators may start with Hutton and Meijer's tutorials [79,80] for more combinators and techniques for improving efficiency, and several more papers on the subject [81–85].
-
Combinators are the key. The parser library we have developed is a language. It is not so much about what specific operations are provided, but the unlimited possibilities through creative programming. As we can see, the very small number (two in our case) of basic parsers, which is typical in EDSLs, can be combined in different ways to produce highly complex programs. This power comes from the combinators which hinge on higher order functions.
-
Monads are very useful. The monadic sequential combination is an excellent formulation of a recurring pattern: a sequence of operations are performed in turn and have their results combined in the end. We have relied on it to program parsers that goes beyond simply consuming a single character.
When the semantics of the domain concepts is obvious, directly encoding the operations that can be performed on them often results in an elegant EDSL implementation. This is exactly what we did for the parser example: the set of combinators implements what we can do to parsers and the set is easily extensible by defining new combinators. On the other hand, adding new domain concepts usually requires a complete reimplementation. Moreover, with this direct approach, performance of the domain-specific programs relies on the optimization of the host language compiler, which is hard to predict and control.
An alternative embedding technique is to generate code from the EDSL programs: the domain concepts are represented as an abstract syntax tree, and a separate interpretation function provides the semantics of the syntax constructs, resulting in a so called embedded domain-specific compiler [86]. In this case, the host language is used only at 'compile time'; the EDSL programmer can use the full power of the host language to express the program, but at runtime, only the generated code needs be executed. This approach is sometimes referred as deep embedding in contrast to the above more direct shallow embedding. The separation of phases in deep embedding provides opportunities for domain-specific optimizations as part of the interpretation function and adding new domain concepts simply means additional interpretation functions. On the other hand, extending the set of operations involves modifying the abstract syntax and existing interpretation functions.
The two embedding approaches are dual in the sense that the former is extensible with regard to adding operations while the latter is extensible with regard to adding concepts [87]. The holy grail of embedded language implementation is to be able to combine the advantages of the two in a single implementation—a manifestation of the expression problem [88]. Current research addresses the problem at two levels: exploiting sufficiently expressive host languages for a modular representation of the abstract syntax tree [89–92], or combining the shallow and deep embedding techniques [93]. Notably in [91], the technique also addresses another source of inefficiency with embedded languages namely the tagging and untagging required for manipulating the abstract syntax trees represented as datatypes.
Lastly, the connection between EDSLs and monads may extend beyond the implementation level. It has become popular to include the monadic constructs as part of the EDSL surface language, which sparks interesting interactions with the underlying type system [94–96].
PARALLEL AND DISTRIBUTED COMPUTATION
For a long time, parallel and distributed programming was seen as a specialized activity by special experts. This situation is currently changing extremely rapidly with pervasive parallel and distributed environments such as multicore/manycore hardware and cloud computing. With the Google's MapReduce [97], one can now easily write a program to process and generate large data sets with a parallel, distributed algorithm on a cluster. The MapReduce model is actually inspired by the map and reduce functions commonly used in functional programming.
Functional programming languages offer a medium where programmers can express the features of parallel algorithms, without having to detail the low-level solutions [98–100]. The high level of programming abstraction of function composition and higher order functions simplifies the task of programming, fosters code reuse, and facilitates the development of substantially architecture-independent programs. The absence of side effects avoids the unnecessary serialization which is a feature of most conventional programs.
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 dependences for easy parallelization.
Skeleton parallel programming
Parallel primitives (also called parallel skeletons [101,102]) 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 the section entitled 'Functional forms' 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 |$\mathit {foldr}\; \mathit{op}\; e$|. The definition of |$\mathit {map}$| has been given in the section entitled 'Functional forms', and the definitions of |$\mathit {reduce}$| and |$\mathit {scan}$| are as follows:
\begin{equation*} \begin{array}{llll}\mathit {reduce}\; \mathit{op}\; e &=& \mathit {foldr}\; \mathit{op}\; e\\ \mathit {scan}\; \mathit{op}\; e &=& \mathit {map}\; (\mathit {foldr}\; \mathit{op}\; e) \circ \mathit {inits} \end{array} \end{equation*}
where op is an associative operator, and |$\mathit {scan}$| is defined as a composition of |$\mathit {map}\; (\mathit {foldr}\; \mathit{op}\; e)$| and |$\mathit {inits}$|. Note that |$\mathit {reduce}$| is different from |$\mathit {foldr}$| in that the operator op it can accept must be associative, which restricts the type of reduce (the operator must combine operands of the same type), but allows the implementation greater freedom to choose an order of combination (foldr always combines from right to left). The definitions above just define the semantics of reduce and scan, not necessarily their implementation.
It has been shown that map, reduce, and scan have nice massively parallel implementations on many architectures [102,103]. If k and an associative ⊕ use O(1) parallel time, then |$\mathit {map}\; k$| can be implemented using O(1) parallel time, and both |$\mathit {reduce}\; op\; e$| and |$\mathit {scan}\; op\; e$| can be implemented using O(logN) parallel time (N denotes the size of the list). For example, |$\mathit {reduce}\; op$| can be computed in parallel on a tree-like structure with the combining operator op applied in the nodes, while |$\mathit {map}\; k$| is computed in parallel with k applied to each of the leaves. The study on efficient parallel implementation of |$\mathit {scan}\; op\; e$| can be found in [102], which plays an important role in the implementation of parallel functional language NESL [104].
Just like |$\mathit {foldr}$| being the most important higher order function for manipulating lists sequentially, |$\mathit {reduce}$| plays the most important role in parallel processing of lists. If we can parallelize |$\mathit {foldr}$| as a parallel program using |$\mathit {reduce}$|, we can parallelize any sequential function that is defined in terms of |$\mathit {foldr}$| (This again shows an advantage of structuring programs using general functional forms.). This has attracted a lot of work in developing programming theories to parallelize |$\mathit {foldr}$| [105–108]. One known theorem for this parallelization is the so-called third homomorphism theorem [109], which shows that |$\mathit {foldr}\; op\; e$| can be parallelized as a composition of a map and a reduce if and only if there exists op ′ such that the following holds:
\begin{equation*} \mathit {foldr}\; op^{\prime }\; e = \mathit {foldr}\; op\; e \circ \mathit {reverse} \end{equation*}
In other words, this theorem says that a foldr is parallelizable if and only if can be written as a foldr on its reverse list. With this theorem, we can see that many of the functions defined in the section entitled 'Functional forms', such as |$\mathit {sum}$|, |$\mathit {sort}$|, |$\mathit {maxlist,}$| and |$\mathit {reverse}$|, can be parallelized as a composition of a map and a reduce. Importantly, this parallelization is not just a guide to programmers but also can be done automatically [110].
Easy parallelization
Purely functional languages have advantages when it comes to (implicit) parallel evaluation [111,112]. Thanks to the absence of side effects, it is always safe to execute computations of subexpressions in parallel. Therefore, it is straightforward to identify the parallel task in a program, which would require complex dependency analysis when parallelizing imperative programs.
Parallel Haskell provides two operators |$\mathit {pseq}$| and |$\mathit {par}$| for parallelization: |$\mathit {pseq}\; e_1\; e_2$| evaluates e 1 then e 2 in a sequential order, and |$\mathit {par}\; e_1\; e_2$| is a kind of fork operation, where e 1 is started in parallel with e 2 and the result of e 2 is returned. Consider the following normal Haskell function that implements the well-known Quicksort algorithm:
\begin{equation*} \begin{array}{llll}\mathit {sort}\; [\,] = [\,]\\ \mathit {sort}\; (x:xs) = \mathit {less} \,{+\!\!+}\, [x] \,{+\!\!+}\, \mathit {greater}\\ \quad \mathbf {where}\; \\ \qquad \mathit {less} = \mathit {sort}\; [ y \; |\; y \leftarrow xs, y<x ]\\ \qquad \mathit {greater} = \mathit {sort}\; [ y \; |\; y {\leftarrow} xs, y \ge x ]\\ \end{array} \end{equation*}
The following parallel version is just a little more complicated (with addition of the underlined codes); |$\mathit {greater}$| is computed in parallel with |$\mathit {less}$| by wrapping the original expression |$\mathit {less} \,{+\!\!+}\, [x] \,{+\!\!+}\, \mathit {greater}$| with |$\mathit {par}\; \mathit {greater}$| and |$\mathit {pseq}\; \mathit {less}$|.
\begin{eqnarray*} \begin{array}{llll}\mathit {parSort}\; [\,] = [\,]\\ \mathit {parSort}\; (x:xs) = \\ \quad \underline{\mathit {par}\; \mathit {greater}}\; (\underline{\mathit {pseq}\; \mathit {less}}\; \\ \qquad (\mathit {less} \,{+\!\!+}\, [x] \,{+\!\!+}\, \mathit {greater}))\\ \quad \mathbf {where}\; \\ \qquad \mathit {less} = \mathit {parSort}\; [ y \; |\; y \leftarrow xs, y<x ]\\ \qquad \mathit {greater} = \mathit {parSort}\; [ y \; |\; y \leftarrow xs, y \ge x ]\\ \end{array} \end{eqnarray*}
We can further control the granularity of the parallel task by switching to the normal |$\mathit {sort}$| when the number of elements of list is shorter enough.
\begin{eqnarray*} \begin{array}{llll}\mathit {parSort}\; [\,] = [\,]\\ \mathit {parSort}\; l@(x:xs) \\ \quad |\; \underline{\mathit {shorter}\; l \; =\; \mathit {sort}\; l}\\ \quad |\; \mathit {otherwise}\; =\; \\ \qquad \quad \underline{\mathit {par}\; \mathit {greater}}\; (\underline{\mathit {pseq}\; \mathit {less}}\; \\ \qquad \qquad (\mathit {less} \,{+\!\!+}\, [x] \,{+\!\!+}\, \mathit {greater}))\\ \quad \mathbf {where}\; \\ \qquad \mathit {less} = \mathit {parSort}\; [ y \; |\; y \leftarrow xs, y<x ]\\ \qquad \mathit {greater} = \mathit {parSort}\; [ y \; |\; y \leftarrow xs, y \ge x ]\\ \end{array} \end{eqnarray*}
It is worth noting that parallel functional programs are easy to debug. Regardless of the order in which computations are executed, the result of the program will always be the same. Specifically, the result will be identical to that obtained when the program is run sequentially. This implies that programs can be debugged sequentially, which represents a huge saving in effort.
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. Instead, nodes communicate by copying messages from sender to receiver; copying a mutable data structure changes semantics, because mutation of one copy is not reflected in the other, but immutable data can be copied transparently. This makes functional programming, with its immutable data structures, a natural fit. For systems which are designed to be scalable, in which overall system performance can be increased just by adding more nodes, it makes sense to use the same share-nothing communication between processes running on the same node, so that they may easily be deployed across multiple nodes as new nodes are added. Distributed systems can also offer high reliability, by using redundancy to tolerate failures, and in-service upgrade, by upgrading one node at a time while the others continue to deliver service.
Erlang was designed at Ericsson in the late 1980s for building systems of this kind, originally for the telecom domain [113]. Later, Erlang proved to be ideal for building scalable internet services, and many start-ups have used it as their 'secret sauce'. The first of these was Bluetail AB, founded in 1998 to develop among others an SSL accelerator in Erlang, and sold for $140 million less than 18 months later; the most spectacular to date is WhatsApp, whose back-end servers are built in Erlang, and sold to Facebook in 2014 for $22 billion.
Erlang is a simple functional language with a slightly wordier syntax than Haskell; the factorial function defined in the introduction would be written in Erlang as follows:
\begin{eqnarray*} \begin{array}{llll}\mathit {fac} (0) \rightarrow 1;\\ \mathit {fac} (N)\; \mathbf {when}\; N > 0 \rightarrow N * \mathit {fac} (N-1) \end{array} \end{eqnarray*}
Erlang provides immutable lists and tuples, and LISP-like atoms, but no user-defined datatypes. Erlang lacks a static type system (Although many developers use Dialyzer [114], a static analysis tool that can detect many type errors.)—a reasonable choice since dynamic code loading, necessary for in-service upgrades, is difficult to type statically to this day.
To this functional core, Erlang adds features for concurrency and message passing. For example, Fig.2 presents a (not very efficient) parallel version of QuickSort in Erlang. This function uses pattern matching on lists to select between the case of an empty list and a cons (|$\mathit {[X|Xs]}$| means |$x:\mathit {xs}$|), and in the latter case uses list comprehensions to select the elements less than or greater than the pivot, then |$\mathit {spawn}$|s two new processes to sort each sublist recursively. Spawning a process calls the function provided (as an Erlang λ-expression, fun() → …end) in the new process. Each of these processes sends the result of its recursive sort back to the parent process (|$\mathit {Parent}\; !\; \ldots$|), using the parent's process identifier, which is obtained by calling |$\mathit {self}()$|. Each result is tagged with an atom (|$\mathit {less}$| or |$\mathit {grtr}$|), which allows the parent process to receive the results in the correct order—messages wait in the recipient's 'mailbox' until a matching receive removes them from it, so it doesn't matter in which order the messages from the child processes actually arrive. Erlang processes share no memory—they each have their own heap—which means that the lists to be sorted must be copied into the new process heaps. This is why we filter |$\mathit {Xs}$| to extract the less and greater elements before starting the child processes: it reduces the costs of copying lists. The advantage of giving each process its own heap is that processes can garbage collect independently while other processes continue working, which avoids long garbage collection pauses and makes Erlang suitable for soft real-time applications.
Figure 1.
Code fragments in three EDSLs.
Figure 1.
Code fragments in three EDSLs.
Figure 2.
Parallel QuickSort in Erlang.
Figure 2.
Parallel QuickSort in Erlang.
Erlang adds mechanisms for one process to monitor another, turning a crash in the monitored process into a message delivered to the monitoring one. These mechanisms are used to support fault tolerance, with a hierarchy of supervisor processes which are responsible for restarting subsystems that fail; indeed, Erlang developers advocate a 'let it crash' approach, in which error-handling code (which is often complex and poorly tested) is omitted from most application code, relying on the supervisors for fault tolerance instead. Common patterns for building fault-tolerant systems are provided in the 'Open Telecom Platform' libraries—essentially higher order functions that permit fault-tolerant systems to be constructed just by instantiating the application-dependent behaviour.
Erlang's approach to concurrency and distribution has been very successful, and has been widely emulated in other languages—for example, Cloud Haskell [115] provides similar features to Haskell developers. One of the best known 'clones' is the Akka library for Scala [15], which is used among others to build Twitter's back-end services.
FUNCTIONAL THINKING IN PRACTICE
Functional programming has had big influences on education and other language design, and seen significant uses in industry.
Education
The style of teaching functional languages as first languages was pioneered by MIT in the 1980s, where functional language scheme was taught in the first course using the famous textbook Structure and Interpretation of Computer Programs [116]. Now many universities such as Oxford (Haskell) and Cambridge (ML) follow this functional-first style. In a recent survey (http://www.pl-enthusiast.net/2014/09/02/who-teaches-functional-programming/), 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. Compared to the other programming-first implementations, 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. In fact, one of the explicit goals of Haskell's designers was to create a language suitable for teaching. Indeed, almost as soon as Haskell was defined, it was being taught to undergraduates at Oxford and Yale.
For learning the latest advanced functional programming techniques, there has been an excellent series of International Summer Schools on Advanced Functional Programming since 1995. Five such summer schools have been held so far in 1995, 1996, 1998, 2002, and 2004, with all lecture notes published in Lecture Notes in Computer Science by Springer. For the new applications of functional programming, there has been another series of Summer Schools on Applied Functional Programming organized by Utrecht University since 2009. The two-week course covers applications of functional programming, concentrating on topics such as language processing, building graphical user interfaces, networking, databases, and programming for the web.
For exchanging ideas of functional programming in education, there is a series of International Workshops on Trends in Functional Programming in Education since 2012, where novel ideas, classroom-tested ideas, and work in progress on the use of functional programming in education are discussed among researchers and teachers. They have previously been held in St Andrews, Scotland (2012); Provo Utah, USA (2013); and Soesterberg, the Netherlands (2014).
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, unleashing influences in an unostentatious manner. It is well conceivable that 'main stream' programmers may be using functional features in their code without realizing.
One of the early examples of such is blocks in Smalltalk—a way of expressing lambda expressions and therefore higher order functions. More recently, the development of C# is influenced by functional programmers working in Microsoft. The LINQ features are directly inspired by monads and functional lists. Lambda expressions are introduced in C# 3.5, but higher order programming had been possible earlier on through delegates. Type inference is part of C#'s design and generics (polymorphism) are added in C# 2.0.
Java's generic type system introduced in Java 5 is based on ML's Hindley–Milner type systems. Subsequent releases gradually introduced type inference, another feature that is usually associated with functional languages. Java 8 embraced functional programming by releasing a wealth of features that specifically aimed at facilitating such a programming style. It includes dedicated support for lambda expressions and the passing of functions as method arguments (i.e. higher order functions), which is further made easy by the new feature of method references.
C++ aboards the lambda expression train in C++11. A particular merit of this C++ feature, as opposed to lambdas in other imperative languages, is that it offers fine-grained control over variable capture. Programmers are able to declare in their definitions whether the lambda bodies may refer to external variables (variables that are not formally declared as parameters) by value, by reference, or not at all—a step towards purity.
Modern multiparadigm languages often have good provision of functional features. Ruby is admitted by its inventor as having Lisp as its origin and blocks at its core. Additional lambda syntax is added in Ruby 1.9. Python adopted the list comprehension notation and has support for lambda expressions. The Python standard library includes many functional tools imported from Haskell and Standard ML. Scala is an object-functional language that has full support for functional programming. In addition to a strong static type system, it also features currying, type inference, immutability, lazy evaluation, and pattern matching.
Meijer's reactive extensions ('RX') [117] enable .NET developers to manipulate asynchronous data streams as immutable collections with purely functional operations defined over them. RX simplifies the construction of event-driven reactive programs dramatically. The design has been copied in many other languages, perhaps most notably at Netflix, where RxJava is heavily used in the Netflix API.
Uses in industry
It has often proven easier to adopt functional programming in small, new companies, rather than in large, existing software development organizations. By now, there have been many, many start-ups using functional programming for their software development. One of the first was Paul Graham's Viaweb, which built a web shop system in Lisp, and was later sold to Yahoo. Graham's well-known article 'Beating the Averages' (http://www.paulgraham.com/avg.html) discusses Lisp's importance as Viaweb's 'secret weapon'. He writes of studying competitors' job adverts: 'The safest kind were the ones that wanted Oracle experience. You never had to worry about those. You were also safe if they said they wanted C++ or Java developers. ...If I had ever seen a job posting looking for Lisp hackers, I would have been really worried.'
The first company to use Haskell was Galois, who develop 'high assurance' software, primarily under government contracts. Galois develop their code in Haskell—which in itself helps to ensure quality—but also use property-based testing, and the theorem provers we have discussed in this paper. 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. At the heart of the system is a DSL for writing the detection logic, firstly implemented in FXL (an in-house functional language) and is being migrated to Haskell at the moment.
Erlang, with its roots in industry, has a strong start-up culture. The first Erlang start-up, Bluetail AB, was set up after Ericsson decided to discourage the use of Erlang internally. Many key members of the Erlang team left Ericsson to found a company focussing on scalable and highly reliable internet products; within 18 months Bluetail was sold to Alteon Web Systems for $150 million. The founders were soon starting new companies, including Klarna AB (providing invoicing services to web shops in seven European countries) and Tail-f (sold to Cisco in 2014 for $175 million). The highest profile Erlang start-up to date, though, is WhatsApp, bought by Facebook in 2014 for $22 billion. 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'. This illustrates nicely the benefits of productivity, scalability, and reliability that functional programming delivers.
Functional programming has also found many users in the financial sector, thanks not least to Peyton-Jones et al's seminal work on modelling financial contracts in Haskell [118]. Traders need to evaluate all kinds of financial derivatives quickly, so they can decide at which price to buy or sell them. But new, ingenious derivatives are being invented constantly, forcing traders to update their evaluation software continuously. By providing combinators for modelling contracts, this task can be accelerated dramatically, bringing a substantial advantage to traders who use them—the first trader able to evaluate a new derivative correctly stands to make a considerable profit. Credit Suisse was the first to use this technology, with the help of Augustsson, who now plays a similar role at Standard and Chartered—but these are far from the only examples. Functional programming is also used for automated trading at Jane Street, whose systems are built in OCaml. The clarity and quality of OCaml code helps Jane Street ensure that there are no bugs, which might rapidly lose large sums of money.
Languages such as Scala and Clojure (which run on the JVM) and F# (which runs on .NET) aim to be less disruptive, by integrating with an existing platform. They are enjoying wide adoption; for example, Apache Spark, a popular open-source framework for Big Data analytics, is largely built in Scala. Nowadays, there are successful companies whose business idea is to support the adoption of functional programming by their customers: Erlang Solutions (for Erlang), Typesafe (for Scala), Cognitect (for Clojure), Well-typed and FP Complete (for Haskell).
New applications of functional programming are appearing constantly. A good way to follow these developments is via developer conferences such as the Erlang Factory, Scala Days and Clojure/conj, and also via the annual conference on Commercial Applications of Functional Programming (http://cufp.org) , held in association with ICFP.
CONCLUSION
Twenty-five years ago, functional programming was high in the sky, favoured 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. Where will functional programming be twenty-five years from now?
REFERENCES
1.
Why functional programming matters
Comput J
1989
32
98
107
2.
et al.
Report on the programming language Haskell a non-strict purely functional language
SIGPLAN Not
1992
27
1
3.
Introduction to Functional Programming
1998
2nd edn
Upper Saddle River, New Jersey
Pearson Education
4.
The Haskell School of Expression: Learning Functional Programming Through Multimedia
2000
New York, NY, USA
Cambridge University Press
5.
ML for the Working Programmer
1996
2nd edn
New York, NY, USA
Cambridge University Press
6.
Programming Erlang: Software for a Concurrent World
2007
Raleigh
Pragmatic Bookshelf
7.
The Definition of Standard ML
1997
Cambridge, MA, USA
MIT Press
8.
Real World OCaml: Functional Programming for the Masses
2013
O'Reilly Media
9.
Ocaml for the masses
Commun ACM
2011
54
53
8
10.
Functional Programming Using F#
2013
New York, NY, USA
Cambridge University Press
11.
Common LISP: The Language
1984
Newton, MA, USA
Digital Press
12.
Practical Common Lisp
2012
1st edn
Berkely, CA, USA
Apress
13.
The Scheme Programming Language
2009
4th edn
Cambridge
The MIT Press
14.
et al.
Krishnamurthi
How to Design Programs: An Introduction to Programming and Computing
2001
Cambridge, MA, USA
MIT Press
15.
Programming Scala: Scalability = Functional Programming + Objects
2009
1st edn
O'Reilly Media
16.
Programming Clojure
2009
1st edn
Raleigh, NC
Pragmatic Bookshelf
17.
QuickCheck: a lightweight tool for random testing of Haskell programs
Proceedings of the Fifth ACM SIGPLAN International Conference on Functional Programming
2000
New York, NY, USA
ACM
268
79
ICFP '00
18.
Formal certification of a compiler back-end or: programming a compiler with a proof assistant
33rd ACM symposium on Principles of Programming Languages
2006
New York, NY, USA
ACM Press
42
54
19.
et al.
Finding and understanding bugs in C compilers
Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation
2011
New York, NY, USA
ACM
PLDI '11
20.
Generics for the masses
J Funct Progr
2006
16
451
83
21.
Security testing and formal methods for high levels certification of smart cards
Proceedings of the 3rd International Conference on Tests and Proofs
2009
Berlin
Springer
1
5
TAP '09
22.
Formal certification of code-based cryptographic proofs
Proceedings of the 36th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
2009
New York, NY, USA
ACM
90
101
POPL '09
23.
QuickCheck testing for fun and profit
Proceedings of the 9th International Conference on Practical Aspects of Declarative Languages
2007
Berlin
Springer
1
32
PADL '07
24.
et al.
Testing telecoms software with Quviq QuickCheck
Proceedings of the 2006 ACM SIGPLAN Workshop on Erlang
2006
New York, NY, USA
ACM
2
10
ERLANG '06
25.
Testing a database for race conditions with QuickCheck: none
Proceedings of the 10th ACM SIGPLAN Workshop on Erlang
2011
New York, NY, USA
ACM
72
7
Erlang '11
26.
et al.
Testing autosar software with QuickCheck
Testing: Academic and Industrial Conference—Practice and Research Techniques, Part of the ICST Workshop Proceedings
2015
Graz, Austria
IEEE Digital Library
27.
A short cut to deforestation
Proceedings of the Conference on Functional Programming Languages and Computer Architecture
1993
New York, NY, USA
ACM
223
32
FPCA '93
28.
Shortcut deforestation in calculational form
Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture
1995
New York, NY, USA
ACM
306
13
FPCA '95
29.
et al.
Tupling calculation eliminates multiple data traversals
Proceedings of the Second ACM SIGPLAN International Conference on Functional Programming
1997
New York, NY, USA
ACM
164
75
ICFP '97
30.
et al.
The hermit in the machine: a plugin for the interactive transformation of GHC core language programs
Proceedings of the 2012 Haskell Symposium
2012
New York, NY, USA
ACM
1
12
Haskell '12
31.
Revisiting catamorphisms over datatypes with embedded functions
Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '96
1996
New York, NY, USA
ACM
284
94
32.
Functional programming with bananas lenses envelopes and barbed wire
Proceddings of the 5th ACM Conference on Functional Programming Languages and Computer Architecture
1991
Cambridge, MA
ACM
124
44
LNCS 23
33.
A fold for all seasons
Proceedings of the Conference on Functional Programming Languages and Computer Architecture
1993
New York, NY, USA
ACM
233
42
FPCA '93
34.
Conjugate hylomorphisms—or: the mother of all structured recursion schemes
Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
2015
New York, NY, USA
ACM
527
38
POPL '15
35.
Deriving structural hylomorphisms from recursive definitions
Proceedings of the First ACM SIGPLAN International Conference on Functional Programming
1996
New York, NY, USA
ACM
73
82
ICFP '96
36.
Pizza into java: translating theory into practice
Proceedings of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
1997
New York, NY, USA
ACM
146
59
POPL '97
37.
Proceedings of the Fourth International Conference on Functional Programming Languages and Computer Architecture
1989
New York, NY, USA
ACM
347
59
FPCA '89, Theorems for free!
38.
Types abstraction and parametric polymorphism
Proceedings of IFIP 9th World Computer Congress
Amsterdam
Elsevier Science Publishers B. V. (North-Holland)
513
23
39.
Type classes as objects and implicits
Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications
2010
New York, NY, USA
ACM
341
60
OOPSLA '10
40.
Interactive Theorem Proving and Program Development: Coq'Art The Calculus of Inductive Constructions
2010
1st edn
Springer Publishing Company
Incorporated
41.
Dependently typed programming in Agda
Proceedings of the 6th International Conference on Advanced Functional Programming
2009
Berlin
Springer
230
66
AFP'08
42.
Constructive functional programming
STOP Summer School on Constructive Algorithmics
1989
43.
Algebra of Programming
1997
Upper Saddle River, NJ, USA
Prentice Hall
44.
Programming as a discipline of mathematical nature
Am Mathemat Mon Comp J
1974
81
608
12
45.
Pearls of Functional Algorithm Design
2010
1st edn
New York, NY, USA
Cambridge University Press
46.
Solving optimisation problems with catamorphism
Proceedings of the Second International Conference on Mathematics of Program Construction
1993
London, UK
Springer
45
66
47.
Program optimizations and transformations in calculational form
Summer School on Generative and Transformational Techniques in Software Engineering
2006
Braga, Portugal
Springer
139
64
LNCS 4043
48.
Program transformation in calculational form
ACM Comput Surv
1998
30
49.
KIDSa knowledges-based software development system
Proceedings of AAAI'88 Workshop on Automating Software Design
1991
The MIT Press
483
514
50.
Generic program transformation
Advanced Functional Programming, Lecture Notes in Computer Science
Berlin
Springer
116
49
51.
Algebra of programming in Agda: dependent types for relational program derivation
J Funct Progr
2009
19
545
79
52.
Netty: a prover's assistant
COMPUTATION TOOLS 2011: The Second International Conference on Computational Logics, Algebras, Programming, Tools, and Benchmarking
25
30
Rome, 2011 September
53.
et al.
Program calculation in Coq
Proceedings of the 13th International Conference on Algebraic Methodology and Software Technology
2011
Berlin
Springer
163
79
AMAST'10
54.
Recent improvements of MagicHaskeller
Proceedings of Workshop on Approaches and Applications of Inductive Programming
2010
Berlin
Springer
174
93
AAIP '10(LNCS 5812)
55.
An analytical inductive functional programming system that avoids unintended programs
Proceedings of the ACM SIGPLAN 2012 Workshop on Partial Evaluation and Program Manipulation
2012
New York, NY, USA
ACM
43
52
PEPM '12
56.
Computational lambda-calculus and monads
Proceedings of the Fourth Annual Symposium on Logic in Computer Science
1989
Piscataway, NJ, USA
IEEE Press
14
23
57.
Notions of computation and monads
Inf Comput
1991
93
55
92
58.
Comprehending monads
Proceedings of the 1990 ACM Conference on LISP and Functional Programming
1990
New York, NY, USA
ACM
61
78
LFP '90
59.
The essence of functional programming
Proceedings of the 19th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
1992
New York, NY, USA
ACM
1
14
POPL '92
60.
Imperative functional programming
Proceedings of the 20th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
1993
ACM
New York, NY, USA
71
84
POPL '93
61.
Peyton Jones SL
. State in Haskell
Lisp Symb Comput
1995
8
293
341
62.
Monadic state: axiomatization and type safety
Proceedings of the Second ACM SIGPLAN International Conference on Functional Programming
1997
New York, NY, USA
ACM
227
38
ICFP '97
63.
Concurrent Haskell
Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
1996
New York, NY, USA
ACM
295
308
POPL '96
64.
et al.
Composable memory transactions
Proceedings of the Tenth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
2005
New York, NY, USA
ACM
48
60
PPoPP '05
65.
Monad transformers and modular interpreters
Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
1995
New York, NY, USA
ACM
333
43
POPL '95
66.
Building interpreters by composing monads
Proceedings of the 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
New York, NY, USA
ACM
472
92
POPL '94
67.
Extensible effects: an alternative to monad transformers
Proceedings of the 2013 ACM SIGPLAN Symposium on Haskell
2013
New York, NY, USA
ACM
59
70
Haskell '13
68.
Monads zippers and views: virtualizing the monad stack
Proceedings of the 16th ACM SIGPLAN International Conference on Functional Programming
2011
New York, NY, USA
ACM
32
44
ICFP '11
69.
Monad factory: type-indexed monads
Proceedings of the 11th International Conference on Trends in Functional Programming
2011
Berlin
Springer
198
213
TFP'10
70.
Generalising monads to arrows
Sci Comput Progr
2000
37
67
111
71.
Arrows and computation
The Fun of Programming
2003
Palgrave Macmillan
201
22
72.
Applicative programming with effects
J Funct Progr
2008
18
1
13
73.
et al.
Arrows robots and functional reactive programming
Summer School on Advanced Functional Programming 2002, Oxford University
2003
Berlin
Springer
159
87
LNCS 2638
74.
et al.
Fixing idioms: a recursion primitive for applicative DSLs
Proceedings of the ACM SIGPLAN 2013 Workshop on Partial Evaluation and Program Manipulation. PEPM '13
2013
New York, NY, USA
ACM
97
106
75.
Idioms are oblivious arrows are meticulous monads are promiscuous
Electron Notes Theor Comput Sci
2011
229
97
117
76.
Building domain-specific embedded languages
ACM Comput Surv.
1996
28
4es, Article 196
77.
Modular domain specific languages and tools
Proceedings of the 5th International Conference on Software Reuse. ICSR '98
1998
Washington, DC, USA
IEEE Computer Society
134
42
78.
et al.
A history of Haskell: being lazy with class
Proceedings of the Third ACM SIGPLAN Conference on History of Programming Languages
2007
New York, NY, USA
ACM
HOPL III, 12-1-;12-55
79.
Monadic parser combinators
Technical Report NOTTCS-TR-96-4
1996
University of Nottingham
Department of Computer Science
80.
Monadic parsing in Haskell
J Funct Progr
1998
8
437
44
81.
Parsing permutation phrases
J Funct Progr
2004
14
635
46
82.
Lazy lexing is fast
Proceedings of the 4th Fuji International Symposium on Functional and Logic Programming. FLOPS '99
1999
London, UK
Springer
68
84
83.
J Funct Progr
2004
14
Parallel parsing processes
741
57
84.
Packrat parsing: simple powerful lazy linear time functional pearl
Proceedings of the Seventh ACM SIGPLAN International Conference on Functional Programming. ICFP '02
2002
New York, NY, USA
ACM
36
47
85.
Swierstra SD Duponcheel
L
Deterministic error-correcting combinator parsers
Advanced Functional Programming, Second International School-Tutorial Text
1996
London, UK
Springer
184
207
86.
Compiling embedded languages
J Funct Progr
2003
13
455
81
87.
Folding domain-specific languages: deep and shallow embeddings (functional pearl)
Proceedings of the 19th ACM SIGPLAN International Conference on Functional Programming. ICFP '14
2014
New York, NY, USA
ACM
339
47
88.
The expression problem. Java Genericity Mailing list
1998
89.
A generic abstract syntax model for embedded languages
Proceedings of the 17th ACM SIGPLAN International Conference on Functional Programming, ICFP '12
2012
New York, NY, USA
ACM
323
34
90.
Compositional data types
Proceedings of the Seventh ACM SIGPLAN Workshop on Generic Programming, WGP '11
2011
New York, NY, USA
ACM
83
94
91.
Finally tagless partially evaluated: tagless staged interpreters for simpler typed languages
J Funct Progr
2009
19
509
43
92.
Data types à la carte la carte
J Funct Progr
2008
18
423
36
93.
Combining deep and shallow embedding for EDSL
Trends in Functional Programming
2013
Berlin
Springer
21
36
LCNS 7829
94.
Generic monadic constructs for embedded languages
Implementation and Application of Functional Languages
2012
Berlin
Springer
85
99
LCNS 7257
95.
et al.
The constrained-monad problem
Proceedings of the 18th ACM SIGPLAN International Conference on Functional Programming. ICFP '13
2013
New York, NY, USA
ACM
287
98
96.
Simple and compositional reification of monadic embedded languages
Proceedings of the 18th ACM SIGPLAN International Conference on Functional Programming. ICFP '13
2013
New York, NY, USA
ACM
299
304
97.
Mapreduce: simplified data processing on large clusters
Proceedings of the 6th Conference on Symposium on Operating Systems Design and Implementation. OSDI'04
2004
Berkeley, CA, USA
USENIX Association
10
98.
Can programming be liberated from the von neumann style?: a functional style and its algebra of programs
Commun ACM
1978
21
613
41
99.
Parallel implementations of functional programming languages
Comput J
1989
32
175
86
100.
et al.
Comparing parallel functional languages: programming and performance
Higher Order Symb Comput
2003
16
203
51
101.
Higher-order functions for parallel evaluation
Proceedings of Computing Science Department Research Report 89/R4
1989
Isle of Bute, Scotland
Glasgow University
8
20
102.
Research Monographs in Parallel and Distributed Computing
Algorithmic skeletons : a structured approach to the management of parallel computation
1989
Pitman, London
103.
Architecture-independent parallel computation
IEEE Comput
1990
23
38
51
104.
NESL: a nested data parallel language
Technical Report CMU-CS-92-103
1992
Carnegie-Mellon University
School of Computer Science
105.
Parallelization via context preservation
IEEE Computer Society International Conference on Computer Languages
1998
Chicago, USA
Loyola University Chicago
106.
Parallelization in calculational forms
25th ACM Symposium on Principles of Programming Languages (POPL'98)
1998
San Diego, CA, USA
ACM Press
316
28
107.
Diffusion: calculating efficient parallel programs
1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation
1999
San Antonio, TX
85
94
BRICS Notes Series NS-99-1
108.
Towards automatic parallelization of tree reductions in dynamic programming
18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2006)
2006
Cambridge, MA, USA
ACM Press
39
48
109.
The third homomorphism theorem
J Funct Progr
1996
6
657
65
110.
et al.
Automatic inversion generates divide-and-conquer parallel programs
Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation. PLDI '07
2007
New York, NY, USA
ACM
146
55
111.
Chakravarty MMT Leshchinskiy
R
et al.
Data parallel Haskell: a status report
Proceedings of the 2007 Workshop on Declarative Aspects of Multicore Programming. DAMP '07
2007
New York, NY, USA
ACM
10
8
112.
Why parallel functional programming matters: panel statement
Proceedings of the 16th Ada-Europe International Conference on Reliable Software Technologies
2011
Berlin
Springer
201
5
Ada-Europe'11
113.
A history of Erlang
Proceedings of the Third ACM SIGPLAN Conference on History of Programming Languages, HOPL III
2007
New York, NY, USA
ACM
6–1
6–26
114.
Detecting defects in Erlang programs using static analysis
Proceedings of the 9th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming. PPDP '07
2007
New York, NY, USA
ACM
37
115.
Towards Haskell in the cloud
Proceedings of the 4th ACM Symposium on Haskell. Haskell '11
2011
New York, NY, USA
ACM
118
29
116.
Structure and Interpretation of Computer Programs
1985
Cambridge, MA, USA
MIT Press
117.
Reactive extensions (rx): curing your asynchronous programming blues
ACM SIGPLAN Commercial Users of Functional Programming. CUFP '10
2010
11
New York, NY, USA
ACM
1
118.
Composing contracts: an adventure in financial engineering (functional pearl)
Proceedings of the Fifth ACM SIGPLAN International Conference on Functional Programming. ICFP '00
2000
New York, NY, USA
ACM
280
92
119.
xhtml: an XHTML combinator library
120.
Functional reactive animation
Proceedings of the Second ACM SIGPLAN International Conference on Functional Programming. ICFP '97
1997
New York, NY, USA
ACM
263
73
121.
et al.
haskelldb: a library of combinators for generating and executing SQL statements
122.
Scans as primitive operations
IEEE Trans Comp
1989
38
1526
38
© The Author(s) 2015. Published by Oxford University Press on behalf of China Science Publishing & Media Ltd. All rights reserved. For Permissions, please email: journals.permissions@oup.com
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/), which permits non-commercial reuse, distribution, and reproduction in any medium, provided the original work is properly cited. for commercial re-use, please contact journals.permissions@oup.com
How to Check Komp Structure During Order Processing
Source: https://academic.oup.com/nsr/article/2/3/349/1427872
0 Response to "How to Check Komp Structure During Order Processing"
Post a Comment