3

I come from an object oriented programming background, therefore, I am pretty curious about the core philosophy of functional programming? Why does it exist at the first place, and what types problems it is trying to solve?

2

3 Answers 3

9

Introduction

Functional programming is a broad tent and so I don't think there is a single answer here. Rather, functional programming is a confluence of several ways of thinking about what a program is each with separate historical roots. I'll talk briefly about three, with an acknowledgment that the boundaries can get a little hazy.

Sources of "Functionalness"

Computation as Evaluating Equivalences

In the earliest computational models (Turing machines, Von Neumann machines) and their actual implementation, a program was treated as a set of rules for manipulating a state. For example, a Turing machine is a set of rules for writing and moving along a tape. There is in these systems a well defined and linear ordering of states such that one can think of the execution of a Turing machine as a temporal process (this temporality is part of what makes physical implementation of a Von Neumann machine natural).

Alonzo Church in studying the mathematical notion of computability, introduced the lambda calculus. This defines a simple language of variables, function (or lambda) abstraction and applications. For example it allows defining terms like (\x.x) which we can informally read as "a function that given x yields x" or "the identity function". Its semantics are given by equivalence relations between terms. For example we can say that (\x.x) and (\y.y) represent equivalent terms (so-called alpha-equivalence) or that ((\x.x)(\x.x)) and (\x.x) represent equivalent terms (so-called beta-equivalence). But these equivalence relationships don't have a natural sense of order and so do not yield any time-bound notion of execution. To make this clear consider ((\y.(\x.x))((\t.(t t))(\t.(t t)))). Here we have two applications of functions, namely (\y.(\x.x)) and ((\t.(t t))(\t.(t t))) that we could take the beta-equivalent of. If we choose the former, going from outside-in, we simplify to (\x.x) but if we choose the latter and go inside-out we get right back to ((\y.(\x.x))((\t.(t t))(\t.(t t)))) [exercise: prove this]. The point is that the lambda calculus does not define a system of computation but you actually have to overlay some rules about traversing the graph of these equivalence relations to get a linear execution model.

In this model, a program is just a collection of definitions and an interpretation of a program is just a way of expanding out those definitions and simplifying by substituting equivalents for equivalents. Actually implementing such programs was pioneered by LISP -- which is clearly inspired both in its syntax and its method of using functions as a primary method of abstraction.

One fundamental flaw in the lambda calculus as a framework for studying computation is that it is unsound (https://en.wikipedia.org/wiki/Curry%27s_paradox). This is not so bad when we think of it in terms of actual programming, as all that means is that we can have programs that never halt. As a solution to the problem in mathematics, Church introduced the simply-typed lambda calculus. This brings us into our next section

Types and Programs as Proofs

Logic itself is much older than computation and modern propositional logic developed shortly before and greatly influenced computer science (it was pioneered by such luminaries as Frege and Russel in the 1890's and early 1900's while Church and Turing were producing their seminal work in the 30's and 40's). One of the revolutionary and highly controversial ideas ideas that came out of Intuitionistic logic pioneered by Brouwer and Heyting is that logic was not in the business of studying truth and falsity (whatever those might be) but in the business of finding proofs and disproofs. In some such systems proofs become first class objects and implications become transformations of proofs. So we might have some proof p of, say, that 2 = 2 and we chain that with a transformation inc which says that n = n -> n + 1 = n + 1 to get inc(p), a proof that 3 = 3. When we start applying these ideas to our programming languages, we come out with two ideas:

  1. Objects can be proofs and types can be propositions.
  2. Type systems are therefore equivalent logical systems and so we can use logic to guide our types.

The use of the first of these is most obvious in languages like Agda and Idris where programs so often really are proofs, but even in functional languages where this is less the case, basic propositions can inspire basic functions and their compositions -- e.g. with the basic fact of "If P, Then P" inspiring the identity function and "If P implies Q and Q implies R, then P implies R" giving function composition. And the second of these encourages the development of languages with different type features, such as sum types, union types, higher kinded types and yes dependent types, and most crucially make types more about meaning than storage location.

Our first notion of programs as systems of equivalences provides us with functional abstractions and our second notion of programs as proofs gives us a sense of our programs having well-defined meanings, there is still a lot of meat left to go on the bones:

Programs as Algebras

All of these sources are rooted in one way or another with very abstract mathematics, and there is one subfield of this abstract mathematics that we have not touched, namely abstract algebra. Abstract algebra takes the features of particular algebras (numbers, vectors, matrices, strings) and, well, abstracts them: forgetting the particularities of those domains while remembering the basic properties and relationships of operations over those objects. So we might notice that addition of numbers is associative (e.g. 2 + (3 + 4) = (2 + 3) + 4) and that concatenation of strings is associative (e.g. "Hello" + (" " + "World") = ("Hello" + " ") + "World") and study the features of associative relationships.

Now I think this field of mathematics has exerted a more passive influence over functional programming (though occasionally it has been more explicit -- one only needs to look at Haskell's type classes to see that), but I think this view of objects as fundamentally participants in algebras and as abstraction over algebras as a fundamental method of achieving genericity is an important part of functional programming. For example it is primarily in this sense that APL can be considered a functional language.

The What of Why of Functional Programming

What counts as a functional program then to me is one that participates in one or more of the sources:

  1. It is written out of functional abstractions where evaluation becomes a matter of expanding out definitions (referential transparency is a big watchword here). Functions are basic building blocks and methods of abstraction.
  2. The semantics of the programs are there in the types. Types are used to guide correctness rather than execution.
  3. Objects are treated not as things stored in memory, but as values that participate in algebras. Polymorphic behavior is achieved by functional abstraction over algebras rather than object oriented delegation.

Hopefully the short history I provided indicates that Functional programming is not some unified thing that someone thought up and advocated for but it is a mush of different but somewhat related ways of thinking about programming that emerged in complicated ways from mathematics and its intermingling with Computer Science. It is not, as the question states, something that evolved in order to solve particular problems or sets of them. Rather it evolved naturally over times.

Nevertheless, it is enjoying popularity right now for a number of reasons:

  1. Functional and algebraic abstractions are wonderful ways of expressing reusable algorithms.
  2. "Functional" type systems provide effective ways of expressing semantics and enforcing some level of correctness.
  3. Features that are consequences of the above three such as referential transparency and immutability of objects benefit both readability and often performance of large systems (e.g. by making multithreading simpler and eliminating copying through sharing).

In this analysis functional program is more about how one thinks about programs than the language and technology used (though of course some languages like Haskell support those ways of thinking about programs much more so than a language like C -- so the term "functional programming language" is not meaningless). It is one with benefits, especially in the world of large, concurrent systems, but it also does not have to be a strait-jacket.

0
1

The basic idea is that looking at programming through the lens of pure functions and immutable data is simpler and more elegant.

A pure function just takes its inputs and produces an output, with the output for a given input always being the same, and no side effects. This simplifies how we can think about functions, since we can think of any given (pure) function call as its output value.

Immutable data is also simpler than mutable data. It can't be changed by some other part of the program, potentially pulling the rug out from under us.

In OO (if you're using mutable objects) you may have to worry about what state other objects are in, or the exact state of several particular variables in the midst of some complicated bit of control flow, or in what exact order you updated several objects and/or variables. Not in purely functional programming. For a pure function, the rest of the program is irrelevant; the only things that are relevant are the body of the function and the values of the inputs. And, if you call another pure function within the body of the function, how that other function works is irrelevant; all that matters is what it does.

There are also a number of elegant features in FP, such as higher order functions, lambdas, and list comprehensions, that make programming easier. Many of these are getting imported into many of the more mainstream OO languages.

Of course, this is a slightly rosy way of looking at it, since it assumes that completely disallowing side effects and mutation is always a good idea without exception. In reality, mutation is sometimes needed from a practical point of view, because it is more efficient or easier to reason about for some problems, and no program can actually do anything useful in the real world without any side effects. That said, you can get a surprising amount of stuff done without side effects or mutation, and even the purest of FP languages has some way of allowing these things.

FP isn't trying to solve any particular problem, any more than OOP is restricted to simulations only.

0
1

That unconstrained assignments are bad.

Some may point you to pure functions that are free of side effects whose return value is completely predictable from it's input and leaves state of the rest of the universe unchanged. But functional programming is more than that.

Monads can be considered pure but they also provide a place impure code can be placed nicely walled off from the rest of your code making reasoning about code behavior easier.

Functional languages aren't the only way to take advantage of a functional philosophy. I write better code in java when I work to keep objects immutable. A philosophy I learned studying functional programming.

The problems it's trying to solve have to do with time. Functional programming takes a very formal attitude when it comes to side effects. Transactions, parallelism, threads, all run into problems because of time. Functional programming can't stop time but is one of the best methodologies to put time in a box so your can predict what your software will do.

When compared with object oriented programming you'll find a clear advantage in functional languages with how easy it is to add new behavior. It comes with a clear disadvantage in that adding new data types is hard.

Not every language forces you to chose one style but it's very hard to code to both at the same time. The choice then should be based on the change you anticipate.

4
  • 1
    Monads are pure. Remember that lists and Maybe/Option types are monads, for example. Even the IO Monad from Haskell, which you're likely thinking of, can be considered pure. But even if you're unconvinced about IO, surely you'll agree a list is both a monad and pure :)
    – Andres F.
    Jan 22, 2017 at 1:12
  • @AndresF. from a certain point of view you're right. But when I'm in a functional environment with the need to do something I know isn't pure the monad is what I turn to because it can, in a pure way, construct something that does impure things for me. That's what provides that wall I was talking about. Jan 22, 2017 at 3:21
  • @CandiedOrange Just to clarify: you're talking specifically about the IO monad, right? Because there are plenty of other monads, and all of them are indisputably pure.
    – Andres F.
    Jan 22, 2017 at 3:40
  • 2
    @CandiedOrange: The impurity is a property of the IO type in general. The fact that the IO type happens to be modeled as a monad is unrelated to its impurity. In other languages, the IO type is not a monad, e.g. in Clean. Jan 22, 2017 at 4:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.