In this paper, starting from vivo Internet technology WeChat public links: mp.weixin.qq.com/s/EWSqZuujH… Author: Yang Kun

In the series on Writing High-quality Functions,

“How to write high-quality JS functions (1) — The” introduction to function execution mechanism, this article will explain how to write high-quality functions through JavaScript from the aspects of function naming, annotation and robustness.

“How to write high-quality JS functions (2) — Naming/commenting/Robustness” from the aspects of function naming, annotation and robustness, explains how to write high-quality functions through JavaScript.

“Before the word”

This is functional programming in a series of articles about writing high-quality functions. Let’s talk about how to use functional programming to improve the quality of your functions.

Functional programming is divided into two parts, which are theory and practice. This article belongs to the theory, in this article, I will through the background and questions, the nature of functional programming, purpose, context and other aspects of a clear exposition.

Writing logic

Through the elaboration of the development history of computer and programming language, find the era background of functional programming. Explore and feel the hidden nature of functional programming through the introduction of people strongly associated with functional programming.

Here is a brief list:

I. Background introduction

  1. The history of computers and programming languages

Two, functional programming 10 questions

  1. Why do functional languages exist? How did functional languages come about? What is the point of its existence?

  2. What is lambda calculus? What exactly does lambda say? What does lambda have to do with functions? Why the Lambda calculus system?

  3. Why should functional programming be implemented with functions?

  4. What does the word function mean in functional languages, or in functional programming? What is it capable of?

  5. What are the key features of functional programming?

  6. Are imperative and functional programming antithetical?

  7. According to FP thinking, you can’t use loops, so how do we solve that?

  8. Throwing an exception has side effects, but if you don’t throw an exception, what do you throw instead?

  9. Does functional programming not allow mutable state? How does our program express without side effects?

  10. Why does functional programming suggest eliminating statements?

Three, JavaScript functional programming 5 questions

  1. Why should this be avoided for functional programming

  2. Is JavaScript a functional language because its functions are first-class citizens? Why is JS a polymorphic language?

  3. Why can we use for loops inside JS functions?

  4. JS function is first-class citizenship is what consciousness? What is the purpose of this?

  5. What are the disadvantages of functional programming with JS?

Four,

  1. The future of functional programming.

After the brief introduction of the catalogue, please look down with me.

PS: I was like a child playing on the seashore, exulting now and then at picking up a smoother pebble than usual, or a prettier shell, while the sea of truth lay unexplored before me.

【 is wen 】

The history of computers and programming languages

The history of computers and programming languages has been dominated by humans, and it is important to understand the people who played a key role in this process.

Let’s take a look at some of the key superheroes.

I. David Hilbert



David Hilbert

Hilbert was called the uncrowned king of mathematics, a genius among geniuses.

The best thing about Hilbert, in my opinion, was that he encouraged the mechanization of proof, so that machines could deduce theorems from formal language.

It was his persistence that propelled formal language to the center of the stage of history.

Alan Matheson Turing



Alan Matheson Turing

Alan Matheson Turing is known as the father of computer science.

His greatest achievement, I think, was the invention of the Turing machine:



The diagram above is a model of a Turing machine.

One thing to note here: from the diagram, we can see that each square can store a number or a letter. This is important information for you to think about.

PS: I’ll see the connection when I introduce Von Neumann.

Alonzo Church



Alonzo Church

Alonzo Church, PhD supervisor of Alan Matheson Turing.

His greatest achievement is that he invented the calculus of lambda.



The figure above is the basic form of the lambda calculus.

Alonzo Church’s lambda calculus and Alan Turing’s Turing machine, together, have rewritten the history of formal languages in today’s world.

Thinking: Church’s calculus of λ and Turing’s Turing machine, what are the differences and connections between the two?

Von Neumann



Von Neumann

Von Neumann is known as the father of the computer.

He proposed the von Neumann architecture:



From the figure above, we can see that von Neumann architecture consists of arithmetic unit, controller, memory, input device and output device. Using binary logic, program storage, execution as the three principles of computer manufacturing.

Note one piece of information: as we know, the underlying instructions of the computer are composed of 0 and 1, and various calculation operations are performed through CRUD of 0 and 1. When we look at a Turing machine, we see that each of its little squares can store a number or a letter.

If you look at this, you see some connection between the von Neumann architecture and the Turing machine.

Yes, the modern von Neumann architecture is a computer structure based on a Turing machine model. Computer zeros and ones are special cases of numbers or letters in the Turing machine’s small squares.

Five, why mention these people

Because if you want to completely solve the puzzle of functional programming, it is necessary to understand the background of the era and the deeds of some key figures.

Six, the Church-Turing thesis

Church was Turing’s PhD supervisor, and there was a famous argument between them, the Churchy-Turing argument.

The general content of the thesis is: Of the two models of Turing and Lambda, is there any calculation that one model can express and the other model cannot?

So far, there is no answer to this question. Because of this, many people have confidence in the Lambda model. In the following years, the Lambda model has been studied, demonstrated and practiced by many people.

The birth of the first programmable computer



It’s called ENAIC.

In 1946, the world’s first electronic computer, ENIAC, was introduced. It could change the way it calculated, that is, it could change the program.

In other words: it’s a programmable computer.

Eight, why programmable

Larry Wall, who designed The Perl language, said that good programmers have three virtues: laziness, impatience, and arrogance.

Programmability perfectly illustrates the virtue of laziness. After the birth of ENAIC, a variety of programming languages appeared. The three virtues are also vividly drawn.

Classification of computer languages



The following information can be obtained from the figure above:

  1. Programming languages are just a category of computer languages.

  2. HTML and XML are data design languages.

  3. In programming languages, it is divided into declarative and declarative.

  4. In the explanatory formula, it also includes functional formula, logical formula and so on. MySQL, in fact, is a logical language, and it does this by asking questions.

  5. The von Neumann system is more in line with process-oriented languages.

This classification can take a good look, will have some feelings.

History of simple programming languages



The chart above is very straightforward, until 1995.

The timeline looks something like this: XXX –> XXX –>…. —> JavaScript …

Fast forward to 1996 and JavaScript is born!

JavaScript is Born!

1. Brandon Edge, the father of JavaScript



This guy’s name is Brandon Edge. That year, he was 34.

Take a look at a passage written by Ruan Yifeng



Here are a few things you can get from the picture above:

  1. First impression: Abramovich has no interest in Java.

  2. Second thought: Because he hated Java, ABU didn’t want to use Java’s object representation, so he borrowed Self and used prototype-based inheritance. Planted the seeds of object-oriented programming with prototypes in the front-end world a few years ago.

  3. Third feeling: ABU uses Scheme language for reference, elevates functions to first-class citizen status, and enables JS to have functional programming ability. Buried JS can be functional programming seeds.

  4. Fourth feeling: JS can be both functional programming and object programming.

3. My personal feelings

After reviewing the history and stories of programming languages, I don’t think JavaScript is a bad language, but rather it’s the middle ground that makes JavaScript so popular today.

Xii. Summary

Through the brief introduction of the development history and key figures of computer language, we can realize the potential and influence of functional programming in the development history of computer language from a high level.

However, through the introduction of background and characters, the understanding of functional programming is limited. I’m going to explain how functional programming works by asking questions.

10 questions of functional programming

The following will explain the theoretical support of functional programming, the birth background of functional programming, the core theory of functional programming and derivation through the answers of 10 questions.

Why do functional languages exist? How did functional languages come about? What is the point of its existence?

Functional languages exist to realize the essence of operational systems — operations.


1. Research on formal operation system

In the days before computers were invented, four big names — Alan Turing, John von Neumann, Kurt Godel, and Alonzo Church. The research of formal operation system is carried out.

To prove a proposition by means of formal systems: real systems can be expressed by simple mathematical laws.

2, Turing machine and von Neumann structural system defects

As can be seen from the above picture and analysis, both the Turing machine and the von Neumann system rely on memory for computing.

In other words: modify memory to reflect the results of an operation. It’s not really an operation.

Modifying memory is not what we want, we just want the computation. From a purposeful point of view, modifying memory can be a side effect of an computing system. Or it’s a way of representing the results of an operation.

Church, Alan’s PhD supervisor, saw what was going on. In order to realize the essence of the operation system – operation, that is, do not modify the memory, directly through the operation to get the results.

He proposed a formal system of lambda calculus, a theory that more closely approximates operations as essential.

The gap between functional and imperative languages

In terms of linguistic classification, there are two different types of computational paradigms.

In terms of hardware systems: they depend on different computer systems (i.e., hardware). The reason for relying on different hardware is that if you use a von Neumann computer, you have to modify the memory to do the computation. However, this contradicts the Lambda calculus system.

Because functional languages based on the lambda calculus system do not need registers, there is no need to use registers to store variable states. It’s all about the operation, and when the operation is done, the result will come out.

The biggest gap is the reliance on different computer systems.

4. Limitations of computer hardware

So far, it is technically impossible to do A computer system based on A paradigm and support B paradigm at the same time. That is, no instruction, logic, or physical design suitable for lambda calculus can be expected from the X86 instruction set.

Why, you might ask, can we do functional programming if the hardware doesn’t support it?

In reality, most people use the von Neumann system of imperative language. So in order to get special computing power and programming features. Languages virtualize an environment at the logical level, which is why multiparadigm languages like JS and scripting languages like PY are born.

The reason for this is that the computer system of the von Neumann system is based on storage and instruction systems, not arithmetic.

The light in the darkness

Church’s lambda calculus was not implemented by programming languages for a long time, given the limitations of the hardware available at the time.

It wasn’t until ten years after Von Neumann and others completed the EDVAC. John McCarthy, an MIT professor, became interested in Church’s work. In 1958, he unveiled LISP, a table-processing language. The LISP language is an implementation of Church’s lambda calculus.

The world’s first functional language was born.

LISP is the originator of functional languages, and has completed the implementation of Lamda calculus. Realizing operation is the essential operation system.



The image above is a Lisp image, to feel the charm of image symbols.

Why do I say dawn?

Because there is no real victory. LISP was still working on von Neumann computers, because that was the only system available.

So since LISP, functional languages have been run in interpreted environments, not compiled ones. The legendary scripting language, interpreter language.

The real victory

It wasn’t until 1973 that a group of programmers at MIT’s Artificial Intelligence Lab developed hardware called a LISP machine. Since then, Alonzo Church’s lambda calculus has finally been implemented in hardware. Finally, a computer (hardware) system can claim to support functional languages at the machine instruction level.

7,

I’ve explained a lot about this question, from the purpose of functional languages, to the difficult process of making functional languages, to the limitations of computer hardware. Finally, with constant efforts, it was possible to complete functional programming of computer systems based on von Neumann’s system through the interpreter. Pure functional programming can also be done on computers that support functional languages at the machine instruction level.

Question to consider: Think about why functional programming is becoming more and more understood and mastered today.

What is lambda calculus system? What exactly does lambda say? What does lambda have to do with functions? Why the Lambda calculus system exists

1. The purpose of the birth of LAMDA

Lambda is an operation scheme to solve the problem that the semantics of functions in mathematics are not clear and it is difficult to express the structural levels of functions clearly.

In other words, instead of using the functional operation form in functions, lambda operation form is used to carry out operations.

2. A brief introduction to LAMda

(1) A system for studying function definition, function application, and recursion.

(2) Functional language is based on lambda operation generated by the operation paradigm.

3. Theoretical foundation of functional programming

Lambda calculus system is a very important knowledge point for learning functional programming. It is the theoretical foundation of functional programming as a whole.

4. Functions in mathematics

As shown below:



From the mathematical function above, we can find the following:

  1. The argument for the given function is not displayed

  2. The distinction between definition and invocation is lax. X2 minus 2 times x plus 1 is both a definition of f(x) and a call to x minus 1 by g(x).

Experience the above points, we will find: mathematics function semantics is not clear, it is difficult to express the clear structure of the function level. The solution was provided by Church, who proposed the lambda(λ) calculus.

5. Lambda (λ) calculus

Basic definition form: λ< variable >.< expression >

A function defined in this way is called a lambda expression.

Lambda can be translated into functions, i.e. lambda expressions can be read as functional expressions.

PS: For example, functions in functional languages refer to lambda, which is different from function in common languages like C.

Chestnuts of a single variable

λx.x2-2*x+1 is a λ expression, which explicitly states that x is the variable. When applying this λ expression definition to specific variable values, you need to enclose the expression in a pair of parentheses, as shown when x is 1:

(lambda 7.0.x.x 2-2 * x + 1) 1

Apply (or call) the procedure, which assigns the value of a variable to the expression x and removes λ < variable > as follows:

(lambda 7.0.x.x 2-2 * x + 1) = 1-2 * 1 + 1 = 0

7. Chestnut with multiple variables

In the expression λx.λy.x+y, there are two variables x and y respectively.

When x=1, y=2 the expression is called as follows:

(λ.λy.2*x+y)1)2 = (λy.2+y) 2 = 4

From the above, we can see that in the invocation of lambda expressions, parameters are executed in order, and can feel the taste of Corrification and composition.

In other words, since functions are expressions, expressions are values. So the return value of a function can be a function, and the call execution continues, and so on.

In this way, the hierarchy of different functions is solved, and higher-order functions are used. In functional programming languages, this rule holds when functions are first-class citizens.

8, summary

Having said that, we have a clear understanding of functional programming fundamentally. Such as its mathematical basis, why it exists, and how it is fundamentally different from imperative languages.

The Lambda calculus system proves that any computable function can be expressed and evaluated in this form, which is equivalent to a Turing machine.

At this point, I’ve explained why functional languages come into being. And the origin and basic content of lambda calculus system, an important theoretical support for functional language.

Why should functional programming be implemented with functions

As mentioned above, the essence of an computing system is arithmetic.

Function is just a means to encapsulate the operation, function is not the real essence, the real essence is the operation.

A,

Having said that, we have a clear understanding of functional programming fundamentally. Such as its mathematical basis, why it exists, and how it is fundamentally different from imperative languages.

What is the meaning of the word function in functional languages or in functional programming? What is it capable of?

1. The meaning of the word function

This function specifically refers to lambda expressions that satisfy the lambda calculus. Functional expressions in functional programming are also called lambda expressions.

This function has four capabilities:

  1. You can call

  2. Is the operator

  3. You can save data inside a function

  4. Operations inside the function have no side effects outside the function

2. Operand

In JS, functions are also operators, but their operations are only calls.



3. The function saves data internally



The existence of closures makes it possible to store data within functions. Function execution, data in different closures, do not affect each other, just as different instances of the object have their own selfish data. There are no class members that can be shared between multiple instances.

4, summarize

As you can see from this question, instead of a language that supports functions, a language can be called a functional language, or a language with functional programming capabilities.

Three, what are the characteristics of functional programming keywords?

To outline it:

References transparency, purity, no side effects, idempotent, lazy/non-lazy evaluation, composition, Coriation, pipes, high-order, closures, immutability, recursion, partial Monad, Monadic, functor, Applicative , tail recursion, strict/non-strict evaluation, infinite flow and co-recursion, state transition, PointFree, first-class citizen, implicit/explicit programming, etc.



1. Referential transparency

Definition: An expression in any program that complies with reference transparency may be replaced by its result without changing the meaning of the program.

Meaning: Make code with better derivation, can be directly translated into results.

For example, in the process of converting TS to JS, if the expression has reference transparency. So at compile time, you can calculate the result of the expression in advance, and then directly into the value, while JS is running, the execution time will be reduced.

2. Purity

Definition: Returns the same output for the same input.

Advantages:

  1. testable

  2. No side effect

  3. You can parallel code

  4. Can be cached

3. Lazy evaluation and non-lazy evaluation

Definition: a parameter is lazily evaluated if it is not evaluated until it is needed. Otherwise, it is non-lazy evaluation.

(1) Lazy evaluation:

true || console.log(Source Terminator)Copy the code


Features: When the result of subsequent expression is no longer needed, it terminates subsequent expression execution, which improves speed and saves resources.

(2) Non-lazy evaluation:

let i = 200
console.log(i+=20, i*=2, 'value: ' + i)
console.log(i)Copy the code


Features: A waste of CPU resources, there will be uncertainty.

4. Pointfree — Implicit programming

The function does not need to mention what data it will manipulate. That is, the function does not specify the parameters of the operation, but lets the function that combines it handle the parameters.

Typically, a Currie sum is used to implement pointFree.



5, combination

(1) No combination:



(2) Situation after combination:



See my actual combat later, I will introduce the role of combination through examples.

6. Corrification



7. Advanced knowledge of functional programming — Functor, Applicative, Monad



Typescript layout solutions Functor, Applicative and Monad

Any one of these advanced points is enough to explain a long time, but I’m not going to explain it here. I recommend an article that is very thorough.

I have some personal opinions about these three advanced knowledge points.

  1. Number one: Don’t be intimidated by nouns, just type code to feel the difference.

  2. Second: since you want to understand the high-level knowledge of functional languages, it is necessary to get rid of the inherent ideas of imperative languages as much as possible, and then to understand these high-level knowledge.

  3. Number three: Why are there these advanced knowledge points in functional programming?

On the third point, my personal feeling is that functional programming requires you to change your implicit programming style to an explicit one. This means that you have to spend a lot of time on the input and output of the function.

How to solve this problem?

This can be done with the advanced knowledge mentioned above. In a particular scenario, such as IO, you don’t need to list all the possibilities, just go through an abstract process that does not throw exceptions.

They all serve the same purpose, reducing the amount of duplicate code and improving code reusability.

8, summary

I did not answer your question in detail. What I want to say is:

These characteristics of keywords, are worthy of careful study, here I only introduced I think the point of attention, specific knowledge points, we go to understand and study.

Are imperative programming and functional programming antithetical?

From some of the previous statements, imperative programming and functional programming are not antithetical. They can exist independently and symbiotically. And in the case of symbiosis, it exerts greater influence.

In my opinion, multi-paradigm languages are king in the world of programming, and a programming language that supports only one paradigm cannot accommodate multiple scenarios.

Five, according to THE IDEA of FP, can not use the cycle, then how should we solve?

For purely functional languages, loops cannot be used. As far as we can think of, we can use recursion to implement loops, recalling the lamda calculus system mentioned earlier, which is a system for studying function definitions, function applications, and recursion. So as a functional language, it’s ready to use recursion to do everything in a loop.

Throwing an exception can cause side effects, but if you don’t throw an exception, what should you do instead?

At this point, we need to change our mindset: in imperative languages, for example, we usually use try catches to catch exceptions thrown. But in purely functional languages, there is no try catch, and functors are usually used instead.

You might wonder why a functor is used instead of a try catch.

Confusion is normal, and the main reason is that we understand functional languages from the theoretical foundations of imperative languages.

If we stand on the theoretical foundation of functional language understanding, there will be no confusion. You will find that it is reasonable and appropriate to implement loops only recursively, with no try catch requirements, etc.

PS: It’s as if someone who has been using a functional language for a long time suddenly gets confused by an imperative language.

Does functional programming not allow mutable state? How does our program express without side effects?

You can use local mutable state, and as long as the local variable does not affect the outside, you can say that changing the function as a whole has no side effects.

Why does functional programming suggest eliminating statements?

Because the essence of a statement is: to describe the logic of an expression evaluation, or to assist expression evaluation.

5 questions about JavaScript functional programming

Why should this be avoided in functional programming

There are two main reasons:

  1. JS this has multiple meanings and complex usage scenarios.

  2. This does not depend on the code inside the function.

    All data should be supplied to functions as arguments, and this does not follow this rule.

Is it possible to use for loops inside JS functions?

A lot of people probably haven’t thought about it

In a purely functional language, there are no loop statements. Loop statements need to use recursion, but JS recursion performance is not good, such as no tail recursion optimization, so what to do?

In order to support functional programming, it is necessary to avoid the recursive performance problems of JS. Finally, for loops are allowed inside functions, and you’ll see implementations of forEach, Map, filter, and reduce all encapsulate for loops. We still use the for loop internally.

PS: In JS, as long as the for loop inside a function does not affect the outside, it can be regarded as reflecting the purity.

Third, JS function is a first-class citizen is what consciousness? What is the purpose of this?

I summed it up, probably have the following consciousness:

  1. An immediate quantity that can be expressed anonymously

  2. Can be stored by variables

  3. Can be stored by other data structures

  4. Have independent, deterministic names (such as syntax keywords)

  5. comparable

  6. Can be passed as a parameter

  7. Can be returned as a function result value

  8. Can be created at run time

  9. Can be expressed in serialized form

  10. Readable (in natural language)

  11. Readable (in a form that can be passed and stored in a distributed or running process in natural language)

1. Expression of serialization

What is this consciousness?

In JS, we’ll find the EVAL API. It is the ability to support serialized expression that makes it possible to execute string functions through eval.

2, summarize

JS’s father designed functions as first-class citizens to enable functional programming in the JS language.

Functions are first-class citizens, which means functions can do anything values can do.

Four, in JS, how to achieve functional programming?

Core idea: Eliminate statements through expressions.

There are several paths:

  1. Example of killing branch statements with expressions: A single if statement can be killed with a Boolean expression

  2. Eliminate loop statements by function recursion

  3. Replace values with functions (only the value returned by a function affects the operation of the system; a function call is really just an evaluation of an expression operation)

What are the disadvantages of functional programming with JS?

  • Lack of immutable data structures (JS is mutable except for primitive types)

  • Does not provide a native way to combine functions to generate new functions, requiring third-party support

  • Lazy sequences are not supported

  • Lack of tail-recursive optimization

  • JS functions are not really pure functional languages in the form of functions (e.g., javascript functions can write looping statements)

  • Expressions support assignment

1. Lack of tail recursive optimization

For functional programming, the lack of tail-recursive optimization is fatal. As of now, tail-recursive optimization is not well supported in browsers.

What is tail recursion?

As shown below:



Let’s take a look at the following two images:





In the first picture, tail recursion is not used, because n * Fatorial (n-1) is the last expression, and fatorial(n-1) is not the last expression. In the second figure, tail recursion is used, and the last expression is the recursive function itself.

The question is, why JS does not support tail recursion well?

The point I want to emphasize here is that any interpreter language that doesn’t explain the environment, i.e., the Runtime, is just a bunch of text. JS mainly runs in the browser and requires the browser to provide an interpretation environment. If the browser interprets the environment poorly for tail-recursive optimization of JS, it means that the tail-recursive optimization of JS is poor. Since there are so many browsers, visible JS still has a long way to go before it can achieve full tail-recursive optimization.

PS: Any requirement has a priority, and for browsers, tail-recursive optimization is obviously not a high priority. In my opinion, the low priority is the reason why so few browsers support tail-recursive optimization so far.

reference

1. Reference links

  • Symbols: abstract, semantic

  • Typescript layout solutions Functor, Applicative, and Monad

  • Church-turing thesis and lambda calculus

  • Why Monad?

  • Why Y?

Second, reference books

  • A guide to JavaScript functional programming

  • Scala functional programming

  • Haskell’s Guide to Fun Learning

  • Other E-books

The future, can be

In this paper, some theoretical knowledge of functional programming has been clearly described by way of explanation and question. Limited by space, some details cannot be developed. If you have any questions, please contact me to communicate and make progress together.

Now the front end is still in rapid development. Function API from recent React Hooks to Vue 3.0. We can feel the growing influence of functional programming.

For the foreseeable future, knowledge of functional programming requires a clear cognitive framework in mind.

Finally, my personal comments:

JavaScript will eventually revert to doing most things as functions.

For more content, please pay attention to vivo Internet technology wechat public account

Note: To reprint the article, please contact our wechat account: LABs2020.