On functional programming

Functional programming is often associated with languages that have features like:

1. Anonymous functions - the function (arg1) {...} style callbacks of JavaScript or the lambda of Python.
2. Lazy evaluation - Python's generator expressions (2*i for i in list1) which are iterators that compute new values only when required.
3. Higher order functions - functions that take other functions as arguments and/or return functions. For example, the famous map and reduce, and others like filter, scan, etc.

However, the distinguishing feature of functional programming is the use of pure functions. The following Python code gives examples of pure and impure functions:

def pure_func(x):
    return 2*x

def impure_func1(list1):
    list1.append(5)
    return list1[0]

def impure_func2(x):
    print(x)
    return 2*x

Pure and impure functions differ in that with pure functions, some thing like

x = func(a)
y = func(a)
z = func(a)

can be replaced with an equivalent

x = func(a)
y = x
z = x

This is not possible with impure functions, as must be clear from the above examples. Functional purity, also called referential transparency, seems to limit what functions are allowed to do. However, it gives very useful guarantees to someone reading and modifying the code. It tells you that a function takes some arguments as inputs and computes some value without any "side-effects". It greatly simplifies understanding how different pieces of code are connected to each other. Pure functions have much simpler semantics. You just substitute symbols for their values and evaluate the function - there is no notion of some memory that is being updated over time. In fact, there is no notion of time itself. Computations are ordered only by dependency.