Modern programming languages have a large set of various tools and useful features that make it possible to write quite a different code in the same language for the same task. Programming paradigm is a way of thinking in the first place – the way the programmer thinks about the representation and processing. In other words, programming paradigm exists in the programmer’s mind; it is not a part of the language. Different languages can support a specific paradigm to varying degrees. If we open Wikipedia and start reading about the most popular programming languages, we’ll see that many of them are described as “multi-paradigm”, i.e. they allow programming in different styles, though some of them will be more convenient to use then others.
In a recent post, we spoke about the practical applications of Lisp and mentioned, without going into details, that it strongly influenced the development of other programming languages. Now it’s high time to explore this topic in more detail and figure out what contribution functional programming in general (not just Lisp!) has made to the development of other languages. Since we use Haskell as our main programming language, we couldn’t help touching upon this topic.
In this post, we’re going to consider several mechanisms which have either emerged in functional programming languages or are most widely used and popularized by these languages, eventually turning up in originally non-functional languages.
First-class functions
The distinctive feature of FP style, in general, is the wide use of functions that has grown into a main development tool. Let’s quickly look through the main definitions outlining the differences between functions and procedures, as well as other similar constructs of non-functional languages.
Higher-order function is a function that either takes another function as an argument or returns some function as the result. They are also called functionals. This behaviour can be implemented even in pure C by using function pointers:
void update_user_balance(int user_id,
double (*update_fn)(double))
{
// ...
user->balance = update_fn(user->balance);
// ...
}First-class functions are the ones which you can manipulate in the same way as any other value: pass as arguments, return as results, assign to variables and structure fields.
Lambda function is an anonymous function. Besides lacking a name, support of lambda functions removes other language restrictions on function declarations (in some languages, e.g. in C99 standard, function declarations can occur only at a higher level). Support of lambda functions implies that the function can be declared in any location where other expressions are valid. Lambda functions are mostly used in higher-order functions; when used in combination, they provide convenience and a significant shortening of the code.
// Example of a lambda function used to print out
// the contents of std::vector
int main() {
std::vector<int> v;
v.push_back(1);
v.push_back(2);
std::for_each(v.begin(), v.end(), [] (int x) {
std::cout << x << '\n';
});
}Closure is a function that can capture some variables from the context in which it was declared, without letting the garbage collector erase the data that can be used in this function, as long as the application has the reference to the function itself. An example in TypeScript:
function createClosures() {
// The variable can be seen in the functions below
let counter = 0;
// The values of fields inc and print are closures
return {
inc: () => { counter++; },
print: () => console.log('counter value: ' + counter),
};
}
const c = createClosures();
c.inc();
c.inc();
c.print(); // >>> "counter value: 2"List comprehension
List comprehension allows writing down concisely the processing or generation of lists using existing ones. Miranda was one of the first languages to use such syntax, which was adopted by Haskell; later on, similar constructs appeared in “less functional” languages such as Python, C#, and Ruby.
As an example, let’s consider the code in Python and Haskell that creates word combinations using adjectives and nouns. These two fragments look very much alike and only have minor syntactical differences, wouldn’t you agree?
# Example in Python
nouns = ["waterfall", "moon", "silence"]
adjectives = ["late", "divine", "blue"]
phrases = [a + " " + n for n in nouns for a in adjectives]
# >>> ['late waterfall', 'divine waterfall',
# 'blue waterfall', 'late moon', 'divine moon',
# 'blue moon', 'late silence', 'divine silence',
# 'blue silence']-- The same in Haskell
nouns = ["waterfall", "moon", "silence"]
adjectives = ["late", "divine", "blue"]
phrases = [a ++ " " ++ n | n <- nouns, a <- adjectives]
-- >>> ['late waterfall', 'divine waterfall',
-- 'blue waterfall', 'late moon', 'divine moon',
-- 'blue moon', 'late silence', 'divine silence',
-- 'blue silence']Algebraic data types
These types can also be called ADTs, sum types, discriminatory unions, disjunctive unions, coproducts, and, probably, some other clever terms. Maybe you use a different name for such types. In a nutshell, this is a compound type containing a discriminant field (which can be called a tag), together with the associated data. One example in Haskell of such a compound type describes the user’s possible actions in a hypothetical application implementation TodoMVC. Some actions involve the “payload” (a string or an element ID).
data UserAction
= TextInput String
| EnterPressed
| EscPressed
| CheckTodoItem ItemId Bool
| EditTodoItem ItemId String
| DeleteTodoItem ItemId
| ApplyFilter TodoFilterDespite its simplicity and usefulness for modelling domain objects, ADTs are rarely supported on a full scale in popular languages and databases. Here are some examples that implement similar types: Enum in Rust, Sealed Classes in Kotlin, std::variant in C++
Pattern Matching
Pattern Matching is a syntactic construct that gives access to the data of the structure consisting of one or several alternatives with different sets of fields (the very ADT, algebraic type sum, enum, std::variant, etc. as we discussed earlier). Pattern Matching resembles the switch-case operator you all know from imperative languages. However, its main advantage is that the compiler checks the access to alternative fields statically by using the information about the expression type, while the switch-case doesn’t prevent errors related to incorrect access to the fields, missing cases or redundant checks.
Pattern Matching is another technique popularized in functional languages, where it turned out to be quite useful. Now it has been adopted and integrated – in various forms – in Python, Java, C#, Rust, and other popular languages.
-- Example of state update function in a hypothetical
-- TodoMVC written in the Elm architecture style.
-- Pattern Matching is used to analyze the
-- user-generated event.
updateTodoList :: UserAction -> TodoState -> TodoState
updateTodoList action oldState = case action of
TextInput newTitle -> oldState {title = newTitle}
EnterPressed -> appendNewItem oldState
EscPressed -> stopEditing oldState
CheckTodoItem itemId itemChecked ->
updateItemById itemId (#checked .~ itemChecked)
EditTodoItem itemId itemTitle ->
updateItemById itemId (#title .~ itemTitle)
DeleteTodoItem itemId -> deleteItembyId itemId oldState
ApplyFilter newFilter -> oldState {filter = newFilter}Lazy evaluations
In most programming languages evaluation is performed when a value is assigned to the variable; all arguments are evaluated before the function call (strict evaluations). The alternative approach is “lazy”, implying that the evaluation is postponed until the value has actually been used. Lazy evaluation allows working with infinite data structures, writing declarative code with definitions arranged in an order convenient for reading, instead of the order of their evaluation. If you use the DSL approach, lazy evaluations will help you to easily implement such constructs as if-then-else (where the values will be evaluated only in the branch you need).
The history of the term can be traced back to lambda calculus, forming part of the theoretical basics of functional programming, so there’s no wonder that it’s used in FP languages. For instance, in Haskell everything is evaluated lazily by default.
Some elements of “laziness” can be found in other languages. Even in pure C, the operators && and || are lazy as they don’t evaluate their second argument if the first one has been correspondingly evaluated as 0 or 1. In higher-level languages, the more common term is “deferred evaluations”, which are implemented using generator functions and the “yield” keyword. Such generators can be found, for example, in Python and Java.
Continuations
Continuation is the “remaining evaluation”, i.e. the description of what is to be done with the result of an expression for each subexpression in the program. An expression gets its continuation in the form of an additional argument, and when the result is obtained, the current function calls the passed continuation with the evaluated value, instead of returning the result directly. Such style of passing the result is called Continuation-Passing Style (CPS).
// Direct style of passing the result
function getFoo(): Foo {..}
// CPS style
function getFooCPS<A>(cont: (foo: Foo) => A): А {..}CPS is rarely found immediately in the software source code. Compilers are one of the main areas of CPS’s application – as an intermediate representation before generating the machine code. Code conversion to CPS allows transforming recursive function calls to tail recursion that can be easily optimized to avoid stack growth during evaluations.
Continuations is a very powerful tool that can be used to implement control structures such as early function exit, explicit call for tail recursion, imperative cycles, etc. For more details on the use of continuations, see the example for the Scheme language here.
Futures and promises
Futures, also known as Promises, or Deferred, are a construct containing the evaluation of asynchronous values. They emerged in functional programming as a tool used to simplify parallel evaluations and execute queries in distributed systems.
const getJson = url => fetch(url).then(resp =>
resp.json());
// Sending 2 serial queries
const getUserInfo = getJson('/current-user-id').then(
userId => getJson(`/user-info/${userId}`).then(
userInfo => console.log(
`Hi ${userInfo.firstName}, your id is ${userId}`)
)
);Promises were popularized mainly because of their adaptation and extensive use in the browser. JavaScript execution in the browser is limited by only one execution thread. Therefore, blocking while waiting for an HTTP response, as is the case with most platforms, would have led to a page hangup and annoyed users. This is why callback functions are used to process responses to HTTP queries in the browser. At the same time, it’s not very convenient to combine such requests and the term “Callback Hell” emerged to describe code that has become illegible due to a large number of callbacks. Promises have enabled a partial solution to the issue of sending parallel queries and serial query chains:
// Sending 3 parallel queries
const fetchInParralel = Promise.all([
getJson('/current-user-info'),
getJson('/shopping-cart'),
getJson('/recently-viewed-items'),
]).then(([userInfo, cart, viewedItems]) => {
// Display the page using the data sent from the server
// ...
})
In many popular languages (such as C#, Java, JavaScript), promises have become the main tool for asynchronous programming.
Monadic interface
The names of many constructs and programming techniques in Haskell were borrowed from category theory and other branches of mathematics. One such term – the Monad – has become the object of many memes and jokes about functional programming. There are lots of posts on the web explaining what “Monads” are in functional languages and how to use them.
To put it simply, “monad” is just an interface with two methods that allow combining evaluations into a chain in the same way as done in the promise chain example. The promises themselves also illustrate the monadic interface implementation.
// Example of a monad used to generate pseudo-random values;
// parameter А is the type of generated value
class Random<A> {
// Creation of Random using a random valueе
static of<A>(value: A): Random<A> {...}
// Method used to implement the call chain
chain<A, B>(this: Random<A>, then: (a: A) => Random<B>):
Random<B> {...}
}
declare function randomNumber(min: number, max: number):
Random<number>;
declare const randomString: Random<string>;
// Example of using the monad chain
const randomUser: Random<User> = randomString.chain(
userName => randomNumber(12, 90).chain(
userAge => Random.of({ name: userName, age: userAge })
)
);
Among other applications of monads in purely functional languages, such as Haskell, is the side effect encapsulation. As it’s not possible to make a database query, read a file or even print a line in the standard output in these languages by calling ordinary functions, monads are used to perform these actions. At the same time, their application goes beyond side effects – the monadic interface is universal and allows writing generic, laconic, high-level code, which is why monads are used everywhere in Haskell. Beyond Haskell, monads themselves are not so widely used, but their influence can be seen primarily in programming using promises and in the async-await construct, which we’ll talk about below.
Async
Getting back to the examples of code with promises, you can notice that, despite all the advantages of promises, call chains look no better than callbacks. The async-await syntactic structure allows taking it a step further and improving the code with the promise chain, turning it into something much like some code with blocking calls.
const getJson = url => fetch(url).then(resp => resp.json());
// Sending 2 serial queries
async function getUserInfo() {
const userId = await getJson('/current-user-id');
const userInfo = await getJson(`/user-info/${userId}`);
console.log(`Hi ${userInfo.firstName}, your id is ${userId}`);
};
The emergence of async-await can be traced back to the research devoted to functional programming in Haskell and ML, which gave rise to the async workflows in F# (2007) and then C# (2011).
Conclusions
Programming languages move on and develop actively, accumulating new, ever more advanced and convenient tools. As you can see, popular languages such as Python and С++ are acquiring a growing number of features, that originated from functional programming. More recent languages such as Scala and Kotlin, have supported functional tools from their outset.
It turns out that functional programming is much closer to home than you might think at first, even if you develop in C++ or Java!