Basic Program Designing Styles

There are mainly 3 styles when we design a computer program:

• Procedural Programming

  a programming paradigm, derived from structured programming, based upon the concept of the procedure call. Procedures, also known as routines, subroutines, or functions, simply contain a series of computational steps to be carried out.

• Object-Oriented Programming

  a programming paradigm based on the concept of “objects”, which may contain data, in the form of fields, often known as attributes; and code, in the form of procedures, often known as methods.

• Functional Programming

  a programming paradigm — a style of building the structure and elements of computer programs — that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.

Most of our readers are probably familiar with Procedural Programming and Object-Oriented Programming, as they are the programming styles that most programmers/computer science students have to learn. However, I guess that most of you may not know much about Functional Programming, which has actually become increasingly popular recently. In this post, I will talk about some basic but interesting concepts of Functional Programming with some example in Haskell, a purely functional programming language.

Function and Lambda Calculus

Lambda Calculus is a theoretical framework used to define the meaning of computation in many functional programming languages, such as Haskell, Agda, Idris, etc. There are two broad kinds of lambda calculus: untyped and typed.

Lamdba calculus includes three different types of expressions, i.e.,

E :: = x   (variables)
​
 | E1 E2   (function application)
​
 | λx.E    (function creation)

Where λx.E is called Lambda abstraction and E is known as λ-expressions.

For details like beta-reduction, alpha-conversion, etc., please see this article.

Higher-order Function

In Procedural Programming or Object-Oriented Programming style, functions usually take parameter(s) which can be an object, a pointer, or an value, and the functions may return a value or an object. However, in Functional Programming, we can take functions as parameters and return functions as return values. A function that does either of those is called a higher order function.

Let’s look at a simple example in Haskell:

sumTen :: Int -> Int
sumTen x = x + 10
​
hof :: (Int -> Int) -> Int
hof fn = 2 * fn 20
​
hof sumTen
hof (\x -> x + 10)

The function hof has been declared in line #4 and takes another Int -> Int function as a parameter (fn). Into the hof body (in line #5), the fn function (Int -> Int, which hof received) is called with an Int argument (20), and we can got the returned Int value. Then, we perform fn = 2 * fn (in this case, fn equals to the returned Int value). Finally, we return an Int value which is the result of fn = 2 * fn. In order to use the hof function, we call it and pass the sumTen function (in line #7), or even pass a lambda function (in line #8), in both cases the result was 60.

Most modern programming languages support this feature (Reference). For example, in many functional programming languages, the map function takes a function f and a collection of elements as arguments, and as the result, returns a new collection with f applied to each element from the collection.

Lazy Evaluation

Haskell is a programming language that uses lazy evaluation strategy (or call-by-need), which means that expressions are not evaluated when they are bound to variables, but their evaluation is deferred until their results are needed by other computations. This can improve processing speed by reduce useless computation when solving some algorithm problems like dynamic programming or quick sort.

The best example to explain this strategy is the use of infinite lists:

infiniteNum :: Int -> Int
infiniteNum n =  inf !! n - 1
    where inf = [1..]
​
infiniteNum 10
infiniteNum 100000
...

Lazy evaluation can create calculable infinite lists without infinite loops or size matters interfering in computation. Theoretically, the return value of the function infiniteNum contains an infinite list of elements. However, when we execute it, it does not run out of memory, because Haskell will only evaluate to 10 or 100000, and does not care about the remaining infinite elements.

Basically most programming languages use strict evaluation as their default strategy. However, some of these languages also support lazy evaluation and we can use it manually (Reference). Please note that lazy evaluation may also have some side effects, so please be careful.

Functor and Monad

They are considered to be the basic mathematical foundation of functional programming, they both provide some tool to wrapped input, returning a wrapped output.

Functor

In Haskell, functor is a typeclass, all types that have container properties can be considered as functors. Let’s look at a example:

fmap :: (Int -> String) -> [Int] -> [String]

The fmap function takes two arguments (Int -> String) and [Int] . Where:

• (Int -> String) is a function which accepts Int and returns String.
• [Int] is a container type which contains Int.
• [String] is the return value of the fmap function, which is a container type contains String.

In this example, fmap accept a function that maps Int to String, then apply the mapped function to the wrapped Int array, finally return the result (a String array).

Monad

Functors apply a function to a wrapped value, applicatives apply a wrapped function to a wrapped value. Monads apply a function that returns a wrapped value to a wrapped value. Monads have a function >>= (we call that “bind”) to do this.

For example:

class Monad m where
    (>>=) :: m a -> (a -> m b) -> m  b

For details, please see Functors, Applicatives, And Monads In Pictures.

Functional Programming and Programming Languages

For purely functional programming language, we mainly have Lisp-family (Clojure, Emacs Lisp), ML-family (OCaml, F#), Haskell, Idris, etc..

In fact, most commonly used programming languages like Java, Rust, C++, TypeScript, etc., have adopt lots of idea from functional programing (though some implementations are considered not to be pure).

Other Useful Information

Why functional programming matters

Functional programming in TypeScript

SICP lecture materials

Haskell tutorial for beginners