Mental activity , In addition to trying to generate all kinds of simple cognition , It is mainly manifested in the following three aspects ：

(1) Combine some simple cognition into a compound cognition , From this we can produce all kinds of complex cognition .

(2) Put two cognitions together , No matter how simple or complex they are , In doing so , It doesn't make them one . And then we get a sense of their relationship .

(3) Separate the knowledge concerned from all other knowledge that exists with them in practice , This is abstraction .This is how all the general knowledge is obtained .

--John Locke Essays on human understanding ,1960

This paper is about SICP Some notes of , It is used to record some different views on computer programs , The purpose of this paper is to introduce the program design through the thinking of mathematical calculation .SCIP It's a book about computing , The calculation process is concerned with the operation of data , The purpose of creating the program is also for data processing , In the code is the elaborate arrangement of symbolic expression , The calculation process is carried out precisely and accurately , Beginners of programming are like wizard apprentices , Learn how to understand and predict the effects of spells , Learn and validate results , however , Learning programs is far less dangerous than witchcraft .SICP All the code practices in are scheme(scheme by Lisp Some version of ,Lisp Is still AI The language with the highest theoretical calculus in the field ), The execution process is the code interaction process of interpreter , Run the program according to the same interpreter principle , It can also be used. python Realize the exercises in the book .

#### The basic elements of programming

Every programming language has three mechanisms ：

- Basic
**Form of expression** **Combine**Methods**abstract**Methods

Basic expressions are the simplest individuals that programming languages care about , And the method of combination is to combine these simple individuals into complex elements . Then abstract the complex elements , You get a unit , The unit can also be combined as a simple individual , Step by step, a complete program is formed , That's why many books are bound to mention ` recursive `

.

In the program , There are two basic elements ： Process and data , The data is what the user wants to operate “ thing ”, And the process is a description of how to operate these rules , Any powerful programming language must express basic data and basic processes , You also need to provide methods for combining and abstracting processes and data . From the perspective of programming today , Using classes in object-oriented programming -- Property and method conventions .

##### expression

The easiest way to get started , Watch the code interact with the interpreter , Suppose the keyboard has entered a ` expression `

, The interpreter displays the evaluation result of the expression , The basic expression is number , for example , Give a number `486`

:

```
mt@mt-P243:~$ python
Python 2.7.17 (default)
[GCC 7.5.0] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 486
486
```

Combine expressions that represent numbers , Form a compound expression

```
Python 2.7.17 (default)
[GCC 7.5.0] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 1000-7
993
>>> 993-7
986
>>> (3*((2*4)+(3+5)))+((10-7)+6)
57
```

For complex arithmetic expressions , Explain that it also operates according to the basic cycle , Read in - evaluation - Print

###### Naming and environment

By naming the data , By using names to do operations , Call the name identifier a variable , Store data in variables . Solve the naming problem , The program is more than half done , The most basic expression is to assign values to variables , At this point, the process of data to variable is also an abstraction ：

```
>>> size = 2
>>> size
2
```

##### Combine

There are two steps to evaluating Portfolio ：

- Evaluation subprocess
- Apply the value of the expression to the new procedure

for example ：

```
>>> (3*((2*4)+(3+5)))
```

We can use tree structure

#### The combination of processes

- Numbers and arithmetic operations are raw data and processes .
- Combinatorial nesting provides a way of combinatorial operation .
- Definitions that associate names with values provide a limited means of limiting abstraction

```
a = (3*((2*4)+(3+5)))+((10-7)+6)
```

#### example ： Using Newton's method to find the square root

computational procedure ：

step 1 | guess | merchant | Average |
---|---|---|---|

(1) | 1 | 2/1=2 | (2+1)/2=1.5 |

(2) | 1.5 | 2/1.5 = 1.333 | (1.333+1.5)/2=1.4165 |

(3) | 1.4165 | 2/1.4165 = 1.412 | (1.4165+1.412)/2=1.41425 |

(4) | 1.41425 | 2/1.41425 = 1.4142 | (1.41425+1.4142)/2=1.414225 |

If there are no restrictions , The calculation will go on , So in order to design a program to calculate the square root, consider the calculation steps

1) Guess first

2) Calculation quotient

3) Calculate the average as the next round guess

If there is no stop condition , So it's going to keep counting , If you look at the results of the calculation, you can see the guess value 、 And the average is getting closer and closer , If you agree on an error range , It can be used as the stop condition of calculation (`good_enough`

).

1) The termination condition of guess

```
def square(x):
return x*x
def good_enough(guess,x):
if abs(square(guess)-square(x))<0.001:
return True
else:
return False
```

2) and 3) Calculate the average , As the start of the next round of guessing , If it turns out to be good , End immediately , Otherwise keep guessing , The iterative process can be written as

```
def improve_guess(guess,x):
return (x/guess + guess)/2
def sqrt_iter(guess,x):
print(guess,x)
if good_enough(guess,improve_guess(guess,x)):
print('guess:'+str(guess))
return guess
else:
return sqrt_iter(improve_guess(guess,x),x)
```

The program can be written as

```
def sqrt(x):
return sqrt_iter(1.0,x)
```

Program decomposition [ Decomposition from original problem to subproblem ]：

「 Using many basic arithmetic operations , Combine operations , By defining various composite processes , Then we abstract the composite process 」

#### Linear iteration and recursion

Consider factorials

The same idea as Newton's method for finding the square root , In order to calculate the number of n Sub iteration , You need to consider n-1 Results of , The factorial can be written as

Then we know the coding ideas in two cases ：

- The first 1 Time n by 1

2) The first n Time To (n-1) Iteration

```
def factorial1(n):
if n==1:
return 1
else:
return n* factorial(n-1)
```

Look at things in a different way ,1*2 And then the result *3, Again *4, until n, So use a counter counter It can be written as the following iteration ：

```
def fact_iter(product, counter, max_count):
if counter>max_count:
return product
else:
return fact_iter(counter*product, counter+1, max_count)
def factorial2(n):
return fact_iter(1,1,n)
```

`factorial1`

The idea of expansion first and calculation later is adopted , and `factorial2`

The idea of calculation before expansion is adopted ,`factorial1`

It's called recursive computation ( The longer the expression is written ), and `factorial2`

The expression does not change during the calculation ,`factorial2`

One more variable is used to save the intermediate results , This iterative process is sometimes similar to the state variables mentioned in computational theory , The calculation process is the process of state transition , And there's another one ( There may be ) The shutdown process of .

##### greatest common divisor

The greatest common divisor of two integers (GCD) It is defined as the largest integer that can divide these two numbers , The algorithm is based on the following observations ： If r yes a Divide b The remainder of , that a and b The common divisor of is exactly b and r The common factor of ：

here , One GCD The problem of computing is reduced continuously to smaller and smaller integer pairs , for example

```
def remainder(a,b):
return a%b
def gcd(a,b):
if b==0:
return a
else:
return gcd(b, remainder(a,b))
```

##### Abstract with higher order function

The above process is a kind of abstraction , Some coincidence operations on numbers are described , But at the same time, it doesn't depend on a specific number -- Pass the number as a parameter into the function . People have an inevitable requirement for a powerful programming language , It's about being able to name public patterns , Create abstraction , And then work directly at the level of abstraction .

Process as a parameter ,

(1) Calculate from a To b The sum of the integers of ：

```
def sum_integers(a,b):
if a > b:
return 0
else:
return a + sum_integers(a+1,b)
```

(2) Calculate from a To b The sum of the cubes of the integers ：

```
def sum_cubes(a,b):
if a > b:
return 0
else:
return cube(a) + sum_cubes(a+1,b)
```

(3) Calculate the sum of the following sequences ：

```
def pi_sum(a,b):
if a > b:
return 0
else:
return 1/(a*(a+2)) + pi_sum(a+4,b)
```

It is obvious that , The three processes share a common fundamental pattern ： from a The function that calculates the terms that need to be added , There's also a way to provide the next a The value of the function , It can be described by a template

```
def sum_term(term, a, next, b):
if a>b:
return 0
else:
return term(a)+sum_term(term, next(a), next, b)
```

And when we calculate the sum of cubes ,`term(a)`

by `cube(a)`

,`next(a)`

For next item , According to this process , You can rewrite the above (1)~(3) Example

```
def inc(n):
return n+1
def cube(a):
return a*a*a
def sum_cubes(a,b):
return sum_term(cube,a,inc,b)
```

With the template above `sum_term`

, Take it as the basic unit , Other concepts can be formalized , For example, in a and b Calculate the approximate value of definite integral between

among `dx`

It's a very small value , You can translate the formula into

```
def integral(f, a, b, dx):
def add_dx(x):
return x + dx
return sum_term(f, a+dx/2, add_dx, b)*dx
```

##### use lambda Construction process

In the original `pi_sum`

Functional expression , Back to “ Its input value plus 4 The process of ” and “ Its input value plus 2 The process of the reciprocal of the product of ”, This process can use auxiliary functions , You can also use lambda expression ,python Medium `labmda`

The expression format is `lambda < Return value of expression >: expression `

```
lambda x:x+4
lambda x: 1/(x*(x+4))
```

In order to achieve and original `pi_sum`

The process of , have access to lambda Expressions and templates `sum_term`

Realize the same function

```
def pi_sum(a,b):
return sum_term(lambda x: 1.0 / (x * (x + 2)),a,
lambda x: x+4,b)
```

##### Find the fixed point of a function

The process of calling a function , Similar to the concept of compound function defined mathematically , If `f(x)=x`

Infinite Dolls , You can find a fixed point ：

For example, the golden section is the fixed point of the following function

The calculation process is as follows ：

```
tolerance = 0.00001
def fixed_point(f, first_guess):
def close_enough(v1,v2):
return True if abs(v1-v2)<tolerance else False
def try_guess(guess):
next_guess = f(guess)
if close_enough(next_guess,guess):
return next_guess
else:
return try_guess(next_guess)
return try_guess(first_guess)
print(fixed_point(lambda x:1+1/x, 1))
```