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 :

  1. Basic Form of expression
  2. Combine Methods
  3. 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 .

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 :

  1. Evaluation subprocess
  2. Apply the value of the expression to the new procedure

    for example :
>>> (3*((2*4)+(3+5)))

We can use tree structure

graph TD
root["3*((2*4)+(3+5))"]--> LT["3"]
root["3*((2*4)+(3+5))"]--> RT["((2*4)+(3+5))"]
RT["((2*4)+(3+5))"]-->RTL["(2*4)"]
RT["((2*4)+(3+5))"]-->RTR["(3+5)"]
RTL["(2*4)"] -->RTLL["2"]
RTL["(2*4)"] -->RTLR["4"]
RTR["(3+5)"] -->RTRL["3"]
RTR["(3+5)"] -->RTRR["5"]

The combination of processes

  1. Numbers and arithmetic operations are raw data and processes .
  2. Combinatorial nesting provides a way of combinatorial operation .
  3. 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

\[\sqrt 2 \approx 1.414
\]

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 ]:

graph TD
root["sqrt"]--> Node["sqrt_iter"]
Node["sqrt_iter"]-->LT["good_enough"]
Node["sqrt_iter"]-->RT["improve"]
RT["improve"] --> improve_guess
LT["good_enough"] --> square
LT["good_enough"] --> abs

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

Linear iteration and recursion

Consider factorials

\[n!=n·(n-1)·(n-2)···3·2·1
\]

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

\[n!=n·(n-1)!
\]

Then we know the coding ideas in two cases :

  1. 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 :

\[product \leftarrow counter \times product \\
counter \leftarrow counter + 1
\]
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 :

\[GCD(a,b)=GCD(b,r)
\]

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

\[GCD(206,40)\\
=GCD(40,6)\\
=GCD(6,4)\\
=GCD(4,2)\\
=GCD(2,0)\\
=2
\]
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 :

\[\frac{1}{1·3}+\frac{1}{5·7}+\frac{1}{9·11}+···\approx \frac{\pi}{8}
\]
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

\[\int_{a}^{b}f dx=[f(a+\frac{dx}{2})+f(a+dx+\frac{dx}{2})+f(a+2dx+\frac{dx}{2})+···]dx
\]

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 :

\[f(x),f(f(x)),f(f(f(x))),...
\]

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

\[f(x)=1+\frac{1}{x}
\]

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))

SCIP: The construction process is abstract -- More articles on object-oriented interpretation

  1. SICP— Chapter one The construction process is abstract

    SICP  Structure And Interpretation Of Computer Programs Chinese language first 2 edition Two parts   S and I Chapter one The construction process is abstract 1, The basic elements of programming 2, too ...

  2. From ordinary functions to object methods ------Windows Object oriented encapsulation of window procedures

    Original address :http://blog.csdn.net/linzhengqun/article/details/1451088 From ordinary functions to object methods ------Windows Object oriented encapsulation of window procedures Start ...

  3. python Comparison of process oriented and object oriented

    Process oriented VS object-oriented Process oriented programming : The core is process , Process refers to the steps to solve the problem , That is, what to do first and then ...... Process oriented design is like elaborately designing a pipeline , It's a mechanical way of thinking . Advantage is : Complexity ...

  4. Process oriented vs object-oriented

    Some process oriented abstracts from the Internet vs. Object oriented analysis , Here's a brief record , I'll continue to sort it out later . Why is object-oriented analysis method ? Because the real world is so complex and changeable , Process oriented analysis cannot be realized . Process oriented Adopting process orientation requires understanding the whole ...

  5. C++ Tectonic process and deconstruction process

    1.C++ The process of construction and deconstruction , It's similar to the process of dressing and stripping . Dressing is : Wear underwear first , Put on your coat . Strip is : Take off your coat first , Take off your underwear .C++ Construction process : First, call the parent class construction method , Then call the subclass construction method .C++ The process of deconstruction : First, call the subclass destructor method ...

  6. from C++ Object memory layout and construction process C++ Package in 、 Inherit 、 polymorphic

    One . Encapsulate the memory layout of the model Members of common class objects may contain the following elements : Built in type . The pointer . quote . Combine objects . Virtual functions . Another angle of classification : Data member : static state . The static Member functions : static state . The static . Virtual functions 1. Only fields with built-in types ...

  7. JS It's process oriented 、 Object oriented or object-based ? Object oriented code representation

    One . problem javascript It's object-oriented , Or process oriented ? Based on what the object means ? object : It refers to the abstraction of a certain kind of things , Abstract the common characteristics and behaviors of this kind of things ( That is, properties and methods ), Those who have the same properties and methods ...

  8. C++ note 005: Using process oriented and object-oriented methods to solve circular area

    Original notes , Reprint please indicate the source ! Click on [ Focus on ], Attention is also a virtue ~ It's the end of the first hello world After procedure , Let's use process oriented and object-oriented methods to solve the problem of circle area , In order to have a clearer understanding of object-oriented and process oriented . ...

  9. essential C++ Description of process oriented and object oriented in

    I was reading yesterday essential C++ See an example of the difference between process oriented and object-oriented , It feels good . recorded .... This example is about cameras . The camera has three properties , It's a position control : Usually use 3 Floating point data to represent its ...

  10. swift note ( fourteen ) —— Construction process

    Construction process To generate classes . Structure . Enumeration, etc , And the preparation process , It's called the construction process . For this process , We usually define a method to finish , This method is called a constructor . Of course, its reverse process , It's called a destructor , Used to do some cleanup before the instance is released ...

Random recommendation

  1. [slim] Slim - Faster, lightweight, a enginer for Ruby

    URL: http://slim-lang.com/ Example: doctype html html head title Slim Examples meta name="keywo ...

  2. php Determine whether It's mobile access

    // Judge whether it is a mobile phone function is_mobile() { $user_agent = $_SERVER['HTTP_USER_AGENT']; $mobile_agents = Array(& ...

  3. 【BZOJ】【3530】【SDOI2014】 Count

    AC automata / digit DP orz zyf Good question = = At the same time, it deepened my understanding of AC automata ( This should be called Trie It's a picture …… Make it up on the outside !) And digital DP The understanding of the …… But it's really weak if you can't write it by yourself …… /************* ...

  4. Why URL code

    We all know Http The transmission of parameters in the protocol is "key=value" This is simply right for the form of , If you want to transfer multiple parameters, you need to use “&” Symbols divide key value pairs . Such as "?name1=value1&a ...

  5. RandomAccessFile&amp;IO flow &amp; Sort &amp; methodology

    RandomAccessFile&IO flow & Sort & methodology We always think that history is a very distant thing , It has nothing to do with us , I also feel that history is hidden in the old books of the library . However , Each of us has a real history . ...

  6. Three level menu python How to write it ( Recursive writing )

    data structure : menu = { ' Beijing ':{ ' haidian ':{ ' Wudaokou ':{ 'soho':{}, ' NetEase ':{}, 'google':{} }, ' Zhongguancun ':{ ' Iqiyi ':{}, ' Car home ':{}, ...

  7. [ I understand it ]Javascript Prototype and prototype chain of

    One . The definition of prototype and prototype chain Prototype : Objects that provide shared properties for other objects notes : When a constructor creates an object , In order to solve the problem of object property reference , The object implicitly references the constructor's "prototype" attribute . Procedure passed const ...

  8. 【BZOJ5416】【NOI2018】 Bubble sort ( Dynamic programming )

    [BZOJ5416][NOI2018] Bubble sort ( Dynamic programming ) Topic BZOJ Luogu UOJ Answer key There are two ascending subsequences , And the length of the longest descending subsequence does not exceed \(2\)... And then it's violent \(dp\) mixed ...

  9. IDEA establish SpringBoot project

    establish SpringBoot There are three ways : Mode one :( Commonly used way )

  10. 【BZOJ4477】[JSOI2015] String tree (Trie Trees )

    [BZOJ4477][JSOI2015] String tree (Trie Trees ) Topic BZOJ Answer key For each point, maintain all strings from it to the root node \(Trie\), Obviously, it's easy to write after persistence . And every time you ask, it's \(u+ ...