Concepts of Functional Programming
What / Why / When
Functional Programming isn’t necessary for Azure Functions and AWS Lambda.
Imperative programs have the environment (state) and a sequence of steps manipulating that environment. Functional programs have an expression that is successively substituted until it reaches normal form.
- Programming paradigm
- Procedural (imperative) -> OO -> Functional
- C -> C# -> F#
Functional programming (often abbreviated FP) is the process of building software by composing pure functions, avoiding shared state, mutable data, and side-effects. Functional programming is declarative rather than imperative, and application state flows through pure functions. Contrast with object oriented & procedural programming, where application state is usually shared and colocated with methods in objects.
LISP: born 1958, based on Lambda calculus (λ) (*) - you don’t run a LISP program, you evaluate a LISP expression
Fibonacci function
(defun fib (n)
(if (or (= n 0) (= n 1))
n
(+ (fib (- n 1)) (fib (- n 2)))))
(fib 10)
(*) the set of logical axioms in the axiomatic method of logical deduction in first-order predicate logic
First-class and higher-order functions
HO functions are functions which can take other functions are arguments or return functions as a result.
In maths, differential operator d/dx
, which returns the derivative of a function f
.
HO functions allow curryings (partial application) which allows a technique that applies a function to its arguments one at a time, with each application returning a new function that accepts the next argument:
fn(a,b) => f(a)(b)
Pure functions
Pure functions (or expressions) have no side effects (memory or I/O). This means that pure functions have several useful properties, many of which can be used to optimize the code.
Pure function is a function which:
- Given the same inputs, always returns the same output, and
- Has no side-effects
Recursion
let rec factorial x =
if x <= 1 then
1
else
x * factorual (x - 1)
factorial 10
Tail=end recursion (such as above) allows for time / space optimisations.
Strict versus non-strict evaluation
print length([2+1, 3*2, 1/0, 5-4])
Lazy evaluation does not evaluate function arguments unless their values are required to evaluate the function call itself. Miranda & Haskell both use Lazy evaluation by default.
Type systems
I’m just going to pretend these don’t exists - believe me it’s easier. [Dependent types - Generalized Algebraic Data Types (GADT’s) ] - pretty soon you in Category Theory & my head hurts a little too much.
Referential transparency
Referential transparency (you can replace a function call with its resulting value without changing the meaning of the program). Functional programs do not have assignment statements, that is, the value of a variable in a functional program never changes once defined.
Not functional : x = x * 10
- value of x
is changed.
int plusone(int x) {return x+1;}
is transparent, as it does not implicitly change the input x
and thus has no such side effects.
Data structures
Arrays can be replaced by maps or random access lists, which admit purely functional implementation, but have logarithmic access and update times. Purely functional data structures have persistence, a property of keeping previous versions of the data structure unmodified.
Functional programming in non-functional languages
It’s possible to write
Fortran
in any programming lanuguage.
It’s also possible to write in a functional sytle in a lot of modern programming languages.