The National Day

I wish: my motherland and I, of course, and you friends, happy National Day ha! National DaybuffBlessings,bugBack away.

I have not updated the article for four months 😂, there are some objective factors, but I came back ️.

Why write this article

Because I wrote an article earlier:

How to Write High Quality Functions — Get through Ren And Du’s Two Chapters

When I look at the article now, I find that some of the ideas don’t go far enough and don’t have that penetrating sense of immediate essence. Therefore, I want to reintroduce the theory of functional programming to a high – latitude overview.

In this article, I will use background and questions to explain the nature, purpose, context and other aspects of functional programming. Please follow me.

Overall introduction to the article

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.

original

This article is published on vivo Internet Technology wechat official account:

Link: mp.weixin.qq.com/s/EWSqZuujH…

Author: Yang Kun. Of course is my own 😂, nuggets version more funny some.

Here is a brief list:

background

  1. The history of computers and programming languages

10 questions of functional programming

  1. Why do functional languages exist? How did functional languages come about? What is the point of its existence?
  2. lambdaWhat is the calculus system?lambdaWhat exactly is it about?lambdaWhat does it have to do with the delta function? Why will there belambdaCalculus 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. In accordance with theFPIdeas, 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?

JavaScript5 questions of functional programming

  1. Why should functional programming be avoidedthis
  2. JavaScriptIf the function is a first-class citizen, you can getJavaScriptIs it functional? Why do you sayJSIs it a polymorphic language?
  3. whyJSFunctions can be used internallyforCycle?
  4. JSThe function is first-class citizen. What is consciousness? What is the purpose of this?
  5. withJSWhat are the disadvantages of functional programming?

conclusion

  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.

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.

David Hilbert

Click on TP introduction: David Hilbert

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

The best thing about Hilbert, in my opinion, is that:

He encouraged people to mechanize the proof process, because then machines could deduce a lot of theorems from formal language.

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

Alan Matheson Turing

Click on TP introduction: Alan Matheson Turing

Alan Matheson Turing was called 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 picture, we can see that each small 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

Click on TP introduction: Alonzo Church

Alonzo Church, PhD supervisor of Alan Matheson Turing.

His greatest achievement was:

Invented the lambda calculus.

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

Click on TP introduction: Von Neumann

Von Neumann is known as the father of the computer.

He proposed the von Neumann architecture:

From the above picture, 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 message:

As we know, the underlying instructions of the computer are composed of 0 and 1, and various calculation operations can be completed 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.

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.

Say something about 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 as follows:

Was there anything in the Turing and Lambda models that one model could represent that the other could not?

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 is a programmable computer.

Why programmable

Perl language designer Larry Wall said:

Good programmers have three great 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 also reflect incisively and vividly.

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 、XMLData Design language.
  3. In programming languages, it is divided into declarative and declarative.
  4. In the explanatory formula, including functional, logical, and so on, in factMySQL. It’s a logical language that does things 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.

The history of simple programming languages

The chart above is pretty straightforward, going back to 1995.

The timeline looks something like this:

xxx —> xxx —> …. —> JavaScript …

Fast forward to 1996 and JavaScript is born!

JavaScript was born!

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 Nguyen Yifeng

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

  1. First feeling: abramovich is rightJavaNo interest at all.
  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: Roman abramovich borrowedSchemeLanguage, which elevates functions to first-class citizen status, letsJSYou have the ability to do functional programming. plantedJSSeeds for functional programming.
  4. Fourth feeling:JSYou can program both functionally and object – oriented.

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.

conclusion

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.

Repeat the important things three times: operation, operation, operation.

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 a formal system:

Simple mathematical rules can be used to express real systems.

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:

Memory is modified 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

From the linguistic classification:

These are two different types of computing paradigms.

From the aspect of hardware system:

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.

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.

Light in the dark

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. Feel the charm of the symbols in the image.

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.

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.

conclusion

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? What exactly does lambda say? What does lambda have to do with functions? Why the Lambda calculus system?

The purpose of lamda’s birth

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.

A brief introduction to Lamda

  1. A system for studying function definition, function application, and recursion.
  2. The number language is based onlambdaAn operation paradigm produced by an operation.

The 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.

Function 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-2*x+1You can view it as a functionf(x)The definition of phi can be viewed as a functiong(x)The variablex-1The call.

After understanding the above points, we will find:

The semantics of function in mathematics are not clear, and it is difficult to express the structure of function. The solution was provided by Church, who proposed the lambda(λ) calculus.

Lambda (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: Just to be clear, a function in a functional language is a lambda, which is the same as a function in a common language like C

Function is two different things.

Take a chestnut

λ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 below when x is 1

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

To apply (or call) the procedure, assign the value of a variable to x in the expression and remove λ < variable > as follows

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

Multiple variables

Lambda x. lambda y.x + y

X =1, y=2, the call is as follows

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

As you can see, the return value of a function can also be a function, so the hierarchy of different functions is solved, and higher-order functions are used here. In functional programming languages, this rule holds when functions are first-class citizens

conclusion

If you think about it, you’ll find the Lambda calculus system, concise and elegant. It can be called the smallest general-purpose programming language. The building process of λ calculus system is the building process of a programming language from scratch. Every complex λ expression in the whole system is glued together by λ abstraction, application, and parentheses.

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.

conclusion

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 does the word function mean in functional languages, or in functional programming? What is it capable of?

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

operator

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

The function holds 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.

conclusion

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.

What are the key features of functional programming?

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.

Referential transparency

Definition:

An expression in any program that conforms to referential transparency can be replaced by its result without changing the meaning of the program.

Meaning:

Make the code more derivable and can be directly translated into results.

Here’s an example:

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.

purity

Definition:

The same output is returned for the same input.

Advantages:

  1. testable
  2. No side effect
  3. You can parallel code
  4. Can be cached

Lazy evaluation versus non-lazy evaluation

Definition:

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

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.

Non-lazy evaluation:

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

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

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

combination

Currie,

Functional programming – Functor, Applicative, 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.

Click on TP: Typescript layout solutions Functor, Applicative, and Monad

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

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

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.

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

On the third point, my personal feelings are as follows:

Functional programming requires you to change from an 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.

We can compare these high-level knowledge points of functional programming with object programming inheritance, etc., and find:

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

conclusion

I will 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.

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

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 has side effects, but if you don’t throw an exception, what do you throw instead?

Speaking of which, 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 common, and the main reasons are:

We stand on the theoretical foundation of imperative language to understand functional language.

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:

Is the logic that describes expression evaluation, or assists expression evaluation.

JavaScript5 questions of functional programming

Why should this be avoided for functional programming

There are two main reasons:

  1. JS 的 thisIt has multiple meanings and complex usage scenarios.
  2. thisIt doesn’t depend on the code inside the function.
  3. All data should be supplied to the function as arguments, whilethisNot following the rules.

Why can we 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.

JS function is first-class citizenship 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)

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.

conclusion

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.

How to do functional programming in JS?

Core idea: Eliminate statements through expressions.

There are several paths:

  1. Eliminate branch statements by expression example: singleifStatement, which can be eliminated by 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?

  1. Lack of immutable data structures (JSEverything is mutable except the primitive type.)
  2. Does not provide a native way to combine functions to generate new functions, requiring third-party support
  3. Lazy sequences are not supported
  4. Lack of tail-recursive optimization
  5. JSIs not a true pure functional language function form (e.gJSYou can write loops in a function.
  6. Expressions support assignment

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 look at the next two pictures

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

Refer to the link

  • Symbols: abstract, semantic
  • Typescript layout solutions Functor, Applicative, and Monad
  • Church-turing thesis and lambda calculus
  • Why Monad?
  • Why Y?

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.

communication

Follow my Nuggets blog or Github for updates on the upcoming series.

Nuggets series of technical articles summarized below, if you feel good, click a star to encourage oh.

github.com/godkun/blog

I am the source terminator, welcome technical exchange.

You can also go to the front end brainstorm group. – Dazzle Group and brainstorm together.

The language of the wind

Don’t say anything, just say:

I wish you a happy National Day buff, away from bugs, happy seven day holiday oh.

Finally: respect the original, reprint please indicate the source ha 😋