SiCp: abstraction of construction process -- object oriented explanation

adminmttt 2021-04-08 11:20:46
sicp abstraction construction process object

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 . From the perspective of programming today , Using classes in object-oriented programming -- Property and method conventions .


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

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-7
>>> (3*((2*4)+(3+5)))+((10-7)+6)

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

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
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):
if good_enough(guess,improve_guess(guess,x)):
return guess
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
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
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
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
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
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
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
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
return try_guess(next_guess)
return try_guess(first_guess)
print(fixed_point(lambda x:1+1/x, 1))

  1. Java 学生成绩管理系统课程设计,附源码!
  2. Java arbitrary audio to MP3
  3. DNS of docker
  4. Docker - build log monitoring system
  5. SSM + MySQL + Maven + Shiro WMS
  6. Top 10 reasons to fall in love with java!
  7. 一本关于HTTP的恋爱日记
  8. 【RocketMQ源码分析】深入消息存储(3)
  9. SpringCloud+Nacos实现服务配置中心(Hoxton版本)
  10. SCIP:构造数据抽象--数据结构中队列与树的解释
  11. SCIP:构造过程抽象--面向对象的解释
  12. 使用 docker 进行 ElasticSearch + Kibana 集群搭建
  13. Spring IOC 特性有哪些,不会读不懂源码!
  14. [DB Bao 41] use of PMM -- monitoring mysql, PG, mongodb, proxysql, etc
  15. Spring Cloud 升级之路 - 2020.0.x - 3. Undertow 的 accesslog 配置
  16. [DB Bao 42] MySQL high availability architecture MHA + proxysql realizes read-write separation and load balancing
  17. [DataGuard] recovery of physical DG in case of losing archive files in main database (7)
  18. MyBatis(3)Map和模糊查询拓展
  19. 【TTS】AIX-&gt;Linux--基于RMAN(真实环境)
  20. 【TTS】传输表空间AIX-&gt;linux基于rman
  21. 【TTS】传输表空间AIX asm -&gt; linux asm
  22. 【TTS】传输表空间Linux asm -&gt; AIX asm
  23. 【DB宝40】MySQL高可用管理工具Orchestrator简介及测试
  24. 【TTS】传输表空间Linux -&gt;AIX 基于rman
  25. 一本关于HTTP的恋爱日记
  26. 【RocketMQ源码分析】深入消息存储(3)
  27. SpringCloud+Nacos实现服务配置中心(Hoxton版本)
  28. SICP:构造过程抽象--面向对象的解释
  29. 3w 字长文爆肝 Java 基础面试题!太顶了!!!
  30. Spring Cloud 升级之路 - 2020.0.x - 3. Undertow 的 accesslog 配置
  31. win10卸载mysql5.7
  32. MySQL 批量插入,如何不插入重复数据?
  33. k8s cronjob应用示例
  34. 非常规方法,轻松应对Oracle数据库危急异常
  35. Oracle hang 之sqlplus -prelim使用方法
  36. 如何全文搜索oracle官方文档
  37. Java student achievement management system course design, with source code!
  38. win10安装mysql8.0
  39. 手把手教你写一个spring IOC容器
  40. JAVA 中的异常(1)- 基本概念
  41. A love diary about http
  42. navicat连接win10 mysql8.0 报错2059
  43. [rocketmq source code analysis] in depth message storage (3)
  44. Implementation of service configuration center with spring cloud + Nacos (Hoxton version)
  45. SCIP: constructing data abstraction -- Explanation of queue and tree in data structure
  46. SCIP: abstraction of construction process -- object oriented explanation
  47. Using docker to build elasticsearch + kibana cluster
  48. What are the spring IOC features? I can't understand the source code!
  49. Spring cloud upgrade road - 2020.0. X - 3. Accesslog configuration of undertow
  50. 导致Oracle性能抖动的参数提醒
  51. 风险提醒之Oracle RAC高可用失效
  52. 小机上运行Oracle需要注意的进程调度bug
  53. Oracle内存过度消耗风险提醒
  54. Oracle SQL monitor
  55. 使用Bifrost实现Mysql的数据同步
  56. 揭秘Oracle数据库truncate原理
  57. 看了此文,Oracle SQL优化文章不必再看!
  58. Mybatis (3) map and fuzzy query expansion
  59. Kafka性能篇:为何这么“快”?
  60. 两个高频设计类面试题:如何设计HashMap和线程池