Functional programming, in its “purest” sense,
is rooted in how functions, variables, and values actually work in mathematics,
which is different from how they typically work in most programming languages.
In functional programming, programs are executed by evaluating expressions, in
contrast with imperative programming where programs are composed of statements
which change global state when executed. Functional programming typically avoids
using mutable state.
Haskell Curry (for whom the Haskell language is
named) helped develop Combinatory Logic, which provides an alternative
theoretical basis for computation. Combinatory Logic examines how combinators,
which are essentially functions, combine to represent a computation. They are
useful for representing the steps in a planned/building blocks of computation,
which can be analyzed for possible bugs and optimization
opportunities.
History
The first language to incorporate functional
programming ideas was Lisp, which was developed in the late 1950s and is the
second-oldest high-level programming language, after Fortran. The ML family of
programming languages started in the 1970s, including Caml, OCaml (a hybrid
object-functional language), and Microsoft’s F#. Perhaps the best known
functional language that comes closest to functional “purity” is Haskell, which
was started in the early 1990s. Other recent functional languages include
Clojure and Scala, both of which run on the JVM but are being ported to the .NET
environment.
Basic Principles of
FP
Avoiding Mutable
state –
X2 +
Y2 = Z2
If I give you values for the variables x and y,
say X=3 and Y=4, you can compute the value for Z (5 in this case). The key idea
here is that values are never modified. It would be crazy to say 3++ (X++), but
you could start over by assigning new values to the same variables.
Why should we avoid mutating values?
i. Allowing mutable values is what
makes multithreaded programming so difficult. If multiple threads can modify the
same shared value, you have to synchronize access to that value. If you make a
value immutable, the synchronization problem disappears. Concurrent reading is
harmless, so multithreaded programming becomes far easier.
ii. Immutable values relates to program
correctness in other ways. It is harder to understand and exhaustively test code
with mutable values, particularly if mutations aren’t localized to one place.
Some of the most difficult bugs to find in large systems occur when state is
modified non-locally, by client code that is located elsewhere in the
program.
Defensively copying objects could be an option
to mimic Immutability but this could prove to be an expensive operation as and
when objects become large for example, large list of Orders. What happens when
the list of orders is supposed to change, but it has become huge? Should we
relent and make it mutable to avoid the overhead of making big copies?
Fortunately, we have an efficient way to copy large data structures; we’ll reuse
the parts that aren’t changing.
Functional programming encourages us to think
strategically about when and where mutability is necessary. If we encapsulate
mutations in well-defined areas and keep the rest of the code free of mutation,
we improve the robustness and modularity of our code. We still need to handle
mutations in a thread-safe way. Software Transactional Memory and the Actor
Model give us this safety.
Functions as First Class
values –
In OOPs, we are accustomed to passing objects
and primitive values to methods, returning them from methods, and assigning them
to variables. This means that objects and primitives are first-class values in
OOPs. A function is more general to method. It is not attached to any
particular class or object. Therefore, all instance methods are functions where
one of the arguments is the object. For example, in java you can’t pass a
method as an argument to another method, return a method from a method, or
assign a method as a value to a variable.
Lambdas
and Closures –
The term lambda is another
term for anonymous function. It comes from the use of the Greek lambda symbol λ
to represent functions in lambda calculus. JDK8 will introduce a syntax for defining anonymous functions. Here is what
the planned syntax looks like:
public FunctionalHelloButtonApp() {
button.addActionListener(
#{
ActionEvent e -> System.out.println("Hello There: event received: "+e)
}
);
}
A closure is formed when the
body of a function refers to one or more free variables, variables that aren’t
passed in as arguments or defined locally, but are defined in the enclosing
scope where the function is defined. The runtime has to “close over” those
variables so they are available when the function is actually executed, which
could happen long after the original variables have gone out of scope! Java has
limited support for closures in inner classes; they can only refer to final
variables in the enclosing scope. For example,
scala> var more =
1
more: Int = 1
scala> val addMore = (x: Int) => x +
more //
addMore: (Int) => Int =
<function>
High
Order Functions –
Functions that take other functions as
arguments or return them as results. They are powerful tools for building
abstractions and composing behavior. Higher-order functions allow nearly
limitless customization of standard library types, like Lists and Maps, and also
promote reusability. Here is a function apply which
takes another function f and a value v and applies function f to v:
def apply(f: Int
=> String, v: Int) = f(v)
For example,
class
Decorator(left: String, right: String) {
def layout[A](x: A) = left + x.toString() + right
}
object FunTest
extends Application {
def apply(f: Int => String, v: Int) = f(v)
val decorator = new Decorator("[",
"]")
println(apply(decorator.layout, 7))
}
Side effect free
Functions –
Another source of complexity, which
leads to bugs, are functions that mutate state, e.g., setting values of an
object’s field or global variables. In mathematics, functions never have side
effects, meaning they are side-effect-free. For
example, no matter how much work sin(x) has to do, its entire result is returned
to the caller. No external state is changed. Being able to replace a function
call for a particular set of parameters with the value it returns is called
referential transparency.
Side-effect-free functions make
excellent building blocks for reuse, since they don’t depend on the context in
which they run. Compared to functions with side effects, they are also easier to
design, comprehend, optimize, and test. Hence, they are less likely to have
bugs.
Recursion –
Functional programming in its purest form
doesn’t allow mutable values. That means we can’t use mutable loop counters to
iterate through a collection! For example,
for(int i=0; i
< size; i++)
The classic
functional alternative to an iterative loop is to use recursion, where
each pass through the function operates on the next item in the collection until
a termination point is reached. Recursion is also a natural fit for certain
algorithms, such as traversing a tree where each branch is itself a
tree.
However, each
recursion adds a new frame to the stack, which can exceed the stack size for
deep recursions. Tail-call recursions can be
converted to loops, eliminating the extra function call overhead. Unfortunately,
the JVM and the Java compiler do not currently perform this optimization (for
details click
here).
Declarative
v/s Imperative Programming –
Finally, functional programming is
declarative, like mathematics,
where properties and relationships are defined. The runtime figures out how to
compute final values. The definition of the factorial function provides an
example:
Factorial(n) = 1 if n=1
n * factorial(n-1) if n > 1
Object-oriented programming is primarily
imperative, where we
tell the computer what specific steps to do. For example,
public static long
declarativeFactorial(int n) {
assert n > 0 : "Argument
must be greater than 0";
if (n == 1) return
1;
else return n *
declarativeFactorial(n-1);
}
public static long
imperativeFactorial(int n) {
assert n > 0 : "Argument
must be greater than 0";
long result =
1;
for (int i = 2; i<= n; i++)
{
result *= i;
}
return result;
}
Declarative programming is made easier by
lazy evaluation, because laziness gives the runtime the opportunity to
“understand” all the properties and relations, then determine the optimal way to
compute values on demand.
Add a comment