Functional programming is a programming paradigm. The common programming paradigm includes Imperative programming, functional programming, and logical programming. The common object-oriented programming is also Imperative programming.
Imperative programming is an abstraction for computer hardware, with variables (corresponding to storage units), assignment statements (get, store instructions), expressions (memory references and arithmetic operations), and control statements (jump instructions). In short, an imperative program is a sequence of instructions on a Von Neumann machine.
Functional programming, on the other hand, is a mathematically oriented abstraction that describes computation as an expression evaluation. In a word, a functional program is an expression.
Nature of Functional Programming The term function in functional programming does not refer to functions in computers (actually subroutines), but rather functions in exponentials, i.e. mappings of independent variables. That is, the value of a function depends only on the parameters of the function, not on other states. For example, SQRT (x) computes the square root of x, and as long as x doesn’t change, it doesn’t change whenever it’s called, how many times it’s called.
In functional languages, functions, as first-class citizens, can be defined anywhere, inside or outside a function, as arguments and return values to a function, and can be combined.
A variable in a purely functional programming language is not a variable in an imperative programming language, which is a unit of state, but a variable in algebra, which is the name of a value. Values of variables are immutable, which means that it is not possible to assign a value to a variable more than once, as is the case in imperative programming languages. For example, in imperative programming languages we write “x = x + 1”, the fact that it depends on mutable state is true for programmers, but false for mathematicians.
In functional languages, such as conditional statements, loop statements are not control statements in imperative programming languages, but syntactic sugar of functions. For example, in Scala, if else is not a statement but a ternary operator that returns a value.
Strictly functional programming means programming without mutable variables, assignments, loops, and other imperative control structures.
In theory, functional languages do not run on the machines of the von Neumann architecture, but by the λ calculus, by substituting variables for their values or expressions, functions for their expressions, and computing according to operators. The λ calculus was Turing’s complete displacement, but for the most part, functional programs were implemented by compiling instructions in machine language.
Benefits of functional Programming Because imperative programming languages can also implement higher-order functions in a manner similar to function Pointers, the main benefit of functional programming is immutability. There is No mutable state, the function is Referential transparency and No Side Effect.
One advantage is that functions do not depend on or modify external states, and the result of a function call does not depend on the time and location of the call, making it easier to reason and less error-prone. This makes unit testing and debugging easier.
Another benefit of immutability: Due to the () between multiple threads do not share state, not cause resource contention (Race condition), also do not need to use the lock to protect mutable state, there would be no deadlock, so that we can better concurrency, especially under the symmetric multiprocessor (SMP) architecture to better use of multiple processors (nuclear) provide the ability of parallel processing.
(Photo: The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software)
The dark blue curve shows the increase in the clock cycle, which has been flattening out since 2005. Programming in a multi-core or multi-processor environment is difficult. The difficulty lies in the shared mutable state. In this context, this benefit is very important.
Because functions are referential transparent, and because functional programming does not focus on execution steps as imperative programming does, this system provides room to optimize functional programs, including lazy evaluation and union processing.
Another benefit is that because functional languages are mathematically oriented abstractions, closer to human language than machine language, the code is cleaner and easier to understand.
Features of functional programming
class Point(x: Int, y: Int){
override def toString() = "Point (" + x + ", " + y + ")"
def moveBy(deltaX: Int, deltaY: Int) = {
new Point(x + deltaX, y + deltaY)
}
}
Copy the code(Sample source: Anders Hejlsberg at echDays 2010)
Also because variables are immutable, loops cannot be implemented in purely functional programming languages, because a For loop uses a mutable state as a counter, whereas a While or DoWhile loop requires a mutable state as a condition For breaking out of the loop. The only way to solve iterative problems in functional languages is recursion, which makes functional programming heavily dependent on recursion.
Iterative
Recursive (recursive
)
public static int fact(int n){
int acc = 1;
for(int k = 1; k <= n; k++){
acc = acc * k;
}
return acc;
}
Copy the code
def fact(n: Int):Int= {
if(n == 0) return 1
n * fact(n-1)
}
Copy the codeAs you can see, there are no loops, no mutable state, shorter functions, no explicit use of the accumulator to hold intermediate results, but the argument n (allocated on the stack) to hold intermediate results. (Example source: 1. Recursion)
Of course, such recursive calls have higher overhead and limitations (call stack depth), so try to write the recursion as a tail recursion, the compiler will automatically optimize for a loop, not to expand here.
In general, recursion is thought to be more human than loops, telling machines what to do rather than how to do it. Handing back can have powerful implications, such as change.
The problem
def countChange(money: Int, coins: List[Int]): Int = {
if (money == 0)
1
else if (coins.size == 0 || money < 0)
0
else
countChange(money, coins.tail) + countChange(money - coins.head, coins)
}
Copy the code(Source: Interesting Scala language: Think recursively.) As you can see from this example, functional programs are very concise, describing what to do, not how to do it.
- Higher-order functions
- Partially Applied Functions
- Currying
- Closure
A higher-order function is one that takes a function as an argument or returns a function. With higher-order functions, you can reduce the granularity of reuse to the functional level, which is lower than in object-oriented languages.
def sumInts(a: Int, b: Int): Int =
if (a > b) 0 else a + sumInts(a + 1, b)
def sumCubes(a: Int, b: Int): Int =
if (a > b) 0 else cube(a) + sumCubes(a + 1, b)
def sumFactorials(a: Int, b: Int): Int =
if (a > b) 0 else fact(a) + sumFactorials(a + 1, b)
Copy the codeThe sum of the integers from a to b, the cubed sum of the integers from a to B, and the factorial sum of the integers from a to b.
All three functions are special cases of the following formula
The only difference between the three functions is f, so can we abstract a common pattern?
def sum(f: Int => Int, a: Int, b: Int): Int =
if (a > b) 0
else f(a) + sum(f, a + 1, b)
Copy the codeThe parameter f is a function in which the function f is called for calculation and summation.
def sumInts(a: Int, b: Int) = sum(id, a, b)
def sumCubs(a: Int, b: Int) = sum(cube, a, b)
def sumFactorials(a: Int, b: Int) = sum(fact, a, b)
def id(x: Int): Int = x
def cube(x: Int): Int = x * x * x
def fact(x: Int): Int = if (x == 0) 1 else fact(x - 1)
Copy the codeThis allows you to reuse the sum function to implement the summation logic in the three functions. (source: sample d396qusza40orc.cloudfront.net/progfun/lec…).
Higher-order functions provide a function-level dependency injection (or reverse control) mechanism. In the above example, the logic of the sum function depends on the logic of the injected function. Many GoF design patterns can be implemented with higher-order functions, such as Visitor, Strategy, Decorator, and so on. For example, the Visitor pattern can be replaced by the map() or foreach() higher-order functions of the collection class.
Functional languages often provide very powerful collections that provide many higher-order functions, making them very easy to use.
scala> val numbers = List(1, 2, 3, 4)
numbers: List[Int] = List(1, 2, 3, 4)
scala> numbers.map(x=>x*2)
res3: List[Int] = List(2, 4, 6, 8)
Copy the code(Example source: Programming Scala: Tackle Multi-core Complexity on the Java Virtual Machine)
Where x=>x*2 is an anonymous function that takes an argument x and outputs x*2. You can also see that functional programming focuses on what to do (x*2), not how to do it (using a loop control structure). Programmers don’t care if the elements in a list are evaluated front to back, back to front, sequentially, or in Parallel, as Scala’s Parallel collection does.
def fact(n: Int): Int = (1 to n).reduceLeft((acc,k)=>acc*k)
Copy the codeWhere (1 to n) generates a sequence of integers, while the reduceLeft() higher-order function simplifies the serialization by calling an anonymous function.
val file = spark.textFile("hdfs://..." ) val counts = file.flatMap(line => line.split(" ")) .map(word => (word, 1)) .reduceByKey(_ + _) counts.saveAsTextFile("hdfs://..." )Copy the code(source: sample spark.apache.org/examples.ht…).
The flatMap() and map() examples are identical to the methods of the same name in the collection class, where the map method argument is also an anonymous function that turns the word into a tuple. The people who write this function don’t care how the function is scheduled. In fact, the Spark framework does this calculation on a distributed cluster of multiple computers.
In addition, if you compare Hadoop’s implementation of word frequency statistics: WordCount – Hadoop Wiki, you can see some of the advantages of functional programming.
Inertia is evaluated
Lazy evaluation
call-by-need
scala> val x = { println("x"); 15 }
x
x: Int = 15
scala> lazy val y = { println("y"); 13 }
y: Int = <lazy>
scala> y
y
res3: Int = 13
scala> y
res4: Int = 13
Copy the code(Sample source: Scala – What does a lazy val do?)
As you can see, in Scala’s interpreter, “x” is printed when the x variable is defined, and “Y” is not printed when the y variable is defined, but when it is first referenced.
Functional programming languages also typically provide powerful Pattern matching capabilities. Algebraic data types can be defined in functional programming languages, and new data types can be formed by combining existing data types. For example, case class is provided in Scala, and the values of Algebraic data types can be analyzed by pattern matching.
Summary Functional programming is another toolkit for software developers, providing us with another way of abstraction and thinking.